##
CS 483

Analysis of Algorithms

Summer 2014

**Dr. David Nordstrom**

**office:** 5345 Nguyen Engineering Bldg.

**office hours:** MTuWTh 10:30 - 11:25 am

**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 *Algorithm Design* by Jon Kleinberg and
É:va Tardos, Addison-Wesley, 2006.
### 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
- More topics as time allows and interest suggests

### 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:

- homework: 30%
- midterm: 35%
- final exam: 35%