Math 1281 - Discrete Mathematics (2006/07)

In Discrete Mathematics (Math 1281) we cover a variety of topics, including basic set theory, graphs, logic and proofs, number structures, basic combinatorics, and algorithms. This is a two semester course that also includes a lab once a week.

News (Last Updated April 14, 2007)

Final Exam and Unofficial Marks The final exam has been graded. Please see the link below for the exam marks and unofficial marks: Exam and Unofficial Marks Also, please check out: PreExam Marks Let me know about any corrections.

Below is a summary of what we did in class, plus any relevant news and/or information.

• March 30, 2007 Our last lecture/class! We did review, and I took questions about the final. I will have class on Monday, but nothing formally prepared. Good luck studying!
• March 28, 2007 Today we looked at Section 11.4 on Karnough maps. You should know how to minimize a circuit. I also showed, in class, some examples of actual circuits. I will do review on Friday.
• March 27, 2007 I added the Review Sheet for the final exam.
• March 26, 2007 I introduced Logic Gates (Section 11.3). Know the three basic gates (inverter, AND, and OR), and how to use the gates to build simple circuits.
• March 23, 2007 We discussed Section 11.2 on how to represent a given Boolean function with miniterms. I also discussed the idea of functional completeness. HWA 18 was due in class. I also gave out HWA 19; please note HWA 19 is a bonus assignment.
• March 21, 2007 We started Section 11.1 on Boolean algebras. You should know the basic operations and rules for dealing with Boolean algebras. I also handed back HWA 17.
• March 19, 2007 We finished up Section 10.4 (how to find a spanning tree) and we discussed how to use either Prims or Kruskal's algorithm to find the spanning tree of minimum weight.
• March 16, 2007 In the first half of class we discussed the idea of a binary search tree (see Section 10.2). In the second half we discussed the notion of a spanning tree, and how to use the depth first algorithm to find such a tree (see Section 10.4). HWA 18 was also given out.
• March 14, 2007 We discussed Section 10.1 on trees. Know the definition of a tree, and the terminology associated to a tree, e.g. descendants, siblings. Also know what an m-ary tree is, and the level and height of a tree.
• March 12, 2007 We finished Section 9.7 on planar graphs. Now how to decide if a graph is planar or not. We also discussed Section 9.8 on graph colourings.
• March 9, 2007 Today we talked about planar graphs. Know what a planar graph is, and also know Euler's formula.
• March 7, 2007 I discussed Dijkstra's algorithm for finding the shortest past in a weighted graph. We also talked about the Travelling Salesman Problem. I explained how to find an approximate answer. I also handed back the latest HWA.
• March 5, 2007 We talked about Hamilton circuits and paths (Section 9.5).
• March 2, 2007 We finised Section 9.4 and discussed the material of Section 9.5 on Euler Circuits and Paths. A new HWA was given out.
• Feb. 28, 2007 We continued our discussion of graphs by talking about connectivity (Section 9.4).
• Feb. 26, 2007 We discussed Section 9.3 on representing graphs and graph isomorphisms.
• Feb. 16, 2007 I cancelled class today (day before reading break). However, I handed back Midterm II and gave out the new HWA.
• Feb. 14, 2007 Midterm II today.
• Feb. 12, 2007 We finished up Section 9.2. You should know the special families of graphs (complete graphs, cycles, n-cubes, wheels) as well as the defintions of bipartite, and induced subgraphs.
• Feb. 9, 2007 We went over the basics of graph theory; we covered Section 9.1 and a little bit of 9.2. Our lecture today was given by a guest speaker: Jane He. There is no HWA for this week, but I did put up the HWA for the week after.
• Feb. 7, 2007 We did a review of Chapter 8 today. We also talked about the Kevin Bacon Number and Erdos number, and how you can define these relations in terms of relations. For more on the Kevin Bacon number see
  • Oracle of Bacon
  For more on the Erdos number, try
  • MathSciNet Collaboration Distance
