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.
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:
|02||Tuesdays||Shillman Hall 135||6:00 pm - 9:00 pm|
|03||Wednesdays||Shillman Hall 220|
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:
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.