CS5800 Algorithms Spring 2013

Presents the mathematical techniques used for the design and analysis of computer algorithms. Focuses on algorithmic design paradigms and techniques for analyzing the correctness, time and space complexity of algorithms. Topics will include: asymptotic notation, recurrences, loop invariants, sorting and searching, lower bounds, hashing, greedy algorithms, dynamic programming, graph algorithms, linear programming, Monte Carlo methods, and NP-completeness.

Prerequisites:

1. Experience in some high level procedural language, especially C or Java.
2. Data Structure
3. Assembly Language and Computer Architecture
4. One year of College Calculus
5. Discrete Mathematics

Of the prerequisites, Data Structure and Calculus are the most important.

The textbook for this course will be:
Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani
This book is available online at http://www.cs.berkeley.edu/~vazirani/algorithms.html.

The course will meet at the following times and locations:

Section	Days	Room	Time
02	Tuesdays	Shillman Hall 135	6:00 pm - 9:00 pm
03	Wednesdays	Shillman Hall 220

Schedule

Assignments

The Mid-Term Exam will be held during the first half of the regular class period on 19 or 20 February 2013, depending on your section. The Final Exam will be held during the regular class period on 23 or 24 April 2013. Both exams are open book/open notes. Sections 02 and 03 are identical so it does not matter which class you attend. However, the exams will differ, so you must come to the one for your section. The exams have assigned seating, and your name will be on the exam. If you come to the wrong exam, you will not be able to take it at all.

The Mid-Term Exam counts for 20% of the course grade, and the Final Exam counts for 30% of the course grade. There are 10 homework assignments, and each homework grade counts for the 5% of the course grade. Assignments that are turned in late will lose 10% for each day or fraction of a day that the submission is late. Note that this is 10% of the maximum grade not 10% of your actual grade.

Reading assignments are from the textbook except for a small amount of supplementary material:

1. The textbook mentions probability theory and randomized algorithms (also called Monte Carlo algorithms) occasionally but never mentions Monte Carlo methods which are some of most important algorithms that make use of probabilistic methods.
2. The satisfiability (SAT) problem was the first problem that was shown to be NP-complete. Indeed, this was where the notion of NP-completeness arose in the first place. A special case of SAT is mentioned briefly in the textbook, but SAT is not covered. SAT has been researched intensively and is probably the most studied algorithmic problem ever, including by faculty in the College.
3. The last supplement is concerned with explaining why algorithms for NP-complete and undecidable problems work so well in spite of the fact that the problems these algorithms solve are theoretically so complex. Chapter 9 of the textbook discusses some ways of coping with NP-completeness, but it does not consider undecidable problems, and it gives no insight into the observed phenomena. A handout will fill in this gap in the textbook.

My advising and office hours are on Tuesdays and Wednesdays at 3:00 PM. I will make material available in my WWW home page which will contain my current schedule (including my office hours). The course website is http://www.ccs.neu.edu/home/kenb/cs5800. The Piazza site for the course is https://piazza.com/northeastern/spring2013/cs58002/home. There will be course TAs. Their contact information will be posted later.