Class Information
Instructor
Location and Time
Office Hours
|
Amarda Shehu , Room #4422 ENG, amarda\AT\gmu.edu
Innovation Hall #206, R, 7:20pm - 10:00 pm
W 4:00 - 6:00 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 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.
Prerequisites
CS 310, CS 330, and MATH 125.
Grade Breakdown
- Homeworks: 40% (10% each)
- Exam 1: 25%
- Exam 2: 35%
Preliminary Class Syllabus
| Date |
Topic |
Chapters |
Assignments |
| Aug 30 |
Course Overview and Introduction to Analysis of Algorithms |
1-3 |
|
| Sep. 06 |
|
|
Labor Day |
| Sep. 13 |
Algorithm Analysis |
3-5 |
Hw1 Out |
| Sep. 20 |
Heapsort, Quicksort, and Linear-Time Sorting |
6-8 |
|
|
|
Data Structures for Mapping and Searching
|
| Oct. 04 |
Order Statistics and Hash Tables |
9, 11-12 |
Hw1 Due, Hw2 Out |
| Oct. 12 |
Binary Search Trees,
Balanced Search Trees, and Binomial Heaps |
13, 19 |
Monday class meets Tuesday |
|
|
Optimization and Advanced Analysis
|
| Oct. 18 |
Dynamic Programming, Greedy
Algorithms |
15-16 |
Hw2 Due, Hw3 Out |
| Oct. 25 |
Greedy Algorithms, Amortized Analysis |
16-17 |
|
| Nov. 01 |
Exam 1 |
|
|
| Nov. 08 |
Graph Representation,
Elementary Graph Algorithms, and Applications of DSF |
22 |
Hw3 Due, Hw4 Out |
| Nov. 15 |
Minimum Spanning Trees and Single-source Shortest Paths |
22-23 |
|
| Nov. 22 |
All-Pairs Shortest Paths and Maximum Flow |
25-26 |
|
| Dec. 06 |
NP-Completeness |
29.1-2 |
Hw4 Due |
| Dec 20 |
Exam 2 |
|
Innovation Hall 206 |
*Chapters correspond to the Cormen et al. book. Check class homepage
for corresponding chapters in the Dasgupta et al. book.