- The final exam has been scheduled by the registrar for April 12,
2018 at 9AM in the Curry Centre.
- Plan to arrive around 20 minutes early.
- The exam is closed book, and 3 hours long.
- The exam is worth 50% of your final mark.
- As per the the syllabus, you must pass the final exam to get more
than a D in the course.
Topics
1 Analysis Techniques
- Asymptotics
- Big O
- big Omega
- big Theta.
- geometric series
- Randomized Analysis
- Linearity of Expectation
- Indicator Variables
- Independence
- Expected number of trials before success.
- Recurrences
- Recursion tree
- Master Theorem
- Substitution/induction method
- Amortized / Charging Schemes
- charging long and short steps in Disjoint sets
- charging complete and incomplete steps in Multithreaded Scheduling
- memoization analysis
2 Design Paradigms
- Divide and Conquer
- Integer multiplication
- (Randomized) Median Finding
- Matrix multiplication
- Merge Sort
- Greedy
- Local Improvement / Swapping argument
- MST
- Cut Property
- Prim's Algorithm
- Kruskals Algorithm
- Huffmann Trees
- Dynamic Programming
- DAG Model
- sequence problems (edit distance, LIS)
- Planning problems
- Backtracking
- expand + test framework
- Backtracking for SAT
- n-queens
- subset sum
- Branch and Bound (time permitting)
3 Multithreaded Algorithms
- Primitives
- spawn
- sync
- parallel for
- implementation of parallel for with spawn
- DAG Model
- work
- span
- parallelism
- Greedy scheduling
- examples
- fibonacci
- matrix-vector product
- matrix product
- race conditions
4 Tools
- Disjoint Set Data Structures
- Topological Sort
Sample exam questions
Note that final exam also covers the material covered by
midterm 1 and midterm 2
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 2b × a, and takes
Θ(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 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 )), n2 ))
z ← plus(z, Mult(xR , yR ))
return z
end function
Recurrences
Let T (n) = T (n/4) + T (n/2) + Θ(n). Prove by substitution that
T (n) ∈ O(n)
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.
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
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 contains e
, and as many
edges of T
as possible.
- Give a condition on e
and T
that guarantees T'
has
smaller total weight than T
.
Heaviest Edge
- Give sufficient conditions for the unique heaviest edge in a graph
not to be in any minimum spanning tree.
- Prove your conditions.
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.
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
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₁
of mergesort
.
- Give a
Θ
bound for recurrence of part (1).
- Give a recurrence for the span
T_∞
of mergesort
.
- Give a big-O bound for the recurrence of part (3).
Backtracking, 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.