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 / 17
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 / 17
(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 / 17
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
Course: COMP 251 Page number: 5 / 17
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
(a) (5 points) Is the flow maximal? Justify your answer with a constructive argument.
(b) (5 points) Draw the residual graph Gf of G.
Course: COMP 251 Page number: 6 / 17
(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.
Course: COMP 251 Page number: 7 / 17
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
Course: COMP 251 Page number: 8 / 17
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 : COMP 251
Page number: 9 / 17
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).
Course: COMP 251 Page number: 10 / 17
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
(b) (10 points)
Course: COMP 251
Page number: 11 / 17
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: 12 / 17
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)
Course: COMP 251 Page number: 13 / 17
(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).
Course: COMP 251 Page number: 14 / 17
(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.
Course: COMP 251 Page number: 15 / 17
(e) (5 points) What is the running time complexity (worst and best case) of this algorithm? No justification needed.
Course: COMP 251 Page number: 16 / 17
Course: COMP 251 Page number: 17 / 17
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com