Notes for MACM 101 Fall 2019 (Surrey)

The following are notes for CMPT 101 Fall 2019 at SFU Surrey. The course marking scheme, assignments, quizzes, due dates, etc. are on Canvas.

Note the following:

  • Students must attain an overall passing grade on the weighted average of exams in the course in order to obtain a clear pass (C- or better).
  • Please read the rules for ethical conduct, and marking. All students in this course are bound by these rules — ignorance is no excuse!

Assignments

See Canvas for assignment due dates.

Please submit your assignment online (in Canvas) as a .docx, .doc, or .pdf file.

You should do the work by hand on paper, and then take and submit pictures of your paper work. You can insert the pictures into a Word, or Google Docs document, and then submit that.

Midterm Exam

For the exact time and location of the midterm, please see Canvas.

The midterm is closed book: no books, notes, papers, calculators, computers, etc. are permitted.

You are responsible for bringing a pen or pencil (and eraser) with which to write the exam.

You will be asked to leave all bags, computers, cell phones, etc. at the front of the room. Do not bring anything valuable that you are uncomfortable leaving at the front of the room.

Please use the washroom before, or after the exam. We don’t have time during the midterm to allow people to leave the room and return.

During the exam, no one can leave in the first 20 minutes. So if you are finished early, you will be asked to wait. Also, if you finish during the last 10 minutes, you will also be asked to wait until the end of the exam (to minimize disturbing people still writing).

Here are some more specific details about your midterm:

  • It include questions about counting and logic up to, and including, 2.4 of the textbook (see Lecture Notes for all textbook readings).
  • There will be no questions about step-by-step proofs using logic. There could be a proof question similar in style to the proof question from assignment 1.
  • No questions that require reading or writing computer programs will be asked.
  • Logical duality will not be tested.
  • Terminology about the different names of conditionals will not be tested, e.g. we don’t need to memorize terms like contrapostive and inverse.
  • You should know the names of the basic and most important rules of logic and inference (e.g. you should definitely know modus ponens and double negation), but you don’t need to know all the names. More importantly, you should know how to prove that they are all valid.
  • There are sample exams and questions below.

Please read the grading FAQ if you have questions about how final grades might be calculated.

Final Exam

For the exact time and location of the final exam, please see Canvas.

Bring your SFU student ID to the exam. If you don’t bring your ID, you may be asked to go get it.

The final is closed book: no books, notes, papers, calculators, computers, etc. are permitted.

You are responsible for bringing a pen or pencil (and eraser) with which to write the exam.

You will be asked to leave all bags, computers, cell phones, etc. at the front of the room. Do not bring anything valuable that you can’t have our of your possession.

Please try use the washroom before, or after, the exam.

During the exam, no one can leave in the first 20 minutes. So if you are finished early, you will be asked to wait. Also, if you finish during the last 10 minutes, you will also be asked to wait until the end of the exam (to minimize disturbing people still writing).

Please read the grading FAQ if you have questions about how final grades might be calculated.

The exam will include the same topics as the midterm, and also the following:

  • 3.1 to 3.3 (Set Theory)
    • While you don’t need to memorize all the laws of set theory (p. 139), you should be able to prove they’re true. You should at least memorize De Morgan’s law for sets.
    • Nothing about probability.
  • 4.1 to 4.5 (Properties of the Integers, and Induction)
    • You don’t need to know anything related to programming.
    • You should know how to calculate greatest common divisors (GCDs) by hand.
  • 5.1 to 5.7 (Relations and Functions)
    • You don’t need to know about projection functions (i.e. definition 5.14).
    • While you should know what onto (surjective) functions are, you don’t need to know the formula for counting onto functions, i.e. you don’t need to know about Stirling numbers of the second kind.
    • While you should know the definitions and examples of 5.7 (computational complexity), you don’t need to know anything about the details of analyzing algorithms beyond what was discussed in the lectures.

Exam Study Advice

Memorize (exactly) all important terms, definitions, and formulas.

Questions on the exam will be similar to the homework, and so may ask you to:

  • Do a calculation to get an answer.
  • State a definition or theorem.
  • Prove, or dis-prove, something.

The best way to prepare for this exam is to do lots of practice questions:

Software

Here is the software I sometimes use in the lectures:

Lecture Notes

The following is the tentative schedule of topics. It may change slightly as the course progresses.

All readings refer to the 5th edition of the Grimaldi textbook.

The official assignment and exam due dates are on Canvas. The dates listed here only for convenience, and if they are not the same as on Canvas then you should assume the Canvas due dates are correct.

Week 1: Sept 3 to Sept 6
  • Tuesday Sept 3 is the first day of classes
  • there are no labs in the first week of classes
  • reading: 1.1 - 1.2
Week 2: Sept 9 to Sept 13
  • reading: 1.1 - 1.4
  • note: we are skipping 1.5 (Catalan numbers); you don’t need to read that
Week 3: Sept 16 to Sept 20
  • asn 1 due
  • reading: 2.1 - 2.3
Week 4: Sept 23 to Sept 27
  • reading: 2.4 - 2.5
Week 5: Sept 30 to Oct 4
  • asn 2 due
  • reading: 2.4 - 2.5

The Midterm Exam covers everything up to, and including, section 2.4 of the textbook.

Week 6: Oct 7 to Oct 11
  • Monday: 101 midterm review
  • Wednesday: 101 midterm
Week 7: Oct 15 to Oct 18
  • SFU is closed on Monday Oct 8: all classes, labs, office hours, etc. are canceled (Thanksgiving holiday)
  • reading: 3.1 - 3.3
Week 8: Oct 21 to 25
  • reading: 4.1 - 4.2
Week 9: Oct 28 to Nov 1
Week 10: Nov 4 to Nov 8
  • reading: 4.3 - 4.5
  • reading: 5.1 - 5.4
Week 11: Nov 12 to Nov 15
  • SFU is closed on Monday Nov 12: all classes, labs, office hours, etc. are canceled (Remembrance day holiday)
  • asn 4 due
  • reading: 5.5 - 5.7
Week 12: Nov 18 to Nov 22
  • reading: 5.5 - 5.7
Week 13: Nov 25 to Nov 29
  • reading: 5.5 - 5.7
Week 14: Dec 2
  • Monday Dec 2 is the last day of classes

Exam schedule: Dec 4 to Dec 16

101 final exam: Sunday Dec 8, noon to 3pm