CSE332 Summer 2010 Final Exam
The exam will take place August 20th at the usual time - 10:50 to 11:50 - in class. You'll have the full hour to work through it. Calculators allowed (though shouldn't be necessary), but no notes or books.
The final will cover all material studied since the midterm, with the exception of NP complexity, which will not be on the exam.
Resources:
- About the final: pptx pdf
- Final Review Slides (doesn't cover all topics): here
- Spring 2010 332 Final: here; note: this final's session was 2 hours long; twice ours
- Info on Winter 2010 326 Final (with sample exams at bottom): here; note: the final's session was 2 hours long, and 326 covered some different topics than were covered in 332
List of Topics on the Final:
- Sorting
- Simple Sorts: Insertion Sort, Selection Sort
- Heap Sort
- Merge Sort
- Quick Sort
- Lower Bound for Comparison-based Sorting
- Bucket Sort & Radix Sort
- Graphs
- Graph Basics & Representations: Adjacency List & Adjacency Matrix
- Graph Traversals
- Topological Sort
- Dijkstra's Algorithm for Finding Shortest Paths
- Prim's Algorithm for Finding Minimum Spanning Trees
- Kruskal's Algorithm for Finding Minimum Spanning Trees
- Parallelism
- ForkJoin Parallelism, and Associated Terms (Work, Span, etc.)
- ForkJoin Applications, ex: Parallel Summing of an Array
- Parallel Prefix Sum Algorithm, Filters, etc.
- Analysis of Parallel Algorithms
- Parallel Sorting
- Amdahl's Law
- Concurrency
- Race Conditions
- Data Races
- Locks & Synchronization
- Course-grained vs Fine-grained Locking; Critical Section Size
- Deadlocks
- Condition Variables
- Amortized Analysis
Topics Not on the Final:
- NP Complexity
- The Material Covered by the Midterm; Hashtables and Before