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
• Labs

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 by contrapositive
  • Review Ch 4, especially sections 4.3 and 4.5
  • No problem set, finish lab2!
• Wed, Sep 27 Lecture 13: Proof by contradiction
  • Review Ch 4, especially sections 4.3 and 4.5
  • No problem set.
• Fri, Sep 29 Lecture 14: Proof by induction
  • Reading 5.1 and 5.2, including "CS Connection"
  • No problem set... but please be sure to do the reading!

Week 6

• Mon, Oct 2 Lecture 15: Proof by induction practice
  • Reading 5.3
  • No problem set, work on lab3!
• Wed, Oct 4 Lecture 16: Proof by strong induction
  • Reading 5.3
  • No problem set... but I encourage you to spend some time thinking about the exercise we started in class on Monday.
• Fri, Oct 6 Lecture 17: Structural induction
  • Reading 5.4 + CS Connections
  • No problem set... try to finish lab 4 before fall break.

Week 7

• Mon, Oct 9 (Fall Break)
• Wed, Oct 11 Lecture 18: Structural induction
  • Review 5.4
• Fri, Oct 13 Lecture 19: Proof review
  • Review Ch. 5

Week 8

• Mon, Oct 16 Lecture 20: Asymptotics
  • Read 6.1, 6.2
  • Problem set 10 (due in class on Monday): 6.5, 6.7, 6.10.
• Tue, Oct 17 through Fri, Oct 20 take-home midterm
• Wed, Oct 18 No Class (due to travel)
• Fri, Oct 20 Lecture 21: Proof review
  • Read 6.3
  • No problem set, finish take-home exam

Week 9

• Mon, Oct 23 class and office hours cancelled due to travel (attending a conference)
• Wed, Oct 25 Lecture 22: Algorithm analysis and recurrence relations
  • Review 6.3 and read 6.4
• Fri, Oct 27 Lecture 23: Recurrence relations
  • Read 6.4

Week 10

• Mon, Oct 30 Lecture 24: Recurrence Relations & Relations I
  • Read 8.2
• Wed, Nov 1 Lecture 25: Relations II
  • Read 8.3
• Fri, Nov 3 Lecture 26: Relations III
  • Read 8.4

Week 11

• Mon, Nov 6 Lecture 27: Relations IV
  • Review 8.4
• Wed, Nov 8 Lecture 28: Topological Sort and DFS
  • Read 11.2.2, 11.3.5
• Fri, Nov 10 [Lecture 29: Wrap up Relations]
  • Review Ch. 8
  • Today we worked on the lab, no lecture slides.

Week 12

• Mon, Nov 13 Lecture 30: Counting
  • Read 9.1, 9.2
• Wed, Nov 15 Lecture 31: Counting II
  • Read 9.3
• Fri, Nov 17 Lecture 32: Counting III
  • Read 9.4

Week 13

Thanksgiving break!

Week 14

• Mon, Nov 27 Lecture 33: Counting IV
  • Review 9.4
• Wed, Nov 29 [Lecture 34: Counting wrapup]
  • Problem set 12 handed out in class, due at start of class on Friday.
• Fri, Dec 1 Lecture 35: Probability
  • Read 10.1-10.2

Week 15

• Mon, Dec 4 Lecture 36: Probability II
  • Review 10.3
• Wed, Nov 6 Lecture 37: Probability III
  • Read 10.4
• Fri, Nov 8 Lecture 38: Probability IV
  • Read 10.4
  • Problem set 13 handed out in class, due at start of class on Monday.

Week 16

• Mon, Dec 11 Lecture 39: Probability V