In Discrete Mathematics 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.

Last Updated: April 18, 2006

• April 18 The exams have been graded, and the marks have been submitted. You can see the UNOFFICIAL marks below: Unofficial Final Marks Have a good summer! Adam
• April 6 The last assignment has been graded. You can now pick up all the old assignments from the box outside my office. I have also calculated all the marks up to the final. To see your mark before the final, check out Math 1281 Prefinal Exam Marks Please let me know as soon as possible about any mistakes.
• March 29 Today was our last class. I finished the course by covering Section 10.4. You should know how to use Karnough maps to simplify Boolean expressions using two or three variables. For the homework, please bring it to my office on Friday and put it under the door.
• March 27 Today we covered Section 10.3 on Logic Gates. Know how to do examples like those in class.
• March 24 We discussed how one could represent a Boolean function. Know what a miniterm is, and also know what is meant by the term functionally complete. Also know the new Boolean operators - NOR and NAND.
• March 23 Below is a "clean" copy of the 2005 final exam: 2005 Final Exam I will put the solutions on ERES so that you can practice with this exam, and then check your answers.
• March 22 Today, we started Chapter 10. We looked at Boolean functions; you should know the basic operations, and how to find all the values of a Boolean function. As well, know what we mean by the dual of a function.
• March 20 We finished Section 9.4 by describing another algorithm (breadth-first search) for finding a spanning tree. We then covered Section 9.5 on finding minimal spanning trees. You should know Prim's algorithm and Kruskal's algorithm.
• March 17 We looked at one application of trees from Section 9.2, namely, binary search trees. We then discussed the notion of a spanning tree and talked about the depth-first search algorithm for finding spanning trees. HWA 15 was handed backed, HWA 16 was due, and HWA 17 was given out.
• March 15 We began Section 9.1 on trees. We covered a large amount of terminology associated to trees.
• March 13 We finished Section 8.7 by discussing how to determine if a graph was planar. We then covered Section 8.8 on graph colouring.
• March 10 Today we talked about Section 8.7 on planar graphs.
• March 8 In class we looked at Section 8.6 on finding the shortest path in a weighted graph. In particular, we looked at Dijkstra's algorithm. We also discussed the Travelling Salesman Problem.
• March 6 We discussed the rest of Section 8.5 on Hamilton circuits and paths.
• March 3 We first finished Section 8.4 on connectivity. We saw how to use the adjancey matrix to count the number of paths between two vertices. We then started Section 8.5. You should know what a Euler path and circuit are, and you should know how to determine if a graph has such an Euler path/circuit. HWA 15 was given out.
• March 1 We studied Section 8.4 on connectedness. You should know the terms: path, circuit, simple path/circuit, length of a path, cut vetex/edge, connected component, strongly connected, weakly connected.
• Feb. 27 We looked at Section 8.3 on representing graphs. You should know the two common methods -- adjacency matrices and incidence matrices. As well, you should know what it means for two graphs to be isomorphic.
• Feb. 17 We completed Section 8.2. After today's class you should know the following terms: complete graph, cycle, wheel, n-cube, bipartite, complete bipartite. Also, you should the various constructions of making new graphs from old. Have a good break!
• Feb. 15 Midterm II was today. I will hand it back in class on Friday.
• Feb. 13 We began Chapter 8 on graphs. We covered Section 8.1, and started Section 8.2. You should the differences between simple graphs, multigraphs, pseudographs, directed graphs, and directed multigraphs. Also, know the following terms: adjacent, incident, degree, isolated vertax, pendant vertix, in-degree, out-degree, complement graph. Know the the Handshaking Theorem. HWA 14 was also handed back.
• Feb. 10 Please note that the HWA due for today should have said Section 7.4 on web, not Section 7.5. I have decided not grade count the questions from 7.4, but I have asked the grader to still mark them so you can use them to study.
• Feb. 10 Today we did a review of Chapter 7. We also looked at the Oracle of Bacon and the Erdos Number. (You need to be on a school computer to access the second link.)
• Feb. 8 We looked at Section 7.6 on partial orders. You should know the definition, and know the definition for such things at poset, totally ordered set, incomparable elements comparable elements, and lexicographical orders.
• Feb. 6 Section 7.5 was covered today. You should know what an equivalence relation is. As well, know what we mean by an equivalence class, and how equivalence classes are related to partitions.
• Feb. 3 Today we talked about the closure of relations. After today's class you should be able to find the closure of the reflexive, symmetric, and transitive relations. A new HWA was also given out.
• Feb. 1 I added the review sheet for the Midterm.
• Feb. 1 Today we covered Section 7.3 on representing relations. You should know how to associate to a relation a zero-one matrix, and how to use this matrix to determine if the relation is reflexive, symmetric or antisymmetric. As well, you should be able to use the zero-one matrix to compute the composite of two relations. HWA 12 was also handed back in class.
• Jan. 30 We finished Sections 7.1 and 7.2 today. You should know how to make the composite of two relations, and know what is meant by the terms n-ary relation, n-tuple, projection.
• Jan. 27 Today was the first lecture of Chapter 7 on relations (our topic for the next two weeks). After today's class you should know what a relation is, and know some terms associated to relations, like: reflexive, symmetric, antisymmetric, and transitive. A new HWA was also given out.
• Jan. 25 We went back to Section 2.7 to look at matrices. After today's class you should know the basic definitions associated to a matrix, and how to add and multiply two matrices together. We also introduced the Boolean AND and Boolean OR. You should know how to use these operations in conjunction with zero-one matrices.
• Jan. 23 We covered two related sections today: Sections 6.5 and 6.6. Both sections discussed topics related to the principle of inclusion-exclusion. You should know what this principle is, and how to do examples like those in class.
• Jan. 20 We finished Section 6.4 on generating functions. We saw how we can use generating functions to answer some counting questions, and how to use them to solve recurrence relations. We also discussed generalized binomial coefficients.
• Jan. 18 Today we did the first of two lectures on Section 6.4. You should know what a generating function is, and what we mean by its closed form. You should be able to do examples like those done in class.
• Jan. 16 Class was cancelled again today since I could not fly into Thunder Bay.
• Jan. 13 Class is cancelled for today.
• Jan. 11 We finished section 6.2. After today's class, you will be able to solve an linear homogeneous recurrence relation of degree 1 and degree 2. You do not need to know how to do higher order degrees. I also gave out HWA 11 since I will be gone on Friday. HWA 10 is due Monday instead of Friday.
• Jan. 9 Today we started Section 6.2. During the next two classes, we want to be able to solve linear homogeneous recurrence relations of degree 1 and degree 2. After today's class you should know what a linear homogeneous recurrence relation is, how to solve those of degree 1, and how to solve some of degree 2.
• Jan. 6 We finished Section 6.1 on recurrence relations. You should be able to do problems like thos in class. I also gave out the first homework assignment. Note: Since I will be gone next Friday, this assignment will be due on Jan. 16th.
• Jan. 4 Welcome back! In today's class I handed back the Christmas Midterms. I also introduce the material of Section 6.1. For the next week or so, we will look at recurrence relations. You should know what a recurrence relation is, and what we mean by initial conditions.

