Henry S. Baird Spring
CRNs: 16763 (CSE); 17775 (Math)
Note to all students: this is a graduate-level 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.
CS Ph.D. graduate students: all first-year CS Ph.D. students are
required to take this course.
to CS M.S. graduate students: this
course fulfills both the "Theory" and "Applied Theory" skill areas.
are methods for
information processing problems which are fully automatable
and provably correct. We also need to understand
runtime and memory demands, especially on large inputs. Fast
algorithms for hard, practically important
problems are among the key discoveries
computer-science research. This course presents algorithms
searching, sorting, manipulating graphs and trees,
scheduling tasks, finding shortest paths, matching patterns in
strings, cryptography, etc---and gives proofs of their correctness and
their time and space complexity. General strategies for
greediness, dynamic programming---are stressed. Limits on algorithm
explored through NP-completeness theory. Quantum
computing is briefly introduced.
- Algorithms with numbers.
- Divide-and-conquer algorithms: the Fast Fourier
- 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.
Course Objective: On completing this course, students will be able to design algorithms
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
solve a wide range of problems. They will understand how to judge
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,
application of algorithms.
Henry Baird, Prof., CSE Dept,
firstname.lastname@example.org. Office: Packard Lab 380.
Office Hours: Wednesdays 12:10-1:00 PM, or by appointment. He will grade all exams and final project reports.
Grader (for homeworks only):
To ask questions about homework problems or grades, contact her by email; if you wish, she will arrange to meet you in person.
Combinatorial Optimization: Algorithms and Complexity
Lectures Time and Place: Tues/Thurs, 2:35 - 3:50 PM, Packard Laboratory room 258.
is one hour exam (in-class midterm on Thursday March 13th) and, by default, one final 3-hour
these are written open-book exams. Instead of taking a final exam, students have these
alternative options: (a) carry out a
challenging algorithm design project; or (b) write an
a thorough critique of the
literature about an algorithm or problem).
Grading: 25% homework, 25% hour exam, 50% final exam/final
CSE-441-Math-441-SP14 Advanced Algorithms. We will use the University's online facility CourseSite to distribute assigned readings, lecture
notes, homeworks, grades, etc. Once you enroll in the course, browse coursesite.lehigh.edu,
your Univ. email id and Portal password, and you should be admitted
to this site. If you can't login, email the instructor
Textbook (required): S. Dasgupta,
C. Papadimitriou, and U. Vazirani, Algorithms, McGraw-Hill, 2008, 336 pages,
softcover. (ISBN-13 9780073523408; ISBN-10 0073523402) [publisher's
page]. If there are no copies available in the Univ. bookstore, email me immediately. A desk copy may be consulted in
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).
text (not required):
C. H. Papadimitriou &
K. Steiglitz, Prentice-Hall (Englewood Cliffs, NJ), 1982 (ISBN-10
No prior knowledge of algorithms is assumed.
- Familiarity with mathematical proof
induction, proof by contradiction, proof by case analysis, etc---is strongly assumed.
- Linear Algebra---or familiarity
with elementary 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
If you have any
questions, ask the instructor: Henry Baird, email@example.com.
Accommodations for Students
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
the Academic Support Services office before accommodations can be
Lehigh University endorses The Principles of Our Equitable Community (http://www4.lehigh.edu/diversity/principles
). We expect each member of this class to acknowledge and practice these Principles. Respect for each other and for differing viewpoints is a vital component of the learning environment inside and outside the classroom.