Algorithms

Exam 1 Topics

• Module 0: Introduction
  • Stable Matching
  • Gale-Shapley Algorithm
• Module 1: Algorithm Analysis
  • Computational Tractability
  • Asymptotic Order of Growth
  • Implementing the Stable Matching Algorithm Using Lists and Arrays
  • Common Running Times
  • Priority Queues
    • Asymptotic order of growth for common operations
• Module 2: Graphs
  • Basic Definitions and Applications
    • Asymptotic order of growth for common tasks for both adjacency matrices and adjacency lists
  • Graph Connectivity and Graph Traversal
  • Implementing Graph Traversal Using Queues and Stacks
  • Bipartiteness
    • Testing bipartiteness
  • Connectivity in Directed Graphs
  • Directed Acyclic Graphs and Topological Ordering
• Module 3: Greedy Algorithms
  • Interval Scheduling
  • Scheduling to Minimize Lateness
  • Optimal Caching
  • Shortest Paths in a Graph
  • The Minimum Spanning Tree Problem
  • Implementing Kruskal's Algorithm: The Union-Find Data Structure (optional)
  • Clustering
  • Huffman Codes and Data Compression (optional)
• Module 4: Divide and Conquer
  • Mergesort
  • Recurrence Relations
  • Master Theorem
  • Counting Inversions
  • Finding the Closest Pair of Points
  • Integer Multiplication
  • Convolutions and the Fast Fourier Transform (optional)

For each algorithm:

• Asymptotic Order of Growth (its Big-O)
• Key point / distinguishing attribute / clever implementation