COM 1390 Algorithms

Course Format
Course Coordinator
Textbooks and References

Prerequisites by Topic
Major Topics Covered in Course
Laboratory Projects

Course Description

Introduces the basic principles and techniques for the discovery, design, analysis, and implementation of efficient algorithms.  Sample algorithms will be drawn from sorting and searching, graph algorithms, string matching algorithms, greedy algorithms, and dynamic programming.  Analysis will use both theoretical and experimental techniques.  The course will conclude with a discussion of "hard problems" for which no efficient algorithms are known and will introduce the concept of NP-complete problems.

4 QH credit
Prerequisite: COM 1350.

Course Information

Course is offered during the Winter and Summer quarters. CS majors are guaranteed a place in class.
 

Winter 2000

Summer 2001

Course Format

BSCS03 required course
BSCS04 Algo & Data core
BACS required core
BSIS general elective

This is a required course for BS CS majors graduating in the year 2003 and before, is an Algorithms & Data core course for BS CS majors graduating in the years 2004 and beyond and a required course for BA CS majors.

Course Coordinators

Professor Rajmohan Rajaraman
raj@ccs.neu.edu

Textbooks and References

Summer 2000

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

References
 

• Sara Baase and Allen Van Gelder.  "Computer Algorithms: Introduction to Design and Analysis", Addison-Wesley, 2000.
• Steven Skiena, "The Algorithm Design Manual", Springer-Verlag, 1998.
• Gregory J. E. Rawlins, "Compared to what?: An Introduction to the Analysis of Algorithms", Computer Science Press/W. H. Freeman, 1998.

Course Goals

A major objective of this course is to provide solid theoretical foundations and technical knowledge that form the basis of effective problem-solving in all areas of computer science.  Techniques for abstraction, design and analysis, and notions of complexity of problems are covered, which enables the students to formally analyze problems and attack them.  It is expected that the systematic coverage of algorithmic techniques in the course will vastly enhance the problem-solving skills of the students.

Prerequisites by Topic

Discrete mathematics (sets, functions, elementary combinatorics)

Elementary data structures (arrays, linked lists, trees, hashing, priority queues)

Encapsulation and abstraction

Programming

Recursion and induction

Models of computation

Major Topics Covered in the Course

Advanced algorithms, the related data structures, and their analysis:
 

Divide and conquer type of algorithms

Maintenance of dynamic sets

Greedy algorithms

Dynamic Programming

Graph traversals

Data Structures

Laboratory projects

The homework consists primarily of assignments requiring written solutions to assigned mathematical problems.  They test problem-solving skills.  A total of 5 homeworks are typically handed out over a period of 10 weeks.  In addition, 1 or 2 programming assignments that span over 2-3 weeks are handed out.