University of Waterloo CS 341 solns midterm ( VERIFIED ANSWERS 100% CORRECT )

Document Content and Description Below

For CS 341 in Winter 2016 only, do not distribute! 1 CS 341: Algorithms @ Waterloo Winter 2016 Midterm Exam Solutions There are totally 110 marks. The full mark is 100. This exam paper has three pa... ges. 1 Short Questions (70 marks) 1. (10 marks) In this question of solving recurrences, we assume that constant size problems can be solved in constant time. More formally, we assume that there exists a constant c0 ≥ 100 so that T (x) ≤ c1 for a constant c1 for all x ≤ c0. We also assume that n is a power of two for simplicity. (a) (5 marks) For the recurrence T (n) = 8T (n=2) + n4, provide the best big-O bound for T (n). Give your answer and a one-line explanation. You can use the Master theorem. Solution. 2. (10 marks) Given a sorted array of distinct integers A[1; n] in increasing order, design an algorithm to check whether there exists A[i] = i in O(log n) time. State your algorithm clearly. No explanations required. Solution. • The middle point of an range should be (start + end)=2, not (start - end)=2. 3. (10 marks) Given two polynomials P(x) = anxn + an-1xn-1 + : : : + a1x + a0 and Q(x) = bnxn + bn-1xn-1 + : : : + b1x + b0, provide an algorithm to multiply these two polynomials in O(nlog2 3) ≈ O(n1:59) word operations (i.e. each addition and multiplication in computing coefficients of PQ(x) is considered one word operation). You can assume that n + 1 is a power of two. State the algorithm clearly. Give a one line explanation of the time complexity. No proofs of correctness required. (Hint: It is very similar to Kuratsuba’s algorithm for integer multiplication.) Solution. 4. (10 marks) For the prefix coding problem, given seven symbols a; b; c; d; e; f; g with frequencies 0:2; 0:25; 0:05; 0:08; 0:15; 0:1; 0:17 respectively, show an optimal binary decoding tree for the problem. Just draw the tree and label the leaves. No explanations or intermediate calculations required. Solution. 5. (10 marks) Given a directed acyclic graph G = (V; E) with the adjacency list representation, provide an O(jV j+jEj)-time algorithm to check whether there exists a directed path that touches every vertex exactly once. Your algorithm just needs to return YES or NO (i.e. no need to return such a path in the YES case). State the algorithm clearly and provide a two-sentence explanation of its correctness. Figure 1: In the graph on the left, the path highlighted touches every vertex exactly once, while in the graph on the right, there is no such path. Solution. 6. (10 marks) If there are multiple shortest paths between s and t, then we prefer a shortest path from s to t with the minimum number of edges. Give an efficient algorithm to solve the following problem. Input: A directed graph G = (V; E) and a positive edge length le for each edge e 2 E, and two vertices s; t 2 V . Output: A shortest path (in terms of the total edge length on the path) from s to t with the minimum number of edges. Show how to use or modify Dijkstra’s algortihm to solve the problem with the same time complexity. You can assume Dijkstra’s algorithm without providing the details. No proofs required. 1 4 3 2 1 3 1 1 3 1 1 2 1 1 1 s t a b c d e f Figure 2: There are two paths (highlighted) of length 4 between s and t, namely s; a; c; b; t and s; d; f; t. The path s; d; f; t has only three edges and is the optimal solution in this example. Note that there are two s-t paths (s; c; t and s; d; t) with only two edges, but they are of length 5 and are not shortest paths. Solution. 7. (10 marks) Given a tree with its adjacency list representation, design an O(n) time preprocessing algorithm so that queries of the form \Is u an ancestor of v" can be answered in constant time. (That is, after the preprocessing, we can answer an arbitrary number of such queries, each in constant time.) Just state your algorithm. No explanation required. (Hint: Use depth-first search.) Solution. 2 Long Questions (40 marks) 1. (20 marks) (Total Weighted Completion Time) We are given n jobs, each with a processing time pi > 0 and a weight wi > 0. Our goal is to find an ordering to schedule all the jobs so as to minimize the total weighted completion time, i.e. min Pn i=1 wiCi, where Ci is the completion time of job i. For example, suppose there are two jobs, with the first job having processing time 5 and weight 4, and the second job having processing time 8 and weight 2. Then, if we schedule the first job before the second job, then the total weighted completion time is 4 × 5 + 2 × (5 + 8) = 46; while if we scheulde the second job before the first job, then the total weighted completion time is 2 × 8 + 4 × (5 + 8) = 68. Job 1 p1 = 5, w1 = 4 Job 2 p2 = 8, w2 = 2 Job 2 p2 = 8, w2 = 2 Job 1 p1 = 5, w1 = 4 0 5 13 0 8 13 Figure 3: On the left, the completion times of job 1 and job 2 are 5 and 13 respectively; on the right, the completion times of job 1 and job 2 are 13 and 8 respectively. (a) (10 marks) Suppose we only have two jobs, with processing times p1; p2 and weights w1; w2 respectively. Give a necessary and sufficient condition (in terms of p1; p2; w1; w2) for the optimal schedule to process job 1 before job 2. Solution. (b) (10 marks) Use (a) or otherwise, design an efficient algorithm to find an ordering to minimize the total weighted completion time for n jobs, with inputs p1; : : : ; pn and w1; : : : ; wn, where pi is the processing time of job i and wi is the weight of job i. State the algorithm, explain the correctness and the time complexity. Solution. 2. (20 marks) (Non-dominated Points) Given two points (x1; y1) and (x2; y2) on the 2D-plane, we say (x1; y1) is dominated by another point For CS 341 in Winter 2016 only, do not distribute! 7 (x2; y2) if x1 < x2 and y1 < y2. Design an algorithm to solve the following problem. Input: n points on the 2D-plane (x1; y1); : : : ; (xn; yn). Output: all points that are not dominated by any other point. You can assume all the x-values and y-values are distinct. State the algorithm, explain the correctness and the time complexity. You will get full marks if the time complexity is O(n log n) and the proofs are correct. x y Figure 4: The circled points are non-dominated points. Solution [Show More]

Last updated: 2 years ago

Preview 1 out of 9 pages