CISC203*Discrete Mathematics for Computing IIFall 2016 
Image by Paul B, used under Creative Commons licence 
"Upon this first, and in one sense this sole, rule of reason, that in order to learn you must desire to learn, and in so desiring not be satisfied with what you already incline to think, there follows one corollary which itself deserves to be inscribed upon every wall of the city of philosophy: Do not block the way of inquiry." Charles S. Peirce 

Internal Links  Announcements  
Personnel  
Course Information  
Schedule  
Course Plan and Record  
Practice Problems  
Recommended Readings  
Sample Tests  
Academic Integrity in CISC 203  
Date  Subject  Text 
2016/10/18 
Section 002 Class Moved 
Due to an unforeseen circumstance, I (Matthew) will be away on October 18 and will not be able to present the October 18 class to section 002.
So, I am asking that all students in my section (Section 002) please go to Prof. Dawes' section of the class on October 18 in Dupuis Auditorium (at the same time as usual).
Thank you for your understanding. 
2016/09/15 
NoteTaker Request 
Please consider
volunteering to be a notetaker for another student in this
class. See this
link for more information. 
Instructors 
Dr. Robin W. Dawes 

Goodwin 537 

dawes
AT cs DOT queensu DOT ca 

http://sites.cs.queensu.ca/dawes/ 

5336061 (but email is a much better
idea) 

Office Hours: TBA 

Matthew Holden  
Goodwin 747  
mholden8@cs.queensu.ca  
http://perk.cs.queensu.ca/users/holden  
N/A  
Office Hours: Wednesday 10:00am  12:00noon (or by appointment) 
TAs 
Name 
Email 
Office Hours 
Picture 
Bodrul Alam 
alam@cs.queensu.ca 

