COSC 290 Discrete Structures Fall 2017

This repository contains course materials for COSC 290 Discrete Structures, Fall 2017 edition, taught by Michael Hay.

Basic info

• Syllabus
• Office hours: typically 1:30-3:00pm on M and F, and Tu 12:15-1. Appointments are encouraged.
• Piazza

Schedule

Week 1

• Tue, Aug 28 Lecture 0: Half-day introduction.
• Wed, Aug 29 Lecture 1: Data types and sets
  • Reading: syllabus, 2.2, 2.3
  • Problem set 1 is due in class.
• Fri, Sep 1 Lecture 2: Sets
  • Reading: 2.3
  • Problem set 2 will be due in class.

Week 2

• Mon, Sep 4 Lecture 3: Sequences, Vectors, Functions
  • Reading: Read the first part of 2.4, up to but not included 2.4.1 closely. Please skim 2.4.1 and 2.4.2, the parts on vectors and matrices. Read 2.5 closely, including the Computer Science Connection on p. 267.
  • Problem set 3 will be due in class.
• Wed, Sep 6 Lecture 4: Propositional Logic Logic
  • Reading: 3-3.2
  • Problem set 4: Please complete problems 3.4-3.10. It is due in class on Wednesday.
  • Lab 1
• Fri, Sep 8 Lecture 5: Propositional Logic continued
  • Reading: 3.3
  • There is no problem set for today, but come prepared to do some logical reasoning!

Week 3

• Mon, Sep 11 Lecture 6: Propositional Logic Equivalence
  • Reading: review 3.2 and 3.3.
  • Problem set 5 (due in class on Monday): complete problems 3.39-3.41, 3.49, 3.60
• Wed, Sep 13 Lecture 7: Argument checking
  • Reading: 3.4
  • No problem set for this lecture. Finish lab1.
• Fri, Sep 15 Lecture 8: Predicate Logic
  • Reading: 3.5
  • No problem set for this lecture. Work on lab2.

Week 4

• Mon, Sep 18 Lecture 9: Error correcting codes
  • Reading: 4.1 and 4.2
  • Problem set 6 (due in class on Monday): complete at least 6 problems from 3.145-3.152. You are free to choose which 6 you do.
• Wed, Sep 20 Lecture 10: Proofs and codes
  • Reading: 4.3
  • Problem set 7 (due in class on Wednesday): complete 4.22 and 4.26. For 4.26, please use {a,b,c,d,e,f,g,h,i,j,k} to represent the 11 bits of the message and then describe each of the 4 parity bits as a subset of {a,b,c,d,e,f,g,h,i,j,k}. If you are stumped on this question, then try writing a Hamming code for 7 bit messages with 4 parity bits. (As a bonus challenge problem, think about 4.29 or 4.31.)
• Fri, Sep 22 Lecture 11: Proofs and codes, continued..
  • Reading: 4.4
  • Problem set 8 (due in class on Friday):
    • 4.13. However, you can just write an answer for error detection and you can skip the error correction part.
    • 4.12. Please do both error detection and correction. Hint: both parts are a proof by construction (Definition 4.15 on p. 433). For example, for the error detection part, you want to show that the given information implies that there exists a pair (codeword c and received bitstring c') such that error detection fails. For the error correction part, you want to show that the given information implies that there exists a bistring c' where error correction fails (the original codeword is c but c' gets corrected to some other valid codeword c'').

Week 5

• Mon, Sep 25 [Lecture 12: Proof techniques]
  • Review Ch 4, especially sections 4.3 and 4.5
  • No problem set, finish lab2!