CSU 690: Algorithms & Data

Spring 2005

240 WVH                                                                              Work: 617-373-2075
College of Computer Science                                                Email: rraj AT ccs DOT neu DOT edu
Northeastern University                                                         Fax:    617-373-5121

Class meeting times/location: 108 WVH,MW 2:50-4:30

Office Hours: M 4:30-5:30 PM, Th 4:15-5:15 PM

Teaching Assistant: Xin Liu (liux AT ccs), WVH 208, 617-373-5878
Office hours: 11:00am~1:00pm

Course Description

Prerequisites

Textbook

Grading

Course calendar (will include all handouts)

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: recurrences, asymptotic notation, asymptotic analysis and formal methods for establishing the correctness of algorithms
Sorting and searching algorithms.
Algorithm design paradigms: divide-and-conquer and dynamic programming.
Graph algorithms: depth-first search, breadth-first search, and shortest paths.
Information theory and fundamental structures for representing data.
Hierarchical representations, dynamic data representations, and data compression.
An introduction to the theory of NP-completeness.

Prerequisites

The following courses are prerequisites: CSU200, CSU213, MTHU481. By topic, the prerequisites are:

Discrete mathematics (sets, functions, elementary combinatorics)
Elementary data structures (arrays, linked lists, trees, hashing, priority queues)
Encapsulation and abstraction
Programming
Recursion and induction
Elementary probability theory

A brief review of discrete mathematics, induction, and elementary probability theory will be done at the beginning of the course. This review, however, does not take the place of the prerequisites. The prerequisites will be strictly enforced. If you do have not taken any of the prerequisite courses (or their equivalents), then you should not take CSU690.

Textbook

T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, MIT Press & McGraw-Hill, Second Edition 2001.

Grading

The course grade will be based on seven problem sets (for a total of 35%), a midterm (20%), a final exam (40%), and class participation (5%). Problem sets are due at the beginning of class. No late homework will be accepted!