🏷️ LIMITED TIME OFFER: GET 20% OFF GRADE+ YEARLY SUBSCRIPTION →

Verified Documents at Queen's University

Discrete Mathematics for Computing I
Queen's University
Verified Notes

Browse the full collection of course materials, past exams, study guides and class notes for CISC 102 - Discrete Mathematics for Computing I at Queen's University verified by our …

PROFESSORS

All Professors

D. Rappaport

Verified Documents for D. Rappaport

Class Notes

Taken by our most diligent verified note takers in class covering the entire semester.

CISC 102 Lecture Notes - Lecture 1: Complex Instruction Set Computing, Discrete Mathematics, Big O Notation

Weekly homework will be solved in class on due date. Quizzes and final exam are based on homework questions. If you miss a quiz, the weight of the fina

CISC 102 Lecture Notes - Lecture 2: Tranche, Complex Instruction Set Computing, Null Set

We convert the hand shake problem into an official math problem using proper notation. The basic building block will be the set. A set is a collection

CISC 102 Lecture Notes - Lecture 3: Null Set, Empty Set, Complex Instruction Set Computing

Homework of the week is to be taken up thursday. Let a and b be two sets, where every element of a is also an element of b. For example: a = {red, blac

CISC 102 Lecture Notes - Lecture 4: Empty Set, Symmetric Difference, Complex Instruction Set Computing

**disclaimer** this note is shorter, as the majority of the class was spent taking up the weekly homework questions. There were no additional notes to

CISC 102 Lecture Notes - Lecture 5: Infinite (Band), Complex Instruction Set Computing, Empty Set

Idempotent laws (1b) a a = a. Associative laws (2b) (a b) c = a (b c) Commutative laws (3b) a b = b a. Distributive laws (4b) a (b c) = (a b) (a c) Ide

CISC 102 Lecture Notes - Lecture 6: Complex Instruction Set Computing, Binary Number

Humans use this system (base 10), using decimal digits 0,1,2,3,4,5,6,7,8,9. It"s equal to: 2 x 103 + 0 x 102 + 1 x 101 + 7 x 100. This can also be figu

CISC 102 Lecture Notes - Lecture 7: Red Guitars, Complex Instruction Set Computing

Ginger owns a music store where all instruments are either red or a guitar (if not red). There are 15 red instruments and 18 guitars. A venn diagram ca

CISC 102 Lecture Notes - Lecture 8: Mathematical Induction, Complex Instruction Set Computing

A proposition is defined as a statement that is either true or false (e. g. sky is blue, earth is flat). In this course we"ll make declarative statemen

CISC 102 Lecture Notes - Lecture 9: Mathematical Induction, Complex Instruction Set Computing

Think of a sequence of dominoes going on forever. All fall, so long as: domino 1 falls (p(1)) If the kth domino falls, it knocks over the k+1st domino.

CISC 102 Lecture Notes - Lecture 10: Mathematical Induction

Today, we went through the solutions to this week"s homework (week 3), so the note was very short. Solutions to weekly homework are always posted on th

CISC 102 Lecture Notes - Lecture 11: Natural Number, Complex Instruction Set Computing, Modular Arithmetic

The sum of the first n odd numbers is n2. Testing some small values of n: n = 1 (1=12), n = 2 (1 + 3 = 4 = 22), n = 3 (1 + 3 + 5 = 9 = 32) Not a proof,

CISC 102 Lecture Notes - Lecture 12: Mathematical Induction, Injective Function, Bijection

We can define n! and (n+1)! using these explicit iterative formulae: n! This is a recursive definition of the factorial function. The factorial functio

CISC 102 Lecture Notes - Lecture 13: Complex Instruction Set Computing

CISC 102 Lecture Notes - Lecture 14: Cartesian Coordinate System, Complex Instruction Set Computing, Cross Product

Functions: mappings from one set to another w specific added properties. Note: a fn has to map all elemtns of the domain set to a single element in the

CISC 102 Lecture Notes - Lecture 15: Natural Number

Relation, r, is reflexive if (a,a) r for all a a. Relation, r, is symmetric if when (a1, a2) r then (a2, a1) . Relation, r, is antisymmetric if when (a

CISC 102 Lecture Notes - Lecture 16: Taipei 101, Partially Ordered Set, Complex Instruction Set Computing

Relation, r, is a partial order if r is reflexive, antisymmetric, and transitive. Partial order relations can be used when we want to compare and order

CISC 102 Lecture Notes - Lecture 18: Euclid, Coprime Integers, Complex Instruction Set Computing

Consider any two interers, a,b, at least one being non-zero. If we list the pos"ve divisors in numeric order from smallest to largest, we"d have two li

CISC 102 Lecture Notes - Lecture 19: Becquerel, Complex Instruction Set Computing, Integer Factorization

CISC 102 Lecture Notes - Lecture 20: Complex Instruction Set Computing, Public-Key Cryptography, Binary Logarithm

These ideas lead to the following theorem that is given without proof: Let a,b be non-zero integers, then gcd(a,b) x lcm(a,b) = |ab|. Factoring an inte

CISC 102 Lecture Notes - Lecture 24: Lemon Meringue Pie, Ice Cream, Complex Instruction Set Computing

How many subsets are there of a set w n elements. Counting problems are useful to determine resources used by an algorithm (i. e. time & space). Le

CISC 102 Lecture Notes - Lecture 25: Minestrone, Complex Instruction Set Computing, Pigeonhole Principle

Suppose we have the same mains and deserts as mentioned in the previous lecture. We can also choose a soup or salad, where the soups are: Gives a total

CISC 102 Lecture Notes - Lecture 26: Pigeonhole Principle, Pigeon Hole (Band), Complex Instruction Set Computing

CISC 102 Lecture Notes - Lecture 27: 5,6,7,8, Complex Instruction Set Computing, Product Rule

Some of the examples being covered will make use of the standard 52 deck of playing cards as shown below. There are 4 suits (clubs, spades, hearts, dia

CISC 102 Lecture Notes - Lecture 28: Complex Instruction Set Computing

Suppose we want to count the num of different 5-card poker hands. Thus, we are interested in the num of ways of selecting 5 from 52 without regard to t

CISC 102 Lecture Notes - Lecture 29: Complex Instruction Set Computing, Bijection, Binomial Coefficient

Suppose we have a peculiar deck of cards so that suits are omitted (clubs, diamonds, hearts, spades). We have 4 identical aces, 4 identical 2s, so on,

CISC 102 Lecture Notes - Lecture 30: Complex Instruction Set Computing, Disjoint Sets

An easy way to calculate a table of binomial coefficients was recognized centuries ago by mathematicians in multiple areas of the world. In the west, t

CISC 102 Lecture Notes - Lecture 31: Proposition, Propositional Calculus, Complex Instruction Set Computing

, for all natural numbers n 1. Now, we observe that the sum is a special case of lemma 2, where m = n, and k = n, as follows below: Philosopher gottfri

CISC 102 Lecture Notes - Lecture 32: Idempotence, Complex Instruction Set Computing, Distributive Property

Tautology: logical expression always true for all values of its variables. Contradiction: logical expression always false (never true) for all values o

CISC 102 Lecture Notes - Lecture 33: Complex Instruction Set Computing, Logical Connective, Truth Table

Typically, statements in mathematics are in the form: if p then q . In all examples below, assume variables are natural numbers. If a b and b a then a

CISC 102 Lecture Notes - Lecture 34: Logical Biconditional, Complex Instruction Set Computing, Truth Table

Shorthand for the pair of statements is used. If a b and b a then a = b. If a = b then a b and b a. Gives: a = b if and only if a b and b a. Which can

CISC 102 Lecture Notes - Lecture 35: Logical Consequence, Complex Instruction Set Computing

Consider expression below: p is true and p implies q is true, as a consequence we can deduce that q must be true. What one means by a valid argument ca

CISC 102 Lecture Notes - Lecture 36: Complex Instruction Set Computing, Propositional Function

We can check validity of the above argument via the use of a truth table to see if the expression is a tautology. p. Let"s look at another logical argu

CISC 102 Lecture Notes - Lecture 37: Propositional Function, Universal Quantification, Complex Instruction Set Computing

P(x): x + 2 > 7; tp = {x : x > 5} P(x): x + 5 < 3; tp = . P(x): x + 5 > 1; tp = . A quantified proposition using the propositional function

CISC 102 Lecture Notes - Lecture 38: Complex Instruction Set Computing, Rule Of Inference, Modus Ponens

An axiom is a statement or proposition that is regarded as being established, accepted, or self-evidently true. Math is a system humans created, which