| Instructor |
Greg Plaxton, plaxton at cs dot utexas dot edu, GDC 4.512. Office hours T 5-6, F 2-3.
|
| |
|
| Teaching Assistants |
Trung Nguyen (20-hr TA); office hours M 3-4 and W 8:45-9:45; trungnguyen at utexas dot edu. Brian Jiang (15-hr UGCA); office hour T 3-4; brianjiang at utexas dot edu. All TA/UGCA office hours will be held on the fourth floor bridge of GDC.
|
| |
|
| 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 these recordings are not intended
as a substitute for attending class in person. They are primarily
being provided so that students can review difficult portions of the
lecture material on their own after class. Please note that the
discussion sections and office hours will not be recorded. Also, some
lecture material may be presented on the board; in such cases, the
Lectures Online system will only capture the associated audio.
|
| |
|
| Discussion Sections |
The discussion sections take place M 1-2 in ECJ 1.308 (section
54850) and M 2-3 in ECJ 1.222 (section 54855).
|
| |
|
| Prerequisites |
The following coursework with a grade of at least C-: Computer Science
429 or 429H; Mathematics 362K or Statistics and Data Sciences 321; and
credit with a grade of at least C- or registration for: Mathematics
340L, 341, or Statistics and Data Sciences 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 a lot 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 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/25-08/29 |
Module 1 |
Module 1 |
Module 1 |
Module 2 |
| 09/01-09/05 |
LABOR DAY |
LABOR DAY |
Quiz 1 |
Module 2 |
| 09/08-09/12 |
Module 3 |
Module 2 |
Quiz 2 |
Module 3 |
| 09/15-09/19 |
Module 4 |
Module 3 |
Quiz 3 |
Module 4 |
| 09/22-09/26 |
Module 5 |
Module 4 |
Quiz 4 |
Module 5 |
| 09/29-10/03 |
Module 6 |
Module 5 |
Quiz 5 |
Module 6 |
| 10/06-10/10 |
Module 7 |
Module 6 |
Quiz 6 |
Module 7 |
| 10/13-10/17 |
Module 8 |
Module 7 |
Quiz 7 |
Module 8 |
| 10/20-10/24 |
Module 9 |
Module 8 |
Quiz 8 |
Module 9 |
| 10/27-11/01 |
Module 10 |
Module 9 |
Quiz 9 |
Module 10 |
| 11/03-11/07 |
Module 11 |
Module 10 |
Quiz 10 |
Module 11 |
| 11/10-11/14 |
Module 12 |
Module 11 |
Quiz 11 |
Module 12 |
| 11/17-11/21 |
Module 13 |
Module 12 |
Quiz 12 |
Module 13 |
| 11/24-11/28 |
THANKSGIVING |
THANKSGIVING |
THANKSGIVING |
THANKSGIVING |
| 12/01-12/05 |
Quiz 13 |
Module 14 |
Module 14 |
Module 14 |
| 12/08-12/12 |
Quiz 14 |
Quiz 14 discussion |
|
|
|
| |
|
| Sample Quiz
Questions |
In the Files section of Canvas, you will find a folder entitled
"old_quizzes" that contains the Fall 2024 quizzes. Sample solutions
to the old quiz 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 54850 and
would like to attend the 54855 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.9), let k denote
⌊40q/9⌋ (thus k belongs to
{0,1,2,3,4}), and let z denote 40q/9-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
40q/9=k+z quiz scores. Examples: (1) The overall
raw score of a student with an attendance score of 90% 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 63% is
(s11+0.2a12)/11.2.
|
| |
|
| Letter Grades |
The overall raw scores will be mapped to letter grades at the end of
the semester. In Fall 2024, the median letter grade was a B+. The
overall score distribution and associated letter grade cutoffs tend to
vary a bit from one offering of the course to the next. Estimates of
the letter grade cutoffs for the present course will be provided as
the semester progresses.
|
| |
|
| 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.
|