• Feb. 5, 2007 The Final Exam will be on April 11, 2007.
• Feb. 5, 2007 Today we looked at Section 8.6 on partial orders. You should know the definition of a partially ordered set, a totally ordered set, a maximal and minimal element, and comparable and incomparable elements. I also handed out the review sheet for the second midterm.
• Feb. 2, 2007 We looked at Section 8.5 on equivalence relations. You should know what an equivalence relation is, and how such a relation gives a partition of a set. I also gave out the new HWA 14.
• Jan. 31, 2007 In today's class we looked at Section 8.4 on the closure of relations. You should know how to find the reflexive closure, symmetric closure, and transitive closure of a given relation. I also handed back HWA 12.
• Jan. 29, 2007 We looked at Section 8.3 on representing relations. We saw that we can represent a relation using zero-one matrices and digraphs. As well, we saw that we could use the zero-one matrix to determine if a relation had a specific property.
• Jan. 26, 2007 We finished talking about Section 8.1 and went through the material of Section 8.2. You should know how to find the composition of two functions, and how this is related to the transitivity property. We also talked about relations on sets. The new homework assignment was also given out.
• Jan. 24, 2007 We started Chapter 8 on relations. You should know the material discussed in Section 8.1 -- what is a relation, and know the terms reflexive, symmetric, ansti-symmetric, and transitive. I also handed back assignment 11.
• Jan. 22, 2007 We went back and covered Section 3.8 on matrices. You should know how to add and multiply two matrices togther, the definition of symmetric and transitive, and you should know how to do all the operations involving Boolean matrices. We will need these results when we look at Chapter 8.
• Jan. 19, 2007 We finished Chapter 7 by doing both sections 7.5 and 7.6. You should the principle of inclusion-exclusion, the reformulation in Section 7.6, and the formula for counting the number of onto functions. I also gave out the new HWA.
• Jan. 17, 2007 We continued our discussion of generating functions by consdering some applications. In particular, we showed how to use generating functions to solve counting problems and solve recurrence relations.
• Jan. 15, 2007 We skipped Section 7.3 and instead looked at Section 7.4 on generating functions. You should know what a generating function is, and you should know what we mean by its closed form. You will be expected to do problems like those done in class.
• Jan. 12, 2007 We finished up Section 7.2. After today's class, you should know how to solve all linear homogeneous recurrence relations of degree one and two. I also gave out the new HWA.
• Jan. 10, 2007 We looked at Section 7.2 and discussed how to solve recurrence relation. In particular, we find an explicit formula for the Fibonacci sequence. We will finish this section on Friday.
• Jan. 8, 2007 We started a new chapter (Chapter 7) on recurrence relation. We covered all of Section 7.1 today.
• Jan. 5, 2007 Today we finished Chapter 6 by going over Section 6.3 on Bayes Theorem. I also gave out the first homework assignment.
• Jan. 3, 2007 Welcome back! In today's class I handed back the Christmas midterm. As well, I covered some material from Section 6.2 on Bernoulli trials.

First Semester News

