CS:3330 Algorithms, Sections 0001, 0002
Spring 2017

Instructors:
Sriram V. Pemmaraju (Section 0001)
Office: 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)

Shreyas Pai (Section 0002)
Office: TBA, shreyas-pai@uiowa.edu
Office Hours: 9:30-10:30 M and F, 2:00-3:00 W (and by appointment)

Course website: http://www.cs.uiowa.edu/~sriram/3330/spring17/
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 algorithms are viewed as the greatest contribution of the field of computer science to every day 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. Previous courses have already given you a taste of "algorithmic thinking" and the main aims of this course are to (i) deepen your algorithmic intuition, (ii) help you build a toolbox of algorithmic design techniques, and (iii) to develop the ability to effectively communicate algorithms.

In this course, We will practise the precise statement of various computational problems, think about different algorithmic strategies to solve them -- either exactly or with some controlled error, 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.

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

1. Introduction to algorithms
2. Introduction to algorithm analysis
3. Algorithms that are not always correct: introduction to randomized and approximation algorithms
4. Introduction to greedy algorithms
5. Shortest path problems
6. The minimum spanning tree problem
7. The Divide-and-Conquer paradigm
8. Introduction to dynamic programming.
9. Computational intractability

Reading Material As the main source of material, we will use the (free and online) lecture notes of Professor Jeff Erikson's. In addition, we will use material from the following textbooks:

• Algorithm Design by Jon Kleinberg and Eva Tardos. (ISBN-13: 978-0321295354, ISBN-10: 0321295358)
• Introduction to Algorithms by Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. (ISBN-10: 0262033844 ISBN-13: 978-0262033848)

Prerequisite
CS:1210 (Computer Science II: Data structures) and either MATH: 1550 (Engineering Math I Single Variable Calculus) or MATH: 1850 (Calculus I).

Teaching Assistants
The TAs for the course are Xin Man (xin-man@uiowa.edu) and Richard Blair (richard-blair@uiowa.edu), both computer science PhD students. Information about office hours of the TAs will be posted on the course website during the first week of classes.

Grading
Plus/Minus grading will be used for the course. There are two components of evaluation that will collectively determine your grade.

• Homeworks 40% You will be assigned 10 homeworks over the course of the semester and you will have about a week to complete each homework. Some of the homeork problems will involve programming.
• Quizzes 5% There will be 5 in-class quizzes, possibly unannounced. Each quiz will be 5-10 mins long and will serve as a way to test your preparation on a specific topic (e.g., using asymptotic order of growth notation).

• Exams 55% There will be two mid-terms exams and one final exam. Each mid-term exam will be worth 15% of your grade and the final will be worth 25%, for a total of 55%. The time and place for the mid-term exams are as follows:

  Mid-term exam 1 	Tue Feb 21st, 6:30-8:30 pm 	Room: Shambaugh Auditorium, Main Library 
  Mid-term exam 2 	Tue April 4th, 6:30-8:30 pm 	Room: Shambaugh Auditorium, Main Library 
  

  The final is also two hours long. The final will take place during the week of May 8th and the exact date and time of the final exam will be announced in March on the course website. The final exam date and time will also be announced by the Registrar via email using your uiowa address generally within the first several weeks of the semester. All exams will be open notes/books exams.

Solutions to programming problems will have to submitted via ICON's dropbox feature. Grades will also be published on ICON. Homeworks, exams and solutions to these will be regularly posted on the course page (http://www.cs.uiowa.edu/~sriram/3330/spring17/) and all together these will form a significant study resource for students.

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 require consistent attendance.

The key to completing homeworks on time is starting early and asking questions. The instructors and the TAs 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 us often during our office hours and if necessary, outside our office hours as well by making an appointment.

Communicating with Instructors and TAs
Asking the instructors and TA questions via e-mail is quite appropriate and any e-mails related to CS:3330 will be answered within 24 hours of e-mail receipt. You should make sure to include CS:3330 in the subject line to ensure that your e-mail is not consumed by spam filters. Try to state your question(s) as clearly as possible. The more easily understood you are, the more likely it is that you will receive a quick response. Occasionally the professor or the TA may send e-mail announcement to all students in the class at your uiowa e-mail address. Note that you are responsible for all official correspondence sent to the uiowa address and so make sure that you check this e-mail account regularly. The instructor and TAs would also prefer receiving e-mails from your uiowa account, rather than from commercial e-mail providers (e.g., gmail or yahoo!).

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 also presupposes that you attend classes regularly, pay attention in class, visit the professor and the TA with your questions during their office hours, etc.

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 at http://www.uiowa.edu/~provost/deos/crossenroll.doc.

