Math 1281 -- Discrete Mathematics

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.

---

End of year information The final exam was on April 22, 2008 in UC 2011 from 1:00-4:00PM You can check your Final Mark plus Exam Mark. You can also check your Pre-exam Grades. Have a great summer!

News (Last Updated April 24, 2008)

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

Semester 2

• April 24, 2008 Marks submitted.
• April 22, 2008 We had the final exam.
• April 8, 2008 Today was our last class! We did some review for the final exam.
• April 7, 2008 We finished Section 11.4 on Karnough maps. Given a Boolean expression, you should know how to use a Karnough map to simplyify your expression.
• April 4, 2008 We looked at Section 11.3 and how to design circuits.
• April 2, 2008 We covered Section 11.2 on how to find a Boolean Expression for a Boolean Function. I also discussed the concept of functional completeness.
• March 31, 2008 We started the class with the course evaluations. We then talked about Boolean functions, the focus of our last chaper, Chapter 11.
• March 28, 2008 We finished Section 10.4 on spanning trees by describing the second algorithm, the breadth first search. I then talked about spanning trees of minimal weight, and two algorithms, Prim's and Kruskal's algorithms, to find the spanning tree of smallest weight. See Section 10.5. I also handed back HWA 16.
• March 26, 2008 I talked about binary search trees (see Section 10.2) and discussed spanning trees and the depth first search algorithm.
• March 19, 2008 Today's class was on trees, i.e., graphs without circuits. See Section 10.1.
• March 17, 2008 We finished our discussion of planar graphs. I also discussed the problem of colouring graphs (Section 9.8).
• March 14, 2008 Happy Pi Day (March 14 = 03/14)! We study Planar Graphs (Section 9.7). As part of our discussion, we talked about Euler's formula. HWA 16 was assigned, and HWA 15 was due in class.
• March 12, 2008 We looked at Section 9.6 on the Shortest Path Problem. You should know how to find the shortest path, and also know the travelling salesman problem.
• March 10, 2008 We finished Section 9.5 by discussing Hamilton circuits and paths. I also handed back Midterm IV.
• March 7, 2008 Midterm IV was today.
• March 5, 2008 I finished 9.4 on connectivity by explaining how to use the adjacency matrix to compute the number of paths between a pair of vertices. I also began our discussion of Euler circuits and paths (Section 9.5).
• March 3, 2008 We looked at Section 9.4 on the notion of connectedness in a graph. I also handed back HWA 14.
• Feb. 29, 2008 I discussed Section 9.3 on how to represent graphs using matrices. I also talked about the question of deciding whether to two graphs isomorphic.
• Feb. 27, 2008 We finished Section 9.2 by going over some special families of graphs, and looking at how one can make new graphs from old graphs. The next midterm (next week Friday) will cover up to today's material. I also handed back the last assignment.
• Feb. 25, 2008 Class will be cancelled today because of the broken water line. Enjoy your extra day of break!
• Feb. 15, 2008 I started Chapter 9 by going over the material of Section 9.1 and 9.2. HWA 13 was due, and HWA 14 was given out. I also gave out the review sheet for the next midterm.
• Feb. 14, 2008 I added the Midterm 4 Information sheet to the webpage. Please note the information about how I will calculate your final mark.
• Feb. 13, 2008 I reviewed some of the material of Chapter 8. As an application, I discussed the Kevin Bacon Number (see the Oracle of Bacon) and the Erdos Number
• Feb. 11, 2008 We covered the material on Section 8.6, namely partial orders. You should know the terms: poset, comparable and incomparable elements, maximal and minimal elements, and a know how to make a Hasse Diagram of a poset.
• Feb. 8, 2008 I discussed Section 8.5 on Equivalence Relations. HWA 12 was due today, and I gave out HWA 13.
• Feb. 6, 2008 Today's lecture was on Section 8.4, on the closure of relations. In particular, we showed how to take a relation that was not reflexive/symmetric/transitive, and turn it into a relation that was reflexive/symmetric/transitive. I also gave back HWA 11.
• Feb. 4, 2008 We discussed two ways to represent a relation: a zero-one matrix and a digraph. See Section 8.3 for more.
• Feb. 1, 2008 I finished Section 8.1 by discussing the composite of two relations. I also covered Section 8.2 on n-ary relations. HWA 11 was due in class today, and I gave out HWA 12.
• Jan. 30, 2008 We started Section 8.1 on relations. Know the terms like reflexive, symmetric, anti-symmetric, and transitive.
• Jan. 28, 2008 I went back to Section 3.8 to cover the material on matrices. The material on 0-1 matrices will appear next week when we discuss representing relations. I also handed back Midterm 3.
• Jan. 25, 2008 Today was Midterm 3.
• Jan. 23, 2008 We went over Section 7.4 on generating functions. Know what such a function is, how to find the closed form, and how to use it to solve some types of counting problems.
• Jan. 21, 2008 We finished Section 7.2 on linear homogenesou recurrence relations. After today's class, you should be able to solve any such equation of degree 1 or 2. HWA 10 was handed back.
• Jan. 18, 2008 Today, we discussed linear homogeneous recurrence relations, and how to solve such equations of degree 1 and 2. See Section 7.2 for more. Note that HWA 10 was due today, and the homework for next week is studying for the third midterm.
• Jan. 16, 2008 We started Chapter 7 by looking at recurrence relations and some examples. Please see Section 7.1 for more.
• Jan. 14, 2008 Today we went over Bayes' Theorem (Section 6.3) and described how Bayes' Theorem can be used in the construction of spam filters. Note that the next midterm covers up until today's material.
• Jan. 11, 2008 We went over the idea of assigning probabilities, conditional probability, and independent events (see Section 6.2). I also went over the Birthday problem found in the text.
• Jan. 9, 2008 In today's class I introduced the idea of Discrete Probability. See Section 6.1 for more.
• Jan. 7, 2008 Class cancelled.

