COSC6111 Advanced Algorithm Design and Analysis
This is an advanced theory course directed at non-theory students with
the standard undergrad background. The goal is to survey the key
theory topics that every computer science graduate student should
know. In about two weeks for each selected topic, we will gain
insights into the basics and study one two example in depth. These
might include:
- Divide and Conquer: fast fourier transformations
- Recursion: parsing
- Greedy Algorithms: matroids
- Amortized Analysis: union find
- Dynamic Programming: parsing CFG
- Network Flow: steepest assent, Edmonds-Karp, matching
- Randomized Algorithms: chernoff bounds, primes
- NP-completeness: reductions
- Approximation Algorithms: knapsack
- Linear Programming: what to put in a hotdog
- Distributed Systems: mud on forehead & common knowledge
- Computability: reducibilities and oracle computations
- Concurrency Theory:
- Cryptography: RSA
- Structural Complexity: polytime hierarchy, P-space, Exp-time
- Data Structures: dynamic perfect hashing
- Quantum algorithms: Shor's factoring algorithm or Grover's database
searching algorithm
Students will be expected to give a presentation on some topic new to
them and solve difficult homework assignments.
Prerequisite: COSC3101 and any fourth year theory course.
Course Rationale
- There needs to a 6xxx course for non-theory grad students to take to
cover their theory requirement.
- It should not be excluded for those students who have taken COSC 4101
or 5101. (Many who went York undergrads have)
- It should cover many theory topics so that a student who takes only
one theory course will have some exposure to them.
- It should be challenging, but accessible to non-theory students.