CISC-102: Discrete Mathematics for Computing I

http://www.cs.queensu.ca/home/akl/102/2022W/2022W.html

(Winter 2022)


Last Modified:


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

Important Notice About Course Delivery in The First Six Weeks Of the 2022 Winter Term

The course will run remotely in the first six weeks of the 2022 Winter Term, with the hope of returning to an in-person format after Reading Week, on February 28, 2022. For further details, concerning lectures and Teaching Assistants office hours, please consult the OnQ page for CISC 102 Winter 2022


Quick Links

Class Hours and Locations
Text
Grading
Outline and Schedule

Course Instructor

Selim Akl
E-MAIL: akl AT cs dot queensu dot ca

Head TA

Jacqueline Heaton
E-MAIL: 16jh12 AT queensu dot ca

Course Teaching Assistants

Teaching assistants will all hold their office hours remotely during the first six weeks of classes (see OnQ page for details).


It is expected that office hours will resume in Goodwin Hall room 248 in the last six weeks.
Teaching assistant office hours will commence on the first week of classes, January 10 - 14, and run until the last week of classes, April 4 - 8.


Name Day Time
Shreyansh Anand Monday 10:00 - 11:30
Shreyansh Anand Tuesday 1:00 - 2:30
Connor Colwill Monday 4:00 - 5:30
Connor Colwill Wednesday 4:00 - 5:30
Reid Moffatt Tuesday 2:30 - 4:00
Reid Moffatt Wednesday 2:30 - 4:00
Mustafa Tariq Tuesday 4:00 - 5:30
Mustafa Tariq Friday 4:00 - 5:30

Class Hours and Locations

Classes will be held remotely in the first six weeks of the 2022 Winter Term (for details, see the OnQ page for the course).

It is expected that classes will be held in the Etherington Hall Auditorium (also know as ETHER AUD), starting March 1, 2022. You can get detailed instructions to find the classroom here.
Tuesday 8:30-9:20
Wednesday 10:30-11:20
Friday 9:30-10:20

Textbooks

Seymour Lipschutz, Marc Lipson, Schaum's Outline of Discrete Mathematics, McGraw-Hill Education (Third Edition, 2007).

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

Both textbooks are available in paperback, and the total cost of the two books is about $100. Electronic copies are also available.

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. Formulate elementary proofs using mathematical induction.
4. Recognize comparative magnitudes of functions such as log(n), n2, 2n.
5. Read and understand some elementary logical proofs.

Grading

Grades will be made up of 5 in-class tests as follows:

1. Test 1 worth 22%
2. Test 2 worth 22%
3. Test 3 worth 22%
4. Test 4 worth 22%
5. Test 5 worth 12%

The tests will be scheduled as follows:

Test 1: Friday, January 28.

Test 2: Friday, February 11.

Test 3: Friday, March 4.

Test 4: Wednesday, March 23.

Test 5: Wednesday, April 6.

Please note: Tests 1 and 2 will be held remotely. For details, you are advised to consult the OnQ page for CISC 102 Winter 2022. There you will find an important message from your Head TA explaining how remote tests will be conducted.

It is expecyted that tests 3, 4, and 5 will be held in our assigned classroom, Etherington Hall Auditorium, during our usual class time. Please try to arrive a bit early so that we can begin the test at the usual start time of the class: 9:30 a.m. for a test scheduled on a Friday, and 10:30 a.m for a test scheduled on a Wednesday.

Calculator Policy

Calculators will not be needed nor will they be permitted at any of the tests held in class.

Cell phone Policy

The use of cell phones during tests is strictly prohibited.

In-person tests will be closed-book

Books, notes, laptops, scrap paper, and so on will not be permitted at any of the in-person tests (that is, tests to be held in class, namely, Test 3, Test 4, and Test 5). Only bring a pencil or pen, and an eraser (if needed).

Grading Method

For each of the five tests in this course you will receive a numerical mark. The final grade you receive for the course will be derived by converting the sum of your five numerical test marks to a letter grade according to the Queen's grade conversion scale shown below.
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

