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 4304
Tel:       703-993-1527
E-mail:    pwang at cs.gmu.edu
Office Hours:   Wed 6 pm - 7 pm;   other times available by appointment

Teaching Assistant:

Ms. Katherine (Raven) Russell
Email:   krusselc at gmu.edu
Office Hours:  Mon 5 - 7 pm;   Tue/Thurs 3:15 - 4:15 pm
Location:  Nguyen Engineering - ENGR 4456

Class Hours:

Sec 002: Wed 7:20 pm - 10 pm;   ENGR 2608
Sec DL1: Wed 7:20 pm - 10 pm;   NET

This course is delivered to the Internet section online using a 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 download material and participate in discussions on the Moodle course page. However, only students in online sections will be able to connect to class sessions and to download recordings of the lectures. 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 4, 2012
Last day to drop: September 4, 2012 (no tuition penalty)
Final day to drop: September 28, 2012

Columbus Day recess: October 8, 2012
Thanksgiving recess: November 21 - 25, 2012
Last day of classes: December 8, 2012

Final Examination: December 12, 2012, 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: 21 Aug 2012
P.Y. Wang