CS583 Analysis of Algorithms (Fall 2014)

Class Information

Instructor Location and Time TA Office Hours Office Hours

Amarda Shehu , Room #4422 ENG, amarda\AT\gmu.edu Innovation Hall 131, 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, algorithms for order statistics, 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 special topics, including NP-completeness and approximation algorithms.

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. All quizzes and exams are closed book. Up to two cheat sheets will be allowed. 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. No late deliverables will be accepted, except for rare documented special circumstances.

Prerequisites

CS 310, CS 330, and MATH 125.

Tentative 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.

Tentative Class Syllabus

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

Sorting

Week 3	Algorithm Analysis	3-5	Quizz
Week 4	Heapsort, Quicksort, and Linear-Time Sorting	6-8	Quizz

Data Structures for Mapping and Searching

Week 5	Order Statistics and Hash Tables	9, 11-12	Quizz, Hw1 Out
Week 6	Binary Search Trees, Balanced Search Trees, and Binomial Heaps	13, 19	Hw1 Due

Optimization and Advanced Analysis

Week 7	Dynamic Programming, Greedy Algorithms	15-16	Quizz
Week 8	Greedy Algorithms, Amortized Analysis	16-17	Quizz
Week 9	Exam 1

Graph Algorithms

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

Complexity Theory

Week 13

NP-Completeness

29.1-2

Hw2 Due

Week 14	NP-Completeness	29.1-2	Quizz
Week 15	Exam 2		ENGR 1103

*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_Fall2014