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

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

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
    • Greedy scheduling
  • Dynamic Programming
    • DAG Model
    • sequence problems (edit distance, LIS)
    • Planning problems
    • memoization
    • dynamic programming via iteration
  • Backtracking
    • expand + test framework
    • Backtracking for SAT
    • n-queens
    • subset sum

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

Minimum Spanning Tree

Dynamic Programming

Multithreaded Algorithms

1 Write a multithreaded algorithm to compute the product of an n × n matrix and an n-vector.

2 Consider the following parallel search algorithm.

function ParStupidSearch (A, p, q, k)
  If p > q return FALSE
  If A[p] = k  return TRUE
  right ← spawn ParStupidSearch(A, p + 3, q, k)
  left ← ParStupidSearch(A, p+1, max(p + 2,q), k)
  sync
  return left or right
end function

Sample assignment questions