22C:31 Algorithms
1:05-2:20 TTh, Room 109 EPB
Instructor:
Sriram V. Pemmaraju
101G MLH, sriram@cs.uiowa.edu, 319-353-2956
Office Hours: MW 9-10:30 am
This course deals with the design and analysis of algorithms.
We will study algorithm design techniques such as
greedy method, dynamic programming,
divide-and-conquer, and randomization and see many examples
of each of these techniques in action.
We will study algorithm analysis techniques such as asymptotic analysis,
recurrence relations, and charging schemes.
Towards the end of the course, we will also study the intractability
of problems, specifically the theory of NP-completeness.
Time permitting, we will study approximation algorithms as a
way of getting around the intractability of some problems.
Syllabus document,
Information about TAs,
Announcements,
Quizzes, Projects, and Exams,
Weekly Topics,
Online Resources
(From xkcd)
There is one Teaching Assistant (TA) assigned to this course,
Lu Bi, a Ph.D. student in computer science. She will be the primary
grader for the course. Her contact details and office hours are
as follows:
office e-mail office phone office hours
201C MLH lu-bi@uiowa.edu 319 353 2546 M 3:30-5:00, F 10-11:30
- 8/31: Posted Homework 1. Due on Tuesday, 9/15, in class.
- 9/15: Posted Homework 2. Due on Tuesday, 9/29, in class.
- 9/23: Posted Solution to Homework 1.
- 9/24: Posted Exam 1. Due on Friday, 9/25, 5 pm, via the ICON dropbox.
- 10/6: Posted Homework 3. Due on Tuesday, 10/20, in class.
- 10/20: Posted Solution to Homework 2.
- 10/22: For Homework 4, solve Problems 1-4 in Chapter 6, pages 312-316. This homework is shorter than usual since a programming assignment is on its
way. Homework is due on Tuesday, Nov 3rd.
- 10/29: Posted Solution to Problem 7 in Homework 3.
- 10/29: Posted Exam 2. Due on Friday, 10/30, 5 pm, via the ICON dropbox.
- 11/5: Posted Programming Project. Due on Friday, 12/11, midnight, via the ICON dropbox.
- 11/9: Posted Homework 5. Due on Thursday, 11/19.
- 11/25: Posted Additional instructions for the programming project.
- 12/2: Posted Homework 6. Due on
Friday, Dec 18th, at final exam time.
- 8/25: Read Chapter 1, including the stuff on stable marriage.
- 8/27: The teaching assistant (TA) for this class is Lu Bi.
Her office is 201C MLH, e-mail: lu-bi@uiowa.edu, office
phone no. 319 353 2546, office hours: M 3:30-5:00, F 10-11:30.
- 8/27: Read Sections 2.1 and 2.2.
- 8/31: Posted Homework 1.
- 8/31: Read all of Chapter 2.
- 9/03: Read Chapter 3, if you need a refresher on basic graph
algorithms.
- 9/03: Read Sections 4.1, 4.2, and 4.3.
- 9/15: Read Sections 4.4 (shortest paths), 4.5 (min. spanning
tree), 4.6 (union-find data structure).
- 9/15: Posted Homework 2.
- 9/20: Exam 1 will be posted 5 pm on Th, 9/24 and will be due back at 5 pm on Fri 9/25.
Here are more details.
- 9/22: ICON dropbox is now available for submitting Exam 1.
The dropbox will close at 5 pm on Fri 9/25.
- 9/23: Solution to Homework 1 has been posted. It might be helpful to review
this for Exam 1.
- 10/6: Posted Homework 3.
- 10/6: Read Section 5.4 (closest point-pair) and Section 5.5
(integer multiplication).
- 10/20: Read Sections 6.1 to 6.4.
- 10/27: Read Sections 6.5 on dynamic programming for discovering
RNA secondary structure.
- 11/3: Due date for HW 4 is postponed to Thursday, 11/3.
- 11/5: Posted Programming Project. Due on Friday, 12/11, midnight, via the ICON dropbox.
- 11/9: Posted Homework 5. Due on Thursday, 11/19.
- 11/25: Posted Additional instructions for the programming project.
- 12/10: Posted Information for the final. Final exam is on
Dec 18th, noon to 2 pm, in classroom.
- 12/10: Additional office hours: 10-11 Fri (12/11), Mon (12/14),
Wed (12/16), and Fri (12/18).
- 12/10: HW6 has been truncated: you only have to turn in the
solutions to the first 5 problems. For Problem 5 (i.e., Problem 3 in Chapter 8)
use a reduction from the decision version of the minimum set cover problem.
- Week 1: 8/25-8/29 Five representative problems:
interval scheduling,
longest common subsequence,
closest point pair,
maximum independent set,
k-center problem (Chapter 1).
Introduction to worst case, asymptotic analysis of running time (Chapter 2).
- Week 2: 8/31-9/4 Asymptotic analysis of running time,
Big Oh, Big Theta, and Big Omega notation, properties of asymptotic
growth rates, common growth rates (logarithmic, polynomial, exponential),
polynomial-time as a definition of efficiency, common running times,
implementing an optimal (greedy) interval scheduling algorithm in O(n log n) time.
- Week 3: 9/7-9/11 Greedy algorithms, proofs of correctness, etc.
for some simple scheduling problems and optimal caching.
- Week 4: 9/14-9/18 Greedy algorithms for computing shortest
paths, minimum spanning trees, proofs of correctness.
- Week 5: 9/21-9/25
Efficient implementation of Dijkstra's algorithm using priority queues
an efficient implementation of Kruskal's algorithm using the min-heap data structure.
Introduction to data compression and Huffman coding.
- Week 6: 9/2-10/2
The Huffman coding algorithm, proof of correctness.
The divide-and-conquer paradigm. Examples such as merge sort and quick sort.
Counting the number of inversions in O(n log n) time.
- Week 7: 10/5-10/9
Methods for solving recurrence relations. An O(n log n)
algorithm for the closest-point pair problem.
An O(n log n) algorithm for integer
multiplication.
- Week 8: 10/12-10/16
Wrapping up the integer multiplication algorithm.
Introduction to dynamic programming:
weighted interval scheduling.
- Week 9: 10/19-10/23
Examples of "1-dimensional" dynamic programming:
weighted interval scheduling and
segmented least squares.
An example of "2-dimensional" dynamic programming: subset sum.
- Week 10: 10/26-10/30
More examples of "2-dimensional" dynamic programming:
knapsack,
matrix-chain multiplication,
RNA Secondary structure, etc.
- Week 11: 11/2-11/6
One more example of 2-dimensional dynamic programming:
longest common subsequence problem.
Revisiting the shortest path problem: beyond Dijkstra's shortest path
algorithms.
Dynamic programming for shortest path problems.
The Bellman-Ford algorithm for shortest-path problems
on graphs with negative edge weights.
- Week 12: 11/7-11/11
The Floyd-Warshall algorithm for the all-pairs shortest
path problem.
A "big picture" view of intractability, the classes P and NP,
NP-hardness, NP-completeness, example problems that are NP-complete.
- Week 13: 11/14-11/18
Four example problems (Maximum Independent Set,
Minimum Vertex Cover, SAT, and Minimum Set Cover).
Optimization problems versus decision problems.
Efficiently solving a problem versus efficiently certifying it.
The class NP. Showing that MIS, MVC, SAT, and MSC are all in NP.
- Week 14: 11/30-12/4
The class NP revisited. How do we show that PRIMES is in NP?
Polynomial-time reductions. MIS -> MVC, MVC -> MIS, SAT -> MIS, etc.
Definitions of the classes NP-hard, NP-complete. The P versus NP question.
- Week 15: 12/7-12/11 CIRCUITSAT, The Cook-Levin Theorem (CIRCUITSAT
is NP-complete), CIRCUITSAT -> SAT (and hence SAT is NP-complete).