CSC226 Discrete Mathematics for Computer Scientists
 Home    Contact    Syllabus    Notes    Outline  

Fall 2015 Outline

Note: some of these dates may change. WebAssign due dates override those listed here.

Due Date Lecture Topics Reading Assignment Optional Reading
8/19/15 Homework 0 Intro to WebAssign
8/24/15 Lecture 1    Introduction, Logic

Note: The first lecture cites an INCORRECT textbook. Your textbook is the Rosen text listed on the syllabus.		 Zybook: 1.1, 1.2, 1.3 Packet 1 (pdf) - Logic & Proof
Rosen ed 3/4: 1.1-2, 3.1, 9.1-3
Rosen ed 5: 1.1-2, 1.5, 10.1-3
Lecture 2    Logical Equivalences & Implications Zybook: 1.4
Lecture 3 Formal Logic Proofs, Circuits (example) Zybook: 2.1,2.2,5.6
Lecture 4 Formal Proofs, Circuits, Disjunctive Normal Form Zybook: 2.3,2.4,2.5,5.3
9/1/15 Homework 1 Practice HW1-2 doc, Practice HW1-2 pdf, Logic, proofs
9/4/15 Homework 2 Practice HW1-2 doc, Practice HW1-2 pdf, Logic & proofs
9/1/15 Lecture 5 Predicate Calculus, Circuits, Multiplexers
Note: Circuits not req. fall 2010		 Zybook: 1.5, 1.6 Packet 2 (pdf), - Pred Calc & Set Theory,
circuits, & pred. calc. examples
Rosen ed 3/4: 1.3, 1.4, 1.5, 9.3
Rosen ed 5: 1.3, 1.6, 1.7, 10.3
Rosen ed 6: 1.3, 2.1, 2.2, 11.3
Lecture 6    Pred. Calc, Set Theory, HW3 help Zybook: 1.8, 1.9, 3.1, 3.2
Lecture 7    Set Theory & Proofs, HW3 help Zybook: 3.3, 3.4
Venn's Paper
9/8/15 - 9/15/15 Deep Thought Proof Lab REQUIRED!
9/11/15 Homework 3 Practice HW3 doc, Practice HW3 pdf, Predicate Calculus
9/14/15 Lecture 8    Test 1 Review, Induction Zybook: 8.1, 8.2
9/16/15 Test 1
9/25/15 Homework 4 Practice HW4 doc, Practice HW4 pdf, Sets & Predicate Calculus
9/28/15 Lecture 9    Induction,Arithmetic Proofs Zybook: 8.3 Packet 3 (pdf) - Induction
Rosen ed 3/4: 1.7, 3.1, 3.2
Rosen ed 5: 1.5, 3.1, 3.2, 3.3
Rosen ed 6: 2.4, 4.1
Lecture 10   Ind, Sets, Recursion (HW5 help) Zybook: 8.7
10/6/15 Homework 5 Practice HW5, Practice HW5 pdf, Sets, Arithmetic Proofs, Induction
10/7/15 Lecture 11   Recursion, Induction Zybook: 8.11, 8.4 Packet 4 (pdf) - Recursion & Big O
Rosen ed 3/4: 3.3, 5.1, 5.2
Rosen ed 5: 3.4, 6.1, 6.2
Rosen ed 6: 4.3, 7.1, 7.2
Lecture 12   Recursion (Towers), Induction, Intro to Growth of Functions Zybook: 8.5, 4.6
Lecture 13    HW6 help, Big O, Induction Pfs with Ineq. big O
10/13/15 Homework 6 Practice HW6 doc, href="http://www.cs.uncc.edu/~tbarnes2/LogicAlgorithms/notes/pdf/HW6.pdf">Practice HW6 pdf, Induction, Recursion
10/14/15 Lecture 14    Big O, Omega, Theta, Ind, Test 2 rev. big O Rosen ed 3/4: 1.8
Rosen ed 5: 2.2
Rosen ed 6: 3.2
Lecture 15    Test 2 Review
10/19/15 Test 2
  • Study HW 4-6, Test 2 Review, & Special Tests 3,4, and 5. You are NOT responsible for Special Test 3, problem 2.
  • Set Theory defns & proofs using predicates
  • Modulus & divisibility
  • Induction
  • Recursion - finding recursive and closed forms and proving correct by induction.
