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

449 views59 pages
5 Nov 2018
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.

Already have an account? Log in
Unlock document

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

Already have an account? Log in
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
an applicant to Google.
#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.

Already have an account? Log in
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.

Already have an account? Log in

Get access

Grade+
$10 USD/m
Billed $120 USD annually
Homework Help
Class Notes
Textbook Notes
40 Verified Answers
Study Guides
1 Booster Class