EECS 203 Final Exam Study Guide

EECS 203 final exam study guide EXAM INFO • • You can bring 3 single-sided sheets "In addition, in your solutions you are allowed to quote without proof any results proved in the lectures, discussion sections, homework, the sample exam, and the textbook." PROPOSITIONS AND OPERATIONS • • • • • Proposition - either true or false, but not both ¬p = negation of p p ∧ q = and (remember that ∧ is like the A in "AND") p ∨ q = or p ⊕ q = Exclusive or; XOR; only one can be true • • Tautology - always true Contradiction - always false • Distributive laws o p ∨ (q ∧ r) ≡ (p v q) ∧ (p v r) o p ∧ (q v r) ≡ (p ∧ q) v (p ∧ r) • De Morgan's Laws o ¬(p ∧ q) ≡ ¬p v ¬q o ¬(p ∨ q) ≡ ¬p ∧ ¬q CONDITIONALS • • p → q: if p, then q T → F = F; everything else is true English ways to express conditionals • • • • • • • • • • • • • "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" Logical equivalences • • • • • • • • • p → q ≡ ¬p v q p → q ≡ ¬q → ¬p p v q ≡ ¬p → q p ∧ q ≡ ¬(p → ¬q) ¬(p → q) ≡ p ∧ ¬q (p → q) ∧ (p → r) ≡ p → (q ∧ r) (p → r) ∧ (q → r) ≡ (p v q) → r (p → q) v (p → r) ≡ p → (q v r) (p → r) v (q → r) ≡ (p ∧ q) → r Biconditional logical equivalences • • • • p ↔ q ≡ (p → q) ∧ (q → p) p ↔ q ≡ ¬p ↔ ¬q p ↔ q ≡ (p ∧ q) v (¬p ∧ ¬q) ¬(p ↔ q) ≡ p ↔ ¬q RULES OF INFERENCE For propositional logic • • • • • • • • [p ∧ (p → q)] → q [¬q ∧ (p → q)] → ¬p [(p → q) ∧ (q → r)] → (p → r) [(p v q) ∧ ¬p] → q p → (p v q) (p ∧ q) → p [(p) ∧ (q)] → (p ∧ q) [(p v q) ∧ (¬p v r)] → (q v r) (modus ponens) (modus tollens) (hypothetical syllogism) (disjunctive syllogism) (addition) (simplification) (conjunction) (resolution) For quantifiers • • • • ∀x P(x) → P(c) (universal instantiation. Example: "All women are wise", therefore "Lisa is wise.") P(c) for arbitrary c → ∀x P(x) (universal generalization) ∃x P(x) → P(c) for some c (existential instantiation) P(c) → ∃x P(x) for some c (existential generalization) QUANTIFIERS • • • ∀x P(x) = P(x) is true for every x on the domain ∃x P(x) = there is an x on the domain for which P(x) is true ∃!x P(x) = there is ONLY ONE x on the domain for which P(x) is true De Morgan's Laws • • ¬∃x P(x) ≡ ∀x ¬P(x) ¬∀x P(x) ≡ ∃x ¬P(x) Nested quantifiers • ∀x ∃x Q(x) ≡ ∀x (∃x Q(x)) Quantifying two variables • • • • • A helpful PowerPoint ∀x ∀y P(x, y) ≡ ∀y ∀x P(x, y) = true when P(x, y) is true for every pair of x and y ∀x ∃y P(x, y) = true when, for every x, there is a y for which P(x, y) is true ∃x ∀y P(x, y) = true when there is an x for which P(x, y) is true for every y ∃x ∃y P(x, y) ≡ ∃y ∃x P(x, y) = true when there's a pair x,y for which P(x, y) is true PROOFS • • • • • Proof by exhaustion: try everything (only works with a finite number of possibilities) Proof by cases: you can break things into groups and show that certain groups work Proof by implication o Assume P is true ▪ Assume P, P then Q, therefore Q ▪ Holds because if P is true you get Q and if P is false then Q is automatically implied ▪ After you prove Q it is no longer safe to assume, P still holds o Prove the contrapositive ▪ Assume Not Q show that it implies Not P Proving "if and only if" o Prove each implies the other ▪ P implies Q AND Q implies P o Construct a chain of iffs ▪ Show P iff R iff S iff Q so P iff Q Proof by contradiction o Show that if the premise is T or F then something F would be T o Example: Show that if P is false, then 0=2 since 0 != 2 P must be true SETS • • • A collection of of objects called elements grouped together Ordering is not important, just which elements are contained (eg, {x,y} is the same as {y,x}) x ∈ D shows x is an element of D • • • • • • • • ϕ = the empty set = {} N = natural numbers = { 0, 1, 2, ... } Z = integers = { ... -2, -1, 0, 1, 2, ... } Z+ = positive integers = { 1, 2, 3, 4, ... } Q = rationals R = reals R+ = positive reals C = complex numbers • Sets can contain other sets denoted S ⊆ T showing S is a subset of T or all the elements in S are in T Unioning (∪) two sets combines all the elements of two sets (additive) Intersection (∩) creates a set containing all elements contained by both sets Subtraction (–) creates a set containing all elements of 1st set except the ones in the 2nd set. Example: A - B contains all the elements of A except the ones that are in B. The complement of a set is everything except the elements in that set A set has a cardinality equal to the number of elements in the set • • • • • o o o o • • • • Example: S = {1, 2, 3}; |S| = 3 S = {{1, 2, 3}, {4, 5, 6}}; |S| = 2 S = {{ϕ}, 1}; |S| = 2 S = {ϕ, 1}; |S| = 2 //note: if ϕ is contained in the set, then it counts as an element. If the set itself is empty, than the cardinality is 0 (see below). o S = ϕ; |S| = 0 Power set o The set containing all subsets of a set (I know, kind of strange wording) o ex. B∈P({1,2}) iff B = { {∅},{1},{2},{1,2} } o Cardinality of a power set is: |P(S)| = 2^|S| Cartesian product of sets o Gives all possible sets of which the first element comes from set one and the second element comes from set 2 Notation for defining a set o A = { n ∈ R | x^3-3x+1 > 0 } Set equality o Two sets are equal if and only if every element in one set is in the other and visa versa INDUCTION • • • Principle o P(n) is your predicate o If P(0) is true and P(k) implies P(k+1) then P(n) is true for all n in the set Induction Template o State you are using induction o Define your predicate P(n) o Prove that P(0) is true (Base Case) o Assume P(n) is true o Show that P(n+1) is true Strong Induction o P(0) is true and P(0) through P(n) imply P(n+1) FUNCTIONS • • • • • • • • A function is a mapping from domain A to codomain B such that for any one input there can only be one output o Denoted f: A → B or f(A) = { y = f(x) | x ∈ A } One-to-one/injective - X is one-to-one with Y if every mapping to Y has exactly ONE value in X that hits it Onto/surjective - X is onto Y if there exist values in X such that mapping them onto Y will hit every value inside of Y Bijective - it goes both ways: onto and one-to-one One-to-one correspondence - A function is a one to one correspondence if it is 1-1 and onto Inverse functions - a function f (x) the maps b onto a iff the function f(x) maps from a to b. This only works if f is onto and 1-1. Countable - a infinite set with a one to one correspondence with the set of Natural numbers Composite functions - Mapping a to c through a set of two functions that map a to b and then b to c, denoted f o g. Otherwise written as f(g(a)). -1 ALGORITHMS • Algorithm - finite sequence of precise instructions to perform a computation Searches • • Linear search - start at the front, brute-force until you find it. Worst case: O(n) Binary search - start at the middle of a sorted list. If you’re too high, search the left half of the list. If you’re too low, search the right half of the list. Worst case: O(log(n)) Sorts • Bubble sort - switch adjacent values over and over again until you don’t switch no more. Another way to think about bubble sort is: find the biggest element and put it at the end, then look for the second biggest element and put it one from the end and so on. Worst case O(n ), best case O(n). Insertion sort - place each element from the unsorted list to the correct place in the sorted list. Worst case O(n ), best case O(n). 2 • 2 Halting problem • • • • Procedure that cannot be solved with an algorithm. H(P, I) defines H as a procedure which takes in two arguments. P is a program and I is arguments to P. H returns true if P will halt with arguments I, or false if P loops forever Proof that H(P, I) cannot be solved with a procedure: define K(P) as halting if H(P, P) ( a program can take itself as an argument) returns false (run for ever). K(P) runs for ever if H(P, P) returns true (halting). If we pass K itself K(K). If K halts then H(K, K) would’ve said the K would run forever and also if K runs forever H(K, K) would’ve said that K halts. Thus, creating a contradiction. SEQUENCES • • A set that follows a pattern Recurrence relations - expresses the value of a as a function of the previous term (a ). Always has a base case like a = 1, a = 1, etc. Common patterns for sequence terms to follow; a+dn, ar , n ,n ,n ,2 ,3 ,n!, fibonacci n 0 • SUMMATIONS n-a 1 n 2 3 4 n n More of these formulas can be found using google if this doesn’t seem comprehensive enough. COSTS OF A COMPUTATION Big O, big Ω, big ϴ • • • Big O - upper bound on the growth of the function o f(x) = O(g(x)) therefore C*g(x) ≥ f(x) Big Omega - lower bound on the growth of a function o f(x) = Ω(g(x)) therefore C*g(x) ≤ f(x) Big Theta - a function that describes the same growth order as function you are observing o f(x) = ϴ(g(x)) therefore C × f(x) = O(g(x)) & C × f(x) = Ω(g(x)) Only matters as the function progresses to infinity, you are allowed to say for all x > k When disproving all big O or big Ω, show no such witnesses pairs (k, C) exist Algebra relations o Addition ▪ f(x) is O(g(x)) & e(x) is O(h(x)) then (f + e) is O(max( g(x), h(x) )) o Scalar multiplication ▪ When f(x) is O(g(x)) and there is a constant k then k*f(x) is O(g(x)) o Product ▪ f(x) is O(g(x)) & e(x) is O(h(x)) then (f*e) is O( g*h ) To determine a function's big O you must find the sum equivalent value and determining what binds it If the limit exists and is finite as x goes to infinity of f(x)/g(x) then f(x) ∈ O(g(x)) o if the limit is infinite, then f(x) ∉ O(g(x)) Recurrence Relations o f(n) = a*f(n/b)+c ▪ O(n^log_b(a)) if a > 1 ▪ O(log(n)) if a = 1 o f(n) = af(n/b) + cn^d[aka...the master theorem] ▪ O(n^d) if a < b^d ▪ O(n^d * log(n)) if a = b^d ▪ O(n^(log_b(a))) if a > b^d 1 • • • • • • Tractability 2 • • • A problem is considered tractable if the algorithm to solve the problem has polynomial or less complexity A problem is considered intractable if the algorithm to solve the problem had exponential or higher complexity A problem is considered unsolvable if no algorithm solves the problem. For example, the Halting problem. COUNTING Inclusion-Exclusion • • |A ∪ B| = |A| + |B| - |A ∩ B| |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C| Cartesian Product • • • S = S × S × ... × S |S| = |S1| |S2| ... |Sn| (whether disjoint or non-disjoint) Composite: not prime 1 2 n Pigeonhole principle • • • If N pigeons nest in k < N holes, then at least one hole will have two or more pigeons. Generalized pigeonhole principle o If N objects are placed into k boxes, then there is at least one box containing at least CEIL(N / k) objects. Purified pigeonhole principle (EWD) o For a nonempty, finite bag of numbers (and bags allows repetitions), the maximum value is at least the average value. BINOMIAL THEOREM • Definition o n ≥ 0, (x + y) = i=0nxiyn-iC(n,i) Similar to the multinomial theorem, which expands it out to an arbitrary m elements n • COMBINATIONS & PERMUTATIONS Combinations/choose (aka binomial coefficient): order doesn’t matter • • • • • C(n, k) The number of ways to choose k objects from n objects if order doesn't matter For example, you want to pick a team of 5 from 20 people -- order doesn't matter, so it's C(20, 5) C(n, k) = n!k!(n-k)! (and you can see it prettier on Wikipedia) With repetition allowed: C(n, r) = (n+r-1)!r!(n-1)! Permutations: order matters • • • P(n, k) The number of ways to choose (pick) k objects from n objects if order matters For example, if you want to pick the top 10 songs from 200, order matters, so it's P(200, 10) • • P(n, k) = n! / (n - k)! (and you can see it prettier on Wikipedia) With repetition allowed: P(n, k) = nk PLACING BALLS IN URNS Placing n balls into m urns (for S(n, m), see below): balls urns # balls/urn # solutions labeled labeled any m labeled labeled <= 1 P(m, n) labeled labeled >= 1 m! S(n, m) labeled labeled k’th urn holds n balls n! / (n ! n ! … n !) unlabeled labeled any C(n + m - 1, m - 1) unlabeled labeled <= 1 C(m, n) labeled unlabeled >= 1 S(n, m) labeled unlabeled any unlabeled unlabeled >= 1 n k 1 2 m k=1mS(n,k) P (n) m Stirling numbers of the second kind • • • S(n, k) = the amount of ways to split n distinguishable objects into k indistinguishable bins For example, if you have 4 employees and want to put them into 2 offices (and you can't distinguish the offices), that's S(4, 2) = 7 different ways to do this There's an ugly formula which you might wanna write down It's usually best to use a chart, which you might also want to write down PROBABILITY • Starts with a defined sample space S and an event E in that sample space o probability of E is p(E) = |E| / |S| o 0 ≤ P(E) ≤ 1 o P(not E) = 1 - P(E) o P(E ∪ E ) = P(E ) + P(E ) - P(E ∩ E ) Method for probability o Find the sample space o Define events of interest o Determine outcome probabilities o Compute event probabilities 1 • 2 1 2 1 2 BAYES' THEOREM • • • • P(E|F) = the probability of E, given F P(E|F)=P(F|E)P(E)P(F|E)(P(E)+P(F|G)(P(G)) o G is the complement of E More generally, P(E|F)=P(F|E)P(E)P(F). P(F) may be given or easier to determine. If you have P(F) = ½, then the you can use a simpler version: P(E|F) = P(F|E) / [ P(F|E) + P(F|E complement)] EXPECTATION and VARIANCE • • Expected value = E(x) X(s) is a random variable... o E(x) = Σ P(s )X(s ) o Expectations are linear, whether or not X are independent ▪ Useful in proving basic propositions ▪ E(X + X ) = E(X ) + E(X ) ▪ E(aX + b) = aE(X) + b o Total Expectations ▪ E(R) = ΣE(R|A )X(A ) Deviation is X(s) - E(x) however this is not very useful and is often squared Variance i i i 1 2 1 i • • o o 2 i where p = probability, x = value, mu = E(X) Standard deviation = √V(x)