CS182Final Study Guide PDF

Preview

Summary

Final Study Guide for CS 182 by Ananth Grama...

Description

CS 18200 Study Guide

Table of Contents Break Up Problem-wise for the final Chapter 1: Logic and Proofs Propositions Truth Tables Equivalences/DeMorgan’s Laws Predicates and Quantifiers Nested Quantifiers Rules of Inference Proofs Chapter 2: Sets, Functions, Sequences, Sums, Matrices Set/Set Operations/Cardinality Functions Sequences Sums Matrices Chapter 3: Algorithms Big O Big Ω Big Θ Chapter 4: Number Theory and Crypto Divisibility Modulus Base Conversion Multiplication in Different Bases Modular Arithmetic/Integer Math Modular Exponentiation Finding GCD Chinese Remainder Theorem Crypto/RSA Chapter 5: Induction and Recursion Induction Strong Induction Recursive Functions Recursive Algorithms Program Correctness Chapter 6: Counting Basic Counting Pigeonhole Principle Permutations and Combinations Binomial Coefficients and Identities

Generalized Perm. and Comb. Chapter 7: Discrete Probability Basic Concepts Probability Theory Bayes’ Theorem Expected Value and Variance Post-Chapter 7: Regular Expressions and Finite State Automata Regex FSA Author’s Note: To whom it may concern, you may be wondering why we chose to write this. We have two reasons. First, we firmly believe that you do not truly understand the content unless you can teach it to someone else, so we’re trying to teach the concepts of this class to the entire class. Second, we love to learn, and we love to see others learn. Grades are below learning on our list of priorities, so our goal is that everyone in this class is able to pass with a firm understanding of everything taught. We hope to also pass this philosophy onto you as the reader. Thank you for reading, and good luck on the final. Special Thanks: Rocky Villano, Kevin Tee

Break Up Problem-wise for the final ❖ 4 Questions: ➢ Logic and Proofs ➢ Sets, Functions, Sequences, Sums, Matrices ➢ Algorithms, Big O, Big Ω, Big Θ ❖ 4 Questions: ➢ Number Theory and Crypto ➢ Induction, Strong Induction, Recursion ➢ Counting ❖ 1 Question: ➢ Discrete Probability ❖ 1 Question: ➢ Regex and Finite State Automata ■ Deterministic FA ■ Non-Deterministic FA

❖ NOTE: Some parts of the guide have blanks. It is just white text bc they have answers to some of the problems in case you would like to try and solve the problems before hand and check your answers. If you want to see the answers, highlight the blanks with your cursor. ❖ Chapter 1: Logic and Proofs ➢ Propositions

■ ■ ■ ■

A statement that is either true or false Propositions can be represented by variables such as p or q Not p or ￢p is defined as It is not the case that p Conjunction or p ⋀ q is defined as p ⋀ q is true when both p and q are true

■

Disjunction or p ∨ q is defined as p ∨ q is true when p or q is true

■

Implication or p → q is defined as p → q is false when p is true and q is false. Other than that implication is true ● If p, then q ● If p, q ● p is sufficient for q ● q if p ● q when p ● A necessary condition for p is q ● q unless ￢p ● p implies q

● ● ● ● ●

p only if q A sufficient condition for q is p q whenever p q is necessary for p q follows from p

■

Converse of Implication ● Implication: p → q ● Converse: q → p

■

Contrapositive of Implication ● Implication: p → q ● Contrapositive: ￢q → ￢p ● Only one of the three that has the same truth value as the normal Implication

■

Inverse of Implication ● Implication: p → q ● Inverse: ￢p → ￢q

■

Biconditional or p ↔ q: which is defined as p implies and is implied by q. ● p is necessary and sufficient for q ● If p then q, and conversely ● p iff q

■

Precedence of operators ● Not ● And ● Or ● Implication ● Biconditional ➢ Truth Tables ➢ Equivalences/DeMorgan’s Laws

■

Identity Laws ● p∧T ≡ p ● p⋁F ≡ p

■

Domination Laws ● p⋁T ≡ T ● p∧F ≡ F

■

Idempotent Laws ● p⋁p ≡ p ● p∧p ≡ p

■

Double Negation Laws ● ￢(￢p) ≡ p

■

Commutative Laws

● p⋁q ● p∧q

≡ q⋁p ≡ q∧p

■

Associative Laws ● (p ⋁ q) ⋁ r ≡ p ⋁ (q ⋁ r) ● (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)

■

Distributive Laws ● p ⋁ (q ∧ r) ● p ∧ (q ⋁ r)

≡ (p ⋁ q) ∧ (p ⋁ r) ≡ (p ∧ q) ⋁ (p ∧ r)

■

De Morgan’s Laws ● ￢(p ∧ q) ≡ ￢p ⋁￢q ● ￢(p ⋁ q) ≡ ￢p ∧ ￢q

■

Absorption Laws ● p ⋁ (p ∧ q) ● p ∧ (p ⋁ q)

≡ p ≡ p

■

Negation Laws ● p ⋁ ￢p ≡ T ● p ∧ ￢p ≡ F

■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■

p→q ≡ ￢p∨q p→q≡ ￢q→ ￢p p∨q≡ ￢p→q p∧q≡ ￢(p→ ￢q) ￢(p→q)≡p∧ ￢q (p→q)∧(p→r)≡p→(q∧r) (p→r)∧(q→r)≡(p∨q)→r (p→q)∨(p→r)≡p→(q∨r) (p→r)∨(q→r)≡(p∧q)→r p↔q≡(p→q)∧(q→p) p↔q≡ ￢p↔ ￢q p↔q≡(p∧q)∨(￢p∧ ￢q)

￢(p↔q)≡p↔ ￢q ➢ Predicates and Quantifiers

■ ■

For all: ∀

■

Modus Ponens p p→q

There exists: ∃ ➢ Nested Quantifiers ➢ Rules of Inference

__________ ∴q

■

Modus Tollens ￢q p→q __________ ∴ ￢p

■

Hypothetical Syllogism p→q q→r __________ ∴ p→r

■

Disjunctive Syllogism p∨q ￢p __________ ∴q

■

Addition p __________ ∴p∨q

■

Simplification p∧q __________ ∴p

■

Conjunction p q __________ ∴p∧q

■

Resolution p∨q ￢p ∨ r __________ ∴q∨r

■

For Quantified Statements ● Universal Instantiation ∀x P( x ) __________ ∴ P( c ) ● Universal Generalization P( c ) for an arbitrary c

__________ ∴ ∀x P( x ) ● Existential Instantiation ∃x P( x ) __________ ∴ P( c ) ● Existential Generalization P( c ) for an arbitrary c __________ ∴ ∃x P( x ) ➢ Proofs

■ ■ ■ ■ ■

Direct: prove p→q Contradiction: prove ￢p → (r ∧ ￢r) Contraposition: prove ￢q→￢p Exhaustive/Cases: show all the cases that can happen Existence: prove ∃x P( x ) where P is the predicate and find an a such that P(a) is true. “a” is called the witness. This is a constructive proof. You can also prove this without finding a witness using contradiction and this would be a non-constructive proof.

■

Uniqueness: prove that ∃x P( x ) is true and for some other y ≠ x then it does not satisfy the predicate

■ ■

Constructive: see Existence Proof Non Constructive see Existence Proof

❖ Chapter 2: Sets, Functions, Sequences, Sums, Matrices ➢ Set/Set Operations/Cardinality

■ ■

Set: an unordered group of distinct elements Operators ● Union or A ⋃ B where A and B are sets: defined as a set of elements that contains all the elements in set A and all the elements in set B without any duplicates ● Intersection or A ∩ B where A and B are sets: defined as a set of elements that contains all the elements that are both in set A and in set B ● Difference or A - B where A and B are sets: defined as a set of elements that contains all the elements in set A that are not in set B ● Complement or A where A is a set: defined as a set of elements that contains all the elements that are not in A ◆ Also defined as U - A where U is the universal set ● Subsets

