# Course: COMPSCI 320

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.

- (initial teasers)
- Review of terminology
- Big-{ O | Theta | Omega}
- Graph jargon

- Stable marriage problem: Gale-Shapely algorithm
- Graph planarity testing: DMP algorithm

- Review of terminology
- 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

- examples
- Divide and conquer
- mergesort
- study of time complexity of recursive algorithms
- Master Theorem

- study of time complexity of recursive algorithms
- 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

- mergesort
- 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

- 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

- primality testing: testing for a number to

- 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

- exercise: