CS 3330: Algorithms
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/13] Instructor and TA office hours are announced.
[6/14] Homework 1 is posted, due in class on Wed, June 20.
[6/20] Homework 2 is posted, due in class on Wed, June 27.
[6/25] Homework 1 solutions are posted in ICON.
[6/27] Homework 3 is posted, due in class on Thu, July 5.
[7/2] Homework 2 solutions are posted in ICON.
[7/10] Homework 3 solutions are posted in ICON.
[7/12] Homework 4 is posted, due in class on Wed, July 18.
[7/16] Midterm exam solutions are posted in ICON.
[7/18] Homework 5 is posted, due by 11:59 pm on Wed, July 25 (ICON submission).
[7/24] Homework 4 solutions are posted in ICON.
[7/25] Homework 5 deadline is extended to 11:59 pm on Thu, July 26.
[7/26] Homework 6 is posted, due in class on Wed, Aug 1.
[8/1] Solutions 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/1] Homework 5 solutions are posted in ICON.
[8/6] Final exam solutions are posted in ICON.
[8/7] Final 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.
Lecture slides: Introduction GS-Algorithm-Demo Asympotic_Analysis
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
Lecture slides: Graph_Algorithms Topological_ordering_demo
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
Lecture slides: Greedy_algorithms Interval_Scheduling_Demo Dijkstra_Demo
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
Lecture slides: Greedy_algorithms MST_Demo
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
Lecture slides: Divide_and_Conquer Mergesort_Demo Counting_Inversions_Demo
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
Lecture slides: Divide_and_Conquer Dynamic_Programming
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
Lecture slides: Dynamic_Programming Network_Flow FordFulkerson_Demo
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
Lecture slides: Network_Flow NP-Completeness