**Sorting:**- Quadratic Sorts: Insertion Sort, Selection Sort
- Faster Sorts: Heap, Merge, Quick
- Sub Linlog Sorts: Bucket Sort, Radix Sort
- Understand their runtimes (best and worst case)
- Understand the lower bound for comparison-based sorting

**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 ForkJoin code
- Parallel Prefix Sum Algorithm, Filters, etc.
- Analysis of Parallel Algorithms
- Parallel Sorting
- Amdahl's Law

**Concurrency and Synchronization:**- Race Conditions
- Bad Interleavings
- Synchronizing your code
- Mutexes
- Deadlock

**Graphs:**- Graph Definitions
- Directed/Undirected
- Weighted/Unweighted
- Simple/Multi
- Walks, paths, cycles
- Connectedness
- Trees, DAGs
- Graph Definitions
- Adjacency List
- Adjacency Matrix
- When to use each representation
- Graph Searches
- Breadth-First Search
- Depth-First Search
- Minimax
- Alpha-Beta
- Other Graph Algorithms
- Topological Sort
- Dijkstra's Algorithm
- Prim's Algorithm
- Kruskal's Algorithm

**Reductions & P/NP:**- Understand what a reduction is
- Understand what the complexity classes P/NP/EXP are
- Be able to explain why a decision problem is in P, NP
- Understand what NP-Complete and NP-Hard mean

**Pre-Midterm Material:**The exam will focus on the newer material, but there will likely be smaller questions that relate to the earlier material. Additionally, since much of the material builds on itself, it would be unwise to not study things like complexity analysis.

- Eclipse
- Generics
- JUnit Testing
- Java syntax

- Note that you
*will*be required to write Java code (in particular, it will be Fork-Join code), but we will not be sticklers for Java syntax. We will care about edge cases and correctness issues in your code. - 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 order to complete the proof.
- The homeworks thus far are a decent indication of the types of questions that could be asked.

**Stacks and Queues:**implementations, runtimes, when to use them**Big Oh (and Omega & Theta):**- Know the definition
- Be able to evaluate whether f(x) is O(g(x)), Big Omega, Big Theta
- Be able to find constants c & n0 to demonstrate Big Oh, Big Omega, Big Theta
- Examining code to determine its Big O running time.

**Recurrence Relations:**- Know closed form for common recurrence relations
- Given a recurrence relation, solve to closed form

**Amortized Analysis:**Be able to understand and analyze amortized runtime arguments**Binary Heaps:**- Structure & ordering properties
- Insertion, findMin, deleteMin, increaseKey, decreaseKey, remove, buildHeap
- Run-times for all the above; including intuition for expected O(1) for insert & O(n) for buildHeap
- Array representation
- d-heaps: how different/related to Binary Heaps

**Dictionary ADT:**insert, find, delete**Binary Search Trees:**- Binary property, BST ordering property
- Inorder, Preorder, Postorder traversals
- Find, insert & delete
- Run-times for all the above

**AVL Trees:**- BST with stored height & balance property
- Height bound resulting from balance property
- Insertions; different rotation cases, no delete
- Run-time for find & insert

**B-Trees:**- Motivation for the B-Tree; how it can minimize disk accesses
- Structure, ordering; use of M, L; principles behind the selection of M & L
- Insertion, find, deletion; the rules followed for insertion and deletion will be those shown in lecture
- Run-times of the above

**Hash Tables:**- Basics of good hash function design
- Collision resolution:
- Separate Chaining
- Open Addressing: Linear probing
- Open Addressing: Quadratic probing probing
- Open Addressing: Double hashing

- Strengths/weaknesses of the above versions
- Load factor
- Run-times for the different versions (though you do NOT need to memorize the equations for expected # of probes for a given load factor)
- Deletion
- Rehashing

- Eclipse
- Generics
- JUnit Testing
- Java syntax

- Note that you may be required to write pseudocode, but it will be evaluated as an algorithm, not as valid Java (or whatever) code
- 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 order to complete the proof.
- The homeworks thus far are a decent indication of the types of questions that could be asked.

TBD