Course Information (links to past and current course materials)

Course FormatCourse Goals

Course Coordinator

Textbooks and References

Prerequisites by Topic

Major Topics Covered in Course

Laboratory Projects

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 is offered during the Winter and Summer quarters. CS majors are guaranteed a place in class.

Winter 2000 Summer 2001

BSCS03 required course

BSCS04 Algo & Datacore

BACS required core

BSIS general electiveThis 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.

Professor Rajmohan Rajaraman

raj@ccs.neu.edu

Summer 2000

- T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms, MIT Press/McGraw-Hill, 1990.
- 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.

**References**

- 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.

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

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

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.