Week 15 Review and Final Exam

Review Session

Run by course staff.

Optional

Friday (May 8th) 5-8pm in Siebel 0216.

Studying for the final Exam

Look through main proof types (see below) and the open-answer rubrics from previous examlets.

Look through the skills lists and review topics that no longer seem familiar, or where you remember being confused earlier in the term.

Try to get enough sleep, enough food.

Final Exam

Format

• 2-4 open answer questions
• 10-15 multiple-choice questions

Length

• Previous examlets took about 35 minutes to finish and then there was 15 minutes of slack.
• Working time for the final is about 2.5 times that of earlier examlets, plus about 20 minutes of slack.
• 110 minutes in the CBTF.

Save, save, save because PrairieLearn doesn't.

The open answer questions

• Expect a tree induction question
• No new rubrics, which means no new general types of open-answer questions
• No inequality direct proof
• Not more than 3 long proofs.
• 4 questions would involve a couple short answer questions.

No DFA builder question, but there could be multiple-choice questions about state machines.

Multiple-choice questions

• New topic: countability
  • Expect several questions, more than an earlier topic but not a huge fraction of the exam.
• Otherwise a broad sampling of questions from the whole term

Specific questions?

• No clue.
• Questions on the final exam come from big pools.
• Carl and Margaret are still finalizing what's in some of the pools.

Proof Techniques

• Direct proof
  • Cases
  • Contrapositive
  • Disproof by concrete counter-example
• Direct proof for particular situations
  • One-to-one
  • Onto
  • Set inclusion
  • Inequality
• Contradiction
• Induction
  • Simple
  • Recursively defined functions
  • Trees
  • Strings, graphs, etc