|
Instructor Class Location and Time TA Contact Info and TA Office Hours Instructor Office Hours |
Amarda Shehu , Room #4452 ENG, amarda\AT\gmu.edu Innovation Hall 204, F 1:30pm - 4:10pm TBD F 11:30am - 1:30pm |
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.
CS 310 (minimum grade of C), CS 330 (minimum grade of C), and MATH 125 (minimum grade of C).
| 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 | NP-Completeness | 29.1-2 | Quizz |
| TBD | Exam 2 | 4:30 pm – 7:15 pm |
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
https://cs.gmu.edu/~ashehu/?q=CS583_Spring2019