COM 1390: Algorithms

Winter 1998

113 Cullinane Hall                                                                      Work: 617-373-2075
College of Computer Science                                                 Email: rraj@ccs.neu.edu
Northeastern University                                                           Home: 617-864-1596
Boston, MA 02115                                                                      Fax:    617-373-5121

Class meeting times/location: MTTh 1:35

Office Hours: Monday 3:00-4:00, Thursday 5:00-6:00, or by appointment

Course Description

Textbook

Grading

Handouts

           Course information                  Problem Set 1           Sample Solution: Problem Set 1        Programming Assignment 1
          Tentative schedule                  Problem Set 2           Sample Solution: Problem Set 2        Clarification on Prog. Ass. 1
          Books for reference                 Problem Set 3           Sample Solution: Problem Set 3
          Questionnaire                          Practice Problems    Quick Solution to Practice Problems
          Revised tentative schedule      Problem Set 4           Sample Solution to Midterm
                                                          Problem Set 5           Report on Programming Assignment 1
                                                                                                                          Sample Solution: Problem Set 4
                                                                                                                          Sample Solution: Problem Set 5

Course Description

This course provides a undergraduate-level introduction to the design, analysis, and implementation of algorithms. Topics covered will include the following.

Mathematical foundations: summations, recurrences, asymptotic notation, and elementary probability theory.

Data structures: hash tables, binary search trees, heaps.

Sorting and searching algorithms.

Algorithm design paradigms: divide-and-conquer and dynamic programming.

Graph algorithms: depth-first search, breadth-first search, and shortest paths.

An introduction to the theory of NP-completeness.

Textbook

T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms, MIT Press/McGraw-Hill, 1990.

Grading

The course grade will be based on five problem sets (for a total of 50%), a midterm (20%), and a final exam (30%). Problem sets are due at the beginning of class. As a general rule, any problem set turned in up to 1 week late will be penalized 20%, and no homework will be accepted beyond 1 week past its due date.