• Dec. 13, 2006 I have finished grading the Christmas Midterm. You can see you mark for the exam and the 1st semester using the link below: First Semester Marks You will receive your exam back on the first day of classes in January. Have a good break!
• Nov. 29, 2006 Today I went over the material of Section 6.2. You will need to know about condition probability and how to assign probabilites. We will have class on Thursday.
• Nov. 27, 2006 You can check out your Pre-Exam Marks I have also posted these on my doors. Please let me know ASAP if there are problems.
• Nov. 27, 2006 I handed out the Exam review sheet. I also started on Section 6.1 on Discrete Probability.
• Nov. 25, 2006 Start studying!! The Christmas Exam Review Sheet is now available. I'll bring a hard copy to class on Monday.
• Nov. 24, 2006 We finished up Section 5.5. I also covered the material of Section 5.6 on the lexicographical order, and how to put partitions in order. HWA 9 was due in class today.
• Nov. 22, 2006 In today's class we continued our discussion of Section 5.5. We will finish up Chapter 5 in Friday's class.
• Nov. 20, 2006 Because the Christmas Exam will soon be here, I'm putting up last year's Christmas Exam for you to practice with. 2005 Christmas Exam (for Practice) I'll post the solutions to last year's exam on E-Res in the next couple of days.
• Nov. 20, 2006 Today we began our discussion of Section 5.5 on generalized permutations and combinations. You should know how to count permutations and combinations when repetition is allowed.
• Nov. 17, 2006 We covered Section 5.4 on Binomial coeffecients. I also gave out the last homework assignment for the semester.
• Nov. 15, 2006 I introduced the notions of permutation and combination (Section 5.3). You should know the formulas to compute the number of r-permutations and r-combinations from a set with n elements. I also handed back HWA 7.
• Nov. 13, 2006 Today we discussed the Pigeonhole Principle, the topic of Section 5.2.
• Nov. 10, 2006 We started Chapter 5 on counting. In today's class I covered Section 5.1 on the basics of couting. You should know the general sum and product rules, the principle of inclusion-exclusion, and how to use trees to count. I also gave out HWA 8 (see to the right).
• Nov. 8, 2006 Today I covered Section 4.3 on recursive definitions, and I briefly covered Section 4.4. You should know how to define a function, sequence, set, and algorithm recursively. As well, you should be to give examples of each.
• Nov. 6, 2006 I finished Section 4.2, our second class on induction. I did a number of new examples, plus I introduced the notion of strong induction.
• Nov. 3, 2006 I did the first of two lectures on mathematical induction. Today, I looked at Section 4.1. I also gave out the new HWA.
• Nov. 1, 2006 We finished Section 3.7 on public key cryptosystem. You should know the difference between a public and private key cryptosystem. HWA 5 was also handed back.
• Oct. 30, 2006 We looked at Section 3.7 on applications of number theory. We discussed some properties of intergers, and some results on linear congruences. I also introduced Fermat's Little Theorem. We will finish this section on Wednesday.
• Oct. 27, 2006 Today we went back and finished up some material in Section 3.4 on modular arithmetic. We also covered the material on the Euclidean algorithm in Section 3.6. HWA 6 was also given out (see to the right).
• Oct. 25, 2006 In Wednesday's we looked at topics from Section 3.4 and 3.5. You should know the definition of division, some of its properties, prime numbers, GCDs and LCMs.
• Oct. 23, 2006 We looked at Section 3.3 on the complexity of algorithms. You should know how time complexity is computed, and be able to figure out the time complexity of some simple algorithms. I also handed back the first midterm.
• Oct. 20, 2006 Today I looked at Section 3.2 on the growth of functions. You should be able to find the Big-O of a function. You do not need to know page 187-190 of 3.2. I also gave out the new HWA. The midterm will be handed back on Monday.
• Oct. 16, 2006 There will be no class or lab today because I'm out of town. Use the time to study for your midterm.
• Oct. 13, 2006 The date of the Christmas Exam has been posted. It will be on Thursday, Dec. 7, 1:00-4:00 in UC 2011.
• Oct. 13, 2006 We began Chapter 3 by going over the material of Section 3.1 on algorithms. In particular, I described three algoriths: find the largest element in a list, linear search, and binary search. I also mentioned what a greedy algorithm is.
• Oct. 11, 2006 Today I talked about sequences and summation, the material of Section 2.4. I also handed back assignment 3.
• Oct. 9, 2006 No class because of Thanksgiving.
• Oct. 6, 2006 Today I went over the material of Section 2.3. You will need to know the following terms: function, domain, codomain, image, preimage, range, onto, one-to-one, bijection, inverse, composition, graph of a function, and the floor and ceiling function. The first midterm will cover the material up to today. HWA 4 was also given out -- see the column to right.
• Oct. 4, 2006 We covered the material of Section 2.2. We covered the four basic set operations: union, intersection, difference, and complement. I also explained how to show two sets are equal. You should know how to use a membership table to show that two sets are equal. I also gave a handout on the first midterm.
• Oct. 2, 2006 Today we looked at Section 2.1. I introduced the basic terminology associated to sets. Know what a set is, an element of a set, the empty set, subsets, cardinality, and how to make special constructions like the power set or cartesian product.
• Oct. 1, 2006 Because the server has been done for the last week, I have not been able to update the webpage until today. Everything is now up-dated!!!
• Sept. 29, 2006 I spent the class reviewing the material in Chapter 1. For examples, I used questions that had appeared on past midterms and exams. I also gave out the new homework assignment (see to the right).
• Sept. 27, 2006 Today we looked at some strategies of prove methods. We concentrated on "Forward-and-Backward Reasoning". I did a worked out example of this type of method. I also discussed the importance of conjectures.
• Sept. 25, 2006 We looked at some more proof strategies, including exhaustive proofs and proof by cases. We also discussed theorems with quantifiers and talked about the difference between a constructive and non-constructive proof.
• Sept. 22, 2006 Today we started our discussion of Section 1.6 on an Introduction to Proofs. You should know what we mean by a direct proof, indirect (or proof by contraposition), proof by contradiction, and a proof involving equivalences. I also gave out the new homework assignment (see to the right).
• Sept. 20, 2006 We finished Section 1.5 by discussing the rules involving quantifiers: universal instantiation and generalization, and existential instantiation and generalization. We also discussed proofs and our our goals for the next couple of lectures.
• Sept. 18, 2006 We started Section 1.5 on the rules of inference. You should know all eight rules of inference. As well, know the two common types of fallacies -- the fallacy of affirming the conclusion, and the fallacy of denying the hypothesis. You should also be able to do problems like Example 6 in Section 1.5.
• Sept. 15, 2006 We finished Section 1.3 on Quantifiers, and we covered section 1.4 on Nested Quantifiers. You should become comfortable translating between statements with quantifiers and statements in English. I also gave out the first homework assignment (see side bar on right).
• Sept. 13, 2006 We covered Section 1.2 on Propositional Equivalences. You should know what a tautology and contradiction are, and what it means for two propositions to be logically equivallent. You should be able to do problems like Example 4. We also started Section 1.3 on Predicates and Quantifiers. Know the univerisal and existential quantifiers.
• Sept. 11, 2006 We finished section 1.1. You should know all the logical operators: negation, conjunction, disjunction, exclusive or, implication, and biconditional, and all their truth tables. As well, you should know how to translate between English and compound propostion, and back. This is Section 1.2. There was no lab today -- we will start next week.
• Sept. 8, 2006 Today was the first day of class. During the first half, I went over the course information sheet. During the second half, I started our discussion of logic (Section 1.1) by introducing propositions, negation, conjuction, and disjunction. We will continue this material on Monday.
• Sept. 7, 2006 First day of class tomorrow. Change of Lab time. The lab time is changing!!!. It will be Monadys 10:30-11:30 in RC 1002.
• August 13, 2006 Web page ready for Sept. 8, 2006, first day of classes.