CS:3330 Algorithms, Section 0002
Spring 2018

Instructor:
Sriram V. Pemmaraju (Section 0002)
Office: 101G MLH, sriram-pemmaraju@uiowa.edu, 319-353-2956
Office Hours: 1:30-2:30 M, 10:30-11:30 W, 2:00-3:00 F (and by appointment)

Course website: http://www.cs.uiowa.edu/~sriram/3330/spring18/
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 algorithms are 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 aims of this course are to (i) deepen your algorithmic intuition, (ii) help you build a toolbox of algorithmic design and analysis techniques, and (iii) to develop 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.

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

Information about TAs

Quizzes, homeworks, exams and other handouts

• Review of common classes of running times: Function Review Handout.
• Homework 1. Due in class on Thu, 1/25.
• Quiz 1 Solution.
• Homework 2. Due in class on Thu, 2/1.
• Homework 3. Due in class on Thu, 2/8. primalityTest.txt.
• modPowerReference.java, modPowerReference.py. Solutions to Homework 1 programming problem; feel free to use in Homework 3.
• Homework 4. Due in class on Thu, 2/15. words.dat.
• Quiz 2 Solution.
• Homework 5. Due in class on Thu, 3/1.
• Homework 6. Due in class on Thu, 3/7.
• Homework 7. Due in class on Thu, 3/29.
• Homework 8. Data file: miles.dat. Due in class on Tue, 4/17.
• Quiz 3 Solution.
• Homework 9. Due in class on Thu, 4/26. Homework 9 Solution.
• Quiz 4 Solution.
• Homework 10. Due in class on Thu, 5/3.
• Exam 1 and Exam 1 Solution.
• Exam 2 and Exam 2 Solution.

• 5/4Information about the final: Final Exam Information.
• 4/30 The final is on Mon, 5/7 from 5:30 pm to 7:30 pm in W128 CB. More details on the final will be posted here soon.
• 4/30 I am out of town on Tue (5/1) and Wed (5/2). My PhD student Talal Riaz will substitute for me in Tuesday's class. My Wednesday office hours are cancelled and I will have makeup office hours on Thursday from 9 am to 10 am.
• 3/31 Here is more information on Exam 2: Exam 2 information. And here are a couple of practice problems on greedy algorithms.
• 3/29 I'll run a help session for Exam 2 from 8 pm to 9:15 pm on Sun, 4/1 in 118 MLH.
• 3/29 Exam 2 is on April 3rd, from 6:30 pm to 8:30 pm in W128 Chemistry Building.
• 2/22 The UICC is this weekend, starting with the keynote at 5:30 pm on Fri, 2/23. You'll receive extra credit for writing a coherent paragraph about an algorithmic issue that came up in any one of the 5 talks in the conference.
• 2/15 I'll run a help session for Exam 1 from 8 pm to 9:15 pm on Sun, 2/18 in 118 MLH.
• 2/15 Here is more information on Exam 1.
• 2/13 The University of Iowa Computing Conference is on Feb 23rd-24th. Register and attend the conference; you might even get extra credit points for CS:3330.
• 2/13 Mid-term exam 1 is scheduled for Tue Feb 20th, 6:30-8:30 pm, in Room: W128 CB (Chemistry Building). More details will be posted soon.
• 2/8: There will be an in-class quiz on Tue 2/13.
• 1/22: There will be an in-class quiz on Tue 1/23.
• 1/16: Every week, one of the two TAs (Wes or Junbin) will be available for office hours in 101N MLH at the following times: Mon 3:30-4:30, Tue 11 to noon, and Wed 1:30-2:30.
• 1/15: Welcome to CS:3330, Section 0002!

Weekly Topics

• Week 1: 1/15-1/19
  Topics:
  • Problem: Given positive integers n and p, (efficiently) compute the n-th Fibonacci number modulo p.
  • Introduction to running time analysis of algorithms.
  • The notion of basic computer operations, solving recurrences by the guess and prove by induction method.
  • The notion of input size and expressing running time as a function of input size.
  Readings: All of Chapter 0 and Section 1.1 from the textbook. Review of common classes of running times: Function Review Handout.
  

• Week 2: 1/22-1/26
  Topics:
  • Finishing up the design of an efficient algorithm for the modular Fibonacci number problem. This algorithm runs in time that is polynomial in the input size log(n)+log(p).
  • Introduction to asymptotic running time of algorithms: the "Big Oh," "Big Omega," and "Big Theta" notation.
  • Introduction to randomized algorithms: Las Vegas algorithms and Monte Carlo algorithms.
  • Using Fermat's Little Theorem to design an efficient, randomized primality testing algorithm, that is almost correct!
  Readings: Section 1.2 (on Modular Arithmetic), but you don't have to read Subsections 1.2.3, 1.2.4, or 1.2.5. Section 1.3 (on Primality Testing), but you don't have to read Subsection 1.3.1. Review of common classes of running times: Function Review Handout.