◆ Subset or A ⊂ B where A and B are sets: defined as A is a Subset of B ◆ Subset or equal to or A ⊆ B where A and B are sets: defined as A is a subset or is equal to the set B ◆ Subset but not equal or A ⊊ B where A and B are sets: defined as A is a subset of B but not equal to B ◆ Not a Subset or A ⊄ B where A and B are sets: defined as A is not a subset of B ● Supersets ◆ Superset or A ⊃ B where A and B are sets: defined as A is a Superset of B ◆ Superset or equal to or A ⊇ B where A and B are sets: defined as A is a Superset or is equal to the set B ◆ Superset but not equal to or A ⊋ B where A and B are sets: defined as A is a Superset but not equal to the set B ◆ Not a Subset of or A ⊅ B where A and B are sets: defined as A is not a Superset of B ● Member ◆ X is a member of set A or x ∈ A ◆ X is not a member of set A or x ∉ A

■

Cardinality or |N| where N is a set: defined as the number of elements of a set

■

Power Set or P(N) where N is a set: defined as the set of all subsets of a set ● The power set of a set has a cardinality of 2k where k is the cardinality of the set that you are taking the power set of. ➢ Functions

■

Function: the mapping from one set to another, where each element in the Domain can only map to one element in the CoDomain

■

Domain: Set of all possible values that are allowed to be inputs into the function

■ ■

Co-Domain: Set of all possible outputs of the function Range: Set of actual outputs of the function ● Ex: f A ⇾ B: ◆ Is a function that maps set A to set B ◆ A is the Domain ◆ B is the Co-Domain

◆ Range is the subset of B that can result from the mapping

■

One-to-One/Injective: A function that maps every element in the Domain to a unique element in the Co-Domain. However, it does not need to map to the entire Co-Domain

■

Onto/Surjective: A function that maps every element in the Domain to a value in the Co-Domain, does not need to be a unique value.

■ ■

Bijective: A function that is both injective and surjective

■ ■

Inverse Function: There is a function f that is one-to-one and it maps the elements, ai ,of A to a unique element, bi , in B. The inverse of f is a function that takes the b i element and maps it back to ai. f-1(b) = a when f(a) = b Composition Functions: (f o g)(x) = f(g(x)) Ceiling function: f(x) = ⌈x⌉ = the smallest integer that is greater than or equal to x

■

Floor function: f(x) = ⌊x⌋ = the largest integer that is less than or equal to x

■

If set A has the same cardinality of the set of integers then it is countably infinite

■

If set A has the same cardinality as the set of real numbers then it is uncountably infinite

■

If A and B are countable sets then A ⋃ B is countable ➢ Sequences

■

Sequences are denoted in the form {an} and then an will be defined as some function such as an =

■ ■

1 n

an represents the nth term in the sequence A geometric can be defined as {an} where an = a(r)n where a and r are members of the Real set of numbers.

■

Sequences can also be defined recursively ● Such as the fibonacci sequence ◆ Fn = Fn-1 + Fn-2 where F0 = 0 and F1 = 1

■

Solving Recurrence Relation Problems ● Segment the sequence until you find a pattern and use that to find the closed form ● Practice Problems:

➢ Sums n

■

Are in the format

∑ ❑a i

where ai is a sequence or closed

i=m

form n

■

k=0 n

■

❑k = ∑ k=0 n

■

∑ ❑k 2 = k=1 n

■

a r n+1− a ,r ≠1 r−1

∑ ❑a r k =

∑ ❑k 3 = k=1 ∞

n(n+1) 2 n(n +1)(2 n +1) 6 2

2

n (n+1) 4

1 1−x

■

❑ x k ,∨x∨¿ 1 = ∑ k=0

■

∑ ❑kxk−1 ,∨x∨¿ 1 =

∞

k=1

■

1 2 (1−x )

How to find the solution for a sum when the starting point is offset 100

● Find

∑ ❑ k2 k=50

◆ We know the closed form for k squared from 1 to n but not for 50 to n so we need to split this into two separate sums ◆

100

100

49

k=50

k=1

k=1

∑ ❑ k2 = ∑ ❑k 2 - ∑ ❑k 2

