Spring 2020: Design and Implementation of Algorithms, CS:4310:0001


The course meets 9:30--10:45 am Tuesday and Thursday at 118 MLH (MacLean Hall).


Kasturi Varadarajan, 101D MacLean Hall, Phone: 335-0732, email:firstname-lastname@uiowa.edu.

Walk-in hours: Monday 10:30--12:00, Wednesday 10:30--12:00; 101D MLH.

Teaching Assistant

Cory Kromer-Edwards; Email: cory-edwards@uiowa.edu.

Walk-in hours: Monday 1:30--2:30 pm, Thursday 11:30--12:00, at 201N MLH.

What this Course is About

This course has two main goals. The first is to develop an understanding of fundamental algorithm design techniques. Here we will focus on ways of approaching algorithm design, and practice communicating our ideas effectively. The second goal is to develop experience with designing and programming algorithms with a view to practical efficiency. These two goals usually interact, but not in a straightforward way.

Topics that we plan to cover include (i) recursive thinking, leading up to divide-and-conquer, backtracking, and dynamic programming, (ii) data structures, (iii) graph algorithms and related data structures, (iv) greedy algorithms, (v) randomized algorithms, and (vi) dealing with intractability. This is preliminary, and the actual course may have small variations.


We will use Jeff Erickson's online textbook, available at this page. This page includes other material under the heading More Algorithms Lecture Notes, which we may also use.


Undergraduate discrete structures and data structures are the official prerequisites.

More specifically, we will assume some comfort with counting and estimating things (the kind we learn in discrete structures), experience with writing programs, and with estimating and communicating running time (for example, what it means to say ``this algorithm's worst case running time is O(n^2)''). We will also assume that when we talk about algorithms, you are comfortable at seeing how they might translate into programs. Computer science undergrads typically pick these skills up in their data structures and algorithms courses.

Student Work and Grading

The grading will be based on (approximately) nine homework assignments (30 percent), two midterms (20 percent each), a final (25 percent), and engagement (5 percent). Four of the nine homeworks will involve programming, and the remaining will be shorter and involve pen and paper work. Engagement includes involvement in class and being able to adequately explain your homework solution when called upon by me or our TA.

The policy on late homework is that you have a quota of four days for the entire semester that you may use for late submissions. So for example, there will be no penalty if you submit the third homework two days late, the fifth two days late, and the rest of the homework assignments on time. Once you use up your quota of four days, any homework submitted late will not be accepted and you will get 0 points for that homework. No individual homework can be late by more than two days. (I don't count the weekends/holidays -- if an assignment is due 1:45 pm on Thursday, and you submit it by 1:00 pm the following Monday, you will be two days late.)

When you submit a homework X days late, your quota gets decreased by X irrevocably. You can only be late by an integer number of days -- if you submit 10 hours after the deadline, for example, your quota is depleted by one day.

Exam Dates

The midterms will be on Thursday, March 5, and Thursday, April 16, in class. The final will be during finals week; the time and place will be announced here after the Registrar's office determines them.

What We Covered Each Week

We will keep track of what we covered each week here.

Handouts and Homeworks

Departmental Information

Department of Computer Science, 14 MacLean Hall. The office of the DEO, Prof. Alberto Segre, is located here.

Administrative Home

The College of Liberal Arts and Sciences (CLAS) is the administrative home of this course. Please visit this page for CLAS teaching policies and resources.