• All Midterm Concepts
  • add "heap" and "graph" to the Data Structures bullet

• Heaps
  • heap order property
  • array-based implementation
  • propagate-up/down operations
  • insertion, deletion, buildheap
  • applications: resource scheduling; simulations

• Selection
  • List, Tree, Heap-based selection
  • Quickselect

• Sorting
  • inversions, adjacent swaps
  • For each sorting algorithm: Insertion Sort, Heapsort, Shellsort, Mergesort, Quicksort, Bucketsort...
    • How they work
    • Running times: best, worst, average
    • Best/worst case inputs

• Graphs
  • terminology (directed, weighted, path, cycle, etc.)
  • adjacency matrix vs. adjacency list implementations
  • breadth-first, depth-first traversals
  • topological orderings
  • shortest path problem (Dijkstra's algorithm)
  • minimum spanning tree problem (Kruskal's/Prim's algorithms)

• Algorithm Classification
  • greedy algorithms
  • divide-and-conquer algorithms
  • intractable problems
  • P and NP problems