= 338,350-

40,425 = 297,925 ➢ Matrices

■

Naming Matrices ● A 3 x 2 matrix has 3 rows and 2 columns

■

Adding Matrices ● To add two matrices the number of rows must be equal and the number of columns must be equal ● For every position in the resultant matrix it is the corresponding positions in the first two matrices added together.

■

Subtracting Matrices ● Same as adding but with subtraction

■

Multiplying Matrices

● To be able to multiply two matrices the columns in the first matrix and the rows in the second need to be the same number ● The size of the resultant matrix is the number of rows of the first matrix and the number of columns of the second matrix ● The first position of the resultant matrix is the the ai term in the first row of the first matrix multiplied by the bi term in the first column of the second matrix ● Then add all of the multiplied terms together and that is the first position of the resultant matrix. ● Then next position is the first row multiplied by the second column. So on and so forth till there are no more columns then you use the next row and multiply by all the columns. ● Matrix Multiplication is not commutative

■

Identity Matrix ● A matrix with ones along the major diagonal and zeros everywhere else ❖ Chapter 3: Algorithms ➢ NOTE: all logs are log base 2 not log base 10 ➢ Big O

■ ■ ■ ■

■

The upper bound of any function C: the coefficient of the upper bound k: the starting point at which the upper bound is always greater than the function EX: find the tight Big O of 3x3+12x2+7 ● x3, x2 and x0 are all bounded above by x3 ∴ we can replace them with x3 ● Our new equation becomes 22x3 ● Our C is 22 and K is 1 ● Answer: 3 x3 +12 x 2 +7 ≤ 22 x3 ∀x >1,3 x 3 +12 x 2 +7 is O( x 3 ) EX: find the tight Big O of 5n2log(n) + 6 n(log(n))2 ● n2log(n) and n(log(n))2 are both bounded by n2log(n) ◆ If you are not sure then this is how you find out ➢ First break the two functions into their respective parts ■ n*n*log(n) ■ n*log(n)*log(n) ➢ Next compare each element on the left with an element on the right: n*n*log(n)=n*log(n)*log(n)

■ On the left and right there is an n so we can remove those since the are the same growth rate ■ Now we have: n*log(n)=log(n)*log(n) ■ Same thing with log(n) ■ Now we have n=log(n) ➢ Now that you have a more simplified equation look at both sides and see which side grows faster ■ We know that n grows faster than log(n) ∴ n2log(n) is the upper bound ● Our new equation becomes 11n2log(n) ● Our C is 11 and K is 1 2

● Answer:

log (n)¿ 2 2 2 log (n)¿ ≤11 (n log (n)) ∀n>1, 5 n log(n)+ 6 n ¿ is O( 5 n2 log(n)+6 n ¿

2 n log(n) ).

➢ Big Ω

■

Very similar to Big O but instead of an upper bound it is now the lower bound

■

Big O is done in a top down way and but for Big Ω it is done in a bottom up way ● C: the coefficient of the lower bound ● k: the starting point at which the lower bound is always less than the function ◆ EX: find the Big Ω of 3x3+12x2+7 ➢ x3, x2 and x0 are all bounded above by x0 ∴ we can replace them with x0 ➢ Our new equation becomes 22x0 ➢ Our C is 22 and K is 1 ➢ Answer: 3x3+12x2+7 = 22O(x0) ∀x > 1 ◆ However this answer is not the tightest bound for the Big Ω ➢ The tightest bound for Big Ω is the largest function ➢ Which would make the tightest bound this: 3x3+12x2+7 =3(x3) ∀x > 1

➢ Big Θ

■

A function’s Big Θ is when a function’s Big O and a function’s Big Ω match

■

f(x) is Θ(g(x)) iff f(x) is O(g(x)) and f(x) is Ω(g(x))

■

Or f(x) = k(g(x)) if you can find a value for k that makes f(x) O(g(x)) and you can find a value for k that makes f(x) Ω(g(x)) then f(x) is Θ(g(x)) ❖ Chapter 4: Number Theory and Crypto ➢ Divisibility

■ ■

