Final exam study guide

The final exam is cumulative. The material since the second prelim will be emphasized slightly more than the other material in the course.

Here are some sample questions from previous semesters (solutions). As usual, different topics have been emphasized to different extents in other semesters.

Reviewing the prelims and homeworks will also be helpful.

Topics since Prelim 2

Here are the new topics since prelim 2; see also the prelim 2 study guide and the prelim 1 study guide. The list is potentially incomplete; everything covered in the lecture or homework is fair game.

Automata and regular expressions

Strong induction

Number theory



Some of the basic material on graphs will be in scope. I will update this section after this week's lectures to clarify.

Update: Know the following definitions: