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.

Exam 2 is NON-CUMULATIVE, which means it will only focus on the second half of the class. This is roughly: Sorting, Graphs, Parallelism, Concurrency. This quarter P/NP is covered on EX12 and thus will NOT be a topic for Exam 2. You should ignore questions on P/NP found on previous exams.

Possible topics Include at least: (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 and properties (stable, in-place, etc.)
• Know how to carry out the sort
• Lower Bound for Comparison-based Sorting
• 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

Topics not tested on

• P/NP
• Parallel sorting algorithms
• 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!