[SOLVED] CS COMP3121/9101

COMP3121/9101

Algorithm Design

Copyright By Assignmentchef assignmentchef

Problem Set 6 Selected Topics

[K] key questions [H] harder questions [E] extended questions [X] beyond the scope of this course

1 SECTION ONE: STRING MATCHING 2

2 SECTION TWO: LINEAR PROGRAMMING 3

3 SECTION THREE: INTRACTABILITY 6

Problem Set 6 SECTION ONE: STRING MATCHING

SECTION ONE: STRING MATCHING

[K] Exercise 1. Consider the text T = dbebfjcgfdfj and pattern P = dh, taken from the alphabet {a, . . . , j}
of size d = 10. We will use the Rabin-Karp algorithm to search for matches of P in T , choosing p = 11.

By close inspection, you will observe that P does not appear as a substring of T even once (indeed, T does not contain
any instances of h). However, the Rabin-Karp algorithm sometimes produces false positives due to hash collisions.

How many false positives are there? That is, letting Ts = tsts+1 for various starting points s, how many times do we
have that H(Ts) = H(P ) but Ts = P?

[K] Exercise 2. Let s = 01011011010 be a string (of length 11) from the alphabet = {0, 1}.

(a) Compute the transition function for the pattern s, i.e. find (k, a) for all 0 k 11 and a .

(b) Draw the corresponding state transition diagram. You may omit arrows to state 0.

(c) Compute the prefix function for the pattern s, i.e. find (k) for all 1 k 11.

[H] Exercise 3. Since the Rabin-Karp algorithm functions on a one-dimensional array, explain how you would extend
the Rabin-Karp method to look for an mm pattern in an n n array of symbols.

[H] Exercise 4. Let T and T be strings of length n. Describe an O(n) time algorithm to determine if T and T are
cyclic rotations of one another. For example, T = car and T = arc are cyclic rotations of each other, while T = arc
and T = acr are not.

[H] Exercise 5. Given a list of strings A and a prefix string s, describe an algorithm to count the number of strings
whose prefix matches s.

[E] Exercise 6. Given two patterns T and T , describe how you would construct a finite automaton that determines
all occurrences of either T or T .

COMP3121/9101 Term 3, 2022 2

Problem Set 6 SECTION TWO: LINEAR PROGRAMMING

SECTION TWO: LINEAR PROGRAMMING

[K] Exercise 7. Manufacturing produces speakers for hi-fi sets in two types, product A and product
B. Two types of processes are needed for their production. The first process combines all machining operations, and
the second consists of all assembly operations. Each unit of product A requires 4 labor-hours of machining and 2
labor-hours of assembly work, whereas each unit of product B requires 3 labor-hours of machining and 0.5 labor-hours
of assembly work. Manufacturing capacity available during the coming production week is 2400 labor-hours, and the
assembly work capacity available for the same week is 750 labor-hours.

Previous sales experience indicates that product B sells at least as much as product A and that there is already an
order of 100 units for product A to be produced during the next period. Furthermore, all products produced during the
week can be sold during the same week. Products A and B provide $7.00 and $5.00 profit per unit sold, respectively.
Management would like to know what quantities of A and B should be manufactured during the next production week
in order to maximize the total profit. The following table summarizes the data.

Operation Product A Product B Capacity
Machining (labor-hours) 4 3 2400
Assembly (labor-hours) 2 0.5 750
Profit per unit ($) 7 5

(a) Write down the linear program P representing this problem in standard form, making sure to define all variables
and constraints involved.

(b) Write down the dual P of the problem P .

(c) Find the optimal value of the objective function and the quantities to produce in order to maximize the total

Hint. You can use MATLAB or other software to find the solution, however, there is a way to compute it analytically,
maybe draw a plot?

[K] Exercise 8. Suppose that there are 3 farmers each with a square of land with the side length of si and center
of the land at (xi, yi) However, due to the current drought, the farmers need to drill a single well to extract water and
keep the crops alive. The wells position must be chosen such that it is within the land of all 3 farmers. The amount of
water that is extractable from a coordinate (x, y) can be written as a w = 4x + 6y and you may assume that no land
will include negative coordinates.

(a) Is there always a valid solution for the position of the well? Explain your answer.