Krystina Correa 
Krystina.correa@queensu.ca  
Nicole Ellis 
nicole.ellis@queensu.ca  
Hillary Elrick  14he@queensu.ca  
Chris Keeler 
1ck7@queensu.ca 
Calendar
Description 
Proof methods. Combinatorics: permutations and combinations, discrete probability, recurrence relations. Graphs and trees. Boolean and abstract algebra. 
Text 
Required: Edward Scheinerman, Mathematics:
a Discrete Introduction, Third Edition 
Syllabus 
pretty much what the calendar says. 
Marking Scheme 
Your final grade is calculated from
your marks on five tests. There are no assignments and no
final examination. A record of test marks will be kept in onQ. Your four best test marks will each be worth 22.5% of your final grade. Your lowest test mark will be worth 10% of your final grade. There will be no makeup tests for missed tests. You will not be able to write a test a day earlier or a day later because it suits your personal schedule better. If you miss a test and can demonstrate sufficient extenuating circumstances we will create a modified marking scheme for you. Sports events, family gettogethers and other social activities (including Queen's Homecoming) are not considered extenuating circumstances. Students with special needs are responsible for contacting the instructors at least a week before each test. Please see the Queen's Disability Services page for students for more information. 
Class
Schedule 
Tuesday 9:30  10:20 Thursday 8:30  9:20 Friday 10:30  11:20 

Test
Schedule 
Date 
Material 
Solutions 
Test 1 
September 29, 2015 
Solutions 

Test 2 
October 14, 2015 

Test 3 
October 28, 2015 

Test 4 
November 17, 2015 

Test 5 
December 2, 2015 
Week 1 
Tuesday September 13 Plan:  Introduction  Review PBC Notes: Section 001 (Dawes) Notes: Section 002 (Holden) 
Thursday September 15 Plan:  Review Recurrence Relations  Review PBI Notes: Section 001 (Dawes) Notes: Section 002 (Holden) 
Friday
September 16 Plan:  Review Functions  Review Counting Problems Notes: Section 001 (Dawes) Notes: Section 002 (Holden) 
Week 2 
Tuesday September 20 Plan:  WellOrdering  Minimal Counterexample Proofs Notes: Section 001 (Dawes) Notes: Section 002 (Holden) 
Thursday September 22 Plan:  Permutations Notes: Section 001 (Dawes)  see Sept 23 Notes: Section 002 (Holden) 
Friday
September 23 Plan:  Permutations  Notation Notes: Section 001 (Dawes)  notes for Sept 22 and 23 Notes: Section 002 (Holden) 
Week 3 
Tuesday September 27 Plan:  Sample Spaces  Events Notes: Section 002 (Holden) 
Thursday September 29 Plan: TEST 1 Solutions 
Friday
September 30 Plan:  Independence  Conditional Probability Notes: Section 001 (Dawes)  notes for Sept 27 and 30 Notes: Section 002 (Holden) 
Week 4 
Tuesday October 4 Plan:  Random Variables Notes: Section 002 (Holden) 
Thursday October 6 Plan:  Expectation Notes: Section 002 (Holden) 
Friday
October 7 Plan:  Modular Arithmetic Notes: Section 001 (Dawes)  Full Week Notes: Section 002 (Holden) 
Week 5 
Tuesday October 11 Plan:  Remainder Theorem Notes: Section 001 (Dawes) Notes: Section 002 (Holden) 
Thursday October 13 Plan:  Groups Notes: Section 001 (Dawes) Notes: Section 002 (Holden) 
Friday
October 14 Plan: TEST 2 
Week 6 
Tuesday October 18 Plan:  Group Isomorphism Notes: Section 002 (Holden) 
Thursday October 20 Plan:  Introduction to Cryptography Notes: Section 002 (Holden) 
Friday
October 21 Plan:  Rabin Cryptography Notes for the entire week: Section 001 (Dawes) Notes: Section 002 (Holden) 
Week 7 
Tuesday October 25 Plan:  RSA Cryptography Notes: Section 001 (Dawes) Notes: Section 002 (Holden) 
Thursday October 27 Plan:  Introduction to Partial Orderings Notes: Section 001 (Dawes) Notes: Section 002 (Holden) 
Friday
October 28 Plan: TEST 3 
Week 8 
Tuesday November 1 Plan:  Minima and Maxima Notes: Section 002 (Holden) 
Thursday November 3 Plan:  Linear Ordering Notes: Section 002 (Holden) 
Friday
November 4 Plan:  Linear Extensions Notes for the entire week: Section 001 (Dawes) Notes: Section 002 (Holden) 
Week 9 
Tuesday November 8 Plan:  Dimensions Notes: Section 002 (Holden) + Example 3D Embedding 
Thursday November 10 Plan:  Lattices Notes for Tuesday and Thursday: Section 001 (Dawes) Notes on Upper and Lower Bounds: Section 001 (Dawes) Notes: Section 002 (Holden) 
Friday
November 11 Plan:  class cancelled for Remembrance Day Services  readings on introduction to Graph Theory 
Week 10 
Tuesday November 15 Plan:  Subgraphs Notes: Section 002 (Holden) 
Thursday November 17 Plan: TEST 4 
Friday
November 18 Plan:  Graph Connectivity Notes: Section 001 (Dawes) Notes: Section 002 (Holden) 
Week 11 
Tuesday November 22 Plan:  Trees Notes: Section 002 (Holden) 
Thursday November 24 Plan:  Eulerian Graphs Notes: Section 002 (Holden) 
Friday
November 25 Plan:  Graph Colouring Notes: Section 001 (Dawes) Notes: Section 002 (Holden) 
Week 12 
Tuesday November 29 Plan:  Planar Graphs Notes: Section 001 (Dawes) Notes: Section 002 (Holden) 
Thursday December 1 Plan:  It's a Mystery Notes: Section 002 (Holden) 
Friday
December 2 Plan: TEST 5 
Topic  Scheinerman  Other Sources 
Proof Methods  PBC: 20.4,
20.5, 20.6, 20.10, 20.13 PBI: 22.1, 22.4, 22.9, 22.16 (ignore part f) 
PBC: http://www.shmoop.com/logicproof/proofbycontradictionexamples.html PBI: http://www.mathcentre.ac.uk/resources/uploaded/mathcentreproof.pdf http://www.cs.cornell.edu/courses/cs211/2004su/exercises/Induction.pdf (ignore Q 4) 
Functions  24.1, 24.2, 24.3, 24.4, 24.7, 24.16, 24.18, 24.20  
Counting Problems  17.1, 17.5, 17.6, 17.7, 17.8, 17.10, 17.11, 17.30  
WellOrdering and Minimal Counterexamples  21.2,
21.3, 21.4, 21.9 

Permutations  27.2, 27.3, 27.5, 27.6, 27.7, 27.10, 27.12, 27.14, 27.19 (ignore
part f) 

Order Notation  29.1 (ignore c and f), 29.3, 29.4, 29.5, 29.6, 29.10  
Probability  30.2, 30.5, 30.7, 30.10 31.1, 31.3, 31.4, 31.5, 31.7, 31.11, 31.15 32.1 (do as many parts as needed), 32.3, 32.9, 32.11, 32.17, 32.21, 32.32 33.1, 33.2, 33.4, 33.6, 33.8 34.2, 34.4, 34.5, 34.15, 34.19 

Modular Arithmetic  37.1 (do as many parts as needed),
37.2, 37.3, 37.6, 37.12 
http://www.math.csusb.edu/notes/cgi/modtutor.cgi 
Number Theory  38.1, 38.3, 38.5, 38.6 

Groups and Group Isomorphism  40.1, 40.2, 40.4, 40.5, 40.9, 40.10, 40.11, 40.16 41.1, 41.2, 41.5, 41.6, 41.7 

Cryptography  44.4 46.1, 46.2, 46.3, 46.4, 46.6 

Partial Orderings  54.1, 54.2, 54.5, 54.8, 54.9, 54.12 55.1, 55.2(a,b,c), 55.4, 55.7 56.1, 56.2, 56.3, 56.4, 56.5 57.1, 57.2, 57.3 58.1, 58.4, 58.5, 58.7 59.1, 59.2, 59.6, 59.7 

Linear Orderings  
Graphs  47.1, 47.2, 47.13, 47.16, 47.19, 47.20 48.1, 48.3, 48.5, 48.8, 48.10, 48.13 49.1, 49.3, 49.5, 49.9, 49.13 50.2, 50.3, 50.6, 50.7, 50.12, 50.17, 50.18 52.1, 52.5, 52.6, 52.7, 52.11 
Source 
Section 
Read
Before ... 
Comments 
Learning
(Your
First Job) 
All 
September 14 
Essential reading for all students 
Computer Science For Fun  Any  whenever  Purely recreational 
David Ferry's Notes on Proof Techniques  All 
September 16 
Proofs 
Mathematics: A Discrete Introduction
(MDI) 
Chapter 1, all sections 
September 19  Review 
MDI 
Chapter 3, all sections 
September 19  
MDI 
Chapter 4, all sections 
September 19  
MDI 
Chapter 5, Sections 24, 25 
September 19 

MDI 
Chapter 5, Section 27 
September 22 
Permutations 
MDI 
Chapter 5, Section 28 
September 23 

MDI 
Chapter 5, Section 29 
September 23 
Notation 
MDI  Chapter 6, all sections  September 30  Probability 
MDI  Chapter 7, Section 37  October 6  Modular Arithmetic 
MDI  Chapter 7, Section 38  October 9  Remainder Theorem 
MDI  Chapter 8, Sections 40, 41  October 12 
Group Theory 
MDI  Chapter 8, Sections 44, 45, 46  October 24 
Cryptography 
MDI  Chapter 10, Section 54  October 26  Introduction to Orderings 
MDI  Chapter 10, all remaining sections  November 10  Orders 
MDI  Chapter 9, Section 47  November 21  Graph Theory 
MDI  Chapter 9, all remaining sections  December 1 
Test 1 
Test
1 from 2015 
Notes: The sample contains
questions about Zb and about base2 notation, which we have not
covered in 2016's version of CISC203. Also the test does not
have questions about functions and permutations, which we have
covered. Nonetheless, it should give you a good sense of the
test format and the difficulty of the questions. Solutions will be posted tomorrow. Please try the problems before you look at the solutions. 
Solutions and marking guide  please take careful note of the marking guidelines. It will help you understand how to obtain part marks even if you cannot completely answer a question on the test.  
Test 2 
Some Sample
Questions Solutions 
Notes: This material has not been in CISC203 so we don't have a
previous test ... but these questions are good practice Notes: The provided solutions are rough sketches and not the only way to answer each of these questions. 
Test 3 
Some Sample
Questions Solutions 
Notes: Again, this material has not been in CISC203 previously, so we don't have a previous test. These are some questions that are good practice. Notes: These solutions are rough sketches and are not the only way to answer each of these questions. Please try the problems before your look at the solutions. 
Test 4 
Some Sample
Questions Solutions 
Notes: Again, this material has not been in CISC203 previously, so we don't have a previous test. These are some questions that are good practice (but may take a bit longer than a test). Notes: These solutions are rough sketches and are not the only way to answer each of these questions. Please try the problems before you look at the solutions. 
Test 5 
Some Sample Questions Solutions 
Notes: Question 1 comes from a previous year's test. The remaining questions are good practice. Notes: These solutions are rough sketches and are not the only way to answer each of these questions. Please try the problems before you look at the solutions. 
Students are responsible for familiarizing themselves with the regulations concerning academic integrity and for ensuring that their assignments conform to the principles of academic integrity. Information on academic integrity is available in the Arts and Science Calendar (see Academic Regulation 1 on the Arts and Science website) and from the instructor of this course.
Departures from academic integrity include plagiarism, use of unauthorized materials, facilitation, forgery and falsification, and are antithetical to the development of an academic community at Queen's. Given the seriousness of these matters, actions which contravene the regulation on academic integrity carry sanctions that can range from a warning or the loss of grades on an assignment to the failure of a course to a requirement to withdraw from the university.
The preceding text on academic integrity is based on a document written by Prof. Margaret Lamb and is used here with her permission.