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