CSCI 432/532: Advanced Algorithm Topics

Course schedule

Schedule subject to change. Lecture videos in this Panopto folder. Credit for the CS Theory lecture notes and problem session questions/solutions to Jeff Erickson. Papers for the algorithms half of the course will be chosen later.

Catalog description

3 Credits. PREREQUISITE: CSCI 332. Advanced algorithm and data structure concepts, including theory, approximation algorithms, randomized algorithms, parallel algorithms, streaming algorithms, linear programming.

Course info

This course meets in Social Sciences 362 on Tuesdays and Thursdays from 9-10:20am.

This course will have two parts: in the first half, we will work to understand what is computable and how fast using computer science theory developed in the 20th century. This will give us a baseline to understand the contemporary algorithms field and familiarity with the concepts, notation, and proof styles necessary. In the second half, we will learn a number of advanced algorithm concepts and see how they are applied in current algorithms research. This will be a highly interactive class, and although the material is challenging, I will try to provide the appropriate level of support and I think students will get a lot out of the course.

Course resources

Paper/chapter presentation and writeup rubrics

In the second half of the class, on Thursdays we will learn a new advanced algorithm topic and on Tuesdays a group will lead a presentation of a book chapter or research paper related to that topic. Presenters should follow these instructions. On days that a student is not a presenter, they must submit a paper/chapter summary to Gradescope according to these instructions.

Moodle

We will use Moodle for course announcements and for homework submission. Otherwise, all course information will be on this webpage, and any questions about course logistics or content should be asked via Piazza.

Gradescope

Some assignments will be submitted using Gradescope. To join the class, visit the Gradescope website and login or signup, and use our course entry code YDXKY7 to join the class.

Group problem sessions

In the first half of the course, we will be working through concepts in computer science theory. The best way to understand these concepts is through practice and discussion. In order to provide you as much support as possible, I will schedule and lead two weekly problem sessions where we will work through problems that are similar to the homework that you turn in every Monday. These are not required, but you can earn some participation points by attending, and if you attend these problem sessions the homework should be much easier to complete. Solutions will be shared after the problem sessions are completed.

In the second half of the class, we will decide how we want to use the group problem session time.

Textbook

There is no textbook for this course; notes from various sources will be shared as needed. However, there are a number of popular textbooks in this field, many of which are available for free online. I will link textbook-style resources here as we go.

Lecture videos

Lectures will be recorded and available to watch after class. However, if there are technical difficulties recording a lecture, it will not be re-recorded, so come to class when you can to make sure that you do not miss course content or announcements. Videos can be found in the Panopto folder.

Piazza discussion

Especially in the first half of the course, you will be working through problems and I would like you to get help as soon as possible. We will use the online tool Piazza to organize questions and answers. To join, follow the signup link and enter the access code 9n3tn7iqak8. Note that you do not need to use your university email or real name if you prefer not to. Also, pay attention to the prompts to opt out of Piazza sharing your information with recruiters.

Grading

You will be graded on the following:

• 20% participation (15 points for attending lecture sessions; 5 points for attending problem sessions during the theory section; 5 points for feedback after presentations during algorithms section; 5 points for check-out activity during finals week TBD–note that this sums to more than 20, so you do not need to get all of the points to get full credit for this category)
• 20% homework problems (during theory portion) (7 assignments; lowest score dropped)
• 20% problem presentations (during theory portion) (each student participates in 3)
• 20% paper presentations (during algorithms portion) (each student participates in two)
• 20% paper summaries (during algorithms portion) (7 papers total; each student writes 5 paper summaries)

Note that there are no tests!

After any curving, your grade will be determined by your total score as follows: 93+: A; 90+: A-; 87+: B+; 83+: B; 80+: B-; 77+: C+; 73+: C; 70+: C-; 67+: D+; 63: D; 60: D-.

Bonus

There are two ways to earn bonus points in this class.

Catch errors in course materials

If you find an error in any of the course materials (typo, incorrect statement, etc.), make a post in Piazza with the errors-in-course-material tag. If it is really an error, you get a quarter of a point. Only the first person to post about an error gets the points. You can earn a max of 1 total point toward your 100 for the course (for four errors).

Course survey and evaluation

If 100% of the class completes the mid-semester course survey, the whole class gets 1 bonus point. Same goes for the course evaluation at the end of the semester.

Collaboration policy

For homework problems, you may work in groups of up to three and turn in a single writeup as a group. Group work on paper summaries is not allowed.

Additionally, you may use any resource available to you, as long as you write up your answers in your own words and properly cite your source. Some examples of resources you might use:

• other students in the class
• other students not in the class
• other instructors
• textbooks or online notes
• anything you find on the internet
• ChatGPT or other AI tools

Please ask if you have questions about how to properly cite a source or a collaborator.