9:30-10:45 TTh Room 110 MLH (MacLean Hall)
Sriram V. Pemmaraju
101G MLH, email@example.com, 319-353-2956
Office Hours: 1:00-2:00 M, 10:30-11:30 W, 2:00-3:00 F (and by appointment)
Course website: http://www.cs.uiowa.edu/~sriram/3330/fall15/
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 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 aim of this course
deepen your algorithmic intuition and 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.
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.
Information about TAs,
Quizzes, Projects, and Exams,
The TA for the course is "Aaron" Shiyao Wang, a computer science PhD student. His e-mail address is: firstname.lastname@example.org. His office is 201N in MLH.
- 12/24 Final Grades.
- 12/8 Here is information on the Final Exam (Mon, Dec 14, 7:30am-9:30am).
- 12/8 The final exam is on Monday, 12/14 from 7:30 am to 9:30 am in W128 CB (Chemistry Building).
- 12/4 Tentative Grades. Please report any errors.
- 10/24 Here is information on Exam 2 (Thursday, Oct 29, 6:30pm-8:30pm).
- 10/15 Midterm 2 is scheduled for Oct 29th, 6:30 pm to 8:30 pm in 101 BBE.
- 10/15 I will be out of town on Friday, 10/16 and will not have office hours.
- 9/29 I will be out of the country next week for a conference; my PhD
student James Hegeman
will lecture (on Tue Oct 6th and Thur Oct 8th) on my behalf.
- 9/22 If you have any questions about the grading of HW1, please see the TA Shiyao Wang during his office hours (Tuesdays, Thursdays. 5pm-6:30pm, 201N MLH).
- 9/21 Here is information on Exam 1 (Thursday, Sept 24, 6:30pm-8:30pm).
- 8/31 TA Office Hours: Shiyao Wang will have office hours in 201N, MLH from 5pm-6:30pm on Tuesdays
- 8/28 Midterm 1 is scheduled for Thursday, Sept 24th from 6:30 pm to 8:30 pm in 101 BBE (Biology Building East).
Midterm 2 is scheduled for Thursday, October 29th from 6:30 pm to 8:30 pm in 101 BBE.
Week 1: 8/24-8/28
Readings: Chapter 1 of textbook.
- Introduction to the course
- The stable marriage problem and the Gale-Shapley (GS) algorithm.
- Proof of correctness of the GS algorithm.
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.
Week 2: 8/31-9/4
Readings: Sections 2.2 and 2.3 of textbook.
- Implementation of the GS algorithm, choice of efficient data structures.
- Framework for running time analysis of algorithms: (a) notion of input size,
(b) notion of basic operations, (c) asymptotic order of growth: definitions of Big Oh, Omega, Theta.
Week 3: 9/7-9/11
Readings: All of Chapter 2 of textbook.
- Properties of asymptotic order of growth notation
- Common examples of running times.
Links: Here is a cleaner version of the picture on the board (from the class on 9/10)
showing the "landscape" of representative running times.
Week 4: 9/14-9/18
Readings: Section 3.1 on basic applications and definitions related to graphs.
- Algorithms that do not always return the correct answer: an introduction to randomized
algorithms and approximation algorithms.
- Illustration of Las Vegas and Monte Carlo algorithms via the balanced partition problem.
- The notion of approximation factor for maximization and minimization problems.
Week 5: 9/21-9/25
- The minimum vertex cover (MVC) problem. Examples showing that the greedy
algorithm can do quite poorly.
- A 2-approximation algorithm for MVC and proof that the algorithm
indeed produces a 2-approximation.
- Exam 1 review
Week 6: 9/28-10/2
- Introduction to graph algorithms.
- Graph representations: adjacency list representation and adjacency
- Graph traversals: breadth-first search; properties of BFS and BFS trees.
- Implementation of BFS in O(m + n) time.
Week 7: 10/5-10/9
- Depth-first search (DFS): using stacks and via recursion.
- Applications of graph traversals: linear-time algorothms for
finding all connected components and 2-approximation for MVC.
Week 8: 10/12-10/16
- Directed graphs; BFS and DFS on directed graphs.
- The strongly connected components problem.
- Directed Acyclic Graphs (DAGs) and the topological sorting problem;
an O(m + n)-time algorithm for topological sort.
- Introduction to greedy algorithms: the interval scheduling problem.
Week 9: 10/19-10/23
- The "Earliest Finish Time First" greedy algorithm for the interval scheduling problem.
- Proof of correctness of the greedy algorithm using the "greedy stays ahead" approach.
- Construction of counterexamples for many other natural greedy algorithms.
- The problem of scheduling to minimize lateness.
- A greedy algorithm for this problem and proof of its correctness using the "exchange" argument.
Week 10: 10/26-10/30
- Introduction to Shortest path problems.
- Dijkstra's shortest path algorithm for the Single Source Shortest Path (SSSP) problem.
- Implementation of Dijkstra's algorithm in O((m + n) log n) time using the min-heap data structure.
- Exam 2 Review.
Week 11: 11/2-11/6
- Proof of correctness of Dijkstra's algorithm.
- The Minimum Spanning Tree (MST) problem.
- Prim's algorithm and Kruskal's algorithm for MST
- Implementation of Prim's algorithm in O((m+n) log n)
Week 12: 11/9-11/13
- Implementation of Kruskal's algorithm using the Disjoint Set Union-Find data structure
- Example of amortized analysis: Find in worst case O(1) time, Union in O(log n) amortized time.
- An alternate implementation of the Disjoint Set Union-Find data structure with Find in
worst case O(log n) time and Union in worst case O(1) time.
- Introduction to the Divide-and-conquer paradigm.
- Writing the recurrence for the running time of Merge Sort.