- Exam policies
- Closed book, closed notes, no calculators allowed.
- The exam begins promptly at 2:30 and ends at 4:20.
- The final will cover all material studied since the midterm.
This is roughly: Sorting, Graphs, Parallelization, Concurrency
- Check the lecture calendar for links to all slides and ink used in
class, as well as readings for each topic.
- Note that the material in this course tends to build on itself,
so it would also be reasonable to expect you to remember the basics
of data structures covered earlier in the quarter or what big-O
etc. means.
Topics (not necessarily an exhaustive list):
- Sorting
- Sorts:
- Simple Sorts: Insertion Sort, Selection Sort
- Heap Sort
- Merge Sort
- Quick Sort
- Bucket Sort & Radix Sort
- Know run-times
- Know how to carry out the sort
- Lower Bound for Comparison-based Sorting
- Won't be ask to give full proof
- But may be asked to use similar techniques
- Be familiar with the ideas
- Graphs
- Graph Basics
- Definition; weights; directedness; degree
- Paths; cycles
- Connectedness
- DAGs
- Graph Representations
- Adjacency List
- Adjacency Matrix
- What each is; how to use it
- Graph Traversals
- Breadth-First
- Depth-First
- What data structures are associated with each?
- 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
- Be able to write pseudo-code
- Reduce: parallel sum, multiply, min, find, etc.
- Map: bit vector, string length, etc.
- Parallel Prefix Sum Algorithm, Filters, etc.
- Analysis of Parallel Algorithms
- Parallel Sorting
- Amdahl's Law
- Concurrency
- Race Conditions
- Data Races
- Synchronizing your code
- Locks, Reentrant locks
- Java's synchronize statement
- Readers/writer locks
- Deadlock
- Issues of critical section size
- Issues of lock scheme granularity coarse vs fine
- Knowledge of bad interleavings
- Condition Variables
- Be able to write pseudo-code for Java threads & locks
Stuff that you will NOT be tested on:
- Eclipse
- Generics
- Junit
- Java syntax
Misc.:
- Note that you WILL be required to write Java code (in particular
Fork-Join or Java thread code), but we will not be sticklers for
Java syntax. Edge cases and other details of a correct algorithm
- yes, semicolons - no.
- Writing a simple proof of some sort is a possibility
- The homeworks are a decent indication of the types of
questions that could be asked
Previous Exams
This quarter's final will be along the same general lines as 332
final exams from previous quarters & 326 finals and midterms in
prior quarters, though the topics covered may vary (especially from
those in the 326 exams). Our hope is that these exams will be
useful in your studying, but you should not take them as a guarantee
of exactly what your exam will be like this quarter.
Previous CSE 332 Exams
Old CSE 326 Exams
We did not cover as many priority queues and balanced trees, so ignore
questions about skew heaps, leftist heaps, binomial queues, null path
lengths, and splay trees. Many of the old exams do not have sample
solutions available, but feel free to post to the message board or ask
the course staff if you have questions.
Good luck with your exam studying!