Semester 1

Use the following link to see your: First Semester Marks for Math 1281 Please let me know if there are any corrections. Note that I haven't included any of the challenge assignment marks.

• Nov. 30, 2007 HWA 9 is graded (and can be found outside my office door). I have also determined all the first semester marks. See the link above.
• Nov. 29, 2007 We finished our discussion of Section 5.5. I also introduced the idea of lexicographical order in order to list all permuations. Today was our last class of the semester. HWA 9 was due in class today.
• Nov. 28, 2007 We continued our discussion of Section 5.5 on combinations with repetition. We spent some time discussing the number of interger solutions to some equations.
• Nov. 26, 2007 In today's class we looked at counting the number of permutations and combinations when repetition is allowed (Section 5.5)
• Nov. 23, 2007 Binomial coeffecients (Section 5.4) we introduced and studied. Know the definition, the Binomial Theorem, Pascal's Identity and Triangle, and Vandemonde's Identity. The last HWA was assigned, and HWA 8 was due in class.
• Nov. 21, 2007 We stated and proved the formulas for the number of permutations and combinations from a set when repetition is not allowed. See Section 5.3 for more details.
• Nov. 19, 2007 We went over Section 5.2 on the pigeonhole principle. I also handed back Midterm II.
• Nov. 16, 2007 Midterm II was today.
• Nov. 14, 2007 Today we started Chapter 5 on counting. You should know the two basic counting principles: the general sum rule and general product rule. Other techniques that are important include the princple of inclusion-exclusion and tree diagrams. I also assigned HWA 8.
• Nov. 12, 2007 We finished Chapter 4 with a discussion on recursion. In particular, we talked about recrusive functions and sequences, sets defined recursively, and recursive algorithms. See Sections 4.3 and 4.4. I also handed back the latest HWA.
• Nov. 9, 2007 There will be on class on Friday. Please put your HWA under my office door (RB 2015) before 2:30 on Friday.
• Nov. 7, 2007 We discussed Section 4.2 on Strong Induction, another flavor of induction.
• Nov. 5, 2007 Today was the first lecture (of many) on proofs by induction. Please see Section 4.1 for more.
• Nov. 2, 2007 We talked about public key cryptography, one of the applications of Section 3.7.
• Oct. 31, 2007 From Section 3.6, we talked about the Euclidean algorithm. From Section 3.7, we discussed solving linear congruences and Fermat's Little Theorem.
• Oct. 29, 2007 Today we talked about Section 3.5 on prime numbers, GCDs, and LCMs. I also handed back HWA 5.
• Oct. 29, 2007 I will move today's office hours to tomorrow, Tuesday, October 30 from 2:30-3:30
• Oct. 26, 2007 Integers and division were discussed today. See Section 3.4 for more.
• Oct. 24, 2007 Today we talked about the complexity of algorithms (Section 3.3). In particular, we talked about time complexity. Know the difference between terms like constant complexity, logarithmic complexity, etc.
• Oct. 22, 2007 We discussed the growth of functions (Section 3.2). In particular, I introduced big-O notation.
• Oct. 19, 2007 Today I gave some more examples of algorithms. In particular, we talked about the binary search algorithm, bubble sort, and greedy algorithms. I also assigned HWA 5.
• Oct. 17, 2007 We started Chapter 3. I introduced the ntion of an algorithm, and discussed some simple examples (finding the max element in a list and searching for an element in a list). As well, I went over the basics of pseudo-code (see Appendix 3).
• Oct. 15, 2007 We continued our discussion of Chapter 2 by looking at sequences, series, and summations (Section 2.4). I also handed back Midterm I.
• Oct. 12, 2007 Midterm I was today.
• Oct. 10, 2007 I introduced the notion of a function in today's class (Section 2.3). You need to know what a function is, the difference between an onto and one-to-one function, a bijection and inverse, the graph of a function, and the ceiling and floor functions. I also handed back HWA 3.
• Oct. 9, 2007 Starting this week, all future assignments will be given out on Friday, and due the following Friday. This means we will be able to use the Lab to talk about the HWA.
• Oct. 5, 2007 Class was cancelled today.
• Oct. 3, 2007 Today's class was on set operations: union, intersection, and complement. Know how to use these operations, and how to prove two sets are equal using a membership table. HWA 3 was due today. There is no HWA for next week -- instead, your homework is to study for the midterm. I also handed out a review sheet (see column to right) describing the midterm.
• Oct. 1, 2007 We started a new chapter today; in particular, we talked about sets (Section 2.1). You should know what a set is, the null set, a subset, the power set, the cardinality of a set, and the cartesian product of a set. I also handed back HWA 2.
• Sept. 28, 2007 In today's class we did a review of Chapter 1 and discussed some common problems of the class. The first midterm will cover all of Chapter 1.
• Sept. 26, 2007 We finished the last section (Section 1.7) of Chapter 1. I talked about some strategies for finding a proof. In particular, I discussed the idea behind "Forward-Backward Reasoning". I also talked about conjectures and their roles in mathematics.
• Sept. 24, 2007 We continued our discussion on proofs and proof strategies. I discussed how to prove statements with biconditionals, prove statements via cases, exhaustive proofs, proofs with quantifiers, and I talked about some common errors in proofs. See Sections 1.6 and 1.7 for this material. Note: I have to cancel my office hour for today because of a meeting.
• Sept. 21, 2007 We covered Section 1.6 on the introduction to proofs. In this important section, I discussed some types of proofs: direct proofs, indirect proofs, proof by contradiction, and proof with if and only if statements. I gave examples of each type of proof, and some common mistakes in proofs.
• Sept. 19, 2007 Today we looked at the rules of inference that involve quantifiers. This finished our look at Section 1.5. HWA 1 was due in class, and HWA 2 was given out.
• Sept. 17, 2007 We looked at Section 1.5 on the Rules of Inference. By the end of today's class, you should know the eight rules, and how to use them to show that a collection of hypotheses imply a given conclusion.
• Sept. 14, 2007 We looked over Sections 1.3 and 1.4 on propositional functions and nest quantifiers. I large portion of the class was spent on the problem of translating between English statements and statements involving quantifiers.
• Sept. 12, 2007 Today I discussed Propositinal Equivalences, Predicates and Quantifiers (see Section 1.2 and 1.3). I also gave out the first HWA (see the column to the right).
• Sept. 10, 2007 I finished up Section 1.1 by going over the remaining logical operators. You should know all the logical operators and their truth tables. I also started discussing the problem of translating sentences into compound propositions, and vice versa.
• Sept. 7, 2007 Today was the first day of class. I started by giving an introduction to the class, and going over the course handout (you can find a copy to the right). I also began our discussion of Section 1.1. I explained what a proposition is, and I introduced three of the six logical operators: negation, conjuction, and disjuntion.
• Aug. 8, 2007 The webpage was linked to my main webpage. Also, all handouts were added to the webpage. I know that school is still a month away, but if you are proactive, you can find a used copy of the textbook on the web. The textbook information is to the right.

