Lecture Time: Monday 7:20
pm - 10:00 pm
Location: Innovation Hall 206
Course webpage: http://www.cs.gmu.edu/~lifei/teaching/cs583_fall12
Credit: 3
Instructor: Fei Li, Room 5326, Engineering Building, email:
mailto:lifei@cs.gmu.edu
Office hours: Monday 4:00pm - 6:00pm
Teaching Assistant: Ermo Wei, Room TBD,
Engineering Building, email: mailto:'ewei@masonlive.gmu.edu'
Office hours: TBD
NEWS:
Lecture |
Date |
Topic |
Lecture
Notes |
Scope |
Assignments |
Note |
1 |
August
27 |
Introduction |
|
|
|
|
2 |
September
3 |
|
|
|
|
|
3 |
September
10 |
|
|
|
|
|
4 |
September
17 |
|
|
|
|
|
5 |
September
24 |
|
|
|
|
|
6 |
October
1 |
|
|
|
|
|
7 |
October
8 |
|
|
|
|
|
Midterm Exam |
October
15 |
|
|
|
|
|
8 |
October
22 |
|
|
|
|
|
9 |
October
29 |
|
|
|
|
|
10 |
November
5 |
|
|
|
|
|
11 |
November
12 |
|
|
|
|
|
12 |
November
19 |
|
|
|
|
|
13 |
November
26 |
|
|
|
|
|
14 |
December
3 |
|
|
|
|
|
Final exam |
December
17 7:30pm
– 10:15pm |
|
|
|
|
|
· Function
growth: O, theta, omega notation --- CLRS 3
· Recurrence
relations --- CLRS 4
· Probabilistic
analysis; randomized algorithms --- CLRS 5
· Amortized
analysis --- CLRS 17
· Dynamic
programming --- CLRS 15
· Greedy
algorithms --- CLRS 16.1-3
· Sorting
heapsort, quicksort, mergesort
--- CLRS 2, 6, 7
· Non-comparison-based
--- CLRS 8
· Selection/order
statistics --- CLRS 9
· Data
structures balanced binary search trees --- CLRS 12, 13
· Hash
tables --- CLRS 11
· Heaps
/ priority queues --- CLRS 6.5, 20
· Graph
algorithms: BFS/DFS --- CLRS 22
· Minimum
spanning tree --- CLRS 23
· Shortest
paths --- CLRS 24, 25
·
Maximum flow --- CLRS 26.1-3
·
Time Complexity, NP-Complete --- CLRS 34
·
Midterm
Exam (30%)
·
Final
Exam (30%)
·
Assignments
(40%)
·
No
make-up exams for missed tests.
·
No
late assignments graded.
In addition to providing
your professors with the appropriate form, please take the initiative to
discuss accommodation with them at the beginning of the semester and as needed
during the term. Because of the range of learning differences, faculty members
need to learn from you the most effective ways to assist you. If you have
contacted the Disability Resource Center and are waiting to hear from a
counselor, please tell me.