• The Christmas Exams have been marked (you will get them back in the new year). Your grade and first semester mark can be found below: Christmas Exam and First Semester Marks
• Dec. 3 HWA 9 has been graded. You can find your assignment in a folder outside of my office door (the solutions are online). I have also calculated your mark for Math 1281 up to the Christmas Exam. You can find the marks on my office door, or using the link below: PreExam Marks Please double check your grades and let me know of any problems.
• Nov. 30 I discussed the format of the exam, and we did some review problems. Exam Format Change: Please note that Part B will now only have 4 questions (each worth 5pts) and Part C will have three questions (and you have to pick one).
• Nov. 28 In today's lecture, we covered the remaining material of Section 5.2. In particular, we learned about independent events and Bernoulli Trials. Please note I will be gone tomorrow and Wednesday morning, so I will not be having my regular office hours.
• Nov. 28 To help you study for the Christmas Exam, you can find a copy of last year's exam here: 2004 Christmas Exam You can find the solutions to the Christmas Exam in ERES. (The solutions should be online by late today, or by tomorrow.)
• Nov. 25 I covered one more topic in Section 5.1, and then I moved onto Section 5.2. We talked about assigning probabilities, conditional propability, and independence of events. I also gave out the last HWA for the semester. Please note that it is due next Thursday, Dec. 1.
• Nov. 23 We began Chapter 5. I introduced discrete probability, and some of the associated terms, e.g., sample space, experiment. We did a number of examples as well.
• Nov. 22 I added the review sheet for the Christmas Exam to the web.
• Nov. 21 We finished Section 4.5 by talking about the number of permuations that can be made from a set with indistinguishable objects. I also introduced the notion of a lexicographical order from Section 4.6.
• Nov. 18 We continued our discussion of Section 4.5. We saw how the methods we learned on Wednesday allow us to count the number of integer solutions to some equations. HWA 6 was handed back; HWA 7 was due today, and HWA 8 was given out.
• Nov. 16 Today I gave the first of two lectures on the material of Section 4.5. You should know the formulas for counting the number of r-perumations or r-combinations from a set with n elements when repetition is allowed.
• Nov. 14 We discussed binomial coefficients, and related topics like Pascal's Identity and Pascal's Triangle. This was the material of Section 4.4.
• Nov. 11 Today we were introduced to r-permutations and r-combinations. You should know the difference between these two things, and the formulas to calculate them. HWA 7 was assigned.
• Nov. 9 Today we discussed Section 4.2 on the Pigeonhole Principle, a new counting technique. You should be able to do problems similiar to the ones discussed in class.
• Nov. 7 Today we started Chapter 4 on counting. I introduced some very basic counting techniques: sum rule, product role, principle of inclusion-exclusion, and tree diagrams. I also gave examples of each method. HWA 5 was also handed back.
• Nov. 4 Today we covered Section 3.4 and the beginning of Section 3.5. You should know what a recursive defined function, sequence, and set are. Also, you should know what a recursive algorithm is, and know some simple examples. The new assignment (HWA 6) was also given out.
• Nov. 2 We spent another lecture on mathematical induction. By the end of this class, I expect you to be able to do problems like we did in class. On Friday we look at Section 3.4.
• Oct. 31 I introduced proofs by induction. We will continue to look at Section 3.3 on Wednesday's class.
• Oct. 28 Today we looked at Section 3.2 on sequences and summations. You should know what a sequence it, a geometric and arithmetic progression, a summation, how to shift indices in a summation, a double summation, and how to sum over a set. We also looked at the The On-line Encyclopedia of Integer Sequences
• Oct. 26 We looked at Section 3.1. We looked at proof strategies, and discussed how a proof is constructed. You should also know what a conjecture and counterexample are. I also handed back to the midterm.
• Oct. 24 We discussed public key encryption systems (Section 2.6). In particular, we discussed the RSA system. Please note: I hope to hand back the midterms on Wednesday in class.
• Oct. 20 I added the next homework assignment to the web. Note the due date.
• Oct. 19 We discussed Section 2.6 on some further properties of integers. You should know how to solve some simple linear congruences.
• Oct. 17 Today we finished our discussiong of Section 2.4 by talking about modular arithmetic. We also discussed the Euclidean Algorithm for find the gcd of two numbers. I handed back assignments 3 and 4.
• Oct. 14 Today we started talking about Section 2.4. I introduced some inportant definitions from number theory: prime numbers, division, division algorithm, gcd, and lcm. The fourth homework was due in class. You assignment for next week is to study for the midterm which is next Friday.
• Oct. 12 We talked about section 2.3 on the time complexity of algorithms. I also handed out the review sheet for the first midterm. You can find it in the lefthand column.
• Note: Thre is no class on Friday, Oct. 7. Homework assignment 3, which was due on Friday, will be due Wed. Oct. 12
• Oct. 5 We covered Section 2.2 on growth of functions. You should know what we mean by the big-O notation, and how to find the witness to the relationship that f(x) is big-0 of g(x). I gave out homework assignment 4 (Due Oct. 14)
• Oct. 3 We started Chapter 2 today. We covered Section 2.1 on algorithms. You should know the three algorithms discussed in class.
• Sept. 30 Today we finished Chapter 1 by covering the remaining material of Section 1.8. You should know the following terms: domain, codomain, image, one-to-one, onto, inverse, composition, and graph. You should also know the ceiling and floor functions. A new homework assignment was also given out.
• Sept. 28 Today we covered the material of Section 1.7, and started on Section 1.8. You should know the various set operations (intersection, union, difference, complement). As well, you need to know how to use set membership tables to verify set identies. The definition of a function is also very important. The first homework assignment was handed back (you can access the solutions to the right). Note that the homework is out of 129, not 137 as it says on the assignment.
• Sept. 26 We covered the material of Section 1.6. You should know what a set is, you should know the various ways to describe a set (listing elements, set builder notation, Venn diagrams), special terms like empty set, subsets, cardinality, and you should know the set constructions like the power set and the Cartesian product.
• Sept. 23 Today we finished the material of Section 1.5. We discussed some more methods of proof, and gave some examples. A new homework assignment was given out.
• Sept. 21 We continued our discussion of Section 1.5. You should know the rules of inference involving quantifiers. As well, you should be able to do problems like we did in class. I also began a discussion on methods of proof, a discussion we will conclude on Friday.
• Sept. 19 Today we began the first of three lectures on Section 1.5. There is a lot of important material in this section, so make sure you understand it! Today we talked about the rules of inference. You should know what they are, be able to identify the rules of inference used in an argument, and to do problems similar to Examples 6 and 7 in the text.
• Sept. 16 We talked some more about quantifiers. We finished up Section 1.3 and Section 1.4. We learned about nested quantifiers, negation of quantifiers, and how to translate statements involving quantifiers. The first homework assignment was also given out.
• Sept. 14 After today's class, you should know how to construct truth tables, and know what a propositional function, tautology and contradication are. As well, you should know what the universal and existential quantifier are.
• Sept. 12 We continued our discussion of Section 1.1. We talked about two more logical operators: implication and biconditional. We also discussed the problem of translating sentences into compound proopostions, and back again.
• Sept. 9 In today's, I introduced the material of the course. I also gave out a handout decribing the course (you can download it to the left). I also gave a lecture. I covered part of Section 1.1. You should know what the following are: proposition, compound proposition, logical operator, and truth table. As well, you should understand the first four logic operators: negation, conjunction, disjunction, and exclusive or.
• Sept. 2 The text books have not arrived at the bookstore. I have been told that they should arrive Sept. 12 or 13. There are used copies floating around. However, you will not need your text book for the first couple of lectures.
• Aug. 15, 2005 Webpage was setup. Welcome!