CS 483 Syllabus

CS 483
Analysis of Algorithms
Summer 2010

Dr. David Nordstrom
office: 5345 Nguyen Engineering Bldg.
office hours: Monday and Wednesday 3:15 - 4:15
email: dnordstr_AT_gmu.edu
phone: (703) 993-1565
The course website is http://cs.gmu.edu/~dnord/cs483.

Textbook

The textbook for the course is Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, third edition, MIT Press, 2009.

The course

The prerequisite for this course is C or better in CS 310, CS 330, and Math 125. We will study fundamental data structures and algorithms with an emphasis on establishing correctness and analysis of running-time properties of the algorithms. Students should be comfortable doing mathematical proofs.

Topics

Topics to be covered include:

Complexity analysis and "Big O"
Analysis of sorting and searching algorithms
Graph algorithms
Dynamic programming
Branch and bound methods
P and NP, NP-completeness

Course Outcomes

An understanding of classical problems in Computer Science
An understanding of classical algorithm design and analysis strategies
An ability to analyze the computability of a problem
Be able to design and analyze new algorithms to solve a computational problem
An ability to reason algorithmically

Grading

There will be regular homework assignments, a midterm, and a final exam. There will be no late homeworks accepted and there will be no make-ups on the exams except for truely exceptional (as judged by me) reason. Grades will be computed from a weighted average using the weights: