# CISC 102 Study Guide - Fall 2018, Comprehensive Quiz Notes - Complex Instruction Set Computing, Mathematical Induction, Integer

449 views59 pages
5 Nov 2018
School
Department
Course
Professor
Queen's University
CISC 102
Discrete Mathematics for Computing I
Quiz
Fall 2018
Prof. D. Rappaport
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 59 pages and 3 million more documents.

Unlock document

This preview shows pages 1-3 of the document.
Unlock all 59 pages and 3 million more documents.

CISC 102
September 6, 2018
PROFESSOR
David Rappaport
daver@cs.queensu.ca
Goodwin G-532
Office hours: Tues 1:30-3:30
HOMEWORK
Weekly homework will be solved in class on due date.
Homework is handed in, not graded.
Quizzes and final exam are based on homework questions.
ASSESSMENT
60% quizzes (4 x 15%)
40% final
If you miss a quiz, the weight of the final increases by 15%
Attendance will not be taken but it is recommended to go
MOTIVATION
According to a recent poll, the preferred employer is Google. Professor Rappaport has interview tips from
#1 tip Algorithm Complexity: You need to know Big-O. If you struggle with
basic big-O complexity analysis, then you are almost guaranteed not to get
hired.
Mastering discrete mathematics is the direct pre-requisite to mastering
algorithms and complexity.
You should view this course as a language course. You will be learning the
language of mathematics and computing.
KEY EQUATION
The equation consists of the most important concepts in mathematics:
Numbers
-0, 1 (integers)
-π, e (irrational real numbers)
-I (a complex number)
Operations
-+ x and the exponentiation (exp. function)
And the relation =
THE PERFECT INTRODUCTORY PROBLEM - COUNTING HAND SHAKES
Alice is having a birthday party at her house, and has invited Bob, Carl, Diane, Eve, Frank, and George.
They all shake hands with each other.
Q: How many handshakes?
George says, “I know the answer and I can prove it to you. There are 7 of us, so I shake hands with 6
other people. That’s also true for everyone else. So the total number of hand shakes is 6 x 7 = 42.”
Note: Big-O
notation is a type of
asymptotic notation.
Describes limiting
behaviour of a fn
that tends towards a
value/infinity.
find more resources at oneclass.com
find more resources at oneclass.com
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 59 pages and 3 million more documents.

CISC 102
September 6, 2018
Frank says, “I have another way of working this out. Suppose there’s only two of us, just George and I.
That’s 1 handshake. For 3 of us, Eve, Frank, and George, we have:
E and F shake hands
E and G shake hands
F and G shake hands
And for 4 of us, Diane, Eve, Frank, and George, we have:
D and E shake hands
D and F shake hands
D and G shake hands
E and F shake hands
E and G shake hands
F and G shake hands. 6 handshakes.
I see the pattern (3 x 2) / 2 = 3, (4 x 3) / 2 = 6.
So, with 7 of us, the correct answer is (6 x 7) / 2 = 21
Who’s right?
Note: this problem
was not solved
but rather given to
us as something
to get us thinking.
We use it again in
the next example
to further our
understanding of
a certain concept.
find more resources at oneclass.com
find more resources at oneclass.com
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 59 pages and 3 million more documents.