| Instructor |
Greg Plaxton, plaxton at cs dot utexas dot edu, GDC 4.512. Office hours T 1:00-3:00 and F 2:30-3:30.
|
| |
|
| Teaching Assistants |
Deniz Imrek (20-hr TA); office hours W 2:30-3:30 at TA Station 2 in GDC basement, M 5--6 at TA Station 3 in GDC basement; deniz dot imrek at utexas dot edu. Rojin Rezvansangsari (10-hr TA; no office hours); rojinrezvan at utexas dot edu.
|
| |
|
| 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 GAR 3.116 (section
50395) and M 2-3 in SZB 3.508 (section 50400).
|
| |
|
| 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 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/26-08/30 |
Module 1 |
Module 1 |
Module 1 |
Module 2 |
| 09/02-09/06 |
LABOR DAY |
LABOR DAY |
Quiz 1 |
Module 2 |
| 09/09-09/13 |
Module 3 |
Module 2 |
Quiz 2 |
Module 3 |
| 09/16-09/20 |
Module 4 |
Module 3 |
Quiz 3 |
Module 4 |
| 09/23-09/27 |
Module 5 |
Module 4 |
Quiz 4 |
Module 5 |
| 09/30-10/04 |
Module 6 |
Module 5 |
Quiz 5 |
Module 6 |
| 10/07-10/11 |
Module 7 |
Module 6 |
Quiz 6 |
Module 7 |
| 10/14-10/18 |
Module 8 |
Module 7 |
Quiz 7 |
Module 8 |
| 10/21-10/25 |
Module 9 |
Module 8 |
Quiz 8 |
Module 9 |
| 10/28-11/02 |
Module 10 |
Module 9 |
Quiz 9 |
Module 10 |
| 11/04-11/08 |
Module 11 |
Module 10 |
Quiz 10 |
Module 11 |
| 11/11-11/15 |
Module 12 |
Module 11 |
Quiz 11 |
Module 12 |
| 11/18-11/22 |
Module 13 |
Module 12 |
Quiz 12 |
Module 13 |
| 11/25-11/29 |
THANKSGIVING |
THANKSGIVING |
THANKSGIVING |
THANKSGIVING |
| 12/02-12/06 |
Quiz 13 |
Module 14 |
Module 14 |
Module 14 |
| 12/09-12/13 |
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 2023 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. |
| |
|
| 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 for that
quiz. As discussed in the "Overall Raw Score" section below, your
lowest quiz score will be dropped, and your second-lowest quiz score
will be assigned a reduced weight.
|
| |
|
| Overall Raw Score |
Your lowest quiz score will be dropped. Your second-lowest quiz
score will be worth 4 points towards your overall raw score out of
100. Your 12 highest quiz scores will each be worth 8 points.
|
| |
|
| Letter Grades |
The overall raw scores will be mapped to letter grades at the end of
the semester. In Fall 2023, the 75th, 50th, and 25th percentile
overall raw scores were 81, 72, and 60, respectively, and the
corresponding letter grades were A, B+, and 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.
|
| |
|
| 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.
|