• Week 3: 1/29-2/2
  Topics:
  • Introduction to randomized algorithms: Las Vegas algorithms and Monte Carlo algorithms.
  • Using Fermat's Little Theorem to design an efficient, randomized primality testing algorithm, that is almost correct!
  • Introduction to Universal Hashing: designing randomized hash functions.
  Readings: Section 1.3 (on Primality Testing), but you don't have to read Subsection 1.3.1 and Section 1.5 (on Universal Hashing).

• Week 4: 2/5-2/9
  Topics:
  • Using number-theoretic ideas and randomization to design good hash functions.
  • Introduction to the divide-and-conquer paradigm. The merge sort example.
  • Writing the recurrence for the running time of merge sort. Solving the recurrence by unrolling. Visualizing the recurrence.
  • Quick sort: analyzing the worst case performance of quick rort.
  • Randomized Quick sort: a randomized Las Vegas algorithm that runs in expected O(n log n) time.
  Readings: Section 2.3 (on Merge Sort).

• Week 5: 2/12-2/16
  Topics:
  • Quick sort: analyzing the worst case performance of quick rort.
  • Randomized Quick sort: a randomized Las Vegas algorithm that runs in expected O(n log n) time
  • Randomized selection and median-finding.
  Readings: Section 2.4 (on finding medians), Section 2.2 (on recurrence relations), Section 2.1 (on integer multiplication)

• Week 6: 2/19-2/23
  Topics:
  • Review for Exam 1
  • Solving recurrences by using the Master Theorem.
  • Gauss' algorithm: solving integer multiplication is less than Theta(n^2) time
  Readings: Section 2.2 (on recurrence relations), Section 2.1 (on integer multiplication), Section 3.1 (introduction to graph algorithms and graph representation).

• Week 7: 2/26-3/2
  Topics:
  • Introduction to graph algorithms, representing graphs, input size for graph algorithms, sparse and dense graphs.
  • Depth-first search (DFS) of undirected and directed graphs.
  • Using DFS to decompose graphs into connected components.
  Readings: Chapter 3.

• Week 8: 3/5-3/9
  Topics:
  • Directed Acyclic Graphs (DAGs) and using DFS pre-visit and post-visit numbers to perform topological sort on a DAG.
  • Breadth-first search (BFS), correctness and efficiency of BFS.
  • Introduction to Dijkstra's algorithm for solving the Single Source Shortest Path (SSSP) problem with non-negative edge weights. connected components.
  Readings: Sections 4.1 through 4.4.

• Week 9: 3/19-3/23
  Topics:
  • Dijkstra's algorithm for solving the Single Source Shortest Path (SSSP) problem with non-negative edge weights. topological sort on a DAG.
  • Running time analysis of Dijkstra's algorithm.
  • The problem with negative edge weights.
  Readings: Chapter 4.

• Week 10: 3/26-3/30
  Topics:
  • The Bellman-Ford algorithm, correctness, and analysis.
  • Introduction to optimization problems and greedy algorithms.
  • The Interval Scheduling problem, examples of natural greedy algorithms that don't work.
  • The Earliest Finish Time First algorithm for the Interval Scheduling problem and its proof of correctness.
  Readings: Chapter 4.

• Week 11: 4/2-4/6
  Topics:
  • Exam 2 review.
  • The Minimum Spanning Tree (MST) problem, Kruskal's algorithm for MST, proof of correctness of Kruskal's algorithm via the cut-property of MST.
  • Implementation of Kruskal's algorithm using the Disjoint Set Union Find data structure.
  Readings: Section 5.1.

• Week 12: 4/9-4/13
  Topics:
  • Union by rank and Path Compression to speed up operations of the Disjoint Set Union Find data structure.
  • Introduction to approximation algorithms, examples of the Minimum Vertex Cover (MVC), Minimum Dominating Set (MDS), and Set Cover problems.
  • Greedy algorithms for MDS and Set Cover and analysis.
  Readings: Section 5.1 and 5.4.

• Week 13: 4/16-4/20
  Topics:
  • Introduction to dynamic programming. Overview of the technique.
  • First example of dynamic programming in action: The Weighted Interval Scheduling problem.
  Readings: Sections 6.1 and 6.2.

• Week 14: 4/23-4/27
  Topics:
  • Solving the Longest Increasing Subsequence problem using dynamic programming.
  • Solving the Edit Distance problem using dynamic programming.
  Readings: Sections 6.3 and 6.4.