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.

Course Learning Outcomes:

By the end of the semester, students will:

- Understand classical problems in Computer Science
- Understand classical algorithm design and analysis strategies
- Be able to analyze the computability of a problem
- Be able to design and analyze new algorithms to solve a computational problem
- Be able to reason algorithmically

Prerequisites:

CS 310 (Data Structures) and CS 330 (Formal Methods & Models)
MATH 125 (Discrete Mathematics)

---

Instructor:

Prof. Pearl Y. Wang
Computer Science Department
Office:  Nguyen Engineering - ENGR 4440
Tel:       703-993-1527
E-mail:    pwang at cs.gmu.edu
Office Hours:   Wed 1 - 3:30 pm;

Teaching Assistants:

Xiaosheng Li (GTA)
Email:   xli22 at gmu.edu
Office Hours:  Thurs 4 - 6 pm; other times by arrangement
Location:  Nguyen Engineering - Rm. 5321

Kazi Kabir (GTA)
Email:   kkabir at gmu.edu
Office Hours:  Tues 1 - 3 pm; other times by arrangement
Location:  Nguyen Engineering - Rm. 4456

Kevin Andrews (UTA)
Email:   kandrew at gmu.edu
Office Hours: Mon 11 am - 1 pm; Fri 1 - 4 pm 
Location:  Nguyen Engineering - Rm 4456

Class Time & Location:

Sec 001: Wednesdays 4:30 pm - 7:10 pm;   Robinson Hall B108

---

Required Textbook:

Kleinberg and Tardos, Algorithms Design, Pearson Education, 2006
     (This book is available at the Mason Bookstore and Mason Library.)

---

Course Requirements & Grading:

The course grade is based on your performance on the weekly quizzes, midterms, and comprehensive final examinations. Make-ups will not be given for missed quizzes and examinations.

See the MyMason for all course information.

Quizzes	24%     (Each quiz is worth 3% of the final grade.)
Two Midterm Exams	36%     (February 27 & April 10)
Final Exam	40%     (May 9)

There are no required homework assignments for this section. Practice problems will be assigned and students are urged to complete them, but these will not be graded. All required quizzes and exams must be taken individually without assistance. Please read the information about GMU and CS Department Academic Integrity and Honor Code Policies at

http://cs.gmu.edu/resources/honor-code/.

These policies will be strictly enforced. Violations of Honor Code policies can result in a failing grade for the course.

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

---

Important Dates:

Last day to add:  January 29, 2019
Last day to drop: February 5, 2019 (no tuition penalty)
Final day to drop: February 12, 2019
Last day for Self-Withdrawal: February 25, 2019
Spring Break: March 13, 2018
Last day of Selective Withdrawal: March 25, 2019
Last day of classes: May 6, 2019

Final Examination: May 8, 2019, 4:30 pm - 7:15 pm

---

Tentative List of Topics:

You are expected to be familiar with the concepts taught in prerequisite courses.

Please see the Timetable for the more details.

Topic	Chapter(s)
Introduction	1
Basics of Algorithm Analysis	2
Graphs	3
Greedy Algorithms	4
Divide-and-Conquer	5
Dynamic Programming	6
Network Flows	7
NP-Completeness	8

---

Privacy:

Student privacy is governed by FERPA. Students must use their MasonLive email account to receive important University information, including communications related to this class. The instructor will not respond to messages sent from a non-Mason email address.

---

Created: 22 Jan 2019
Updated: 6 Feb 2019
P.Y. Wang