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. If you’d like to check out last year’s version of the class to see how things might go, go here.

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

Canvas

We will use Canvas 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 Discord. You can find the invite to join the Discord on Canvas.

Group problem solving 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 strictly required, but you 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. The problem session for Monday’s lecture will be scheduled outside of class, and the problem session for Wednesday’s lecture will be held during the Friday lecture time.

Please fill out this poll during the first week of class to help schedule the problem session for Monday lecture: https://whenisgood.net/ayijc9t.

Textbook

There is no required textbook for this course; notes from various sources will be on the schedule above for each lecture as needed. However, if you would like to consult additional resources, I can recommend a number of popular textbooks in this field, many of which are available for free online.

• Jeff Erickson’s Algorithms Notes. We follow the Models of Computation notes at the bottom of the page in the first half of this class.
• Avi Wigderson’s Mathematics and Computation. Avi is one of the most prolific computer science theorists of the modern age. He won the ACM Turing award in 2023. His book offers a broad perspective on computer science theory and has inspired some changes to our course for 2025.
• Sipser’s Introduction to the Theory of Computation. The textbook on computer science theory, used in many computer science courses. Not officially available for free, but I bet you can figure out how to find a pdf online.

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.

PrairieLearn homework

Part of your homework grade (at least for the first half of the class) will come from auto-graded “guided” problem sets on a platform called PrairieLearn. You can try these problems as many times as you would like until you get the right answer, because they automatically generate new variations of the problem each time. For some assignments, you will need to complete multiple variations of the same problem to get full credit. Make sure you look at the “Total points” value on the right-hand side of the screen. By completing these assignments before attempting the written homework, you can get feedback about whether you are understanding what we are looking for in the homework. You can access the guided problem sets here. You should select either the “Sign in with Google” or the “Sign in with Microsoft” option. You can log in with any Google or Microsoft email account; your UM email will work as a Microsoft account if you prefer.

Office hours

I have office hours on Mondays from 11-12 and Thursdays from 3:30-4:30 in my office, Social Sciences 420.

Paper/chapter presentation and writeup rubrics

In the second half of the class, on Mondays and Wednesdays we will learn a new advanced algorithm topic and on Fridays 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 Canvas according to these instructions.

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% prairie learn homework problems (during theory portion) (7 assignments)
• 20% written homework problems (during theory portion) (6 assignments)
• 20% paper presentations (during algorithms portion) (each student participates in approximately two)
• 20% paper summaries and problem sets (during algorithms portion) (TBD)

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.