CS 583
Analysis of Algorithms

Time/Location: Thursday 4:30-7:10,   The Engineering Building 4457
Instructor: Dr. Jana Kosecka
Office: 4444, Research II
email: kosecka@cs.gmu.edu
Course website http://cs.gmu.edu/~kosecka/cs583/
Teaching Assitant: tba
Office Hours: tba

Course Scope: In this course, a thorough examination of several well-known techniques that are used for the design and analysis of algorithms will be covered. Topics to be covered include theoretical measures of algorithm complexity, sorting and selection algorithms, greedy algorithms, divide and conquer techniques, dynamic programming, graph algorithms, search strategies, and an introduction to the theory of NP-completeness. Additional topics may be covered if time permits. Students are expected to have taken prior undergraduate courses in data structures and algorithms, as well as calculus and discrete mathematics. Programming skills are also a prerequisite.

CS 310 and CS 330 Calculus (MATH 113, 114, 213) and MATH 125 Familiarity with a high-level programming language

Schedule, Homeworks, Handouts

Required Textbook:
Cormen, Leiserson & Rivest, Introduction to Algorithms, McGraw Hill, 1990

Recommended Textbook:
S. Dasgupta, C.H.Papadimitriou and U.V. Vazirani: Algorithms

Course Requirements:
There will be a midterm examination, several practice homework assignments, one programming projects and a comprehensive final examination. All required assignments must be completed by the stated due date and time. Late coursework will not be accepted and make-up tests will not be given for missed examinations. Please note that all coursework is to be done independently- see the GMU Honor Code System and Policies at http://www.gmu.edu/catalog/acadpol.html .

Homeworks 30%
Midterm 35%
Final 35%

Tentative List of Topics:
Topic  Chapter(s) 
Growth of Functions  2
Summations and Recurrences  3,4
Counting and Probability  6
Sorting and Order Statistics  7 - 10
Red-Black Trees  14
Dynamic Programming  16
Greedy Algorithms  17
Graph Algorithms  23 - 26
NP-Completeness and Approximation Algorithms  36 - 37

Please Note: You are expected to be familiar with the material in Chapters 1, 11 - 13, 19.