**George Mason University **

**DEPARTMENT OF COMPUTER SCIENCE**

**CS630 - Advanced Algorithms - Fall 2012**

T 4:30-7:10, Krug Hall 7

Prerequisites | Description | Readings | Syllabus | Grading | Late | Dates

TA and Instructions for Mailing List

This page last updated on 8/21/12.

703-993-1545

richards@cs.gmu.edu (email should have "CS630" in the subject line

Course office hours: TR, 11:00--12:00 or by appt.

Engineering Bldg 5320

*PREREQUISITES :*

CS583 (and therefore CS310, CS 330 and discrete mathematics).

*DESCRIPTION :*

Provides an overview of advanced algorithm design and analysis techniques. Topics include algorithms for hash tables, matrix operations, number theory, string matching, computational geometry, combinatorial optimization, and linear programming; also the areas of NP-completeness and approximation algorithms.

This course covers those topics in the text not usually discussed in CS583, plus a few other topics.

*READINGS: *

- Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, 2009, third edition.

*SYLLABUS:*

The material will be drawn from.

- Introductory material - Various problems from the review chapters
- Data structures - chapters 11, 18, 20 and splay trees.
- Design and analysis techniques - chapter 16 (starred sections)
- Graph algorithms - chapter 26.
- Selected topics - chapters 27, 28, 29, 30, 31, 32, 33, 35

There are more chapters listed here than we will have time to cover.

*GRADING : *

Exams -- 100

The two exams, the midterm and the final, each cover about a half of the semester; i.e., the final is not cumulative.

Of these exams the highest score will count 60% and the lowest 40%.

Late work and missed exams will not be allowed without an official university excuse.

The midterm date will be announced; it is tentatively scheduled for Oct 16.

The final is scheduled for Dec 11.

**NO LAPTOPS**, etc. (If you NEED a laptop for note-taking then speak to me.)