cs473: ALGORITHMS (SPRING 2022)

- 2022-01-21: The psets have been renumbered to start with 0.

**Description:** cs473 is an algorithms course aimed at advanced undergraduates and graduate students in computer science and related disciplines.

**Lecture:** TR2-3:15, Siebel 1404.

**Staff:**

role | name | (netid) |
office hour |
---|---|---|---|

instructor: |
Prof. Michael A. Forbes | (miforbes) |
T3:30, TBA |

teaching assistant: |
Christian Howard | (howard28) |
TBA |

teaching assistant: |
Pooja Kulkarni | (poojark2) |
TBA |

course assistant: |
TBA |

The **calendar** lists lecture topics, associated lecture materials, and auxiliary reading. It also lists the problem sets with release- and due-dates, as well as listing the exam schedule.

The forum for the class is Piazza (code).

The submission server for the class is Gradescope (code). When submitting assignments, student must use their `@illinois.edu` netid so the course staff can appropriately map students to submissions.

A students grade in the course compromises the 12 psets of 3 problems each (25%), 2 (non-cumulative) exams (22.5% each), and 1 (cumulative) final (30%).

The lectures for the course will be in-person, subject to covid modifications. If and when lectures are online, lectures will be held synchronously on zoom.

Materials from lecture (slides, boardwork, etc) will be posted, within 24 hours of the lecture, on the calendar. Recordings of the (online, or in-person) lecture will similarly be posted, within 24 hours of the lecture, on the calendar

The main materials for the class are the above-mentioned lecture materials. Auxiliary pointers to written material will be listed for each lecture, and are approved materials for collaboration purposes. Additional approved textbooks are as follows.

*Algorithm Design*, by Jon Kleinberg and Éva Tardos*Algorithms*, by Jeff Erickson*Introduction to Algorithms*, by Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, and Clifford Stein*Understanding and Using Linear Programming*(fulltext), by Jiří Matoušek and Bernd Gärtner

cs374 or equivalent, or graduate standing. In particular, students are assumed to have *mastered* the material taught in cs173 (discrete mathematics) and cs225 (basic algorithms and data structures). We emphasize that "mastery" is not the same as "exposure" or even "a good grade". Programming experience is helpful; a strong mathematics background is even more helpful.

Students who have completed this course are prepared for various other theoretical computer science courses at UIUC, such as the following regularly offered courses.

In accordance with university guidelines for Spring 2022, the first week of the course will be online. Lectures will be held synchronously on zoom; lecture recordings will be posted on the calendar.

In accordance with university guidelines for facial coverings, all in-person participants in lecture must wear an approved facial covering, regardless of vaccination status. In addition, no eating or drinking will be allowed in the lecture hall.

The course will use Piazza as a forum.

The forum will be the sole source of announcements from the course staff. Students should sign-up promptly to avoid missing such announcements.

The forum is also intended for students to connect amongst themselves on all course-related issues, **except** when such discussion reveals significant information about solutions to pending assignments. Posts can be made anonymously to other students (but not to the course staff). The students in the course can sometimes offer the best help; please make this resource the best it can be.

The forum is finally meant for private communication between the students and the course staff, especially for logistical matters such as scheduling conflicts. Emailing course staff directly is *heavily discouraged*. While the forum can be used for private help from the course staff on course content, a quicker and more thorough response is often achieved through a public discussion.

In order to avoid distracting other students, any student (without prior accommodation) who uses a computing device with a screen that does not lie flat on table/lap *must* sit in the back half of the lecture hall. Some examples:

- If you are using a tablet to take notes and the tablet lies flat on a table, you can sit wherever you want.
- If you are using a laptop, you must sit in the back half of the room.
- If you are using a smartphone and you leave it
*on the desk*, you can sit wherever you want. But if you use your smartphone and it does not lie flat, you must sit in the back of the room.

If you require an accommodation with regards to this policy, please contact the course staff.

Students are allowed to work in groups of up to **three** when submitting problem sets, *except* for pset0 which must be submitted individually. A single pset submitted with multiple authors must be an honest collaboration of *all* students involved on *all* problems of the pset, and is otherwise considered a violation of academic integrity.