Course Information

Instructor: Adam Van Tuyl

Office: RB 2015
Office Hours: M 2:30-3:30 and W 3:30-4:30
Email: avantuyl AT sleet.lakeheadu.ca

Place and Time:

Class: MWF 1:30-2:30 in RB 2047
Lab: W 2:30-3:30 in RB 3044

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 Wednesday Friday, and will be due, at the beginning of class, the following WednesdayFriday. Assignments must conform to the guidelines in the course outline. Assignments are posted below.

Assignment 1 (Due: Sept 19)

Sec. 1.1 -- 6aceg, 10ace, 14, 20gh, 24a, 28adf, 32bd
Sec. 1.2 -- 8bd, 10d, 18, 32, 46
Sec. 1.3 -- 8, 12aceg, 16bd, 24ab, 32ace

Assignment 2 (Due: Sept 26)

Sec. 1.4 -- 4ace, 12abdeh, 14abc, 20ab, 24ab, 30bc
Sec. 1.5 -- 4, 6, 10af, 14ad, 18, 20

Assignment 3 (Due: Oct 3)

Sec. 1.6 -- 2, 6, 14, 18, 28, 38
Sec. 1.7 -- 6, 12, 20, 28, 38 Bonus - 8

Assignment 4 (Due: Oct 19)

