CISC-102: Discrete Mathematics for Computing I

(Winter 2020)


Last Modified:


Education is not the filling of a pail, but the lighting of a fire. Plutarch.

There will be no more updates to this webpage. Please check announcements on OnQ for all further information.

Quick Links

Class Hours and Locations
Text
Grading
Outline and Schedule

Course Instructor

David Rappaport
GOODWIN HALL Room 532
E-MAIL: daver AT cs dot queensu dot ca
OFFICE HOURS: Tuesday 12:30-2:30
Or contact me after class or by e-mail to make an appointment.

Course Teaching Assistants

Teaching assistants will all hold their office hours in Goodwin Hall room 230. TA office hours will begin on Monday January 13 and run until April 3 March 13. There will be no TA office hours during reading week February 17-21.
The following table lists all the teaching assistants and their office hours.

Name Day Time
Sam McPhail Monday 10:00 - 12:00
Catherine Wu Monday 14:30 - 16:30
Feiyi Yang Monday 16:30 - 18:30
Anna Chulukov Tuesday 10:30 - 12:30
Rebecca Hisey Tuesday 14:30 - 16:30
V.S. Kartik Srinivasan Tuesday 16:30 - 18:30

Class Hours and Locations

Classes will be held in the Dupuis Hall Auditorium. You can get detailed instructions to find the class here.
Tuesday 8:30-99:30
Wednesday 10:30-11:30
Friday 9:30-10:30

Text

(required) Marc Lipson, Seymour Lipschutz, Schaum's Outline of Discrete Mathematics, McGraw-Hill Education (2009).

(optional) L. Lovász, J. Pelikán, K. Vesztergombi, Discrete Mathematics Elementary and Beyond, Springer (2003).

I use both of these books, but you should view the Schaum's notes as the only required book. They are both available in paperback, and the total cost of the two books is well under $100.

Intended Student Learning Outcomes

To complete this course students will demonstrate their ability to:
1. Understand standard Mathematics notation used in the field of Computing.
2. Recognize the difference between a proof and a counter example.
3. Able to formulate elementary proofs using mathematical induction.
4. Recognize comparative magnitudes of functions such as log(n), n2, 2n.
5. Ability to read and understand some elementary logical proofs.

Grading

Grades will be made up of midterm quizzes and a final.
The quizzes will be scheduled on 2 Wed. during our normal class time from 10:30-11:20 as follows:
Quiz 1: Wednesday, January 29.
Quiz 2: Wednesday, February 26.
Quiz 3: Wednesday, March 25.
Please make every effort to be present for the midterm quizzes. However, writing any of the quizzes is up to you, all quizzes are optional. At the end of the term I will tally three grades for everyone in the class as follows.
1. 2 quizzes 25% each and 50% Final.
2. Best single quiz grade 25% and 75% Final
3. 100% Final.
You will then get the maximum of the grades 1, 2, or 3, with the exception that if you get 49% or less on the final exam, then that will be your grade.

Calculator Policy

Calculators, scrap paper, or anything other than pencils, pens, and/or erasers, will not be needed nor will they be permitted at any of the quizzes or the final exam.

Grading Method

All components of this course will receive numerical percentage marks. The final grade you receive for the course will be derived by converting your numerical course average to a letter grade according to the Queen's grade conversion scale.
Numeric Range Letter Grade GPA
90-100 A+ 4.3
85-89 A 4.0
80-84 A- 3.7
77-79 B+ 3.3
73-76 B 3.0
70-72 B- 2.7
67-69 C+ 2.3
63-66 C 2.0
60-62 C- 1.7
57-59 D+ 1.3
53-56 D 1.0
50-52 D- 0.7
0-49 F 0

Location and Timing of Final Examinations

