[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 Nimal Nissanke "Introductory Logic and Sets for Computer Scientists", 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 30 -- September 3 | ||
Introduction, course overview. Logical systems, scientific theories, mathematical models. Reading: Ch. 1, 2. |
Propositions and propositional connectives. |
Propositions (continue). |
Week 2: September 6 -- September 10 | ||
Labor Day Holiday -- no class |
Propositional logic as a language (grammar, semantics).
Reading: Ch. 3. Problem set 1: Propositions (due Wedn., September 15th) |
Truth tables, logical equivalence, logical implications. |
Week 3: September 13 -- September 17 | ||
Digital circuits. |
Logical laws Reading: Ch. 4. Problem set 1 due Problem set 2: formal language of propositional logic, truth tables, digital circuits (due Wedn., Sept. 22) |
Transformational proofs and their applications. |
Week 4: September 20 -- September 24 | ||
Transformational proofs and their applications (cont.). |
Introduction to deductive proofs. Validity, truth tables. Reading: Ch. 5. Problem set 2 due Problem set 3: transformational proofs. (due Wedn., Sept. 29th) |
Proving validity using deductive proofs, inference rules. |
Week 5: September 27 -- October 1 | ||
Reasoning in theories; examples. |
Introduction to predicate logic, its relation to propositional
logic. Reading: Ch. 6. Problem set 3 due Problem set 4: Deductive proofs. (due Wedn., Oct. 6th) |
Quanifiers, unary predicates. |
Week 6: October 4 -- October 8 | ||
Predicates with higher arities, examples. |
Scope of quantifiers, bound and free variables. Reading: Ch. 7. Problem set 4 due Problem set 5: Predicates and quantifiers. (due Wedn., Oct. 13th) |
Comparison with variable usage in programming and mathematics. |
Week 7: October 11 -- October 15 | ||
Interpretation of universal and existential quantifiers (finite model).
Reading: Ch. 8. |
Theorems in predicate logic. Problem set 5 due |
Formulae in propositional form.
Reading: Ch. 9. Problem set 6: Scope of quantifiers, interpretation of formulae. (due Mon., Oct. 25th) |
Week 8: October 18 -- October 22 | ||
Fall break -- no class. |
Review for the exam. |
Midterm exam (includes material up to Friday, Oct. 15th.) |
Week 9: October 25 -- October 29 | ||
Theorems and proofs in predicate logic. Reading: Ch. 9, handout. Problem set 6 due Problem set 7: Proofs in predicate logic (due Wedn., Nov. 3rd) |
More examples of proofs in predicate logic. |
Introduction to loops in imperative programming languages. Loop invariants. Reading: TBA |
Week 10: November 1 -- November 5 | ||
Mathematical induction (introduction). Reading: Ch. 10. |
More on mathematical induction. Problem set 7 due. Problem set 8: Mathematical induction. (due Wedn., Nov. 10th) |
Big-Oh notation, etc. Reading: handouts (given in class) |
Week 11: November 8 -- November 12 | ||
Algorithm analysis. Reading: handouts (given in class). |
Algorithm analysis (cont.).
Problem set 8 due. Problem set 9: Algorithm analysis. (due Wedn., Nov. 17th). |
Algorithm analysis (cont.). |
Week 12: November 15 -- November 20 | ||
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 22 -- November 26 | ||
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 29 -- December 3 | ||
Equivalence classes, relational closures. |
Relational closures (cont.) |
Introduction to graph theory. Reading: handout (given in class) |
Week 15: December 6 -- December 10 | ||
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 13 -- December 15 | ||
Catch up and discussion. |
Last day of classes Review and wrap up. Problem set 12 due. |
|
Final exam: Friday, Dec. 17th, 11am-1pm |