

Henry S. Baird Spring 2013 Course Advanced Algorithms CSE/Math 441 3 credits CRN 16763 Note to all students: this is a graduatelevel version of the undergraduate Algorithms course CSE/Math 340, which covers fewer topics and is generally easier; no student may take both of these courses for credit. Note to CS Ph.D. graduate students: all firstyear CS Ph.D. students are required to take this course. Note to CS M.S. graduate students: this course fulfills both the "Theory" and "Applied Theory" skill areas. Algorithms are methods for solving information processing problems which are fully automatable and provably correct. We also need to understand their runtime and memory demands, especially on large inputs. Fast algorithms for hard, practically important problems are among the key discoveries of computerscience research. This course presents algorithms for searching, sorting, manipulating graphs and trees, scheduling tasks, finding shortest paths, matching patterns in strings, cryptography, etcand gives proofs of their correctness and analysis of their time and space complexity. General strategies for designing algorithmse.g. recursion, divideandconquer, greediness, dynamic programmingare stressed. Limits on algorithm efficiency are explored through NPcompleteness theory. Quantum computing is briefly introduced. Syllabus (approximate):
Course Objective: On completing this course, students will be able to design algorithms and to apply knowledge of complexity; and, more generally, to apply mathematics to CS problems. They will be sufficiently familiar with the theory, practice, notation, and vocabulary of algorithm design and analysis to be able to locate in the literature (or design from scratch) provably correct andto the extent possibleefficient algorithms to solve a wide range of problems. They will understand how to judge whether or not a new problem is likely to have an efficient algorithm. They will also have a grasp of basic engineering issues arising in the implementation, adaptation, and application of algorithms. Instructor: Henry Baird, Prof., CSE Dept, hsb2@lehigh.edu. Office: Packard Lab 380. Office Hours: Wednesdays 12:101:00 PM, or by appointment. Lectures: Tuesdays/Thursdays, 2:35  3:50 PM (the classroom is not yet assigned). Exams: There is one hour exam (inclass midterm) and, by default, one final 3hour exam: these are written openbook exams. Instead of taking a final exam, students have these alternative options: (a) carry out a challenging algorithm design project; or (b) write an extended technical report (e.g. a thorough critique of the literature about an algorithm or problem). Grading: 25% homework, 25% hour exam, 50% final exam/final project/final report). CourseSite: CSE441Math441SP13 Advanced Algorithms. We will use the online facility CourseSite to distribute assigned readings, lecture notes, homeworks, grades, etc. Once you enroll in the course, browse coursesite.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): S. Dasgupta, C. Papadimitriou, and U. Vazirani, Algorithms, McGrawHill, 2008, 336 pages, softcover. (ISBN13 9780073523408; ISBN10 0073523402) [publisher's page]. A desk copy may be consulted in the CSE Dept office PL 354 when the office is open (but the copy cannot be taken away). Another extra copy is available in Dr. Baird's office (PL380) when he's there (but, again, the copy can't be taken away). Supplementary text (not required): Prerequisites:
If you have any questions, ask the instructor: Henry Baird, hsb2@lehigh.edu. Accommodations for Students with Disabilities: If you have a disability for which you are or may be requesting accommodations, please contact both your instructor and the Office of Academic Support Services, University Center 212 (6107584152) as early as possible in the semester. You must have documentation from the Academic Support Services office before accommodations can be granted.


