CIT 592 Lecture Schedule (Fall 2014)


The content of the course will not be too different from previous year, but the order of topics will be switched around a bit.

This course is math heavy (as the name should suggest), so I strongly recommend reading the first few pages of How to Solve It by Polya. The book is a classic and often when you are stuck with seemingly no clue about how to solve a homework/exam question, going back to the basics of problem solving can prove to be very helpful.


In terms of how deep we go into topics in this course here are last year's exams. If you are wondering whether you know the material or not, these should help.

Date Lecture Topics Assigned Readings & Other Info
Aug 28
  • Course introduction
Sep 2
  • Sets/functions
Sep 4
  • Sets/Relations
  • Zybook sections 2.3 and 2.4
  • Zybook section 3.1
Sep 9
  • Counting(Combinatorics)
  • Zybook sections 9.1 and 9.2
Sep 11
  • Counting(Combinatorics)
Sep 16
  • Combinatorics (Binomial Theorem)
  • Zybook sections 9.5 and 9.6
Sep 18
  • Probability
Sep 23
  • Conditional probability
  • Independence
  • Zybook section 11.3
Sep 25
  • Conditional Prob and Bayes Theorem
Sep 30
  • midterm review
Oct 2
  • midterm1
Oct 7
  • Expectation and Indicator variables
  • Zybook sections 11.5-11.8 (we will try and finish the chapter)
Oct 14
  • Basic logic and truth tables
  • Quantifiers
  • Negating a quantified statement
  • Zybook Chapter 1 (spread out across the lectures)
  • DMA 2.1 - 2.3
Oct 16
  • Proof techniques
  • Proof handout from Scheinerman (see Canvas for the pdf)
Oct 21
  • Proof by contrapositive
  • Proof by contradiction
  • Zybook 1.9 - 1.11
Oct 23
  • Proofs involving sets
  • Section 6.2 of the DMA book
Oct 28
  • Induction intro
  • Zybook 7.3
Oct 30
  • Strong induction
  • Zybook 7.4
Nov 4
  • Recursion trees. Big-Oh (will not be part of the midterm)
  • Zybook 7.1 and 7.2
Nov 6
  • midterm 2
Nov 11
  • Analysis of Algorithms part 1
  • 6.1, 6.2 and 6.3 of Zybook
Nov 13
  • Analysis of Algorithms
  • DMA book - Section 11.3
  • Detailed explanations in Chapter 11 of the book
Nov 18
  • Recursion trees
  • Graphs - basic introduction
  • Handout from Discrete math for Computer Scientists book (found on canvas)
Nov 20
  • Graphs - basic results
Nov 25
  • Graph colouring, Paths in graphs
  • Zybook - 12.3, 12.4, 12.5
Dec 2
  • Paths in graphs
  • 12.3, 12.4, 12.5
Dec 4
  • Trees
  • Zybook 13.1.
Dec 9
  • Review of 592
  • Preview of 596
Dec 17
  • final exam
  • 12pm - 2pm