10/21/15 Lecture 16    Big-O help, Binary Relations Zybooks: 6.1, 6.2 Packet 5 (pdf) - Binary Relations
Binary Relations web slides
Rosen ed 3/4: 6.1, 6.3, 6.4, 6.5, 6.6
Rosen ed 5: 7.1, 7.3, 7.4, 7.5, 7.6
Rosen ed 6: 8.1, 8.3, 8.4, 8.5, 8.6
Lecture 17    HW7 help, Binary Relations

Binary Relations notes:

  • In Lecture 17, I mistakenly read R1 o R2 as "R2 composed with R1". This should be read "R1 composed with R2".
  • In packet 5, I use Rf for reflexive closure of R, Rs for symmetric closure of R, and Rt for transitive closure of R. In lecture I refered to them as Rrc, Rsc, and Rtc. Either notation is acceptable (others as well, there is not a mathematical standard for this, you will have to denote it as a particular closure in English).

 Zybooks: 6.5, 6.7, 6.9
10/27/15 Homework 7 Practice HW7 doc, Practice HW7 pdf, Big O, Ind, Recursion
10/28/15 Lecture 18    Binary Relations, HW8 help, Intro to Counting Zybook :10.1
11/3/15 Homework 8 Practice HW8 doc, Practice HW8 pdf, Binary Relations
11/4/15 Lecture 19   Counting Zybook: 10.11 Packet 6 (pdf) - Counting & Graphs
Hasse Diagrams: Packet 5, pages 14-16.
Rosen ed 3: 4.1, 4.2, 4.3, 4.6, 4.7, 5.4
Rosen ed 4: 4.1, 4.2, 4.3, 4.6, 4.7, 5.5
Rosen ed 5: 4.1, 4.2, 4.3, 4.5, 4.6, 6.5
Rosen ed 6: 5.1, 5.2 5.3, 5.5, 5.6, 7.5
Lecture 20   Counting Zybook: 10.3,10.4,11.3
Lecture 21 Counting, Graph Theory, Pascal's Triangle, HW9 help Zybook: 13.1, 13.2, 13.3, 13.4
11/10/15 Homework 9 Practice HW9, Practice HW9 pdf, Counting
11/19/15 Test 3
  • Study HW 7-9, Test 3 Review, Special Tests 6-9, & Test 3 Study Sheet (PDF)
  • Recursion - proving closed forms
  • Big-O,Big-Theta, Big-Omega
  • Binary relations
  • Watch Review of Big-O and Binary Rel in Lecture 22
  • Counting - draw picture, combinations, permutations, Addition Rule, Mult Rule, Inclusion-Exclusion, Formulas, Rearranging letters in word, Pigeonhole Principle - find # of pigeons, holes, or the # of pigeons you can guarantee are in one hole, Divider problems.
  • Watch Counting portion of Lecture 27, former Test 4 review.
11/23/15 Lecture 22 Graph Theory, Review of Big-O & Binary Relations Zybook: 14.5, 14.6 FSM packet (pdf);
Rosen ed 3/4: 6.6, 7.2, 7.3, 7.5, 8.6, 10.3
Rosen ed 5: 7.6, 8.2, 8.3, 8.5, 9.5, 11.5
Rosen ed 6: 9.2, 9.3, 9.5, 10.5, 12.5
Lecture 23 Finite State Machines Zybook: 7.4
Lecture 24 Finite State Machines
12/4/15 Homework 10 Practice HW10, Practice HW10, Graphs, Hasse Diagrams
Optional Lecture 25 Grey Codes, The Universal Problem
Lecture 26 Grey Codes, The Universal Problem
12/4/15 Lecture 27 Former Test 4 Review (Counting, Graphs, FSMs)
12/10/15 (002), 12/16/15 (001) Final Exam 1-4 pm (002) 8-11 am (001)
  • Study materials for tests 1-3.
  • Study Practice HW 10, Former Test 4 Review, Special Test 10, Packet 6 examples.
  • Graphs - Euler circuits & paths & nec. conditions for both, Hamilton circuits, Kruskal's algorithm for Minimum Spanning Trees,
  • Binary relations - Draw Hasse diagrams, find minimal, maximal, minimum, and maximum elements, least upper bounds and greatest lower bounds.
  • Finite State Machines - Create a finite state machine given a regular expression. Label start and end states. Create a regular expression given a finite state machine.