Specialisation elective of Part 3, semester 2: COMPSCI 320 - "Applied Algorithmics"

This course seems to be a sequel of COMPSCI 220 - "Algorithms and Data Structures". In 220, allegedly, some basic algorithmic concepts (like "big-O" or hash tables) were taught; here in 320, they seem to try to be more systematic, and to give some overview (i.e., some higher level understanding) of those algorithms and stuff from 220, and more.

  1. (initial teasers)
    • Review of terminology
      • Big-{ O | Theta | Omega}
      • Graph jargon
    • Stable marriage problem: Gale-Shapely algorithm
    • Graph planarity testing: DMP algorithm
  2. Greedy algorithms
    • examples
      • interval scheduling
      • shortest path
        • Dijkstra's algorithm, Bellman-Ford algorithm
      • making change / counting coins
      • fuelling up gas at various gas stations on a 1-dimension trip
      • Huffman encoding
    • proof of correctness
      • "staying ahead", "lower bound constraint", "exchange argument"
      • modifying the optimal solution to the greedy solution without loss of optimality
  3. Divide and conquer
    • mergesort
      • study of time complexity of recursive algorithms
        • Master Theorem
    • closest pair of points on a 2-D plane
    • k-th smallest element in a sequence
    • matrix multiplication: less than O(n^3), e.g. Strassen algorithm
    • fast Fourier transform
  4. Dynamic programming
    • the necessary "optimal sub-structure property" of a problem in order for DP to be useful
    • examples
      • weighted interval scheduling
      • arbitrary-piece-count piece-wise linear curve-fitting (with more punishment for using more pieces)
      • knapsack problem (binary version: one of each type of item only)
      • egg-dropping problem (figure out the "highest safe floor" using minimal number of drops)
      • "optimal stopping problem": hiring one "good" or "bad" applicant for the remaining time
      • Floyd's algorithm, Bellman-Ford algorithm
  5. NP-completeness etc.
    • "(polynomial time) reduction" (of problems to other problems)
    • studied problems (usually reducing among each other):
      • (maximum) independent set (IS)
      • (minimum) vertex cover (VC)
      • (minimum) set cover (SC)
      • constraint satisfaction problem
        • 2-SAT, 3-SAT
        • circuit-SAT
        • polynomially reducing 3-SAT to IS
      • subset sum (SS)
    • decision problems vs. optimization problems: polynomially-reducible to each other
    • "pseudo-polynomial problems" (e.g., SS): poly on the value, not on the bitstring length
    • P, NP
    • NP-completeness
    • NP, co-NP: on the asymmetry between proving "yes" and "no" for a decision problem
      • primality testing: testing for a number to be prime, then to not be prime
        • in both NP & co-NP
      • integer factorization: also in both NP & co-NP
  6. Randomized algorithms
    • exercise:
      • simulating a biased coin using a fair coin
      • simulating a fair coin using a biased coin
    • categorization:
      • Monte Carlo vs. Las Vegas
      • biased MC algorithms (e.g. "yes"-biased: if it says yes, it's right.)
        • checking matrix multiplication results, determinant calculations
        • (biased/"half") primality testing
    • "p-correct" stochastic algorithm
    • amplification of stochastic advantage: the signal vs. noise view of random events
    • multiple-correct-answer problems: correct answers competing among each other while the wrong answer wins
    • converting between MC & LV algorithms
    • more complexity classes:
      • ZPP, BPP
      • RP, co-RP