CS 483 Spring 2016
Design and Analysis of Algorithms

Lecture time: Tuesday and Thursday 10:30am-11:45am

Location: Art and Design Building 2026

Course webpage:

Credit: 3

Instructor: Fei Li, Room 5326, Engineering Building, email: lifei@cs.gmu.edu

Office hours: Thursday 12:00pm-2:00pm

Teaching assistant: TBD

Office hours: TBD

News:

Course overview:

In this course, a thorough examination of several well-known techniques that are used for the design and analysis of efficient algorithms will be covered. Topics to be covered include theoretical measures of algorithm complexity, greedy algorithms, divide and conquer techniques, dynamic programming, graph algorithms, search strategies, and an introduction to the theory of NP-completeness.

Prerequisites:

CS 310 and CS 330 Calculus (MATH 113, 114, 213) and MATH 125. Please contact with the instructor if you are not sure.

Textbook:

Algorithm Design by Jon Kleinberg and Eva Tardos, Addison Wesley (2006).

Reserved at the Gateway Library inside the Johnson Center QA76.9.A43 K54 2006

Course materials:

 Lectures Topics Lecture Notes Scopes Assignments Notes 1 Introduction Chapter 1 2 Algorithm Analysis Chapter 2.1-2.3 3 Chapter 2.4 4 Graphs Chapter 3.1-3.3 5 Chapter 3.4-3.6 6 7 8 9 Greedy Algorithms Chapter 4.1-4.2 10 11 Chapter 4.4-4.5 12 13 Midterm Exam 14 15 16 Divide and Conquer Chapter 5.1-5.3 17 Master Theorem 18 19 Dynamic Programming 20 21 22 23 24 25 Network Flows 26 27 28 Final Exam

Topics:

In this course, we will consider the algorithm design and analysis techniques of various problems coming from the following areas:

Analysis of Algorithm Efficiency (asymptotic notation, amortized analysis)

Brute Force Techniques (sorting, search, traveling salesmen)

Divide and Conquer (merge sort, quicksort, matrix multiplication, polynomial multiplication)

Graph decomposition and search (connected components, shortest path problem)

Greedy Techniques (minimum spanning tree, Huffman trees)

Dynamic Programming (edit distance,matrix chainmultiplication, knapsack, all pairs shortest paths)

Linear Programming (network flows, matching, simplex, duality)

Randomized Algorithms

Course outcomes:

An understanding of classical problems in Computer Science

An understanding of classical algorithm design and analysis strategies

An ability to analyze the computability of a problem

Be able to design and analyze new algorithms to solve a computational problem

An ability to reason algorithmically

Weekly assignments or quizzes (10 * 3 ~ 30%)

Midterm exam (30%)

Final exam (40%)

Policies:

Hand in hard copies of assignments in class. Please note that all coursework is to be done independently. Plagiarizing the homework will be penalized by maximum negative credit and cheating on the exam will earn you an F in the course. See the GMU Honor Code System and Policies at http://www.gmu.edu/catalog/acadpol.html and http://www.cs.gmu.edu/honor-code.html. You are encouraged to discuss the material BEFORE you do the assignment. As a part of the interaction you can discuss a meaning of the question or possible ways of approaching the solution. The homework should be written strictly by yourself. In case your solution is based on the important idea of someone else please acknowledge that in your solution, to avoid any accusations.