CS:3330 Algorithms, Sections 0001, 0002
Spring 2017

Instructors:
Sriram V. Pemmaraju (Section 0001)
Office: 101G MLH, sriram-pemmaraju@uiowa.edu, 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, shreyas-pai@uiowa.edu
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.

Syllabus document, Information about TAs, Announcements, Quizzes, Projects, and Exams, Weekly Topics, Online Resources

Information about TAs

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.

Homeworks and Exams

• Review of common classes of running times: Function Review Handout.
• Homework 1. Due: 1/26 (in class).
• Practice for Quiz 1. Use to prepare for in-class Quiz 1 on Tue, 1/24.
• Quiz 1 and solutions (all 4 versions).
• Homework 2. Due: 2/2 (in class). Homework 2 Solution
• Homework 3. Due: 2/9 (in class). Homework 3 Solution
• Homework 4. Due: 2/21 (in class and on ICON). Readings for Homework 4: Pseudocode and analysis of greedy algorithm for minimum dominating set, Chapter 3 on Graphs from the Kleinberg and Tardos textbook (up till and including Section 3.3) (see posted pdf on ICON).
• Practice problems for Exam 1 on approximation algorithms.
• Homework 5. Due: 3/2 (at the start of class).
• Homework 6. Due: 3/9 (at the start of class). Homework 6 Solution.
• Exam 1.
• Homework 7. Due: 3/30 (at the start of class). Homework 7 Solution.
• Homework 8. Due: 4/18 (at the start of class and on ICON). Data file: miles.dat.
• Exam 2, Exam 2 Solution.
• Homework 9. Due: 4/27 (at the start of class). Homework 9 Solution.
• Homework 10. Due: 5/4 (at the start of class). Homework 10 Solution.

• 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.

Weekly Topics

• Week 14: 4/24-4/28
  Topics:
  • 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.
  Readings: Section 5.2 on the Longest Increasing Subsequence (LIS) from Section 5.1 in Prof. Jeff Erickson's lecture notes.

• Week 13: 4/17-4/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/10-4/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/3-4/7
  Topics:
  • 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.
  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/27-3/31
  Topics:
  • 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.
  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

• Week 9: 3/20-3/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 run-time analysis
  • Proofs of the "Blue Rule" and "Red Rule".
  • Kruskal's algorithms and the Disjoint Set Union-Find 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/6-3/10
  Topics:
  • 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.
  Readings: Sections 21.1 through 21.4 on SSSP algorithms from Prof. Jeff Erickson's lecture notes.

• Week 7: 2/27-3/3
  Topics:
  • 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.
  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/20-2/24
  Topics:
  • 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.
  Readings: Section 7.4 "Huffman Codes" from Prof. Jeff Erickson's lecture notes.

• Week 5: 2/13-2/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/6-2/10
  Topics:
  • 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 algorithm.
  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.

  Week 3: 1/30-2/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/23-1/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 Kleinberg-Tardos textbook, posted on ICON.

• Week 1: 1/16-1/20
  Topics:
  • 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
  Readings: Chapter 1 from the Kleinberg-Tardos 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 5-page "information for the public" from the Royal Swedish Academy of Sciences on the work of Shapley and Roth.