Spring 2008

(no courses taken)

Fall 2007

Graduate Algorithms (CS:473g)

Professor: Sariel Har-Peled

Primary textbook: Jon Kleinberg and Eva Tardos. Algorithm Design. Addison Wesley, 2005. (Amazon.com)

Topics covered: NP Completeness, Dynamic Programming, Approximation Algorithms, Randomized Algorithms, Network Flow, Linear Programming, Entropy

Logical Foundations of Computer Science (CS:498mv)

Professor: Mahesh Viswanathan

Topics covered: Propositional Logic, Resolution, Compleneteness, Compactness, First / Second / Monadic Second Order Logic, Tree Languages, E-F Games, Fagin's Theorem, Courcelle's Theorem

Spring 2007

Computational Complexity(CS:579)

Professor: Manoj Prabhakaran

Primary textbook: Sanjeev Arora and Boaz Barak. Complexity Theory: A Modern Approach. Webdraft, January 2007.

Topics covered: Time complexity, Diagonalization, Time/Space Hierarchy, Polynomial Hierarchy, Circuit Complexity, Interactive Proofs, Complexity of Counting

General Topology (MATH:535:D1)

Professor: Daniel R. Grayson

Primary source of course material: the lecture notes of Friedhelm Waldhausen

Topics covered: Space-filling curves, Homeomorphisms, Connectedness, Compactness, Hausdorff, Products, CoProducts, Zorn's Lemma, Images, CoImages, Quotient Spaces, Simplicial Complexes

Fall 2006

Approximation Algorithms (CS:598:CC)

Professor: Chandra Chekuri

Primary textbook: Vijay Vazirani. Approximation Algorithms. Springer-Verlag 2004. (Amazon.com)

Topics covered: NP Optimization problems, Approximation Ratio, Greedy methods, Local search, Linear Programming rounding, Knapsack, Bin packing, Scheduling, Network design, Constraint satisfaction, Cut problems, routing problems

Combinatorial Mathematics (CS:571 / MATH:580)

Professor: Douglas West

Primary textbook: Douglas B. West. Combinatorial Mathematics. Preprint, Fall 2006. (I found some typos!)

Topics covered: Combinatorial Arguments, Recurrence Relations, Generating Functions, Inclusion-Exclusion, Polya-Redfield Counting, Matchings, Connectivity and Cycles, Coloring, Planar Graphs, Ramsey Theory, POsets, Probabilistic Method, Arrangements

Spring 2006

Topics in Algorithms: Data Structures (CS:573:C)

Professor: Jeff Erickson

Topics covered: Bentley-Saxe logarithmic method, local and global rebuilding, splay trees, maintaining dynamic data structures, kinetic data structures, persistent data structures, bit tricks

Notes I scribed: Kinetic Data Structures

Randomness and Quasirandomness in Combinatorics and Computational Geometry (MATH:595:CGC)

Professor: Zoltan Furedi

Recursive Function Theory (MATH:573:C1)

Professor: Lou van den Dries

Fall 2005

Computational Geometry (CS:598:EAR)

Professor: Edgar A. Ramos

Primary textbook: M. de Berg, M. Overmars, M. van Kreveld, O. Schwarzkopf. Computational Geometry: Algorithms and Applications. 2nd revised edition. Springer, 2000. (Amazon.com)

Topics covered: convex hulls, linear programming, Voronoi diagrams, Delaunay triangulations, planar subdivisions, range spaces, VC-exponent, epsilon-approximations, configuration spaces

Fun with Expanders (CS:598:MAN)

Professor: Manoj M. Prabhakaran

Class "blog"

Article about Expanders on Wikipedia