|
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: Thurs 6 pm - 7 pm; other times available by appointment
Teaching Assistant:
Ms. Katherine (Raven) Russell
Email: krusselc at gmu.edu
Office Hours: T/Th 3-4 pm; Wed 5-7 pm
Location: ENGR 4456
Class Hours:
Sec 002: Thurs 7:20 pm - 10 pm; ENGR 4457
Sec DL1: 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 on Moodle and download the slide files from 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 6, 2011
Last day to drop: September 6, 2011 (no tuition penalty)
Last day to drop: September 30, 2011
Columbus Day recess: October 10, 2011
Thanksgiving recess: November 23 - 27, 2011
Last day of classes: December 10, 2011
Final Examination: December 15, 2011, 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 2011
P.Y. Wang
|