Homework

Homework will be assigned weekly. This work will not be collected for grading; rather, solutions to homework will be done in class. All five tests will be similar to the homework assignments.

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 (Introduction to Computing Science I).

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 Outline of Discrete Mathematics (DM) is 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. DM 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. DM does a good job of presenting this. However, DMEB is better at providing lots of insight from experts. DM 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.
(Note: In what follows, chapter numbers are from DM. 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 following table will be updated as the term progresses.
Week 1
Introduction, Notation, Set Theory, Counting Problems
Please read the lecture notes for week 1, the readings posted for homework, and work on homework 1 so that you finish it by Friday, January 14.
Notes for week 1.
Homework 1
Tuesday, January 11
Sets and subsets.
Wednesday, January 12
Set operations, permutations, and combinations.
Friday, January 14
Solutions to Homework 1
Week 2
Laws of Set Theory, Indexed Sets, Principle of Inclusion and Exclusion
Please read the lecture notes for week 2, the readings posted for homework, and work on homework 2 so that you finish it by Friday, January 21.
Notes for week 2.
Homework 2
Tuesday, January 18
Wednesday, January 19
Review 1
Friday, January 21
Solutions to Homework 2
Week 3
Mathematical Induction
Notes for week 3.
Homework 3
Sample test 1
Tuesday, January 25
Wednesday, January 26
Sample test 1 solutions
Friday, January 28

Test Number 1 (on material up to and including Homework 2)

Week 4
Functions
Notes for week 4.
Homework 4
Tuesday, February 1
Solutions to Homework 3
Wednesday, February 2
Friday, February 4
Solutions to Homework 4
Week 5
Relations.
Notes for week 5.
Homework 5
Sample test 2
Tuesday, February 8
Wednesday, February 9
Sample test 2 solutions
Friday, February 11

Test Number 2 (on material up to and including Homework 3)

Week 6
Chapter 11. Properties of the Integers
Notes for week 6.
Homework 6.
Tuesday, February 15
Wednesday, February 16
Solutions to Homework 5
Friday, February 18
Week 7
Chapter 11. Properties of the Integers
Notes for week 7 same as for week 6.
Homework 6
Sample test 3
Tuesday, March 1
Wednesday, March 2
Sample test 3 solutions
Friday, March 4

Test Number 3 (on material up to and including Homework 5)

Week 8
Congruence Relations
Notes for week 8
Homework 7
Tuesday, March 8
Solutions to Homework 6
Wednesday, March 9


Friday, March 11

Week 9
Chapter 5. Counting, Permutations, Combinations, Binomial Coefficients.
Notes for week 9.
Homework 8
Sample test 4
Tuesday, March 15
Wednesday, March 16
Solutions to Homework 7

Friday, March 18
Sample test 4 solutions
Week 10
Binomial Theorem, Pascal's Triangle, Propositional Logic
Notes for week 10
Homework 9
Tuesday, March 22
Solutions to Homework 8
Wednesday, March 23

Test Number 4 (on material up to and including Homework 7)

Friday, March 25
Week 11
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 )
Sample test 5
Tuesday, March 29
Solutions to Homework 9
Wednesday, March 30

Friday, April 1

Week 12
Wrap up and Review
Tuesday, April 5
Sample test 5 solutions
Wednesday, April 6

Test Number 5 (on material up to and including Homework 9)

Friday, April 8

Mid-Term Reading Week

The Winter Term break will take place on the week of February 21, 2022 to February 25, 2022. There will be no classes in CISC-102 on the following dates: February 22, 23 and 25, 2022.

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: https://www.queensu.ca/studentwellness/accessibility-services

Common Syllabus Information

The web page on standard syllabus elements is part of this syllabus; you are expected to be familiar with everything on that page.

THE QUEEN'S SCHOOL OF COMPUTING IS COMMITTED TO EQUITY, DIVERSITY, INCLUSION, AND INDIGENEITY.