Henry S. Baird    Spring 2010 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 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 may 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, in PL 514B (separate from CSE/Math 340).

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 required hour exams and (optionally) a 3-hour final 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:  Wednesdays 12:00-1:00 PM, or by appointment.

Grader: (for the CSE/Math 340 Homework) Ulit Jaidee, ulj208@lehigh.edu.  Office Hours: Wednesdays 1:00-2:00 PM, in PL 514B, or by appointment.  Prof. Baird will grade all the exams and the CSE 498-specific homeworks, projects etc.

Course Site:  CSE-498-010-SP10 Advanced Algorithms. We will use the online Course Site system in this course to email announcements & distribute lecture notes, homeworks, grades, etc. Once you enroll in the course, browse coursesite.lehigh.edu, login using your Lehigh id and password, and you should be admitted to this site. If you can't login, email the instructor immediately.

Textbook (required): T. Cormen, C. Leiserson, R. Rivest, & C. Stein, Introduction to Algorithms, 3rd Edition, The MIT Press,  Cambridge, Massachusetts, 2009 (ISBN 978-0-262-03384-8 hardcover, or 978-0-262-53305-8 paperback).  Note:  we will use the THIRD edition.  You do not need to buy the companion Java CD-ROM.  A desk copy may be consulted in the CSE Dept office PL 354 (but cannot be taken away). Another extra copy is available in Dr. Baird's office (PL514C), when he's there; but, again, it can't be taken away.

We follow the textbook closely.  Lectures may discuss only the most important topics in a section of the textbook, but students are expected to study the corresponding section completely. Unless stated otherwise, all material in covered sections is relevant to homework and tests.

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

Calculus II (Math 22 or Math 32) or close quivalent.

Discrete Structures (CSE/Math 261) or close equivalent.  To review your Discrete Structures background, look at the textbook's Appendix sections A.1-2, B.1-3,  C.1., & D.1.

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.