CS:4980:0002 (22C:196:002) Topics in Computer Science II: Randomized Algorithms

12:30-1:45 TTh Room 302 Lindquist Center (LC)


Instructor: Sriram V. Pemmaraju
101G MLH, sriram-pemmaraju@uiowa.edu, 319-353-2956
Office Hours: 1:00 to 2:30 MW and by appointment.
Course webpage: homepage.cs.uiowa.edu/~sriram/196/fall13/

Randomization has played a powerful role in computer science over the last 3 decades, both in foundational areas such as algorithms, complexity theory, learning theory, etc., and in applied areas such as networks and data mining. In this course we will study the use of randomization in the design of algorithms. Specifically, we will study:

A more detailed list of topics appears further below in the syllabus.

Prerequisite
Undergraduate algorithms (22C:31 or equivalent) and a probability and statistics course (equivalent of 22C:120 or 22C:130). If you do not have the latter prerequisite, but still want to take the course, please talk to me.

Textbook
Michael Mitzenmacher and Eli Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, ISBN 0521835402.

We will follow this textbook closely for some topics. For other topics, we will use material from the following excellent books:

  1. Rajeev Motwani, Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press.
  2. David Williamson, David Shmoys, The design of approximation algorithms, Cambridge University Press.
  3. Devdatt Dubhashi, Alessandro Panconesi, Concentration of Measure for the analysis of randomized algorithms, Cambridge University Press.
I will also post links to relevant papers as we go along.

Detailed List of Topics

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

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. 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".

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 or send me e-mail for an appointment.

Academic Dishonesty
Solving problem sets on your own is the primary way to gain mastery of the material in the course. Thus collaboration is not allowed on homeworks and exams. However, I want to encourage discussions among students in the class about the material being covered - I know that discussion with peers is an excellent way to reinforce your understanding. So as a rule of thumb you should feel free to discuss the material being covered in class, but not specific problems that appear on the homeworks. All students taking College of Liberal Arts and Sciences (CLAS) courses have, in essence, agreed to the College's Code of Academic Honesty: "I pledge to do my own academic work and to excel to the best of my abilities, upholding the IOWA Challenge. I promise not to lie about my academic work, to cheat, or to steal the words or ideas of others; nor will I help fellow students to violate the Code of Academic Honesty." Any student committing academic misconduct is reported to the College and placed on disciplinary probation or may be suspended or expelled (CLAS Academic Policies Handbook). In the context of the guidelines I've provided above, if you are unclear about what constitutes academic misconduct contact your me or consult the printed policy in the Schedule of Courses and the CLAS Bulletin (online version). In the end, it is your responsibility to understand the boundaries between academic misconduct and acceptable behavior.

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

Course Home
This course is run by the Computer Science department which is part of 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.

University Statement on Sexual Harassment
Sexual harassment subverts the mission of the University and threatens the well-being of students, faculty, and staff. All members of the UI community have a responsibility to uphold this mission and to contribute to a safe environment that enhances learning. Incidents of sexual harassment should be reported immediately. See the UI Comprehensive Guide on Sexual Harassment for assistance, definitions, and the full University policy.

Reacting Safely to Severe Weather
In severe weather, class members should seek appropriate shelter immediately, leaving the classroom if necessary. The class will continue if possible when the event is over. For more information on Hawk Alert and the siren warning system, visit the Public Safety web site.

Electronic Communication
University policy specifies that students are responsible for all official correspondences sent to their University of Iowa e-mail address (@uiowa.edu). From time to time, I will send you e-mail at your @uiowa.edu address. Sometimes this may need your immediate attention, so please check this e-mail account regularly.