Cheatography

# CIS 206 Cheat Sheet (DRAFT) by ajhalling

This is a draft cheat sheet. It is a work in progress and is not finished yet.

### Vocabulary

 Modus Ponens If P, then Q. P. Therefore, Q. If the cake is made with sugar, then the cake is sweet. The cake is made with sugar. Therefore, the cake is sweet. Modus Tollens If P, then Q. Not Q. Therefore, not P. If the cake is made with sugar, then the cake is sweet. The cake is not sweet. Therefore, the cake is not made with sugar. Onto Function For every element Y in the codomain Y of F there is at least one element X in the domain X of X. Horizontal Line Test. One-To-One Function A function for which every element of the range of the function corres­ponds to exactly one element of the domain. Bijection Each element of one set is paired with exactly one element of the other set, and each element of the other set is paired with exactly one element of the first set. Domain The set of all possible input x-values which will make the function "­wor­k", and output y-values. Codomain The set of all possible output values of a function. Range The set of actual output values of a function. Preimage Another word for Domain Image Another word for Codomain Fibonacci Sequence F(n) = F(n-1) + F(n-2) Universal Quantifier ∀ Expresses that the statements within its scope are true for everyt­hing, or every instance of a specific thing. Existe­ntial Quantifier ∃ Expresses that the statements within its scope are true for at least one instance of something. Scope Denoted by symbols such as parent­hesis and brackets to identify the section of the wff to which the quantifier applies. (∀x)[P­(x)­->Q(x)] - the scope of ∀x is found within the brackets. Universal Instan­tiation Lets you remove ∀ from a predicate. Existe­ntial Instan­tiation Lets you remove ∃ from a predicate. - Must be used before Universal Instan­tiation Method­/Su­bro­utine A subroutine (such as a function) returns a a value. A method is a subroutine or function that you can call on an object in an OO language. Principle of Well-O­rdering Every collection of positive integers that contains any members at all has a smallest number 1st Principle of Mathem­atical Induction Two assert­ions: 1. You can reach the first rung 2. Once you get to a rung, you can always climb to the next one up. (Impli­cat­ion). 1. P(1) 2. For any positive integer k, P(k)->­P(k+1) 2nd Principle of Mathem­atical Induction Show that it's true for P(1), assume it's true for some value "­k", use that assumption to show that it's true for K+1 Binomial Theorem Expands binomials. (a+b)2 = a2 + 2ab + b^2 Pascal's Triangle a triangular array of numbers in which those at the ends of the rows are 1 and each of the others is the sum of the nearest two numbers in the row above (the apex, 1, being at the top). 1st Order Recurrence Relation No need to find the two that precede it. Does it fit the pattern? S(n) = cS(n-1) + g(n) Step 1. Find C. Find g(n). Step 3. Plug n Chug. 2nd Order Recurrence Relation Requires the values from the previous two solutions. Fibonacci sequence is an example of 2nd Order RR. Closed­-Form Solution a mathem­atical expression that can be evaluated in a finite number of operat­ions. No recurr­ence. Binary Predicate Tests the truth value of a predicate which takes two arguments. Domain of Interp­ret­ation Explains what is objects the predicate has meaning over. If P(x) x lives in the water, domain could be sea turtles. Big-O Explains where the "­bul­k" of the work is happening in a function. Drops coeffi­cients. Comput­ational Complexity The amount of resources required for running an algorithm Permut­ation An ordered arrang­ement of objects. Multiply the factorial of the P(n,r) values to find the values. n!/n-r! Factorial A value multiplied by the value before it subseq­uently to 1. 5! = 5 4 3 2 1 Combin­ation An unordered arrang­ement of objects C(n,r). n!/(r!­(n-r)!)