CS:5350 Design and Analysis of Algorithms
Spring 2016
9:30-10:45 TTh Room 71 SH (Schaeffer Hall)
Instructor:
Sriram V. Pemmaraju
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)
Course website: http://www.cs.uiowa.edu/~sriram/5350/spring16/
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 "algorithmic thinking" is viewed as the greatest contribution of the field of computer
science to everyday 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.
This course is on the design and analysis of algorithms (as indicated by the
title!) and the difficulty (tractability) of problems from an algorithmic
point of view.
In this course, we will practice the precise statement of various computational problems,
study different algorithmic strategies to solve them -- either exactly or with some controlled
error, learn to state algorithms precisely, 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.
The increasing need to process enormous volumes of data has led to the development of algorithms
in alternate computational models (e.g., models that explicitly recognize the fact that all the input data may
not fit into main memory). We will understand the basic features of
some of these models and design algorithms within these models for some simple problems.
We will organize the course in terms of the following topics:
- Divide-and-Conquer
- Dynamic Programming
- Flows, cuts, and matchings
- Randomized Algorithms
- Computational Intractability
- Models of Computations and Algorithms for "Big Data"
Syllabus document,
Information about TAs,
Announcements,
Quizzes, Projects, and Exams,
Weekly Topics,
Online Resources
The TA for the course is James Hegeman, a 5th year computer science PhD student. His e-mail address is: james-hegeman@uiowa.edu.
Office Hours: Tue 2pm-3pm, Wed 3pm-4pm.
Homework 1. Due on Thu, Jan 28 in class.
Homework 2. Due on Thu, Feb 4 in class.
Homework 3. Due on Thu, Feb 11 in class.
Homework 4. Due on Thu, Feb 25 in class.
Homework 5. Due on Thu, March 3 at exam time.
Homework 6. Due on Thu, March 24 in class.
Midterm Exam.
Homework 7. Due on Thu, March 31 in class.
Homework 8. Due on Thu, April 7 in class.
Homework 9. Due on Tue, April 26 in class.
Homework 10. Due on Thu, May 5 in class.
Midterm Retake Exam.
- The final exam is on Monday, May 9th 7:30am to 9:30am, in 3505 SC. Here are a few details about the final.
- Midterm Exam Retake will be on Sunday, April 17, 6:30 pm to 8:30 pm in S107 PBB.
- I will not have office hours Fri, Feb 26 through Fri, March 4. Our TA, James Hegeman will have
one additional office hour during the week of Feb 29th, before the exam on March 3rd. That announcement
is coming soon.
- There will be no class on Thursday, March 3rd due to the midterm in the evening. Instead I will
hold office hours during class time: 9:30 am to 10:45 am in my office (101G MLH).
- Information about the midterm exam.
- Midterm is on Thursday, March 3rd, 2016 from 6:30 pm to 8:30 pm in 125 Trowbridge Hall.
- The TA for the course, James Hegeman will have office hours on Tue 2 pm to 3 pm and
Wed 3 pm to 4 pm in 201N, MLH.
- My office hours are moved slightly on Mondays. They are now from 1:30 pm
to 2:30 pm (originally, they were from 1 pm to 2 pm on Mondays). The other
office hours remain the same.
-
Week 1: 1/18-1/22
Topics:
- Introduction to the divide-and-conquer paradigm.
- The power-mod problem. Designing an efficient divide-and-conquer
algorithm for the power-mod problem. Run-time analysis of the algorithm via recurrence relations.
Review of ideas such as input size, polynomial running time vs exponential running time, etc.
- The inversion counting problem.
Designing a merge-sort-based O(n log n) time algorithm for the inversion counting problem.
Correctness argument for the algorithm. Run-time analysis via recurrence relations.
Readings:
Lecture Notes on the power-mod problem,
Sections 1.1, 1.2, 1.4 (MergeSort), 1.9 (Exponentiation) from Chapter 1 (Simplify and Delegate)
from Prof. Jeff Erickson's notes,
Section 5.3
from the Kleinberg and Tardos textbook
on an algorithm for counting inversions.
-
Week 2: 1/25-1/29
Topics:
- Finishing up the discussion on the counting Inversions problem.
- The d-dimensional closest point pair problem. The simple 1-d case via
divide-and-conquer.
The more interesting 2-d case via divide-and-conquer.
- Dealing with higher dimensional
problems by projecting "sparse" problems to lower dimensional space.
Readings:
Lecture notes due to Subhash Suri on
a divide-and-conquer algorithm for the d-dimensional closest point pair
problem.
-
Week 3: 2/1-2/5
Topics:
- Finishing up the d-dimensional closest point pair problem.
- Algorithms for the selection problem. Preview of randomized algorithms.
A divide-and-conquer, deterministc linear-time algorithm for the selection problem.
Readings:
Section 1.7 from Prof. Jeff Erickson's notes
on a linear-time algorithm for median selection.
-
Week 4: 2/8-2/12
Topics:
- Introduction to the dynamic programming paradigm.
- Introductory example: Computing Fibonacci numbers efficiently. The idea of memoization.
- The weighted interval scheduling problem. Principles of designing dynamic programming algorithms.
Readings:
Section 5.1 from Prof. Jeff Erickson's notes
on computing Fibonacci number efficiently.
Section 6.1
from the Kleinberg and Tardos textbook
on a dynamic programming solution to the weighted interval scheduling problem.
-
Week 5: 2/15-2/19
Topics:
- The longest common subsequence (LCS) problem. An example of "2-dimensional" dynamic programming.
- Related problems: longest increasing subsequence, edit distance.
Readings:
Notes on the LCS problem by Prof. Charles
Leiserson,
Sections 5.2-5.5 from Prof. Jeff Erickson's notes
on the Longest Increasing Subsequence and Edit Distance problems and on principles of dynamic programming.
-
Week 6: 2/22-2/26
Topics:
- Dynamic programming on trees; a linear-time solution to the maximum independent set problem on
trees.
- Dynamic programming algorithms for the all pairs shortest path problem. The Floyd-Warshall
algorithm.
Readings: Section 5.9 from Prof. Jeff Erickson's notes and these notes on the Floyd-Warshall algorithm.
-
Week 7: 2/29-3/4
Topics:
- A divide-and-conquer-based technique to reduce memory usage of
dynamic programming algorithms.
- The midterm will be on Thursday, March 3rd in the evening. So no class
on March 3rd.
Readings: Section 6.1 from Prof. Jeff Erickson's notes.
-
Week 8: 3/7-3/11
Topics:
- Maximum Flows and Minimum Cuts. Definitions of flows, cuts,
and the maxflow-mincut theorem.
- Definitions of residual graphs, augmenting paths, and description of Ford-Fulkerson's augmenting path
algorithm.
Readings: Sections 23.1 through 23.5 from Prof. Jeff Erickson's notes.
- Week 9: 3/14-3/18
Topics:
- Proof of the maxflow-mincut theorem.
- Worst case running time examples of the Ford-Fulkerson algorithm.
- The Edmonds-Karp "fat pipe" heuristic and "short pipe" heuristics.
Readings: Sections 23.1 through 23.5 from Prof. Jeff Erickson's notes.
- Week 10: 3/21-3/25
Topics:
- Analysis of the running time of the "fat pipe" heuristic.
- Analysis of the running time of the Edmonds-Karp "short pipe" heuristic.
Readings: Sections 23.6 from Prof. Jeff Erickson's notes.
- Week 11: 3/28-4/1
Topics:
- Finishing up the analysis of Edmonds-Karp "short pipe" heuristic.
- Modeling assignment problems as network flow problems.
- Modeling baseball elimination as a network flow problem.
- Randomized algorithms: Introduction to Karger's min-cut algorithm.
Readings: Sections 24.1 through 24.5 (on applications of network flows) and Sections 14.1 and 14.2 (on randomized min-cut) from Prof. Jeff Erickson's notes.
- Week 12: 4/4-4/8
Topics:
- Analysis of Karger's min-cut algorithm. Probability amplification. Las Vegas Algorithms vs Monte Carlo Algorithms.
- The Nuts and Bolts problem.
- Connection to Randomized QuickSort.
Readings: Sections 14.1 and 14.2 (on randomized min-cut) and Sections 9.1-9.4 (on nuts and bolts) from Prof. Jeff Erickson's notes.
- Week 13: 4/11-4/15
Topics:
- Analysis of the worst case expected running time of the nuts and bolts algorithm. Probabilitics recurrences, linearity of expectation.
- Contention Resolution with no communication: a randomized solution.
Readings: Sections 9.1-9.7 (on nuts and bolts) from Prof. Jeff Erickson's notes.
Basic probability theory useful in analyzing randomized algorithms: Appendix C from the book "Introduction to Algorithms" by Cormel, Leiserson, Rivest, and Stein.
- Week 14: 4/18-4/22
Topics:
- Analysis of a contention resolution protocol with one shared resource.
- Contention resolution with as many shared resources as processes.
- Polynomial reductions: Maximum Independent Set to Minimum Vertex Cover, 3SAT to Maximum Independent Set.
Readings: Section on contention resolution from the Kleinberg and Tardos textbook.
Sections 8.1 and 8.2 on polynomial reductions from the Kleinberg and Tardos textbook.
- Week 15: 4/25-4/29
Topics:
- More polynomial reductions: Minimum Vertex Cover to Minimum Set Cover.
- Definitions of classes: NP, NP-hard, NP-complete.
- Cook-Levin Theorem: CircuitSAT is NP-complete. Polynomial reduction from CircuitSAT to 3SAT.
Readings: Sections 8.3 and 8.4 definitions on classes NP, NP-hard, NP-complete from the Kleinberg and Tardos textbook.