Fall 2008
CS 583 Analysis of Algorithms
Sections 001 and 002

Professor Pearl Y. Wang



Course Description:

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, formal methods and models, as well as calculus and discrete mathematics. Programming skills are also a prerequisite.

Class Web Site:

URL: http://cs.gmu.edu/~pwang/Fall08/cs583

The class website contains links to this syllabus page, practice homework asssignments, timetable, and lecture notes pages.

Prerequisites:

CS 310 and CS 330
Calculus (MATH 113, 114, 213) and MATH 125
Ability to program in a high-level language that supports recursion (e.g. PL/I, Pascal, C, C++, Lisp, Java)


Instructor:

Prof. Pearl Y. Wang
Computer Science Department
Office:   Science & Tech 2, Room 430B
Tel:       703-993-1527
E-mail:    pwang at cs dot gmu dot edu
Office Hours:   Thurs 6 pm - 7 pm;   other times available by appointment

Teaching Assistant:

Ms. Zhi Zhang
Email:     zzhang8 at gmu dot edu
Office Hours:   Tues 5 pm - 7 pm
Location:    Science & Tech 2, Room 330

Class Hours:

Sec 001: Thurs 7:20 pm - 10 pm;   Science & Tech I, Room 126
Sec 002: Thurs 7:20 pm - 10 pm;   NET

This course is delivered to the Internet section online by Network EducationWare (NEW). Students in all sections have accounts on NEW and can play back the lectures and download the NEW PDF slide files at http://disted.ite.gmu.edu.


Required Textbook:

Cormen, Leiserson, Rivest, & Stein, Introduction to Algorithms (Second Edition), McGraw Hill, 2001

Course Requirements & Grading:

The course grade is based on at least two 1.5 hour examinations and a comprehensive final examination. All required coursework 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. Students in the NET section are expected to come to GMU to take the exams on the dates/times stated in the detailed Timetable.
1.5-Hour Exams:   50 %
Final Exam:           50 %
All required coursework for this class is to be performed independently. Please read the information about GMU and CS Department Academic Integrity and Honor Code Policies at http://cs.gmu.edu/wiki/pmwiki.php/HonorCode/HomePage.

These policies will be strictly enforced.

If you have a documented learning disability or other condition that may affect academic performance you should: 1) make sure this documentation is on file with the Office of Disability Services (SUB I, Rm. 222; 993-2474; http://www.gmu.edu/student/drc) to determine the accommodations you need; and 2) talk with me to discuss your accommodation needs.


Important Dates:

Last day to add:  September 9, 2008
Last day to drop: September 9, 2008 (no tuition penalty)
Last day to drop: September 26, 2008

Columbus Day recess: October 13, 2008
Thanksgiving recess: November 26 - 30, 2008
Last day of classes: December 6, 2008

Final Examination: December 11, 2008, 7:30 pm - 10:15 pm


Tentative List of Topics:

Topic Chapter(s)
Introduction 1-2
Growth of Functions 3
Recurrences 4
Randomized Algorithms 5
Sorting and Order Statistics 6 - 9
Red-Black Trees 13
Dynamic Programming 15
Greedy Algorithms 16
Graph Algorithms (21) 22 - 26
NP-Completeness 34 - 35

You are expected to be familiar with the material in Chapters 10 - 12.

See the detailed Class Website for more information.


Created: 17 Aug 2008
Updated: 27 Aug 2008
P.Y. Wang