CS:3330 Algorithms, Sections 0001, 0002
Section 0001: 11:00-12:15 TTh Room 110 MLH (MacLean Hall)
Section 0002: 12:30-1:45 TTh Room 118 MLH (MacLean Hall)
Sriram V. Pemmaraju (Section 0001)
Office: 101G MLH, email@example.com, 319-353-2956
Office Hours: 1:30-2:30 M, 10:30-11:30 W, 2:00-3:00 F (and by appointment)
Shreyas Pai (Section 0002)
Office: 101A MLH, firstname.lastname@example.org
Office Hours: 11:00-noon M, 2:00-3:00 W, 9:30-10:30 F (and by appointment)
Course website: http://www.cs.uiowa.edu/~sriram/3330/spring17/
Department website: http://www.cs.uiowa.edu/
Algorithms are "recipes" for solving computational problems and have been around at least
since 300 BCE when Euclid
described an algorithm for computing the greatest common divisor of a given pair of
numbers. Now algorithms are viewed as the greatest contribution of the field of computer
science to every day life. Algorithms are used wherever computers are; search engines, weather prediction,
drug design, financial markets, supply-chain management and even "JEOPARDY!" are just a few examples
from among many.
Previous courses have already given you a taste of "algorithmic thinking" and the main aims of this course
are to (i) deepen your algorithmic intuition, (ii) help you build a toolbox of algorithmic design
techniques, and (iii) to develop the ability to effectively communicate algorithms.
In this course, We will practise the precise statement of various computational problems,
think about different algorithmic strategies to solve them -- either exactly or with some controlled
error, reason about their correctness, evaluate these algorithms from the point of view of efficiency
(usually running time) and accuracy, and develop a feel for the difficulty of problems and the
applicability of various techniques we will learn.
Information about TAs,
Quizzes, Projects, and Exams,
The TAs for the course are Xin Man (email@example.com) and Richard Blair
(firstname.lastname@example.org), both computer science PhD students.
Information about office hours of the TAs will be posted here during the first week of
Both TAs will hold office hours in 101N MLH according to the following schedule:
Xin Man: T 5:00pm to 6:30pm and Th 9:30am to 11:00am.
Richard Blair: M 10:30am to noon and Th 5:00pm to 6:30pm.
- 4/25 Final exam is from 7:30 am to 9:30 am on Wed, 5/10, in LR1 Van Allen Hall. Here is some information about the final exam.
- 3/30 Reteach session in preparation for Exam 2 will be in 118 MLH, 8pm-9:15pm on Sun, April 2nd.
- 3/30 Tentative mid-semester scores and letter grades.
- 3/27 Exam 2 will be on Tue, Apr 4th from 6:30 pm to 8:30 pm in Shambaugh Auditorium, Main Library.
Here is some information about the exam.
- 3/27 There will be an in-class quiz (Quiz 3) on MST algorithms on Thu 3/30.
- 3/21 There will be an in-class quiz (Quiz 2) on SSSP algorithms on Thu 3/23.
- 3/3 Shryeas Pai (instructor for Section 2) has moved his Monday office hours to 11 am to 12 noon. This is in the hopes
of getting more of you to visit him during office hours.
- 1/13 Exam 1 will be on Tue, Feb 21st from 6:30 pm to 8:30 pm in Shambaugh Auditorium, Main Library.
Here is some information about the exam. Here are two exams from
a previous semester (Fall 15) when I taught this course: Fall 15 exam1.pdf,
Fall 15 mini-exam1.pdf. Practice problems for Exam 1 on approximation algorithms.
Here is my Solution to the practice exam.
- 1/24 TA Xin Man will hold office hours: T 5:00pm to 6:30pm and Th 9:30am to 11:00am in 101N MLH.
- 1/20 TA Richard Blair will hold office hours: M 10:30am to noon and Th 5:00pm to 6:30pm in 101N MLH.
- 1/17 Quiz 1 on common classes of running times (Function Review Handout 1) will be in class on Tue, 1/24.
- 1/16 Shreyas Pai, instructor for Section 2 will hold office hours in 101A MLH.
Week 14: 4/24-4/28
Section 5.2 on the Longest Increasing Subsequence (LIS) from Section 5.1 in Prof. Jeff Erickson's lecture notes.
- An example of 2-dimensional dynamic programming: the Longest Increasing Subsequence problem
- A gentle introduction to intractability: optimization problems versus decision problems,
the class P and some prominent examples of members of this class,
the notion of efficient certification, the definition of the class NP.
- The P vs NP problem.
Week 13: 4/17-4/21
Section 5.1 on the Fibonacci numbers example from Section 5.1 in Prof. Jeff Erickson's lecture notes, Section 6.1 on the Weighted Interval Scheduling problem from "Algorithm Design" by Kleinberg and Tardos -- this section has been posted on ICON.
- Introduction to dynamic programming using the Fibonacci numbers example.
- Recursive definitions, recursive algorithms implementing recursive definitions, memoization for speeding up
recursive functions, explicit filling of tables while removing recursion, shrinking table size to save memory.
- A dynamic programming solution to weighted interval scheduling.
Week 12: 4/10-4/14
Readings: Section 1.5 (on QuickSort), Section 1.8 (on Karatsuba's Multiplication algorithm)
from Chapter 1 in Prof. Jeff Erickson's lecture notes, and Sections 2.1, 2.3, and Section 3 from Prof. Erickson's appendix on solving recurrences.
- Karatsuba's multiplication algorithm
- Solution to the Karatsuba recurrence, solving recurrences of the form
T(n) = a T(n/b) + f(n), the Master Theorem for solving such recurrences
- Randomized QuickSort, using the solution to Balanced Partition in Randomized Quicksort.
Week 11: 4/3-4/7
Readings: Chapter 1 (Sections 1.4) on merge sort at
Merge Sort in Prof. Jeff Erickson's lecture notes, and Sections 2.1, 2.3, and Section 3 from Prof. Erickson's appendix on solving recurrences.
- Exam 2 review and Exam 2.
- Introduction to the divide-and-conquer paradigm: the merge sort algorithm, the merge sort recurrence, solving recurrences of a certain form. Examples of recurrences that arise
in randomized selection, Karatsuba's multiplication algorithm, etc.
Week 10: 3/27-3/31
Readings: Chapter 20 (except Section 20.5, which can be skipped) on MST algorithms from
Prof. Jeff Erickson's lecture notes,
Chapter 17 (Sections 17.1, 17.2, and 17.3) on the Disjoint Set Union-Find data structure at
Union Find in Prof. Jeff Erickson's lecture notes, and
Chapter 1 (Sections 1.4) on merge sort at
Merge Sort in Prof. Jeff Erickson's lecture notes, and
- Kruskal's algorithms and the Disjoint Set Union-Find data structure.
- Alternative implementations of the Disjoint Set Union-Find data structure: union by depth, shallow trees, and path compression; amortized analysis of data structures.
Week 9: 3/20-3/24
Readings: Chapter 20 (except Section 20.5, which can be skipped) on MST algorithms from Prof. Jeff Erickson's lecture notes.
- The Minimum Spanning Tree (MST) problem.
- The "Blue Rule" for including edges in the MST and the "Red Rule" for excluding edges from the MST.
- The algorithms of Boruvka and Prim, their implementations, and run-time analysis
- Proofs of the "Blue Rule" and "Red Rule".
- Kruskal's algorithms and the Disjoint Set Union-Find data structure.
Week 8: 3/6-3/10
Readings: Sections 21.1 through 21.4 on SSSP algorithms from Prof. Jeff Erickson's lecture notes.
- Proof of correctness of the Ford-Dantzig generic SSSP algorithm (v1)
- The Ford-Dantzig generic SSSP algorithm (v2) with the "bag" data structure
- Obtaining Dijkstra's algorithm by replacing the "bag" data structure by a min-heap priority queue
- Run-time analysis of Dijkstra's algorithm when all edge-weights are non-negative.
Week 7: 2/27-3/3
Readings: Section 7.4 "Huffman Codes" and Sections 21.1 through 21.4 on SSSP algorithms from Prof. Jeff Erickson's lecture notes.
- Proof of correctness of the Huffman coding algorithm.
- Shortest Path problems: the s-t Shortest Path problem, the Single Source Shortest Path (SSSP) problem, the All Pairs Shortest Path (APSP) problem.
- The Ford-Dantzig generic SSSP algorithm that works even when edge weights are negative, provided no negative cycles are present.
Week 6: 2/20-2/24
Readings: Section 7.4 "Huffman Codes" from Prof. Jeff Erickson's lecture notes.
- Exam 1 review and Exam 1.
- The Minimum Length Prefix-Free Binary Encoding problem and Huffman's greedy algorithm to solve it.
- Examples of prefix-free binary encodings and their connection to binary encoding trees.
Week 5: 2/13-2/17
Readings: Section 7.2 "Scheduling Classes" (on the Interval Scheduling problem)
from Prof. Jeff Erickson's lecture notes.
- The Interval Scheduling problem: a maximization problem and
construction of counterexamples for some natural greedy algorithms.
- The "Earliest Finish Time First" greedy algorithm for the interval scheduling problem.
- Proof of correctness of the greedy algorithm using the "exchange" approach.
Week 4: 2/6-2/10
Readings: A well-written blog post on the 2-approximation to MVC, Section 35.1 from textbook by Cormen, Leiserson, Rivest, and Stein, posted on ICON.
- A 2-approximation algorithm for MVC using maximal matchings.
- Introduction to randomized algorithms via the Balanced Partition problem.
- A Las Vegas algorithm and a Monte Carlo algorithm for Balanced Partition.
- Analysis of expected running time of Las Vegas algorithm and error probability of Monte Carlo
Week 3: 1/30-2/3
- Examples of analysis of algorithms: selectionSort, primality, maximum independent set problem, etc.
to further illustrate the use of asymtotic notation, input size, worst case analysis, etc.
- Optimization problems, the notion of approximation algorithms for optimization problems.
- The minimum vertex cover (MVC) problem, a natural "greedy" algorithm for MVC, a "bad" example
for this "greedy" algorithm.
Week 2: 1/23-1/27
Readings: Read Section 2.2 (on asymptotic notation), Section 2.3 (on implementing the Stable
Marriage algorithm), and Section 2.4 (on some common examples of running times) all from Chapter 2 of the
Kleinberg-Tardos textbook, posted on ICON.
- Introduction to the analysis of algorithms
- The RAM model, the notion of input size; the notion of worst case analysis; examples of running time analysis
- Notation for asymptotic growth of functions; properties of asymptotic notation
- Common classes of running times: polynomials, exponentials, logarithmic functions; the notion of efficient algorithms
Week 1: 1/16-1/20
Readings: Chapter 1 from the Kleinberg-Tardos textbook, posted on ICON,
Review of common classes of running times: Function Review Handout.
- Introduction to the course
- The stable marriage problem and the Gale-Shapley (GS) algorithm.
- Proof of correctness of the GS algorithm.
- Worst case example for the GS algorithm
Links: The 2012 Nobel prize in Economics was awarded to Lloyd Shapley and Alvin Roth; to Shapley for
his work with David Gale on the stable marriage problem and to Roth for his work in the 1980's on the
design of matching markets for matching doctors and hospitals, students and high schools,
kidneys and patients, etc. Here is a 5-page "information for the public" from the Royal Swedish Academy
of Sciences on the work of Shapley and Roth.