Overall course ELO: Students completing this course should be able to read, write and dissect proofs. They should see the logical underpinnings of a high-level intutitive proof and the differences between a valid and an invalid proof. They will also learn some elementary Discrete Mathematics, including sets, functions, cardinality, induction, recursive equations and simple combinatorics. They will also learn the basics of algorithm analysis including evaluating the complexity of simple iterative (and if time permits, recursive) algorithms.

ELO by chapters and topics:

1. Ch 1: Logic and proofs. This chapter introduces the basics of formal proof techniques. Upon completion, the high-level ELO is that students should be able to prove simple facts and understand the difference between a valid proof and an invalid one. They should understand (and be able to choose from) a set of techniques covered in class. They should also see the role of formal logic in the proofs we cover. More specific ELOs are below.
   • Sec 1.1-1.3: Students should be able to translate English statements to predicates and vice versa. They should be able to prove that 2 statements are (or are not) logically equivalent, e.g. as in Q20, page 35. They should be able to construct and simplify compound propositions, including by using the rules in Table 6, page 27.
   • They should understand the notions of Tautology, Contradiction, Propositional Equivalences and be able to show these hold for given propositions.
   • Sec 1.4-1.5: Students should be able to define and use Predicates, and translate back and forth from English to predicate logic. They should understand the scope of quantifiers, nesting of quantifiers and negation of quantified expressions.
   • Sec 1.6: Students should be able to derive statements using the rules of inference for propositional logic. They should understand and remember the names of Modus Ponens and Resolution. The other rules are intuitive and students should be able to use thm but need not remember the names.
   • Sec 1.7-1.8: Students should know what a logical proof is and what an intuitive proof is. They should be able to see that intuitive proofs are rigorous in that there is a more detailed and completely specified logical proof that can be constructed by filling in all the details if desired. They should understand what axioms, conjectures, definitions are.
   • Students should be able to understand and use (as needed) the different proof strategies taught. They should be able to construct rigorous proofs for simple statements. They should have some idea of the role of proofs in program correctness, algorithm design, inference and planning.
2. Ch 2: Sets, functions, sequences, sums (omit 2.6: Matrices)
3. Ch 3: Algorithm analysis and complexity.
4. Ch 5: Induction and recursion.
5. Ch 6: Counting Techniques (omit 6.5, 6.6).
6. Ch 8 Advanced counting techniques (8.1 - 8.3) - as time permits.