22C:31 Algorithms

Instructor: Sriram V. Pemmaraju
101G MLH, sriram@cs.uiowa.edu, 319-353-2956
Office Hours: 9-10:30 MW
Course website: http://www.cs.uiowa.edu/~sriram/31/spring10/

This course deals with the design and analysis of algorithms. We will study algorithm design techniques such as greedy method, dynamic programming, divide-and-conquer, and randomization and see many examples of each of these techniques in action. We will study algorithm analysis techniques such as asymptotic analysis, recurrence relations, and charging schemes. Towards the end of the course, we will also study the intractability of problems, specifically the theory of NP-completeness. Time permitting, we will study approximation algorithms as a way of getting around the intractability of some problems.

Required Legalese
This course is run by the College of Liberal Arts and Sciences. This means that class policies on matters such as requirements, grading, and sanctions for academic dishonesty are governed by the College of Liberal Arts and Sciences. Students wishing to add or drop this course after the official deadline must receive the approval of the Dean of the College of Liberal Arts and Sciences. Details of the University policy of cross enrollments may be found online here.

Prerequisite
C- or better in 22C:21 and 22M:025 or 22M:031

Textbook

The textbook for this course is Algorithm Design by Kleinberg and Tardos (see this for more details).

Teaching Assistant

There may be a Teaching Assistant (TA) assigned to this course. We'll find out soon. The TA's primary responsibilities will be to grade homeworks that you submit and hold office hours (3 hours per week) to provide help on homeworks and material being covered in the lectures. More details regarding the TA will be posted as soon as I find out.

Course Accounts

For this course, it will be helpful if you have an account on computer science machines. Most of you already have such accounts; the rest of you will get CS accounts by the end of the first week. You will also need a HawkID and a password to login to ICON to electronically submit your assigned work.

Grading
Plus/Minus grading will be used for the course. There are the three components that will determine your grade.

• Homeworks: 42% You will be assigned 7 homeworks during the semester. Each homework will be due back in about 2 weeks.

• 1 Programming Project: 8% You will be assigned one programming project in the second half of the course.

• 2 Exams: 50% There will be two take-home mid-term exams (each worth 15% of your grade) and one final (worth 20% of your grade). The schedule for the exams is:
  • Exam 1, handed out on Feb 18th, Thurday; due back the following day.
  • Exam 2, handed out on April 1st, Thursday; due back the following day.
  • Final exam, 9:45-11:45 am, Tuesday, May 11th, 2010.
  More details on exam logistics (e.g., how and at what time will they be handed out, etc.) will be announced closer to the exams. The final will be cumulative and open notes/textbook.

Late submissions will not be accepted and in general you will be better off turning in what you have on time rather than seeking extra time to complete your work. Starting early is the key, and the TA and I will be glad to help with any questions you may have on the assignments. So please visit us often during our office hours and if necessary, outside our office hours as well. There will be no make-up exams in general and exceptions will be rare and only for students whose reasons are included in the University's policy on "Excused Absences from Examinations".

Solutions will be provided on the course page for all the homeworks.

Students with disabilities
I would like to hear from anyone who has a disability which may require seating modifications or testing accommodations or accommodations of other class requirements, so that appropriate arrangements may be made. Please contact me during my office hours.

Academic Dishonesty
Academic dishonesty will not be tolerated. Under no circumstances should you pass off someone else's work as your own. This also applies to code or other material that you might find on the internet. Note that we will routinely use available software systems for detecting software plagiarism, to test any suspicions we might have. If you are unclear about what constitutes academic dishonesty contact your professor or consult the policy in the CLAS Bulletin (online version). We do want students to talk to each other about concepts and ideas that relate to the class. However, it is important to ensure that these discussions do not lead to the actual exchange of written material.

Student Complaints
If you have any complaints or concerns about how the course is being conducted by me or by the TAs please feel free to talk to me. You are also welcome to get in touch the the Computer Science department chair, Prof. Jim Cremer (cremer@cs.uiowa.edu, 319-335-1713, 14D McLean Hall). Consult the college policy on Student Complaints Concerning Faculty Actions (online version) for more information.

Tentative List of Topics

• Representative problems; input representation (Chapter 1)
• Running times, asymptotic analysis, Big O, Big Omega, Big Theta (Chapter 2)
• Greedy Algorithms (Chapter 4)
• Divide and Conquer (Chapter 5)
• Dynamic Programming (Chapter 6)
• Randomized Algorithms (Chapter 13)
• NP-completeness and Intractability (Chapter 8)
• Approximation Algorithms (Chapter 11)