Henry S. Baird    Spring 2010 Course


Advanced Algorithms
 
CSE/Math 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 CSE/Math 340 lectures (3 hours/week); in addition, they will attend a special one-hour seminar each week. This is a 3 credit course. Assignments and Exams will consist of a subset of those for CSE/Math 340, plus problems special to this course.  Students may 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
• Quantum Computing Algorithms
• (if there's time) 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 AM - 12:00 PM, Packard Lab 416 (the same as CSE/Math 340); and Mondays 4:10 - 5:00 PM, PL 514B.

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

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; and both CSE/Math 340 and this course satisfy Core Computer Software Systems.

This course is designed as an effective preparation for the CS Ph.D. Algorithms Qualifier Exam, normally given a couple of weeks after the end of the Spring term; CS PhD students are very welcome to "sit in on" this course without either registering for it or formally auditing it.

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/Math 441 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: <to be determined>.

Grader: <to be determined>

BlackBoard site:  Design & Analysis of Algorithms (SP10), CSE-MATH-340-010-SP10. 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 (3rd Edition), Cormen, Leiserson, Rivest, & Stein, MIT Press (Cambridge, MA, ISBN 978-0-262-03384-8).  (You do not need to buy the companion Java CD-ROM. There are no programming assignments.)

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.