CS:4310 Design and Implementation of Algorithms
Fall 2021

Instructor:
Sriram V. Pemmaraju sriram-pemmaraju@uiowa.edu
Drop-in zoom office Hours: 1:30-2:30 T, 11:00-noon Th, 2:00-3:00 F (zoom link on ICON) and by appointment

Course website: on ICON
Department website: http://www.cs.uiowa.edu/
Course modality: Face-to-face, 10:30-11:20 MWF Room 217 MLH (MacLean Hall)

Course content
This course will cover fairly traditional undergraduate-level algorithms material, but at a faster pace than our undergraduate algorithms course and with a distinct emphasis on translating pen-and-paper algorithms into correct and (usually) efficient implementations. The main topics we plan to cover are: divide-and-conquer, backtracking, dynamic programming, greedy algorithms, data structures, and graph algorithms. We will also make brief forays into randomized algorithms and data structures, NP-completeness, and approximation algorithms.

Prerequisite
The official prerequisites for the course are undergraduate data structures (CS: 2230 or equivalent) and undergraduate discrete structures (CS: 2210 or equivalent). What this means is that you should have a background in using asymptotic notation, counting and estimating discrete quantities, elementary probability, and data structures. Furthermore, you should have reasonable proficiency in at least one high level programming language and be able to independently implement algorithms and data structures in this language.

Textbook
Most of the material for the course will come from the textbook of Jeff Erickson, which is freely a available online at http://jeffe.cs.illinois.edu/teaching/algorithms/. In addition, I will regularly point to videos by Tim Roughgarden, available at http://www.algorithmsilluminated.org/, that accompany his "Algorithms Illuminated" course. As I cover material, I will regularly assign readings and videos each week from these resources.

Teaching Assistants
CS PhD student Osama Khalid is the Teaching Assistant (TA) for this course. His virtual office hours are: 9:00-10:20 M, 12:30-2:00 W. His zoom link appears on the ICON course page.

Grading
Plus/Minus grading will be used for the course. Grades will be published on ICON. There are four components of evaluation that will collectively determine your grade.

• Weekly check 20% Every week you will need to complete a "check" to make sure that you are keeping up with and understanding the course material (i.e., assigned readings, material covered in lectures). The "check" may take the form of a "reading response", i.e., simple questions on assigned readings that you will have a 2-3 days to answer or it make take the form of a quiz. In some weeks, you may have to complete both a "reading response" and a quiz.

• Weekly engagement 15% You are expected to show continuous "engagement" with the course material. You can show this by asking questions or answering questions about the material, either in class or during office hours (with me or with the TA). As I lecture, I will ask students a number of questions, partly to keep the class interactive and partly to assess how well the material is being understood. This will be one opportunity to get "engagement" points. But, you can also get engagement points by asking questions about aspects of the assigned readings or lectures or about homeworks. Each week will contribute to 1% of the "engagement" points with 1-2 bonus percentage points.

• Homeworks 30% You will be assigned 8-10 homeworks over the course of the semester. About half of the homeworks will be pen-and-paper homeworks and the other half will be programming problems. You will have about a week each to complete the pen-and-paper homeworks and about 2 weeks for the programming problems. More details on the programming problems will be provided when the first programming problem is assigned.

• Exams 35% There will be one midterm exam (15%) and one final exam (20%). Both will be a two-hour long, open notes/book exams. The date and location of the exams will be posted soon on the course website.

Attending classes
Attendance will not be marked, however there is a strong correlation between staying engaged in the course and performance in the course. One way to stay engaged in the course is to regularly attend lectures. Since this course has a face-to-face modality, I don't plan on providing a full-fledged parallel, online version of the course. But, I do understand that COVID-19 spread (as well as concern about COVID-19 spread) could impact classroom attendance for some students. I will do my best to support the learning of students, even when they are unable attend some classes.

Late Submissions
In general, 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, I completely understand this this is a highly unusual semester and there may be COVID-19-related or unrelated reasons for a student to not complete their work on time or be present at the midterm. So I will be flexible and will follow the University and College of Liberal Arts and Sciences (CLAS) policies and advice on student absences. Students will be allowed to make up missed exams and assignments due to illness (COVID-19-related or otherwise), quarantine or self-isolation, 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.

The key to completing homeworks on time is starting early and asking questions (see the "Weekly engagement" component of evaluation). The TA and I will be glad to help with any questions you may have on homeworks, either by e-mail or in our virtual office hours. If you cannot make our office hours, please feel free to make an appointment for a meeting at a different time. I am also happy to chat with you in-person before or after class.

