22C:31 Algorithms
10:55-12:10 TTh, Room 218 PH
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)
Lincoln Lourens Office hours: Friday 1:30-2:30 Office: B20J, MLH Phone: 515 975 4539 (cell) E-mail: lincoln-lourens@uiowa.edu
Wed 3:30-4:30
Clifton J. (CJ) Palmer Office hours: Mon: 1:30-2:30 Office: B20J, MLH Phone: E-mail: clifton-palmer@uiowa.edu
Tues: 2:15-3:15
- 5/8 MWT samples.
This contains two examples of input and output for the Minimum Weight
Triangulation problem on convex polygons. You can use these examples
to test your code.
- 5/7 Final Exam Information.
- 4/27 Programming Assignment. Due via
ICON dropbox on 5/10.
- 4/26 Homework 6. Due in class on
Thursday, May 6th.
- 4/9 Homework 5. Due in class on
Thursday, April 22th.
- 4/1 Exam 2. Due via ICON dropbox by
5:30 pm, Friday, April 2nd.
- 3/26 Homework 4. Due in class on
Thursday, April 8th.
- 3/4 Homework 3. Due in class on
Tuesday, March 23rd.
- 2/18 Exam 1. Due via ICON dropbox by
5:30 pm, Friday, Feb 19th.
- 2/10 Homework 2. Due in class on Tuesday, Feb 23rd.
- 1/27 Homework 1. Due in class on Tuesday, Feb 9th.
- 5/20 Final Grades
- 4/15 Handed out solutions to HW4.
- 3/30 Exam 2 will be posted on Thursday, 4/1, 5:00 pm.
It is due back via an ICON dropbox by 5:00 pm on Friday, 4/2.
- 3/30 HW3 solutions handed out.
- 3/22 HW3 due date moved to Thursday, March 25th. Also, only the
first 6 problems will be graded.
- 2/23 Handed out HW2 solutions in class.
- 2/17 Exam 1 will be posted by 5:30 pm on Thursday, 2/17.
It is due back via a 22C:31 ICON dropbox by 5:30 pm on Friday, 2/18.
Here are more details.
- 2/10 Handed out HW1 solutions in class.
- 2/10 We now have another Teaching Assistant (TA) for the course:
Clifton J. (CJ) Palmer. Details about Clifton are posted above.
- 2/2 We now have a Teaching Assistant (TA) for the course: Lincoln Lourens. Details about Lincoln are posted above.
- 1/27 Homework 1 has been posted. Due in class on Tuesday, Feb 9th.
- 1/19 I have updated the syllabus document with date/time for the
final exam.
- Week 13: 4/19-4/23
How can knapsack and subset sum have dynamic programming solutions
even when they are said to be intractable? Introduction to
pseudo-polynomial time algorithms.
Final example of dynamic programming: The Bellman-Ford Algorithm.
Introduction to NP-completeness.
- Week 12: 4/12-4/16
Finished up the longest common subsequence problem.
The knapsack problem and the subset sum problem.
Dynamic programming solution to the subset sum problem.
- Week 11: 4/5-4/9
Two more examples of 1-dimensional dynamic programming algorithms:
finding a longest path in an ordered graph, pretty printing.
Examples of 2-dimensional dynamic programming: matrix-chain multiplication
and longest common subsequence.
- Week 10: 3/29-4/2
Finding a local minima via divide-and-conquer.
Introduction to dynamic programming.
Why recursion can be costly. Memoization as a solution. The example of
computing Fibonacci numbers. Our first example: weighted interval scheduling.
- Week 9: 3/22-3/26
More examples of the divide-and-conquer paradigm.
Closest point pair problem, Strassen matrix multiplication algorithm,
and computing the local minima in a matrix.
Reading: Sections 5.4 and 6.1
- Week 8: 3/8-3/12
Solving recurrence relations using the recursion tree method and
by use the substitution method.
Proof that merge sort runs in O(n log n) time.
A divide-and-conquer algorithm for counting inversions.
A divide-and-conquer algorithm for closest point pair.
Reading: Sections 5.3 and 5.4.
- Week 7: 3/1-3/5
The Union-Find data structure. An implementation that has good average running time.
Efficient implementation of Kruskal's algorithm using the Union-Find data structure.
The divide-and-conquer paradigm.
MergeSort as a first example of a divide-and-conquer algorithm.
Reading: Sections 5.1 and 5.2.
- Week 6: 2/22-2/26
Exam 1 review; homework 2 review. Greedy algorithms for minimum spanning tree.
Cut Theorem. Correctness of Prim's and Kruskal's algorithm derived from the Cut Theorem.
Reading: Sections 4.4 and 4.5.
- Week 5: 2/15-2/19
Greedy algorithm for the problem of scheduling to minimize lateness.
Proof via the "exchange argument."
The shortest path problem and the minimum spanning tree problem.
Dijkstra's algorithm for the shortest path problem. Proof of correctness
and running time analysis.
Reading: Sections 4.4 and 4.5.
- Week 4: 2/8-2/12
The interval scheduling problem. Proof that greedy "stays ahead."
The interval coloring problem. Proof that greedy matches lower bound.
Reading: Sections 4.1 and 4.2.
- Week 3: 2/1-2/5
More examples of the use of asymptotic notation.
Logarithmic functions vs Polynomial functions vs Exponential functions.
Common running times of algorithms.
Introduction to greedy algorithms. The interval scheduling problem.
Reading: All of Chapter 2 and Section 4.1.
- Week 2: 1/25-1/29
Analyzing the running time of algorithms: basic operations, worst case analysis.
Example 1: showing that InsertionSort runs in quadratic time.
Example 2: showing that BinarySearch runs in logarithmic time.
Asymptotic notation: Big Oh, Big Omega, and Big Theta.
Reading: Sections 2.1, 2.2, and 2.4.
- Week 1: 1/18-1/22 Five representative problems:
interval scheduling,
weighted interval scheduling,
closest point pair,
traveling salesperson problem,
maximum independent set
Constructing counterexamples for greedy algorithms.
Reading: All of Chapter 1, including the material on the Stable Marriage problem.