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

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 algorithms. 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).

News (Last Updated Dec. 16, 2011)

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

PostExam Information

Here are the unofficial results from the class. I will formally submit the marks on Monday.

Unofficial Marks

Please see me ASAP if you notice any problems.

PreExam Information

To help you study, the following material may be useful.

Final Exam Review Sheet
Pre-exam Marks Find your mark before the exam. Please note that I have not included the challenge assignments. As well, I have used the weighting of 25% for each midterm. If you see any mistakes, please let me know as soon as possible. (I apologize for the quality of the page -- some extra characters seems to have been added.)
Old Math 1281 Exam This is the exam from last year's course. Please note that it will be very different from this year's course. We covered different material in the course last year. However, it may still prove useful for studying. I have put the solutions on reserve on ERES and in the library.

Dec 5 Our last day of class! I did a review for the final exam. A reminder that your HWA 9 is due at 5PM today.
Dec 2 We finished Chapter 9 by looking at Section 9.5 on RSA cyrptography. Here's a video with the inventors of RSA cryptography describing the algorithm. HWA 8 was due in class.
Nov 30 In today's class we looked at Sections 9.3 and 9.4 on cryptography. Here's a video on the Caesar Cipher. Please note: I assigned HWA 9 today and it is due on Monday at 5PM.
Nov 28 The review sheet for the final exam was added to the webpage.
Nov 28 We looked at Section 9.2 on modular arithemetic and the Chinese Remainder Theorem. Here's a video on the Chinese Remainder Theorem.
Nov 25 We started Chapter 9 today (we won't be doing Chapter 9). You should know what a prime number is, the Division Algorithm, and the Euclidean Algorithm. I assigned HWA 8 and also collected HWA 7 and the Challenge Problem 2. Here's today's video
Nov 23 We finished Chapter 7 today by looking at Hamilton circuits (Section 7.67) and the Traveling Salesman Problem (Section 7.7). Here's a video describing the nearest neighbour algorithm.
Nov 21 In today's class we went over Section 7.5 on trees. You should know how to find the minimal spanning tree of a graph. I also handed back Midterm II.
Nov 18 Midterm II
Nov 16 We finished up Section 7.3 on walks, paths, and cycles, and then I explained Dijkstra's Algorithm for finding the shortest path in a weighted graph (see Section 7.4). I also handed back HWA 6 and assigned HWA 7. And here's today video from Nu3bers.
Nov 14 Today we looked at Section 7.2 on Euler curcuits and walks. Here's a video on the Konigsberg Bridge Problem.
Nov 11 Class cancelled.
Nov 9 We started Chapter 7. We looked at the material on Section 7.1, an introduction to graphs. HWA 5 was also handed back. Since we are studying graphs, you can now answer the Good Will Hunting Math Problem.
Nov 7 We finished Chapter 6 today by looking at Section 6.5 on Bayes Theorem. The following video is indirectly related to Bayes Theorem; it explains the famous Monty Hall Problem. This video doesn't explain Bayes Theorem very well, but it has Mario and Luigi!
Nov 4 In class we looked at Sections 6.3 and 6.4 (we are skipping Section 6.2). You HWA 5 was due in class today.
Nov 2 We began Chapter 6 today, which focuses on probability. We went over some of the basic definitions, and we looked at the Birthday problem which is found in Section 6.2. I also handed back HWA 4. There are A LOT of videos on probability. Here is the first video in a series of videos on probability.
Oct 31 In today's class we finished up a number of topics from Chapter 5: Pascal's triangle from Section 5.5, the binomial theorem from Section 5.6, and the formula for Derangements from Section 5.7. This video is interesting because it gives you a mechinical way of computing binomial coefficients (the sound cuts out, but the the number of marbles at the end in each bin is a binomial coefficient).
Oct 28 We looked at Section 5.5 on selections and combinations. HWA 4 was collected and HWA 5 was assigned.
Oct 26 Today's topic was arrangements. See Section 5.4 for more. Here's a video on permutations. In fact, it is the start of a whole series of videos on the topic.
Oct 24 We looked at Section 5.3 on one-to-one correspondences and the cardinality of infinite sets. You should know the difference between a countable and uncountable set. And here is a dinosaur comic about Hilbert's Hotel.
Oct 21 We started Chapter 5 on counting. We covered Section 5.1. Here's today's video.
Oct 19 Today I finished up Section 4.3 by discussing the connection between functions and relations. I also talked about the Kevin Bacon Number (see The Oracle of Bacon). I also handed back the midterm.
Oct 17 We first finished up Section 4.2 by quickly discussing partial orders. I then talked about functions. You should know what a function is, and terms such as one-to-one, onto, bijection, and inverse.
Oct 14 Midterm I was today.
Oct 12 We focused on Section 4.2 today. We learned about equivalence relations and partial orders. Here's today video on equivalence relations. Note I will have another office hour tomorrow (Thursday) from 1 to 2:30 since we did not have a lab this week. Also, I will not be at the midterm on Friday; someone else will be supervising the midterm so don't be surprised if you don't see me.
Oct 7 Today was our first class on relations. You should know the definition of a relation, and terms like reflexive, symmetric, transitive, and antisymmetric. You HWA for the week is to study.
Oct 5 We finished Chapter 3 by going over Section 3.4 on digitial circuits. Please note that the midterm next week will go up to today's lecture. Here's today's video: it shows how to build logic gates using dominoes.
Oct 3 In Monday's class we examined how one can use a Karnough Map (see Section 3.3) to simplify a Boolean expression written in disjunctive form. I also handed out a review sheet for the first midterm. Here's a video, but be aware that it is slightly different than how I explained it in class (it is equivalent, however).
Sept 30 In today's class, we looked at Section 3.1 on Boolean forms. We looked at literals, fundamental products, and disjunctive forms. I assigned HWA 3 and collected HWA 2.
Sept 28 We began our discussion of Chapter 3 by looking at the definition of a Boolean algebra. I also handed back HWA 1. Here's a video on Boolean algebras.
Sept 26 We finished our look at induction (Section 2.5).
Sept 23 Today we looked at Section 2.5 on induction. We will conclude our discussion on induction on Monday. HWA 1 was due in class, and HWA 2 was given out. Here's a good video on induction.
Sept 21 We looked at how to use a membership table and a Venn diagram to prove some set identities. We also consider some other set operations like the cartesian product and symmetric difference. This material is Sections 2.3 and 2.4. Need more help: check out Mr. Venn
Sept 19 Section 2.2 on sets and set operations were the focus of today's class. You should know the various operations: union, intersection, complement, and constructions like the power set. Here's a video on set operations; but be careful -- there is a mistake!! Can you find it?
Sept 16 In today's class we talked about propostions and logic. Here's a video on today's topic. I also gave out the first HWA.

LAB UPDATE: According to our poll, Monday at 9:30 was the best time for the lab. So, we will meet on Monday's from 9:30-10:30 in BB 1075. I still need to get the schedule updated, but we will start on Monday. I have changed my office hours as well.
Sept 14 In today's class we went over summation notation and writing numbers in different bases (Sections 1.3-1.4 of the textbook). Here's a video about number bases.
Sept 12 Today was the first day of class. I went over the course outline, and talked about sets, prime numbers, and functions like the floor and ceiling. Here's a video about the sets of numbers
Sept 5 HWA 1 added to the web.
August 15 I added the course handout to the webpage (see to the right).
August 3 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.

Course Information

Instructor: Adam Van Tuyl

Office: RB 2015
Office Hours: M: 2:30-3:30 WF: 9:30-10:30
Email: avantuyl AT lakeheadu.ca

Place and Time:

Class: MWF 8:30-9:30 in BB 1075
Lab: M 9:30-8:30 in BB 1075

Textbook:

A Beginner's Guide to Discrete Mathematics
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 23)

