CSC 226 PRACTICE FINAL EXAM
NAME: STUDENT NO: Instructor: Nishant Mehta
NOTES:
Duration: 3 hours
1. This is a practice final exam; the number of questions was not designed with the 3 hour time limit in mind. It might take you more or less time than 3 hours. I didn’t try in any way to take into account the time limit (but I will do so for the actual final exam).
2. While the actual final exam is open book, this practice final exam contains some questions which are trivial if you use the textbooks or notes. Therefore, treat this practice final exam as a closed book exam.
1. Short answer questions
(a) What is the approximate value of nk=1 k1 ? You may assume that n is large and use asymptotic notation.
(b) Suppose that an algorithm has runtime T(n) which satisfies the recurrence relation T(n) = 3T(⌊n/3⌋)+cn for a positive constant c, and for all k ≤ 5 we have T(k) ≤ 2. What is the asymptotic runtime of this algorithm?
Answer: Θ( )
(c) In terms of how much code can be shared between the algorithms, which algorithm
is most similar to Dijkstra’s algorithm?
A. Ford-Fulkerson D. Kruskal’s algorithm B. Floyd-Warshall E. Prim’s algorithm C. Edmonds-Karp
(d) True or False: The Floyd-Warshall algorithm is a correct algorithm for the all-pairs shortest paths problem if the graph has negative weight edges, provided there are no negative cycles.
(e) A Hamiltonian path is a path which
.
Answer:
(f) The Edmonds-Karp algorithm involves using the Ford-Fulkerson algorithm as well as which of the following subprocedures for finding an augmenting path?
A. Floyd-Warshall algorithm C. Depth-first search
B. Dijkstra’s algorithm
D. Breadth-first search
Page 2
(g) Consider an s-t cut (A,B) in a flow network. We say that a directed edge is “out of A” if it originates in A and ends in B. Likewise, we say that a directed edge is “into A” if it originates in B and ends up in A. The value of a flow f is equal to
A. f(e) e out of A
B. f(e) e into A
C. f(e)− f(e) eoutofA eintoofA
D. f(e)− f(e) eintoA eoutofA
(h) What does the Max-Flow Min-Cut Theorem say?
Answer:
(i) Consider a flow network. Let f be an arbitrary
(A,B) be an arbitrary s-t cut with capacity c(A,B). Which one of the following relationships is guaranteed to be true?
A. c(A,B)≤v(f) B. c(A,B)=v(f) C. c(A,B)≥v(f)
(j) Consider the following type of algorithm for finding a solution based on an input of size n. First, partition the input into 3 roughly equal pieces, yielding 3 disjoint subproblems. Run the algorithm recursively on each piece. Somehow combine the solutions for the subproblems to obtain a solution for the original problem. What algorithm design paradigm does this algorithm best fit into?
A. Divide and Conquer C. Dynamic Programming B. Greedy D. Brute Force
(k) In what algorithm design paradigm is memoization used?
A. Divide and Conquer B. Greedy
C. Dynamic Programming D. Brute Force
Page 3
flow with value v(f), and let
2. Let X be a Bernoulli random variable with success probability 0.5, and let Y be Bernoulli random variable with success probability 0.25. What is E[2X + 4Y ]?
3. Divide and Conquer
(a) Suppose that we are using QuickSelect with the median-of-medians pivot, where the medians are over groups of size 7. In the very first call to QuickSelect, we have an array of n elements. Assuming that n/7 is an odd integer, what is the minimum number of these elements that can be strictly less than the median-of-medians?
(b) Consider the recurrence relationship T(n) = T(n/10)+T(n/5)+2n. For all n < 20, assume that T(n) is upper bounded 50. Which of the following is the smallest correct asymptotic upper bound on T(n)?
A. O(logn) B. O(√n) C. O(n) D. O(nlogn) E. O(n2)
Page 4
4. In the worst case (and using poor choices for augmenting paths), how does the runtime of the Ford-Fulkerson algorithm scale with maxe ce, where the max is taken over all edges and ce is the capacity of edge e? You may assume that the number of edges present in the original flow network is bounded by an absolute constant (say, 10).
Page 5
5. In the flow network below, the label x/y indicates that there currently is a flow of x units along the edge, and the capacity of the edge is y. For instance, 1 unit (out of a total possible of 9 units) is flowing along the left-most vertex s to the vertex that is below it immediately to the right. Given the flow shown below, draw the corresponding residual network. Be sure to indicate the capacities for each edge.
Flow network with given flow:
2/10 0/5
2/2
s 0/8 2/5 0/5 t
0/5
3/6
1/9
1/1 3/6
Answer:
st
Page 6
6. In this problem we consider the KMP algorithm’s DFA when the alphabet is {A, B, C} and the pattern is CABCAC. Below, you will find a partially completed drawing of the DFA and the corresponding partially completed table indicating the state transitions. Complete the remaining entries of the table.
To help you in filling in the table, it is recommended (but optional) to also complete the drawing of the DFA.
012345 A0
B0 C1
A,B 0C123456
Page 7
7. Recall that in the knapsack problem, we are given n items {1, . . . , n}, and each item has a nonnegative weight wi and a value vi (for i = 1,...,n). We also are given an upper bound W . The goal is to select a subset S of the n items so that i∈S vi is the maximum possible, subject to the constraint that i∈S wi ≤ W.
For any j ∈ {0,1,...,n} and w ≥ 0, let OPT(j,w) denote the value of the optimal solution among items {1,...,j} subject to the sum of the weights of the items used being at most w.
What is the key recurrence which allows us to compute opt(j, w) via optimal solutions to subproblems?
opt(w, j) =
Page 8
8. Consider a nationwide wireless network band allocation problem for the country of New Zealand. There is a range of frequencies available, starting from fmin and going all the way up to fmax. Each of n companies would like to request a contiguous open interval that is a subset of this band. In particular, company j would like to request the open interval (lj,uj), containing all the frequencies strictly in between the lower bound lj and the upper bound uj. Since these intervals may overlap, not all companies can be allocated their request. The government of New Zealand, being a friendly bunch, wants to satisfy as many companies as possible by maximizing the number of companies that receive their requested intervals.
Describe an efficient algorithm for solving this problem, and also mention which al- gorithm design paradigm (if any) this algorithm most closely matches. If this is an algorithm you have seen before, then it is not necessary to prove correctness. If your algorithm is novel, then at least a brief explanation of correctness is needed.
9. Suppose that we want to support a hash table for an application where the operations are almost entirely insertions until the load factor becomes 1/2, and thereafter the number of insertions and deletions is balanced so that the load factor stays close to 1/2. Discuss whether we should resolve collisions using chaining or open addressing and why.
10. [5 marks] This problem is about hashing. Let the set of keys be the set of all binary se- quences of length 4. So, one example key is 1010 (so, keys are strings, not integers). Each hash function corresponds to taking a unique permutation of the digits, then retaining only the first 3 digits, and finally interpreting the result as an integer. For example, the hash function that swaps the middle two digits gives does the following transformations to get the slot index:
1010 → 1100 → 110 → 6.
In total, we have one hash function for each permutation of {1, 2, 3, 4}. Is this a universal
hash family? Explain your answer.
Page 9
11. Suppose we want to implement a special, multi-part data structure. There is a stack and a linked list (think of it as “the garbage bin”). The operations are as follows:
• push: pushes an element onto the stack;
• pop: pops an element off the stack and appends it to the tail of the linked list;
• k-pop: calls pop on each of the top k elements on stack A (or all the elements if the stack has less than k elements), just like we saw in class;
• empty: deletes each element in the linked list (“we empty the garbage bin”). Note that the cost of empty is linear in the number of elements in the linked list.
Using the accounting method, devise an accounting scheme to show that any sequence n operations consisting of push, pop, k-pop, and empty operations can be processed in linear time.
Page 10