Sec. 2.1 -- 6, 8aceg, 18, 22, 28ab, 34ab
Sec. 2.2 -- 4, 18e, 24, 30, 34, 48ab
Sec. 2.3 -- 4ab, 8abcd, 16, 26ac, 46

Assignment 5 (Due: Oct 26)

Sec. 2.4 -- 4, 6adg, 10abeg, 14, 18ac, 20, 24
Sec. 3.1 -- 4, 6, 16, 18, 20 36, 52

Assignment 6 (Due: Nov. 2)

Sec. 3.2 -- 2abcd, 6, 12, 18
Sec. 3.3 -- 2, 4, 8 Bonus 28a
Sec. 3.4 -- 6, 8, 16, 22, 24, 32a

Assignment 7 (Due: Nov. 9)

Sec. 3.5 -- 4ad, 10, 12ad, 14a, 20abce, 22abce, 32 Bonus: 14b
Sec. 3.6 -- 24bdf, 26
Sec. 3.7 -- 4, 6, 10, 12, 28a, 46

Assignment 8 (Due: Nov. 23)

Sec. 4.1 -- 4, 6, 20, 32
Sec. 4.2 -- 4, 8, 32
Sec. 4.3 -- 4ab, 8ac, 22, 24ab
Sec. 4.4 -- 8, 32

Assignment 9 (Due: Nov. 29)

Sec. 5.1 -- 6, 8, 16, 22abef, 30ab, 34, 40ab
Sec. 5.2 -- 6, 8, 16, 18
Sec. 5.3 -- 10, 12, 22bdf, 36
Sec. 5.4 -- 8, 12, 20, 28b

Assignment 10 (Due: Jan. 18)

