Math 1281 -- Discrete Mathematics (2010-11)

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.

PreExam Marks

HWA 18 has now been graded and can be picked up in my office. You can also check out your current mark before the exam here: PreExam Marks for Math 1281

If you notice any problems, please see me as soon as possible so we can make corrections.

News (Last Updated April 11, 2011)

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

Semester 2

April 1 Our last day of class. We did some review for the final exam.
March 30 We discussed Section 11.4 on Karnough maps.
March 28 We continued looking at Chapter 11. We looked at section 11.2, and described how to use miniterms to represent any boolean function, and Section 11.3, which introduces logic gates.
March 25 Our first class on boolean functions. See Section 11.1. HWA 17 was due, and we also did course evaluations.
March 23 Things we discussed today: the breadth first search algorithm, Prim's algorithm, and Kruskal's algorithm. I also handed back HWA 16.
March 21 Continuing our discussion of trees, we looked at binary search trees (Section 10.2) and the idea of a spanning tree.
March 18 Today's class was an introduction to Trees (Chapter 10)
March 16 We finished Chapter 9 by looking at the problem of colouring graphs. I also handed back HWA 15.
March 14 Happy Pi Day. Today we looked at planar graphs (see Section 9.7)
March 11 We looked at Section 9.6 that discussed how to find the shortest path in a weighted graph. We also talked about Travelling Salesman Problem. I handed back the midterm.
March 9 Class canceled due to a power outage.
March 7 We looked at the problem of finding Hamilton circuits and paths in a graph.
March 4 Midterm IV was today.
March 2 We finished up connectivity, and then we discussed Euler paths and circuits (Section 9.5).
Feb 28 Welcome back! Today's topic was Section 9.4 (Connectivity). I also handed back HWA 14.
Feb 18 Today we looked at Section 9.3 which describes ways to represent a graph. We also looked at the problem of determining if two graphs are the same (see Section 9.4).
Feb 16 We spent today's class going over some graph theory terminology, like complete graph, bipartite graph, and induced graph. See Section 9.2 for more. The latest homework assignment was also handed back.
Feb 14 Today's class was an introduction to graph theory. We defined a graph, and some of the basic terminology (e.g. degree of a vertex). See Sections 9.1 and 9.2 for more.
Feb 11 We did a review of relations. As special examples, we looked at the Oracle of Bacon and the Erdos Number. (the second link will only work if you are on campus). HWA 13 was due, and HWA 14 was assigned.
Feb 9 We continued our look at special types of relations. In particular, we looked at partial orders. See Section 8.6.
Feb 7 We looked at equivalence relations. I also handed back HWA 12 and Challenge Assignment 3.
Feb 4 We considered the propblem of finding the closure of a relation (Section 8.4). HWA 12 was due, as was Challenge Assignment 3.
Feb 2 We showed how to use zero-one matrices and digraphs to represent matrices (See Section 8.3)
Jan 31 We continued our introduction to relations. You should know how to construct the composition of two relations, and what it means to form relations on many sets. See Section 8.1 and 8.2.
Jan 28 Today was our first look at relations on a set (see Section 8.1). You should know terms like: reflexive, symmetric, antisymmetric, and transitive. I also handed back Midterm III and assigned HWA 12
Jan 26 We went back to Section 3.8 to talk about matrices. In particular, you should know what a 0-1 matrix is, and the boolean operations one can do with 0-1 matrices. I hope to have Midterm III graded by Friday.
Jan 24 Todays topic: principle of inclusion/exclusion.
Jan 21 Midterm III!
Jan 19 Today we looked at generating functions (Section 7.4). I also assigned HWA 11 which is due next week Friday.
Jan 18 We finished our discussion on linear homogeneous recurrence relations of degree 2. HWA 10 was handed back.
Jan 14 Today we looked at the problem of solving recurrence relations of order 1 and 2. (See Section 7.2). There is no HWA this week, but you need to study for the midterm. HWA 10 was collected.
Jan 12 Today's class was the start of Chapter 7. We looked at sequences defined recursively (Section 7.1).
Jan 10 We looked at Section 6.3 on Bayes Theorem. We discussed two examples: false postives and spam filters.
Jan 7 We examined Section 6.2 on assigning probabilities. Your next homework assignment was also given out.
Jan 5 We looked at Section 6.1 on discrete probability. I also handed back HWA 8 and 9.
Jan 3 Happy New Year! I have changed my office hours for the semester (they are now MWF from 11:30-12:30). I have also added some more info to the webpage (e.g. the next HWA has been added, as well as the review sheet for the next midterm). See you on Wednesday.

