CISC203 DISCRETE MATHEMATICS FOR COMPUTING II, fall 2019
Course Description  fall 2019
NEWS AND ANNOUNCEMENTS
 Nov. 24
 During the week Nov. 25  Nov. 28 we have the usual office hours.
In the week before the exam office hours are held as follows:
 Tuesday Dec. 3, 12:30  1:30 PM, Diana Balant, Goodwin 230
 Tuesday Dec. 3, 1:30  2:30 PM, Daniel Forestell, Goodwin 230
 Wednesday Dec. 4, 10:30  11:30 AM, Benjamin Lammers, Goodwin 230
 Wednesday Dec. 4, 11:30AM  12:30PM, Yan He, Goodwin 230
 Wednesday Dec. 4, 12:30  1:30 PM, Tong Liu, Goodwin 230
 Wednesday Dec. 4, 1:30  2:30 PM, Kai Salomaa, Goodwin 545
 Thursday Dec. 5, 11:30AM  12:30 PM, Chris Keeler, Goodwin 230
 Thursday Dec. 5, 2:30  3:30 PM, Shengan Li, Goodwin 230
 Nov. 24

 Information concerning the
final exam is posted
here.
The final exam is on Saturday December 7 at 9:00AM.
 The last classes on Nov. 25
(given by Taylor Smith),
on Nov. 26 and on Nov. 29 will be
used for review for the final exam.
 A practice exam has been posted
here.
Solutions
can be found here.
 Nov. 22
 The three classes in the last week will be used
for review for the final exam.
The class on Monday Nov. 25 is
given by Taylor Smith.
 Nov. 10
 Assignment 4 has been posted
on the assignments page.
Assignment 4 is due on
Thursday November 28.
 Nov. 4
 The midterm papers can be picked up during Chris Keeler
office hour Thursday Nov. 7, 11:30  12:30 or at end of class
Friday Nov. 8.
Sample solutions for the
midterm are here.
 Nov. 2
 The lectures on Tuesday Nov. 5 and on Friday Nov. 8
are given by Taylor Smith.
 Oct. 22
 There is no class on Friday Oct. 25. Have a good midterm
break!
 Oct. 21
 Assignment 3 has been posted
on the assignments page.
Assignment 3 is due on
Thursday November 7.
 Reminder

 The CISC203 midterm test takes place in class on
Monday October 21 at 4:30 PM.
Detailed information on the midterm test is posted
here.
 The midterm is a closed book test
and covers everything covered in the course
up to and including Oct. 7. The corresponding lecture notes
and textbook sections are listed at
http://research.cs.queensu.ca/home/cisc203/index.html#SU
 A practice midterm is posted
here. We will go through questions of
the practice midterm in class on Tuesday Oct. 15.
Solutions for the practice midterm.
 Sept. 23
 Assignment 2 has been posted
on the assignments page.
Assignment 2 is due on
Thursday October 10.
 Sept. 11
 Assignment 1 has been posted
on the assignments page.
Assignment 1 is due on
Thursday September 26.
 Sept. 11
 The TA office hours have been posted below. The office hours
begin the week of Sept. 16.
 Sept. 1
 Welcome to the course!
Announcements concerning the course will be posted above and
you are expected to check this page frequently.
Monday 4:30 PM 
Tueasday 2:30 PM 
Friday 2:30 PM 
Note: The classes meet in two different locations.
The Monday and Friday classes meet in
Chernoff Hall
Auditorium and the Tuesday class meets in
Etherington Hall Auditorium.
For the locations see
campus map
Instructor
 Kai Salomaa
 Goodwin 545, 5336073
 Office hour: Tuesday 3:30  4:30 PM

Email:
When sending me email concerning the course, please make
sure to use your Queen's email account and include CISC203 in the
subject line. Otherwise I may never see the email.
Teaching Assistants
 Diana Balant
 dab10 [at] queensu.ca
 Office hour: Tuesday 12:30  1:30 PM, Goodwin 230
Email for appointment at other times.
 Daniel Forestell
 16dtf1 [at] queensu.ca
 Office hour: Thursday 12:30  1:30 PM, Goodwin 230
Email for appointment at other times.
 Yan He
 16yh53 [at] queensu.ca
 Office hour: Wednesday 11:30 AM  12:30 PM, Goodwin 230
Email for appointment at other times.
 Chris Keeler
 keeler [at] cs.queensu.ca
 Office hour: Thursday 11:30 AM  12:30 PM, Goodwin 230
Email for appointment at other times.
 Benjamin Lammers
 16bdl2 [at] queensu.ca
 Office hour: Wednesday 10:30  11:30 AM, Goodwin 230
Email for appointment at other times.
 Shengan Li
 16sl75 [at] queensu.ca
 Office hour: Monday 1:30  2:30 PM, Goodwin 230
