Spring 2018
CS 483 Analysis of Algorithms
Section 001

  Syllabus Page

  Lecture Timetable

  Lectures (MyMason)

  Homework (MyMason)

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, randomized algorithms, 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 4300
Tel:       703-993-1530
E-mail:    pwang at cs.gmu.edu
CS 483 Office Hours:   Send me email
General Office Hours:   Tues 1 - 4 pm; Wed 1 - 3 pm by appointment (Email csug at gmu.edu)

Teaching Assistants:

Xiaosheng Li
Email:   xli22 at gmu.edu
Office Hours:  Fri 4 - 6 pm; other times by arrangement
Location:  Nguyen Engineering - Rm. 4456

Kunling Zeng
Email:   kzeng3 at gmu.edu
Office Hours:  Wed 2 - 4 pm; other times by arrangement
Location:  Nguyen Engineering - Rm. 5321

Class Time & Location:

Sec 001: Wednesdays 4:30 pm - 7:10 pm;   Exploratory Hall L003


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 required homework assignments, weekly quizzes, midterm, and comprehensive final examinations. 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.

See the MyMason for all course information.

Homework   16%
Quizzes   24%     (Lowest Quiz grade will be dropped)
Midterm Exam   30%
Comprehensive Final Exam   30%
All students must work in groups on the Homework assignments. Groups will be assigned by the instructor and additional information related to group responsibilities and grading will be distributed in the first class.
All required quizzes and exams must be performed independently. 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 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, 2018
Last day to drop: January 29, 2018 (no tuition penalty)
Final day to drop: February 23, 2018

Spring Break: March 14, 2018
Last day of Selective Withdrawal: March 30, 2018
Last day of classes: May 5, 2018

Final Examination: May 9, 2018, 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
Randomized Algorithms 13

Created: 24 Jan 2018
P.Y. Wang