CS5800 Algorithms Spring 2014

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/.

The course will meet at the following times and locations:
SectionDaysRoomTime
01WednesdaysShillman Hall 3206:00 pm - 9:00 pm
03ThursdaysShillman Hall 420


Schedule

Assignments


The Final Exam will be held during the regular class period on 23 or 24 April 2014. The final exam is an open book/open notes exam. Sections 01 and 03 are identical so it does not matter which class you attend. However, the final 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 Final Exam counts for 60% of the course grade, and the homework assignments count 40%. There are 10 homework assignments that each count for 4% of the course grade. Each homework assignment has 100 points. Submit your homework assignments to Blackboard.

The course grade will be reduced for the following:

  1. Unexcused class absences
  2. Arriving late to a class or leaving during a class (when unexcused)
  3. Submitting an assignment late (1 point out of 100 for each hour)
  4. Submitting the Final Exam late (1 point out of 60 for each minute)

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.


General Information

My advising and office hours are on Wednesdays and Thursdays from 4:00 PM to 5: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/spring2014/cs580001/home. There will be course TAs. Their contact information will be posted later.


Ken Baclawski
342 WVH
College of Computer Science
Northeastern University
360 Huntington Avenue
Boston, MA 02115
kenb@ccs.neu.edu
(617) 373-4631 / Fax: (617) 373-5121