Email for appointment at other times.
 Tong Liu
 9tl14 [at] queensu.ca
 Office hour: Wednesday 12:30  1:30 PM, Goodwin 230
Email for appointment at other times.
 Taylor Smith
 tsmith [at] cs.queensu.ca

Email for appointment.
Note: TA office hours begin the week of Sept. 16th.
TA office hours are for tutorial help with the course material
and assignments,
and discussions of assignment and midterm grading.
If you need additional help, please
see the
COMPSA
web pages.
Required textbook
The textbook is available at the campus bookstore.
Information from campus bookstore can be found
here.
Supplementary reading

There are many textbooks covering related material on discrete
mathematics.
An example is the
text by Rosen
that is available
through Queen's Library:
Author/Creator:Rosen, Kenneth H.
Title:Discrete mathematics and its applications / Kenneth H. Rosen, formerly AT&T Laboratories.
Edition:Eighth edition.
Published:New York, NY : McGrawHill, 2019.
©2019.
Topics covered in class
The topics covered in individual
classes, with references to corresponding material
in the textbook and/or the lecture notes,
will be posted below (in reverse chronological order).
Scans of class notes will be posted at the end of each week.
At the end of each week we will also post a list of
selftest exercises from the
textbook that you can use to test understanding of that weeks material. The
selftest exercises will not be marked. The textbook contains partial
solutions and hints for many of the exercises.
 Scans of review notes for week12
are here.
See also practice exam
solutions.
 Scans of class notes for week11
are here.
 Selftest exercices for week11: Chapter 9
selftest questions: 9, 10, 13, Exercises: 50.2, 50.6, 50.10, 50.12
 Nov. 22 topics
notes6, pp. 1627, textbook:
Section 50, pp. 354355
 Nov. 19 topics
notes6, pp. 815
 Nov. 18 topics
notes6, pp. 18,
textbook Section 50, pp. 350354
 Scans of class notes for week10
are here.
 Selftest exercices for week10: Chapter 9
selftest questions: 17, 18, 19, 20, Exercices 51.1, 51.2, 51.4
 Nov. 15 topics
notes5, pp. 1418, 2327,
textbook: Section 52: pp. 361366
 Nov. 12 topics
notes5, pp. 1114,
textbook: Section 51, pp. 356360
 Nov. 11 topics
notes5, pp. 611,
textbook: Section 49, pp. 344349
 Selftest exercices for week9: Chapter 9
selftest questions: 1, 2, 3, 8, 11, 21, 22, 23
 Scans of class notes for Nov5 and Nov8
(guest lecture by Taylor Smith)
are here.
 Nov. 5 and Nov. 8 topics
notes5, pp. 1823,
textbook: Section 53, pp. 367372
 Scans of class notes for Nov1 and Nov4
are here.
 Nov. 4 topics notes5,
pp. 17,
textbook: Section 47, pp. 331337
 Selftest exercices for week8: Chapter
4 selftest questions: 13, 14, 15, 16, 20
 Scans of class notes for Oct28 and Oct29
are here.
 Nov. 1 topics notes4,
pp. 1720,
textbook: 155157
 Oct. 29 topics notes4,
pp. 1217,
textbook: Section 23, pp. 151154
 Oct. 28 topics notes4, pp.
612,
textbook: Section 23, pp. 149151
 Scans of class notes for weeks 6 and 7
are here.
 Oct. 22 topics notes4, pp. 46,
textbook: Section 22, pp. 141145
 Oct. 21 topics midterm
 Oct. 18 topics review for midterm
 Selftest exercices for week6: Chapter
4 selftest questions: 5, 6, 7, 9, 10, 11, 12
 Oct. 15 topics practice midterm
 Oct. 11 topics
notes4, pp. 24,
textbook: Section 22, pp. 135141
 Selftest exercices for week5: Chapter 6 selftest
questions 13, 14, 15, Chapter 10 selftest questions 1, 2
 Scans of class notes for week5
are here.
 Oct. 8 topics partial orders
notes4, pp. 12 ,
textbook: Sections 5455, pp. 379385
 Oct. 7 topics
textbook: Section 34, pp. 244247, Section 32, p. 227
 Oct. 4 topics
notes34, pp. 110,
textbook: Section 34, pp. 241244
 Selftest exercices for week4: Chapter 6 selftest
questions 1, 3, 5, 6, 7, 12
 Scans of class notes for week4
are here.
 Oct. 1 topics
example on probability/expectation of substring occurrences,
textbook: Section 34, pp. 235241
 Sept. 30 topics
notes32, pp. 15,
notes33, pp. 14,
textbook: Sections 3233, pp. 223228 and 231234
 Sept. 27 topics introduction to probability
