|
Instructor Location and Time Office Hours |
Amarda Shehu , Room #4422 ENG, amarda\AT\gmu.edu STI #122, W, 4:30pm - 7:10 pm T 2:00 - 4:00 pm |
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 homeworks and exams. In addition to the basic material, special topics will be covered. Extra credit in the homeworks and exams 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. Some homeworks may include programming and reporting on the performance of algorithms implemented. No programming is involved in the exams, only pseudocode. No late homeworks or project deliverables will be accepted.
C or better in CS 310, CS 330, and Math 125.
| Date | Topic | Chapters | Assignments |
|---|---|---|---|
| Jan. 20 | Course Overview and Introduction to Analysis of Algorithms | 1-3 | |
| Jan. 27 | Algorithm Analysis | 3-5 | Hw1 Out |
| Sorting |
| Feb. 03 | Heapsort, Quicksort, and Linear-Time Sorting | 6-8 | |
| Feb. 10 | Order Statistics and Convex Hull | 9, 33.1, 33.3 | Hw1 Due, Hw2 Out |
| Data Structures for Mapping and Searching | ||
| Feb. 17 | Hash Tables, Binary Search Trees | 12 | |
| Feb. 24 | Balanced Search Trees and Binomial Heaps | 13, 19 | Hw2 Due |
| Optimization and Advanced Analysis | ||
| Mar. 03 | Midterm Exam Dynamic Programming |
15 | |
| Mar. 10 | Spring Break | ||
| Mar. 17 | Greedy Algorithms and Amortized Analysis | 16-17 | Hw3 Out |
| Graph Algorithms | ||
| Mar. 24 | Graph Representation and Elementary Graph Algorithms | 22 | |
| Mar. 31 | Minimum Spanning Trees and Single-source Shortest Paths | 22-23 | Hw3 Due, Hw4 Out |
| Apr. 07 | All-Pairs Shortest Paths and Maximum Flow | 24,25 | |
| Selected Topics | ||
| Apr. 14 | Linear Programming | 24.4 | Hw4 Due |
| Apr. 21 | NP-completeness | 26.1-26.2, 29 | Apr. 28 | Approximation Algorithms | 35 |
| May 05 | Final Exam |
The class enforces the GMU Honor Code. Violations of academic honesty will not be tolerated.
If a disability or other condition affects your academic performance, document it with the Office of Disability Services.
Latest lectures and other course materials will be available at
URL
http://www.cs.gmu.edu/~ashehu/?q=CS483_Spring2010