CIT 592 Lecture Schedule (Fall 2013)

Date Lecture Topics Assigned Readings & Other Info
Aug 29
• Course introduction
• Basic counting, sum and product principles, counting subsets
Sep 3
• Bijection principle
• Pascal's Triangle
Sep 5
• Bijection principle take 2
• Binomial Theorem
• Relations
Sep 10
• Equivalence Relations, Posets, Orders
• Counting with equivalence relations
• Textbook - Pages 43 to the end of Chapter 1
Sep 12
• Finishing up Chapter 1
• Logic and truth tables
Sep 17
• Boolean Algebra
• Quantifiers
Sep 19
• Negation of quantifiers
• First steps on what is a proof?
Sep 24
• More proofs
• Contrapositive
Sep 26
• Proof by smallest counter example (not part of midterm)
• Section 3.3
• Section 4.1
Oct 1
Oct 3
• Induction
• Chapter 4 - weak induction
Oct 8
• More induction. Intro to strong induction
Oct 10
• Induction in a CS algorithm (binary search)
• Induction using structures (triangulations of polygons)
• Chapter 4 - structural induction
Oct 15
• Recurrences
• Recursion
• Chapter 4.2
Oct 17
• Theorems on recurrences
• Read the 2/3 examples pertaining to application of the theorem from the book
Oct 22
• Divide and conquer
• Specific example of mergesort (Intro to recursion trees)
Oct 24
• 3 different recursion trees giving different big-theta answers
• Chapter 4, Section 4.3
Oct 28
• Intro to probability
• Chapter 5, Section 5.1
Oct 31
• Inclusion Exclusion principle
• Derangements
• Chapter 5, Section 5.2
Nov 5
• Conditional probability
• Bayes theorem
Nov 7
• Independence
• Probability trees
Nov 12
• Exam 2
Nov 14
• Expectation
• Book section 5.4
Nov 19
• Expectation calculations in hashing
• Book section 5.5 - only the results we did in class
• 6.1 - we just started with the definitions
Nov 21
• Lots of definitions in graph theory
• intro to induction in graphs
Nov 26
• Trees
Dec 3
• Eulerian tours
Dec 5
• More Eulerian tours
• Hamiltonian tours
• Section 6.3
• Chinese Postman Problem
• Traveling Salesman Problem
Dec 10
• Graph Colouring
Dec 20
• Final exam