CISC-102: Discrete Mathematics for Computing I

(Winter 2016)


Last Modified:


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

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: Monday 13:00-15:00
Or contact me after class or by e-mail appointment.

Course Teaching Assistants

Hassan Hanino

GOODWIN HALL Room 241
E-MAIL: 13hah2 AT queensu dot ca
OFFICE HOURS: Monday 15:00-16:00 and Friday 13:00-14:00

Joey Sun

GOODWIN HALL Room 241
E-MAIL: 14cyjs AT queensu dot ca
OFFICE HOURS: Monday 17:30-18:30 and Friday 14:00-15:00

Class Hours and Locations

Tuesday 9:30-10:30 Ellis Hall Room 324
Wednesday 8:30-9:30 Ellis Hall Room 324
Friday 10:30-11:30 Ellis Hall Room 324

Text

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

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

I will use both of these books. 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.
Four in class midterm quizzes, each worth 17%, total: 68%
Final exam: 32%
The quizzes will be scheduled as follows:
Quiz 1: Tuesday, January 26.
Quiz 2: Tuesday, February 9.
Quiz 3: Tuesday, March 8.
Quiz 4: Tuesday, March 29.
Please note: Quizzes will be held in Dupuis Hall room 215. Please try to arrive a bit early so that we can start the quiz at 9:30 sharp. You can find directions here.
Please make every effort to be present for the midterm quizzes. It may be that you will be forced to miss a quiz for health, or other legitimate reasons. With my permission, you may miss up to two of the quizzes. If you miss quizzes then the marking scheme will be revised for you as follows:
1 missed - 3 quizzes 20% each and 40% final.
2 missed - 2 quizzes 25%, and 50% final.

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 (in the order that I will be presenting them). The amount of time to be spent on each topic is approximate. Chapter numbers are from SN. Topics from DMEB will be selected as the course progresses.

Sets (2 weeks) together with some logic. (Chapter 1, and Chapter 4)
Relations (2 weeks)(Chapter 2)
Functions (2 weeks)(Chapter 3)
Integers and Induction (3 weeks)(Chapter 11)
Introduction to Mathematical Discourse (Chapter 4)
The topics covered this term will be similar to last term (Fall 2015), but may differ slightly at times. You can see a fairly detailed record on last term's web page: http://research.cs.queensu.ca/home/daver/102/2015Fall/
The following table will be updated as the term progresses.
Week 1
Introduction, Notation, Set Theory, Counting Problems
Tuesday, January 4
It would be a good idea to check out the homework posted under Friday's lecture. I will go over solutions to Homework 1 on January 15.
Lecture 1

Thursday, January 7
Lecture 2

Friday, January 8
Lecture 3
Homework 1

Week 2
More Notation, Set Theory, Counting Problems
Tuesday, January 12
Permutations, Combinations, More set operations.
Lecture 4
Thursday, January 14
Lecture 5
Friday, January 15
Homework 2
Solutions Homework 1

Week 3
Principle of Inclusion and Exclusion, Mathematical Induction
Tuesday, January 19
Lecture 6
Thursday, January 21
Lecture 7
Friday, January 22
Homework 3
Solutions Homework 2
Week 4
Product sets, Relations, Functions
Tuesday, January 26
QUIZ #1 examining material from homework 1 and 2. The quizzes will be held in Dupuis Hall room 215. Please try to arrive a bit early so that we can start the quiz at 9:30 sharp.
Thursday, January 28
Lecture 8
Friday, January 29
Homework 4
Solutions to Quiz #1
Solutions Homework 3
Week 5
Properties of the Integers
Tuesday, February 2
Lecture 9
Thursday, February 4
Lecture 10
Friday, February 5
Homework 5
Solutions Homework 4
Week 6
Integers, Primes, G.C.D., L.C.M.
Tuesday, February 9
QUIZ #2 examining material from homework 3 and 4.
Thursday, February 11
Lecture 11
Friday, February 12
Homework 6.
Solutions Homework 5.
Solutions Quiz 2.
READING WEEK
Tuesday, February 16
Thursday, February 18
Friday, February 19
Week 7
GCD, LCM, Congruence Relations, Counting
Tuesday, February 23
Lecture 12
Thursday, February 25
Lecture 13
Friday, February 26
Homework 7
Solutions Homework 6
Week 8
Counting, Binomial coefficients
Tuesday, March 1
Lecture 14
Thursday, March 3
Lecture 15
Friday, March 4
Homework 8
Solutions Homework 7
Week 9
Proofs using counting arguments.
Tuesday, March 8
QUIZ #3 examining material from from homework 5, 6, and 7.
Thursday, March 10

Lecture 16
Friday, March 11
Homework 9
Solutions Homework 8
Solutions to Quiz #3

Week 10
Propositional Logic
Tuesday, March 15
Lecture 17
Thursday, March 17
Lecture 18
Friday, March 18
Homework 10
Solutions Homework 9
Week 11
Propositional Logic, Methods of Mathematical Proof
(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 )
Tuesday, March 22
Lecture 19
Thursday, March 24 Friday, March 25
Solutions Homework 10
Week 12
Wrap up and Review
Tuesday, March 29
QUIZ #4 examining material from from Homework 8, 9, 10.
Thursday, March 30
Final review
2014 Final Exam
Solutions to Quiz #4

Friday, April 1
Final review

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

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 (see Academic Integrity ), 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.

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/