|
EECS-1019C
Discrete Mathematics for Computer Science
York University
Fall 2015
|
Class Homepage
|
|
|
Instructor:
|
Parke Godfrey
|
Office:
|
#2050 LAS
|
Office Hours:
|
We 3–5pm
|
& by appointment / availability
|
Ph#:
|
416-736-2100 x66671
|
e-mail:
|
godfrey@yorku.ca
|
|
|
T.A.'s:
|
To be announced...
|
Office:
|
|
Office Hours:
|
|
e-mail:
|
|
|
|
|
Term:
|
Fall 2015
|
Time:
|
Mondays 7:00–10:00pm
|
Place:
|
LAS C
|
|
|
|
|
Welcome
to the course
Discrete Mathematics for Computer Science,
EECS-1019 (cross-listed as MATH-1019)
for fall term 2015.
Materials, instructions, and notices
for the course will accumulate here over the semester.
|
|
|
|
Class
announcements will accumulate here over the term.
Be certain to check here regularly.
Also, be certain to refresh this page via your browser
when you visit to ensure that you are not looking at an old, cached copy.
Otherwise, you can miss the latest message.
Marks will accumulate on
ePost
(for if you have an EECS account).
Final exam preparation guide.
Tutorial 6-8pm Thursday 17 December
in #3033 Lassonde Builing.
Tutorial 6-8pm Thursday 10 December
in #3033 Lassonde Builing.
Final exam is 7:00pm–10:00pm Tuesday 22 December
at TC VIVA.
Tutorial 4-6pm Friday 20 November
in #3033 Lassonde Builing.
Test #2 is the first half of lecture time
on Monday 23 November.
It is closed notes, closed books.
It covers the material from
§2.4 & 2.5,
§3.1–3.3,
§5.1–5.3,
and what we cover in class on Monday 16 November,
which was §6.1 & 6.3,
as in the textbook and as we covered in lecture.
Problems will be very similar to those in the book
and in the assignments.
See these
“test #1's” from previous terms as examples.
Of course,
each of the tests from above from different terms
had slightly different coverage of material.
So only pay attention to those questions
that are from the sections
that our test #2 covers.
Test #1 is the first half of lecture time
on Monday 19 October.
It is closed notes, closed books.
It covers the material from §1.1–1.8
and §2.1–2.3
as in the textbook and as we covered in lecture.
(Know just the basic definitions for functions from §2.3;
the test will not do into depth on this,
as we covered it briefly.)
Problems will be very similar to those in the book
and in the assignments.
See these
“test #1's” from previous terms as examples.
The Lassonde Student Government offers free tutoring via
Excellassonde.
Tutorials (i.e., review sessions) start this week
on 6-8pm Thursday 1 October.
They will be weekly each week ending
with 6-8pm Thursday 3 December.
They will take place in CFA #312.
They are not obligatory.
Apologies.
No tutorial for Thursday night 24 September;
I could not get a room scheduled for it.
We should be scheduled for next week onward, though,
so will start with a tutorial on 6-8pm Thursday on 1 October.
Welcome to the class!
|
|
|
|
|
The Topic (from the academic calendar)
Introduction
to abstraction;
use and development of precise formulations of mathematical ideas;
informal introduction to logic; introduction to naïve set theory;
induction;
relations and functions;
big-O notation;
recursive definitions, recurrence relations and their solutions;
graphs and trees.
|
|
Course Content (from the academic calendar)
A
detailed list of topics is as follows.
proof techniques (without using a formal system)
naïve set theory
proving that one set is a subset of another
proving equality of two sets
basic operations on sets
(union, intersection, Cartesian product, power sets, etc.)
cardinality of sets (finite and infinite)
strings
functions and relations
review of basic definitions
(relation, function, domain, range, functions, 1-1 correspondence,
function composition, closures of relations, etc.)
equivalence relations
asymptotic notation
big-O, big-Omega, big-Theta
proving f is in O(g), proving f is not in O(g)
classifying functions into a hierarchy of important classes
recursive definitions & solving recurrences
recursive definitions of mathematical objects
solving simple recurrences
bounding divide-and-conquer recurrences of the form
using structural induction on recursively defined objects
sums
elementary graph theory
|
|
Required Textbook / Reading
Course
materials will be drawn from the assigned readings
from the course textbook
Or you can sign up for additional study materials
& the electronic edition via McGraw Hill Connect.
McGraw Hill Connect Notes for our class:
PDF,
PPT.
(Thanks to Michele Peach of McGraw Hill.)
|
|
Grading Criteria & Course Requirements
what
|
%
|
when
|
Homework Assignments 1–10
|
20%
|
ten, due weekly over the term
|
Test #1
|
20%
|
Mo 19 Oct
|
Test #2
|
20%
|
Mo 23 Nov
|
Final Exam
|
40%
|
? Dec
|
There
will be 10 homework assignments altogether,
one per week.
The first two are to be done using McGraw Hill Connect.
(See the bottom of this page for instructions.)
The tests will be held in the class's lecture room
during the first 90 minutes of the lecture time
on the days as stated.
The final exam will be during the fall-term examination period.
The date will be announced.
If you miss one of the tests
for a justified reason (e.g., medical),
the credit for that test will be transfered to the final exam.
In that case,
your final exam's weight will be 60%.
See the section on Polices below.
|
|
Schedule
week#
|
day
|
topic
|
reading
|
due
|
I. Logic
|
#1
|
Mo 14 Sep
|
introduction
propositional logic
predicates & quantifiers
|
§1.1–1.3
|
|
#2
|
Mo 21 Sep
|
predicates & quantifiers
nested quantifiers
|
§1.4 & 1.5
|
A-1
A-2
|
#3
|
Mo 28 Sep
|
rules of inference
introduction to proofs
proof methods & strategies
|
§1.6–1.8
|
A-3
|
#4
|
Mo 5 Oct
|
sets
set operations
functions
|
§2.1–2.3
|
A-4
|
Thanksgiving (12 October)
|
II. Counting & Complexity
|
#5
|
Mo 19 Oct
|
Test #1
|
sequences & summations
cardinality of sets
the growth of functions
|
§2.4, 2.5
§3.1
|
A-5
|
#6
|
Mo 26 Oct
|
the growth of functions
complexity of algorithms
|
§3.2 & 3.3
|
A-6
|
#7
|
Mo 2 Nov
|
mathematical induction
strong induction & well-ordering
recursive definitions & structural induction
|
§5.1—5.3
|
A-7
|
#8
|
Mo 9 Nov
|
the basics of counting
permutations & combinations
binomial coefficients & identities
|
§6.1, 6.3, & 6.4
|
A-8
|
#9
|
Mo 16 Nov
|
applications of recurrence relations
solving linear recurrence relations
divide-and-conquer algorithms & recurrence relations
|
§8.1—8.3
|
A-9
|
III. Relations & Graphs
|
#10
|
Mo 23 Nov
|
Test #2
|
relations and their properties
n-ary relations & their applications
representing relations
|
§9.1—9.3
|
A-10
|
#11
|
Mo 30 Nov
|
closures of relations
equivalence relations
|
§9.4 & 9.5
|
|
#12
|
Mo 7 Dec
|
graphs & graph models
graph terminology & special types of graphs
representing graphs & graph isomorphism
|
§10.1–10.3
|
|
exam period (9–23 Dec)
|
|
? Dec
|
Final Exam
|
The
homework assignments (the A-#'s)
are due before the next class lecture.
For example,
A-3 is due by Monday 5 October before 7pm (lecture).
A-4 is not due until Monday 19 October (before 7pm)
due to Thanksgiving intervening.
A-1 and A-2
are both due by Monday 28 September (before 7pm).
This is just to give some buffer on A-1
as term is starting.
Caution: Do not put it off!
|
|
|
|
Lecture Notes
introduction &propositional logic
propositional logic continued, predicate logic
arguments & proofs
sets & functions
sequences, summations, & cardinalities
algorithms: basics, growth of functions, &
algorithmic complexity
induction & recursion
counting / combinatorics
advanced counting techniques: solving recurrence relations
relations
|
|
|
Homework Assignments
Assignments
A-1 & A-2 must be done online.
You need to register for a free trial of
Connect
and submit
the homeworks electronically.
McGraw-Hill Connect
is a learning tool that allows,
among other things,
automatic homework submission and evaluation.
You will find the instructions on where to find Connect here.
Make sure you register for appropriate section.
When you register for
Connect,
remember to include your first and last name exactly
as they appear in York's records;
otherwise, we will not be able to identify your homework,
and you will not receive credit for it.
For Assignments A-3 through A-10,
you may either keep submitting homeworks online via
Connect
(given you decided to purchase it),
or you may submit them in hardcopy.
week#
|
problems
|
due
|
#1
|
On
Connect.
§1.1: 2a–f,
12a–f,
24a–h
(choose 10 of 20, 2pt each)
§1.2: 10,
16
(5pt each)
§1.3: 6,
8a–d,
10a–d,
30,
34a–c
(choose 10 of 13, 2pt each)
|
Due before lecture on Monday 28 Sept
A1 (PDF)
|
#2
|
On
Connect.
§1.4: 8a–d,
20a–e,
24a–e
(2pt each)
§1.5: 6a–f
(2pt each)
|
Due before lecture on Monday 28 Sept
A2 (PDF)
|
#3
|
§1.6: 8, 14, & 24
§1.7: 6, 8, 16, 24, & 26
§1.8: 4 & 14
Each will be graded out of 4 marks: 40pt total.
|
Due before lecture on Monday 5 Oct
A3 (PDF)
|
#4
|
§2.1: 6 (4pt),
20a–d (1pt each),
32 (4pt),
44 a–c (2pt each)
§2.2: 16a–e (2pt each),
50a–d (2pt each),
§2.3: 12,
(4pt),
34 (5pt),
36 (5pt)
50pt total.
|
Due before lecture on Monday 19 Oct
A4 (PDF)
|
#5
|
§2.4: 10a–e,
30a–d
§2.5: 2a–f
2pt each: 30pt total.
|
Due before lecture on Monday 26 Oct
A5 (PDF)
|
#6
|
§3.1: 4 & 12
(5pt each)
§3.2: 18 (5pt) & 30a–e
(2pt each)
25pt total.
|
Due before lecture on Monday 2 Nov
A6 (PDF)
|
#7
|
§3.3: 8, 14a, 14b, & 18
(5pt each: 20pt total.)
|
Due before lecture on Monday 9 Nov
A7 (PDF)
|
#8
|
§5.1: 20, 22, & 32
§5.2: 12
§5.3: 12 & 44
(5pt each: 30pt total.)
|
Due before lecture on Monday 16 Nov
A8 (PDF)
|
#9
|
§6.1: 8, 12, 32b, d, & f, & 64
§6.3: (4), 14 & 26a, b, & c
§6.4: 4, 6, & 14
(2pt each)
|
Due before lecture on Monday 30 Nov
(Amnesty for week of Test #2.)
A9 (PDF)
|
#10
|
§8.1:
11a–c
§8.2:
4a–e,
8a&b,
12 (4pt),
24a–c;
(2pt each, except as noted)
|
Due before lecture on Monday 7 Dec
A10 (PDF)
|
Homework assignments in hardcopy must be
readable and should show
the work that led to your answer.
All hardcopy homework assignments must be dropped
off at the drop-box for EECS-1019
in the lobby of the Lassonde Building
(which houses the EECS department)
adjacent to room #1003
by 7:00pm (before the class lecture)
of the day they are due.
No late assignments will be accepted.
Any discussion about the grading should be conducted with the TA.
|
|
Tutorials
Tutorials
start with 6-8pm Thursday 1 October.
They will be weekly each week,
ending with 6-8pm Thursday 3 December.
They will take place in CFA #312.
They are not obligatory.
|
|
|
Other References
- Norman L. Biggs.
Discrete Mathematics.
Oxford University Press, 2002.
- Alan Doerr and Kenneth Lavasseur.
Applied Discrete Structures for Computer Science.
Science Research Associates, 1985.
- Gary Haggard, John Schlipf and Sue Whitesides.
Discrete Mathematics for Computer Science.
Thomson, 2006.
- Rod Haggarty.
Discrete Mathematics for computing.
Addison-Wesley, 2002.
- Bernard Kolman, Robert C. Busby and Sharon Cutler Ross.
Discrete Mathematical Structures.
Pearson, 2004.
- Edward Scheinerman.
Mathematics: A Discrete Introduction.
Thomson, 2006.
- Daniel Solow.
How to Read and Do Proofs:
An Introduction to Mathematical Thought Processes.
Wiley, 2002.
- Andrew Wohlgemuth.
Introduction to Proof in Abstract Mathematics.
Saunders College Publishing, 1990.
|
|
|
|
Exams & Attendance
Tests
and the Final Exam
must be taken when scheduled unless the student has a medical
documentation or can demonstrate special circumstances for a
need for a rescheduled exam.
The student must obtain approval
from the instructor.
As stated above,
one missed test (with proper justification)
will be shifted onto the weight of the Final Exam.
Class attendance is useful and highly encouraged,
as the student will have an
opportunity to ask for clarification of course and text material.
There will be problem solving sessions during class period
so that students gain experience applying the theory in practice.
However,
class attendance will not be monitored
and is not part of the grade.
|
|
E-mail Policy
On e-mail from students with questions regarding course materials.
I will not answer these e-mails by e-mail reply,
in general.
My time is spent more productively for the class's sake
in different ways.
For pertinent questions on the materials that students send me
by e-mail
—
or for questions that many people seem to be having
—
I will try to address them in class.
If you have an urgent question I have not addressed,
come see me during my office hours,
or make an appointment if you need to.
Many students do this already;
it is a good use of my time and theirs.
I can usually answer a question a student asks
in person in about a tenth the time than by an e-mail exchange.
Writing it out takes much longer.
And for many of the questions people send me,
the question is often unclear.
It then requires a back and forth by e-mail several times.
On e-mail from students with issues regarding administrative matters.
For administrative requests
(e.g., “I cannot make the test,”),
e-mail is fine, of course,
and I will attempt to answer you directly.
Please use a York University account when e-mailing me
(with regards to the course),
so that I can know who it is.
Please include [1019] at the beginning
of the subject line so I am able to sort it.
Send messages in plain text, without attachments.
I do not mind students sending questions by e-mail.
Just do not necessarily expect a direct reply.
I do read them,
and I try to address the issues and questions people raise.
If your question or issue remains after some time,
do let me know.
|
|
Academic Integrity, Honesty, & Plagiarism
The
Department of Electrical Engineering & Computer Science's
Academic Honesty Guidelines
are in effect for this course,
as, indeed, they are for any EECS course.
Plagiarism is defined as taking the language, ideas, or thoughts
of another,
and representing them as your own.
If you use someone else's ideas, cite them.
If you use someone else's words, clearly mark them as a quotation.
Note that plagiarism includes using another's computer programs or pieces
of a program.
All noted instances of plagiarism will be reported.
These policies are not intended to keep students
from working with other students.
One can learn much working with others,
so this is to be encouraged.
Should you encounter any situations for which you are uncertain
whether the collaboration is permitted or not,
please ask.
|
|
|
|
|