CSE 332 Autumn 2013 Final Exam: Thursday, December 12, 2013

8:30-10:20am

The final will be in SIG 134 (our regular classroom)

• Exam policies
  • Closed book, closed notes, no calculators allowed.
  • The exam begins promptly at 8:30 and ends at 10:20.
• The final will focus on all material studied since the midterm. This is roughly: Sorting, Graphs, Parallelization, Concurrency, Amortization
• 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. I will not ask you to actually *do* an AVL insertion or a B-tree insertion/deletion, but having a reasonable idea of how these work would be a good idea.

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 asked to give full proof
• But may be asked to use similar techniques
• Be familiar with the ideas
• Graphs - In general, know how to carry out the operation/algorithm & running time.
• Graph Basics
  • Definition; weights; directedness; degree
  • Paths; cycles
  • Connectedness
  • DAGs
• Graph Representations
  • Adjacency List
  • Adjacency Matrix
  • What each is; how to use it; pros and cons of each.
• 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
• Amortized Analysis
• Difference between amortized and worst case performance
• Why amortized analysis is useful

Stuff that you will NOT be tested on:

• Eclipse
• Generics
• Junit
• Java syntax

Misc.:

• Note that you WILL likely 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. 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 the course of the proof.
• 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. Our hope is that these exams will be useful in your studying, HOWEVER you should not take them as a guarantee of exactly what your exam will be like this quarter.

Previous CSE 332 Exams

• CSE 332 12sp final (Soln)
• CSE 332 12wi final (Soln)
• CSE 332 12su final (Soln) Note: this exam was only 90 minutes long.
• CSE 332 10sp final (Soln)
• CSE 332 10su final (no solution available) Note: this exam was only an hour long.
• CSE 332 10su final review slides

  Good luck with your exam studying!