CS:5350 Design and Analysis of Algorithms
Spring 2016

9:30-10:45 TTh Room 71 SH (Schaeffer Hall)

Sriram V. Pemmaraju
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/5350/spring16/
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 everyday 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.

This course is on the design and analysis of algorithms (as indicated by the title!) and the difficulty (tractability) of problems from an algorithmic point of view. In this course, we will practice the precise statement of various computational problems, study different algorithmic strategies to solve them -- either exactly or with some controlled error, learn to state algorithms precisely, 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.

We will organize the course in terms of the following topics:

  1. Divide-and-Conquer
  2. Dynamic Programming
  3. Flows, cuts, and matchings
  4. Randomized Algorithms
  5. Computational Intractability
  6. Models of Computations and Algorithms for "Big Data"

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

Information about TAs

The TA for the course is James Hegeman, a 5th year computer science PhD student. His e-mail address is: james-hegeman@uiowa.edu.
Office Hours: Tue 2pm-3pm, Wed 3pm-4pm.

Homeworks and Exams

  • Homework 1. Due on Thu, Jan 28 in class.
  • Homework 2. Due on Thu, Feb 4 in class.
  • Homework 3. Due on Thu, Feb 11 in class.
  • Homework 4. Due on Thu, Feb 25 in class.
  • Homework 5. Due on Thu, March 3 at exam time.
  • Homework 6. Due on Thu, March 24 in class.
  • Midterm Exam.
  • Homework 7. Due on Thu, March 31 in class.
  • Homework 8. Due on Thu, April 7 in class.
  • Homework 9. Due on Tue, April 26 in class.
  • Homework 10. Due on Thu, May 5 in class.
  • Midterm Retake Exam.


    Weekly Topics