You will have 110 minutes to complete the exam. We will distribute the exam
early and you can read and fill out the cover page of the exam, but you should
not look at the exam questions until you are told to begin.
The exam will be closed book. You will not be allowed a calculator,
cell phone, or any other electronic device.
All material from Lecture 1 up to and including P/NP is fair game. The exam will
focus on the material from sorting onwards.
Reductions & P/NP:
- Quadratic Sorts: Insertion Sort, Selection Sort
- Faster Sorts: Heap, Merge, Quick
- Sub Linlog Sorts: Bucket Sort, Radix Sort
- Understand their runtimes (best and worst case)
- Understand the lower bound for comparison-based sorting
- ForkJoin Parallelism, and Associated Terms (Work, Span, etc.)
- ForkJoin Applications, ex: Parallel Summing of an Array
- Reduce: parallel sum, multiply, min, find, etc.
- Map: bit vector, string length, etc.
- Be able to write Java ForkJoin code
- Parallel Prefix Sum Algorithm, Filters, etc.
- Analysis of Parallel Algorithms
- Parallel Sorting
- Amdahl's Law
- Concurrency and Synchronization:
- Race Conditions
- Bad Interleavings
- Synchronizing your code
- Graph Definitions
- Walks, paths, cycles
- Trees, DAGs
- Graph Definitions
- Adjacency List
- Adjacency Matrix
- When to use each representation
- Graph Searches
- Breadth-First Search
- Depth-First Search
- Other Graph Algorithms
- Topological Sort
- Dijkstra's Algorithm
- Prim's Algorithm
- Kruskal's Algorithm
Pre-Midterm Material: The exam will focus on the newer material, but
there will likely be smaller questions that relate to the earlier material.
Additionally, since much of the material builds on itself, it would be unwise
to not study things like complexity analysis.
- Understand what a reduction is
- Understand what the complexity classes P/NP/EXP are
- Be able to explain why a decision problem is in P, NP
- Understand what NP-Complete and NP-Hard mean
The following topics will not
appear on the exam:
- JUnit Testing
- Java syntax
- Note that you will be required to write Java code (in particular,
it will be Fork-Join code), but we will not be sticklers for Java syntax. We
will care about edge cases and correctness issues in your code.
- Writing a simple proof of some sort is a possibility. Any such
proof will be intended to show that you know how to prove
things. You will not be expected to have a "magic insight" in
order to complete the proof.
- The homeworks thus far are a decent indication of the types of
questions that could be asked.
We strongly suggest that you try to solve all of these problems yourself, on paper
without looking at the answer key until you're done. You may also want to time yourself to practice your pacing.