CS583 Analysis of Algorithms (Spring 2013)

Class Information

Instructor Location and Time TA Office Hours Office Hours

Amarda Shehu , Room #4422 ENG, amarda\AT\gmu.edu Robinson Hall B113, W, 4:30pm - 7:10 pm W 12:30 - 2:30 pm W 2:30 - 4:30 pm

Class Information

This course will offer students a set of techniques by which to design and analyze algorithms. The class will cover recurrence relations, probabilistic analysis, sorting algorithms, advanced data structures for searching and mapping, optimization algorithms and advanced analysis, and graph algorithms. The last few lectures of the class will be devoted to the topic of NP-completeness, approximation algorithms, and other special topics.

Material will be disseminated in the form of lectures. Students will be tested on the comprehension of the basic material through a combination of quizzes, homeworks, and exams. In addition to the basic material, special topics will be covered. Extra credit will allow students that are interested in advanced topics and research to demonstrate their abilities. Extra credit will not account for more than 10% of the total grade of a homework or exam. Homeworks may include programming and reporting on the performance of algorithms implemented. No programming is involved in the exams, only pseudocode. No late deliverables will be accepted.

Prerequisites

CS 310, CS 330, and MATH 125.

Grade Breakdown

• Quizzes: 40% (~ 5% each)
• Homeworks: 10% (5% each)
• Exam 1: 20%
• Exam 2: 30%
Each hw and quizz is roughly 5% of the total grade. There will be the option of dropping the lowest hw or quizz grade from the total grade.

Preliminary Class Syllabus

Date	Topic	Chapters	Assignments
Jan 23	Course Overview and Introduction to Analysis of Algorithms	1-3	Self-eval. quizz
Jan 30	Algorithm Analysis	3-5	Quizz

Sorting

Feb 6	Algorithm Analysis	3-5	Quizz
Feb 13	Heapsort, Quicksort, and Linear-Time Sorting	6-8	Quizz

Data Structures for Mapping and Searching

Feb 20	Order Statistics and Hash Tables	9, 11-12	Quizz, Hw1 Out
Feb 27	Binary Search Trees, Balanced Search Trees, and Binomial Heaps	13, 19	Hw1 Due

Optimization and Advanced Analysis

Mar 6	Dynamic Programming, Greedy Algorithms	15-16	Quizz
Mar 20	Greedy Algorithms, Amortized Analysis	16-17	Quizz
Mar 27	Exam 1

Graph Algorithms

Apr 03	Graph Representation, Elementary Graph Algorithms, and Applications of DSF	22	Hw2 Out
Apr 10	Minimum Spanning Trees and Single-source Shortest Paths	22-23	Quizz
Apr 17	All-Pairs Shortest Paths and Maximum Flow	25-26	Quizz

Complexity Theory

Apr 24

NP-Completeness

29.1-2

Hw2 Due

May 01	NP-Completeness	29.1-2	Quizz
May 08	Exam 2		Robinson Hall B113

*Chapters correspond to the Cormen et al. book. Check class homepage for corresponding chapters in the Dasgupta et al. book.

Honor Code

The class enforces the GMU Honor Code. Violations of academic honesty will not be tolerated.

Disability Statement

If a disability or other condition affects your academic performance, document it with the Office of Disability Services.

Class Homepage

Latest lectures and other course materials will be available at URL
http://www.cs.gmu.edu/~ashehu/?q=CS583_Spring2013