Semester: Summer 2018
Instructor: Sikder Huq, 101A MLH, sikderrezwanul-huq AT uiowa.edu
Class meeting time: MTWTh 9:30-10:45 AM in 205 MLH
Office Hours: MT 11AM - 12:30PM in 101A MLH and by appointment.
Teaching Assistant: David McDermott, david-mcdermott-1 AT uiowa.edu
TA Office Hours: TW 12:30-1:30PM in 301 MLH
Textbook
Algorithm Design
Klienberg and Tardos
As a reference, we may also use lecture notes from Jeff Erickson.
Course objectives
Upon successful completion of this course, students are expected to:
- learn how to abstract clearly stated algorithmic problems from messy, real world problems
- learn different techniques to solve algorithmic problems
- be able to identify algorithm design technique appropriate for the context
- learn how to mathematically analyze algorithms and quantify their merits
- develop algorithmic intuition (i.e. feel for the difficulty of the problems) and ability to effectively communicate algorithms
The course is expected to cover the following topics:
- Introduction
- Asymptotic Order of Growth
- Basic Graph Algorithms
- Greedy Algorithms and Analysis
- Recursive Thinking: Divide-and-Conquer
- Recursive Thinking: Dynamic Programming
- Network Flow and Applications
- Randomized Algorithms
- NP-completeness
Grading
Final grade will be determined by the following components:
Homework assignments (30%): There will be approximately six homework assignments during the course. Some of the homework problems will be based on programming.
Exams (65%): There will be one mid-term and one final exam. The mid-term exam will cover 30% and final exam will cover 35% of the total grade.
Participation (5%): You are expected to actively participate in the class discussions. There might be be in-class exercises and short quizzes, and some of them will be graded.
Grades will be curved. CLAS expects senior level undergraduate classes to have the following approximate distribution: 22% A, 38% B, 36% C, 3% D and 1% F.
Late policy
You may use a quota of three days for the entire semester for late submissions. When you submit an assignment X days late, your quota gets decreased by X irrevocably. You can only be late by an integer number of days. For example, if you submit 5 hours after the deadline, your quota is depleted by one day. Once you use up your quota of three days, any assignment submitted late will not be accepted and you will get 0 points for that assignment.
Exams
- The midterm exam will take place in class on Monday, July 9. Find more information about the midterm exam here.
- The final exam will take place in class on Thursday, Aug 2. Details of the final exam can be found here.
Announcements and homeworks
- 6/13Instructor and TA office hours are announced.
- 6/14Homework 1 is posted, due in class on Wed, June 20.
- 6/20Homework 2 is posted, due in class on Wed, June 27.
- 6/25Homework 1 solutions are posted in ICON.
- 6/27Homework 3 is posted, due in class on Thu, July 5.
- 7/2Homework 2 solutions are posted in ICON.
- 7/10Homework 3 solutions are posted in ICON.
- 7/12Homework 4 is posted, due in class on Wed, July 18.
- 7/16Midterm exam solutions are posted in ICON.
- 7/18Homework 5 is posted, due by 11:59 pm on Wed, July 25 (ICON submission).
- 7/24Homework 4 solutions are posted in ICON.
- 7/25Homework 5 deadline is extended to 11:59 pm on Thu, July 26.
- 7/26Homework 6 is posted, due in class on Wed, Aug 1.
- 8/1Solutions to the problems 5,8,16, and 28 from chapter 7 (for practice) are posted in ICON. Try to solve these problems without looking at the solutions first.
- 8/1Homework 5 solutions are posted in ICON.
- 8/6Final exam solutions are posted in ICON.
- 8/7Final exam solutions are updated in ICON.
Lecture summaries
Week 1 6/11 - 6/14
Topics:
- Course Introduction
- The stable matching problem and the Gale-Shapley (GS) algorithm
- Proof of correctness of the GS algorithm
- Variations of the stable matching problem
- Proving termination of an algorithm
- five representative problems
- Asymptotic order of growth: definition of Big Oh, Omega, Theta
- Properties of asymptotic order of growth notation
- common example of running times
Links: (taken from Prof. Pemmaraju's algorithms course page)
- 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.
- A picture showing the "landscape" of representative running times.
Week 2 6/18 - 6/21
Topics:
- Introduction to graph algorithms
- Graph representations: adjacency list representation and adjacency matrix representation
- Graph traversals: breadth-first search; properties of BFS and BFS trees
- Depth-first search (DFS)
- Applications of graph traversals: testing bipartiteness and finding all connected components
- Directed graphs
- Exercises related to BSF and DSF
- The strongly connected components problem
- Directed Acyclic Graphs (DAGs) and the topological sorting problem; an O(m + n)-time algorithm for topological sort
Week 3 6/25 - 6/28
Topics:
- A greedy algorithm for the interval scheduling problem
- A greedy algorithm for the truck driver's problem
- A greedy algorithm for the interval partitioning problem
- Three (greedy stays ahead, structural, and exchange argument) greedy analysis strategies
- A greedy algorithm for the coin-chaining problem
- A greedy algorithm for the scheduling to minimizing lateness problem
- Different greedy design exercises
- Dijkstra's shortest path algorithm, analysis, and implementation
- Introduction to the Minimum Spanning Tree (MST) problem
- Quick Introduction to Kruskal's algorithm and Prim's algorithm for MST
Week 4 7/2 - 7/5
Topics:
- Revisiting the implementation of Dijkstra's algorithm using priority queue
- Kruskal's and Prim's algorithms for the MST problem
- Cycle and cut properties of MST
- Proof of correctness and implementation of Kruskal's algorithm
- Proof of correctness and implementation of Prim's algorithm
- Solving various problems
Week 5 7/9 - 7/12
Topics:
- Introduction to the Divide and Conquer paradigm
- Mergesort algorithm and analysis
- Different methods for solving recurrence relations
- The Counting Inversion problem with an O(n log n) solution
- The Closest Pair of Points problem with an O(n log n) solution
- Karatsuba Multiplication for the Integer Multiplication problem
Week 6 7/16 - 7/19
Topics:
- Strassen's divide and conquer algorithm for matrix multiplication
- The master theorem for solving recurrence relations
- An O(n^2) divide and conquer algorithm for computing GCD of 2 n-bit positive intergers
- History of Dynamic Programming
- Introduction to Dynamic Programming using Fibonacci numbers
- The Weighted Interval Scheduling problem
- The Segmented Least Square Problem
- The Sequence Alignment Problem
- Solving various Dynamic Programming exercises
Week 7 7/23 - 7/26
Topics:
- The knapsack Problem
- Exercise: Longest Palindromic Sub-sequence problem and Smallest Palindromic Partitioning problem
- The RNA Secondary Structure problem
- Bellman-Ford algorithm for the shortest path problem
- Introduction to the max-flow min-cut problem
- The Ford-Fulkerson algorithm
Week 8 7/30 - 8/1
Topics:
- Capacity scaling for choosing good augmenting paths
- Network flow applications: bipartite matching, edge disjoint paths, network connectivity, baseball elimination
- Polynomial-time reductions
- Definition of P, NP, NP-Completeness and EXP