CS583 Analysis of Algorithms
Fall 2010
Information
Instructor: Amarda Shehu amarda\AT\cs.gmu.edu
Place and Time: Innovation Hall #206, M 7:20-10:00 pm
Office Hours: ENGR #4422, M 5:00-7:00 pm
TA: Yanyan Lu, ENGR #4456, ylu4\AT\gmu.edu, W 5:00-7:00 pm
Description
This course will offer students a set of techniques by which to design and analyze algorithms. The class will cover recurrence relations, probabilistic analysis, sorting algorithms, advanced data structures for searching and mapping, optimization algorithms and advanced analysis, and graph algorithms. The last few lectures of the class will be devoted to the topic of NP-completeness, approximation algorithms, and special topics in bioinformatics.
Format
Material will be disseminated in the form of lectures. Students will be tested on the comprehension of the basic material through homeworks and exams. In addition to the basic material, special topics will be covered. Extra credit in the homeworks and exams will allow students that are interested in advanced topics and research to demonstrate their abilities. Extra credit will not account for more than 10% of the total grade of a homework or exam. Some homeworks may include programming and reporting on the performance of algorithms implemented. No programming is involved in the exams, only pseudocode. No late homeworks will be accepted.
Prerequisites
CS 310 (Data Structures) and CS 330 (Formal Methods & Models).
Calculus (MATH 113, 114, 213) and MATH 125 (Discrete Math).
Programming in a high-level language that supports recursion (e.g. PL/I, Pascal, C, C++, Lisp, Java).
Reading
Required Reading: Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, The McGraw-Hill Companies, 2nd Edition (2001). Recommended Reading: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, The McGraw-Hill Companies (2008). The book is available at http://www.cs.berkeley.edu/~vazirani/algorithms.html.
Reading
The class material will combine online modules developed as part of the connexions project and the textbook: Introduction to Bioinformatics by Arthur M. Lesk, Oxford University Press, 3rd Edition.
Grade Breakdown
Homeworks: 40% (10% each)
Exam 1: 25%
Exam 2: 35%