[Home] [Syllabus] [Assignments] [Resources and Handouts]

While I try to follow the timeline as closely as possible, keep in mind that topics, dates, and deadlines are subject to change. Changes to deadlines will be announced in class or by e-mail. It is your responsibility to keep up with the changes. If in doubt, please do not hesitate to ask me.

The dates for the midterm and the final are set. If you have any conflicts with those dates, please let me know as soon as possible. No makeup exams will be given unless circumstances beyond your control prevented you from taking the test at the scheduled time AND you have notified me (in person, by e-mail, or by phone) in advance or, if this was not possible, as soon as it became possible.

Both the midterm and the final exams are open book, open notes.

All reading is from Discrete Mathematics with Applications by Susanna S. Epp (3rd edition), unless specified otherwise.

**Late problem sets policy:**
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 5 minutes after beginning of the class
may be considered late.

Working together with other students on problem sets helps you understand the material better. You may hand in group assignments (two students per group). Hand in one assignment from the entire group with names of both students on the first page. Groups are not set in stone for the entire semester, it's perfectly OK to change them or do some problem sets on your own, just make sure to coordinate it with the other person in your group. However, you cannot do a part of a problem set on your own and a part in collaboration or a part in one group and a part in another.

Working in groups helps learning only 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 most of 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.

Discussion with students other than those in your group (or anyone not
in this class) should be limited to general approaches to the
problem. All such discussions as well as use of sources other than the
textbook and the handouts given in class **must be acknowledged**
in the beginning of the problem solution.

Studying in groups is strongly encouraged. You may study for tests, go over textbook materials or lecture notes, and discuss problem sets in general terms (i.e. without actually writing the formulas or giving out the answers).

There will be approximately 7-10 quizzes during the semester. A quiz
will be about 10-15 minutes and will be based on recent material
(including the material of the previous class meeting and the assigned
reading). Quizzes are **open book**: you may use your notes and the
textbook and your notes on a quiz. Quiz
dates will **not** be announced in advance.

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: January 12 - 16 | ||

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 Fri., Jan. 23.) |

Week 2: January 19 - 23 | ||

Martin Luther King Day, no classes |
Logical equivalence. |
Conditional and biconditional statements. Reading: Ch. 1.2 Problem set 1 due Problem set 2: Logical equivalence (cont.) (due Wedn., Jan. 28) |

Week 3: January 26 - 30 | ||

Valid and invalid arguments. Logical deduction. Reading: Ch. 1.3 |
Logical deduction (continue) Problem set 2 due Problem set 3: Logical deduction. (due Wedn., Feb. 4) |
Digital circuits. Reading: Ch. 1.4 |

Week 4: February 2 - 6 | ||

Digital circuits and number manipulation. Reading: Ch. 1.4 |
Digital circuits and number manipulation (cont.). Problem set 3 due Problem set 4: Digital circuits and number manipulation. (due Wedn., Feb. 11) |
Introduction to quantifiers and predicates. Reading: Ch. 2.1 |

Week 5: February 9 - 13 | ||

Formulas with quantifiers. |
Equivalence of quantified formulas. Reading: Ch. 2.2. Problem set 4 due Problem set 5: Quantifiers and predicates. (due Wedn., Feb. 18) |
Equivalence of quantified formulas (cont.) Scope of quantifiers, bound and free variables. |

Week 6: February 16 - 20 | ||

Statements containing multiple quantifiers, their equivalence. Equivalence of formulas with multiple quantifiers. Reading: Ch. 2.3 |
Deduction in predicate logic Reading: Ch. 2.4 Problem set 5 due Problem set 6: Equivalence of quantified formulas (due Wedn., February 25) |
Deduction in predicate logic (cont.) Reading: Ch. 3.1, handout |

Week 7: February 23 - 27 | ||

Deduction in predicate logic (cont.) Reading: Ch. 3.2, 3.3 |
Deduction in predicate logic (cont.) Reading: Ch. 3.4, 3.6 Problem set 6 due Problem set 7: Deduction in predicate logic (due Wedn., March 4) |
Proving correctness of algorithms. Reading: Ch. 3.8 |

Week 8: March 2 - 7 | ||

Introduction to mathematical induction. Reading: Ch. 4.1, 4.2 |
Mathematical induction (cont.). Reading: Ch. 4.3, 4.4. Problem set 7 due |
Mathematical induction (cont.). Problem set 8: mathematical induction (due Friday, March 20th) |

March 9 - 13. Spring break, no classes | ||

Week 9: March 16 - 20 | ||

Review for the exam |
Midterm exam. Covers material up to (including) Monday, March 2nd. |
Introduction to loops in imperative programming languages. Loop invariants. Reading: Ch. 4.5 Problem set 8 due Problem set 9: Loop invariants, efficiency of algorithms (due Wedn., April 1st) |

Week 10: March 23 - 27 | ||

More on loop invariants. |
Efficiency of algorithms, Big-Oh notation Reading: 9.1, 9.2 |
Efficiency of algorithms Reading: 9.3, 9.4 |

Week 11: March 30 - April 3 | ||

Efficiency of algorithms (cont.) Reading: 9.5 |
Introduction to sets, basic concepts of set theory. Reading: Ch. 5.1. Problem set 9 due. Problem set 10: Efficiency of algorithms. (due Wedn., April 8). |
Set operations |

Week 12: April 6 - 10 | ||

Proving properties of sets. Reading: Ch. 5.2, 5.3 |
Relations (introduction). Reading: Ch. 10.1 Problem set 10 due. Problem set 11: sets, operations on sets (due Wedn., April 15) |
Relations (cont.), composition of relations. |

Week 13: April 13 - 17 | ||

Properties of relations; functions Reading: Ch. 10.2, 10.3 |
Relational closures Problem set 11 due. Problem set 12: Relations, relational closures, equivalence classes (due Wedn., April 22) |
Partial order relations Reading: 10.5 |

Week 14: April 20 - 24 | ||

Graphs. Reading: Ch. 11.1, 11.2 |
Graph representations, adjacency matrices Reading: Ch. 11.3 Problem set 12 due. Problem set 13: Partial order relations, graphs (due Wedn., April 29) |
Graph isomorphism; Trees. Reading: Ch. 11.4, 11.5. |

Week 15: April 27 - May 1 | ||

Graph traversals. Reading: TBA |
Catch up and discussion. Problem set 13 due. |
Last day of classes Review and wrap up. Last day to submit any late work. |

Final exam: 1:30-3:30pm Monday May 4th in Sci 3650 |

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.