UNB/ CS/ David Bremner/ teaching/ cs3383/ tests/ Final Exam


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


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
        i = random(n)

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)
        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

Topological Sort

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

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

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.


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)
        parallel_merge(A, lo, mid, hi)

Assume that parallel_merge takes Θ(k) work and has span Θ(\log^2(k)) when called on k elements (i.e. hi-lo = k).

  1. Give a recurrence for the work T₁ of mergesort.
  2. Give a Θ bound for recurrence of part (1).
  3. Give a recurrence for the span T_∞ of mergesort.
  4. 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.