COMP 1002 -- Introduction to Logic for Computer Scientists, Winter 2019
- 10/4/2019 Practice exam marks are now posted, sorry for the delay. Please let me know right away if you do not see yours. (Just to confirm -- if you are happy with your practice exam mark you do not need to come to the final exam. If you come to both I'll take the maximum of the two.) I will have office hours tomorrow 3:30-4:30pm, you are welcome to come and get your practice exam then, and ask me any questions you still have.
- 9/4/2019 I will have office hours tomorrow (Wednesday), 3-5pm. As for the exam, I am still marking, hope to be done by the office hours tomorrow -- sorry for the delay!
- 2/4/2019 Study sheet for the exams is now posted. Remember that it is just to help you prepare for the exams; the exams themselves are closed-book no-aids-allowed.
- 28/3/2019 Clarification on question 1d on assignment 6: the restriction about routers not next to each other applies just to the two router shelves on the same rack. Routers on the other rack could be in the same places as on the first. So if the first rack has routers on shelves 2 and 5, the second can also have them on 2 and 5, or on 3 and 5, or 4 and 6, etc...
- 27/3/2019 Next week there is no lab on Monday. Instead, everybody is welcome to come to the practice exam on Wednesday, 9-11am, in the lab. The practice exam is optional, however I will mark it and take the maximum of your practice exam and the actual final exam mark. The exam is "no-aids-allowed" (closed-book); just bring your ID and some pens/pencils/erasers.
- 24/3/2019 Assignment is now posted. Due April 1st, 10pm.
- 13/3/2019 I will be out of town all of next week (16th to 24th). There is still a lecture on Monday, March 18th, taught by Elham Karimi. There will be no office hours; please ask the TAs and the lab instructors during the labs, or email me if you have questions. There will be labs, as normal.
- 13/3/2019 Assignment 5 is now posted. Due March 21, 10pm.
- 3/3/2019 Assignment 4 is now posted. Due March 12, 10pm.
- 27/2/2019 The office hours on Thursday, Feb 28 will move to 3:30-4:40pm (I need to be at a departmental event 2:30-3:30pm).
- 26/2/2019 A sample midterm is now posted. Note that it covers somewhat different material, and based on different assignments -- ours will be based on the first 3 assignments and first 4 labs.
- 16/2/2019 A study sheet for the midterm is now posted. Use it to prepare for the midterm on Feb 28th. The midterm is no-aids-allowed though, so you would not be able to use this study sheet during the midterm itself. We will have a review for the midterm in Feb 26th lecture.
- 8/2/2019 As discussed in class, we are implementing the following late assignment policy. For every assignment there will be 12 hours after the deadline when assignments would still be accepted, but the marks will be decreased by 10% of the total mark. After this 12-hour period, no assignments will be accepted. If there are several submissions, only the latest will be considered.
That is, if the deadline is at 10pm on Saturday evening, you can submit with no penalty until this time. Assignments submitted between 10pm Saturday and 10am Sunday morning will have the mark decreased by 10% of the total mark, e.g. by 10 points on a 100-point assignment. After 10am Sunday, we would not accept any assignments. So an assignment that would get 80/100 points when submitted at 9pm Saturday, if submitted at 9am Sunday would get 70/100, and get 0 (not accepted) if not submitted by 10am Sunday.
- 7/2/2019 Assignment 3 is now posted. Due Feb 16th, at 10pm. Type it up and upload on D2L.
- 26/1/2019 Assignment 2 is now posted. Due Feb 5th, at 10pm. Type it up and upload on D2L.
- 17/1/2019 As agreed in class, the midterm test will be on Feb 28th.
- 22/1/2019 See this page for a tutorial on how to do tables in LaTeX
(just take the code for the second or third example and start editing). In Markdown, see e.g.
this Github Markdown cheatsheet .
In EazyTeX, builtin tables seem to be not quite working: either switch to the expert mode and edit LaTeX directly, replacing dots by formulas in dollar signs, or use something
like Markdown syntax.
- 18/1/2019 To enter math in LaTeX, Markdown or HTML, just remember that every equation (even a single symbol) should be between two dollar signs (
see the source for examples.) The symbols that you need should all be in the file already, but here is the list of names:
$\wedge$ is \wedge, $\vee$ is \vee, $\neg$ is \neg, $\to$ is \to, $\leftrightarrow$ is \leftrightarrow, and $\equiv$ is \equiv.
- 15/1/2019 Assignment 1 is now posted. Due Jan 24th, at 10pm. Type it up and upload on D2L.
- 14/1/2019 By popular demand, we are changing our marking scheme from 5 assignments at 6% each, to 6 (smaller) assignments 5% each.
- 14/1/2019 Lab 1 is posted. Please try to do the individual part of the lab before coming to the lab itself (of course, you can still ask me/TAs/lab instructor questions about that part in the lab, and/or in classes, or email me).
- 9/1/2019 On Monday, Jan 14 we will have an extra class from 10am to 12pm in room C 3033 (Chemistry building). This is to make up for the time in March when I will be away for a conference.
- 9/1/2019 The labs will start on Jan 21/23.
- 7/1/2019 As discusses in class, office hours will be 2:30pm-3:30pm on Tuesdays.
- 6/1/2019 There will be no labs the first week of classes (Jan 7th and 9th). I will post the lab start dates later on Monday.
- 2/1/2019 There will be no class on Thursday, January 3rd (flights to St. John's cancelled due to weather).
- 2/1/2019 If you have questions about registration, please contact the department or the registrar's office. I have no control over the registration, and would not be able to help you with it, sorry!... All the course materials will be posted here in the open access.
http://www.cs.mun.ca/~kol/courses/1002-w19 . Also see Brightspace (D2L) .
Kolokolova , email:[Your browser cannot view this email address] , office ER-6033.
Lectures Monday, Tuesday and Thursday, 1pm-1:50pm in EN 1054
Labs: Monday (section 1) / Wednesday (section 2) 9am-11:50am in CS-1019.
Instructor office hours: Tuesday/Thursday 2:30pm-3:30pm, in ER-6033.
Textbook: (not required) Discrete Mathematics and Its Applications: Kenneth H. Rosen.
Discrete Mathematics With Applications: Susanna S. Epp
Lab quizzes 24% total (lowest mark dropped), 6 assignments of 5% each, a midterm test 15% and a final exam 31%. Note
that the last assignment may be due during the last week of the
semester (to provide adequate preparation for the final exam).
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, including the 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. We will also touch upon basic combinatorics, counting methods and probability, and theory of computation.
Labs start on Jan 21st (Section 2) and Jan 23rd (Section 1). Every lab will end with a quiz; the lowest quiz mark will be dropped. You have to be in the lab to write the quizzes.
Assignment 1. ( LaTeX , EazyTeX , Markdown , HTML ) Due Jan 24, at 10pm.
Assignment 2. ( LaTeX , EazyTeX , Markdown , HTML ) Due Feb 5, at 10pm.
Assignment 3. ( LaTeX , EazyTeX , Markdown , HTML ) Due Feb 16, at 10pm.
Assignment 4. ( LaTeX , EazyTeX , Markdown , HTML ) Due March 12, at 10pm.
Assignment 5 ( LaTeX EazyTeX , Markdown , HTML ) Due March 21, at 10pm.
Assignment 6 ( LaTeX EazyTeX , Markdown , HTML ) Due April 1, at 10pm.
Please type up your assignments and upload them on Brightspace (D2L) as a pdf file; please also
upload your source file.
There are four source files that you can start with: LaTeX, EazyTeX, Markdown and HTML. I typeset assignments in LaTeX; Overleaf is a good online editor for LaTeX. If you prefer a more WYSIWYG interface, EazyTeX is a new lightweight LaTeX editor designed for students; use the EazyTeX source file there and check D2L for the EazyTeX license for our class. If you want something intermediate, Markdown is a popular language (used e.g. for Github documentation), and it can handle LaTeX-style mathematics; StackEdit is a nice online Markdown editor which can handle LaTeX-style mathematics. Finally, HTML supports LaTeX-style math (with "MathJax" script), as in the source.
Late assignment policy: For every assignment there will be 12 hours after the deadline when assignments would still be accepted, but the marks will be decreased by 10% of the total mark (e.g. a 100-point assignment will receive 10 points less if submitted within 12 hours after the deadline). After this 12-hour period, no assignments will be accepted. If there are several submissions, only the latest will be considered.
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 slides as we go; you are welcome to check the slides and other materials from the previous semester.
Here is the A study guide for the midterm and for the final exams
Here is a guide from a famous mathematician Polya on how to approach solving problems.
- 7/1/2019 Lecture 1: Introduction
- 8/1/2019 Lecture 2: Language of logic, truth tables, order of precedence, parse trees
- 10/1/2019 Lecture 3: Knights and knaves, negation, de Morgan's laws
- 14/1/2019 Lectures 4-5: Simplifications, equivalences, contrapositive/converse/inverse
- 14/1/2019 Lecture 6: Natural deduction, valid arguments, rules of inference
- 15/1/2019 Lecture 7: Resolution, million dollar problem
- 17/1/2019 Lecture 8: Pigeonhole principle, Resolution, CNFs
- 21/1/2019 Lecture 9: Formulas vs. circuits, canonical CNF/DNF, complete set of connectives
- 22/1/2019 Lecture 10: Sets, predicates, quantifiers
- 24/1/2019 Lecture 11: Mixed quantifiers and negation, prenex normal form
- 28/1/2019 Lecture 12: Theorems, theories, axioms, counterexamples
- 29/1/2019 Lecture 13: Rules of inference in predicate logic, universal modus ponens, instantiation/generalization
- 31/1/2019 Lecture 14: Types of proofs, modular arithmetic, direct proofs and proofs by contraposition
- 4/2/2019 Lecture 15: Proofs by cases, square root of 2 is irrational
- 5/2/2019 Lecture 16: Infinitely many primes, operations on sets, cardinalities.
- 7/2/2019 Lecture 17: Inclusion/exclusion, powersets, cartesian product, laws of set theory, Boolean algebra
- 11/2/2019 Lecture 18: Relations and functions
- 12/2/2019 Lecture 19: Countable and uncountable sets, diagonalization, Halting problem
- 14/2/2019 Lecture 20: Properties of binary relations, equivalences, orders
- 4/3/2019 Lecture 21: Well-ordering principle
- 5/3/2019 Lecture 22: Mathematical induction, strong induction
- 7/3/2019 Lecture 23: Strong induction (product of prime powers), recursive definitions, arithmetic/geometric progressions.
- 11/3/2019 Lecture 24: Recursive definitions of sets, fractals, trees. Grammars. Fractal grower
- 12/3/2019 Lecture 25: Structural induction, growth of functions
- 14/3/2019 Lecture 26: Combinatorics
- 18/3/2019 Lecture 27: Binomial theorem, probabilities
- 25/3/2019 Lecture 28: Conditional probabilities, independence, Monty Hall puzzle
- 26/3/2019 Lecture 29: Bayes theorem, expectations
- 28/3/2019 Lecture 30: Recurrences and algorithms, correctness of algorithms
- 1/4/2019 Lecture 31: Algorithm correctness and running time