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/.
The course will meet at the following times and locations:
|01||Wednesdays||Shillman Hall 320||6:00 pm - 9:00 pm|
|03||Thursdays||Shillman Hall 420|
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:
Reading assignments are from the textbook except for a small amount of supplementary material:
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.