Sec. 1.1 -- 4, 14, 22, 30, 44
Sec. 1.2 -- 12, 14, 16
Sec. 1.3 -- 4, 16, 52, 70
Sec. 1.4 -- 2(iii), 12, 30, 44

Assignment 2 (Due: Sept 30)

Sec. 2.1 -- 8, 15, 22,38
Sec. 2.2 -- 7, 11, 19, 28, 36
Sec. 2.3 -- 8, 13, 20, 26
Sec. 2.4 -- 8, 12, 16

Assignment 3 (Due: Oct 7)

Sec. 2.5 -- 3, 10, 15, 26i
Sec. 3.1 -- 6, 16, 18, 23 (use boolean algebra B = {0,1} for problems)
Sec. 3.2 -- 4, 24, 28, 36
Sec. 3.3 -- 8, 14, 20, 24

Assignment 4 (Due: Oct 28)

Sec. 4.1 -- 1, 8, 22, 35
Sec. 4.2 -- 4, 7, 9, 17 (2nd part of 17ii is a bonus)
Sec. 4.3 -- 6, 12, 13, 14, 20
Sec. 5.1 -- 2, 4

Assignment 5 (Due: Nov 4)

Sec. 5.1 -- 10, 17
Sec. 5.2 -- 4, 6
Sec. 5.3 -- 2, 3, 9i,ii, 13
Sec. 5.4 -- 2, 14, 20, 30
Sec. 5.5 -- 10, 16, 22, 29

Assignment 6 (Due: Nov 11)

Sec. 5.6 -- 2, 6, 12
Sec. 5.7 -- 2, 4 (first part), 10
Sec. 6.1 -- 8, 18, 20, 28
Sec. 6.3 -- 4, 12
Sec. 6.4 -- 6, 16, 22, 44

Assignment 7 (Due: Nov 25)

Sec. 7.1 -- 16i, 20, 22, 24 Bonus: 33
Sec. 7.2 -- 3, 11, 18, 23
Sec. 7.3 -- 1, 4, 10, 17
Sec. 7.4 -- 3, 17

Assignment 8 (Due: Dec 2)

Sec. 7.5 -- 2, 12, 18, 20 (use Prim's method only for 18,20)
Sec. 7.6 -- 3, 8, 9
Sec. 7.7 -- 2, 10 (use nearest neighbour method only)
Sec. 9.1 -- 2, 12, 16, 20

Assignment 9 (Due: Dec 5) NOTE: Due at 5PM on SPECIAL DAY!!!!!

Sec. 9.2 -- 18, 44, 64
Sec. 9.3 -- 4, 26
Sec. 9.4 -- 2, 24
Sec. 9.5 -- 4, 16

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 21, 2011

Challenge 2 Assignment
Due: Nov 23, 2011