Topics Include at least: (NOT NECESSARILY AN EXHAUSTIVE LIST)

• Stacks and Queues - array and linked list implementations. Runtimes.
• 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.
  • Best case, worst case, average case
  • Space complexity
  • Space/Time tradeoffs
• Recurrence Relations:
  • Know closed form for common recurrence relations
  • Given a recurrence relation, solve to closed form
• Binary Heaps:
  • Structure & ordering properties
  • Related: Perfect and Complete Trees.
  • 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
• Tries:
  • Find, insert & delete operations as described in P1
• 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 (you do not need to memorize the proof, but being familiar with how you construct the worst case AVL tree may be helpful)
  • 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

Topics you will NOT be tested on:

• IntelliJ
• Generics
• Java syntax

Misc

1. Note that you may be required to write pseudocode, but it will be evaluated as an algorithm, not as valid Java (or whatever) code.

2. 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.

3. The homeworks and section problems thus far are a decent indication of the types of questions that could be asked.

Topics Include at least: (NOT NECESSARILY AN EXHAUSTIVE LIST)

• Topics from the first half (see the Midterm Topics list)
• Hashtables:
  • Basics of good Hash function design
  • Different versions of collision resolution:
    • Separate Chaining
    • Open Addressing: Linear probing
    • Open Addressing: Quadratic 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 (that is, the process of resizing a hash table)
• 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
• 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
• Parallel Sorting
• Amdahl's Law
• 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
• 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 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.