| Instructor |
Greg Plaxton; office hours Th 3-4, F 3-4 in GDC
4.512; plaxton at cs dot utexas dot edu. NOTE: If there are several
students in attendance, I will try to hold the office hour in the
nearby seminar room 4.516, or in 4.414A (also nearby) if 4.516 is not
available.
|
| |
|
| Teaching Assistant |
Deniz Imrek; office hours M 11-12, T 10-11 at TA Station 1;
imrekd at cs dot 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. With regard to exercises that the class is actively working
on, students are allowed to post questions and responses related to
problem clarification, but should not post partial or complete
solutions.
|
| |
|
| Problem Sets |
There will be eight problem sets. Your solutions are required to
be typeset using LaTeX, and to be turned in electronically using
Canvas. Sample solutions will be made available on Canvas shortly
after the submission deadline. If you find yourself having difficulty
with a problem set question, you are strongly encouraged to attend
the office hours. You can also post questions on the online forum.
You can discuss high-level solution approaches with other students in
the class, but you are not allowed share detailed solutions, and you
are required to write up your solutions on your own. If you obtain a
key idea from another source, you are required to credit that source
in your solution, and to write up the solution in your own words.
|
| |
|
| 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 |
Problem Sets |
| 01/15-01/19 |
MLK |
01A |
PS1 out 01/17 (due 01/28) |
| 01/22-01/26 |
01B |
01C |
|
| 01/29-02/02 |
02A |
02B |
PS2 out 01/29 (due 02/09) |
| 02/05-02/09 |
02C |
03A |
|
| 02/12-02/16 |
T1 |
03B |
PS3 out 02/12 (due 02/22) |
| 02/19-02/23 |
03C |
04A |
PS4 out 02/22 (due 03/04) |
| 02/26-03/01 |
04B |
04C |
|
| 03/04-03/08 |
05A |
T2 |
PS5 out 03/06 (due 03/24) |
| 03/11-03/15 |
SPRING |
BREAK |
|
| 03/18-03/22 |
05B |
05C |
|
| 03/25-03/29 |
06A |
06B |
PS6 out 03/25 (due 04/05) |
| 04/01-04/05 |
06C |
07A |
|
| 04/08-04/12 |
T3 |
07B |
PS7 out 04/08 (due 04/17) |
| 04/15-04/19 |
07C |
08A |
PS8 out 04/17 (due 04/27) |
| 04/22-04/26 |
08B |
08C |
|
| 04/29-05/03 |
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
68% of the score based on the four tests (17% each) and
32% based on the eight problem sets (4% each).
|
| |
|
| Letter Grades |
The numerical cutoffs between different letter grades will be
determined at the end of the semester. (The last time I taught
this course, the overall class GPA was 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.
|