Henry S. Baird    Spring 2009 Course


Advanced Algorithms
 
CSE 498    (CRN 14799)


Note:  this is an extended, graduate-level version of the undergraduate core course CSE/Math 340 Design and Analysis of Algorithms. Students will attend all 340 lectures (3 hours/week); in addition, they will attend a special seminar one hour/week. This is a 3 credit course. Assignments and Exams will consist of a subset of those for 340, plus problems special to this course.  Students will present summaries of certain topics in class.

The syllabus consists of the complete set of topics covered in CSE/Math 340, plus these:

• 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 algorithms
• Approximation algorithms for NP-complete problems
• (if there's time) Amortized algorithms

Instead of taking 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).

Classroom lectures:  MWF 11:10-12:00 AM in Packard Lab 416 (PL 416); also Mondays 4:10-5:00 PM in PL 508.

No student can take both this course and CSE/Math 340 for credit.

Notes for graduate students.  For CS MS & PhD students, this course counts as a Theory course for purposes of Breadth requirements. For CompE MS & PhD students:  both CSE/Math 340 and this course satisfy the Core (Breadth) Requirements; both CSE/Math 340 and this course satisfy Core Computer Software Systems.

A graduate student can test out of (avoid taking) the Ph.D. Algorithms Qualifier Exam by earning an A- or better in this course. (CSE/Math 340 cannot be used to test out of the Algorithms Qualifier.)

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.

Exams: There are two hour exams and a final 3-hour exam:  all are closed-book, in-class, written exams.   As an alternative to the final exam, students in CSE 498 may choose to carry out a software project or write a survey of the literature.

Grading: 80% Exams (20% 1st hour exam, 20% 2nd hour exam, 40% final exam/final project/final report); 20% Homeworks + Quizzes + Presentations.

Instructor:  Henry Baird, Prof., CSE Dept, hsb2@lehigh.edu. Office:  Packard Lab 514C.   Office Hours: Thursdays 11:00-12:00 AM or by appointment.

Grader: Bryan Auslander, bla204@lehigh.edu. Office hours:  Thursdays 10-11 AM, PL 514B or by appointment.

BlackBoard site:  Design & Analysis of Algorithms (SP09), CSE-MATH-340-010-SP09. We will use BlackBoard in this course to email announcements & distribute lecture notes, homeworks, grades, etc. Once you enroll in the course, browse bb.lehigh.edu, login using your Univ. email id and Portal password, and you should be admitted to this site. If you can't login, email the instructor immediately.

Textbook (required): Introduction to Algorithms (2nd Edition), Cormen, Leiserson, Rivest, & Stein, MIT Press (Cambridge, Massachusetts), 2001 (ISBN 0-262-03293-7).  You do not need to buy the companion Java CD-ROM. (Note:  the LU Bookstore stocks this.)

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

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.