CSE 450 Design and Analysis of Algorithms: Assignment 4 Dynamic Programming
CSE 450: Assignment 4 (Dynamic Programming)
This assignment should be completed in groups of two. As stated in the course syllabus, “students are encouraged to discuss homework problems with others, but each group is expected to turn in the results of their own effort, not that of another group’s.” Even when not explicitly asked, you should concisely justify your answers. Each individual or group should prepare a single writeup in LATEX using the provided template and submit it as a PDF on Canvas to receive credit.
Problem 1
The instance of Weighted-Interval-Scheduling shown below has its intervals sorted by increasing finish time. The weight of interval i is given by wi and its predecessor is given by p(i). Detail the complete execution of the dynamic programming algorithm for Weighted-Interval-Scheduling on this instance using either of the memoized recursive or bottom-up versions. State both the optimal set of intervals and their total weight.
w1=2 w2=4 w3=4 w4=7 w5=2 w6=1
Problem 2
p(1)=0 p(2)=0 p(3)=1 p(4)=0 p(5)=3 p(6)=4
An ordered graph is a connected, directed graph G = (V, E) with nodes V = {v1, . . . , vn} such that (1) every edge (vi,vj) ∈ E has i < j; i.e., each edge starts at a node with a lower index than the node where it ends, and (2) every node except vn has at least one outgoing edge. We want to find the longest path starting at v1 and ending at vn, where the length of a path is its number of edges. For the example ordered graph below, the longest path is P = [v1, v2, v4, v5] which has length 3.
v1 v2 v3 v4 v5
(a) Prove that the following algorithm does not correctly solve this problem by (1) defining an ordered graph G on which this algorithm does not find the longest path, (2) identifying what the true longest path in G is and what its length is, and (3) identifying what path the algorithm outputs. time
Algorithm 1 BrokenOrderedLongestPath Input: An ordered graph G = (V, E).
1: 2: 3: 4: 5:
InitializeP =[v1],l←0,andv←v1. while there is an edge leaving node v do
Let (v,vi) be the edge for which i is as small as possible.
Appendvi toP,updatev←vi,andupdatel←l+1. return the longest path P and its length l.
(b) Use dynamic programming to devise an efficient algorithm for finding the longest path in an ordered graph. Your solution should (1) define the OPT function, (2) define and justify the dynamic program- ming recurrence for OPT, (3) state your algorithm in pseudocode, and (4) briefly state and justify your algorithm’s asymptotic runtime.
Problem 3
Suppose that as you near the end of the semester, you have n final projects to complete. You only have H > n total hours to allocate to working on these projects, so you want to determine the optimal allocation of hours to projects that will get you the best overall grades. For each project i, there is a function fi that estimates the relationship between hours spent and the final grade; specifically, for a number of hours hi ≤ H spent on project i, fi(hi) ≥ 1 is your numerical grade for the project. You may assume that the input to any estimation functions fi is always an integer number of hours. You may also assume that the functions fi are “nondecreasing”; i.e., if h > h′, then fi(h) ≥ fi(h′).
Use dynamic programming to design an algorithm that takes as input the functions f1 , . . . , fn and returns an allocation of hours h1, . . . , hn to spend on each project that maximizes ?ni=1 fi(hi). Your solution should (1) define the OPT function, (2) define and justify the dynamic programming recurrence for OPT, (3) state your algorithm in pseudocode, and (4) briefly state and justify your algorithm’s asymptotic runtime. Its runtime should be polynomial in n and H.
Problem 4
Gerrymandering is the practice of drawing the boundaries of electoral districts such that outcomes will favor a particular political party. Algorithms for performing and fighting against gerrymandering have been a major tension in social computing over the last two decades. To understand how this is an algorithmic issue, consider the following (simplified) scenario.
Suppose we have n “precincts” each containing m voters. We are additionally given the political party registrations of each of the m voters in each precinct; for simplicity, we assume all voters are registered with one of two political parties. A set of precincts is susceptible to gerrymandering if it is possible to partition the precincts into two electoral districts, each containing n/2 of the precincts, such that the same political party holds the majority in both districts. For example, the precincts shown in the table below are susceptible to gerrymandering because if the districts were defined as precincts (1, 4) and (2, 3), then party A—despite only having a slim majority in the overall population—would have the majority in both districts.
Precinct
Party A Voters Party B Voters
1 2
55 43 45 57
3 4
60 47 40 53
Give a dynamic programming algorithm determining whether a set of precincts is susceptible to gerryman- dering. Your solution should (1) define the OPT function, (2) define and justify the dynamic programming recurrence for OPT, (3) state your algorithm in pseudocode, and (4) briefly state and justify your algorithm’s asymptotic runtime. Its runtime should be polynomial in n and m.
Problem 5
Let c1,...,cn be the different currencies used across the global economy. For every pair of currencies (ci,cj) where i ̸= j, there is an exchange rate rij that determines how much one unit of currency ci is worth in currency cj. For example, if the exchange rate from USD to EUR is 1:0.93, then rUSD,EUR = 0.93 and rEUR,USD = 1/0.93 ≈ 1.075. Informally, an arbitrage opportunity is a series of exchanges starting and ending in the same currency such that the amount of currency you end with is greater than the amount you started with. Formally, an arbitrage opportunity is a cycle C such that the product of exchange rates over the cycle is strictly greater than 1; i.e.,
rij > 1. (ci ,cj )∈C
Give a polynomial-time algorithm that finds an arbitrage opportunity, if one exists, and otherwise declares that there is none. Briefly state and justify its runtime. [Hint: log(a · b) = log a + log b.]
Problem 6
Consider the Sequence-Alignment problem on the DNA sequences CGAAGTCA and CTCAAGA using a gap penalty of δ = −1 and the substitution matrix:
AGCT
A 1 −1 −1 −1 G −1 1 −1 −1 C −1 −1 1 −1 T −1 −1 −1 1
For each of the Needleman–Wunsch (global alignment) and Smith–Waterman (local alignment) algorithms, show the completed tables of alignment scores and their tracebacks and state the final sequence alignment and score. Note that you do not have to show the step-by-step executions; you can simply give the completed tables of optimal values and the resulting tracebacks. If you are not comfortable creating these tables in LATEX, you can draw them by hand, take pictures, and include them as figures in your LATEX writeup.