As noted in Academic Regulation 8.2.1, "the final examination in any class offered in a term or session (including Summer Term) must be written on the campus on which it was taken, at the end of the appropriate term or session at the time scheduled by the Examinations Office." The exam period is listed in the key dates prior to the start of the academic year in the Faculty of Arts and Science Academic Calendar and on the Office of the University Registrar's webpage. A detailed exam schedule for the Fall Term is posted before the Thanksgiving holiday; for the Winter Term it is posted the Friday before Reading Week, and for the Summer Term the window of dates is noted on the Arts and Science Online syllabus prior to the start of the course. Students should delay finalizing any travel plans until after the examination schedule has been posted. Exams will not be moved or deferred to accommodate employment, travel /holiday plans or flight reservations.

Homework

Homework will be assigned weekly. This work will not be collected for grading, rather, solutions to homework will be done in class. There will be four midterm quizzes that will be directly based on the homework assignments. Please see the grading scheme above.

Course Description

Calendar Description of CISC-102

Introduction to mathematical discourse and proof methods. Sets, functions, sequences, and relations. Properties of the integers. Induction. Equivalence relations. Linear and partial orderings.

This course is a direct prerequisite to CISC-203/3.0 (Discrete Mathematics for Computing II) CISC-204/3.0 (Logic in Computing) and a co- or pre-requisite to CISC-121/3.0.

This course is required in all Computing programs except COMA.

Course Syllabus

Mathematics plays an important role in many aspects of computer science. This course sets the stage for the type of mathematics that computer scientists rely on to produce effective software solutions. This course can be viewed as a language course, that is, you will be learning the language of mathematics. I will follow two books that cover similar material in distinctly different ways. Schaum's Notes (SN) are an excellent resource for a well organized source of course material. Discrete Mathematics Elementary and Beyond (DMEB) provides colour and motivation for the same material.
The course will consist of the following elements:

Notation and definitions and notational conventions: Using the language learning analogy this is equivalent to learning vocabulary and grammar and colloquialisms. SN will be the main source for this material.

Tricks and techniques: Sticking with the language learning analogy, this is equivalent to learning writing styles, problem solving methods. SN does a good job of presenting this. However, DMEB is better at providing lots of insight from experts. SN is a great guide for students, whereas DMEB comes straight from the experts in a more informal but also more insightful way.

Practice, practice, practice: This is the key to success. Doing exercises is the only way to absorb the material properly. You can't learn to play a sport, play an instrument, or how to be a good writer solely by reading a book. This material is no different.

Outline and Schedule

Topics. Chapter numbers are from SN. Topics from DMEB will be selected as the course progresses.

Sets (Chapter 1)
Relations (Chapter 2)
Functions (Chapter 3)
Logic (Chapter 4)
Counting Techniques (Chapter 5 and 6)
Integers and Induction (Chapter 11)
Patterns of Proof (PDF Handout) (Chapter 4)
The topics covered this term will be similar to last term (Fall 2018), but may differ slightly at times. You can see a fairly detailed record on last term's web page: here
The following table will be updated as the term progresses.
Week 1
Introduction, Notation, Set Theory, Counting Problems
Notes for week 1.
Tuesday, January 7
Please read the lecture notes for week 1, the readings posted for homework, and work on homework 1 so that you finish it by next Tuesday.
Homework 1


Wednesday, January 8
Friday, January 10

Week 2
Laws of Set Theory, Indexed Sets, Principle of Inclusion and Exclusion
Notes for week 2.
Homework 2
Tuesday, January 14
Solutions Homework 1
Wednesday, January 15
We finished up the lecture notes for week 1 today. We will get an early start on the week 3 notes on Friday.
Friday, January 17

