Queen's School of Computing CISC-203* - Fall 2017 Title and Photo Table




CISC-203*

Discrete Mathematics for Computing II

Fall 2017


 
Painting

"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


CISC-203 Urgent News
Internal LinksAnnouncements

Personnel

Course Information

Schedule

Course Plan and Record

Practice Problems

Recommended Readings

Sample Tests

Academic Integrity in CISC 203


External_Links
External Links
Queen's School of Computing
Computing Students' Association
Class Photo Gallery
Learning - Your First Job (Paper by Dr. R. Leamnson) - ESSENTIAL READING
Academic Integrity Statement from Faculty of Arts and Science






Announcements

Announcements
Date Subject Text








Return to menu



Personnel

Personnel
Instructors
Dr. Robin W. Dawes
Robin Dawes
Goodwin 537 
dawes AT cs DOT queensu DOT ca
http://sites.cs.queensu.ca/dawes/
533-6061 (but e-mail is a much better idea)
Office Hours: TBA



TA Crew
Name
Email  
Office Hours
Picture

Bodrul Alam alam@cs.queensu.ca


Diana Balant
dab10@queensu.ca


Krystina Correa
krystina.correa@queensu.ca


Jeffrey Diamond
14jd16@queensu.ca


Hillary Elrick
14he@queensu.ca


Chris Keeler
1ck7@queensu.ca


Sean Nesdoly 13sn50@queensu.ca


David Seekatz
16das4@queensu.ca






Return to menu



Course Information

Course_Information
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 make-up 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 Queen's Homecoming) 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 Disability Services page for students for more information.




Return to menu



Schedule

Schedule_Table
Class Schedule


Monday 8:30 - 9:20

Tuesday 10:30 - 11:20

Thursday 9:30 - 10:20





Test Schedule

Date
Material
Solutions
Test 1
October 5, 2017, 9:30 AM

Solutions
Test 2
October 19, 2017, 9:30 AM

Solutions
Test 3
November 2, 2017, 9:30 AM


Test 4
November 16, 2017, 9:30 AM


Test 5
November 30, 2017, 9:30 AM





Return to menu



Course Plan and Record

Record Table

Week 1
Monday September 11
Plan:
- Introduction
- Review PBC
Tuesday September 12
Plan:
- Review Recurrence Relations
- Review PBI
Notes for Monday and Tuesday
Thursday September 14
Plan:
- Review Functions
- Review Counting Problems
Notes for Thursday
Week 2
Monday September 18
Plan:
- Well-Ordering
- Minimal Counter-example Proofs
Tuesday September 19
Plan: 
- Permutations

Notes for Monday and Tuesday
Thursday September 21
Plan:
- Permutations
- Notation
Notes for Thursday
Week 3
Monday September 25
Plan:
- Sample Spaces
- Events
Tuesday September 26
Plan:
- Independence
- Conditional Probability
Thursday September 28
Plan:
- Random Variables
Notes for the week
Week 4
Monday October 2
Plan:
 - Expectation
Notes on Conditional Probability (we are running a bit behind the plan)
Tuesday October 3
Plan:

Notes on Independent Events and Random Variables
Thursday October 5
Plan: TEST 1

Test and Solutions
Week 5
Monday October 9
Plan:
THANKSGIVING
Tuesday October 10
Plan:
Thursday October 12
Notes for the week
Week 6
Monday October 16
Plan:
Modular Arithmetic
Notes for October 16
Tuesday October 17
Plan:
More Modular Arithmetic
Notes for October 17
Thursday October 19
Plan: TEST 2
Week 7
Monday October 23
Plan:
Exponentiation in Modular Arithmetic
Notes for October 23
Tuesday October 24
Plan:
- More Modularity
Thursday October 26
Plan:
Remainder Theorem
Notes for October 24 and 26
Week 8

Monday October 30
Plan:
 - RSA Cryptography
Notes on RSA
Tuesday October 31
Plan:
 - Orderings
Thursday November 2
Plan:  TEST 3
Week 9
Monday November 6
Plan:
 - More Orderings
Tuesday November 7
Plan:
- Even More Orderings
Thursday November 9
Plan:
- Still Ranting On about Orderings
All notes on orderings to this point
Week 10
Monday November 13
Plan:
Finally done with Orderings
Final notes on orderings
Tuesday November 14
Plan:
- Intro to Graph Theory
Thursday November 16
Plan: TEST 4
Week 11
Monday November 20
Plan:
- Trees
Tuesday November 21
Plan:
- Eulerian Graphs
Thursday November 25
Plan:
- Graph Colouring
Week 12
Monday November 27
Plan:
- Planar Graphs
Tuesday November 28
Plan:
- It's a Mystery
Thursday November 30
Plan: TEST 5




Return to menu



Practice Problems

Practice Problems
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/logic-proof/proof-by-contradiction-examples.html

http://riemann.math.unideb.hu/~kozma/Contradiction-Proof-exercises.pdf

PBI: http://www.mathcentre.ac.uk/resources/uploaded/mathcentre-proof.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
Well-Ordering and Minimal Counter-examples 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




Return to menu



Recommended Readings

Recommended Readings
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


Return to menu



Sample Tests

CISC-203* Sample Tests
Test 1
Test 1 from 2016
Question 5 part b - this was a fair question last year because last year we spent more time on transpositions.  This year I think this would not be a reasonable question. 
Solutions
Please do not look at the solutions until you have done your best to answer the test questions.
Test 2
Test 2 from 2016
Question 1 deals with complexity - we have not covered this material.
Question 3 mentions the variance of a random variable - we have not covered this material.  Question 4 deals with modular arithmetic - we will cover this material next week.
Solutions
Test 3
Test 3 from 2016
Some of the questions involve group theory - we have not covered this material.  Instead we spent several days on exponentiation in modular arithmetic
Solutions
Test 4
Test 4 from 2016
One question deals with lattices.  This material will not be included on Test 4 this year
 
Test 5




Return to menu



Academic Integrity in CISC 203

Academic Integrity Academic integrity is constituted by the five core fundamental values of honesty, trust, fairness, respect and responsibility (see www.academicintegrity.org). These values are central to the building, nurturing and sustaining of an academic community in which all members of the community will thrive. Adherence to the values expressed through academic integrity forms a foundation for the "freedom of inquiry and exchange of ideas" essential to the intellectual life of the University (see the Senate Report on Principles and Priorities).

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.



Return to menu