Comp 251: Final examination
Instructor: Jérôme Waldispühl April 21th, 2017
True or False
Copyright By PowCoder代写 加微信 powcoder
1. True or False? (Circle your answers. Wrong answers will receive a penalty of -1 point. No
justification needed. )
(a) (2 points) Using the array representation seen in class, the following array [20 15 18 7 9 5 12 3 6 2]formsamax-heap.
A. True B. False
(b) (2 points) The height of binary search tree with n nodes is Ω(log n). A. True B. False
(c) (2points) GivenaweightedgraphG=(V,E,w)andasetS⊆V,let(u,v)beanedge such that (u, v) is the minimum weight edge between any vertex of S and any vertex of V − S. In this case, the minimum spanning tree of G must include the edge (u, v) (you can assume that the weights of all edges are distinct).
A. True B. False
(d) (2 points) Let T be a minimum spanning tree of a graph G. Then, for any pair of vertices s and t, the shortest path from s to t in G is the path from s to t in T .
A. True B. False
(e) (2 points) When a graph has no negative weight cycles, the Bellman-Ford algorithm and Dijkstra’s algorithm always produce the same output.
A. True B. False
(f) (2 points) Given a weighted directed graph G = (V, E, w) and a shortest path p from s to t, if we doubled the weight of every edge to produce G′ = (V, E, w′), then p is also a shortest path in G′.
A. True B. False
(g) (2 points) The total amortized cost of a sequence of n operations (i.e. the sum over all operations, of the amortized cost per operation) gives a lower bound on the actual cost of the sequence of operations.
A. True B. False
(h) (2points) Alldynamicprogrammingalgorithmssatisfyanoptimalsubstructureproperty. A. True B. False
(i) (2points) Supposethatahashtablewithcollisionsresolvedbychainingcontainsnitems and has a load factor of α = 1/ log n. Assuming simple uniform hashing, the expected time to search for an item in the table is O(1/ log n).
A. True B. False
(j) (2 points) An adversary can provide randomized quicksort with an input array of length n that forces the algorithm to run in Ω(n log n) time on that input.
A. True B. False
Course: COMP 251
Page number: 2 / 14
Multiple choice questions
2. Multiple choice questions (Circle your answers. No justification needed. You may circle zero, one or multiple answers.)
(a) (4 points) We perform a rotation on a binary search tree. Which assertions are true?
A. The resulting tree is a binary search tree.
B. The height of the tree is preserved.
C. The resulting tree is balanced.
D. The running time of a rotation is O(1).
(b) (4 points) Which of the following graphs are bipartite?
(A)G1 * (B)G2 * (C)G3 (D)G4
(c) (4 points) We are applying the dynamic programming algorithm we have seen in class to solve the weighted activity scheduling problem. An instance of this problem is show below. The weight of an activity ai is noted Vi and is equal to the length (or duration) of the activity. The predecessor of an activity ai is noted pred(ai). We started to fill the dynamic programming table M for the first, second and third activity (i.e. column a1, a2, and a3 in the table below).
activity (ai) pred
a1 a2 – a1
a1 a2 M[ai] 125? Vi +M[pred(ai)] 1 2 5 ? M[ai−1] 0 1 2 ?
(A) Instance of the weighted activity scheduling problem.
Which values should appear in the column of the last activity (i.e. a4)?
4 4 5 5 A. 5 B. 4 C. 5 D. 4
(B) Dynamic programming table M
Course: COMP 251 Page number: 3 / 14
(d) (4 points) We use a tree representation to model disjoint sets. We implement unions as union-by-size with path compression. What is the worst case running time for the opera- tions find and union?
A. O(1) for both.
B. O(logn)forboth.
C. O(n) for find, and O(1) for union. D. O(1) for find, and O(n) for union.
(e) (4points) Whatistheratioofrandombooleanvariableassignmentsthatsatisfiesaclause of 3-SAT (i.e. the clause is True)?
A. 1/2 B. 2/3 C. 7/8
Course: COMP 251
Page number: 4 / 14
Short answers
3. (4 points) Let S be a set of n integers. One can create a data structure for S so that determining whether an integer x belongs to S can be performed in O(1) time in the worst case. How?
4. For each algorithm listed below,
• give a recurrence that describes its running time complexity, and
• give its running time complexity using Θ-notation. No justification needed.
(a) (8 points) Binary search (i.e. The classic dichotomic search algorithm for finding a value in a sorted array)
(b) (8 points) Merge sort
(c) (8 points) Karatsuba
Flow network
5. Let G be a flow network shown in the figure below. The source is the vertex s and the sink the vertex t. The notation a/b describes a units of flow in an edge of capacity b. Each edge is annotated with the value of the flow traversing it and its capacity.
s 3/7 0/2 1/4 t 6/6 x 3/3 y 4/4
Solution: Use a hash table (Note: Solution such as a simple table can be accepted albeit not optimal)
Course: COMP 251
Page number: 5 / 14
Solution: T(n)=T(n/2)+Θ(1)=Θ(logn)
Solution: T(n)=2·T(n/2)+Θ(n)=Θ(n·logn)
Solution: T(n)=3·T(n/2)+Θ(n)=Θ(nlog3)
(a) (5 points) Is the flow maximal? Justify your answer with a constructive argument.
(b) (5 points) Draw the residual graph Gf of G.
Solution: Yes. Consider the capacity of the cut {s,u,x} and {v, t,y} that is 5. The flow is already equal to 5. The flow in a graph cannot exceed the capacity of any cut, thus it is maximal.
(c) (5 points) Use the residual graph Gf to find a minimal cut in G. Give the minimal cut (i.e. the partition of vertices) and explain how you calculate it.
Solution: {s,u, x} and {v, t, y} is a minimal cut. We run DFS (or BFS) to determine all vertices reachable from the source s. The latter determine the cut.
Course: COMP 251 Page number: 6 / 14
Master method
6. We remind you the master method.
Theorem 1 (Master method) Let a ≥ 1 and b ≥ 1 be two constants, and f (n) a function. ∀n ∈ N+ we define T(n) as:
T(n)=aTn+f(n),where nb isinterpretedas⌊nb⌋or⌈nb⌉. b
Then, we can find asymptotical bounds for T (n) such that:
1. If f(n) = O(nlogb a−ε) with ε > 0, then T(n) = Θ(nlogb a).
2. If f(n) = Θ(nlogb a · logp n), then T(n) = Θ(nlogb a logp+1 n).
3. Iff(n) = Ω(nlogba+ε)withε > 0,anda·fn ≤ cf(n),∀n > n0 withc < 1and b
n0 > 0. Then T(n) = Θ(f(n)).
When possible, apply the master method to find the asymptotic behaviour of T(n) below.
Indicate which case has been applied, or alternatively why you cannot use the method. (a) (8points) T(n)=4·T(n2)+logn
(b) (8points) T(n)=2n ·T(n2)+nn (c) (8points) T(n)=7·T(n3)+n2 (d) (8points) T(n)=3·T(n3)+n2
Solution: Θ(n2) (Case 1)
Solution: Does not apply (a is not constant)
Solution: Θ(n2) (Case 3)
Solution: Θ(nlogn)(Case2)
Course: COMP 251 Page number: 7 / 14
Stable matching
7. (10 points) We have a group of 3 applicants (i.e. candidates) and 3 companies with prefer- ences. Apply the Gale-Shapley algorithm to find a stable matching. Show your work.
Candidates
Baidu Alphabet
Preferences
2nd Alphabet
Campbell Campbell
3rd Campbell
Alphabet Baidu
Alphabet Baidu Campbell
1st Xavier
Preferences
2nd Yulia
3rd : Xavier → Alphabet Yulia → Baidu
Zhang → Campbell
Amortized analysis
8. We consider the implementation of a queue with two stacks S1 and S2. At any time, at least one of the two stacks is empty. The method enqueue pushes a new element in the non-empty stack (say S1). While the method dequeue pops all elements from the non-empty stack (Say S1) and pushes them into the empty one (S2), and then returns the last element inserted in S2. We want to determine the amortized complexity of the operations enqueue and dequeue.
(a) (5 points) Let n be the number of elements in the queue. What is the worst running time complexity of enqueue and dequeue (No justification needed).
(b) (15 points) Calculate the amortized cost per operation of a sequence of m operations enqueue and dequeue (You can choose to use the aggregate or accounting method).
Solution: enqueue: O(1), dequeue: O(n).
Aggregate method: As each element is processed, it is clearly pushed at most twice and popped at most twice. However, if an element is enqueued and never dequeued then it is pushed at most twice and popped at most once. Thus the cost of each en- queue is 3 and of each dequeue is 1.
Accounting method: Allocate $2 to each element stored in the queue structure. This will cover the cost of popping it and pushing it from stack1 to stack2 if that ever needs
Course: COMP 251 Page number: 8 / 14
to be done. There is an additional cost of $1 for the initial push onto S1, for a cost of $3. The dequeue operations cost $1 to pop from S2.
Course: COMP 251 Page number: 9 / 14
Minimum Spanning Tree
9. We give pseudocode for different algorithms to compute minimum spanning trees. Each one takes a graph as input and returns a set of edges T . For each algorithm, you must either prove that T is a minimum spanning tree or show a counter-example.
(a) (10 points)
Algorithm 1 MAYBE-MST-B(G,w)
for all edge e, taken in arbitrary order do
if T ∪ {e} has no cycle then T ← T ∪ {e}
end if end for
Solution: It will not give a minimum spanning tree, that can be proven by a counter- example.
The MST would have edges (w;u) and (v;w) with weight 3.
MAYBE-MST-B could add edges (u;v) and (v;w) to T, then try to add (w;u) which forms a cycle, then return T (weight 5), since the algorithm takes edges in arbitrary order.
(b) (10 points)
Algorithm 2 MAYBE-MST-A(G,w)
Sort the edges into non-increasing (decreasing) order of edge weights w
for all edge e, taken in non-increasing order by weight do
if T − {e} is a connected graph then T ← T − {e}
end if end for
Course: COMP 251
Page number: 10 / 14
Solution: Observe that MAYBE-MST-A removes edges in non-increasing order as long as the graph remains connected. Then, the resulting T is a minimum spanning tree. The correctness of the algorithm can be shown as follows:
let S be a MST of G. When an edge e is about to be removed, either e ∈ S or e ̸∈ S. If e ̸∈ S, then we can just remove it.
If e ∈ S, removing e will disconnect S into two trees (Note: this does not disconnect the graph). It is clear that no other edge can connect these trees with smaller weight than e, because by assumption S is a MST, and if a larger edge existed that connected the trees the algorithm would have removed it before removing e. Since the graph is still connected, this means a path exists. So, there must be another edge with equal weight that has not been discovered yet, which means we can remove e.
Course: COMP 251 Page number: 11 / 14
Longest common substring
10. We define the longest common substring problem as: Given two strings, α of length m and β of length n, find the longest string which is a substring of both α and β (Note: a substring is a sequence of consecutive letters). For instance, 011 is the longest common substring of α = 00011 and β = 0111. This common substring can be visualized with a simple alignment:
α = 00011-
β = –0111
As illustrated above, we want to find an alignment with the longest series of consecutive
(a) We aim to design a dynamic programming algorithm to solve the longest common sub- string problem. We propose below a recurrence to solve this problem. Let α and β be the input substrings of length m and n. First, we define a recursive equation to calculate the longest common suffix for all pairs of prefixes of the strings. Let LCS be the array such that LCS(i, j) stores the length of longest common suffix of α[1, i] = α1 · · · αi (i.e. prefix of α) and β[1, j] = β1 · · · βj (i.e. prefix of β). Our recurrence is:
LCS(i−1,j−1)+1 ifα[i]=β[j] LCS(i, j) = 0 Otherwise
i. (5 points) What is the base case? (i.e. how do you initialize the array LCS?)
ii. (5 points) Assume that the array LCS is now fully calculated. Where will you po- tentially find (i.e. in which cell(s)) the value of the length of the longest substring value in this table? (Note: This will also be the starting point of the backtracking procedure used to retrieve the solution)
(b) (5 points) What is the optimal substructure of the longest common substring problem? You do not need to prove your answer.
(c) (10points) Basedontherecurrencedescribedabove,writethepseudo-codeofadynamic programming algorithm that fills/calculates the array LCS, and returns the length of the longest common substring (Note: We do not ask you to write the backtracking procedure).
Solution: LCS[i,j]=0ifi=0orj =0
Solution: It can be anywhere in the dynamic array.
Solution: It is found in the recursive equation given above. Any prefix ending at index(i−k,j−k)(k ≤ LCS(i,j))ofthelongestcommonsubstringendingatindex (i, j) is also a longest common substring ending at index (i − k, j − k).
More generally, you could also say that the longest common suffix of a prefix of your prefix (I know it starts to be convoluted…) should be itself optimal.
Course: COMP 251 Page number: 12 / 14
for (i=1; i<=m; i++)
LCS[i,0] = 0
for (j=1; j<=n; i++)
LCS[0,i] = 0
for (i=1; i<=m; i++)
for (j=1; j<=n; j++)
if a[i] == b[j]
LCS[i,j] = LCS[i-1,j-1] + 1;
if LCS[i,j] > best:
best = LCS[i,j]
LCS[i,j] = 0
return best
(d) (5 points) Execute your algorithm with α = 1100 and β = 101. Show the complete dynamic programming table filled by your algorithm. Then, show the cell that contains the value of the longest common substring, as well as the path in the dynamic table corresponding to the longest common substring.
(e) (5 points) What is the running time complexity (worst and best case) of this algorithm? No justification needed.
-1100 -00000 Solution: 1 0 1 1 0 0 000021 101100
Solution: Θ(m·n)
Course: COMP 251 Page number: 13 / 14
Course: COMP 251 Page number: 14 / 14
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com