Henry S. Baird    Fall 2006 Course


Advanced Topics in Algorithms
 

Independent Study     CSE 492-14 / 392-14


Note to undergraduates:  you are welcome in this course if you excelled in CSE/Math 340 Design and Analysis of Algorithms (or in an equivalent course at another University).  You'll carry out the same presentations and exams as the grad students, but you'll report on fewer research papers and be allowed to choose a less time-consuming final project.  After I approve your joining the course, enroll for CSE 392-14 (3 credits); it can count as a technical elective.

A small, selective seminar on advanced topics in algorithms:

• Matroid theory:  a unifying framework for many problems which possess greedy algorithms
• Linear programming, Max-flow, Min-cost flow, Simplex algorithm, Kachian's algorithm, primal-dual algorithms
• Computational geometry:  closest-point, line-intersection, Voronoi diagrams, multidimensional search
• Randomized & amortized algorithms
• Approximation algorithms for NP-complete problems

In addition to occasional homework assignments, students will select topics from textbooks, or sets of related research papers (or a dissertation) from the literature, and present short talks in class summarizing and critiquing them.  There will be an in-class written open-book midterm exam.  Instead of a final exam, students can choose between (a) a software and/or experimental project or (b) a written report (e.g. an extended critique of the literature).

Please see/email the instructor for permission to join this seminar.
The course will meet in Packard Lab 514B twice a week at a time determined by the schedules of all the participants. 

Course objective: On completing this seminar, students will be sufficiently familiar with the theory and basic principles of advanced algorithms to be able to pursue many matters of interest in the current technical literature. 

Textbook (required): Introduction to Algorithms (2nd Edition), Cormen, Leiserson, Rivest, & Stein, MIT Press (Cambridge, Massachusetts), 2001 (ISBN 0-262-03293-7).  (Note:  the LU Bookstore does not stock this; order it privately, e.g. from Amazon.com.)

Supplementary text (not required):  Combinatorial Optimization: Algorithms and Complexity, C. H. Papadimitriou & K. Steiglitz, Prentice-Hall (Englewood Cliffs, NJ), 1982 (ISBN 0-13-152462-3).

Prerequisites

CSE/Math 340:  Design and Analysis of Algorithms -- or comparable background in fundamental algorithms and data structures.

Math 205: Linear Algebra etc -- or basic familiarity with linear algebra & matrices.

Math 231 or Math 309 or CSC 450: Applied Probability -- or basic familiarity with discrete probability theory.

If you have any questions about prerequisites, ask the instructor: hsb2@lehigh.edu.  He will be traveling in China (Beijing & Hong Kong) August 13-25, but he expects to be able to check email. He hopes to negotiate the time of the first meeting over the weekend of August 26/27, so please check email then.