Sec. 5.5 -- 12, 16, 20, 32, 40
Sec. 5.6 -- 2, 4bf
Sec. 6.1 -- 10, 14, 16, 24d, 34
Sec. 6.2 -- 2, 8, 12, 16
Sec. 6.3 -- 2, 8, 18

Assignment 11 (Due: Feb. 1)

Sec. 7.1 -- 2d, 4c, 8b, 18, 28
Sec. 7.2 -- 2bdf, 4aefg, 38
Sec. 7.4 -- 4bdh, 6d, 10b, 18, 30be

Assignment 12 (Due: Feb. 8)

Sec. 3.8 -- 2a, 4c, 10, 28, 30, 32
Sec. 8.1 -- 4, 10, 16, 24, 30, 32ab, 40
Sec. 8.2 -- 2, 10, 14

Assignment 13 (Due: Feb. 15)

Sec. 8.3 -- 2d, 4c, 10b, 12, 14abcd, 26
Sec. 8.4 -- 6, 8, 18adg, 20, 26b
Sec. 8.5 -- 2be, 12, 22, 32, 46ace

Assignment 14 (Due: Feb. 29)

Sec. 8.6 -- 4, 8c, 10, 14, 22c, 32
Sec. 9.1 -- 8, 16
Sec. 9.2 -- 2, 8, 12, 18, 20ad, 22, 26b, 32

Assignment 15 (Due: March 14)

Sec. 9.3 -- 6, 18, 20, 30, 34, 36, 40, 48, 50
Sec. 9.4 -- 2ad, 10, 12, 18, 30, 32
Sec. 9.5 -- 2, 4, 10, 26

Assignment 16 (Due: March 26) (Note date change!)

Sec. 9.5 -- 30, 36, 38, 40, 44
Sec. 9.6 -- 2, 6ad, 14, 18, 20, 26
Sec. 9.7 -- 6, 8, 12, 14, 15, 20, 24, 26

Assignment 17 (Due: April 4)

Sec. 9.8 -- 10, 15, 18, 20, 24
Sec. 10.1 -- 4, 6, 10c, 12a, 14, 18, 44
Sec. 10.2 -- 2, 4
Sec. 10.4 -- 4, 10, 14, 16 (do 14 only), 20, 24
Sec. 10.5 -- 4, 8, 10, 12, 14

Assignment 18 (Due: April 8 at 5PM at my office) (Note change of time!)

Sec. 11.1 -- 6bc, 10, 12, 18, 28bc
Sec. 11.2 -- 4ad, 12cd, 15, 16
Sec. 11.3 -- 2, 4, 6ac, 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'm trying something new this year. 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 Assignment 1
Due: Sept. 21, 2007

Challenge Assignment 2
Due: Nov. 9, 2007

Challenge Assignment 3
Due: Feb. 1, 2008

Challenge Assignment 4
Due: March 14, 2008

Grading Scheme

Your final mark is broken down as:

Homework = 10%
4 Midterms = 50% (12.5% each)
Final Exam = 40%

Note: In calculating your final mark, I will calculate your midterm mark in two ways: (1) I will use the method described in the course handout, i.e., each test will be work 12.5%; (2) I will drop the lowest midterm and add its weight to final exam. So, midterms will be worth 37.5% and your final 52.5%. I will then take the highest of the two marks.

Important Dates

Sept. 6, 2007
First semester classes begin

Oct. 5, 2007
Class cancelled (I'm at a conference)

Oct. 8, 2007
Thanksgiving (no class)

Oct. 12, 2007
Midterm 1

Nov. 16, 2007
Midterm 2

Nov. 29, 2007
First semester classes end

Jan. 7, 2008
Second semester classes begin

Jan. 25, 2008
Midterm 3

Feb. 7, 2008
Last day to drop without penalty

Feb. 18-22, 2008
Reading Break

March 7, 2008
Midterm 4

March 21-24, 2008
Easter Break (no classes)

April 10, 2008
Second semester classes end

April 14-26, 2008
Final Exams

Links

Lakehead University

LU Math Department

Adam's Home Page

Student Code of Conduct