[Home] [Syllabus] [Assignments] [Resources]
Both the midterm and the final exams are open book, open notes.
Note that the date for the midterm exam is set and will not change. If you have a conflict with this date, please let me know right away.
All reading is from Discrete Mathematics with Applications by Susanna S. Epp (3rd edition), unless specified otherwise.
Problem sets are due in the beginning of the class on the due
date. If a problem set is submitted at (or before) the next class meeting
after the due date, it is graded out of 3/4 credit. If it is submitted any
time after the next meeting (until the last class meeting), then it is graded
out of 1/2 credit.
Problem sets submitted more than 2 minutes after beginning of the class
are considered late.
Working in groups helps learning if all students in the group discuss all of the problems and participate equally. It doesn't help you learn if you divide problems among the group members (so that one person works on one problem and another works on another) or if one person does all the work, and the other just puts their name on it. If you feel that group participation is uneven, it's time to talk to your partner(s) and possibly to change your group or to start working individually.
Missed quizzes are counted as 0. The lowest quiz grade in the semester will be dropped (i.e. it will not contribute to overall grade).
Monday | Wednesday | Friday |
---|---|---|
Week 1: August 29 -- September 2 | ||
Introduction, course overview. Logical systems, scientific theories, mathematical models. |
Propositional logic: statements and connectives. Reading: Ch. 1.1 |
Statements and connectives (continue); truth tables Problem set 1: Statements, logical equivalence (due Wedn., September 14th) |
Week 2: September 5 -- September 9 | ||
Labor Day Holiday -- no class |
Logical equivalence. |
Conditional and biconditional statements. Reading: Ch. 1.2 |
Week 3: September 12 -- September 16 | ||
Valid and invalid arguments. Logical deduction. Reading: Ch. 1.3 |
Logical deduction (continue) Problem set 1 due Problem set 2: Logical deduction (due Wedn., Sept. 21) |
Digital circuits. Reading: Ch. 1.4 |
Week 4: September 19 -- September 23 | ||
Digital circuits and number manipulation. Reading: Ch. 1.4 |
Digital circuits and number manipulation (cont.). Problem set 2 due Problem set 3: Digital circuits and number manipulation. (due Wedn., Sept. 28th) |
Introduction to quantifiers and predicates. Reading: Ch. 2.1 |
Week 5: September 26 -- September 30 | ||
Formulas with quantifiers. |
Equivalences of quantified formulas.
Reading: Ch. 2.2. Problem set 3 due Problem set 4: Quantifiers and predicates. (due Wedn., Oct. 5th) |
Equivalences of quantified formulas (cont.) Scope of quantifiers, bound and free variables. |
Week 6: October 3 -- October 7 | ||
Statements containing multiple quantifiers, their equivalences. Equivalences of formulas with multiple quantifiers. Reading: Ch. 2.3 |
Deduction in predicate logic Reading: Ch. 2.4 Problem set 4 due Problem set 5: Predicates and quantifiers. (due Wedn., Oct 12th) |
Deduction in predicate logic (cont.) Reading: Ch. 3.1 |
Week 7: October 10 -- October 14 | ||
Deduction in predicate logic (cont.) Reading: Ch. 3.2, 3.3 |
Deduction in predicate logic (cont.) Reading: Ch. 3.4, 3.6 Problem set 5 due Problem set 6: Deduction in predicate logic (due Mon., Oct. 24th) |
Applications of proofs to algorithms. Reading: Ch. 3.8 |
Week 8: October 17 -- October 21 | ||
Fall break -- no class. |
Review for the exam. |
Midterm exam (includes material up to Friday, Oct. 14th.) |
Week 9: October 24 -- October 28 | ||
Introduction to mathematical induction. Reading: Ch. 4.1, 4.2 Problem set 6 due Problem set 7: Deduction in predicate logic (due Wedn., Nov. 2nd) |
More on mathematical induction. Reading: Ch. 4.3, 4.4. |
Introduction to loops in imperative programming languages. Loop invariants. Reading: Ch. 4.5 |
Week 10: October 1 -- November 4 | ||
More on loop invariants. |
Efficiency of algorithms, Big-Oh notation Reading: TBA Problem set 7 due. Problem set 8: Mathematical induction, algorithm analysis. (due Wedn., Nov. 9th) |
Big-Oh notation (cont.) |
Week 11: November 7 -- November 11 | ||
Introduction to sets, basic concepts of set theory. Reading: Ch. 5.1. |
Set operations Reading: Ch. 5.2, 5.3 Problem set 8 due. Problem set 9: Algorithm analysis, Introduction to sets (due Wedn., Nov. 16th). |
Algorithm analysis (cont.). |
Week 12: November 14 -- November 19 | ||
Introduction to sets, basic concepts of set theory. Subsets, power sets, etc. Reading: Ch. 11. |
Set operations. Reading: Ch. 12 Problem set 9 due. Problem set 10: sets, operations on sets (due Wedn., Nov. 24th) |
Relations (introduction). Reading: Ch. 13. |
Week 13: November 21 -- November 25 | ||
More on relations, Relational databases. |
Properties of binary relations; equivalence relations Reading: Ch. 14 (up to 14.2), 15. Problem set 10 due. Problem set 11: Relations, relational closures, equivalence classes (due Wedn., Dec. 8) |
Thanksgiving -- no class |
Week 14: November 28 -- December 2 | ||
Equivalence classes, relational closures. |
Relational closures (cont.) |
Introduction to graph theory. Reading: handout (given in class) |
Week 15: December 5 -- December 9 | ||
Search algorithms on graphs. Reading: handout (given in class) |
Functions as relations. Reading: Ch. 16. Problem set 11 due. Problem set 12: Graphs, functions (due Wedn., Dec. 15th) |
Function composition. Examples of use of functions. Functional
programming (overview). |
Week 16: December 12 -- December 15 | ||
Catch up and discussion. |
Last day of classes Review and wrap up. Problem set 12 due. |
|
Final exam: Thursday, Dec. 22 8:30-10:30 AM |