### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# CS 250, Study Guide (Week1-3 Notes) CS 250

PSU

GPA 3.82

### View Full Document

## About this Document

## 81

## 1

## Popular in Discrete Structures I

## Popular in Computer Science and Engineering

This 27 page Study Guide was uploaded by Parker Moore on Monday October 17, 2016. The Study Guide belongs to CS 250 at Portland State University taught by Sergio Antony in Fall 2016. Since its upload, it has received 81 views. For similar materials see Discrete Structures I in Computer Science and Engineering at Portland State University.

## Similar to CS 250 at PSU

## Popular in Computer Science and Engineering

## Reviews for CS 250, Study Guide (Week1-3 Notes)

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/17/16

CS250: Discrete Structures I Fall 2016 Proposition: A statement either true or false. Connectives Operators that make propositions from other proposition, e.g., "today is Monday AND 3 = 7." *bicondictional means they are true if they are the same Connectives are defined by truth tables An application This is for testers. Consider the following fragment of code (in which language?): if (x && y) || (!x && y) { function_1(); } else { function_2(); } Determine the assignments xand y) that execute function_1 and those that execute function_2 X Y # of functions executed T T 1 T F 2 F F 1 Tautology, Contradiction, Contingency Tautology: proposition true for any assignment. (true) Contradiction: proposition false for any assignment. (false) Contingency: proposition not above. (neither) Logical Equivalence Same value for all assignments,p→q≡¬p∨q P Q P->Q ¬P ¬p v Q T T T F T T F F F F F T T T T F F T T T Some famous equivalences are the De Morgan's Laws: ¬(p ∨ q ) ≡ ¬p ∧¬ q ¬(p ∧ q) ≡ ¬p ∨¬ q Conditional Propositions The expressiop→q is called conditional p is the antecendent or hypothesis q is the consequent or conclusion q→p is called converse ¬q→¬p is called contrapositive A conditional and its contrapositive are logically equivalent Ex. If a dog then an animal || If not a dog then not an animal PredicateA statement containing variables, e.g., x=7x=7 . The truth typically depends on the assignment of the variables. Each variable is intended of the appropriate type. Variables are quantified (not discussed in this course) Proofs Axioms: assumed propositions. Undefined terms: primitive/assumed concepts. Definitions: concepts from other concepts. Theorem: proposition with proof. Ex. Definition: Communitive property (a+b) = (b+a) Classes of Proofs Direct Indirect (contrapositive) Contradiction Exhaustive Example Ifx is even, thenx^2 is even. Ifx^2 is odd, thex is odd. Ex. If … X=2h X^2 = 2*h*2*h ( K ) Then … X^2 = 2K Prove If (X^2 = 2K + 1) then (x = 2H+1) A conditional and its contrapositive are logically equivalent Rules of inference Argument: sequence of propositionsp 1,p2,…p np1,p2,…pn (hypotheses) followed by propositionqq (conclusion). Valid argument: qq is true wheneverp1,p2,…p np1,p2,…pn are true. Rule of inference: simple valid argument (show with table). Some examples: 1. Modus Ponens or Rule of Detachment: p → q p ∴ q 2. Modus Tollens: p → q ¬q ∴ ¬p 3. Addition: p ∴ p ∨ q 4. Simplification: p ∧ q ∴ p 5. Conjunction: 1.3. PROOFS 16 p q ∴ p ∧ q 6. Hypothetical Syllogism: p → q q → r ∴ p → r 7. Disjunctive Syllogism: p ∨ q ¬p ∴ q 8. Resolution: p ∨ q ¬p ∨ r ∴ q ∨ r Day2 Notes: Set A collection/bunch/group/class/aggregate of elements. It is safer to consider elements all of the same kind. Membership: key operation, x∈A Many other operations later. Examples/Notation -A={1,2,3,4,5}five-element set. -2∈A 7∉A membership in AA . -If the set is finite, its number of elements is represented |A|, e.g. if A = {1,2,3,4,5} then |A| = 5 -{}or ∅ empty set, no member element. 1. N = {0, 1, 2, 3, · · · } = the set of natural numbers.1 2. Z = {· · · , −3, −2, −1, 0, 1, 2, 3, · · · } = the set of integers. 3. Q = the set of rational numbers. 4. R = the set of real numbers. 5. C = the set of complex numbers -E={x∣x=2y for some y∈Z} even integers. // x such that x = 2y for some y in Z -S+,S−,S∗pos, neg, non-zero elements of SS. -{1,2,{1,2},3}beware of tricky sets. -R={x∣x∉x} does R∈RR∈R ?! Some Operations Subset:A⊂BA⊂B if∀x(x∈A→x∈B) //A is contained within B Subset notationsA⊂B vs. A⊆B vs.A⊊B // A is contained in B (<)/ A is possibly contained in B / A is strictly contained in B EqualityA=BA=B if∀x(x∈A↔x∈B) Equality (alternatA=BA=B iffA⊂B andB⊂A Powerset The powerset of a sAt contains all and only the subseA. of Suppose A={0,1}. -P(A)={∅,{0},{1},A} is the powerset Af. //{{0},{1},{0,1},{}} Also denoted2^A //powerset has 4 elements hence 2^A (A contains 2 elements) Ex. How many elements are there in 2^A, if there are n elements in A? There would be 2^N elements. Combining sets Ex. A = {1,2,5} B = {1,2,3,4} IntersectioA∩B={x∣x∈A∧x∈B} // {1,2} Union:A U B={x∣x∈A∨x∈B} . // {1,2,3,4,5} Complement:¯¯¯A={x∈U∣x∉A} // Every number inside the “universe” that is not included in the // complement of A, using all natural numbers, would be every number except {1,2,5} DifferenceA−B={x∣x∈A∧x∉B} //Elements that are in A but not in B so A = {5} Symmetric DifferencA⊕B={x∣x∈A⊕x∈B} . //Take out same elements so A⊕ B = {3,4,5} Venn diagrams Intersection Union n sets produce 2n regions. IfA has N elements and B has m , how many elements are in A∪B ? Answer: N elements + m elements – intersecting elements Some properties of set Associative: A ∪ (B∪C) = (A∪B) ∪ C Commnutative: A ∪ B = B ∪ A Absorption: A ∪ (A∩B) = A ... dozen more ... Generalized union and intersection ∪Nn=1 =A ∪A 2∪…A N={x∣∃n(x∈A n)} Similar formula for intersection. Upper bound can be infinity. Partition A partition of a Se is a set of disjoint nonempty subseS whose union isS. //Some subsets of that when you do the Union of all you will get S E.g.,S={1,2,3,4} ,P={{1},{2,3},{4}} . Question: how many elements can be in a partitionA, iA hasn elements? Answer: at least one and at most N Cartesian product A×B={(a,b)∣a∈A∧b∈B} Generalized to n sets. Power notation, A^ n=A×⋯×A n tiim s The elements of a cartesian product are called tuples. Cartesian products are a way to group things. Classes in C++ code are Cartesian products. Ex. A = {1,2} B = {red,yellow} A x B = {(1,red),(1,yellow),(2,red),(2,yellow)} Multisets In a set there is no order and there are no repetitions. A multiset is a setlike structure in which elements can be repeated (still no order). Same notation as set (beware). How to define membership, union and intersection (hint: what should A∪A and A∩A be)? Ex. A = {1,1,2} B = {1,2,2} A U B = {1,1,1,2,2,2} or {1,1,2,2} A ∩ B = {1,2,} Resources: I found this video very helpful for the first week. If you are struggling or wanted to review give it a watch. Only 18 minutes. https://www.youtube.com/watch?v=OLGVhszBlq4 CS 250 Week 2 Notes PSU: Fall term Highlight = Link to further help on topic Function A function ffrom a setA (the domain) to a setB (the codomain) associates to each element x of A exactly one elementy of B. Notations: f:A→B and f(x)=y Examples name of students. parent of students. f(x)=x2 ? f(x)=√ x ? Concepts Let f:A→B Ify=f(x), thenyis the image ofxx and xx is a preimage ofy (for some authors, sets not elements). IfC⊂A , thef(C)={f(x)∣x∈C}is the image oC . The image of A is called the range f, e.g., range of temperature in Portland in July. Properties Injective (one-to-one∀x,y∈A,f(x)=f(y)→x=ySame output implies same input. Surjective (onto)∀y∈B,∃x∈A,y=f(x). Every element (of the codomain) is an output (of some input). Bijective: both injective(1-1) and surjective(onto) Surjective (Onto Function) A function f from A to B is called onto if for all b in B there is an a in Asuch that f (a) = b. All elements in B are used. Such functions are referred to as surjective. "Onto" NOT "Onto" (all elements in B are used) (the 8 and 1 in Set B are not used) By definition, to determine if a function is ONTO, you need to know information about both set A and B. When working in the coordinate plane, tAeandtB may both become the Real numbers, stated as . EXAMPLE 1: Is f (x) = 3x - 4onto where ? This function (a straight line) iONTO. As you progress along the line, every possible y-value is used. In addition, this straight line also possesses the property that each x-value has one uniquey-value that is not used by any other x-element. This characteristic is referred to as being one-to-one. EXAMPLE 2: Is g (x) = x² - 2onto where ? This function (a parabola) is NOTONTO. Values less than -2 on the y-axis are never used. Since possible y-values belong to the set of ALL Real numbers, not ALL possibley-values are used. In addition, this parabola also has y- values that are paired with more than one x-value, such as (3, 7) and (-3, 7). This function will not be one-to-one. EXAMPLE 3: Is g (x) = x² - 2onto where ? If seB is redefined to be , ALL of the possible y-values are now used, and function g (x) (under these conditiONTO.is Injective (One-to-One Function) A function f from A to B is called one-to-one (or 1-1) if whenever f (a) = f (b) then a = b. No element of B is the image of more than one element in A. In a one-to-one function, given any y there is only one x that can be paired with the given y. Such functions are referred to as injective. "One-to-One" NOT "One-to-One" EXAMPLE 1: Is f (x) = x³ one-to-one where ? This functionOne-to- One. This cubic function possesses the property that each x-value has one unique y-value that is not used by any other x-element. This characteristic is referred to as being 1-1. Also, in this function, as you progress along the graph, every possible y-value is used, making the function onto. EXAMPLE 2: Is g (x) = | x - 2 |one-to-one where ? This function is NOTOne-to-One. This absolute value function has y-values that are paired with more than one x- value, such as (4, 2) and (0, 2). This function is not one-to-one. In addition, values less than 0 on the y- axis are never used, making the function NOT onto. EXAMPLE 3: Is g (x) = | x - 2 |one-to-one where ? With setB redefined to be , function g (x) will still be NOT one-to-one, but it will now be ONTO. BOTH Functions can be both one-to-one and onto. Such functions are called bijective. Bijections are functions that are both injective and surjective. "Both" NOT "Both" - not Onto . Composition Iff:A→B and g:B→C , then(g∘f):A→C is defined b(g∘f)(x)=g(f(.)) Composition help: https://www.youtube.com/watch?v=G7rGep_v-EM Inverse The function 1A:A→A1 defined by ∀x∈A (1A(x)=x)is called the identity function foA . Iff:A→B is bijective, then there exists a unique functionf−:B→A , called the inverse of , such that f∘−1=1Bf∘f−1=1Band −1∘f=1Af−1∘f=1A. Help with Converse, inverse, Contrapositive: https://www.youtube.com/watch?v=afAt0jEF74c Operator A function from A×A to A, e.g., ''+'' ovZ(binary). Extends to unary and ternary. Help with operators: https://en.wikibooks.org/wiki/Discrete_Mathematics/Logic Relations A relation R is a subset of the cartesian product of some sets S1,…SnS1,…Sn. Example: SS set of students {Ann,Bud,Carla,…}{Ann,Bud,Carla,,C set of course {162,250,…}{162,250,…}. Relation takes⊆S×C is defined by takes={(Ann,161),(Bud,250),(Ann,250)…} Infix notation:Ann takes 161Ann takes 1.1 Notation for binary relations: (Z,<. Help with Relations: https://www.youtube.com/watch?v=h34hZ_hynzE Representing relations Venn diagrams (a relation is a set). Arrow diagrams (a relation is similar to a function). Binary relation on a set: a directed graph (defined later). Binary relation on a set: a matrix. Inverse, composition IfA and Bare sets and R a relation overA×B , then the inverse R−1R−1 ofR is defined by: ∀a∈A,b∈B ((b,a)∈R −1↔(a,b)∈R Question: if RR is ''parent'' what Rs−1R−1? IfA, B and C are sets,R⊆A×B , andS⊆B×C then the composition R∘S ofR and Sis defined by: ∀a∈A,c∈C ((a,c)∈R∘S↔∃b∈B((a,b)∈R∧(b,c)∈S)) Ex: compose ''student takes course'' with ''course is taught in classroom'' Properties Let R be a binary relation on a seA . reflexive:∀x∈A (x R x). symmetric: ∀x,y∈A (x R y→y R x). transitive:∀x,y,z∈A (x R y∧y R z→x R .) antisymmetric: ∀x,y∈A (x R y∧y R x→x=y. Help with properties of relations: https://www.youtube.com/watch?v=LPIWJ1tOM-E Partial order Reflexive, transitive, antisymmetric. Denoted '' ≤'' or ⪯'''. Ex.: (Z,≤, (Z+,|where a|b↔∃t (b=at)a|b↔∃t (b=at) ,(2A,⊆)where A is any set. Note: reflexive is optional for some authors. Representation: Hasse diagrams, left 2 {a,b,, right({1,2,…10},|. Links to partial order help: http://mathworld.wolfram.com/PartialOrder.html https://www.youtube.com/watch?v=hQweMQ7usmU Equivalence Reflexive, symmetric, transitive. Denoted '' ∼''. Ex.: on Z,x∼y↔x mod 5=y mod 5x∼y↔x mod 5=y mod 5 . Ex.: on Students, x∼y↔x and yare born in the same month. Equivalence class of xx: [x]={y∣x∼y,y∈A}. Quotient: A/∼={[x]∣x∈A}. A/∼ is a partition{A1,A2,…} ofA : 1. Ai∩A =∅ , foi≠j 2. ∪A =A Help with equivalence: https://www.youtube.com/watch?v=2p5AuV35i2s Notation Both Nk and Zk denote the set {0,1,…k−1}. Elements in this set can be added, multiplied, etc., always modulo k E.g.,N ={0,1,2,3,4}and in this set2−4=3 because −2=3 (everything mod 5). CS 250, Week 3 Notes PSU: Fall term HighLight = Keyterm Algorithms: Finite set of instructions which, if followed, accomplish a particular task. In addition every algorithm must satisfy the following criteria: input: there are zero or more quantities which are externally supplied; output: at least one quantity is produced; definiteness: each instruction must be clear and unambiguous; finiteness: if we trace out the instructions of an algorithm, then for all cases the algorithm will terminate after a finite number of steps; Effectiveness: every instruction must be sufficiently basic that it can in principle be carried out by a person using only pencil and paper. It is not enough that each operation be definite, but it must also be feasible. Recursive algorithm: Algorithm which calls itself with “smaller” input values, and which obtains the result for the current input by applying simple operations to the returned value for the smaller input. More generally if a problem can be solved utilizing solutions to smaller versions of the same problem, and the smaller versions reduce to easily solvable cases, then one can use a recursive algorithm to solve that problem. Example 2: Given some dollar value in cents (e.g. 200 = 2 dollars, 1000 = 10 dollars), find all the combinations of coins that make up the dollar value. There are only penny, nickel, dime, and quarter. (quarter = 25 cents, dime = 10 cents, nickel = 5 cents, penny = 1 cent) def countChange(money: Int, coins: List[Int]): Int = if (money == 0) 1 else if (coins.isEmpty || money < 0) 0 else countChange(money - coins.head, coins) + countChange(money, coins.tail) Complexity: numerical function T(n) – time versus the input size n. Returns the number of times some step is executed. Examples: Sorting: number of elements, number of comparisons. Big Oh Notation. A function f(n) is said to be of order at most g(n), written f(n) = O(g(n)), if there is a constant C1 such that |f(n)| ≤ C1|g(n)| Omega Notation. A function f(n) is said to be of order at least g(n), written f(n) = Ω(g(n)), if there is a constant C2 such that |f(n)| ≥ C2|g(n)| Theta Notation. A function f(n) is said to be of order g(n), written f(n) = Θ(g(n)), if f(n) = O(g(n)) and f(n) = Ω(g(n)). The following are several common growth functions: Complexity Algorithm(s) O(log(n)) binary search O(n) linear search O(n log(n)) efficient sort O(n 2) naive sort O(n 3) matrix mult., shortest path O(a n) traveling salesman Euclidean Algorithm The Division Algorithm- If a, b ∈ Z, b > 0, then there exist unique q, r ∈ Z such that a = qb + r, 0 ≤ r < b. Here q is called quotient of the integer division of a by b, and r is called remainder. ∀a∈Z,b∈Z+ (∃q,r∈Z (0≤r<b∧a=bq+r)) Divisibility- Given two integers a, b, b 6= 0, we say that b divides a, written b|a, if there is some integer q such that a = bq: b|a ⇔ ∃q, a = bq . We also say that b divides or is a divisor of a, or that a is a multiple of b. Fundamental Theorem of Arithmetic-Every integer n ≥ 2 can be written as a product of primes uniquely, up to the order of the primes. It is customary to write the factorization in the following way: n = p s1 1 p s2 2 . . . p sk k , where all the exponents are positive and the primes are written so that p1 < p2 < · · · < pk. For instance: 13104 = 2^4 · 3^ 2 · 7 · 13 Greatest common Divisor- Definition straight from the name. Euclid algorithm: gcd(a,0)=a gcd(a,b)=gcd(b,amodb) Ex. find gcd(189,33) 189 = 33 ∙ 5 + 24 33 = 24 ∙ 1 + 9 24 = 9 ∙ 2 + 6 9 = 6 ∙ 1 + 3 6 = 3 ∙ 2 + 0 Formal description of the Euclidean algorithm Input Two positive integers, a and b. Output The greatest common divisor, g, of a and b. Internal computation 1. If a<b, exchange a and b. 2. Divide a by b and get the remainder, r. If r=0, report b as the GCD of a and b. 3. Replace a by b and replace b by r. Return to the previous step. Euclid’sAlgorithm Calculator- http://www.calculatorsoup.com/calculators/math/gcf-euclids-algorithm.php Encryption- Modular arithmetic- Map letters to letters. Ceasar code, simply "two letters down" plain: A B C D E F G H I J ... Y Z cipher: C D E F G H I J K L ... A B Ex.: HELLO becomes JGNNQ. Encrypt: E(x)=ax+b%26 , for somea and b. Must choose a and b such thatE is a bijection. Theorem (bijection) Let n>1 and f:Nn→N n defined by f(x)=(ax+b)%n Then: f is bijective igcd(a,n)=1 Ex.: f(x)=(4x+1)mod5 is bijective. In mathematics, a bijection, bijective function orone-to-one correspondence is a function between the elements of two sets, where 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. There are no unpaired elements. Theorem (decryption) Given fabove, letD(x)=(kx+c)%n where f(c)=0f(c)=and ak+nm=1 for some k and m. Then ∀x (D(E(x))=E(D(x))=x) Ex.: Find the inverse of. Theorem (fixpoint) Let n>1 and f:Nn→N ndefined by f(x)=(ax+b)modn Then: f has no fix points ifgcd(a–1,n)does not divideb . Ex.: Find the fixpoints off(x)=3x+2mod10f(x)=3x+2mod10 . Topological Sort Definition A linear ordering of a poset. If a≺b in the poset, a is before b in the topological sort. Good: 1,2,4,5,10,… Bad: 1,2,4,10,5,… Resources: Discrete Mathematics – algorithms: https://www.youtube.com/watch?v=NGu- Xad_8os Discrete Mathematics – algorithms: https://www.youtube.com/watch?v=qH9oe_I5ums Big O notation- https://www.youtube.com/watch?v=N5_sTEhnZKM

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.