Class Behavioral Expectations
Students are expected to comply with University policies regarding appropriate classroom behavior as outlined in the Code of Student Life. This includes policies and procedures related to COVID-19. The University of Iowa strongly encourages the use of face masks and social distancing when possible. The City of Iowa City requires you wear a mask in public spaces, including campus buildings. Furthermore, the University strongly encourages students, faculty, and staff to receive the COVID-19 vaccine, in consultation with their healthcare provider.

With regards to behavior not related to COVID-19, showing up to class late, leaving your cell phone ringer on, chatting with your friends, burying your head in laptop or phone, etc., can be quite distracting to the instructor 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. In the event that a student disrupts the classroom environment through the failure to comply with the reasonable directive of an instructor or the University, the instructor has the authority to ask that the student immediately leave the space for the remainder of the class period. Additionally, the instructor is asked to report serious or repeated incidents to the Office of Student Accountability for the possibility of additional follow-up. For more information consult the CLAS statement on Student Rights and Responsibilities at http://clas.uiowa.edu/students/handbook/student-rights-responsibilities. Students who need a temporary alternative learning arrangement due to COVID-19 should contact Student Disability Services (phone: +1 319 335-1462).

Class Recordings: Privacy and Sharing
Some of the sessions of a course could be recorded or live-streamed. Such recordings/streaming will only be available to students registered for this class. These recordings are the intellectual property of the faculty, and they may not be shared or reproduced without the explicit, written consent of the faculty member. Further, students may not share these sessions with those not in the class or upload them to any other online environment. Doing so would be a breach of the Code of Student Conduct, and, in some cases, a violation of the Federal Education Rights and Privacy Act (FERPA).

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 assigned readings, answering reading response questions, solving homework problems, preparing for exams, etc. However, the "6 hours per week" estimate is an average and also presupposes that you attend classes regularly, pay attention in class, visit the instructor your questions during office hours, etc.

Administrative Home
This course is run by the Department of Computer Science which is part of the College of Liberal Arts and Sciences. This means that class policies on matters such as the add/drop deadlines, the second-grade-only option, and other related issues are governed by the College of Liberal Arts and Sciences (CLAS). Questions may be addressed to 120 Schaeffer Hall, or see the CLAS Academic Policies Handbook at http://clas.uiowa.edu/students/handbook. Students wishing to add or drop this course after CLAS deadlines must receive the approval of the Dean of CLAS. Details of the University policy of cross enrollments may be found online at https://provost.uiowa.edu/files/provost.uiowa.edu/files/crossenroll.pdf.

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.

Accommodations for Disabilities
The University of Iowa is committed to providing an educational experience that is accessible to all students. A student may request academic accommodations for a disability (which includes but is not limited to mental health, attention, learning, vision, and physical or health-related conditions). A student seeking academic accommodations should first register with Student Disability Services (SDS) and then meet with the course instructor privately in the instructor's office to make particular arrangements. Reasonable accommodations are established through an interactive process among the student, instructor ,and SDS. For more information, see http://sds.studentlife.uiowa.edu/.

Academic Honesty
The components of evaluation for this course (reading responses, homeworks and exams) are meant to test your individual mastery of the material. Hence none of these are collaborative and under no circumstances should you pass off the work of someone else as your own. Doing so would constitute academic dishonesty. This also applies to code or other material that you might find on the internet; if your answers depend of material you have found on the internet or elsewhere, please provide full attribution. Providing answers to another student also constitutes academic dishonesty.

We do want students to talk to each other about concepts and ideas that relate to the class. We believe that this type of peer-interaction can be quite helpful to students. However, this interaction needs to happen without actual exchange of written answers (e.g., code or pseudocode snippets) to homeworks. 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. All CLAS students or students taking classes offered by CLAS 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. See the CLAS Academic Policies Handbook at https://clas.uiowa.edu/students/handbook for more details.

Student Complaints
If you have any complaints or concerns about how the course is being conducted please feel free to talk to the instructor. 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). Consult the CLAS statement on Student Rights and Responsibilities at http://clas.uiowa.edu/students/handbook/student-rights-responsibilities for more information.

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 http://opsmanual.uiowa.edu/community-policies/sexual-harassment for assistance, definitions, and the full University policy. Also see http://www.sexualharassment.uiowa.edu/ for additional resources.

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 http://hawkalert.uiowa.edu/.

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. We will also be using piazza for reading responses, homework discussions, and other announcements.