CSCI 362 -- Exam 3 Review

Hash Table:

• insertion, removal, iteration with separate chaining

Divide and Conquer Algorithms (Non-sorting):

• nth_element
  • recurrence
  • complexity
• recursive median-of-five
  • how does it work
  • recurrence

Comparison-based Sorting:

• Shell Sort
  • h-sort
  • choosing a good "h" sequence
• Merge Sort
  • merge operation
  • out-of-place merge
• Quick Sort
  • partition (<=, >)
  • three-way partition (<, ==, >)
  • choosing a good pivot
• How each perform when data is:
  • reversed
  • sorted
  • almost sorted

Non-comparison-based Sorting:

• Radix Sort
• Counting Sort
• Complexity
• Limitations

Disjoint Sets

• Logical operations
• Be able to "trace" through sequence of operations

Graphs:

• Representation
  • Adjacency Matrix
  • Adjacency List
• Terms
  • Vertices, Edges
  • Directed vs. Undirected
  • Disconnected, Connected, Complete
  • Strongly vs. Weakly connected
  • Minimum Spanning Tree
  • Cycles
• Algorithms
  • Searching
    • Breadth-First
    • Depth-First
    • Be able to trace through an example!
  • Topological Sort
    • When to use
    • Algorithm
    • Be able to trace through an example
  • Minimum Spanning Tree
    • Prim's vs. Kruskal's
      • how both work
      • comparison between the two
      • be able to trace through an example
    • Complexity
  • Shortest Path
    • Dijkstra's
      • complexity
      • be able to trace through an example
    • Bellman-Ford
      • complexity
    • Note: they (ultimately) do the same thing

ACM Code of Ethics