CS:3330 Algorithms, Sections 0001, 0002
Spring 2017
Section 0001: 11:0012:15 TTh Room 110 MLH (MacLean Hall)
Section 0002: 12:301:45 TTh Room 118 MLH (MacLean Hall)
Instructors:
Sriram V. Pemmaraju (Section 0001)
Office: 101G MLH, srirampemmaraju@uiowa.edu, 3193532956
Office Hours: 1:302:30 M, 10:3011:30 W, 2:003:00 F (and by appointment)
Shreyas Pai (Section 0002)
Office: 101A MLH, shreyaspai@uiowa.edu
Office Hours: 11:00noon M, 2:003:00 W, 9:3010: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, supplychain 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.
Syllabus document,
Information about TAs,
Announcements,
Quizzes, Projects, and Exams,
Weekly Topics,
Online Resources
The TAs for the course are Xin Man (xinman@uiowa.edu) and Richard Blair
(richardblair@uiowa.edu), both computer science PhD students.
Information about office hours of the TAs will be posted here during the first week of
classes.
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.
Announcements
 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, 8pm9:15pm on Sun, April 2nd.
 3/30 Tentative midsemester 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 inclass quiz (Quiz 3) on MST algorithms on Thu 3/30.
 3/21 There will be an inclass 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 miniexam1.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/244/28
Topics:
 An example of 2dimensional 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.
Readings:
Section 5.2 on the Longest Increasing Subsequence (LIS) from Section 5.1 in Prof. Jeff Erickson's lecture notes.

Week 13: 4/174/21
Topics:
 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.
Readings:
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.

Week 12: 4/104/14
Topics:
 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.
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.

Week 11: 4/34/7
Topics:
 Exam 2 review and Exam 2.
 Introduction to the divideandconquer 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.
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.

Week 10: 3/273/31
Topics:
 Kruskal's algorithms and the Disjoint Set UnionFind data structure.
 Alternative implementations of the Disjoint Set UnionFind data structure: union by depth, shallow trees, and path compression; amortized analysis of data structures.
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 UnionFind 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

Week 9: 3/203/24
Topics:

 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 runtime analysis
 Proofs of the "Blue Rule" and "Red Rule".
 Kruskal's algorithms and the Disjoint Set UnionFind data structure.
Readings: Chapter 20 (except Section 20.5, which can be skipped) on MST algorithms from Prof. Jeff Erickson's lecture notes.

Week 8: 3/63/10
Topics:
 Proof of correctness of the FordDantzig generic SSSP algorithm (v1)
 The FordDantzig generic SSSP algorithm (v2) with the "bag" data structure
 Obtaining Dijkstra's algorithm by replacing the "bag" data structure by a minheap priority queue
 Runtime analysis of Dijkstra's algorithm when all edgeweights are nonnegative.
Readings: Sections 21.1 through 21.4 on SSSP algorithms from Prof. Jeff Erickson's lecture notes.

Week 7: 2/273/3
Topics:
 Proof of correctness of the Huffman coding algorithm.
 Shortest Path problems: the st Shortest Path problem, the Single Source Shortest Path (SSSP) problem, the All Pairs Shortest Path (APSP) problem.
 The FordDantzig generic SSSP algorithm that works even when edge weights are negative, provided no negative cycles are present.
Readings: Section 7.4 "Huffman Codes" and Sections 21.1 through 21.4 on SSSP algorithms from Prof. Jeff Erickson's lecture notes.

Week 6: 2/202/24
Topics:
 Exam 1 review and Exam 1.
 The Minimum Length PrefixFree Binary Encoding problem and Huffman's greedy algorithm to solve it.
 Examples of prefixfree binary encodings and their connection to binary encoding trees.
Readings: Section 7.4 "Huffman Codes" from Prof. Jeff Erickson's lecture notes.

Week 5: 2/132/17
Topics:
 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.
Readings: Section 7.2 "Scheduling Classes" (on the Interval Scheduling problem)
from Prof. Jeff Erickson's lecture notes.

Week 4: 2/62/10
Topics:
 A 2approximation 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
algorithm.
Readings: A wellwritten blog post on the 2approximation to MVC, Section 35.1 from textbook by Cormen, Leiserson, Rivest, and Stein, posted on ICON.
Week 3: 1/302/3
Topics:
 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.
Readings: None

Week 2: 1/231/27
Topics:
 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
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
KleinbergTardos textbook, posted on ICON.

Week 1: 1/161/20
Topics:
 Introduction to the course
 The stable marriage problem and the GaleShapley (GS) algorithm.
 Proof of correctness of the GS algorithm.
 Worst case example for the GS algorithm
Readings: Chapter 1 from the KleinbergTardos textbook, posted on ICON,
Review of common classes of running times: Function Review Handout.
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 5page "information for the public" from the Royal Swedish Academy
of Sciences on the work of Shapley and Roth.