Spring 2015: Analysis of Algorithms [CS 483]

Professor: Carlotta Domeniconi, Rm 4424 ENG, carlotta\AT\cs.gmu.edu Office hours: MW 3:00pm - 4:00pm
Teaching Assistant: TBA
Prerequisites: CS 310, CS 330, and Math 125
Location and Time: We meet in the Art and Design Building 2026, MW 1:30pm - 2:45pm
Textbook: Jon Kleinberg and Eva Tardos, Algorithm Design, Addison Wesley, 2006
Course Web Page

General Description and Preliminary List of Topics

The design and analysis of algorithms is at the core of computer science. This course covers the principles of algorithm design and the analysis of the performance of algorithms. The emphasis is on designing correct and efficient algorithms when solving a given problem. Examples will be drawn from a variety of application scenarios.

Topics include: Measures of algorithm complexity; Graph algorithms, Greedy algorithms; Divide and conquer techniques; Dynamic programming; Network algorithms; Theory of NP-completeness.

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
An ability to design and analyze new algorithms to solve a computational problem
An ability to reason algorithmically

Grading

Quizzes: 20%
Assignments: 20%
Midterm: 30%
Final: 30%

Quizzes and exams are closed book. The lowest quiz grade will be dropped. Assignments must be performed individually. Group work is NOT allowed. Any deviation from this policy will be considered a violation of the GMU Honor Code and will not be tolerated. The CS Department has specific CS Honor Code Policies. Please, no laptops in class!

Disabilities

If a disability or other condition affects your academic performance, make sure it's documented with the Office of Disability Services.