Advanced Algorithms, CS 441/541, Fall 2015

Final Exams Grades and Final Course Grades are now posted
Grade cut-offs were the following percentages:
A  > 90
A- > 80
B+ > 75
B  > 70
B- > 65

I reserve A+ grades for performance that is truly exceptional.

Because of the 441/541 structuring of this course, and the fact that I
had the "541/bonus" problems have a relatively large value, there were
an extraordinary number of possible bonus points for 441 students.

In this course I gave 2 A+'s.  Both were undergraduate students who
had more than 110% of the possible points.  I gave no A+'s to 541
students because:

(a) Either you are a PhD student and an A+ signifies that you are 
spending too much time on your coursework, or

(b) You are an MS student in a professional degree program and
meaningless decorations on a A grade shouldn't matter, and in any case

(c) You got smoked by two undergraduates who got more raw points than
you did.

Some end of class thoughts:

At the end of the semester I sometimes allow myself to wax
philosophical and put the course in context.  First, I hope that you liked
this algorithms course.  Algorithms, especially proving them correct
under worst case performance, are the core of modern computer science.
Aside from being sad that our lectures are over, perhaps you are
interested in further courses in this direction.  Some options are:

CSE 581T: Approximation Algorithms, and 
CSE 582T: Complexity Theory

These start at the discussion of NP-Complete problems, and go in
different directions.  581 - studies more completely the ways to
approximate algorithms, what it means to give probabilistic algorithms
for approximations (e.g. it could be that probably your answer is
close to optimal, or probably you finish your algorithm in poly-time),
and more formal structure approaches to finding approximation

582 - explores the complexity heirarchy, beyond P vs. NP, to the
category Co-NP that we mentioned, to the category EXP (what can be solved
in exponential time?  or, more interestingly, what are problems so
hard that they can't be solved in exponential time?).  This course
tends to be quite abstract in order to make strong claims about
computational complexity classes.

Algorithms courses with an applications focus include:

CSE 587 Algorithms for Computational Biology
CSE 584 Algorithms for Biosequence Comparison
CSE 554 Geometric Computing for Biomedicine
CSE 546 Computational Geometry

Which all have the same "provable algorithm performance" outlook, but
focus on algorithms with a particular application domain.  Finally, 

CSE 543 Algorithms for Nonlinear Optimization, 

is an outstanding course that starts with problems that can be
expressed as Linear Programs and explores many variations, including
integer programs, or programs that have quadratic or multi-linear
constraints (where you have unknowns multiplied by each other in your

Finally, I think this may be one of the last times we offer 441/541.
There is a new undergraduate theory course coming on line, CSE 347T
which I think will largely take the place of 441.  I hope this will
allow 541 to become a more true graduate algorithms course, one that
can assume that students have seen NP-completeness, and dynamic
programming, and can push in more modern directions - what does it
mean to think about complexity in the context of big-data where you
can only ever possibly have time/space to look at each data item once.
These concepts of streaming complexity, or a richer study of 
randomized algorithms are fascinating topics that we didn't get the chance to
explore in the course as we teach it now, but we might get to in the

I greatly enjoyed teaching this class this semester, and hope that you
enjoyed the class


Lecture Topics will approximately follow the online syllabus.

Course Textbook: Cormen, Leiserson, Rivest, and Stein (3rd Edition). You may also use the (cheaper, and easier to find used) 2nd Edition.

Additional Reading Sometimes one presentation in lecture and/or the presentation in our textbook is limiting. Here are alterative resources you can use to get another viewpoint on our class topics.

Instructor and TAs
Robert Pless (pless)
Alli Bukys (abukys)
Eileen Duffner (eduffner)
Patrick Chao (pengningchao)
Brian Choi (brian.choi)

all e-mails

This term we will be using Piazza for class discussion. The system is highly catered to getting you help fast and efficiently from classmates, the TA, and myself. Rather than emailing questions to the teaching staff, I encourage you to post your questions on Piazza. If you have any problems or feedback for the developers, email Find our class page at:

Grades will be calculated as 40\% homeworks and 60\% exams. There will be approximately 4 graded homeworks and 3 exams.

Office Hours:
Office Hours are visible on the Course Calendar.

Collaboration Policy:
This course will follow the traditional collaboration policy that the course followed in previous semesters, detailed here.