Homework #7 Solution

$30.00

Description

1. Dijkstras Algorithm (3 points)

Run Dijkstras algorithm on the graph G1 to compute the shortest paths from a to all of the other vertices.

Image missing

2. NP-Hardness Reduction (6 points)

Let’s de ne a new problem: The satis ability problem with at most 5 copies of each variable (SAT5C):

Input: a boolean formula f with m clauses over n variables. No variable appears in more than 5 clauses.

Output: TRUE if there is an assignment to the variables that makes the formula true, FALSE otherwise.

    1. (1 point) Is the following boolean formula satis able (justify your answer): Yes, setting x1 = F , x2 = F , and x3 = F

(:x3 _x2)^(x1 _x3 _:x2)^(:x3 _:x2)^(:x1 _x3)^(x1 _:x3)^(x3 _:x2) (T _ F ) ^ (F _ F _ T ) ^ (T _ T ) ^ (T _ F ) ^ (F _ T ) ^ (F _ T )

Each clause evaluates to T , so the formula evaluates to TRUE.

    1. (1 point) Is the above an example of the SAT5C problem? Why or why

not?

No, x3 is in 6 clauses, which is greater than the allowable 5 clauses.

(4 points) Show that SAT 5C is NP-hard by giving a polynomial time

reduction from SAT to SAT 5C (i.e., SAT SAT 5C):

(Hint: you can ensure two variables have the same truth value by adding 2 additional clauses each of which have two variables in them)

Given a formula f with m clauses over n variables as input to SAT, a reduction to SAT5C can be constructed trivially if all n variables appear in 5 or less clauses. Otherwise, inputs for SAT5C may be constructed as

follows:

Let k = the number of appearances of a variable xi in f

fSAT 5C = fSAT [ mSAT 5C

mSAT 5C = mSAT such that each occurrence of xi 2 nSAT : k > 5 is replaced by the k new variables in nSAT 5C conjoined with, for each new variable xj for j = 1; 2; :::; k 1, (xj _ 😡j+1), nally conjoined with (xk 1 _ 😡1)

nSAT 5C = nSAT where for each xi 2 nSAT : k > 5 is replaced by k new variables not in nSAT for each of the k appearances of xi

The replacement of a variable with k > 5 appearances with k new vari-ables and the resulting conjunction with the clauses described in mSAT 5C results in the removal of the o ending variable replaced by k new vari-ables all with < 5 appearances. The additional clauses ensure that each of the new variables have the same truth value (the truth value of the o ending variable) because for all clauses in the chain to be true, each of the new variables must have the same truth value.

  1. P vs. NP (14 points)

Once again let’s imagine company X has hired you as a software engineer. In this case, the company has several databases of customer information it manages for its resale business.

The business tracks items that customers want to sell and ones they want to buy (See example gure 1). It also tracks \fair” prices for buying and selling each of the items (See example gure 2). Naturally the buy price will be higher than the sell price since the company will keep some money a buyer pays as pro t.

Below is a list of features the company wants you to look into adding. Speci – cally, identify whether the given problem can be solved in polynomial time. If it can, give a short description of an algorithm to compute it (feel free to use algorithms and data structures we learned earlier this semester in your jus-ti cation). Alternatively, if you believe the problem is NP-hard, give a short justi cation why (this doesn’t need to be a proof but try to point out a similar NP-hard problem).

You can assume there are n people in the Figure 1 database and m items in

Fig. 1. Customers and their items

Customer

Username

Rating

Date of Birth

Wants to Sell

Wants to Buy

Name

Kenneth

KRosen

50

1950/02/03

Item #0980

Item #0351

Rosen

Item #1063

Item #2048

Alonzo

LambdaC

70

1903/06/14

Item #1085

Item #1702

Church

Item #2048

Stephen

PvsNP

20

1939/12/14

none

Item #0980

Cook

Item #1702

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

Fig. 2. Prices of items

Item #

Item Description

Purchase

Sell Price

Price

Item #0351

Used Discrete Math Text Book

$45

$20

Item #0980

Used Graphing Calculator

$60

$27

Item #1085

Used Book of GRE Practice

$6

$2

Problems

.

.

.

.

.

.

.

.

.

.

.

.

the Figure 2 database. You can treat these databases as 2d arrays (there are some additional caveats for working with real databases that we won’t worry about here). You can assume each customer’s \Wants to Buy” and \Wants to Sell” information are stored in linked lists of length at most m.

  1. Process Transaction I: For a given item nd a customer with it on their sell list.

Assuming constant time to access a customer’s info in the rst database, by linearly searching through each customers sell list an item may be found in polynomial time. In the worst case using this approach, the item is not on any customer’s sell list and thus the algorithm would nish after searching through every customer’s sell list in O(nm) time since each of the n customers could potentially have m items on their sell list.

  1. Process Transaction II: For a given item nd the highest rated cus-tomer selling that item.

This requires a simple modi cation to the rst algorithm, where we must search every customer no matter what and, if the item is found in a cus-tomer’s sell list, update a variable keeping track of the maximum rating

found for a customer selling that item. Thus, the running time for this algorithm would also be O(nm) polynomial time.

  1. Shopping Buddy I: Check if there are 3 users where each pair of users have at least one item in common which they want to buy.

Example: These 3 people all share at least one item in their buy list

f Item #0927, Item #1085, Item #2048 g f Item #1085, Item #1555 g

f Item #1555, Item #1702, Item #2048, Item #3730 g

This problem is NP-hard, it is identical to nding a size three clique in a graph. Letting each customer represent a vertex, add an edge between two vertices if they share an item on their buy list. Then we are look-ing for three vertices where each is adjacent to the other two. This is equivalent to nding a size three clique, so this problem is also NP-hard.

  1. Shopping Buddy II: Check if there is a set of k users where each pair of users have at least one item in common which they want to buy. This is the same problem as Shopping Buddy I except, instead of three users, we are looking for any k of the n users that have at least one item in common on their buy list. Thus, this problem is equivalent to nding a clique of size k and thus also NP-hard.

  1. Impostor Usernames: Find all pairs of usernames where they share a subsequence of k characters.

(for a real application k would vary based on the length of the user-names but for the sake of simplicity we are assuming a static value).

Example: Some pairs of names which share at least 5 characters

  • SipserToC, SimpsonToC )

  • KRosen2000, JRosen1999 )

  • PvsNP, P vs NP )

