- The final exam has scheduled by the registrar for December 8, 2016, at 9AM, in d'Avray South Gym.
- 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

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

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

.

- Explain how to create a new spanning tree

### Dynamic Programming

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

Suppose the courses in some university are numbered

`1...n`

and for each course`c`

you are given a set of prerequisites`P(c) = { p₁… pₖ }`

where`pᵢ ∈ { 1...n }`

. You may assume there are no prerequisite cycles.- Give a recursive function to compute the length of the longest sequence
`c₁, c₂… cₙ`

such that for`cᵢ`

is a prerequisite for`c_{i+1}`

- Give a non-memoization dynamic programming algorithm based on this recursive function.

- Give a recursive function to compute the length of the longest sequence

### Multithreaded Algorithms

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

Write a O(log n) span algorithm to multiply one row of a matrix by a vector.

Use a parallel for loop, along with your algorithm from part (a) to multiply a matrix by a vector.

Analyze the work and span of the resulting algorithm.

**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
```

- Give a recurrence for span of this algorithm
- Solve the recurrence

## Sample assignment questions

Write an

`O(m+n)`

time algorithm that, given a set of`m`

2SAT clauses with`n`

variables`x[j]`

, an index`j ∈ {1 … n}`

, and value`v ∈ { 0, 1 }`

, returns the set of "reduced" clauses after setting`x[j] = v`

, (set variable`j`

to value`v`

) i.e. remove satisfied clauses and false literals. Analyze your algorithm.In the text there is at a dynamic programming algorithm for TSP that runs in time

`O(n²2ⁿ)`

. Compare this to the`Ω(n·n!)`

brute force algorithm.At the beginning of lecture notes 05.1, there is a backtracking algorithm for subset sum. Rewrite this into the "test + expand" model given previously for SAT and N-Queens.

(ex 27.1-7 from Cormen et. al) Consider the following multithreaded pseudocode for transposing an n×n matrix A in place:

`P-TRANSPOSE (A) n ← A.rows parallel for j ← 2 to n parallel for i ← 1 to j - 1 swap A[i,j],A[j,i]`

Analyze the work, span, and parallelism of this algorithm.