Math 1271/3071 -- Discrete Mathematics
(Fall 2012)

In Discrete Mathematics (Math 1271/3071) we cover a variety of topics, including basic set theory, graphs, logic and proofs, number structures, basic combinatorics, and cryptography. This is a one semester course that also includes a lab once a week. Engineers should enroll in Math 3071 (Discrete Mathematics for Engineers); all other students should enroll in Math 1271 (Discrete Mathematics).

Final Exam

The final exam is going to be on December 6. To practice, you can download the

2011 Final Exam I will put the solutions on reserve.

News (Last Updated Nov. 30, 2012)

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

Nov. 30 Today is our last class. We did some review for the final, plus the course evaluations.
Nov. 28 In today's class we looked at RSA cryptography.
Nov. 26 In class we looked at the basics of cryptography. In particular, we looked at Sections 9.3 and 9.4 which described some of the primitive ways in which one can encode a message.
Nov. 23 Today we looked at Section 9.2 on modular arithmetic and the Chinese Remainder Theorem. I also assigned HWA 9, and HWA 8 was collected.
Nov. 21 We started looking at Chapter 9 on cryptography and elementary number theory. I also handed back Midterm II.
Nov. 19 Class and lab cancelled.
Nov. 16 Midterm II.
Nov. 14 I will have an extra office hour on Thursday from 3:00 to 4:00PM. Also, there is no class on Monday, Nov. 19.
Nov. 14 Today's topic was Hamilton Cycles and the Travelling Salesman Problem (see Sections 7.6 and 7.7). Just a reminder that the midterm is on Friday! I also handed back HWA 7.
Nov. 12 In class we looked at the family of graphs called trees. We talked about some of their basic properties, defined a spanning a tree, and went over Prim's algorithm to find the spanning tree of smallest weight in a weighted graph.
Nov. 9 Today we looked at the problem of finding the shortest path in a weighted graph. See Sections 7.3 and 7.4. I also handed back HWA 6 and collected HWA 7.
Nov. 7 We looked at Euler circuits and walks, and we applied these ideas to the Konigsberg Bridge Problem (see Section 7.2). I also started to look at Section 7.3.
Nov. 5 In today's class, we started Chapter 7 on Graph Theory. Here's a video
Nov. 2 We finished our look at Chapter 6 by covering Bayes Theorem (Section 6.5). I assigned HWA 7, collected HWA 6 and returned HWA 5.
Oct. 31 Today we covered two sections: Sections 6.3 and 6.4. In particular, we used the counting techniques from Chapter 5 to calculate some probabilities, and I introduced the notion of conditional probability.
Oct. 29 We began our discussion of probability. Today, we looked at Section 6.1. Here's a video to help you.
Oct. 26 We finished our look at counting by doing Section 5.7. You should know what a derangement is, and know how to use the Pigeonhole Principle. I assigned HWA 6, and collected HWA 5.
Oct. 24 We looked at binomial coefficients (Section 5.6). I also handed back the first challenge assignment.
Oct. 22 In today's class we looked at Section 5.5 on combinations and how to count them. I introduced the binomial coefficient and Pascal's triangle. Here's a video related to today's material, and here is Pascatz Triangle
Oct. 19 Because I was out of town, Dr. Biermann gave today's lecture. She talked about counting the number of permutations of a set. HWA 4 was due, and HWA 5 was collected, as well as the challenge assignment.
Oct. 17 We started Chapter 5 on counting and counting techniques. In particular, we looked at Section 5.1.
Oct. 15 In today's class we reviewed some of the concepts of Chapter 4. I also talked about the Oracle of Bacon and the Erdos Number. Midterm 1 was returned.
Oct. 12 Midterm 1 was this morning. They will be graded and returned by Monday's class.
Oct. 10 Welcome back from the holiday! Today we will continue our discussion of Chapter 4 by looking at Section 4.3. Here's a video on one-to-one and onto functions. I also assigned the next homework assignment (due next week Friday).
Oct. 5 We went over Section 4.2 which discussed two special types of relations: equivalence relations and partial orders. I handed back HWA 2, and collected HWA 3. Your homework for next week is to study for the midterm. Here's a video to help you with equivalence relations.
Oct. 3 We started Chapter 4 with a discussion of binary relations.
Oct. 1 We finished Chapter 3 with a discussion of Section 3.4 on digital circuits. We also described how to carry out binary addition. If you want to plan with more complicated digital circuits, you can check out this website (thanks to Andrew M. for the link).
Sept. 28 We looked at Section 3.3 on Karnough maps. After today's class, you should know how to use these diagrams to simplify boolean expressions. I returned HWA 1, I collected HWA 2, and assigned HWA 3.
Sept. 26 Today we looked at Section 3.2 on representing Boolean functions.
Sept. 24 Added the review sheet for the first midterm.
Sept. 24 Today we started Chapter 3 which looks at Boolean algebra. Although the book considers more general Boolean algebras, we will focus on the the two element Boolean algebra. Here's a short video. And here's an old video (but good) from TVOntario.
Sept. 21 We finished Section 2.5 by talking about more examples of induction. We also talked about this comic. HWA 1 was collected and HWA 2 was assigned.
Sept. 19 We did the first of two lectures on mathematical induction. See Section 2.5 for more details. Here is a nice video that works out an example.
Sept. 17 Today we did two sections: Seciton 2.3 and 2.4. Section 2.3 discusses how to prove two sets are equal, and Section 2.4 introduces two additional set operations.
Sept. 14 We looked at Section 2.2 on elementary set theory. I also assigned the first homework assignment. Here's a simple video (there is a mistake in the video -- can you find it?)
Sept. 12 In today's class we looked at propositions and the basic logical operators. See Section 2.1 for more details.
Sept. 10 First day of classes! I went over the course outline, and I did a quick review of the material of Sections 1.1-1.3. You should have seen must of this material before. If you are a little rusty on changing bases of numbers, here's a video
Sept. 9 Office hours added to the webpage.
Sept. 6 Added the first two Homework Assignments to the webpage and first challenge assignment.
August 14 Course outline added to website and some dates added.
August 8 Not much to see yet. Just starting to put together the web page. If you are looking for something math related to watch, check out this video.

