Spring 2018: Design and Analysis of Algorithms, CS:5350

Coordinates

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

Instructor

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

Office hours: Monday 3:00--4:30, Wednesday 1:30--3:00; 101D MLH.

Teaching Assistant

Tanmay Inamdar. Email: firstname-lastname@uiowa.edu.

Office hours: Monday 10:30--12:00, at 101N MLH.

What this Course is About

We will practice the precise statement of various computational problems, think about different strategies or algorithms to solve them, reason about their correctness, evaluate these algorithms from the point of view of efficiency (usually running time), and develop a feel for the difficulty of problems and the applicability of various techniques we will learn. It is convenient to organize the course in terms of the following topics:

Topics like Divide-and-Conquer and Dynamic Programming are also covered in most undergraduate algorithms courses. Our treatment of such topics will therefore be at a faster pace, and aim to cover more material. We may cover one or two other topics, possibly from the following list: exact algorithms for hard problems, approximation algorithms, more of probabilistic algorithms, basic computational geometry algorithms.

Throughout the course, we will focus on developing algorithmic intuition and learning to communicate algorithms effectively.

The above course description is preliminary, and the actual course may have small variations.

Textbook

We will rely on lecture notes. Mostly, we will use the notes from Jeff Erickson.

Prerequisites

Undergraduate Algorithms is the prerequisite.

More specifically, we will assume some comfort with counting and estimating things (the kind we learn in discrete structures), some experience with writing programs, and some experience 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.

From undergraduate data structures and algorithms courses, we will assume familiarity with basic data structures, topics such as sorting, graph exploration (breadth first search, depth first search), and shortest path algorithms. Beyond this, we won't assume familiarity with specific topics, but will instead assume a certain (grad-level) maturity.

Grading

The grading will be based on (approximately) six homework assignments (35 percent), a midterm (25 percent), a final (35 percent), and class participation (5 percent). One or two of the homework assignments will be based on programming.

The policy on late homework is that you have a quota of three 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 a day late, the fifth two days late, and the rest of the homework assignments on time. Once you use up your quota of three days, any homework submitted late will not be accepted and you will get 0 points for that homework.

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 midterm will be on Thursday, March 29, in class. The final will be during finals week; the time and place will be announced after the Registrar's office determines it.

What We Covered Each Week

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

Handouts and Homeworks

For a previous episode of this course, see the Spring 2017 offering.