Semester 1

First Semester Marks

You can now view your marks for the first semester: First Semester Marks Please make sure you marks have been recorded correctly. Feel free to stop by my office if you have corrections and/or to pick up your old homework assignments.

Have a good Christmas!
-AVT

Dec. 1 Our last class for the semester. We discussed the rest of Section 5.5. Just a reminder that there is no class on Friday and Monday. However, your HWA 9 is due on Monday under my office door. I will calculate your first semester mark hopefully by Dec. 10. Good luck with your exams, and see you in January!
Nov. 29 In today's class, we discussed combinations with repetition.
Nov. 26 We talked about binomials and Pascal's Triangle. HWA 8 was due in class today.
Nov. 24 Today's lecture was on Section 5.3 where we counted the number of r-combinations and the number of r-permutations.
Nov. 22 We looked at Section 5.2 on the pigeonhole principle. I also handed back mditerm II.
Nov. 19 Midterm II was today.
Nov. 17 We started Section 5.1 on counting. I also handed back HWA 6 and 7.
Nov. 15 We continued our discussion of Chapter 4 by looking at Sections 4.3 and 4.4, both of which talked about recursion. We talked about the idea of a recursive set, sequence, function, and algorithm.
Nov. 12 I was out of town today, so Dr. A.J. Dean gave a lecture on strong induction. The latest HWA was also collected.
Nov. 10 Today was our first class on the topic of Mathematical Induction.
Nov. 8 We finished our discussion of Chapter 3. We looked at Section 3.6, which talked about the Euclidean Algorithm, and from 3.7, we discussed the role of linear comibinations and how to write a gcd as a linear combination. As well, we talked about Fermat's Little Theorem.
Nov. 5 Class was cancelled today.
Nov. 3 Today's topic was prime numbers, gcds, and lcms (see Section 3.5 for more). I also handed back HWA 5.
Nov. 1 We started our discussion of Section 3.4 on integers and divisiblity. We also discussed modular arithmetic.
Oct. 29 For Halloween, I brought some candy! We also looked at how to measure the complexity of an algorithm. HWA 5 was collected, and HWA 6 was assigned.
Oct. 27 We talked about the growth of functions (Section 3.2), and in particular, how to use big-O notation.
Oct. 25 Now that we know a little bit about pseudo-code, we can look at algorithms (Section 3.1). I described two search algorithms (the linear search and binary search), and one sorting algorithm (bubble sort). We also talked about greedy algorithms.
Oct. 22 We jumped to the back of the book to look at Appendix 3 on pseudo-code. I also assigned HWA 5.
Oct. 20 We looked at Section 2.4 on sequences and summations. As part of our discussion on sequences, I introduced the Online Encyclopedia of Integer Sequences
Oct. 18 We went over section 2.3 on functions. I also handed back Midterm 1.
Oct. 15 Today was Midterm 1
Oct. 13 We did some review for Midterm 1. I went over some past questions of previous exams. I also returned HWA 3, and assigned HWA 4 (due next week Friday).
Oct. 8 Today we looked at Section 2.2 on set operations. I handed back HWA 2, and I collected HWA 3 and the challenge assignment. Your homework for this week is to study for Midterm I which is next week Friday.
Oct. 6 We looked at Section 2.1 on sets. You should know what a set is, how to construct sets like the power set and cartesian product, and know terms like the emptyset. Just a reminder that there is no lab tomorrow.
Oct. 4 We finished Section 1.7. I spent some time discussing how to find a proof (e.g. Forward-Backward Reasoning), and I also discussed the role of a conjectures in math.
Oct. 1 In today's class, we discussed some more types of proofs (those involving quantifiers). See Section 1.7 for more details. I handed back HWA 1, and collected HWA 2.
Sept. 29 We looked at Section 1.6 on types of proofs.
Sept. 27 We finished Section 1.5 on the rules of inference involving quantifiers, and we did some examples.
Sept. 24 We started Section 1.5 on the rules of inference. Your first HWA was due in class; the second HWA was assigned.
Sept. 22 We looked at Section 1.4 on nested quantifiers, i.e., propositional functions with more than one quantifier.
Sept. 20 Please note that our classroom will now be in RC 1001.
Sept. 20 We looked at Section 1.3 on proposition functions, universal quantifiers, existential quantifiers, and how to take the negation of a quantifier.
Sept. 17 We finished up Section 1.1 and covered 1.2. You should know how to construct truth tables, and how to verify two statements are logically equivalent. As well, you should be able to translate statments into compound propositions, and vice versa.
Sept. 16 The first two Challenge Assignments were added to the web (see links to the right).
Sept. 15 We looked at Section 1.1 on logical operators. You should know all the operators and their associated truth table.
Sept. 13 First day of class. I went over the course content, and some adminstrative details like office hours, and so on. I also introduced propositions, the building blocks of logic.
Sept. 6 One week to go! I added the first homework assignment to the web.
August 5 Added some more detail to the class web page (e.g. midterm dates).

