Henry S. Baird Spring 2015 Course
Advanced Algorithms
CSE/Math 441
3 credits
CRNs: 16763 (CSE); 17775 (Math)
Note to all students: this is a graduatelevel version of
the undergraduate Algorithms course CSE/Math
340, which covers fewer topics, moves more slowly, and expects fewer Math skills; 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):
 Algorithms with numbers.
 Divideandconquer algorithms: the Fast Fourier
Transform.
 Decompositions of graphs; paths in graphs.
 Greedy algorithms
& matroid theory.
 Dynamic programming.
 Computational geometry: closestpoint,
lineintersection, Voronoi diagrams, multidimensional search.
 Linear programming, Maxflow, Mincost flow, Simplex
algorithm, Kachian's algorithm, and primaldual algorithms.
 NPcomplete problems.
 Coping with NPcompleteness; approximation algorithms.
 Randomized and amortized algorithms.
 Quantum algorithms.
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. He will grade all exams and final project reports.
Grader (for homeworks only):
To ask him questions about homework problems or grades, contact him by email; if you wish, he will arrange to meet you in person. He is also available to explain ideas to you.
Lectures Time and Place: Tues/Thurs, 2:35  3:50 PM, Packard Laboratory classroom 258.
Exams: There
is one "Midterm" exam (inclass), probably on Thursday March 26; and, by default, one final 3hour
exam:
these are written openbook exams. Instead of taking a final exam, students may choose among 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
published literature on some algorithm or problem).
Grading: 25% homework, 25% hour exam, 50% final exam/final
project/final report).
Course Site:
CSE441Math441SP15 Advanced Algorithms. We will use the University's online facility CourseSite to distribute assigned readings, lecture
notes, homeworks, grades, etc. Once you have enrolled 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,
in a paperback edition only. (ISBN13 9780073523408; ISBN10 0073523402). If there are no copies for sale in the Univ. bookstore, consider other sources:
 Amazon.com: (a) Paperback new, $45 (as fast as twoday delivery); (b) Paperback used, $33 and up (27 day delivery); (c) Kindle edition, $43 (autodelivered wirelessly).
 Buy or borrow from a former CSE/Math 441 student: ask the instructor for a list of students to ask.
A "desk copy" of this textbook 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 (PL 380) when he's
there (but, again, the copy can't be taken away).
Supplementary
text (not required):
Combinatorial Optimization: Algorithms and Complexity,
C. H. Papadimitriou &
K. Steiglitz, PrenticeHall (Englewood Cliffs, NJ), 1982 (ISBN10
0131524623).
Prerequisites:

No prior knowledge of algorithms is assumed.
 Familiarity with mathematical proof
techniquese.g.
proofs by
induction, by contradiction, by case analysis, etcis strongly assumed.
 Linear Algebraor familiarity
with elementary linear algebra & matrices (e.g. LU Math 205).
 Basic Applied Probabilityor familiarity
with elementary discrete probability theory (e.g. LU Math 231 or
Math 309 or CSC
450).
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.
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.