CS 124 Midterm: Spring 2021
Your name: CS 124 Staff Instructions:
• Spend at most 90 minutes on the exam, from the time you first see a problem to the last time you write anything in your solutions. (Time spent uploading doesn’t count against your time.)
Time started: Time ended:
Copyright By PowCoder代写 加微信 powcoder
• Do not communicate with anyone but the course staff about the contents of the exam.
• Do not use a computer or other electronic aids during the exam for anything except for:
1. (optionally) typesetting your solutions,
2. (optionally) accessing the reference materials in the list below.
3. (optionally) asking clarification questions of the instructors on Ed.
• Do not use any reference materials (e.g. class notes, textbooks, internet) except:
1. ’s textbook Algorithms at http://jeffe.cs.illinois.edu/teaching/
algorithms/
2. Cormen, Leiserson, Rivest, and Stein’s textbook Introduction to Algorithms
3. Kleinberg and Tardos’s textbook Algorithm Design
4. The note sheet titled “CS-124-Algorithms-review” from Canvas-Files-Exam Prep
5. At most one single-sided letter/A4-sized sheet of paper with your own handwritten notes.
• After you finish the exam, write your name in affirmation of the following statement:
I, , pledge
my honor that I have obeyed all instructions on this page in taking this exam.
After you finish, upload your exam to Gradescope as if it were a problem set.
• You have 90 minutes to earn a maximum of 90 points. We recommend that you read all the problems first, and attack them in the order that allows you to make the most progress. Do not spend too much time on any single problem: We recommend roughly n minutes on an n point problem (leaving time to check your answers).
• You can ask clarification questions of the instructors on Ed.
• Be neat and write legibly and clearly. You will be graded not only on the correctness of your
answers, but also on the clarity with which you express them.
• Do not waste time re-deriving results presented in class or sections. You may simply state and cite them.
1 True/False (14 points)
For each of the following statements, say whether the statement is TRUE or FALSE. Each correct answer is worth 2 points. Incorrect answers are worth 0 points. No explanations are needed.
1. 2(4n) = O(4(2n)) TRUE
42n =(2·2)2n =22n22n =(22n)2.Since24n−2n =ω(22n),thestatementisfalse.
2. n(n/2) = O((n/2)n) TRUE
limn→∞ n(n/2)/(n/2)n = lim 2n/nn/2 = 0 so the statement is true.
3. Suppose a DFS on a directed graph G starting from a vertex s labels edge e as a forward
edge. Then no other DFS of G starting from s labels e as a back edge. TRUE
Edges BC and CB in the followng graph are counterexamples.
4. If a DFS on a directed graph G finds a back edge, every other DFS of G will also find a back edge.
If there’s a back edge, then the graph has a cycle and every DFS will detect this cycle.
5. If I have a Huffman tree for a file, and then change the file by adding 1 copy of each character in the file at the end, the same Huffman tree works for the file.
TRUE FALSE
“abcdeee” and “abcdeeeabcde” have different trees.
6. I have a biased coin. I flip it until I either see a TH (tails followed by a heads) or a HT (heads following by a tails). In the first case I return TAILS, in the seccond case I return HEADS; this gives me an unbiased flip.
TRUE FALSE
Let p be the probability that the biased coin is heads. Then, P(H) = P(HT) + P(HHT) + P(HHHT)+… = p(1−p)+p2(1−p)+p3(1−p)+… = p and p does not necessarily equal 1/2.
7. Consider a recursive algorithm for matrix multiplication (like Strassen’s algorithm) in which I split a matrix into 70 smaller n/4 × n/4 submatrices and do 124 multiplications of them; all other work is a constant number of matrix additions. This algorithm is o(n3).
TRUE FALSE
T (n) = 124T (n/4) + O(n2). By the Master’s Theorem, this is Θ(nlog4 124) ̸= o(n3).
2 Multiple Choice (8 points)
No explanations are necessary for these multiple-choice questions:
1. Let Fn be the nth Fibonacci number; here F0 = 0, F1 = 1, and Fi+1 = Fi + Fi−1. Which of the following are true:
(a) The sum F0 +F1 +…+Fn equals Fn+2 −1.
(b) The sum F1 +F3 +F5 …+F2n−1 equals F2n −1. (c) The sum F0 +F2 +F4 …+F2n equals F2n+1 −1.
(d) none of the above (e) i. and ii.
(f) i. and iii.
(g) ii. and iii.
(h) i. and ii. and iii.
(b) fails for n = 2.
2. Consider each of the following words as a set of letters: [arid, dash, drain, heard, lost, nose, shun, slate, snare, thread]. If I apply the greedy set-cover algorithm to cover the union of those sets of letters, breaking ties in favor of the word that appears first in the dictionary, what is the size of the resulting set cover?
(a) 1 (b) 2 (c) 3
(d) 4 (e) 5 (f) 6
Set cover will be [thread, shun, lost, drain].
3 Counterexamples (12 points)
Show that the following statements are false by providing a suitable counter-example. A statement like “this statement is false if x goes to infinity” is not a counter-example! Give a specific example; e.g. “this statement is false if x is a billion”. We are not looking for a proof, but if you feel necessary, you may also give a short explanation. For minimum spanning tree problems, assume the graph has a minimum spanning tree (i.e. is an undirected and connected graph).
1. log(log∗ n) ≤ 2 for all n. (All logarithms are base 2.) Consider n such that log∗ n = 8.
2. You want to find the longest path in a tree with positive edge weights. Consider the following greedy algorithm. Begin at the root of the tree, and pick the outgoing edge of highest weight. Repeat until you reach a leaf. This gives the longest path.
Consider the following counterexample:
3. The following divide and conquer algorithm gives a minimum spanning tree: divide the vertices V into V1 ∪ V2, with sizes ⌊n/2⌋ and ⌈n/2⌉, find the MST on each subgraph, and add in the lightest edge in between.
Consider the following graph with V1 = {A, C} and V2 = {B, D}:
4. The following algorithm gives a minimum spanning tree: start with an arbitrary tree on the graph, and repeat n times. Remove a highest weight edge (if there is more than one, pick any of them); insert the minimum weight edge between the resulting two components.
Consider the following graph.
If the initial tree is the yellow highlighted edges, then our algorithm will return AB, BC, CD, but this is not an MST.
4 Topological Sort (5 points)
How many different valid topological sort orderings does this graph have? (That is, how many different ways can one come up with a valid ordering satisfying the ordering constraints implied by the edges?) (No explanation necessary.)
10. A and D are fixed as the first and last entry in the sort, and E, F, G must be in that order. This leaves 10 positions for BC: 1 when B is between G and D, 2 if B is between F and G, 3 if B is between E and F and 4 if B is between A and E.
Calculations (10 points)
Draw the binary min heap that results from inserting 11,10,4,2,5,9,13,6,0 in that order into an initially empty binary min heap. (No explanation necessary.)
Consider the set of initially unrelated elements 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Each is made into a set using make-set, and then the following operations are performed using union-by-rank with path compression, breaking ties by keeping the FIRST element as the root: Union(0,2), Union(3,4), Union(9,7), Union(9,4), Union (6,8), Union(6,0), Union(12,6), Union(1,11), Union(9,6). Show the final trees. Then, also, show the change by doing Find(4) after these union operations. (No explanation necessary.)
Tree before Find(4):
Tree after Find(4):
6 Short distances (13 points)
Consider the following problem: we’re given an undirected and unweighted graph G with n = |V (G)| andm=|E(G)|,asubsetS⊆V(G)oftheverticesofG,andapositiveintegerd≤n. Wewantto determine whether any of the vertices in S is at distance at most d from any other vertex of S. (A vertex is at distance 0 from itself and distance 1 from its neighbors.) (We don’t care which pairs of vertices are within distance d of each other, only whether a pair exists.)
Give an O(n + m)-time algorithm to solve the problem. (Note that d is part of the input, so an O(n · d)-time algorithm would be too slow, but since d ≤ n, an O(n + m + d)-time algorithm would be fine.)
Prove that your algorithm is correct.
For partial credit of up to 10 points, you can either assume that d is even or assume that d is odd.
Run a simultaneous BFS starting from each member of S for ⌈d/2⌉ iterations. Maintain an array D[v] (initialized to ∞) which keeps track of the distance from v to some vertex in S. For the first iteration, loop over every member of S and update the distance to each neighbor to be 1. For each subsequent iteration, run one BFS update step for each member of S, starting where we left off in the previous iteration. If, during the update step, D[v] ̸= ∞ and the sum of our current distance and D[v] is less than or equal to d, we have found a valid pair and the algorithm terminates.
Runtime: This algorithm is O(n + m) time, since we touch each vertex and each edge a constant number of times (if we see a vertex twice, we know we’ve found a valid pair and we terminate).
Correctness: If a path exists between some u and v in S, there will be some z such that the distances from u to x and from x to v are at most ⌈d/2⌉. Our simultaneous BFS’s will thus reach x and discover that the distance from u to v through x is at most d and will correctly terminate. If no valid path exists, then no such x will exist, so our algorithm won’t reach a visited vertex within ⌈d/2⌉ iterations, and will correctly return that no path exists.
7 Avengers (12 points)
Thanos wants to destroy the Avengers’ base, but the Avengers are guarding it! The Avengers’ base is an array [a1, a2, . . . , an] of n rooms where each room i contains a nonnegative integer number ai of Avengers. At each moment, he can do either of the following:
1. Spend 100 power to snap a base [a1,a2,…,ak] into two halves, the bases [a1,a2,…,ak ] and 2
[ak2 +1,a2,…,ak]. (You may assume that n is a power of 2, so the base can always be snapped into two equal halves.)
2. Destroy a base by spending na · l power, where na is the total number of Avengers in the base and l is the length of the base.
1. (9 points) Suppose that you can can find the number of Avengers in any range [a, b] in O(1) time. Give an O(n)-time algorithm to find minimum amount of power needed by Thanos to destroy the Avengers’ base. (You don’t need to analyze its runtime or prove it correct.)
2. (3 points) Give an algorithm that, in O(n) time for the first query and O(1) time per subsequent query, can answer queries of the form “what’s the number of Avengers in a range [a, b]”. (You don’t need to analyze its runtime or prove it correct.)
1. We can use the following divide and conquer algorithm: 0
D(A) = A[0]
min(i(A[i]) ∗ |A|, 100 + D[0 : |A|/2] + D[|A|/2 : |A|])
| A | = 0 |A| = 1
Remember that we are given that we can calculate i(A[i]) in O(1) time, so the following algorithm has recurrence T (n) = 2T (n/2) + O(1), which is O(n).
2. During the first call, compute an array S where S[j] = ji=0 A[i]. This can be done in O(n) time because S[j] = A[j] + S[j − 1]. For each subsequent call, simply return S[j] − S[i − 1], which takes time O(1).
8 Subsequences (16 points)
In this problem, I have a target sequence T = (t1,t2,…,tn) over some alphabet and a pattern sequence P = (p1, p2, . . . , pk), over the same alphabet with k < n. Each target letter ti has a value ci > 0. The goal is to find a subsequence of T that matches the pattern P (in order, the letters match as a string, but they don’t have to be sequential characters) with the highest value. For example,ifT =XYZXXYYZ,P =XYZ,andc1 =c2 =c3 =3,c4 =c5 =c7 =2,c6 =c8 =4, then the best match for P would be characters t1,t6,t8 in the target for a value of 11. It may be that no subsequence of T matches P, in which case the best match is 0.
1. (4 points) Suppose that every value ci is 1, so we only care about whether T has a subse- quence that matches P at all. Give a greedy algorithm for this problem. (No proof necessary.)
2. (12 points) Give an efficient dynamic-programming algorithm for the problem. You should give a recurrence, and briefly explain the running time and space. (Explaining the recurrence suitably suffices for a proof.)
1. Iterate over T until we find p1. From that point, continue iterating until we find p2. Repeat until all letters are matched, or we hit the end of T, in which case no match is possible. O(n) runtime because we touch each letter in T once. If a match occurs, p1 must occur before p2, which must occur before p3, and so on, so my algorithm will find it. If no match occurs, then there will be some letter pi that isn’t found in the right position, so my algorithm will reach the end of T and terminate correctly.
2. Let D(i,j) represent the maximum cost of matching p1,…pi with t1,…tj. We will return D[k,n]. Then,
−∞ 0
max(cj +D(i−1,j−1),D(i,j−1)) D(i, j − 1)
i ̸= 0 ∧ j = 0 or i > j i = 0
If we have pattern characters (i ̸= 0) but no more target characters (j = 0), then the gain is negative infinity because no matching exists. The same holds if we have more pattern char- acters than target characters. The second base case occurs if we have no pattern characters left, in which case the gain is 0.
If tj = pi, then we can either match this character and gain cj plus the gain from matching the rest of the pattern with the rest of the target, or we can ignore this match and match the pattern with the rest of the target. If tj ̸= pi, then we have to try to match the rest of the target with the pattern.
This is an n by k array, so the algorithm takes O(nk) space. Calculating each D(i,j) takes constant time, so this is an O(nk) time algorithm as well.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com