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.