Students with disabilities
We 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 the instructor by e-mail or in person during office hours. For more information visit the website of Student Disability Services at http://sds.studentlife.uiowa.edu/.

Academic Dishonesty
The components of evaluation for this course (quizzes, 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. Providing answers to another student also constitutes academic dishonesty. Note that we will routinely use available software systems for detecting software plagiarism, to test any suspicions we might have.

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.

Student Complaints
If you have any complaints or concerns about how the course is being conducted please feel free to talk to the instrutors. 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.

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 http://www.uiowa.edu/~our/opmanual/ii/04.htm 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 the Public Safety web site at http://police.uiowa.edu/stay-informed/emergency-communication/.

Detailed List of Topics

• Introduction to algorithms
  The stable marriage problem, the Gale-Shapley (GS) algorithm, proof of correctness of the GS algorithm, implementation of the GS algorithm.
• Introduction to algorithm analysis
  Notion of input size, notion of basic operations, counting basic operations, the notion of worst-case analysis, asymptotic growth of functions, the "Big Oh", Omega, and Theta notation for asymptotic growth, properties of asymptotic growth notation, examples of common running times: logarithmic, polynomial, exponential running times.
• Algorithms that are not always correct
  An introduction to randomized and approximation algorithms, illustration of Las Vegas and Monte Carlo randomized algorithms via the Balanced Partition problem, optimization problems and the notion of approximation algorithms, the Minimum Vertex Cover (MVC) problem, the notion of "greedy" algorithms, the poor performance of the natural greedy algorithm for MVC, a 2-approximation for MVC using maximal matchings.
• Introduction to greedy algorithms
  The Interval Scheduling problem, construction of counterexamples showing that many natural greedy algorithms do not work, the "earliest finish time first" greedy algorithm, proof of correctness of this algorithm using the "greedy stays ahead" approach, the problem of Scheduling to Minimize Lateness, greedy algorithm for this problem and its proof of correctness using the "exchange" argument.
• Shortest path problems
  Dijkstra's shortest path algorithm for the Single Source Shortest Path (SSSP) problem, implementation of Dijkstra's algorithm in O((|V| + |E|) log |V|) time using the min-heap data structure, Negative edge-weights and the Bellman-Ford algorithm.
• The minimum spanning tree problem
  The Minimum Spanning Tree (MST) problem, Prim's algorithm and Kruskal's algorithm for MST, implementation of Prim's algorithm in O((|V| + |E|) log |V|) time, implementation of Kruskal's algorithm using the Disjoint Set Union-Find data structure, example of amortized analysis: find in worst case O(1) time, union in O(log |V|) amortized time, an alternate implementation of the Disjoint Set Union-Find data structure with find in worst case O(log |V|) time and union in worst case O(1) time.
• The Divide-and-Conquer paradigm
  The Merge Sort algorithm, writing and solving the recurrence for the running time of Merge Sort, the recursion tree method for solving recurrences, the Integer Multiplication problem, improving over the grade-school multiplication algorithm using Karatsuba's algorithm, the Master Method for solving recurrences, randomized Quick Sort and the probabilistic recurrence for randomized Quick Sort.
• Introduction to Dynamic Programming
  The Fibonacci Number problem, the problem with the recursive Fibonacci number function, memoization, the Weighted Interval Scheduling problem: an example of 1-dimensional dynamic programming, the Longest Common Subsequence problem: an example of 2-dimensional dynamic programming.
• Computational Intractability
  Decisions problems, the class P and the class NP, examples of problems in NP that are not known to be in P: Minimum Vertex Cover (MVC), Maximum Independent Set, Maximum Clique, SAT, 3SAT, Hamiltonian Cycle and Travelling Salesman Problem (TSP), polynomial-time reductions, the classes NP-hard and NP-complete, the Cook-Levin Theorem: CircuitSAT is NP-complete, NP-completeness of 3SAT and a bunch of other problems.

  ---