Main Navigation (Top Menu) Secondary Navigation (Side Menu) Page Content

CISC-203* - Winter 2020 Title and Photo Table

CISC-203*

Discrete Mathematics for Computing II

Winter 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

CISC-203 Urgent News

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

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

Announcements

Announcements

Date	Subject	Text

Return to menu

Personnel

Personnel

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 COVID-19 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/

533-6061 (but speaking to me in person is a much better idea) - this phone line is not being monitored during the COVID-19 outbreak.

Office Hours:

Office hours during the COVID-19 outbreak will be held online every day. The times of online office hours will be confirmed on a daily basis.

Monday	TBA
Tuesday	TBA
Wednesday	TBA
Thursday	TBA
Friday	TBA

TA Crew	Name	Email	Office Hours	Picture

	Bodrul Alam	abmb
	Dimitrios Economou	de32
	Xavier McMaster-Hubner	xjem

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 in-class 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: Tests 1, 2, 3, and 4: Your lowest of these four tests is worth 11% of your grade. The other three tests are each worth 23% of your grade. Test 5 is worth 20% of your 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 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.

Return to menu

Schedule

Schedule_Table

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

Return to menu

Course Plan and Record

Record Table

Week 1	Monday January 6 Plan: Introduction Review Notes: Mental Arithmetic	Tuesday January 7 Plan: Review Notes: Jumping Josephus!	Thursday January 9 Plan: Well-Ordered Sets Minimal Counter Example Proofs Notes: Well-Ordered Sets and ... PMCE
Week 2	Monday January 13 Plan: Permutations Notes: PMCE, Composing Functions	Tuesday January 14 Plan: Permutations Notes: Permutations	Thursday January 16 Plan: Permutations Notation Notes: Tremponsitua
Week 3	Monday January 20 Plan: Sample Spaces Events Revised Plan: Finishing Permutations Notes: Mostiaputern	Tuesday January 21 Plan: Independence Conditional Probability Revised Plan: Starting Probability Notes: Time for a new topic? Probably!	Thursday January 23 Plan: Random Variables Expectation Revised Plan: Conditional Probability Notes: Some Conditions May Apply
Week 4	Monday January 27 Plan: Independent Events Notes: Random Variables (which are not random, and not variables)	Tuesday January 28 Plan: Modular Arithmetic Notes: Math a la Mod	Thursday January 30 TEST 1 (Review, Permutations, Probability)
Week 5	Monday February 3 Plan: Modular Arithmetic Notes: Thoroughly Modern Modularity	Tuesday February 4 Plan: Modular Division	Thursday February 6 Plan: Applying Modular Arithmetic Notes: Combined notes for Feb 4 and Feb 6
Week 6	Monday February 10 Plan: Solving Equations Using Modular Arithmetic Notes: Apply as Needed	Tuesday February 11 Plan: Remainder Theorem Revised Plan: Modular Exponentiation	Thursday February 13 TEST 2 (Modular Arithmetic)
*** Reading Week ***
Week 7	Monday February 24 Plan: Cryptography Revised Plan Finish Modular Exponentiation Notes: See February 25	Tuesday February 25 Plan: Cryptography Revised Plan: Remainder Theorem Start of Cryptography Notes: Combined notes for Feb 24 and Feb 25	Thursday February 27 Plan: Cryptography Notes: RSA Cryptography
Week 8	Monday March 2 Plan: Finish RSA Orderings	Tuesday March 3 Plan: Orderings Minima and Maxima First notes on Orderings	Thursday March 5 TEST 3 (Remainder Theorem, Cryptography)
Week 9	Monday March 9 Plan: Orderings	Tuesday March 10 Plan: Orderings	Thursday March 12 Plan: Orderings Notes: More notes on orderings Final notes on orderings
Week 10	Monday March 16 Plan: Introduction to Graph Theory Subgraphs Revised Plan: Class cancelled	Tuesday March 17 Plan: Connectivity Revised Plan: Class cancelled	Thursday March 19 TEST 4 (Orderings) - cancelled
Week 11	Monday March 23 Plan: Complete Graph Theory notes, in advance: Introduction Connectivity Subgraphs Trees Tours and Cycles Cliques and Independent Sets Colouring Isomorphism	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)

Return to menu

Practice Problems

Practice Problems

Topic	Scheinerman	Other Sources

Review		Summer CISC-102 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/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	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

Return to menu

Recommended Readings

Recommended Readings

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	Permutations
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	Graph Theory

Return to menu

Sample Tests

CISC-203* Sample Tests

Test 1	Test 1 from 2018F Note: in 2018 we spent more time reviewing basic material from CISC-102 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!

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

a warning
loss of grades on an assignment or test
failure of a course
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

Change Log

Change Log

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	Complete notes for Week 2 posted Revised marking scheme posted Revised office hours posted
20200123	Sample Test 1 posted
20200126	Complete notes for Week 3 posted Sample Test 1 solutions posted
20200127	Notes for 20200127 posted
20200202 (Palindrome Day)	Notes for 20200128 posted
20200207	Sample Test 2 posted
20200209	Sample Test 2 solutions posted Notes for 20200203 posted Combined notes for 20200204 and 20200206 posted
20200210	Notes for 20200210 posted
20200301	Notes for Week 7 posted Practice problems for Test 3 posted
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

Return to menu

Queen's University is situated on traditional Anishinaabe and Haudenosaunee Territory.