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.

News (Last Updated April 6, 2010)

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

Final Exam Informtion:

The final exam will be on April 14, 2010 in RC 0005 from 9AM to 12PM. Here is some things to help you study:

Here are your marks up to, but not including the final. There are two final marks: the first is according to the weighting in the original course handout; the second is the weighting with the lowest midterm dropped.

PreExam Marks

Plese let me know ASAP if you notice any mistakes.

Semester 2

April 6 HWA 18 is now graded! Please come and pick up all old assignments some time before the final.
March 31 Our last formal class (I'll still be in class next Tuesday). We did some review for the final. I also handed back HWA 17.
March 29 We finished Chapter 11 today by looking at Section 11.4 on Karnough maps.
March 24 Today we looked at logic gates, and we can design circuits. I handed back HWA 16, and assigned HWA 18.
March 23 We looked at Section 11.2 on representing Boolean functions.
March 22 We started our last chapter (Chapter 11) on Boolean Algebra. Today we looked at Secion 11.1 where I inroduced the boolean opeartions, and boolean expressions.
March 19 We finished Section 10.4 by discussing the Breadth First Search. We also discussed minimal spanning trees, and how to find them, e.g. Prim's Algorithm and Kruskal's Algorithm. HWA 16 was due in class, and HWA 17 was assigned.
March 17 We looked at an application of a tree (Binary Search Tree) and looked at spanning trees, and how to construct them. See Sections 10.2 and 10.4 for more.
March 15 Today's was an introduction to trees (in the graph theory sense). See Section 10.1. I also handed back Midterm 4.
March 12 Midterm 4: Last of the Midterms!
March 10 We finished up Section 9.7 on planar graphs. You should know how to detemine if a graph is planar or not. We then talked about graph colouring. HWA 15 was returned, and HWA 16 was given out. Remember -- test on Friday!
March 8 Section 9.7 was covered. We discussed planar graphs, and the Euler's formula.
March 5 Today's topic was based upon shortest path problems. In particular, we discussed Dijkstra's algorithm and the travelling salesman problem (see Section 9.6). HWA 14 was returned. HWA for next week is to study for the midterm.
March 3 We looked at Hamilton circuits and paths (the rest of Section 9.5).
March 1 We finished Section 9.4 by discussing how to use the adjacency matrix of a graph to count the number of paths between two vertices. I also introduced Euler paths and circuits (Section 9.5). The review sheet for Midterm 4 was handed out (it is also available on this page).
Feb. 26 Today's topic was connectivity in graphs (Section 9.4). I assigned HWA 15, and HWA 14 was due in class.
Feb. 24 We looked at Section 9.3 which described the various ways to represent a graph. I also talked about the notion of two isomorphic graphs.
Feb. 22 Welcome back from Reading Break! In today's class I finished Section 9.2. We went over more graph terminology, and I introduced some special families of graphs.
Feb. 10 I introduced the idea of a graph today. See Sections 9.1 and 9.2 for more details. I also handed back HWA 12, and assigned HWA 14. Just a reminder that HWA 13 is due on Friday at noon under my office door.
Feb. 9 We had a class today instead of the lab. I reviewed the material of Chapter 8. As well, I discussed the Oracle of Bacon, and how we can view the Kevin Bacon Number as a relation. Also, to see what happens when you combine the Erdos number with Kevin Bacon number, you get the Erdos-Bacon Number.
Feb. 8 Today I introduced the idea of a poset and a partial order. We also talked about a totally ordered set and the lexicographical ordering. See Section 8.6 for more details.
Feb. 5 We went over Section 8.5 on equivalence relations. You should know the definition of an equivalence relation, how to form the equivalence class, and understand the connection to partitions. I also assigned HWA 13 and collected HWA 12.
Feb. 3 Today's class was on Section 8.4. We learned how to "close" a relation with either the reflexive, symmetric, or transitive property.
Feb. 1 We looked at how to use 0-1 matrices to represent matrices. I handed back Midterm 3 and HWA 11.
Jan. 29 Midterm 3 was today.
Jan. 27 We discussed the rest of Section 8.1, and we did a quick overview of Section 8.2 which discussed n-arry relations.
Jan. 25 We finished up Section 3.8, and started our discussion of relations, the topic of Chapter 8.
Jan. 22 We have no class today since we had one on Tuesday. However, your assignments are due by noon. They are to be placed under my office door (RB 2015)
Jan. 20 We went back to Section 3.8 to discuss the properties of matrices. In particular, you should know how to work with 0-1 matrices.
Jan. 19 We discussed Sections 7.5 and 7.6 on the principle of inclusion-exculsion. (We met during Tuesday's lab).
Jan. 18 Today's topic was generating functions (see Section 7.4).
Jan. 15 We finished Section 7.2 today. After today's class, you will be able to solve all linear homogeneous recurrence relations of degree one or two. HWA 10 was due in class today, and HWA 11 was assigned today. I also handed out the review sheet for Midterm III. NOTE: Next week, we will have class on Monday, Tuesday, and Wednesday. We will have class during the lab time.
Jan. 13 Today we started our discussion on Section 7.2 on how to solve linear homogeneous recurrence relations. We ended today's class with a formula for the Fibonacci sequence.
Jan. 12 I added the review sheet for Midterm III to the web. See to the right.
Jan. 11 Recurrence relations were introduced in today's class. See Section 7.1 for more on this topic.
Jan. 8 In today's class we looked at Bayes Theorem (Section 6.3). I also assigned HWA 10.
Jan. 6 We went over Section 6.2 on assigning probalities, conditional probability, and independent events.
Jan. 4 Happy New Year! Today we went over Section 6.1 on Discrete Probability. I explained some of the basic definitions, and I gave a handful of examples. Please note that my office hours have changed this semester. They are now MWF 10:00-11:00.

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.

Dec. 3 I finished Section 5.5. I also handed out a questionnaire about the first semester. HWA 8 was given back, and HWA 9 was due.
Dec. 2 We continued Section 5.5 by discussing combinations when repetition is allowed.
Nov. 30 We talked about the binomial theorem and Pascal's triangle (Section 5.4). I also started on Section 5.5 by discussing Section 5.5 on permutations with repetition.
Nov. 27 I finished Section 5.2 on the pigeonhole principle, and I talked about permutations and combinations (Section 5.3).
Nov. 25 We began Section 5.2 on the pigeonhole principle.
Nov. 23 We started Chapter 5 on counting. I also handed back the second midterm.
Nov. 20 Today was Midterm 2.
Nov. 18 We looked at the idea of recursion by studying recursive functions, recursive sequeneces, recursive sets, and recursive algorithms. See Sections 4.4 and 4.5. I also handed back HWA 7.
Nov. 16 We continued to look at Mathematical Induction (Section 4.2). In particular, we looked at Strong Induction. I did a number of examples involving induction.
Nov. 13 We started to look at Mathematical Induction (Section 4.1). I also handed back HWA 6 and collected HWA 7. Your homework for next week is to study for the midterm.
Nov. 11 We looked at Section 3.7 on Public Key Crytpography and a description of RSA.
Nov. 9 We looked at the Euclidean Algorithm from Section 3.6, and we discussed some of the results in Section 3.7, like Fermat's Little Theorem. We will use these results on Wednesday when we talk about RSA cyrptopgraphy. I handed back HWA 5, and collected HWA 6.
Nov. 6 I cancelled today's class because I was sick.
Nov. 4 Today's topic was Section 3.5 on prime numbers and the greatest common divisor.
Nov. 2 We looked at Section 3.4 on integers and division. You should know the division algorithm and modular arithmetic. I gave back HWA 4, and HWA 5 was due in class today. Also note that the next challenge assignment will be due next week Friday, not this Friday.
Oct. 30 Class cancelled. HWA 5 will be due on Monday.
Oct. 28 We looked at Section 3.3 on the complexity of algorithms. In particular, I related the idea of big-O notation from last class to the problem of determining the complexity of the algorithm
Oct. 26 We went over Section 3.2 on the growth of functions. Please note, that there is no class on this Friday. This weeks homework will be due on the following Monday.
Oct. 23 I started the class by going over pseudocode (see the appendices of the textbook for more). I then discussed some types of algorithms, like the linear search algorithm and the bubble sort algorithm. You should also know what a greedy algorithm is. HWA 4 was due in class today.
Oct. 21 We talked about cardinality, and in particular, countable sets. We showed that the integers and rational numbers have the same cardinality, but the real number is a larger set. We also began our discussion of algorithms (Section 3.1).
Oct. 19 I handed back Midterm 1. We also discussed Section 2.4 on sequences and summations. I showed the the class The On-Line Encyclopedia of Integer Sequences . Try the look-and-say sequence: 1, 11, 21, 1211, 111221,312211,13112221
Oct. 16 Midterm 1 was today.
Oct. 14 We had a review today on the material of Chapter 1. I also assigned next weeks assignment (HWA 4). HWA 3 will be graded by this afternoon -- you can come by my office either Wednesday afternoon or Thursday afternoon to pick it up.
Oct. 9 We went over functions today. You should know the following terms: one-to-one, onto, bijection. As well, you should know what we mean by the inverse function and the ceiling and floor functions. HWA 3 was due in class today. On Wednesday, please bring any questions you may have. Also, there is no lab on Tuesday morning.
Oct. 7 Today, we looked at Section 2.2 on set operations. You should know how to take the intersection, union, and complement of sets. As well, you should be able to show that two sets are equal using membership tables.
Oct. 5 We started Chapter 2 with a discussion of sets. You should know some of the special terms associated to sets -- null set, subset, and some of the constructions -- power set and cartesian products.
Oct. 2 We finished Chapter 1 today by talking about the remaining material of Section 1.7. I talked about how to make a proof, and some famous conjectures. I handed back HWA 1, collected HWA 2, and assigned HWA 3.
Sept. 30 We started Section 1.7 on proof methods and strategies. In particular, we talked about proof by cases, exhaustive proofs, and existence proofs. I gave examples of each.
Sept. 28 Today we looked at Section 1.6 where I introduced various types of proofs: direct proofs, indirect proofs, proofs by contradiction, and proofs with biconditionals. I gave examples of each.
Sept. 25 We finished Section 1.5 by looking at the rules of inference involving quantifiers. I also started talking about Section 1.6. The first HWA was due, and the second HWA was assigned.
Sept. 23 We looked at the first half of Section 1.5 on the rules of inference. You should memorize the eight rules discussed in class, know what a fallacy is, and how to do problems like those discussed in class.
Sept. 21 We continued our look at quantifies by going over the material of Section 1.4. We talked about nested quantifies, and how to translate statements with many quantifiers.
Sept. 18 We looked at Section 1.3 on the universal and existential quantifiers. I also assigned the first homework assignment, and I gave out the first challenge assignment.
Sept. 16 We finished Section 1.1 by discussing the problem of translating sentences into compound propositions, and back again. We also learned how to construct truth tables for compound propositions, and terms like tautology and contradiction, and how to determine if two propositions are equivalent.
Sept. 14 I went over the material of Section 1.1. You should know the names of all the logical operators and their truth tables.
Sept. 11 Welcome to the first day of class! I went over the course handout and we did some simple problems in logic to get warmed up for the semester.
Sept. 4 More details were added to the webpage, including the first homework assignment.
Aug. 20 I added the course outline to the web page, and updated some of the information.
July 17 Not much to see yet! Just getting the web page ready. Come back in about a month for more! Nothing on this page is set in stone yet -- wait until I'll make the course handout. In the meantime, you can watch a short video about MATHS to get you ready for the course. Perhaps you can help the school win the computer toaster system!

Course Information

Instructor: Adam Van Tuyl

Office: RB 2015
Office Hours: MWF 10:00-11:00
Email: avantuyl AT lakeheadu.ca

Place and Time:

Class: MWF 8:30-9:30 in RC 1001
Lab: T 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 25)

Sec. 1.1 -- 6eh, 10ad, 24a, 28d,32c
Sec. 1.2 -- 8d, 14, 20, 30, 46, 47
Sec. 1.3 -- 6be, 8, 12ef, 14ac, 24ab, 34bc

Assignment 2 (Due: Oct 2)

Sec. 1.4 -- 6cf, 10bh, 14cf, 24cd, 30ab
Sec. 1.5 -- 4de, 10af, 14ad, 20, 24

Assignment 3 (Due: Oct 9)

Sec. 1.6 -- 2, 6, 18, 26, 34
Sec. 1.7 -- 6, 12, 20, 28, 38c

Assignment 4 (Due: Oct 23)

Sec. 2.1 -- 4, 8aceg, 16, 19b, 24, 34c
Sec. 2.2 -- 14, 18d, 24, 30ab, 32,36
Sec. 2.3 -- 4ab, 8ah, 16, 32, 44

Assignment 5 (Due: ~~Oct 30~~ Nov. 2)

Sec. 2.4 -- 4ab, 6dg, 10be, 16b, 18a, 20, 32a
Sec. 3.1 -- 6, 8, 12, 16, 52a, 56

Assignment 6 (Due: Nov 6)

Sec. 3.2 -- 2ace, 6, 12, 16, 18
Sec. 3.3 -- 2, 4, 8, 12a

Assignment 7 (Due: Nov 13)

Sec. 3.4 -- 6, 8, 10ah, 16, 18, 22
Sec. 3.5 -- 4ef, 10, 14a, 17b, 18, 20ad, 22ad
Sec. 3.6 -- 24ace, 26
Sec. 3.7 -- 6, 12, 28a

Assignment 8 (Due: Nov 27)

Sec. 4.1 -- 4, 6, 20, 32
Sec. 4.2 -- 4, 14, 26a
Sec. 4.3 -- 2ad, 8bc, 24ab, 50
Sec. 4.4 -- 8

Assignment 9 (Due: Dec. 3) (Note: This is a Thursday!)

Sec. 5.1 -- 6, 12, 20abcd, 32cd
Sec. 5.2 -- 4, 6, 16, 24, 30
Sec. 5.3 -- 6ef, 12, 22def, 32

Assignment 10 (Due: Jan. 15)

Sec. 5.4 -- 8, 12, 24
Sec. 5.5 -- 10ad, 16d, 20, 32, 40
Sec. 6.1 -- 6, 10, 18, 32
Sec. 6.2 -- 10ace, 12, 24
Sec. 6.3 -- 8, 20

Assignment 11 (Due: Jan. 22) (Note: Place under my office door by noon since no class Friday)

Sec. 7.1 -- 2ae, 4c, 6ab, 14, 18, 28
Sec. 7.2 -- 2bdf, 4bdf, 8

Assignment 12 (Due: Feb. 5)

Sec. 7.4 -- 4df, 8cd, 22, 24a
Sec. 7.5 -- 6, 10, 16
Sec. 7.6 -- 2, 10
Sec. 3.8 -- 2a, 4c, 28, 30
Sec. 8.1 -- 4, 10, 17, 24, 30, 54a
Sec. 8.2 -- 2, 14

Assignment 13 (Due: Feb. 12) (Note: Place under my office door by noon since no class Friday)

Sec. 8.3 -- 4c, 8 (do only 4a), 10a, 14abc, 30
Sec. 8.4 -- 4, 8, 16b, 20, 26b (use Theorem 3)
Sec. 8.5 -- 2bc, 12, 22, 42bc, 46ad

Assignment 14 (Due: Feb. 26)

Sec. 8.6 -- 4, 8c, 10, 14, 16ab, 34ab
Sec. 9.1 -- 2, 16, 18, 22
Sec. 9.2 -- 2, 8, 12, 18, 19

Assignment 15 (Due: March 5)

Sec. 9.2 -- 20abc, 22, 26ab, 32, 36ac
Sec. 9.3 -- 8, 12, 20, 30, 36, 40, 54ab
Sec. 9.4 -- 2, 6, 10, 20, 30 54abcd

Assignment 16 (Due: March 19)

Sec. 9.5 -- 2, 10, 20, 26, 32, 36
Sec. 9.6 -- 2, 4, 8d, 14, 18, 20
Sec. 9.7 -- 6, 8, 12, 14, 15, 24
Sec. 9.8 -- 6, 10, 16, 28, 30

Assignment 17 (Due: March 26) (Note: Place under my office door by noon since no class Friday)

Sec. 10.1 -- 4, 8, 12a, 22, 24
Sec. 10.2 -- 2, 4
Sec. 10.4 -- 4, 10, 14, 16 (do 14 only), 20, 24
Sec. 10.5 -- 4, 8, 12, 14

Assignment 18 (Due: April 6) (Note: Place under my office door by noon on TUESDAY!)

Sec. 11.1 -- 6d, 8 (do 6d only), 20, 24, 28
Sec. 11.2 -- 4d, 8, 12a, 15c
Sec. 11.3 -- 4, 6bc, 8
Sec. 11.4 -- 4ab, 6, 12c

Handouts

All class handouts are available as PDF files.

Course Information
Handout for first day

Midterm 1 Information
Handout for first midterm

Midterm 2 Information
Handout for second midterm

Midterm 3 Information
Handout for third midterm

Midterm 4 Information
Handout for fourth midterm

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 Assignment 1
Due: Sept. 25, 2009

Challenge Assignment 2
Due: ~~Nov. 6, 2009~~ Nov 13, 2009

Challenge Assignment 3
Due: Feb. 5, 2010

Challenge Assignment 4
Due: March 19, 2010