a, b ∈ the set of integers a ≠ 0

■

Or

■ ■ ■ ■ ■

So a is a multiple of b

■ ■ ■ ■

a mod b = the remainder of a | b

■

Conversion from Base X to Base 10: ● If A i represents the digits of your number in Base X,

Then a divides b if there is an integer c such that b = ac

b is an integer a

a divides b is equivalent to a | b If a | b and a | c , then a | (b+c) If a | b , then a | bc for all integers c

If a | b and b | c, then a | c ➢ Modulus a mod b = a % b (a+b) mod m = ((a mod m) + (b mod m))mod m

ab mod m = ((a mod m)(b mod m))mod m ➢ Base Conversion

then A n A n−1 ... A2 A 1 ¿ X = X

■

n−1

A n+ X n−2 A n−1+...+ X 1 A2 +X 0 A1 ¿

Conversion from Base 10 to Base X: ● If a is your number in Base 10, then following the following algorithm: ● Step 1: a mod X = Ai . ● Step 2: Divide a by X and discard the remainder. ● Repeat until a is 0. ● The digits of your number in Base X are represented by the

A i values you calculated in reverse order.

■

Conversion between Base 2 (Binary), Base 8 (Octal), and Base 16 (Hexadecimal): ● 4 binary digits correspond to 1 hexadecimal digit. 3 binary digits correspond to 1 octal digit. ➢ Multiplication in Different Bases

■

This is the same as multiplication in Base 10 except you keep in mind the new base.

DE 1 ¿16

● Example: Evaluate A 06 ¿16 ׿

¿

A06 DE1 A06 8C540 824E00 8B1D46 ➢ Modular Arithmetic/Integer Math

■

Modulus: If a and b are integers and m is a positive integer, then a is congruent to b modulo m if m divides a - b, denoted a ≡b (mod m) . ● a ≡b (mod m) iff a(mod m)= b(mod m) . ● a ≡b (mod m) iff there exists an integer k such that a =b + km . ● If a ≡b (mod m ) and c ≡ d (mod m) , then a+ c ≡b +d (mod m) and ac ≡ bd (mod m) . (a+b)( mod m)=((a mod m )+( b mod m )) mod m . ●

ab (mod m)=((a mod m)(b mod m)) mod m . ● ➢ Modular Exponentiation

■

To find bn mod m , where b, n, and m are very large integers, follow this algorithm:

■ ■ ■

Step 1: Express n in binary. Step 2: Calculate

b mod m .

Step 3: Calculate bi mod m , where i is double the previous term’s exponent by squaring the previous term.

■ ■

Repeat Step 3 until i is the last power of 2 below n.

■

Fermat’s Little Theorem ● If p is prime and p, a are relatively prime then ● ap-1 ≣ 1 mod p ● ap ≣ a mod p

Step 4: Multiply together the terms corresponding to the appropriate 1’s in the binary representation of n. ➢ Finding GCD

■

Euclidean Algorithm ● Pg. 267 ➢ Chinese Remainder Theorem

■

Pg. 277

➢ Crypto/RSA

■ ■

ISBN problems pg. 290 RSA pg. 299

❖ Chapter 5: Induction and Recursion ➢ Induction

■

Concept of Mathematical Induction: You can prove that you can reach any rung of a ladder by proving the following: ● 1. You can reach the first rung of the ladder (Basis Step). ● 2. If you can reach the kth rung of the ladder, you can reach the k+1st rung (Induction Step).

■

Principle of Mathematical Induction: To prove that the

propositional function P(n) is true for all positive integers n, you must prove the following: ● Verify that P(1) is true (Basis Step). ● Show that ∀k (P( k )→ P(k +1)) is true (Induction Step). ➢ Strong Induction

■

Strong Induction: To prove that the propositional function P(n) is true for all positive integers n, you must prove the following: ● Verify that P(1) is true (Basis Step).

● Show that ∀k (( P ( 1 ) ∧ P (2)∧ ...∧ P( k ))→ P(k +1)) true (Induction Step). ➢ Recursive Functions

■

is

Recursively Def...