### CSE 240: Logic and Discrete Math, Fall 2014

## Lectures:Tuesday/Thursday, 11:30-1:00pm, Room: Wilson 214## Professor:Robert PlessOffice Hours: Thursday 1:30-2:30pm, Jolley 404 ## TAs and Office Hours:Office hours are in Jolley 431 Conference room, unless otherwise noted. Joseph O'Sullivan, osullj@wustl.edu, Monday 6-8pmEileen Duffner, eduffner@wustl.edu, Tue/Thur, 10-11am Christine Lucky, c.e.lucky@wustl.edu, Tuesday 1-2, Friday, 12-1 Kevin Hays, k.t.hays@wustl.edu, Wed/Fri 3-4 Jack MacCarthy, Monday 2:30-3:30, Friday 1-2 ## Textbooks:The best book that I have ever found for this class is: "Discrete Mathematics with Applications" by Susanna S. Epp. Last year when I required this book for the class, the bookstore charged over $300 for it, and the rental was also absurd. I refuse to support such ridiculous pricing, especially for a subject area that has not changed in 100 years. So, I strongly recommend that you buy the book used from Amazon and there are suggested readings in the syllabus below, but there will be no assigned problems directly from the book. Links: Amazon page, amazon used book page.## Grades:A final exam will be worth 25% of the grade.Two in class midterms will each be worth 20% of the grade. Exams are closed book/closed notes but "Open Chalkboard" Homeworks will 35%. Grade cut-offs will not be harsher than: 90% of total possible will give a grade of A- or better. 80% of total possible will give a grade of B- or better. 70% of total possible will give a grade of C- or better. |

#### Announcements:

- Alternate Exam (Dec. 9, 11:30-1:30) Sign Up. Exam Location: Lopata 101.
- Sample Final
Exam here,
and solutions
are here.
Some fixes to those solutions:
- Problem 1a: The transitive closure should also include: (2,4), (3,4), (2,3)
- Problem 1.d.ii should read (10 choose 2) / (50 choose 2)
- Problem 5d: The starting state needs a an arrow to itself labelled "0".

- Google Doc Shared Cheatsheet

#### Approximate Syllabus:

There are suggested readings from the suggested textbook. The best sections to read are indicated with [], and should be read*before*the lecture.

- Lecture 1: Logic, Propositions, Connectives and Truth Tables, Reading: [1.1, 2.1] from recommended textbook, and/or Pages Lo 1- Lo 8 from: Arithmetic Logic and Numbers
- Homework 1 Due Thursday, Sept. 4,
beginning of class:
- Homework 1, and
- its LaTex source.
- Also, for reference are the solutions to the practice problems here,
- and the latex source for those practice solutions here.

- Lecture 2: Connectives, Propositional Equivalence, All you need is NAND, LaTeX. Reading: [2.2]. Comic!
- Lecture Notes: A bunch of propositional equivalences that you can use for proving two statements are equivalent
- Notes: Rules of Inference, Predicates and Quantifiers [2.3].
- Homework 2 Due Thursday, Sept. 11,
beginning of class.
- Homework 2, and
- its LaTex source.
- Solutions to the some of practice problems here (this is from last year so the "to turn in problems" are different).
- Solutions to the "turn in" problems here

- Lecture 4: Predicates and Quantifiers[3.1, 3.2, 3.3]
- Lecture 5: Direct Proofs, Indirect Proofs, and Proofs by Contradiction Reading: [4.1-4.3]
- Notes:, In class audio-visual experience Indirect proofs and proofs by contradiction. [4.1-4.5 (yes, i know it is a lot of reading)].
- HOMEWORK 3... Homework 3, its LaTex source.
- Homework 3 Solutions pdf, and as latex source, and, finally, solutions to the practice problems.
- Tuesday September 16 More proofs, non-constructive proofs, intro to induction [4.6, 4.7]
- Mathematical Induction II (ppt) [5.2-5.4]
- Mathematical Induction III [5.4]
- HOMEWORK 4... DUE AT BEGINNING OF CLASS, Sept. 30 Homework 4, its LaTex source, and its solutions, and solutions to the practice problems.
- Notes Program Correctness 1
- Notes Program Correctness 2
- Exam 1, October 2.
- Do you want lots of possible example problems? This is a compendium of hundreds of problems and solutions (link). Best problems are in Chapters 2.4, 2.5, and 2.6, and 5.1.1 and 5.1.2.
- Comments as I grade the test: Proof by contradiction VS. Proof of the Contrapositive on the sqrt(x) problem.

- Notes on recursive definitions.
- HOMEWORK 5... DUE AT BEGINNING OF CLASS, October 17 (typo corrected, Oct. 9, 7:11pm) Homework 5, its LaTex source, and its solutions.
- Notes on Sets and Cardinality
- Functions and sizes of large sets Approx. Notes
from Todd's Lecture.
- My notes on related topics: here.

- Counting Sum and Product Rule Todd's Lecture Notes
- Explanation of this xkcd comic strip, and a TED TALK by Wash U. alumna Lorrie Cranor.
- HOMEWORK 6... DUE AT BEGINNING OF CLASS, October 28 Homework 6, its LaTex source, and with complete solutions here
- Notes More Counting [9.5-9.7]
- Notes Recursive and explicit formulas for sequences [5.6-5.9]
- Notes Series, summations, Ramsey numbers, and other "Embarrassing" open problems in maths.
- Exam 2, November 4
- Notes: Intro to Probability [9.8-9.9], and Notes: Conditional Probability, Health, and SPAM. Also, nerdy xkcd joke
- Notes Relations and Representing Relations [8.1, 8.2]
- HOMEWORK 7... (NOW due Nov. 20)Homework 7, its LaTex source, and solutions to some problems of the practice problems: here, and complete solutions to the homework.
- Notes Equivalence Relations, Total Orders, Partial Orders [8.3, 8.5]
- Notes Graphs [10.1, 10.2]
- Notes Graphs II, Euler Tours and Rubiks Cubes [10.3, 10.4]
- Audio-Visual Adventures
- graph cut 2
- HOMEWORK 8... (due
Dec. 2)Homework
(pdf),
and Homework
(TeX),
and solutions to
homework 8. These solutions have a few errors (sorry!):
- The Hasse Diagram from 1(a) forgot lines from 1 up to 6 and 1 up to 8.
- The minimal and maximal elements lists are backwards, and the
minimal elements should NOT include 6 or 10. So the correct answer
for 2b is:
- Maximal elements are: 3,5,7,9,4,6,8,10
- Minimal elements are: 1,2,3,5,7,9

- HOMEWORK CLARIFICATION: A "total order consistent with a partial order" is an ordered list of all the elements of the set, where IF x comes before y in the ordered list, then (y,x) is not in the partial order. Another way to say this is: "every order produced by a topoligcal sort is a total order consistent with a partial order". Page 5-7 of the following site gives a concrete example of this: http://web.mit.edu/neboat/Public/6.042/relations.pdf.
- Notes Using Finite State Machines and DFAs to Model Computation [12.2 (but read 12.1 also)].
- (minimal) notes Travelling Salesmen and Locker Rooms [No specific book section]
- Alternate Final Exam, Closed Book/Notes, Open Chalkboard, Dec 9 2014 11:30AM - 1:30PM.
- Final Exam, Closed Book/Notes, Open Chalkboard, Dec 15 2014 1:00PM - 3:00PM