| Instructor |
Greg Plaxton; office hours T 3-4, F 3-4 in GDC
4.512; plaxton at cs dot utexas dot edu.
|
| |
|
| Teaching Assistant |
Trung Nguyen; office hours TBD; trungnguyen at utexas dot edu.
|
| |
|
| Class Time |
MW 2-3:30 |
| |
|
| Class Location |
GDC 4.304 |
| |
|
| Lectures Online |
Any material displayed over the projector during the lectures
will be automatically captured by the Lectures Online system. The
resulting recordings will populate in the Lectures Online section of
Canvas.
|
| |
|
| Recommended Textbook |
There is no required textbook for this course. However, several of the
lectures are based on material from
Introduction to Algorithms by Cormen, Leiserson, Rivest, and
Stein. Other good references are Algorithm Design by Kleinberg
and Tardos and Algorithms Erickson. The latter text can be
downloaded for free from Jeff's UIUC website. See also the additional
lecture notes available on Jeff's website under the heading "More
Algorithms Lecture Notes".
|
| |
|
| Course Outline |
This is a graduate course in the design and analysis of
algorithms. Some of the course material revisits topics that are
covered in a typical undergraduate algorithms course; in such cases,
we tend to emphasize more advanced aspects. The course material is
organized into 8 modules as indicated in the table below. The slides
listed in the table may be found (with extension .pdf) in the Files
section of Canvas.
| Module |
Slides |
Topic |
| 1 |
01A_introduction |
Growth of functions; divide-and-conquer algorithms |
| 1 |
01B_fast_fourier_transform |
The Fast Fourier Transform algorithm |
| 1 |
01C_basic_graph_algs |
Graph traversal |
| 2 |
02A_dynamic_programming |
Dynamic programming |
| 2 |
02B_greedy |
Greedy algorithms |
| 2 |
02C_matroids |
Matroids |
| 3 |
03A_amortized_analysis |
Amortized analysis |
| 3 |
03B_splay_trees |
Splay trees |
| 3 |
03C_augmented_trees |
Augmented trees |
| 4 |
04A_fibonacci_heaps |
Fibonacci heaps |
| 4 |
04B_union_find |
Data structures for disjoint sets |
| 4 |
04C_ford_fulkerson |
The Ford-Fulkerson max-flow algorithm |
| 5 |
05A_edmonds_karp |
The Edmonds-Karp max-flow algorithm |
| 5 |
05B_push_relabel |
Push-relabel max-flow algorithms |
| 5 |
05C_min-cost_perfect_matching |
Minimum-cost bipartite perfect matching |
| 6 |
06A_linear_programming |
Linear programming |
| 6 |
06B_p_and_np |
The complexity classes P and NP |
| 6 |
06C_np-completeness |
NP-completeness |
| 7 |
07A_np-completeness_and_beyond |
NP-completeness; classes beyond NP |
| 7 |
07B_load_balancing |
Approximate load balancing |
| 7 |
07C_vertex_cover |
Approximability of vertex cover |
| 8 |
08A_set_cover |
Approximability of set cover |
| 8 |
08B_randomized_algorithms |
Randomized algorithms |
| 8 |
08C_hypercube_routing |
Randomized routing on the hypercube |
|
| |
|
| Prerequisites |
Graduate standing and an undergraduate algorithms course, or consent
of the instructor.
|
|
| |
|
| Online Forum |
Ed Discussion (accessible within Canvas) will be used for online
discussion of the course material. If you have a question for the
instructional staff that might be of interest to someone else, you
should generally post it to the online forum instead of sending an
email.
|
| |
|
| Solved Exercises |
At the beginning of each module, a set of solved exercises will
be released (in the Files section of Canvas). If you are having
difficulty understanding one of the solved exercises or sample
solutions, you are encouraged to attend office hours or to post a
question on Ed Discussion.
|
| |
|
| Tests |
There will be four tests administered during the usual lecture
period. No course materials or electronic devices (including
calculators) may be used during the tests. The calendar below shows
when each test will take place. It also indicates which lecture slides
will be covered in each of the remaining class meetings. Test 1 will
be based on the lectures, problem sets, and solved exercises related
to Modules 1 and 2. Similarly, Test 2 will be based on Modules 3 and
4, Test 3 will be based on Modules 5 and 6, and Test 4 will be based
on Modules 7 and 8.
| Week |
Monday |
Wednesday |
Solved Exercises |
| 01/12-01/16 |
1A |
1B |
| 01/19-01/23 |
MLK |
1C |
| 01/26-01/30 |
2A |
2B |
| 02/02-02/06 |
2C |
3A |
| 02/09-02/13 |
T1 |
3B |
| 02/16-02/29 |
3C |
4A |
| 02/23-02/27 |
4B |
4C |
| 03/02-03/06 |
5A |
T2 |
| 03/09-03/13 |
5B |
5C |
| 03/16-03/20 |
SPRING |
BREAK |
| 03/23-03/27 |
6A |
6B |
| 03/30-04/03 |
6C |
7A |
| 04/06-04/10 |
T3 |
7B |
| 04/13-04/17 |
7C |
8A |
| 04/20-04/24 |
8B |
8C |
| 04/27-05/01 |
T4 |
|
|
| |
|
| Make-Up Tests |
Please note that no make-up tests will be given in this course. If a
student has a legitimate and properly documented excuse for missing
one of the tests, the missing test score will be estimated based on
the other test scores. In the event of an unexcused absence, a score
of zero will be assigned. |
| |
|
| Overall Raw Score |
Each student will be assigned an overall raw score out of 100, with
each of the four tests counting for 25%.
|
| |
|
| Letter Grades |
The numerical cutoffs between different letter grades will be
determined at the end of the semester. (The last couple of times I
taught this course, the overall class GPA was about 3.5.)
|
| |
|
| Disability & Access |
Students with disabilities may request appropriate academic
accommodations from the Division of Diversity and Community
Engagement, Services for Students with Disabilities, 512-471-6259.
The university is committed to creating an accessible and inclusive
learning environment consistent with university policy and federal and
state law. Please let me know if you experience any barriers to
learning so I can work with you to ensure you have equal opportunity
to participate fully in this course. If you are a student with a
disability, or think you may have a disability, and need
accommodations please contact Disability & Access (D&A). Please refer
to the D&A
website for more information. If you are already registered with
D&A, please deliver your Accommodation Letter to me as early as
possible in the semester so we can discuss your approved
accommodations and needs in this course.
|