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

449 views59 pages

Queen's University

CISC 102

Discrete Mathematics for Computing I

Quiz

Fall 2018

Prof. D. Rappaport

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

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