Course Information

Instructor: Adam Van Tuyl

Office: RB 2015
Office Hours: MWF 11:30-12:30
Email: avantuyl AT lakeheadu.ca

Place and Time:

Class: MWF 10:30-11:30 in RC 1001
Lab: Th 10:30-11:30 in RC 1001

Textbook

Discrete Mathematics and Its Applications, 6th Edition
by K. Rosen

Homework Soutions

All the solutions to the homework and tests are posted electronically on eRES, the electronic reserves of Lakehead's library. The solutions are PDF files.

Homework Assignments

Homework is given out every Friday, and will be due, at the beginning of class, the following Friday. Assignments must conform to the guidelines in the course outline. Assignments are posted below.

Assignment 1 (Due: Sept 24)

Sec. 1.1 -- 8ace,14ac,20cd,28ac,32e
Sec. 1.2 -- 8b, 10c, 22, 32, 58

Assignment 2 (Due: Oct. 1)

Sec. 1.3 -- 6af, 16, 28acd, 32a, 36
Sec. 1.4 -- 4af, 12adk, 20bc, 32abd
Sec. 1.5 -- 4, 10af, 16bc, 30

Assignment 3 (Due: Oct. 8)

Sec. 1.5 -- 14ad, 18, 20, 24
Sec. 1.6 -- 2, 10, 18, 24
Sec. 1.7 -- 8, 20, 28, 38b

Assignment 4 (Due: Oct. 22)

Sec. 2.1 -- 4, 8abcd, 16, 22ac, 24, 34ab
Sec. 2.2 -- 4bc, 14, 18ab, 24, 30ab, 46a

Assignment 5 (Due: Oct. 29)

Sec. 2.3 -- 6ab, 8gh, 16, 30, 46
Sec. 2.4 -- 4ab, 6d, 10gh, 18cd
Appendix 3 -- 1, 2, 3

Assignment 6 (Due: Nov. 5)

Sec. 3.1 -- 4, 6, 8, 10
Sec. 3.2 -- 2ace, 8ac, 16
Sec. 3.3 -- 2, 8, 10a

Assignment 7 (Due: Nov. 12)

