

Henry S. Baird Spring 2010 Course Advanced Algorithms CSE 498 (CRN 14799) Note: this is an extended, graduatelevel 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 onehour 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:
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 3hour final exam: all are closedbook, inclass, 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:001:00 PM, or by appointment. Grader: (for the CSE/Math 340 Homework) Ulit Jaidee, ulj208@lehigh.edu. Office Hours: Wednesdays 1:002:00 PM, in PL 514B, or by appointment. Prof. Baird will grade all the exams and the CSE 498specific homeworks, projects etc.Course Site: CSE498010SP10 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 9780262033848 hardcover, or 9780262533058 paperback). Note: we will use the THIRD edition. You do not need to buy the companion Java CDROM. 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, PrenticeHall (Englewood Cliffs, NJ), 1982 (ISBN 0131524623). PrerequisitesCalculus 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.12, B.13, 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.


