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

CISC-203*

Discrete Mathematics for Computing II

Fall 2016


 PHP
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 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
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
Note-Taker Request
Please consider volunteering to be a note-taker for another student in this class.  See this link for more information.





Return to top



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


Matthew Holden 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





Return to top



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 we will create a modified marking scheme for you.  Sports events, family get-togethers 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.




Return to top



Schedule

Schedule_Table
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





Return to top



Course Plan and Record

Record Table

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:
- Well-Ordering
- Minimal Counter-example 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




Return to top



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

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




Return to top



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 top



Sample Tests

CISC-203* Sample Tests
Test 1
Test 1 from 2015
Notes:  The sample contains questions about Zb and about base-2 notation, which we have not covered in 2016's version of CISC-203.  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 CISC-203 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 CISC-203 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 CISC-203 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.


Return to top



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 top