CISC203*Discrete Mathematics for Computing IIWinter 2020 
Circle Limit III  M.C. Escher Image found on WikiArt Used here under Fair Use principle 
"Beauty is the first test: there is no permanent place in the world for ugly mathematics."G. H. Hardy
"There should be no such thing as boring mathematics."Edsger Dijkstra


Internal Links  Announcements  
Personnel  
Course Information  
Schedule  
Course Plan and Record  
Practice Problems  
Recommended Readings  
Sample Tests  
Academic Integrity in CISC 203  
Change Log  
External Links 
Queen's School of Computing 
Computing
Students'
Association 

Class
Photo Gallery 

Learning

Your First Job (Paper by Dr. R. Leamnson)  ESSENTIAL READING 

Queen's
Academic
Integrity Page 

Date  Subject  Text 
Instructor 
Dr. Robin W. Dawes 

Goodwin 537 

dawes
AT cs DOT queensu DOT ca I typically receive more than 100 email messages each day. I cannot guarantee a response to any message  not even if you put "URGENT" in the subject line. If it's really urgent, see me in person. During the COVID19 outbreak the amount of email arriving in my inbox has escalated to the point at which email is effectively useless  the noise is totally swamping the signal. Please use the daily online office hours to communicate with me directly. 

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

5336061 (but speaking to me in
person is a much better idea)  this phone line is not being
monitored during the COVID19 outbreak. 

Office Hours: Office hours during the COVID19 outbreak will be held online every day. The times of online office hours will be confirmed on a daily basis.


TA
Crew 
Name 
Email 
Office Hours 
Picture 
Bodrul Alam  abmb 

Dimitrios Economou 
de32 

Xavier McMasterHubner 
xjem 
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 inclass tests. There are no assignments
and there is no final examination. A record of test marks will
be kept in onQ. New, "improved" marking scheme:
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 I will create a modified marking scheme for you. Job interviews, sports events, family gatherings and other social activities (including Reading Week plans) are not considered extenuating circumstances. Students with special needs are responsible for contacting the instructor at least a week before each test. Please see the Queen's Student Accessibility Services for more information. 
Class
Schedule 
Monday 8:30  9:20 Tuesday 10:30  11:20 Thursday 9:30  10:20 
All classes in Dupuis 217 

Test
Schedule 
Date 
Material 
Solutions 
Test 1 
January 30 2020, 9:30 AM  Review Permutations Probability 

Test 2 
February 13 2020, 9:30 AM  Modular Arithmetic 

Test 3 
March 5 2020, 9:30 AM 
Remainder Theorem Cryptography Orderings 

Test 4 
March 19 2020, 9:30 AM 
Orderings 

Test 5 
April 2 2020, 9:30 AM 
Graph Theory 
Week 1 
Monday January 6 Plan:
Notes: 
Tuesday January 7 Plan:
Notes: 
Thursday
January 9 Plan:
Notes: WellOrdered Sets and ... PMCE 
Week 2 
Monday January 13 Plan:
Notes: 
Tuesday January 14 Plan:
Permutations 
Thursday
January 16 Plan:
Notes: 
Week 3 
Monday January 20 Plan:
Revised Plan:
Notes: 
Tuesday January 21 Plan:
Revised Plan:
Notes: Time for a new topic? Probably! 
Thursday
January 23 Plan:
Revised Plan:
Notes: 
Week 4 
Monday January 27 Plan:
Notes: Random Variables (which are not random, and not variables) 
Tuesday January 28 Plan:
Notes: 
Thursday
January 30 TEST 1 (Review, Permutations, Probability) 
Week 5 
Monday February 3 Plan:
Notes: 
Tuesday February 4 Plan:

Thursday
February 6 Plan:
Notes: Combined notes for Feb 4 and Feb 6 
Week 6 
Monday February 10 Plan:
Notes: 
Tuesday February 11 Plan:
Revised Plan:

Thursday
February 13 TEST 2 (Modular Arithmetic) 
***** Reading Week *****  
Week 7 
Monday February 24 Plan:
Revised Plan
Notes: See February 25

Tuesday February 25 Plan:
Revised Plan:
Notes: Combined notes for Feb 24 and Feb 25 
Thursday
February 27 Plan:
Notes: 
Week 8 
Monday March 2 Plan:

Tuesday March 3 Plan:

Thursday
March 5 TEST 3 (Remainder Theorem, Cryptography) 
Week 9 
Monday March 9 Plan:

Tuesday March 10 Plan:

Thursday
March 12 Plan:
Notes: More notes on orderings 
Week 10 
Monday March 16 Plan:
Revised Plan:

Tuesday March 17 Plan:
Revised Plan:

Thursday
March 19 TEST 4 (Orderings)  cancelled 
Week 11 
Monday March 23 Plan: Complete Graph Theory notes, in advance: 
Tuesday March 24 Plan: 
Thursday
March 26 Plan: 
Week 12 
Monday March 30 Plan: 
Tuesday March 31 Plan: 
Thursday
April 2 TEST 5 (Orderings and Graph Theory) 
Topic  Scheinerman  Other Sources 
Review  Summer CISC102 Final Exam  
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 http://riemann.math.unideb.hu/~kozma/ContradictionProofexercises.pdf 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.2, 47.3, 47.6, 47.16, 47.17, 47.19, 47.21(d) 48.4, 48.5, 48.6 50.1, 50.2, 50.12 51.1, 51.4 52.7 
Source 
Section 
Read
Before ... 
Comments 
Learning
(Your
First Job) 
All 
September 10 
Essential reading for all students 
Computer Science For Fun  Any  whenever  Purely recreational 
David Ferry's Notes on Proof Techniques  All 
September 11 
Proofs 
Mathematics: A Discrete Introduction
(MDI) 
Chapter 1, all sections 
September 11  Review 
MDI 
Chapter 3, all sections 
September 11  
MDI 
Chapter 4, all sections 
September 11  
MDI 
Chapter 5, Sections 24, 25 
September 11 

MDI 
Chapter 5, Section 27 
September 13 
Permutations 
MDI 
Chapter 5, Section 28 
September 13 

MDI 
Chapter 5, Section 29 
September 17 
Notation 
MDI  Chapter 6, all sections  September 20  Probability 
MDI  Chapter 7, Section 37  October 1  Modular Arithmetic 
MDI  Chapter 7, Section 38  October 9  Remainder Theorem 
MDI  Chapter 8, Sections 40, 41  October 15 
Group Theory 
MDI  Chapter 8, Sections 44, 45, 46  October 22 
Cryptography 
MDI  Chapter 10, Section 54  October 29  Introduction to Orderings 
MDI  Chapter 10, all remaining sections  November 5  Orders 
MDI  Chapter 9, Section 47  November 12  Graph Theory 
MDI  Chapter 9, all remaining sections  November 20 
Test 1 
Test
1 from 2018F Note: in 2018 we spent more time reviewing basic material from CISC102 so this test contains some questions that focus on review material. This year we did less review so we are further ahead with the course content. However, the difficulty level of the questions on this 2018 test is a good indicator of the difficulty of the questions on the test you will write. 
Solutions
(with marking guide) Please review the marking guide as well as the solutions. This will help you understand the things I will look for in your answers. 
Test 2 
Test 3 from 2018F Note: in 2018 modular arithmetic was covered later in the course, and was tested on Test 3 that year. This year we are much further ahead so that year's Test 3 is a pretty good preparation for this year's Test 2. 
Solutions and marking guide 
Test 3 
Practice
Questions Because of the shift in the course material, there is no previous test that matches this year's Test 3. I have created this set of practice questions to help you prepare. If time permits, I will post solutions ... but you should have no trouble answering them! 

Test 4 
*** cancelled *** 

Test 5 
Test 4 from 2018 Test 5 from 2018 Our Test 5 will cover both orderings and graphs. Bear in mind that we are not covering all of the subtopics within these topics this year, so some questions on these two 2018 tests will be outside our scope. For example, the sample Test 5 has questions on planarity and colouring  we won't have time to cover those this year. 
Solutions for Test 4 Solutions for Test 5 Please remember that in 2018 we were able to cover more material! 
Students are responsible for familiarizing themselves with the regulations concerning academic integrity and for ensuring that their actions 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).
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 include but are not
limited to
The preceding text on academic integrity is based on a document written by Prof. Margaret Lamb and is used here with her permission.
Date  Log Entry 
20200104 
2020W website initialized 
20200107 
Test dates corrected  thank you to the student who spotted the
typos 
20200112 
Complete notes for Week 1 posted 
20200118 

20200123 
Sample Test 1 posted 
20200126 

20200127 
Notes for 20200127 posted 
20200202 (Palindrome Day) 
Notes for 20200128 posted 
20200207 
Sample Test 2 posted 
20200209 

20200210 
Notes for 20200210 posted 
20200301 

20200304 
Previous test solutions posted 
20200308 
First notes on orderings posted 
20200314 
All remaining notes on orderings posted 
20200321 
Full notes on graph theory posted (including topics that we won't
have time to cover) 
20200328 
Practice tests posted to prepare for Test 5 
20200331 
Solutions for practice tests posted 