notes31, pp. 13,
textbook: Sections 3031, pp. 213221
 Selftest exercices for week3: Chapter 3 selftest
questions 13, 14, 15, 17, 20, 21
 Scans of class notes for week3
are here.
 Sept. 24 topics kcombinations with repetition, binomial
coefficients
notes2, pp. 2025,
textbook: Section 17, pp. 9098, Section 18, pp. 101105
 Sept. 23 topics
combinations
notes2, pp. 1220
 Sept. 20 topics
permutations, kpermutations
notes2, pp. 7  12,
textbook: Section 27, pp. 188191
 Selftest exercices for week2: Chapter 3 selftest
questions 4, 7, 8, Exercices 25.2, 25.3, 25.7
 Scans of class notes for week2
are here.
 Sept. 17 topics
pigeonhole principle
notes2, pp. 57 ,
textbook: Section 24, pp. 174175, Section 25, pp. 178179
 Sept. 16 topics
introduction
to combinatorics, counting, inclusionexclusion
notes2, pp. 14,
textbook: Section 19, pp. 109112
 Sept. 13 topics more functions,
equivalence relations, partitions
notes, pp. 1721 ,
textbook: Sections 1516, pp. 7886
 Selftest exercices for week1: Chapter 2 selftest questions
9, 10, 15, 16; Ch. 5 selftest questions 1, 9, 12, 24
 Scans of class notes for week1
are here.
 Sept. 10 topics relations, inverse of functions
notes, pp. 16  19 ,
textbook: Section 14, pp. 7376, Section 24, pp. 171174
 Sept. 9 topics functions
notes, pp. 9  15,
textbook: Section 24, pp. 167171, Section 29, pp. 205208
 Sept. 6 topics: Course outline, review:
basic concepts for sets, notes, pp. 18,
textbook: Section 10, pp. 4349
(the later lecture notes remain under construction)
 Introduction, sets, functions and relations
 Combinatorics: counting and permutations
 Discrete probability
 Partial orders, induction and recurrence relations
 Graph theory
 Trees
 Number theory and cryptography
Class note outlines will be posted
on the lecture notes page.
Note: The purpose of the posted outlines
is to assist you in taking notes in class.
Reading the posted notes is not a substitute
for attending the classes.
In particular, most of the examples we go over in class
are not included in the posted outlines.
Academic Integrity
Please see a
Statement on Academic
Integrity from the Arts and Science
web site posted
here.
There will be 4 sets of assignments, due by 2:30 PM on the
following Thursdays:
September 26, October 10, November 7, November 28.
The assignments must be based on individual work.
Each assignment is worth 8% of your course mark.
The assignment questions (and their solutions after the due date)
will be posted
on the assignments page.
Rules of the assignments:
 The assignments must be based on individual work
since otherwise this
will be a violation of
Academic
Integrity.

The assignments are submitted into the locked CISC 203
dropoff box
on the second floor of Goodwin hall (near rooms
233, 241).

Please note: Assignments must be submitted in hardcopy.
Assignments sent by email are not accepted.

Please note. You should submit your assignment
into the locked dropoff box only after you are
completely sure you have
the final version of the assignment. Submitting multiple
copies of the same assignment is not permitted. (We have
a very large class and the TAs are overworked as it is.)
 If you submit more than one copy of the same assignment,
only one randomly chosen version will be marked.

A student submitting more than one copy
of the same assignment automatically forfeits
the bonus mark for the assignment.
(See information on the bonus mark
on the posted assignments.)
 Format of assignments:
At the top of the first page
of the assignment, please include
the following information printed or written
neatly in clear capital letters on four separate lines:
 CISC203, assignment X (where X is the number
of the current assignment)
 your full name exactly as it appears on solus
(LASTNAME, FIRSTNAME),
 your student number,
 your signature (the signature need not be easily readable).
 Each of the above four items should be on its own line.
If the submission consists of several pages, the pages must be
stapled together.
Note: You are asked to write your assignment solutions
using nonerasable pen (or to type the solutions). Solutions written
in pencil or erasable ink will be marked, but they will not
be considered for remarking after the assignments are returned.
If you have questions concerning assignment marking, you should
discuss them with the TA who did the marking
within one week
from the time when the marked assignments are made available.
All assignment marks are considered final after that time.
If you cannot attend the office hours
of the particular TA,
please fill out the
form here. Place the
form and your assignment
in an envelope and hand it to the instructor in class
or to any of the TAs within
one week after the marked assignments were returned in class.
Late Assignment Penalty

An assignment that is
at most 24 hours late will have deducted a penalty of
10% of the maximum mark.
That is, if you submit a late assignment before 2:30 PM on the Friday
following the due date, the assignment incurs a 10% late penalty.