Sec. 3.4 -- 8, 10bc, 12, 18, 20
Sec. 3.5 -- 6, 10, 20, 22
Sec. 3.6 -- 24bdf,26
Sec. 3.7 -- 2bcd, 28a

Assignment 8 (Due: Nov. 26)

Sec. 4.1 -- 4, 8, 34, 38
Sec. 4.2 -- 4, 26ab, 30
Sec. 4.3 -- 2ab, 8ad, 12, 24ab
Sec. 4.4 -- 4

Assignment 9 (Due: Dec. 6 at my office)

Sec. 5.1 -- 14, 22de, 34, 40ac
Sec. 5.2 -- 4, 14, 18
Sec. 5.3 -- 18ac, 22bd, 38
Sec. 5.4 -- 8, 12, 32
Sec. 5.5 -- 14, 16ad, 18

Assignment 10 (Due: Jan. 14)

Sec. 6.1 -- 6, 12, 14, 30
Sec. 6.2 -- 2, 6ab, 12, 24
Sec. 6.3 -- 4, 6, 18

Assignment 11 (Due: Jan. 28)

Sec. 7.1 -- 4bc, 8d, 20, 28
Sec. 7.2 -- 2abcd, 4adg
Sec. 7.4 -- 4bch, 10b, 22

Assignment 12 (Due: Feb. 4)

Sec. 7.5 -- 6, 10, 16
Sec. 7.6 -- 2, 6, 10
Sec. 3.8 -- 4b, 10abc, 28
Sec. 8.1 -- 4ad, 10ad, 24, 28

Assignment 13 (Due: Feb. 11)

Sec. 8.1 -- 30, 36, 44abc
(Typo: replace S with R in #44)
Sec. 8.2 -- 2, 16
Sec. 8.3 -- 2ad, 6, 10b, 14abc, 24
Sec. 8.4 -- 4, 8, 10 26b (use Theorem 3)

Assignment 14 (Due: Feb. 18)

Sec. 8.5 -- 2ace, 8, 12, 22, 24ab, 44ace
Sec. 8.6 -- 4bd, 8c, 10, 14, 16a, 34abcd

Assignment 15 (Due: March 11)

Sec. 9.1 -- 4, 8, 16, 24
Sec. 9.2 -- 2, 8, 14, 20bc, 24, 32, 36a
Sec. 9.3 -- 8, 16, 28, 40, 48
Sec. 9.4 -- 10, 12, 20, 30, 36

Assignment 16 (Due: March 18)

Sec. 9.5 -- 4, 6, 28, 34, 44bc, 56, 60
Sec. 9.6 -- 2, 6d, 10c, 18, 25
Sec. 9.7 -- 6, 12, 15, 16, 24

Assignment 17 (Due: March 25)

Sec. 9.8 -- 6, 8, 16, 20, 24
Sec. 10.1 -- 2, 4, 10c, 18, 22
Sec. 10.2 -- 2, 14
Sec. 10.4 -- 4, 10, 14, 16 (14only), 24

Assignment 18 (Due: April 1)

Sec. 10.5 -- 2, 8, 12
Sec. 11.1 -- 6bc, 20
Sec. 11.2 -- 4bc, 12ac
Sec. 11.3 -- 2, 4, 6ad, 8

Handouts

All class handouts are available as PDF files.

Course Information
Handout for first day

Midterm 1 Information
Handout describing the first midterm

Midterm 2 Information
Handout describing the second midterm

Midterm 3 Information
Handout describing the third midterm

Midterm 4 Information
Handout describing the fourth midterm

Final Exam Information
Handout describing the final exam

Challenge Assignment

I will be giving out extra credit problems to work on that will allow you to learn the material in greater depth. There are four such assignments. Each will be worth up to 1 percent bonus.

Challenge 1 Assignment
Due: Oct 8

Challenge 2 Assignment
Due: Nov 12

Challenge 3 Assignment
Due: Feb 4

Challenge 4 Assignment
Due: March 18