Schedule

Problem Set 5 is due Friday at 6:29pm.

Thursday’s Class may include review for Exam 1. Before 6:59pm Wednesday, send me topics you would like to review:

• fewer than 10 total requests: class is not being sufficiently challenged and we should be doing more difficult material (except for the 10 requestors who get exam exemptions).
  
• exactly 10 total requests: all requestors get automatic exam exemptions, review requested topics.
  
• more than 10 requests implies we should spend Thursday’s class on reviewing requested topics, no exam exemptions.

Friday, 3:30pm (Rice Hall Auditorium): Eva Tardos (Cornell University), Learning and Efficiency of Outcomes in Games. (She could definitely help you answer questions 7-9 on PS5!)

Exam 1

Exam 1 will be in class on Thursday, 6 October.

Resources. You will be permitted to use a single paper page of notes that you prepare and bring to the exam. It is fine to collaborate with others to prepare your notes. The page should be no larger than a US Letter size page ($8.5 \times 11$ inches), and you may write (or print) on both sides of the page. No other resources are permitted during the exam.

Content. The problems on the exam will cover material from Classes 1–11, Problem Sets 1–5 (including the provided solutions), and MCS Chapters 1–5. Everything on the exam will be something you have seen in at least two of these (Classes, Problem Sets, and MCS Book), and most of the exam will be things you have seen in all three. If you understand the problems on the problem sets and questions on the class notes well enough to be able to answer similar questions, you should do well on the exam.

The main topics the exam will cover include:

• Propositions, axioms, and proofs (you should understand what each of these are and how to define them precisely)

• Inference rules (how to determine and show if an inference rule is sound or unsound, how to correctly use inference rules in a proof)

• Logical formula (how to interpret logical formulas and convert English statements into logic, determine the validity or satisfiability of a formula, and show equivalence or non-equivalence of two formulas)

• Logical quantifiers (how to reason about logical formula using $\forall$ and $\exists$, including showing logical equivalence and implication)

• Proof methods (you should be able to read and write proofs that use direct proof, contrapositive proof, and proof by contradiction)

• Well ordering (you should be able to explain what it means for a set to be well ordered, determine if a given set and operator is well ordered, and be able to construct proofs using the well ordering principle and identify flaws in misuses of the well ordering principle)

• Induction (you should understand mathematical induction and be able to construct proofs using induction and identify flaws in misuses of induction in proofs)

For most students, I believe the best way to prepare for the exam will be to (1) go over the problem sets and their solutions, and make sure you understand well any of the problems you did not get before; (2) go through the questions in the class notes and convince yourself you can answer them well; (3) re-read chapters of the book, solving the associated practice problems, especially for any sections on topics where you had difficulty on the problem sets. If you do #1 and understand well the problems on the problem set, you should be confident you’ll do well on the exam; if you struggled on the problem sets, you would benefit from doing #2 and #3 as well.