CS:3330 Algorithms, Section 0002
Spring 2018
Section 0002: 12:301:45 TTh Room 110 MLH (MacLean Hall)
Instructor:
Sriram V. Pemmaraju (Section 0002)
Office: 101G MLH, srirampemmaraju@uiowa.edu, 3193532956
Office Hours: 1:302:30 M, 10:3011:30 W, 2:003: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, supplychain 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
The TAs for the course are CS seniors Wes Weirather (wesleyweirather@uiowa.edu) and Junbin Ma (junbinma@uiowa.edu).
Information about office hours of the TAs will be posted here during the first week of
classes.
 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.
Announcements
 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 23rd24th. Register and attend the conference; you might even get extra credit points for CS:3330.
 2/13 Midterm exam 1 is scheduled for Tue Feb 20th, 6:308:30 pm, in Room: W128 CB (Chemistry Building). More details will be posted soon.
 2/8: There will be an inclass quiz on Tue 2/13.
 1/22: There will be an inclass 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:304:30, Tue 11 to noon, and Wed 1:302:30.
 1/15: Welcome to CS:3330, Section 0002!

Week 1: 1/151/19
Topics:
 Problem: Given positive integers n and p, (efficiently) compute the nth 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/221/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/292/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/52/9
Topics:
 Using numbertheoretic ideas and randomization to design good hash functions.
 Introduction to the divideandconquer 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/122/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 medianfinding.
Readings: Section 2.4 (on finding medians), Section 2.2 (on
recurrence relations), Section 2.1 (on integer multiplication)

Week 6: 2/192/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/263/2
Topics:
 Introduction to graph algorithms, representing graphs, input size for graph algorithms, sparse and dense graphs.
 Depthfirst search (DFS) of undirected and directed graphs.
 Using DFS to decompose graphs into connected components.
Readings: Chapter 3.

Week 8: 3/53/9
Topics:
 Directed Acyclic Graphs (DAGs) and using DFS previsit and postvisit numbers to perform
topological sort on a DAG.
 Breadthfirst search (BFS), correctness and efficiency of BFS.
 Introduction to Dijkstra's algorithm for solving the Single Source Shortest Path (SSSP) problem with nonnegative edge weights.
connected components.
Readings: Sections 4.1 through 4.4.

Week 9: 3/193/23
Topics:
 Dijkstra's algorithm for solving the Single Source Shortest Path (SSSP) problem with nonnegative 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/263/30
Topics:
 The BellmanFord 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/24/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 cutproperty of MST.
 Implementation of Kruskal's algorithm using the Disjoint
Set Union Find data structure.
Readings: Section 5.1.

Week 12: 4/94/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/164/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/234/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.