

Henry S. Baird Spring 2006 Course Design & Analysis of Algorithms Algorithms are broadly applicable methods for solving information processing problems fully automatically and as efficiently as possible. They are among the central achievements of computer science research. This course presents algorithms for searching, sorting, manipulating graphs and trees, scheduling tasks, finding shortest paths, matching patterns in strings, etcwith proofs of their correctness and analysis of their runtime and memory requirements. Strategies for designing algorithmse.g. recursion, divideandconquer, greedinessare introduced. Limits on algorithm efficiency are explored through elementary NPcompleteness theory. Prerequisites: Math 22 and CSE/Math 261 (or close equivalents). This is a required course for these degrees: B.S. in CS (in RCEAS), B.A. in CS (in CAS), and the B.S. in Computer Science & Business (in RCEAS & CBE). It is also the basis for the CS PhD Qualifier exam for Algorithms. Course objective: On completing this course, students 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) correct and (to the extent possible) efficient algorithms to solve a wide range of problems. They will also have a grasp of engineering issues arising in the implementation and application of algorithms. Textbook: Anany Levitin, Introduction to the Design and Analysis of Algorithms, AddisonWesley (2003) (ISBN 0201743957). 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. Homework: There are weekly written homework assignments, due normally on Friday morning, to be handed in as hardcopy at the start of the class. For part of each Friday's class students are invited to present their solutions on the blackboard, for which they will receive credit (whether or not their solution is correct). Attendance and Quizes: Attendance in class is not required. There are, however, Pop Quizes, and a missing quiz results in zero points. Exams: There are two hour exams and a final exam: all are closedbook, inclass, written exams. Exams are not repeated: if under extraordinary circumstances a student cannot take an exam, it is assigned the average grade of the other two exams. Grading: 80% Exams (20% 1st hour exam, 20% 2nd hour exam, 40% final exam); 20% Homeworks+Quizzes+Presentations. Instructor: Prof. Henry Baird, hsb2@lehigh.edu; office: Packard Lab 514C. Office Hour: Tuesdays 12 PM or by appointment. Teaching Assistant: Fu Zhou, fuz204@lehigh.edu; office: desk #14 on 6th floor, Packard Lab. Office hour: Thursdays 10:4511:45 AM or by appointment. BlackBoard site: Design and Analysis of Algorithms (SP06), CSE340010SP06. We will use BlackBoard in this course to distribute lecture notes, homeworks, grades, etc. Browse bb.lehigh.edu, login using your Univ. email id and Portal password, and you should see that you have access to this course.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. Topics Covered (with textbook section nos.): If you have any questions, ask the instructor: hsb2@lehigh.edu. 