Verbal discussion (oral or electronic) with other students in the course is highly encouraged, subject to the constraint that submitted psets must list all such collaborators. However, the composition of the pset submissions must be solely the work of the listed author(s). In particular, no sharing of written solutions is allowed.

For example, if a student in a group of 2 others, works with another 5 other peers in a collaboration group, then the submitted pset of the original student must list all 5 peers, but only have been written by the original group of 3 students.

Students are allowed to use any listed course materials, or discussions with students or staff affiliated with the course. Students are forbidden from using any other online, textbook, or human resource.

The first violation of academic integrity is a zero for the entire assignment (pset, exam, or final). The second violation is a reduction of 1 letter grade.

A students grade in the course compromises the 12 psets of 3 problems each (25%), 2 (non-cumulative) exams (22.5% each), and 1 (cumulative) final (30%). All problems from problem sets are worth the same number of points. The 6 lowest-scoring problems for all pset problems will be dropped for the entire collection of 3× 12=36 problems algorithm, *except* for those problems for which students receive zero scores due to integrity violations.

Regrade requests will be open for two weeks after an assignment is returned. Regrade requests will result in the *entire* assignment (pset, exam, or final) in being regraded; as a result the overall score may decrease.

Solutions will be presented for all graded coursework. Do not share solutions beyond students and staff affiliated with the course.

As mention in the section, the 6 lowest-scoring pset problems will be dropped from a students score. As such, no late psets will be accepted.

In **extreme** circumstances, coursework (psets, exams, or final) may be dropped. Such circumstances include documented injury or illness, and do *not* include predictable events such as job interviews. Students should contact the course staff if they believe this policy applies to them.

Above all, coursework should be **clear** and **concise**. Students are suggested to address the following sections in their coursework:

**algorithm:**What is the algorithm? Students should precisely describe an algorithm. While pseudocode can be precise, it is often tedious to write, and to read. While sometimes this level of detail is appropriate, students are encouraged to use as high a level of language possible, while still maintaining rigor and precision.**correctness:**Why is the output of the algorithm the correct? Students should provide a*proof*of correctness, in particular by referencing the particular algorithm they are proposing. When considering a*randomized*algorithm, correctness also includes that the algorithm produces the correct input*with high probability*.**complexity:**Why is the algorithm efficient? How much resources does the algorithm require to produce an output? Students should provide a*proof*that the described algorithm uses few resources (time, or sometimes space) to produce an output, on*all*inputs. In particular, it should follow from the proof that the algorithm always halts.

The level of detail required for coursework should be more than is presented in lecture — lecture is time-constrained so not all details can always be presented in full. In contrast, coursework solutions are presented in *more* detail than is typically expected of students — such solutions are so detailed to ensure student comprehension.

Figures are **highly** encouraged. Many algorithms act on combinatorial objects such as graphs, and discussing such objects without a figure is a pain to write, and to read.

Student psets must obey the following constraints:

- Each problem starts on its own page.
- The first page has the following metadata:
- author(s) of the problem set
- name(s)
- netid(s)
- pset number
- list of collaborators

To use your time wisely, students are encouraged to focus on *content* of their coursework over *format*. However, content and format are not fully independent. As such, students are suggested to consider the following advice on submission formats.

**typesetting submissions:**Typesetting is generally encouraged. Electronic documents are easier to revise, and as such easier to use to ensure content quality as first drafts are rarely polished. Typesetting ensures legibility, which is important as the course staff cannot give credit for work they cannot read. Finally, learning to typeset is a skill useful in many parts of academia and industry.**However**, including figures in typeset documents is often difficult, to the point that often students prefer to omit figures altogether. This can lead to a significant decrease in coursework clarity and concision, which can impact the score received. For beginners to typesetting there is the additional burden of having to learn to typeset while learning the course material. The result is often an ungainly document, to the point that the legibility gained by typesetting is offset by the poor usage of typesetting's abilities.**handwriten submissions:**Handwritten submissions are accepted, as long as they are at least as legible as the handwriting of the instructor, and also that the submissions use**figures**.

When multiple students can form a group to submit problem sets, a *single* student should upload the submission on behalf of the rest. That student should ensure that they appropriately label the additional authors (in the submission server upload, as well as within the pset.

When submitting assignments, student must use their `@illinois.edu` netid so the course staff can appropriately map students to submissions.