This is similar to nding the longest common subsequence which is op-timized using dynamic programming, except we are trying to nd a sub-sequence of length k between pairs of usernames instead of the longest common subsequence. Using dynamic programming to nd the longest common subsequence between two usernames, we can examine the result and see if the LCS is at least k. This algorithm runs in O(st) where s and t are the lengths of the two usernames respectively. Since we are search

for all pairs of usernames we must do this for every pair of usernames resulting in a runtime of O(n2st) which is polynomial in runtime. s and t may change between usernames, but it should be insigni cant especially if there is a limit to username length.

  1. Equal Trade Problem: For a given customer check if there is a subset of items that they want to buy which is equal in value to a subset of items they want to sell.

Hint: Check out Knapsack and Subset Sum problems.

This is almost identical to the Subset Sum problem. Given the customer’s buy and sell list, create a combined list of both lists while setting the customer’s buy values to their respective negatives. Now we are simply looking for a subset of items in this set that will sum to zero, which means that a subset of the buy list is equal in value to a subset of the sell list if there is a subset in the combined list that sums to zero. Since the Subset Sum problem and this one are equivalent and the Subset Sum problem is NP-Complete, then this problem is NP-Hard.

  1. Gift Exchange: Check to see if there are k users where every user can give an item from their sell list to another user who has it on their buy list. All of the k people should give exactly one gift and receive exactly one gift.

Start by building a directed graph where each vertex is a customer, add a directed edge from one customer to another if the furst customer has an item on their sell list that the other has on their buy list. This can be done in polynomial time since there are at most m items of a buy list and for each of those you must check each of the m items of the

n 1 other customers for each of the n customers, resulting in a time O(n2m2). Then, to solve the problem we simply use DFS to look for a simple cycle of length k. If such a cycle exists then there are k users that will all receive exactly one gift and give exactly one gift, which would form a simply cycle in this graphical representation. Since DFS and cycle detection are also polynomial in runtime, this problem may be solved in an overall polynomial runtime.