| Instructor |
Greg Plaxton, plaxton at cs dot utexas dot edu, GDC 4.512. Office hours TW 3-4.
|
| |
|
| Teaching Assistants |
Vignesh Manoharan (vigneshm at cs dot utexas dot edu, office hours T 11-12, F 3-4 at TA Station 2);
Maxwell Wu (25wum at utexas dot edu, office hours Th 2:30-3:30 at TA station 2). UPDATE ADDED 10/16/23: Between now and Thanksgiving, Vignesh will not hold his F 3-4 office hour and will instead hold a second office hour on Tuesday evening. That office hour will run from 7:30 to 8:30 and will be held over zoom. See the Zoom section of Canvas for the link.
|
| |
|
| Lectures |
MWF 10-11 in RLP 0.128 |
| |
|
| Lectures Online |
Any material displayed over the projector during the lectures in
RLP 0.128 will be automatically captured by the Lectures Online
system. The resulting recordings will populate in the Lectures Online
section of Canvas. Please note that the discussion sections and office
hours will not be recorded.
|
| |
|
| Discussion Sections |
The discussion sections take place M 1-2 in GDC 2.210 (section
52785) and M 2-3 in MEZ 1.120 (section 52790).
|
| |
|
| Prerequisites |
The following coursework with a grade of at least C- in each
course: CS 429 (or 310) or 429H (or 310H); M 362K or SDS 321 (or SSC
321) or M 362K; and a pre-req or co-req of M 340L, 341, or SDS 329C
(or SSC 329C).
|
| |
|
| Recommended Textbook |
In some sense, the lecture slides (posted in the Files section of
Canvas) play the role of the course textbook. Please note that, like
a textbook, some of the lecture slides include more material (e.g.,
detailed proofs, extra examples) than we will be able to cover in
class. In preparing for a given quiz, students should review all of
the material on the associated lecture slides (though the material
presented in class will generally be given greater emphasis on the
quiz). While there is no required textbook for this course, most
students will find it beneficial to consult outside resources (e.g.,
an algorithms text, Wikipedia) from time to time. The recommended
text is Algorithms by Jeff Erickson, which can be downloaded
for free from
Jeff's
website. Some of the topics that we cover are not included in
this text, but are covered by additional lecture notes available on
Jeff's site under the headings "More Algorithms Lecture Notes" and
"Models of Computation". Other algorithms textbooks cover many of
the same topics, and can serve as useful alternative references. For
example, Algorithm Design by Kleinberg and Tardos is an
excellent text, as is Introduction to Algorithms by Cormen,
Leiserson, Rivest, and Stein.
|
| |
|
| Course Outline |
The course material is organized into 14 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 |
Course overview; growth of functions |
| 1 |
01B_stable_marriage |
Stable marriage |
| 2 |
02A_basic_graph_algs |
Graph traversal |
| 2 |
02B_greedy_algs |
Greedy algorithms |
| 3 |
03A_dijkstra_sssp |
Dijkstra's single-source shortest paths algorithm |
| 3 |
03B_kruskal_mst |
Kruskal's MST algorithm |
| 3 |
03C_divide_and_conquer |
Divide and conquer recurrences |
| 4 |
04A_fast_fourier_transform |
The Fast Fourier Transform algorithm |
| 4 |
04B_dynamic_programming |
Dynamic programming |
| 5 |
05A_bellman_ford_and_floyd_warshall |
The Bellman-Ford and Floyd-Warshall algorithms |
| 5 |
05B_knapsack |
The knapsack problem |
| 5 |
05C_amortized_analysis |
Amortized analysis |
| 6 |
06A_splay_trees |
Splay trees |
| 6 |
06B_augmented_trees |
Augmented trees |
| 7 |
07A_ford_fulkerson |
The Ford-Fulkerson max-flow algorithm |
| 7 |
07B_edmonds_karp |
The Edmonds-Karp max-flow algorithm |
| 8 |
08A_project_selection |
A project selection problem |
| 8 |
08B_bipartite_matching |
Bipartite matching |
| 8 |
08C_linear_programming |
Linear programming |
| 9 |
09A_polynomial-time_reductions |
Polynomial-time reductions |
| 9 |
09B_satisfiability |
Satisfiability |
| 9 |
09C_the_class_NP |
The class NP |
| 10 |
10A_NP-completeness |
NP-completness |
| 10 |
10B_three-dimensional_matching |
The three-dimensional matching problem |
| 11 |
11A_graph_coloring |
The graph coloring problem |
| 11 |
11B_PSPACE |
PSPACE and PSPACE-completeness |
| 11 |
11C_turing_machines |
Turing machines |
| 12 |
12A_undecidability |
Undecidability |
| 12 |
12B_halting_problem |
The halting problem |
| 12 |
12C_load_balancing |
Approximation algorithms |
| 13 |
13A_vertex_cover |
Approximation algorithms for vertex cover |
| 13 |
13B_set_cover |
Approximation algorithms for set cover |
| 14 |
14A_randomized_algs |
Randomized algorithms |
| 14 |
14B_quicksort |
Randomized sorting |
|
| |
|
| Online Forum |
Ed Discussion (accessible through Canvas) will be used for online
discussion of the course material. If you have a personal question for
the instructional staff (e.g., if one of your scores was not recorded
properly), you can initiate private thread. Otherwise, you should post
your comments publicly so that other students can benefit from seeing
a response.
|
| |
|
| Recommended Exercises |
At the beginning of each module, a set of recommended exercises
will be released (in the Files section of Canvas). Sample solutions
will be provided for these exercises. Questions related to the
recommended exercises may appear on the associated quiz. If you are
having difficulty understanding one of the recommended exercises or
sample solutions, you are encouraged to post a question on Ed
Discussion; generally speaking, such a post should indicate the
particular word or phrase that is giving you
difficulty. Alternatively, you can pose your questions during the
office hours.
|
| |
|
| Quizzes |
Each of the 14 course modules will have an associated quiz that is
administered during one of the lecture periods. No course materials
or electronic devices may be used during the quizzes. The calendar
below shows when each quiz will take place. It also indicates which
module will be covered in each of the remaining class meetings. The
questions on a given quiz will be based on the material covered in the
associated class meetings, lecture slides, and recommended exercises.
In the table below, the column labeled "Monday AM" refers to the
Monday morning class period, and the column labeled "Monday PM" refers
to the Monday afternoon discussion section.
| Week |
Monday AM |
Monday PM |
Wednesday |
Friday |
| 08/21-08/25 |
Module 1 |
Module 1 |
Module 1 |
Module 2 |
| 08/28-09/01 |
Quiz 1 |
Module 2 |
Module 2 |
Module 3 |
| 09/04-09/08 |
LABOR DAY |
LABOR DAY |
Quiz 2 |
Module 3 |
| 09/11-09/15 |
Module 4 |
Module 3 |
Quiz 3 |
Module 4 |
| 09/18-09/22 |
Module 5 |
Module 4 |
Quiz 4 |
Module 5 |
| 09/25-09/29 |
Module 6 |
Module 5 |
Quiz 5 |
Module 6 |
| 10/02-10/06 |
Module 7 |
Module 6 |
Quiz 6 |
Module 7 |
| 10/09-10/13 |
Module 8 |
Module 7 |
Quiz 7 |
Module 8 |
| 10/16-10/20 |
Module 9 |
Module 8 |
Quiz 8 |
Module 9 |
| 10/23-10/27 |
Module 10 |
Module 9 |
Quiz 9 |
Module 10 |
| 10/30-11/03 |
Module 11 |
Module 10 |
Quiz 10 |
Module 11 |
| 11/06-11/10 |
Module 12 |
Module 11 |
Quiz 11 |
Module 12 |
| 11/13-11/17 |
Module 13 |
Module 12 |
Quiz 12 |
Module 13 |
| 11/20-11/24 |
THANKSGIVING |
THANKSGIVING |
THANKSGIVING |
THANKSGIVING |
| 11/27-12/01 |
Quiz 13 |
Module 14 |
Module 14 |
Module 14 |
| 12/04-12/08 |
Quiz 14 |
Quiz 14 discussion |
|
|
|
| |
|
| Sample Quiz
Questions |
The last time I taught this course, there were four tests instead
of 14 quizzes. In the Files section of Canvas, you will find a folder
entitled "old_tests" that contains the four tests from this previous
offering. You should refer to those tests to see some sample
questions. Sample solutions to the old test questions will not be
provided, but some of these questions may be discussed in class and we
will be happy to discuss any of them during office hours. |
| |
|
| Attendance |
Attendance will sometimes be taken at the lectures and discussion
sections. If attendance is taken at a given class meeting, you risk
being counted as absent if you are not present for the entire meeting
(e.g., from 10 to 10:50 for a lecture). Attendance scores do not
directly contribute to a student's overall score in the
course. Instead, they are used to determine the number (between 0 and
4) of low quiz scores to be dropped; see the section entitled "Overall
Raw Score" below for further details. Any student is welcome to
attend any discussion section; however, for the purposes of scoring
attendance, a student will only be given credit for attending their
assigned discussion section. Remark: If you are registed for 52785 and
would like to attend the 52790 discussion section throughout the
semester (or vice versa), let me know and I will re-classify you for
attendance purposes.
|
| |
|
| Make-Up Quizzes |
No make-up quizzes will be given in this course. If a student misses
a quiz for any reason, they will receive a score of zero. Please note
that the attendance policy allows for as many as four low quiz scores
to be dropped; see the "Overall Raw Score" section below for further
details.
|
| |
|
| Overall Raw Score |
Assume that a given student attends a p fraction of the class
meetings where attendance is taken. Let the student's (sorted) quiz
scores be a1≥...≥a14, and
for any integer i in {1,...,14}, let si
denote the sum of the student's i highest scores. Let q
denote min(p,0.8), let k denote
⌊5q⌋ (thus k belongs to
{0,1,2,3,4}), and let z denote 5q-k (thus
0≤z<1). The student's overall raw score is defined as
[s13-k+(1-z)a14-k]/(14-k-z),
which can be interpreted as the (appropriately weighted) average
obtained after dropping the student's lowest
5q=k+z quiz scores. Examples: (1) The overall
raw score of a student with an attendance score of 80% or higher is
the average of their 10 highest quiz scores; (2) The overall raw score
of a student with an attendance score of zero is the average of their
14 quiz scores; (3) The overall raw score of a student with an
attendance score of 52% is
(s11+0.4a12)/11.4.
|
| |
|
| Letter Grades |
The overall raw scores will be mapped to letter grades at the end of
the semester. Estimates of the numerical cutoffs associated with this
mapping will be provided as the semester progresses. It is possible
for everyone to get an A. Typically, the class GPA is about 3.5.
|
| |
|
| Quantitative Reasoning |
This course carries the Quantitative Reasoning flag. Quantitative
Reasoning courses are designed to equip you with skills that are
necessary for understanding the types of quantitative arguments you
will regularly encounter in your adult and professional life. You
should therefore expect a substantial portion of your grade to come
from your use of quantitative skills to analyze real-world problems.
|
| |
|
| 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.
|