Final exam policies

1. Closed book, closed notes.

2. No calculators, cell phones, or other electronic devices allowed.

3. You will be provided a reference sheet during the exam. We expect it to be this reference sheet, but might add more similar information if needed.

The final is cumulative, which means we can ask you about any topic from the whole class. That said, we will put significantly more focus on the second-half of the course. I will not ask you to actually *do* an AVL insertion, but having a reasonable idea of how these work would be a good idea. This is roughly: Sorting, Graphs, Parallelism, Concurrency, P/NP.

Possible topics Include at least: (NOT NECESSARILY AN EXHAUSTIVE LIST)

• Topics from the first half (see the midterm list)
• Sorting
• Sorts:
  • Simple Sorts: Insertion Sort, Selection Sort
  • Heap Sort
  • Merge Sort
  • Quick Sort
  • Knowing there are non-comparison based sorts, and that they require extra assumptions about the input; an extra video covers Bucket Sort & Radix Sort, though we won't ask you to execute these.
• Know run-times and properties (stable, in-place, etc.)
• 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?
• Dijkstra's Algorithm for Finding Shortest Paths
• Topological Sort
• Prim's Algorithm for Finding Minimum Spanning Trees
• Kruskal's Algorithm for Finding Minimum Spanning Trees
• Use of Disjoint Sets in Kruskal's Algorithm
• Parallelism
• 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 fork join code for simple maps & reductions
• Parallel Prefix Sum Algorithm, Filters, etc.
• Analysis of Parallel Algorithms
• Amdahl's Law
• Given a scenario, use maps, reduces, filters and/or packs to give a high-level algorithm description
• Concurrency
• Race Conditions
• Data Races
• Bad Interleavings
• Synchronizing your code
  • Locks, Reentrant locks
  • Java's synchronized statement
  • Issues of lock scheme granularity: coarse vs fine
  • Issues of critical section size
  • Deadlock
• Be able to write pseudo-code for Java threads & locks
• P, NP, NP-completeness
• What does each of these classes mean
• Examples of problems in each class (problems will either be ones we've explicitly discussed or closely-related problems)
• What to do if you think the problem you are trying to solve is NP-complete?

Topics not tested on

• IntelliJ
• Generics
• Java syntax

Misc

• Note that you WILL likely be required to write Java code (in particular Fork-Join code), but we will not be sticklers for Java syntax. Edge cases and other details of a correct algorithm - yes, semicolons - no.

Good luck with your exam studying!