Henry S. Baird    Spring 2011 Course


Advanced Algorithms
 
CSE/Math 441    (CRN 16763)


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 computer-science research.  This course presents algorithms for searching, sorting, manipulating graphs and trees, scheduling tasks, finding shortest paths, matching patterns in strings, etc---and gives proofs of their correctness and analysis of their time and space complexity. General strategies for designing algorithms---e.g. recursion, divide-and-conquer, greediness, dynamic programming---are stressed. Limits on algorithm efficiency are explored through elementary NP-completeness theory.   Quantum computing is briefly introduced.

(Note:  this is a graduate-level version of the undergraduate course CSE/Math 340, which covers fewer topics and is generally easier; no student may take both of these two courses for credit.)

(All first-year CS Ph.D. students are required to take this course, starting this year.  Other CS or CompE M.S. & Ph.D. students may count this as a Theory course for purposes of breadth requirements.)


Syllabus (tentative):

• Algorithms with numbers.
• Divide-and-conquer algorithms.
• Decompositions of graphs; paths in graphs.
• Greedy algorithms & matroid theory.
• Dynamic programming.
• Computational geometry:  closest-point, line-intersection, Voronoi diagrams, multidimensional search.
• Linear programming, Max-flow, Min-cost flow, Simplex algorithm, Kachian's algorithm, and primal-dual algorithms.
• NP-complete problems.
• Coping with NP-completeness; approximation algorithms.
• Randomized and amortized algorithms.
• Quantum algorithms.

Instructor:  Henry Baird, Prof., CSE Dept, hsb2@lehigh.edu. Office:  Packard Lab 514C.   Office Hours: Wednesdays 12:10-1:00 PM, or by appointment.

Classroom lectures:  Tuesdays/Thuursdays 1:10 - 2:25 PM, in Neville 3 (NV003).

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 and---to the extent possible---efficient 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.

Exams: There is one hour exam (midterm) and a final 3-hour exam:  all are closed-book, in-class, written exams.   Instead of taking a final exam, students also have these options: (a) a challenging algorithm design project; or (b) an extended written 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).

BlackBoard site:  Advanced Algorithms (SP11), CSE-441-010-SP11. 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): S. Dasgupta, C. Papadimitriou, and U. Vazirani, Algorithms, McGraw-Hill, 2006, 336 pages. (ISBN13 9780073523408; ISBN10 0073523402) [publisher's page].

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

No prior knowkedge of algorithms is assumed.

Familiarity with mathematical proof techniques---e.g. proof by induction, proof by contradiction, proof by case analysis, etc---will be assumed.

Linear Algebra etc -- or basic familiarity with linear algebra & matrices (e.g. LU Math 205).

Basic Applied Probability -- or familiarity with elementary discrete probability theory (e.g. LU Math 231 or Math 309 or CSC 450).


If you have any questions about prerequisites, ask the instructor: 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 (610-758-4152) as early as possible in the semester.  You must have documentation from the Academic Support Services office before accommodations can be granted.