CSU 690: Algorithms & Data

Fall 2006

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: 104 West Village Bldg G, TuF 3:25 PM-5:05 PM

Office Hours: Tu 12:30-1:30 PM, Th 4:30-5:30 PM

Teaching Assistant: Abhishek Chaubey (chaubey AT ccs), WVH 266
Office hours: M 4:45-5:45 PM, F 10:45-11:45 AM

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
Algorithm design paradigms: divide-and-conquer, greedy, dynamic programming, randomization.
Graph algorithms: traversals, shortest paths, spanning trees, network flows.
Information theory, fundamental structures for representing data, 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 have not taken any of the prerequisite courses (or their equivalents), then you should not take CSU690.

Textbook

J. Kleinberg and É. Tardos, Algorithm Design, Addison-Wesley, 2006.

Grading

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