(b) Suppose a valid solution exists, derive the standard form LP formulation P that finds the correct position to drill
the well such that most amount of water can be extracted while satisfying the requirement.

(c) How can you extend the definition of this problem to n farmers?

[K] Exercise 9. You are the boss of a large manufacturing company and you wish to produce a certain amount of
items to sell to the customers while making as much profit as possible.

Based on the technical constraint, you can choose to produce any amount of n different types of items each with
a cost of ci.

Your accounting department also gives an estimate of the profit for each unit of item i is pi and your budget is
C in total.

Manufacturing each item i also produces a certain amount of pollution. Based on the constraint set by EPA,
there are k many different types of pollution measures and limit you must adhere to for each pollution measure

COMP3121/9101 Term 3, 2022 3

Problem Set 6 SECTION TWO: LINEAR PROGRAMMING

be denoted by Li.

Producing each item i will cause any amount of pollution for each of the different measures, we denote this by
(w(i,1), w(i,2), . . . , w(i,k)).

(a) Classify this problem as either Linear Programming or Integer Linear Programming, and deduce whether there
is a known algorithm to solve it in polynomial time?

(b) Formulate this problem P in standard form, making sure to define all variables and constraints involved.

(c) Formulate the dual of this problem P .

(d) Suppose that all of a sudden, exactly m < n many types items are required to produce exactly 1, 2, . . . m many.How should you modify your LP formulation? (you can assume that producing those items do not exceed thepollution requirement)[H] Exercise 10. Linear programming comes up in financial mathematics, here for this problem we will give a previewof the problem of arbitrage betting. Say there is a huge sports tournament going on with m teams competing and ndifferent betting agencies currently allowing you to place bets on the outcome of the tournament.(a) Suppose that each betting agency i now allows you to put a bet on the tith team wins at the end of the tournamentwith a payout of fi : 1, write down a standard form (matrix form) LP problem P that allows you to maximizeyour risk-free profit (i.e., a strategy that yields a profit regardless of the outcomes) with a budget of B.(b) Write down the dual problem P for the LP formulation you have derived in (a).(c) Does your LP procedure always give a solution that will make you money? Explain your answer.Hint. You may want to consider the Arbitrage Theorem.[H] Exercise 11. Linear programming shows up in game theory as well. Suppose there are n armies advancing on mcities and each army i is commanded by a General Gi with Ri many regiments. Each general Gi can send choose to send some amount of regiments to a city. In each city, the army that sends the most amount of regiments to the city captures both the city and all otherarmys regiments. If there are any ties in the number of regiment for the 1st place, then those corresponding armies draws and losesno points. The rest of the armies are penalised the same amount of points as the regiments sent to that city. Each army scores 1 point per city captured and 1 point per captured regiment.Assume that each army needs to make full use of its regiments, and wants to maximize the sum of the difference betweenits reward and all other opponents reward.(a) This is an example of a zero-sum game. Denote a strategy j = (1, 2, . . . , m) as follows: the general j sends iregiments to city i and so on and let Si denote the space of all possible strategies that can be done by general i.We define the payoff matrix (or tensor) Ck : S1 S2 Sn Z, which each of the C(1, 2, . . . , n) denotesthe payoff of each of the generals selecting the strategy of 1, 2, . . . , n in the perspective of Gk. E.g. If General1 uses the strategy (4, 0) and General 2 uses the strategy (3, 0) then the corresponding C2((4, 0), (3, 0)) is 4 asGeneral A captures 1 city and 3 regiments, resulting in a loss of 4.Generate the payoff matrix C2 for n = 2, m = 2 and R1 = 4, R2 = 3.(b) For n = 2, write down the standard form LP formulation that finds the optimal strategy for any General in aCOMP3121/9101 Term 3, 2022 4https://wiki.analytica.com/Arbitrage_TheoremProblem Set 6 SECTION TWO: LINEAR PROGRAMMINGprobabilistic sense.COMP3121/9101 Term 3, 2022 5Problem Set 6 SECTION THREE: INTRACTABILITY SECTION THREE: INTRACTABILITY[K] Exercise 12. Determine for each of the following whether it is a polynomial time algorithm.(a) O(n) input, O(n log n) running time.(b) O(n+ logC) input, O(nC) running time.(c) O(n) input, O(n3) running time.(d) O(n) input, O(2n) running time.[K] Exercise 13. A clique of a graph G = (V,E) is a subset U V of vertices such that any two elements, u, v Uare adjacent; that is, for any distinct pairs of vertices u, v U , there exist an edge such that (u, v) E of G.Consider the optimisation version of the clique problem as stated below.Maximum CliqueInstance: An undirected graph G = (V,E).Task: Choose a subset U V of vertices of maximum size such that for any two vertices u, v U , we have(u, v) E.(a) Convert this optimisation problem to the corresponding decision problem (Clique).(b) Explain how an algorithm which solves the Clique problem can be extended to solve the original optimisationproblem (Maximum Clique) with log |V | overhead.(c) Show that the Clique problem is in class NP.[K] Exercise 14. Recall the Integer Knapsack problem from the Dynamic Programming lecture. The problem isstated below.Integer KnapsackInstance: a positive integer n, integers wi and vi for each 1 i n, and a positive integer C.Task: Choose a combination of items (with repetition allowed) which all fit in the knapsack and whose total valueis as large as possible.(a) Is this an optimisation or decision problem?(b) If this is an optimisation problem, convert it to a corresponding decision problem.(c) Show that the decision problem is in NP.[K] Exercise 15. Suppose that U and V are decision problems in class NP, and that there exists a polynomialreduction f from U to V . What can you deduce if:(a) V is in class P?(b) V is in class NP-C?(c) U is in class P?COMP3121/9101 Term 3, 2022 6Problem Set 6 SECTION THREE: INTRACTABILITY(d) U is in class NP-C?[H] Exercise 16. Recall that the Vertex Cover problem is as follows:Vertex Cover (VC)Instance: G = (V,E), an undirected and unweighted graph, and a positive integer k.Task: Is it possible to choose k vertices so that every edge is incident to at least one of the chosen vertices?In lectures, we showed that the Vertex Cover problem is in NP-complete. We will use this problem to prove that arelated problem is also NP-complete.Consider the Feedback Vertex Set problem stated below.Feedback Vertex Set (FVS)Instance: G = (V,E), an undirected (or directed) graph, and a positive integer k.Task: Is it possible to choose k |V | vertices so that, if we remove all k vertices and their corresponding adjacentedges from G, the new graph is cycle-free?(a) Show that Feedback Vertex Set is in NP.(b) We now prove that Feedback Vertex Set is in NP-hard. Consider the following reduction.Given a graph G = (V,E), we construct G = (V , E) where: V = UV UE , where UV consists of the vertices of G and, for each edge in (v1, v2) E, we create a newvertex uv1,v2 which belong in UE . E consists of the edges constructed as follows: For each edge (v1, v2) E in the original graph, we construct three edges: an edge from v1 UV tov2 UV , an edge from v1 UV to uv1,v2 UE , and an edge from v2 UV to uv1,v2 UE .We claim that(G, k) VC (G, k) FVS .Consider the following graph G.COMP3121/9101 Term 3, 2022 7Problem Set 6 SECTION THREE: INTRACTABILITY(i) Using the reduction described above, construct G.(ii) Show that G has a vertex cover of size 2, and find the corresponding feedback vertex set of size 2 in G. Howcan we generalise this to arbitrary graphs G, and thus, deduce that Feedback Vertex Set is in NP-hard?(c) Using the previous two results, conclude that Feedback Vertex Set is in NP-complete.[E] Exercise 17. Recall that a decision problem X is said to be in NP if yes instances of X have a certificate and apolynomial-time verifier.In a similar way, we can then define the following class of problems:A decision problem X is said to be in coNP if no instances of X have a certificate and a polynomial-time verifier.We say that the complement of a problem is the result of switching the yes and no results. Using the definition ofthe complement of a problem, we can also define the following class of problems:A decision problem X is said to be in coP if the complement of X is solvable in polynomial time.(a) Show that P = coP.(b) Using part (a), show that, if P = NP, then NP = coNP.COMP3121/9101 Term 3, 2022 8SECTION ONE: STRING MATCHINGSECTION TWO: LINEAR PROGRAMMINGSECTION THREE: INTRACTABILITY CS: assignmentchef QQ: 1823890830 Email: [email protected]