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 studied 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.

Prerequisites:

CS 310 (Data Structures) and CS 330 (Formal Methods & Models)
Calculus (MATH 113, 114, 213) and MATH 125 (Discrete Mathematics)
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:  Nguyen Engineering - ENGR 5322
Tel:       703-993-1527
E-mail:    pwang at cs.gmu.edu
Office Hours:   Thurs 6 pm - 7 pm;   other times available by appointment

Teaching Assistant:

Ms. Yanyan Lu
Email:    ylu4 at gmu.edu
Office Hours:  Wed 5 - 7 pm
Location:     ENGR 4456

Class Hours:

Sec 002: Thurs 7:20 pm - 10 pm;   ENGR 4457
Sec 003: Thurs 7:20 pm - 10 pm;   NET

This course is delivered to the Internet section online using Moodle learning management system with MIST/C, which has replaced the Network EducationWare (NEW) delivery system. Students in all sections will have accounts and will be able to play recordings of the lectures and download the slide files from the Moodle course page. Login information will be sent to all enrolled students by email, before the first scheduled class.

---

Required Textbook:

Cormen, Leiserson, Rivest, & Stein, Introduction to Algorithms (Third Edition), The MIT Press, 2009 Please note this is the latest edition of the textbook. If you are using an earlier edition, the content and problem numbers may not agree with those used in the class lectures and materials.

---

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. 4205; 993-2474; http://ods.gmu.edu/) to determine the accommodations you need; and 2) talk with me to discuss your accommodation needs.

---

Important Dates:

Last day to add:  September 14, 2010
Last day to drop: September 14, 2010 (no tuition penalty)
Last day to drop: September 21, 2010

Columbus Day recess: October 11, 2010
Thanksgiving recess: November 24 - 28, 2010
Last day of classes: December 11, 2010

Final Examination: December 16, 2010, 7:30 pm - 10:15 pm

---

Tentative List of Topics:

Please see the Timetable for the final list of topics.

You are expected to be familiar with the material in Chapters 10 - 12 and Appendix VIII that is taught in prerequisite courses.

Topic	Chapter(s)
Introduction	1-2
Growth of Functions	3
Divide-and-Conquer	4
Probabilistic Analysis and Randomized Algorithms	5
Sorting and Order Statistics	6 - 9
Red-Black Trees	13
Dynamic Programming	15
Greedy Algorithms	16
Amortized Analysis	17
Fibonacci Heaps & Disjoint Sets	19, 21
Graph Algorithms	22 - 25
Multi-threaded Algorithms (if time permits)	27
NP-Completeness	34 - 35

---

Created: 18 Aug 2010
P.Y. Wang