CS:5350 Design and Analysis of Algorithms

Fall 2019, 9:30-10:45 TTh 15 SH (Schaeffer Hall)

Instructor: 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 webpage: homepage.cs.uiowa.edu/~sriram/5350/fall19/
Department website: http://www.cs.uiowa.edu/

This is the graduate algorithms course aimed at CS PhD students. It will be assumed that a typical student in the course has a solid background in undergraduate-level algorithms material. Please refer to the syllabus of a recent offering of CS:3330 (e.g., https://homepage.divms.uiowa.edu/~sriram/3330/spring18/syllabus.html) to better understand this expectation. Facility in discrete math, especially discrete probability, will be a definite benefit for students in this course. The course material is organized into 4 parts: (i) combinatorial optimization, (ii) randomized algorithms, (iii) approximation algorithms, and (iv) streaming and parallel algorithms. The material on streaming and parallel algorithms can be viewed as a modern application of the material in Parts (I)-(III). Details on specific topics that are likely to be covered, appears further below.

Undergraduate algorithms (CS:3330 or equivalent).

Reading Material You are not required to purchase a textbook for this course. I will use a variety of sources, but mainly:

We will use Erickson's notes for the material on flows, cuts, and matchings, the Williamson-Shmoys book for approximation algorithms, the Mtzenmacher-Upfal book for randomized algorithms, and Chakrabarti's notes for streaming algorithms. I will also post links to relevant papers as we go along.

Tentative* List of Topics

*This is the first time we are offering this version of CS:5350, aimed exclusively at CS PhD students. So the material is somewhat different from material covered in previous offerings of the course. I expect to make changes to the material "on the fly" based on feedback from students and my impression of how things are going.

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

CLAS Final Examination Policies
The final exam schedule for each semester is announced around the fifth week of classes; students are responsible for knowing the date, time, and place of a final exam. Students should not make travel plans until knowing this final exam information. No exams of any kind are allowed the week before finals. (See https://clas.uiowa.edu/faculty/teaching-policies-resources-examination-policies).

Your work on homework solutions can be collaborative in the following sense. Groups of at most two students can work collaboratively on a homework. If a homework solution is submitted by a group of two students, then both members of the group will get an identical grade for the homework. Homework groups may change from homework to homework.

Academic Integrity
Your work on homeworks may be collaborative in a limited manner, as described above and you are, of course, welcome to discuss homework problems with me. But, you need to be extremely careful about any other unsanctioned collaboration or help. For example, you are welcome to talk to classmates outside your homework group about concepts and ideas that relate to the class, but avoid talking about specifics directly connected to homework problems. Also, any help you receive from online sources or books/articles (other than the books and lecture notes mentioned above) should be carefully attributed. Of course, students are welcome (in fact, encouraged) to study together for exams.

If you are unclear about what constitutes academic dishonesty contact the instructor or consult the CLAS Code of Academic Honesty at http://clas.uiowa.edu/students/handbook/academic-fraud-honor-code.

Tardiness and Absences
Late submissions will not be accepted and make-up exams should not be expected. To get credit for assignments you should plan on turning in what you have on time. Having said this, it is also worth noting that this course will follow the University and College of Liberal Arts and Sciences (CLAS) policies that require that students be allowed to make up missed examinations and assignments due to illness, certain University activities, circumstances beyond a student's control (such as a death in the family), or mandatory religious obligations. See http://clas.uiowa.edu/students/handbook/attendance-absences for more details on this policy. Attendance will not be marked, however there is a strong correlation between attendance and performance in the course. For most students, to be successful in this course will at the minimum require 100% attendance.

The key to completing homeworks on time is starting early and asking questions. I will be glad to help with any questions you may have on homeworks, either by e-mail or in person. So please feel free to visit me often during our office hours and if necessary, outside our office hours as well by making an appointment.

Effort Level
According to University guidelines, a student should expect to work for 2 hours per week (outside the classroom) for each course credit. This is a 3 credit course and so you should expect to spend on average about 6 hours per week studying lecture notes and the textbook, solving homeworks, preparing for exams, etc. However, the "6 hours per week" estimate is an average and it also presupposes that you attend classes regularly, pay attention in class, visit me with your questions during my office hours, etc.

Nondiscrimination in the Classroom
UI is committed to making the classroom a respectful and inclusive space for all people irrespective of their gender, sexual, racial, religious or other identities. Toward this goal, students are invited to optionally share their preferred names and pronouns with their instructors and classmates. The University of Iowa prohibits discrimination and harassment against individuals on the basis of race, class, gender, sexual orientation, national origin, and other identity categories set forth in the University’s Human Rights policy. For more information, contact the Office of Equal Opportunity and Diversity at diversity@uiowa.edu or diversity.uiowa.edu.

Students with disabilities
UI is committed to an educational experience that is accessible to all students. A student may request academic accommodations for a disability (such as mental health, attention, learning, vision, and physical or health-related condition) by registering with Student Disability Services (SDS). The student should then discuss accommodations with the course instructor. For more information visit the website of Student Disability Services at http://sds.studentlife.uiowa.edu/.

Student Complaints
If you have any complaints or concerns about how the course is being conducted please feel free to talk to me. You are also welcome to get in touch with Prof. Alberto Segre, the Computer Science department chair (alberto-segre@uiowa.edu, 319-335-1713, 14D MacLean Hall). Students may then bring the concern to CLAS. Consult the CLAS statement on Student Rights and Responsibilities at http://clas.uiowa.edu/students/handbook/student-rights-responsibilities for more information.

Administrative 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, add/drop deadlines, second-grade options 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. These policies vary by college https://clas.uiowa.edu/students/handbook.

Classroom Etiquette
Showing up to class late, leaving your cell phone ringer on, reading a newspaper in class, chatting with your friends, etc., can be quite distracting to the professor and to fellow students. If you are in class, it is your responsibility to pay attention and to make sure that you are not doing anything that makes it harder for fellow-students to pay attention. When disruptive activity occurs, a University instructor has the authority to determine classroom seating patterns and to request that a student exit immediately for the remainder of the period. One-day suspensions are reported to appropriate departmental, collegiate, and Student Services personnel (Office of the Vice President for Student Services and Dean of Students). For more information consult the CLAS statement on Student Rights and Responsibilities at http://clas.uiowa.edu/students/handbook/student-rights-responsibilities.

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 policy on sexual harassment at https://osmrc.uiowa.edu/ for assistance, definitions, and the full University policy.

Electronic Communication
University policy specifies that students are responsible for all official correspondences sent to their University of Iowa e-mail address (@uiowa.edu) and must use this address for all communication within UI. 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.