- The final exam has been scheduled by the registrar at 2PM on December 19.
- The exam is online, open book, and 3 hours long.
- For exam weight, see evaluation
- Sample questions are given below
Recurrences
example 1
Let T (n) = T (n/4) + T (n/2) + Θ(n). Prove by substitution that
T (n) ∈ O(n)
example 2
Let T(n) = T(n/6) + T(4n/5) + Θ(n)
. Show that T(n) ∈ O(n)
Divide and Conquer
Binary Multiplication
In the following, suppose x and y are two n bit numbers, where n = 2ᵏ for some integer k. The function shiftl(a, b) returns 2ᵇ × a, and takes Θ(log b) time. The function plus(a, b) returns a + b and takes Θ(log a + log b) time (i.e. plus(x, y) would take Θ(n) time). Analyze the complexity of the following algorithm.
function Mult(x, y)
Let n = bits(x) = bits(y)
if n=1 return x*y
Let xL (yL ) be the left n/2 bits of x (y).
Let xR (yR) be the right n/2 bits of x (y).
z ← shiftl(Mult(xL , yL ), n)
z ← plus(z, shiftl(plus(Mult(xL , yR ), Mult(xR , yL )), n/2 ))
z ← plus(z, Mult(xR , yR ))
return z
end function
Randomized Algorithms
Recursive example 1
function foo(n)
if n ≤ 1
return
else
i = random(n)
foo(i)
end
end
Suppose that random(n)
takes Θ(1)
time to return a random integer
between 1
and n
inclusive.
Give a recurrence for the running time of
foo(n)
. Use random variables to incorporate the behaviour ofrandom()
into your recurrence.Derive a recurrence for the expected running time of
foo(n)
.
Recursive example II: Loopy
Suppose that random(n) returns a random integer between 1 and n inclusive. What is the expected running time of Loopy as a function of n and a. You may assume random(n) takes Θ(1) time, and that 1 ≤ a < n/2.
function Loopy(n, a, j)
r ← random(n)
if (r ≤ a or r > n − a) then
return Loopy(n, a, j + 1)
else
return j
end if
end function
Randomized select
Consider the following randomized selection algorithm we studied in class.
You may assume RandomPartition
takes O(n)
def RandSelect (A, p, q, i):
if p == q:
return A[p]
r = RandPartition (A, p, q)
k = r – p + 1
if i == k:
return A[r]
if i < k:
return RandSelect (A, p, r – 1, i )
else
return RandSelect (A, r + 1, q, i – k )
Let Xⱼ
be the indicator variable defined by
Xⱼ = 1 if j = k = r-p+1
0 otherwise
Let n
denote q-p+1
.
Let T(n)
denote the (random) running time of this algorithm. Use your
indicator variables to show that
E[T(n)] ≤ 1/n ∑_{j=1}ⁿ E[max(T(j-1), T(n-j))] + O(n)
Minimum Spanning Tree
Local improvement
Let G = (V, E)
be a connected, undirected graph with distinct edge weights. Let T
be a
spanning tree of G
. Let e
be an edge of G
not in T
.
- Explain how to create a new spanning tree
T'
that containse
, and as many edges ofT
as possible. - Give a condition on
e
andT
that guaranteesT'
has smaller total weight thanT
.
Heaviest Edge
- Give sufficient conditions for the unique heaviest edge in a graph not to be in any minimum spanning tree.
- Prove your conditions.
Kruskal's Algorithm
Prove during the execution of Kruskal's algorithm (below) that X
always represents a forest, i.e. a graph without any cycles.
for u ∈ V:
makeset(u)
X ← {}
sort edges by weight
for (u, v) ∈ E:
if find(u) ≠ find(v):
X ← X ∪ \{(u, v)\}
union(u,v)
Topological Sort
- Explain what a topological sort of a DAG is.
- Give an algorithm to produce a topological sort.
- Prove your algorithm is correct.
Dynamic Programming
Longest Alternating subsequence
Given a sequence of nonzero integers, the longest alternating subsequence is the longest subsequence such that succesive elements of the subsequence change sign. For example given the sequence
1, 7, −3, −4, 5, 7, −9,
a (non-unique) longest alternating subsequence is 7, −3, 5, −9. We interested here in computing the length of the longest alternating subsequence.
Give a dynamic programming algorithm for this problem
- based on memoization
- without using memoization
Longest Divisor Sequence
This is a midterm question based on the previous question (also very similar to Longest Increasing Subsequence from class).
A divisor sequence from a list (array) S
, is a subsequence of
not-necessarily consecutive elements from S
such that each element
of the subsequence after the first divides the previous on. Given the input S
28, -3, 14, 7, −3, −4, 5, -7, −9, 1
The longest divisor sequence is 28, 14, 7, -7, 1
Give a recursive function that calculates the length of the longest divisor sequence. Your answer should use the mathematical function form from class, with two or cases. Do not write procedural code. Explain what your parameters mean.
Give a memoization based algorithm based on the first part.
- Give a non-memoization (non-recursive) based algorithm based on the first part.
Edit Distance
Edit distance measures the number of single character inserts, deletes, and substitutions needed to transform one string into another. Each set of editing operations can be represented as an alignment, i.e. a table where all non-matching positions cost one operation. For example the following alignment costs 5.
exam__ination
_caffeination
- Prove that if we remove any column from an optimal alignment, we have an optimal alignment for the remaining substrings.
- Give a recurrence to find the edit distance.
- Describe the DAG of subproblems for dynamic programming.
- Give an iterative (non-recursive) dynamic programming algorithm to compute edit distance.
University of Dynamic Programming
At the University of Dynamic Programming, you can take a course if you
have taken any one of it's prerequisites (i.e. all of the prequisite
lists are of the form "Course 1 or Course 2 or Course 3 ...").
Courses are numbered from 1
to n
across the entire University, and
each course is priced individually (according to a scheme based on
popularity). You may assume there are no directed cycles in the
prerequisite structure.
recursive function
Define a recursive function mincost(c)
for the minimum cost of
taking course c
. You may assume the existence of a function
prereqs(c)
that returns a list of prerequisite courses for course
c
, and a function tuition(c)
that returns the tuition for course
c
.
Hint: This should only be a few lines of pseudocode.
Memoization
Give a memoized implementation of mincost(c)
table driven algorithm
Give a non-memoized dynamic programming algorithm for mincost(c)
.
Hint: Think about the ordering of subproblems.
Huffman Tree
The cost of a Huffman tree is defined as ∑ᵢ f_i d_i
where f_i
is the frequency of symbol i
(part of the input to the
tree builder), and d_i
is the depth of symbol i
in the tree.
Prove that in any minimum cost tree with the two symbols with smallest
f_i
are on the lowest level.
Union Find
Prove that if we only union root elements x
and y
with rank(x) ==
rank(y)
, the invariant ∀ z rank(z) ≤ height(z)
is maintained
Multithreaded algorithms
Merge sort
function mergesort(A, lo, hi) // Sort A[lo...hi-1]
if lo+1 < hi then // at least two elements.
mid =⌊(lo + hi) / 2⌋
spawn mergesort(A, lo, mid)
mergesort(A, mid, hi)
sync
parallel_merge(A, lo, mid, hi)
end
end
Assume that parallel_merge
takes Θ(k)
work and has span
Θ(log^2(k))
when called on k
elements (i.e. hi-lo = k
).
- Give a recurrence for the work
T₁
ofmergesort
. - Give a
Θ
bound for recurrence of part (1). - Give a recurrence for the span
T_∞
ofmergesort
. - Give a big-O bound for the recurrence of part (3).
Counting non-zeros
Write a O(log n)
span algorithm to count the non-zero elements in
an array. Analyze the work and span of your algorithm.
Backtracking, SAT
Monotone SAT
Give a fast algorithm for solving monotone SAT problems, i.e. the input is CNF either without any negated variables, or with all negated variables.
Partition
The Partition problem is defined as follows. You are given a set S
of positive integers, and you need to decide is there is a partition
of S
into two sets disjoint sets U,V
such that ∑_{u ∈ U} u =
∑_{v∈ V} v
.
def backtrack(P_0):
Q = { P_0 }
while ! empty(Q):
P= Q.dequeue()
for R ∈ expand(P):
v = test(R)
if (v == True ): # SUCCESS
return R
elif (v == None): # UNKNOWN
Q.enqueue(R)
elif (v == False):
pass
- Define a representation for a partial solution to the partition problem with input
S
. - Give an
extend()
function for use in the generic backtracking algorithm above. - Give a
test()
function for use in the backtracking algorithm above. Your function should returnTrue
if the given subproblem is complete, i.e. it is a solution to the corresponding