COMP 1002 -- Introduction to Logic for Computer Scientists, Winter 2017
- 14/4/2017 Just to confirm -- if you are happy with your practice exam mark, you don't need to come to the final exam, I will just use your practice exam mark in the calculation. If you do come, I will take the maximum of the two.
- 13/4/2017 If you have made special arrangements with me during the semester (e.g., if you were sick for a lab), I have noted that on D2L in the "notes" section. If you did email me and it is not reflected there, please let me know as soon as possible (before the exam). I cannot make any new arrangements for the work missed during the semester, sorry.
- 13/4/2017 I will have office hours tomorrow (Friday) from 1pm to 3pm. This will be the last office hours before the final exam on Saturday morning.
- 11/4/2017 A self-assessment is now set up which gives a random question from each lab. Please use it for preparing for the final exam, to review lab questions.
- 9/4/2017 I will hold office hours on Wednesday, April 12, from 1pm to 4pm. Please let me know if you cannot make this time slot. Hopefully all the marking will be done by then, and I will be able to return your practice exams.
- 9/4/2017 The assignment 4 was marked harsher than I intended. Since it seems that people lost on average 3-4 points, I will add 5 points to everybody's mark (everybody who submitted, that is). This will be done as the final mark is calculated (harder to set it up in D2L).
- 3/4/2017 Here is a study sheet for the exams. As before, this is just to help you study, not to use during the exams (which are closed-book). Please let me know if you notice any mistakes or omissions!
- 3/4/2017 A small clarification on 3b: when n=1, you have 6 tuples: (0,0,0,0,0), (0,0,0,0,1), (0,0,0,1,1), (0,0,1,1,1), (0,1,1,1,1) and (1,1,1,1,1).
- 3/4/2017 Looks like our lecture today is cancelled... Please still take some time to go over the mini-lab and try the "self-assessment" (instead of a quiz), to prepare for the exams. I will go over assignment solutions tomorrow in the lecture, and will have office hours after tomorrow class.
- 2/4/2017 Please fill the course evaluations, especially the comments! As this is the first time we offer this course, it would be really useful to know what worked and what did not, what was good and what should be done differently next time. Were the labs useful; which ones were better and which ones were worse? Should we spend more time explaining some topics? Any other suggestions?
- 2/4/2017 Plan for next week:
- Monday, April 3rd: "mini-lab" (during the lecture, lecture time and place), answers to questions.
- Tuesday, April 4th: review for exams.
- Wednesday, April 5th: practice exam (in the lab, CS-1019 for everybody, 9am-11am).
- 30/3/2017 By popular demand, assignment 5 is due on Monday, April 3rd, at 7pm.
- 28/3/2017 A typo in 3c is fixed. Please use the updated version of Assignment 5 !
- 28/3/2017 To avoid ambiguity, question 3b in Assignment 5 has been rephrased as follows: given a natural number n, compute the number of 5-tuples of natural numbers (i,j,k,l,m), where i,j,k,l,m are all between 0 and n (inclusive), and are always in non-decreasing order (that is, j is at least i, k is at least j, etc, and m is at most n).
- 23/3/2017 Assignment 5 is now posted. Due April 2nd, 7pm.
- 23/3/2017 Assignment 4 is now due by Saturday morning, 7am.
- 16/3/2017 On Monday, March 20th, my office hours will be from 2:30pm to 3:30pm. If you would have liked to come, but cannot make it, please email me.
- 13/3/2017 Assignment 4 is now posted. Due March 23th.
- 13/3/2017 Assignment 3 is now due on Tuesday, March 14th (due to the power outage over the weekend).
- 3/3/2017 Assignment 3 is now posted. Due March 13th.
- 2/3/2017 Today is the final drop date. If you have any concerns about your mark, please talk to me after the midterm -- we will look at your midterm together, to get a better sense for where you are.
- 2/3/2017 Midterm test is today! Usual time and place (same as the lecture). See you there!
- 1/3/2017 All assignments 1 and 2 are marked. Please email me if there is any problem, and make sure to read the feedback before tomorrow midterm!
- 1/3/2017 I have posted slides for the lecture we did not have the time to do on Tuesday. There are pretty much only definitions. Please read them on your own, and if you have questions, please ask -- we will work on this in the next lab.
- 25/2/2017 I do not plan to post answers to the sample midterm, since everybody's answers would be different, and it would be misleading to have one "correct" solution. I will be happy to go over it in class and look at your answers.
- 25/2/2017 Here is a study sheet for the midterm. Note: this is only to help you study, *not* to use during the midterm itself.
- 18/2/2017 Here is a sample test from a related course. Since in that course we had a test after every assignment, it only covers the material for assignment 1; we covered some extra topics in that course such as circuits. Our midterm will cover assignments 1 and 2, and labs 1 through 5 (that is, lectures 1-16).
- 18/2/2017 Lab 5 will be moved to March 1st (weather permitting).
- 16/2/2017 By popular demand, assignment 2 due date has been moved to Monday, Feb 20th, 7pm. I plan to be out of town though, so if you have questions, please email me and I will reply when I can.
- 7/2/2017 The slides that were supposed to be for today's lecture are now posted. I did not go through all the material, but I will only do the last proof (by contradiction) and the puzzle in the next lecture. Please use the rest as a reference for a few more examples of proofs.
- 6/2/2017 The exercises for lab 4 are now posted.
- 5/2/2017 Assignment 2 is now posted. Due Feb 17th.
- 31/1/2017 As decided in class today, midterm is tentatively scheduled for March 2nd. Also, the remaining assignments will be each split in two, so we will have assignment 2,3,4 and 5 each worth 5%.
- 26/1/2017 If you are doing your assignment 1 in LaTeX, you are welcome to start with the source file and modify it. For drawing resolution proofs, here is a beautiful example with tikz-qtree package. If you need a LaTeX compiler, the simplest way is to use an online one, such as ShareLaTeX. Just load the source file and start adding your solutions.
- 30/1/2017 The exercises for lab 3 are now posted.
- 23/1/2017 The exercises for lab 2 are now posted.
- 22/1/2017 A correction for assignment 1, question 1d and 1g: as the variant with "either COMP 1002 is not a prereq or logic is studied in COMP 1002" was causing confusion on question 1g, it has been changed, in 1d, to "both COMP 1002 is not a prerequisite for COMP 2002 and logic is studied in COMP 1002". Please see the new version of assignment 1.
- 19/1/2017. The assignment 1 is now posted. Due Feb 6, 7pm on D2L. Please see below for more information, and email me if you have any questions.
- 16/1/2017 The exercises for Wednesday lab are now posted. If you have a time conflict at 11am (and will be doing the lab in EN-1049), do the "Individual work" part before coming to the lab at 9am on Wednesday. If you are in the main section, you can do all exercises during the lab, both individual and group part.
The quiz will be roughly within the last half an hour of your lab, on D2L. All the work other than the quiz should be done with pen and paper; please bring some paper with you to the lab.
- 15/1/2017 The first lab is this Wednesday, Jan 18th, at 9am. If you have a time conflict at 11am, please go to EN-1049. That lab will be shorter, so you will have to do the first part at home. If you do not have a time conflict at 11am, please go to CS-1019. If you do have a conflict and were not in class when I asked for the number of people who need to leave earlier, please email me right away (to make sure everybody gets a place in a lab).
- 5/1/2017 As decided in class today, office hours will be on Mondays and Thursdays after class (2pm-3pm).
- 4/1/2017 The first lab is planned for Jan 18th. Lectures start on Jan 5th.
- 4/1/2017 If you have questions about registration, please contact our undergraduate advisor, Donna Batten at [Your browser cannot view this email address] .
Lectures: Monday, Tuesday and Thursday, 1pm-1:50pm in EN-2007
Labs: Wednesday 9am-11:50am at CS-1019 (section 1) and EN-1049 (section 2).
Kolokolova , email: [Your browser cannot view this email address] , office ER-6033.
Instructor office hours: Monday and Thursday 2pm-3pm.
Textbook: There will be no textbook for this course; lecture materials will be posted online.
- Discrete Mathematics With Applications: Susanna S. Epp
- Discrete Mathematics and Its Applications: Kenneth H. Rosen
Marking scheme ( tentative! ):
Lab quizzes 25% total (lowest mark dropped), 3 assignments of 10% each, a midterm test 15% and a final exam 30%. Note
that the last assignment may be due during the last week of the
semester (to provide adequate preparation for the final exam).
Tentative course description
Logic has been called the "calculus of computer science": just as sciences
such as physics that deal with continuous realm rely on calculus techniques,
we rely on logic. Indeed, so many areas of our field are based on logic: from
designing circuits to determining complexity of problems; from verifying
correctness of algorithms and devising database queries to automated
reasoning in artificial intelligence.
This course is intended to be an introduction to mathematical logic with
emphasis on Computer Science applications and methodologies. We will cover propositional
and predicate logic with applications to Boolean circuits and database querying,
respectively; that will also cover Resolution proof technique, which is the
basis of most modern-day automated problem solvers. Then we will discuss basic
proof techniques such as mathematical induction, again with computer science
applications including proving algorithm correctness. We will also touch upon basic combinatorics and counting methods.
- Lab 1: Jan 18th
- Lab 2: Jan 25th
- Lab 3: Feb 1st
- Lab 4: Feb 8th
- Lab 5: Feb 15th (moved to Mar 1st)
- Lab 6: Mar 8th
- Lab 7: Mar 15th
- Lab 8: Mar 22nd
- Lab 9: Mar 29th
- Mini-lab: Apr 3rd
Please type up your assignment and upload it on D2L as a pdf file. If you know how to use LaTeX (or want to learn an easy way to typeset mathematics), this would be a perfect choice; otherwise, use whichever word processor you are comfortable with.
Policy on collaboration: The work you submit must
be your own. You may discuss problems from assignments with each
other; however, you should prepare written solutions alone.
Plagiarism is a serious academic offense and will be dealt with
I will be posting lecture materials as we go; you are welcome to check the lecture notes from a related course.
- 5/1/2017 Lecture 1: Introduction
- 9/1/2017 Lecture 2: Language of logic, truth tables
- 10/1/2017 Lecture 3: Knights and knaves, negation, de Morgan's laws
- 12/1/2017 Lecture 4: Negation, de Morgan's laws, simplifications
- 16/1/2017 Lecture 5: More on simplifications, equivalences
- 17/1/2017 Lecture 6: Implications, contrapositive, converse, inverse
- 19/1/2017 Lecture 7: Natural deduction, arguments, validity, modus ponens
- 23/1/2017 Lecture 8: Resolution, CNFs, million dollar problem
- 24/1/2017 Lecture 9: Formulas vs. circuits, canonical CNF/DNF, complete set of connectives
- 26/1/2017 Lecture 10: Sets, predicates, quantifiers
- 30/1/2017 Lecture 11: Mixed quantifiers and negation, prenex normal form
- 31/1/2017 Lecture 12: Theorems, theories, axioms, counterexamples
- 2/2/2017 Lecture 13: Rules of inference in predicate logic, universal modus ponens, instantiation/generalization
- 7/2/2017 Lecture 14: Types of proofs, modular arithmetic
- 9/2/2017 Lecture 15: Square root of 2 is irrational, operations on sets
- 13/2/2017 Lecture 16: Cardinalities, powersets, cartesian product, laws of set theory, Boolean algebra
- 16/2/2017 Lecture 17: Relations and functions
- 27/2/2017 Lecture 18: Countable and uncountable sets, diagonalization, Halting problem
- 28/2/2017 Lecture 19: Properties of binary relations, equivalences, orders
- 6/3/2017 Lecture 20: Well-ordering principle, sum and product notation
- 7/3/2017 Lecture 21: Mathematical induction, strong induction
- 9/3/2017 Lecture 22: Recurrences, progressions, fractals and white horses Fractal grower
- 13/3/2017 Lecture 23: Recursive definitions of sets, trees. Grammars.
- 14/3/2017 Lecture 24: Structural induction
- 16/3/2017 Lecture 25: Regular expressions, finite automata, Turing machines Conway Game of Life (select longer delay and rainbow colour to see more clearly; rules are under the applet).
- 20/3/2017 Lecture 26: Combinatorics: rules of sum and product
- 21/3/2017 Lecture 27: Permutations and combinations
- 23/3/2017 Lecture 28: Binomial theorem, Pascal triangle, probabilities
- 27/3/2017 Lecture 29 Distributions, birthday paradox, conditional probability, Bayes theorem
- 28/3/2017 Lecture 30 Expectation, Bernoulli trials
- 30/3/2017 Lecture 31 O-notation, solving recurrences, Master theorem.