COMP3121/9101
Algorithm Design
Copyright By PowCoder代写 加微信 powcoder
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 m×m 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 well’s 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 the pollution requirement) [H] Exercise 10. Linear programming comes up in financial mathematics, here for this problem we will give a preview of the problem of arbitrage betting. Say there is a huge sports tournament going on with m teams competing and n different 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 tournament with a payout of fi : 1, write down a standard form (matrix form) LP problem P that allows you to maximize your 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 m cities 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 other army’s regiments. • If there are any ties in the number of regiment for the 1st place, then those corresponding armies draws and loses no 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 between its reward and all other opponent’s reward. (a) This is an example of a zero-sum game. Denote a strategy πj = (π1, π2, . . . , πm) as follows: the general j sends πi regiments 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) denotes the payoff of each of the generals selecting the strategy of π1, π2, . . . , πn in the perspective of Gk. E.g. If General 1 uses the strategy (4, 0) and General 2 uses the strategy (3, 0) then the corresponding C2((4, 0), (3, 0)) is −4 as General 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 a COMP3121/9101 – Term 3, 2022 4 https://wiki.analytica.com/Arbitrage_Theorem Problem Set 6 SECTION TWO: LINEAR PROGRAMMING probabilistic sense. COMP3121/9101 – Term 3, 2022 5 Problem 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 ∈ U are 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 Clique Instance: 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 optimisation problem (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 is stated below. Integer Knapsack Instance: 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 value is 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 polynomial reduction 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 6 Problem 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 a related 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 adjacent edges 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 new vertex 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 to v2 ∈ 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 7 Problem 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′. How can 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 a polynomial-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 of the 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 8 SECTION ONE: STRING MATCHING SECTION TWO: LINEAR PROGRAMMING SECTION THREE: INTRACTABILITY 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com