AL. Algorithms and Complexity (31 core hours)

AL1. Basic algorithmic analysis (core -- 4 hours)

  Asymptotic analysis of upper and average complexity bounds
  Identifying differences among best, average, and worst case behaviors
  Big "O" and little "o" notation
  Standard complexity classes
  Time and space tradeoffs in algorithms
  Using recurrence relations to analyze recursive algorithms

AL2. Algorithmic strategies (core -- 6 hours)

  Brute-force algorithms
  Greedy algorithms
  Divide-and-conquer
  Backtracking
  Branch-and-bound
  Heuristics
  Pattern matching and string/text algorithms
  Numerical approximation algorithms

AL3. Fundamental computing algorithms (core -- 12 hours)

  Simple numerical algorithms
  Sequential and binary search algorithms
  Quadratic sorting algorithms (selection, insertion)
  O(N log N) sorting algorithms (Quicksort, heapsort, mergesort)
  Hash tables, including collision-avoidance strategies
  Binary search trees
  Representations of graphs (adjacency list, adjacency matrix)
  Depth- and breadth-first traversals
  Shortest-path algorithms (Dijkstra's and Floyd's algorithms)
  Transitive closure (Floyd's algorithm)
  Minimum spanning tree (Prim's and Kruskal's algorithms)
  Topological sort

AL4. Distributed algorithms (core -- 3 hours)

  Consensus and election
  Termination detection
  Fault tolerance
  Stabilization

AL5. Basic computability theory (core -- 6 hours)

  Finite-state machines
  Context-free grammars
  Uncomputable functions
  The halting problem
  Implications of uncomputability

AL6. The complexity classes P and NP

  Tractable and intractable problems
  Definition of the classes P and NP
  NP-completeness (Cook's theorem)
  Standard NP-complete problems
  Reduction techniques

AL7. Automata theory

  Deterministic finite automata (DFAs)
  Nondeterministic finite automata (NFAs)
  Equivalence of DFAs and NFAs
  Regular expressions
  The pumping lemma for regular expressions
  Push-down automata (PDAs)
  Relationship of PDAs and context-free grammars
  Properties of context-free grammars
  Turing machines
  Nondeterministic Turing machines
  Sets and languages
  Chomsky hierarchy

AL8. Advanced algorithmic analysis

  Amortized analysis
  Online and offline algorithms
  Randomized algorithms
  Dynamic programming
  Combinatorial optimization

AL9. Cryptographic algorithms

  Historical overview of cryptography
  Private-key cryptography and the key-exchange problem
  Public-key cryptography
  Digital signatures
  Security protocols
  Applications (zero-knowledge proofs, authentication, and so on)

AL10. Geometric algorithms

Line segments: properties, intersections
Convex hull finding algorithms