COM 1390: Algorithms

Winter 2001

Instructor:  Rajmohan Rajaraman

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

Class meeting times/location:     173 DG, MTTh 1:35

Office Hours:    Tuesday 3:00-4:00,  Thursday 5:30-6:30

Course Description

Textbook

Grading

Handouts (in postscript)

           Course Information                         Problem Set 1                             Sample Solution to PS1
          Tentative Course Schedule            Problem Set 2                             Sample Solution to PS2
          Questionnaire                                Problem Set 3                              Sample Solution to PS3
          Books for Reference                      Midterm practice problems         Sample Solution to PS4
          Review of math formulae              Problem Set 4                             Sample Solution to PS5
          Honors adjunct                              Problem Set 5
                                                                Sample Final
                                                                Solution to Sample Final

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

    Sara Baase and Allen Van Gelder,  Computer Algorithms: Introduction to Design and Analysis, Addison-Wesley, Third Edition 2000.

    Grading

    The course grade will be based on five problem sets (for a total of 40%), a midterm (20%), and a final exam (40%).  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.