CS483 Analysis of Algorithms (Spring 2017)

Class Information

Instructor Location and Time TA Office Hours Office Hours

Amarda Shehu , Room #4452 ENG, amarda\AT\gmu.edu Robinson Hall A111, MW 9:00am - 10:15am TBD TBD

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, such as 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. No late deliverables will be accepted, except for rare documented special circumstances.

Prerequisites

CS 310 (minimum grade of C), CS 330 (minimum grade of C), and MATH 125 (minimum grade of C).

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	Applications of DFS	22	Quizz
Week 12	Minimum Spanning Trees and Single-source Shortest Paths	22-23	Quizz
Week 13	All-Pairs Shortest Paths and Maximum Flow	25-26	Quizz

Complexity Theory

Week 14-15	NP-Completeness	29.1-2	Quizz
05/15	Exam 2		7:30 am – 10:15 am

*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=CS483_Spring2017