Text Book Information

We will be using the following textbook in this course:

A Beginner's Guide to Discrete Mathematics (Second Edition)
by W.D. Wallis

Please note that we are using the second edition. It is important that you have this version; not only will I use it for homework assignments, but there are number of typos from the first edition that have been corrected.

You can obtain this textbook in at least four ways:

Purchase from the internet at a website like Amazon.
Purchase a copy from Lakehead's Bookstore.
Dowload a FREE electronic copy via Lakehead's Libary Web Page. Here's how to do this:
1. Go to Lakehead Library
2. On the search tab, click on "LIBRARY CATALOUGE"
3. Type in the title of the book: "A Beginner's Guide to Discrete Mathematics"
4. The second item that shows up is the electronic resource. Click on it. Click on the link to "Access SpringerLink e-book (Springer)"
5. If you are off-campus, you will be taken to a log-in screen. Use your Lakehead email login and password on this page to continue. If you are on-campus, you can skip this step.
6. The page that you are taken to will contain all the chapters of the book as PDF files. Unfortunately, you cannot download the whole book at once, but you have to download each chapter individually.
The following weblink will bring you to the publisher. I have not tried this link, but you should be asked for your Lakehead login and email before you get to this webpage. On this webpage, you can also download a PDF of each chapter or view the book on the website. Alternatively, you have the option of buying a print-on-demand version for $24.95US. Click on this option to get this copy.

Please let me know if you have any trouble with these directions. I will try to fix them.

Course Information

Instructor: Adam Van Tuyl

Office: Ryan Building 2015
Office Hours: T: 2:00-3:00PM and W: 9:30-10:30AM
Email: avantuyl AT lakeheadu.ca

Place and Time:

Class: MWF 8:30-9:30 in Braun Building 1075
Lab: M 9:30-8:30 in Braun Building 1075

Textbook:

A Beginner's Guide to Discrete Mathematics (Second Edition)
by W.D. Wallis

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 21)

Sec. 1.1 -- 8, 10, 12, 32, 50, 58
Sec. 1.2 -- 6, 10, 14
Sec. 1.3 -- 14, 24, 46, 62
Sec. 2.1 -- 6, 14, 24, 36
Sec. 2.2 -- 4ii,iv, 6, 26, 32, 34, 40

Assignment 2 (Due: Sept 28)

Sec. 2.3 -- 8, 12, 20, 26
Sec. 2.4 -- 2, 10, 16i
Sec. 2.5 -- 4, 10, 14, 16

Assignment 3 (Due: Oct. 5)

Sec. 3.1 -- 6, 16, 22
Sec. 3.2 -- 4, 24, 26, 30, 44
Sec. 3.3 -- 8, 12, 20, 26, 32ii
Sec. 3.4 -- 6, 8, 14, 16

Assignment 4 (Due: Oct. 19)

Sec. 4.1 -- 2, 8, 10, 22, 28, 34i, v
Sec. 4.2 -- 4, 7, 12, 17i
Sec. 4.3 -- 2, 6, 12, 14, 18 (Bonus: 20)

Assignment 5 (Due: Oct. 26)

Sec. 5.1 -- 6, 8, 10 ,14, 24
Sec. 5.2 -- 4, 10, 14, 16
Sec. 5.4 -- 8, 14, 16, 20, 28

Assignment 6 (Due: Nov. 2)

Sec. 5.5 -- 4, 14, 20, 24, 36
Sec. 5.6 -- 2, 8, 12, 15
Sec. 5.7 -- 2, 8 ,12, 14, 16

Assignment 7 (Due: Nov. 9)

Sec. 6.1 -- 6, 14, 18, 22, 30
Sec. 6.3 -- 4, 10
Sec. 6.4 -- 6, 20, 26, 28
Sec. 6.5 -- 4i, 18

Assignment 8 (Due: Nov. 23)

Sec. 7.1 -- 16ii, 18, 20, 22
Sec. 7.2 -- 6, 8, 18, 28
Sec. 7.3 -- 2, 4, 12, 16, 20
Sec. 7.4 -- 4, 16, 20, 22
Sec. 7.5 -- 18, 22 (use only Prim's Algorithm)

Assignment 9 (Due: Nov. 30)

Sec. 7.6 -- 4, 8, 9
Sec. 7.7 -- 2, 12 (use only nearest neighbour method)
Sec. 9.1 -- 2, 10, 12, 18, 24
Sec. 9.2 -- 22, 24, 26, 42, 66

Handouts

All class handouts are available as PDF files.

Course Information
Course handout from first day of class

Midterm 1 Information
Review sheet for first midterm.

Midterm 2 Information
Review sheet for second midterm.

Final Exam Information
Review sheet for 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 19, 2012

Challenge 2 Assignment
Due: Nov 23, 2011