CS:3330 Algorithms
Fall 2015

Instructor:
Sriram V. Pemmaraju
101G MLH, sriram-pemmaraju@uiowa.edu, 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.

Syllabus document, Information about TAs, Announcements, Quizzes, Projects, and Exams, Weekly Topics, Online Resources

Information about TAs

Homeworks and Exams

• Homework 1. Due in class on Tue, Sept 15th.
• Homework 2. Due in class on Tue, Sept 29th.
• Homework 3. Due in class on Tue, Oct 20th. Input file: graph.txt. Solution.
• Homework 4. Due in class on Tue, Nov 3rd.
• Practice Problems on Dijkstra's Shortest Path Algorithm.
• Exam 2 and solution.
• Homework 5. Due in class on Tue, Dec 1st.
• Homework 6. Due in class on Thu, Dec 10th.
• miniExam1.pdf, miniExam2.pdf. Due before class on Tuesday, Dec 8th.
• Practice Problems on NP-completeness.

Announcements

• 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 and Thursdays.
• 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.

Weekly Topics

• Week 1: 8/24-8/28
  Topics:
  • Introduction to the course
  • The stable marriage problem and the Gale-Shapley (GS) algorithm.
  • Proof of correctness of the GS algorithm.
  Readings: Chapter 1 of textbook.
  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
  Topics:
  • 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.
  Readings: Sections 2.2 and 2.3 of textbook.

• Week 3: 9/7-9/11
  Topics:
  • Properties of asymptotic order of growth notation
  • Common examples of running times.
  Readings: All of Chapter 2 of textbook.
  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
  Topics:
  • 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.
  Readings: Section 3.1 on basic applications and definitions related to graphs.
  

• Week 5: 9/21-9/25
  Topics:
  • 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
  Topics:
  • Introduction to graph algorithms.
  • Graph representations: adjacency list representation and adjacency matric representation.
  • 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
  Topics:
  • 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
  Topics:
  • 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
  Topics:
  • 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
  Topics:
  • 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
  Topics:
  • 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
  Topics:
  • 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.