Week 3
Mathematical Induction
Notes for week 3.
Homework 3
Tuesday, January 21
Solutions Homework 2
Wednesday, January 22
Friday, January 24
Week 4
Functions
Notes for week 4.
Homework 4
Tuesday, January 28
Solutions Homework 3
Wednesday, January 29
Quiz 1 based on homework 1, 2 and 3.
Friday, January 31
Week 5
Relations
Notes for week 5.
Homework 5
Tuesday, February 4
Solutions to Quiz #1
Solutions Homework 4
Wednesday, February 5
Friday, February 7
Week 6
Integers, Primes
Notes for week 6.
Homework 6
Tuesday, February 11
Solutions Homework 5.
Wednesday, February 12
Friday, February 14
READING WEEK
Tuesday, February 18
READING WEEK No Class.
Wednesday, February 19
READING WEEK No Class.
Friday, February 21
READING WEEK No Class.
Week 7
Congruence Relations, Counting.
Notes for week 7.
Tuesday, February 25
I will go over solutions to homework 6 today. Solutions Homework 6
Wednesday, February 26
Quiz 2 based on homework 4, 5, and 6.
Friday, February 28
Week 8
Principles of Counting
Notes for week 8.
Homework 7.
Tuesday, March 3
Solutions Quiz 2
Wednesday, March 4
Friday, March 8

Week 9
Binomial Coefficients. Fibonacci numbers.
Notes for week 9.
Notes for week 9 addendum.
Homework 8
Tuesday, March 10
Solutions Homework 7
Wednesday, March 11

Friday, March 13
Week 10
No lectures this week, and no further in person interaction, including the final exam, for the end of the term.
Tuesday, March 17
Wednesday, March 18
Friday, March 20
Week 11
There will be no in person lectures. I will be providing some video support for the lecture notes. Stay tuned for more information.
Propositional Logic
Notes for week 10.
Homework 9
Solutions Homework 8
Solutions Homework 8 Video. You may have to turn up the volume.
Tuesday, March 24
Video supporting lecture notes for week 10 Part 1. You may have to turn up the volume.
Wednesday, March 25
Quiz 3 has been cancelled.
You can practice with the quiz from last year. Please note, the correct multiple choice answer is underlined. Solutions to Quiz #3

Friday, March 27
Week 12
There will be no in person lectures. I will be providing some video support for the lecture notes. Stay tuned for more information.
Methods of Mathematical Proof
Notes for week 11.
(Please see Patterns of Proof Tom Leighton, and Marten Dijk. 6.042J Mathematics for Computer Science, Fall 2010. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed 18 Nov, 2015). License: Creative Commons BY-NC-SA ) Wrap up and review.
Tuesday, March 31
Try the 2014 final exam for practice. Solutions are provided in a separate file.
2014 Final Exam
Wednesday, April 1

Friday, April 3
2014 Final Exam Solutions

Accessibility Statement

Queen's is committed to an inclusive campus community with accessible goods, services, and facilities that respect the dignity and independence of persons with disabilities. This webpage is available in an accessible format or with appropriate communication supports upon request.
Please contact:
The Equity Office
B513 Mackintosh-Corry Hall
Phone: (613) 533-2563
Fax: (613) 533-2031
E-mail: equity@queensu.ca

Academic Integrity

Queen's students, faculty, administrators and staff all have responsibilities for supporting and upholding the fundamental values of academic integrity. Academic integrity is constituted by the five core fundamental values of honesty, trust, fairness, respect and responsibility (see www.academicintegrity.org) and by the quality of courage. These values and qualities 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. Students are responsible for familiarizing themselves with and adhering to the regulations concerning academic integrity. General information on academic integrity is available at Integrity@Queen's University, along with Faculty or School specific information. Departures from academic integrity include, but are not limited to, plagiarism, use of unauthorized materials, facilitation, forgery and falsification. Actions which contravene the regulation on academic integrity carry sanctions that can range from a warning, to loss of grades on an assignment, to failure of a course, to requirement to withdraw from the university.

Accommodation Statement

Queen's University is committed to achieving full accessibility for persons with disabilities. Part of this commitment includes arranging academic accommodations for students with disabilities to ensure they have an equitable opportunity to participate in all of their academic activities. If you are a student with a disability and think you may need accommodations, you are strongly encouraged to contact Student Wellness Services (SWS) and register as early as possible. For more information, including important deadlines, please visit the Student Wellness website at: http://www.queensu.ca/studentwellness/accessibility-services/