SP19:Prelim 1 guide

From CS2800 wiki

Updates: I've added a note to the list of all proofs below, and to the number theory section.

Update: Here are the board notes from the first review session. Review 2 board. The video is here.

Prelim 1 will cover material all material covered in lecture and the homework up to and including material covered on Friday 3/1. Material that you've had homework problems on will be stressed more heavily. The exam will be closed book, closed notes, and will be 90 minutes long.

Here are some questions from past prelims. These questions are 10-15 minute questions; I would expect 4-7 of them on an exam. (Solutions)

Here is a brief summary of what we've covered; for an exhaustive list see the Main Page.

  • Be able to prove and apply the following basic results from number theory
    • Euclidean division algorithm
    • Base b representation (be able to represent a number in base b and interpret a sequence of digits as a number)
    • Update: GCD algorithm (Update: don't worry about memorizing the gcd algorithm; however the proofs of correctness are a good example of strong induction proof, so you can treat them as good practice problems)
    • Update: (depending how far we get Friday: computing Bézout coefficients; we didn't cover this)