CSCE 629: Analysis of Algorithms
Fall 2012
Algorithm design and analysis is a fundamental and important part of computer science. This course introduces students to advanced techniques for the design and analysis of algorithms, and explores a variety of applications.
The topics and applications that we tentatively plan to cover include greedy algorithms, network algorithms and network design, huffman codes and data compression, NP-hardness, approximation and randomized algorithms. Enroute, we will encounter various useful ideas, including randomization, probabilistic analysis, amortized analysis, competitive analysis, eigenvalues, linear and semi-definite programming, high dimensional geometry, and random walks.
- September 4, 2012: This is a graduate (hence, advanced) algorithms class, which assumes that you have taken an introductory algorithms class. If you still find that you are missing necessary background material, one helpful resource may be the following introductory algorithms class with online video lectures and notes---I recommend that you closely study the materials, homeworks and solutions from that class.
- August 28, 2012: Homework 1A has been emailed to the class list. Please email me if you did not receive it.
- August 27, 2012: Right now, the class is totally full. The class capacity is limited to the registrar's room limit (58 in this case). Students wanting to be forced in should go to
this website
to enter a force request. At this point, it is basically first-come, first-served. We have 2 people on the waiting list right now.
- Professor: Evdokia Nikolova. Office: HRBB 515A.
Office Hours: Thursdays 10:50 am--11:50 am or by appointment.
- TA: Grant Fan (Email: grantfan AT cs.tamu.edu) Office: HRBB 328A.
Office Hours: Thursdays 3 pm--4 pm or by appointment.
- Lecture: Tuesday-Thursday 9:35 am--10:50 am @ HRBB 113.
- Textbook: There is no required textbook; however, the following text may be helpful:
- Algorithm Design by Jon Kleinberg & Eva Tardos.
Additional relevant research papers and surveys will be posted as the class develops the list.
- Prerequisites: A course in algorithms (CSCE 411 or equivalent), mathematical maturity.
- Assessment:
- 50% from homework problems;
- 25% from Exam #1 (on Oct.25, 2012);
- 25% from Exam #2 (on Dec 4, 2012).
There is a dynamic component to the course, as topics drop
in and out, or get longer or shorter treatment, depending on audience
interest/reaction/resistence. Given this, here is a rough outline of the course material:
- Greedy algorithms: Minimum spanning tree; Huffman codes and Data compression;
- Dynamic programming: Subset sum, Knapsack, Shortest paths;
- Network flow: Max flow, Min cut, Disjoint paths and other applications;
- NP and Computational Intractability: Polynomial-time reductions, SAT, Partitioning, Graph Coloring, etc.;
- Approximation algorithms;
- Randomized algorithms.
The lecture notes below, except otherwise stated, are from the course
Advanced Algorithms by Shuchi Chawla.
Abbreviations: K&T=Kleinberg & Tardos
- Lecture 1 (August 28, 2012): Course overview; Greedy Algorithms.
Notes. Suggested reading: K&T §2, §4.
- Lecture 2 (August 30, 2012): Divide & conquer algorithms.
Notes. Suggested reading: K&T §5.
- Lecture 3 (September 4, 2012): Dynamic Programming.
Notes. Suggested reading: K&T §6.
- Lecture 4 (September 6, 2012): Dynamic Programming. Shortest paths continued.
Notes. Suggested reading: K&T §6.
- Lecture 5 (September 11, 2012): Network Flow.
Notes. Suggested reading: K&T §7.
- Lecture 6 (September 13, 2012): Network Flow. Max-flow min-cut theorem.
Notes. Suggested reading: K&T §7.
- Lecture 7 (September 18, 2012): Bipartite Matching.
Notes. Suggested reading: K&T §7.
- Lecture 8 (September 20, 2012): Applications of network flow.
Notes. Suggested reading: K&T §7.
- Lecture 9 (September 25, 2012): Linear Programming (LP) Duality.
Notes.
- Lecture 10 (September 27, 2012): Randomized Algorithms.
Notes. Suggested reading: K&T §13.
- Lecture 11 (October 2, 2012): Karger's Global Min-Cut Algorithm.
Notes. Suggested reading: K&T §13.
- Lecture 12 (October 4, 2012): Problem solving session. Come with questions!
- Lecture 13 (October 9, 2012): Randomized Load Balancing (Balls and Bins). Notes. Suggested reading: K&T §13.
- Lecture 14 (October 11, 2012): NP-Completeness. Notes. Suggested reading: K&T §8.
- Lecture 15 (October 16, 2012): NP-Completeness continued. Notes. Suggested reading: K&T §8.
- Lecture 16 (October 18, 2012): Approximation Algorithms. Notes.
- Lecture 17 (October 23, 2012): Practice session for exam by Grant. Come with questions!
- Lecture 18 (October 25, 2012): Exam 1: CLOSED BOOK. Covering material up to and excluding NP-Completeness.
- Lecture 19 (October 30, 2012): Cancelled.
- Lecture 20 (November 1, 2012): Approximation Algorithm for Metric TSP. Notes.
- Lecture 21 (November 6, 2012): LP Relaxation & Rounding. Notes.
- Lecture 22 (November 8, 2012): LP Relaxation & Rounding for Facility Location. Notes.
- Lecture 23 (November 13, 2012): Polynomials and the Fast Fourier Transform. Guest lecture by Prof. Jennifer Welch. Notes.
- Lecture 24 (November 15, 2012): Randomized Rounding. Notes.
- Lecture 25 (November 20, 2012): Randomized Rounding for Routing to Mimize Congestion. Notes.
- Lecture 26 (November 27, 2012): Online Algorithms. 14.1, 14.6 of these Notes.
- Lecture 27 (November 29, 2012): Practice session.
LaTeX: Feel free to use the following template for writing your assignments in LaTeX. The template contains commands for Theorem, Lemma, Corollary, Proposition, Claim, Definition, Construction, Remark etc. An example file where this template is used is here which results in the following pdf.
Similar classes at other universities: