(Adapted from the Course Calendar) Some of the topics covered
in this course are: basic set theory, graphs and algebras, introduction
to logic and proofs, number structures, basic combinatorics,
and algorithms. This is a two semester course that also includes
one lab a week.
|
Time |
Class: MWF 2:30-3:30 Lab: M 3:30-4:30 |
|
Place |
Class: RC 0005 Lab: RC 1001 |
|
Instructor |
Adam Van Tuyl |
|
|
Office: RB 2015 |
|
|
Office Hours: Tues. 1:00-2:00 Wed. 3:30-4:30
|
|
|
|
Text |
Discrete Mathematics and Its Applications, 5th Edition by K.
Rosen
|
Email |
avantuyl@sleet.lakeheadu.ca |
|
Web Page |
flash.lakeheadu.ca/~avantuyl/courses/2004_fall_math1281.html
|
|
Some links that you might find useful:
Any relevant news about the course will be posted in
this
section. Please check here for information about the course, homework
assignments, etc.
News last updated: April 15, 2005
Second Semester
- April 15, 2005 The unofficial marks for the course have now
been posted. To see them, use the link below:
Have a good summer and see you next fall in Linear Algebra! -- Adam.
- April 8, 2005 The assignments have been graded. They can be
collected outside of my office. Also, use the following link to see
Please let me know ASAP if any corrections are needed.
- April 5, 2005 We did a review today.
- April 4, 2005 Today we finished the material of Section 10.4
on Boolean Algebra. You should know how to use a Karnough map to
simplify a Boolean expression if it has two or three variables.
- April 1, 2005 We discussed the material of Section 10.3 on
logic gates. You should know what the basic logic gates are, and how to
draw simple circuits.
- March 30, 2005 The last homework assignment was given out
(Due on April 6). I also talked about finding Boolean expressions
for a given Boolean function, and what it means for a system
of Boolean operators to be functionally complete.
- March 28, 2005 The questions for the last homework assignment
have been posted to the web. Also, Start Studying! by
using the exam review
handout. A paper copy of this will be handed out next week in
class.
- March 23, 2005 Today we started Chapter 10 on Boolean
algebra. I went over the basic definitions.
- March 21, 2005 We covered Section 9.5 on finding minimal
spanning trees. I introduced two algorithms (Prim's Algorithm and
Kruskal's Algorithm) for finding the minimal spanning tree in a weighted
graph. You should know how to use either algorithm. We also did the
course evaluations, and I handed back the latest assignment.
- March 18, 2005 We skipped Section 9.3, and moved unto
Section 9.4 on spanning trees. You should know how to use the two
algorithms (Depth First vs. Breadth First) to find a spanning tree of a
graph. Also, HWA 17 was given out. Please note that the assignment
will be due on Wednesday, March 30 because of the Easter Break.
- March 16, 2005 Today we looked at Section 9.2 on
applications of trees. You should know how to make binary search trees
and how to use trees to represent possible decisions.
- March 14, 2005 We started Chapter 9 on trees. Today we went
over the basic terminology associated with trees.
- March 11, 2005 Today we finished Section 8.7 on planar
graphs, and we covered the material of Section 8.8 on graph colourings.
The new homework assignment was also posted.
- March 9, 2005 We will start Section 8.7 on planar graphs.
We will finish this section up on Friday.
- March 7, 2005 Today we will cover Section 8.6 on finding the
shortest path in a weighted graph.
- March 4, 2005 Class cancelled.
- March 2, 2005 We pick up where we left from last class in
Section 8.5. We discussed Euler circuits, Euler paths, Hamilton paths,
and Hamilton circuits.
- Feb. 28, 2005 I handed back the midterms. As well, we
finished Section 8.4 and moved on the material of Section 8.5. Since
the next homework assignment is long, I have posted it to the webpage
already (it is due March 11).
- Feb. 25, 2005 Today was the second midterm.
- Feb. 23, 2005 We covered some material of Section 8.3 on
graph isomorphisms. We also talked about connectedness.
- Feb. 21, 2005 Welcome back from Reading Break. I handed
back HWA 14 in class today. As well, I covered the material of Section
8.3 on representing graphs.
- Feb. 11, 2005 In Friday's class, we finished up Section 8.2.
The next midterm (Feb. 25) will cover all the material up to today's
class. There is no homework assignment over the break. Instead, it is
suggested you use the time to study. I also gave out a handout
describing the midterm.
- Feb. 9, 2005 In today's class we started looking at Chapter
8 on the material of graph theory. We spent some time going over the
basic definitions.
- Feb. 7, 2005 Today, we did a review of the material of
Chapter 7. We also discussed how the Kevin Bacon Number can
be defined using the language of relations. To check out the websites
we visited in class, you can use the links below:
- Feb. 4, 2005 We study the first two parts of Section 7.6 on
partial orders. You should know all the material of this section
up to and including the material on lexicographical ordering.
- Feb. 2, 2005 We looked at Section 7.5 on equivalence
relations. You should know the definition of an equivalence relation,
and how equivalence relations are related to partitions.
- Jan. 31, 2005 We covered the material of Section 7.4. After
today's lecture you should know how to find the reflexive, symmetric,
and transitive closure of a relation.
- Jan. 28, 2005 Today we did Section 7.3 on representing
relations. HWA 13 was also assigned today. See below.
- Jan. 26, 2005 We finished Section 7.1, and we also
did Section 7.2 on n-ary relations.
- Jan. 24, 2005 We started Chapter 7 today. You should
know what a relation is, on some terms associated to
relations, e.g., reflexive, symmetric, antisymmetric, and transitive.
HWA 11 was also handed back.
- Jan. 21, 2005 In today's class we went back to an earlier
section, Section 2.7, on matrices. You should know all the definitions
presented in class, and in particular, you should know what a zero-one
matrix is, and know how to perform all the related Boolean operations.
A new homework assignment was also given out.
- Jan. 19, 2005 We looked at two sections today - Section 6.5
and 6.6. Both sections were on the Principle of Inclusion-Exclusion.
- Jan. 17, 2005 We finished our discussion of Section 6.4 on
generating functions. We described how to use generating functions to
count. I also talked about the generalized binomial coefficients. HWA
10 was also handed back.
- Jan. 14, 2005 In today's class we started the first of two
lectures on Section 6.4 - Generating functions. You should know what a
generating function is, what a closed form of a generating function is,
and how to manipulate formal power series. I also gave out a new
homework assignmet (see below).
- Jan. 12, 2005 We finished Section 6.2. You should be able
to find formulas for all sequences that satisfy a linear homogeneous
recurrence relation of degree 1 and 2. You do not need to know how to
solve relations of higher degree.
- Jan. 10, 2005 We began Section 6.2 in today's class. You
should know what a linear homogeneous recurrence relation is, and how
to solve such a relation of degree 1.
- Jan. 7, 2005 In today's class we finished discussing
the material of Section 6.1. I also assigned the first homework
assignment (see below).
- Jan 5, 2005 WELCOME BACK! In class I handed back the
Christmas Exam. If you did not receive your exam, please come and see
me. As well, we started looking at Section 6.1 on recurrence relations.
We will finish this section in Friday's class.
First Semester
- Dec. 19, 2004 The Christmas Exams have been graded. To see
your mark, and your overall mark for the first semester, please use
the link below:
Christmas Exam Marks
I will hand back the exams after the Christmas Break. Have a good
holiday!
- Dec. 3, 2004 The assignments are graded. They can be
picked up in the box outside of my office. Also, you can see your marks
for the first semester using the link below:
First Semester Math 1281
Marks
- Dec. 2, 2004 We had a second day of review. The homework
assignments were also due.
- Dec. 1, 2004 We reviewed.
- Nov. 29, 2004 We finished Section 5.2. You should now
know about Bernoulli Trials and Random Variables.
- Nov. 26, 2004 Today we talked some more about probability
theory (Section 5.2). You should know about assigning probabilities,
combinations of events, conditional probability, and independent events.
A new homework assignment was also given out.
- Nov. 25, 2004 The Christmas Exam will be on Dec. 16, 2004.
I have posted a study sheet for the exam to the webpage. (See the
bottom of this page).
- Nov. 24, 2004 I introduced the idea of discrete probability.
You should know the material of Section 5.1.
- Nov. 22, 2004 In this class we covered the rest of section
4.5 (on the number of permutations that can be made from a set
with indistinguishable objects). As well, we briefly looked at Section
4.6. You should know how to find the next largest permutation in
lexicographical order. The last homework assignment was handed back.
- Nov. 19, 2004 We continued our discussion on Section 4.5.
We looked at counting the number of integer solutions to equations.
The new homework assignment was also given out.
- Nov. 17, 2004 We started are examination of Section 4.5 on
generalized permutations and combinations.
- Nov. 15, 2004 Today we looked at binomial coefficients and
Pascal's Triangle. Homework assignment 6 was also handed back.
- Nov. 12, 2004 We begin our discussion of Permutations
and Combinations (see Section 4.3). The new homework assignment was
also given out.
- Nov. 10, 2004 Today we discussed the pigeonhole principle
(see Section 4.2). You should know how to use the generalized
pigeonhole prinicple.
MIDTERM CORRECTION: It has come to my attention that
Exercise 2ii on the midterm has another equivalent answer. If you
got the question wrong, please let me see it so I can determine whether
your answer is correct or not.
- Nov. 7, 2004 Today's class looked at Chapter 4.1 on
counting techniques.
- Nov. 5, 2004 We finished Chapter 3 today. We looked at
Section 3.4 on recursive functions, sequences, and sets. We also
looked at the Section in 3.5 on recursive algorithms. The
new homework assignment was also given out.
- Nov. 3, 2004 I handed back the midterms (please see me to
get your midterm if you were not in class). The solutions are on
reserve at the library. We also spent today going over some more
induction proofs.
- Nov. 1, 2004 I gave the first of two lectures on Section
3.3 - Mathematical Induction.
- Oct. 29, 2004 Midterm I was held today.
- Oct. 27, 2004 We covered the material of Section 3.2 today,
on sequences and summations. If you want to know about sequences
check out
The On-line Encyclopedia of Integer Sequences
- Oct. 25, 2004 Today's class was a discussion of the material
in Section 3.1 on methods of proof and conjectures. Some things you
should know by the end of class: forward and backward reasoning, what
a conjecture is, and what a counterexample is. You don't need to know
about the Halting Problem.
- Oct. 22, 2004 In today's class we talked some more about
congruences. I also handed out a study sheet for the first midterm.
There is no homework assignment this week because I want you to
spend your time studying.
- Oct. 20, 2004 Today I intoduced the notion of congruence.
As well, I explained the Division Algorithm. You should be able to
do problems like the ones we discussed in class today. (We finished
Section 2.4, and covered only part of Section 2.5).
- Oct. 18, 2004 We looked at the properties of integers today
(Section 2.4). Specifically, we looked at four topics: division, prime
numbers, the division algorithm, and GCDs and LCMs. As well, I gave out
a new homework assignment. Please note that it is due by this Friday.
- Oct. 15, 2004 Class cancelled for today. Have a good
weekend!
- Oct. 13, 2004 We looked at the material on time complexity
in Section 2.3.
NOTE: There will be no class on Friday, Oct. 15, 2004. Your
homework assignment will be due on Monday, Oct. 18.
- Oct. 8, 2004 Today we studied the material on complexity
in Section 2.2. I also gave out the new homework assignment.
- Oct. 6, 2004 In today's class we looked at Section 2.1.
You should become comfortable reading algorithms written in pseudocode.
As well, you should become familiar with the algorithms we discussed in
class.
- Oct. 4, 2004 Today we looked at some of the basic
terminology of functions, and I gave a large number of examples.
You should know what a one-to-one function, onto function, and bijection
are. (Section 1.8) Assignmet 2 was handed back.
Correction: In class on Friday, when I wrote down
the assignment, I meant to assign 26 of Section 1.7, not 36. So,
please do Section 1.7 number 26.
- Oct. 1, 2004 Today we finished looking at sets (Section
1.7), and we started looking at functions (Section 1.8). I also
gave out the new homework assignment.
- Sept. 29, 2004 In today's class I introduce the notion
of a set, and some basic definitions and properties associated to a set.
You will be responsible for all the material of this section.
- Sept. 27, 2004 We spent our last day looking at Section
1.5. You should make yourself comfortable reading proofs.
- Sept. 24, 2004 We continued our look at Section 1.5. You
should now know the rules of inference for statements involving
quantifieres. As well, we started looking at methods of proof.
The new homework assignment was given out.
- Sept. 22, 2004 Today I gave the first of three lectures
on Section 1.5. You should know what all the rules of inference are,
and how to do problems like those given in class.
- Sept. 20, 2004 In today's class we went over the material
of Section 1.4. You should become comfortable with translating
setences involving many quantifiers. Plus, you should know how to take
the negations of such objects.
- Sept. 17, 2004 I introduce Predicates and Quantifiers
today. You should know what a propositional function is, you
should know what the two quantifiers are (universal and existentaial),
and how to take the negation of quantifiers. The first HWA was
also given out (see below).
- Sept. 15, 2004 To wrap up the material on Section 1.1,
I covered precedence of logical operators, and the idea
of translating sentences in to statements with logical operators
and back again. We covered all the material of Section 1.2. You
should be able to verify two compound propositions are logically
equivalent through the use of truth tables.
- Sept. 13, 2004 In today's class we went over Section 1.1.
You should know what a proposition is, and know all the logical
operators and their truth tables.
- Sept. 10, 2004 The first day of class. I went over the
course handout (you can find a PDF copy at the bottom of the page).
- Sept. 2, 2004 This web page was made.
Homework Assignments and Solutions |
Note. If
you wish to hand in an assignment early, please put it under my
door.
Thanks! A.
First Semester
- Assignment 1 (Due: Sept. 24)
- Section 1.1 -- 2ace, 6ace, 8e, 10def, 18ace, 24ef, 26ef, 28ef
- Section 1.2 -- 6, 8b, 14, 30, 34
- Section 1.3 -- 2, 8, 10abcd, 16, 22ab
- Assignment 2 (Due: Oct 1)
- Section 1.3 -- 30abc, 34
- Section 1.4 -- 4, 6def, 10abc, 12def, 14ab, 28abc, 30ab
- Section 1.5 -- 2abc, 4 (Hint: use DeMorgan's Law), 8af, 10ad
- Assignment 3 (Due: Oct 8)
- Section 1.5 -- 12, 16, 20a, 22b, 24
- Section 1.6 -- 4, 8, 14, 15b, 24ad, 28
- Section 1.7 -- 2, 4, 10, 12e, 14e, 18, 22, 24, 26, 37
- Assignment 4 (Due: Mon, Oct 18) Note the change of date
- Section 1.8 -- 2, 4ab, 8adg, 10, 11, 16, 22ac, 28, 40
- Section 2.1 -- (Read 125-127 on Sorting) 3, 4, 6, 16, 34, 52
- Section 2.2 -- 2abd, 6, 10
- Assignment 5 (Due: Oct 22)
- Section 2.3 -- 2, 7, 8
- Section 2.4 -- 6, 10cdef, 16, 20a, 25ac, 28cdef, 30 (apply
to 28cdef only), 40
- Assignment 6 (Due: Nov 12)
- Section 3.2 -- 4ac, 6adeg, 8, 14bd, 16bd, 18bd, 19, 20
- Section 3.3 -- 4, 10, 18, 20
- Section 3.4 -- 2ad, 8ad, 12, 24ab
- Section 3.5 -- 2
- Assignment 7 (Due: Nov 19)
- Section 4.1 -- 6, 12, 16, 22, 28abgh, 32, 37
- Section 4.2 -- 4, 6, 9, 14, 16, 30
- Section 4.3 -- 4b, 8, 12, 16, 28, 30
- Assignment 8 (Due: Nov 26)
- Section 4.4 -- 4, 8, 12, 21b, 24, 32
- Section 4.5 -- 4, 10, 20
- Assignment 9 (Due: Dec 2) Note the Date!
- Section 4.5 -- 16, 18 26, 30, 40
- Section 4.6 -- 2, 4
- Section 5.1 -- 4, 6, 8, 12, 16, 18, 26ab, 36
- Section 5.2 -- 6, 10bc, 12, 24, 26
Second Semester
- Assignment 10 (Due: Jan 14)
- Section 6.1 -- 2ace, 4ad, 6ace, 8ace, 12, 20
- Assignment 11 (Due: Jan 21)
- Section 6.2 -- 2, 4defg, 8, 38
- Section 6.4 -- 4bdfh, 6bd, 8acd, 12ab
- Assignment 12 (Due: Jan 28)
- Section 6.4 -- 14, 18 (Just the generating functions for 14,18),
22, 46ab
- Section 6.5 -- 4, 6, 12, 16, 23
- Section 6.6 -- 2, 6, 10
- Section 2.7 -- 2a, 4a, 10, 15, 28, 30
- Assignment 13 (Due: Feb 4)
- Section 7.1 -- 4, 6ef, 10, 13, 22, 24, 28, 30, 31, 32bce, 54a
- Section 7.2 -- 2, 10, 12, 14, 16
- Section 7.3 -- 2cd, 4b, 8 (apply to 4a only), 10a, 12, 14abc
- Assignment 14 (Due: Feb 11)
- Section 7.4 -- 2, 10, 19, 20, 26ab (use Theorem 3 as in class)
- Section 7.5 -- 2ae, 8, 12, 18, 26, 32, 42a
- Section 7.6 -- 2, 8, 9, 10ab, 22
- Assignmet 15 (Due: March 11)
- Section 8.3 -- 8, 12, 18, 26, 28, 34, 36, 42, 48
- Section 8.4 -- 2, 6, 10, 18a, 24, 26
- Section 8.5 -- 2, 4, 10, 20, 26abc, 32, 36, 37, 42, 44abc
- Section 8.6 -- 2, 6, 12ad, 18, 28
- Assignment 16 (Due: March 18)
- Section 8.7 -- 6, 8, 12, 14, 16, 20, 22, 26, 27a
- Section 8.8 -- 4, 8 ,12, 13, 15, 16, 22c, 24, 26
- Assignment 17 (Due: March 30 Note the change of date)
- Section 9.1 -- 2, 4, 8, 16, 20, 24
- Section 9.2 -- 2, 4, 6, 14, 38ac
- Section 9.4 -- 2, 4, 6, 14, 16(apply to 14 only), 17a, 18(apply
to 17a only), 20, 24, 25
- Assignment 18 (Due: April 6)
- Section 9.5 -- 2, 3, 6, 7, 10, 11, 12, 13, 14
- Section 10.1 -- 2, 4ab, 12, 18, 26
- Section 10.2 -- 2ab, 4cd, 12ab, 13bd, 15, 16
- Section 10.3 -- 2, 4, 6, 8
The final grade is made up of three components.
- Homework (10%) A homework assignment will be given out
every Friday. It will be due the following Friday at the end of
class. There will be 9 homework assignments per semester.
The homework assignment with the lowest grade will not be counted.
Note: Homework must always be stapled together.
Also, it must be legible enough so that it be read. Failure to do
this will result in 5 points deducted from the assignment.
Homework will have 5 points deducted for every day
(the weekend is counted as one day) that it is late.
Homework can be handed in early by either giving it to me
or by placing it under my office door.
- Tests (2 Midterms, 15% each)
There will be two midterms. The dates of the midterms
are (provisionally):
- October 29, 2004 - Midterm 1
- Feb. 25,2005 - Midterm 2
- Exams (Mid-year exam 20%, Final Exam 40%)
There will a mid-year exam in December that will be cumulative, and
a final exam in April, that will also be cumulative. The exact dates
will be given later.
- Sept. 9, 2004 - First semester classes begin
- Oct. 11, 2004 - Thanksgiving (no classes)
- Dec. 1, 2004 - First semester classes end
- Jan 4, 2005 - Second semester classes begin
- Feb. 8, 2005 - Last date for course withdrawal without academic
penalty
- Feb. 14-18, 2005 - Reading Week (no classes)
- April 4, 2005 - Second semester classes end
Any course handouts will also be posted to the web.
They will be posted as PDF documents, so make sure you
have Adobe Acroreader installed.
Adam Van Tuyl
URL:
http://flash.lakeheadu.ca/~avantuyl/coures/2004_fall_math1281.html
avantuyl@sleet.lakeheadu.ca