A late assignment submitted before 2:30 PM on the Monday following
the Thursday due date of the asssignment will have deducted
a penalty of 30% of the maximum mark.

An assignment which is more than 96 hours late will
not be accepted. That is, assignments submitted after 2:30 PM on the Monday
following the Thursday due date are not accepted.
All late assignments should be submitted into the same locked CISC203
dropoff box on Goodwin hall second floor (near rooms 233, 241).
There will be a 40 minute midterm test
during the class hour on

Monday October 21 at 4:30 PM.
The midterm is a
closed book test. You may bring with you
one 8.5" x 11" page of notes and use it during
the midterm test.
The final exam will be held during the regular fall term
final examination period. The final is a 3 hour closed book exam.
You may bring
one 8.5" x 11" sheet containing notes
and use it during the final exam.
Your grade is calculated as follows (with the two modifications
listed below):
Midterm 
18% 
Assignments
(4 assignments, each 8%)

32% 
Final exam 
50% 
Total: 
100% 
Note:

If you receive less than 50% on the final exam, your course mark is
calculated as: 75% final exam, 25% midterm. That is, to pass the course
you need to pass the final (unless you do very well in the midterm).

To allow you to replace possible poor marks obtained
during the term by doing well in the final exam,
the following alternate marking scheme is available
to students who
have made a serious attempt in the midterm:
Provided that
you
make a serious attempt in the midterm,
you can replace your midterm grade by
the final exam grade (as a percentage).
Note: The components of this course will receive numerical marks
that will be used to calculate a percentage final grade, as
explained above. The final grade you receive for the course
will be derived by converting your percentage grade to
a letter grade according to Queen's official grade conversion
scale.
Calendar description for CISC203
Proof methods. Combinatorics: permutations and combinations,
discrete probability, recurrence relations.
Graphs and trees. Boolean and abstract algebra.
Goals of the course
 The course covers main concepts of discrete mathematics,
as it is used for applications in computing.
 The main topics include:
 Combinatorics: counting and permutations
 Discrete probability
 Graph theory
 Number theory and cryptography
 An important goal of the course is to get
practice with various proof techniques
and become familiar with the notion of
formal
proof as used in mathematics.
We do not cover proof methods as its own topic
but instead illustrate different proof techniques
by examples
as we go through the main technical topics.
A course learning outcome is a brief statement of a skill, competency, or attitude a successful student will
achieve by the end of a course. The following list of learning outcomes for CISC 203 is provided by the
School of Computing. (http://www.cs.queensu.ca/students/undergraduate/outcomes/CLO.php)
 Critique and construct moderately sophisticated
mathematical arguments such as proof by contradiction,
proof by induction, proof by minimal counterexample,
counting arguments, and recognition of orderings

Apply discrete mathematical tools and models such as graph theory, probability, group theory and modular arithmetic to problems such as modelling relational data and networks, scheduling and resource allocation, network design, predicting expected performance, motion planning, cryptography

Apply basic discrete probability techniques to computational tasks

Build a foundation for further learning by exposure to multiple computer languages, development tools, and methodologies.
The School's web page at
http://www.cs.queensu.ca/students/undergraduate/syllabus/year201920.php,
and the pages to which it links, are part of this syllabus.
Accommodations Statement
Queen's University is committed to achieving full
accessibility for persons with
disabilities.
Part of this commitment includes arranging academic
accommodations for students with
disabilities to ensure they have an equitable opportunity
to participate in all of
their
academic activities. If you are a student with a disability
and think you may need
accommodations,
you are strongly encouraged to contact Student
Wellness Services (SWS) and register
as early as possible. For more information,
including important deadlines, please
visit the Student Wellness
website at: http://www.queensu.ca/studentwellness/accessibilityservices/
Academic Consideration for Students in Extenuating Circumstances
The Senate Policy on Academic Consideration for Students
in Extenuating Circumstances
(http://www.queensu.ca/secretariat/sites/webpublish.queensu.ca.uslcwww/files/files/policies/senateandtrustees/Academic%20Considerations%20for%20Extenuating%20Circumstances%20Policy%20Final.pdf)
was approved in April, 2017. Queen's University is
committed to providing academic consideration to students
experiencing extenuating circumstances that are beyond
their control and which have a direct and substantial impact on their
ability to meet essential academic requirements.
Each Faculty has developed a protocol to provide
a consistent and equitable approach
in dealing with requests for academic consideration
for students facing extenuating circumstances.
Arts and Science undergraduate
students can find the Faculty of Arts and Science protocol
and the portal where they submit a request at:
http://www.queensu.ca/artsci/accommodations.
Students in other Faculties and Schools should refer to the protocol for their home Faculty.