### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Math for Computer Science CSCI 1900

ETSU

GPA 3.95

### View Full Document

## 23

## 0

## Popular in Course

## Popular in Communication Studies

This 50 page Class Notes was uploaded by Amira Von on Sunday October 11, 2015. The Class Notes belongs to CSCI 1900 at East Tennessee State University taught by Staff in Fall. Since its upload, it has received 23 views. For similar materials see /class/221377/csci-1900-east-tennessee-state-university in Communication Studies at East Tennessee State University.

## Reviews for Math for Computer Science

### 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/11/15

CSCI 1900 Discrete Structures Operations on Sets Reading Kolman Section 12 cScI 191m 7 Discrete Structures Operatiom on Sets rPage 1 Operation on Sets An operation on a set is where two sets are combined to produce a third cScI 191m rDiscreIe Structures Operations on Sets rPage 2 Union AuBxxerrxeB Example LetA a b c e f and B b d r s AuBabcdefrs Venn diagram cScI 191m 7 Discrete Structures Operatiom on Sets 7 Page 3 Intersection AmBxxeAa dxeB Example LetA a b c e f B b e f r s and C a t u v cScI 191m 7 Discrete Structures Operatiors on Sets rPage 4 Disjoint Sets Disjoint sets are sets where the intersection results in the empty set U Not disjoint Disjoint cScI 191m 7 Discrete Structures Operatiom on Sets 7 Page 5 Unions and Intersections Across Multiple Sets Both intersection and union can be performed on multiple sets AUBUCXIXEAOFXE BOI39XE C AmBmCxXEAandXE BandXE 0 Example A1 23457B13 89andC 131323 AUBUC123456789 A m B m c 1 3 cScI 191m rDiscreIe Structures Operations on Sets rPage 5 Com plement The complement ofA with respect to the universal set U all elements of the universal set U that are not a member of A Denoted A Example lfA x x is an integer and x 5 4 and U Z then A x x is an integer and x gt 4 Venn diagram Complement With Respect toquot The complement of B with respect to A all elements belonging to A but not to B It s as if U is in the complement is replaced with A DenotedA BxxeAandxe B Example Assume A a b c and B b c cl e Venn diagram B A A B CSCI 1900 eDrsrrene nururres Operatrorrs on Set Jaye 7 CSCI 19007 Drsrrene nurtures Operanorrs orr SES 7 Page 8 Symmetric difference Symmetric difference If A and B are two sets the symmetric difference is the set of elements belonging to A or B but not both A and B DenotedA BX x e Aandx at B or XE Bandx A A B A BUB A Venn diagram Algebraic Properties of Set Operations Commutative properties A A m B B m A Associative properties C A U B U C A B C A BrC Distributive properties BOCAmBOAmC AOBmCAOBmAOC CSCI 1900 eDrsrrene nururres Operatrorrs on Set Jaye 9 CSCI 19007 Drsrrene nurtures Operatrorrs on Set Jaye 10 More Algebraic Properties of Set Operations ldempotent properties AOAA Properties of the complement AA AUAU i A QU u AOBAn De Morgan s law AnBAOB De Morgan s law More Algebraic Properties of Set Operations Properties of a Universal Set A U U U A m U A Properties ofthe Empty Set AO AorAOA Am orAm CSCI 1900 eDrsrrene nururres Operanorrs orr ses Jaye 11 CSCI 19007 Drsrrene nurtures Operatrorrs on Set Jaye 12 The Addition Principle The Addition Principle associates the cardinality of sets with the cardinality of their union IfA and B are finite sets then AuBAB AnB Lets use a Venn diagram to prove this A n B The Roman Numerals indicate how many times each segment is included forthe expression A B Therefore we need to remove one A n B since it is counted tvwce CSCI 1900 episcrae Structures Operanons on Se 7 Page 11 Addition Principle Example LetAabcdeandBcefh k m A5 B6 and AmBc e2 AuBa bcd ef h k m AuB956 2 IfA m B 9 Le A and B are disjoint sets then the A m B term drops out leaving A B CSCI 1900 7 Discrete sumruns Operanons on Se 7 Page 14 CSCI 1900 Discrete Structures Methods of Proof Reading Kolman Section 23 CSCI 1900 7 Discrete structures Methods omeof7 Page 1 Past Experience Up to now we ve used the following methods to write proofs Used direct proofs with generic elements definitions and given facts Used proof by cases such as when we used truth tables CSCI 1900 7 Discrete swuctures Memods omeof7 Page 2 General Description of Process p 2 7 denotes quotq logically follows from p Implication may take the form p A p2 A p3 A A p7 2 o q logically follows from p1 p2 p3 p7 CSCI 1900 7 Discrete structures Methods omeof7 Page J General Description continued The process is generally written as P1 P2 P3 pl q CSCI 1900 7 Discrete swuctures Memods omeof7 Page 4 Components of a Proof The p39s are called hypotheses or premises q is called the conclusion Proof shows that if all ofthe p39s are true then 7 has to be true lf result is a tautology then the implication p 2 7 represents a universally correct method of reasoning and is called a rule ofinference CSCI 1900 7 Discrete structures Methods omeof7 Page 5 Example of a Proof based on a Tautology If p implies q and q implies r then p implies r P Q Q p 2 r o By replacing the bar under q 2 rwith the the proof above becomes p 2 q A q 2 r 2 P F o The next slide shows that this is a tautology and therefore is universally valid CSCI 1900 7 Discrete swuctures Memods omeof7 Page is Tautology Example continued Equivalences Some mathematical theorems are equivalences ie p cgt q o The proof of such a theorem is equivalent with proving both p 2 q and q 2 p CSCI 1900 7 Discrete souctures Memods omeofr Page 8 P q r p q q r p qM par p qu rD q i r i p i r T T T T T T T T T F T F F F T T F T F T F T T T F F F T F F T F T T T T T T T F T F T F F T T F F T T T T T T F F F T T T T T CSCI 1 Methods omeofrPRgEI modus ponens form the method of asserting p at q Example p a man used the toilet q the toilet seat is up p 3 q If a man used the toilet the seat was left up Supported by the tautology p p 2 q 2 q CSCI 1900 7 Discrete structures Methods omeofr Page 9 modus ponens continued p q I pal I pMqu I momme T T T T T T F F F T F T T F T F F T F T CSCI 1900 7 Discrete souctures Methods omeofr Page 10 Invalid Conclusions from Invalid Premises Just because the format of the argument is valid does not mean that the conclusion is true A premise may be false For example Acorns are money If acorns were monev no one would have to work 39No one has to work Argument is valid since it is in modus ponens Conclusion is false because premise p is false CSCI 1900 7 Discrete structures Memods omeofr Page 1 1 Invalid Conclusion from Invalid Argument Sometimes an argument that looks like modus ponens is actually not in the correct form For example lftuition was free enrollment would increase Enrollment increased Tuition is free Argument is invalid since its form is P q 9 p CSCI 1900 7 Discrete souctures Methods omeofr Page 12 Invalid Argument continued Truth table shows that this is not a tautology P 1 maa Hma F F p q p qu p qAq2 p T T T F F T T T F T F T CSCI 1900 7 Discrete structures Methods omeofr Page 1 Indirect Method Another method of proof is to use the tautology P Q Q Q quotq QNP The form ofthe proof is CSCI 1900 7 Discrete swuctures Methods omeofr Page 14 Indirect Method Example 39 PiMY e mail address is available on a web site q I am getting spam p3 q If my email address is available on a web site then I am getting spam q 3 mail a p Ifl am not getting spam then my e ddress must not be available on a web site This proof says that if I am not getting spam then my e mail address is not on a web site CSCI 1900 7 Discrete structures Methods omeofr Page 15 Another Indirect Method Example Prove that if the square of an integer is odd then the integer is odd too p n2 is odd q n is odd q 2 p If n is even then n2 is even If n is even then there exists an integer m for which n 2gtltm n2 therefore would equal 2gtltm2 4gtltm2 which must be even CSCI 1900 7 Discrete swuctures Methods omeofr Page 15 ta uto Proof by Contradiction Another method of proof is to use the logy P 3 Q A quot1 3 NP The form ofthe proof is P 3 q 3 p CSCI 1900 7 Discrete structures Methods omeofr Page 17 Proof by Contradiction continued p q p Nq P3CI Np ommcq q Nq Np T T T F F F T T F F T F F T F T T F F T T F F T T T T T CSCI 1900 7 Discrete swuctures Methods omeofr Page 18 Proof by Contradiction continued The best application for this is where you cannot possibly go through a large number such as infinite of cases to prove that every one is true Memods oerore Page 19 CSCI 1900 7 Discrete structures Proof by Contradiction Example Prove that x2 is irrational ie cannot be represented with mn where m and n are integers p 2 is a rational number q There exists integers m and n for every rational number such that the rational number can be expressed as mn p 3 q If 2 is a rational number then we can find m and n The goal is to prove that we cannot find an m and an n ie q is true CSCI 1900 7 Discrete swucturas Methods oerore Page 20 Proof by Contradiction Example continued Assume mm2 2 and that m and n are in their most reduced form This means that m2 2n Therefore m must be even and m2 must contain 22 Therefore n must be even too Therefore mm is not in the most reduced form we can pull a 2 out of both m and n This is a contradiction Cannot come up with m and n ie q IS rue Therefore p is true and 2 must not be a rational number CSCI 1900 7 Discrete structures Memods oerore Page 21 CSCI 1900 Discrete Structures Graphs and Finite State Machines R ading Kolman Sections 81 and 103 cscr W age 1 State Machines A machine that has input an internal memory that can keep track of information about the input history and an optional output is called a state machine Paraphrased from textbook p o The complete internal condition of the state machine and all of its memory at any particular time is said to constitute the state of the machine at that time Quoted from textbook p cscr W rscrete sumruns Bags 2 More Informal Definition ofa State The current condition of any machine is defined by certain properties including the inputs that brought the machine to this state the current output of the machine and the response the machine will have to new inputs These conditions are referred to as states cscr W age J Finite State Machine Assume that we have a finite set of states that a machine can be in S and a finite set of possible inputs to that machine I o A machine is a Finite State Machine FSM if when any input from the setI is input to the machine causing it to change state the state it changes to will be contained in the finite set of states S cscr W rscrete sumruns Dag Real World Examples All ofthe math aside many common items or even nontechnical tasks can be modeled with a finite state machine Examples Soda machine Software applications Spell checker Driving to schoolwork cscr W age 5 Example Soda Vending Machine Assume a soda vending machine that accepts only nickles dimes and quarters sells only one kind of soda for 25 a piece Identify all of the possible states 0 no money at all waiting for any money 5 10 15 and 20 some money but not enough waiting for coin return or more money 25 30 35 40 and 45 enough money waiting for select button or coin return button Finite states 10 and finite inputs 5 10 25 select button and coin return button cscr W rscrete sumruns Bags 5 Soda Machine Block Diagram Nickles 4 Dirnes Soda 439 Seda ouarters Machine Select Elutturi 4gt Change Cuin Return CSCI W age 7 State Transitions A state transition is the definition of the destination state based on the current state and the system input A state transition must be defined for every input out of every state Exactly one destination state is defined for every allowable input Example In testing software for quality control every possible user input from every possible state must be considered even if the input makes no sense In addition no user input can take the system to more than one state CSCI W iscrete sumruns Bags 8 State Transition Functions The function fx that defines which state the machine will go to after an input x is called the state transition function Denoted fxs where x denotes the input and 5 denotes the current state Example lfthe soda machine is in the state representing 10 received inserting a nic e will move it to the state representing 15 received fNickle10 15 5 CSCI W age 9 Set of State Transitions Relation Since the state transition function defines every transition of an FSM a set of tuples of the form sm s can be created where sm is the state where a transition starts and SN is the state where that transition ends Assume a relation RM is the set of tuples described above A SM then can be defined as the set of all states S the set of inputs 1 and the relation defining the state transitions RM RM SmfsmX V x e and V sm 6 S 555 W e a u State Transistion Table A table summarizing all of the state transitions of a finite state machine is called a state transition table Each row of a state transition table represents the current state while the columns for that row show the destination or next states based on different possible inputs 555 w a Soda Machine State Transition Table Current I Nickle Dirne ouarter Select cein return ate b bull u 5 1 in 1 25 1 u u 4 5 iti 1 i5 1 3ti 1 5 u 4 iu i5 1 zn 1 35 1 iu u 4 i5 2ti 1 25 1 4n 1 i5 u 4 2u 25 1 3n 1 45 1 2u u 4 25 25 2 25 2 25 2 ti 3 u 4 3u 3ti 2 3n 2 3ti 2 ti 3 u 4 35 35 2 35 2 35 2 ti 3 u 4 4u 4n 2 4n 2 4n 2 ti 3 u 4 45 45 2 45 2 45 2 El 3 u 4 i 3 2 7 Any money inserted is returned LAii inserted money is returned 555 W e a e FSM Labeled Digraph Since a relation RM can be defined for an FSM using a state transition function then a digraph can be created to represent the relation It must be a labeled digraph to indicate which input specifies which transition c t sutrarteen a b RM Soy50 so Sow1150 Si Sir 50 52 51 52 SD Sivfb51 so 52 Si 52 Sh52 Si Szv 52 52 FSM Labeled Digraph continued 555 W a a u Soda Machine Digraph Seiect button transitions are missing Coin return button 555 w a CSCI 1900 Discrete Structures Combinations Reading Kolman Section 32 CSCI 1900 7 Discrete structures Combmatlors 7 Page 1 Order Doesn t Matter In the previous section we looked at two cases where order matters Multiplication Principle duplicates allowed Permutations duplicates not allowed CSCI 1900 7 Discrete swuctures Combinanons 7 Page 2 Order Doesn t Matter Duplicates Not Allowed What if order doesn t matter for example a hand of cards in poker Example the elements 6 5 and 2 make six possible sequences 652 625 256 265 526 and 562 o If order doesn t matter these six sequences would be considered the same CSCI 1900 7 Discrete structures Combmatlors 7 Page J Removing Order from Order Notice the example given on the previous slide ofthe possible sequences involving the elements 6 5 and 2 The number of arrangements of 6 5 and 2 equals the number of ways three elements can be ordered ie 3P3 3Pe 333 61 6 CSCI 1900 7 Discrete swuctures Combinanons 7 Page 4 Removing Order from Order continued Assume that we came up with the number of permutations of three elements from the ten decimal digits mF g 10103107 720 Each subset of three integers from the ten decimal digits would produce 6 sequences Therefore to remove orderfrom the 720 sequences simply divide by 6 to get 120 CSCI 1900 7 Discrete structures Combmatlors 7 Page 5 Combinations of 3 Digits m2 D27 D48 123 139 lEB 247 289 BBB 47B CSCI 1900 7 Discrete swuctures Combinanons 7 Page is Combinations Notation NC is called number of combinations of n objects taken rat a time NC nr n r Example How many 5 card hands can be dealt from a deck of 52 C5 525 52 5 Example Pick 3 horses from 10 to place in any order Why are these examples different How many ways can a pair ofdice come up How many dominoes are there in a pack CSCI 1900 7 Discrete structures Combmatlors 7 Page 7 Order Doesn t Matter Duplicates Allowed Assume you are walking with your grocery cart past the 2 liter sodas in Walmart You need to pick up 10 bottles out of Coke Sprite Dr Pepper Pepsi AampW Root Beer CSCI 1900 7 Discrete swuctures Combinanons 7 Page 8 Buying Sodas You can define how you selected the sodas with a binary string of ones and zeros A one indicates you have selected a soda from that category A zero says that you have moved onto the next category CSCI 1900 7 Discrete structures Combmatlors 7 Page 9 Buying Sodas continued Muvedtu Dr Pepper Moved to Moved to Moved to Last 1539 5 Sprites F39Epsl AampW unnecessary i l i 1 1 0 0 1 1 1 0 1 1 0 1 1 1 2 Cake 3 Dr 2 Pepsi 3AampW s vvere Sprites Peppers were were picked vvere were picked picked picked picked CSCI 1900 7 Discrete swuctures Commnanors 7 Page 10 Buying Sodas continued This means that a binary pattern of 10 5 1 14 ones and zeros can be used to represent a selection of 10 items from 5 possibilities without worrying about order and allowing duplicates This is the same as having 14 elements from which we will select 10 to be set as one ie 14c10 141014101001 CSCI 1900 7 Discrete structures Combinanons 7 Page 1 1 Order Doesn t Matter Duplicates Allowed The general formula for order doesn t matter and duplicates allowed for a selection of r items from a set of n items is nr 1Cr CSCI 1900 7 Discrete swuctures Commnanors 7 Page 12 CSCI 1900 Discrete Structures Searching Trees Reading Kolman Section 73 cscr 1900 7 Discrete structures Searching nees 7 Page 1 Tree Searching Trees can represent the organization of elements but they can also represent a process with each vertex specifying a task Forloop example 5 array1 7 1M1 3 Mathematical expression from section 72 each vertex represents a computation that combines its offspring cscr 1900 7 Discrete swuctures searching Trees 7 Page 2 Terminology Visiting a vertex the act of performing a task at a vertex eg perform a computation or make a decision Searching the tree the process of visiting each vertex in a specific order or path The term searching can be misleading Just think of it as traversing the tree cscr 1900 7 Discrete structures Searching nees 7 Page 1 Tree Search The application of some trees involves traversing the tree in a methodical pattern so as to address every vertex Our book uses the term search but sometimes search can imply we re looking for a particular vertex This is not the case Example Assume we want to compute the average age maximum a e and minimum age ofall of the children from five families Tree is on next slide cscr 1900 7 Discrete swuctures searching Trees 7 Page 4 Search Example families Tayrur LEIrl karen Mike agel ag24 agel4 agEE Phil Lexi Elan Ben agEE agEZ agElZ agEZ Searching nees 7Page 5 kary Tummy age 3 age 5 cscr 1900 7 Discrete structures Search Example continued To calculate the average max and min ages for all ofthe children we need to have a method for going through the tree so that we don t miss a child By defining a rigorous process not only can a human be sure not to miss a vertex but also an algorithm can be defined for a computer cscr 1900 7 Discrete swuctures searching Trees 7 Page is A Suggested Process for Searching a Tree 1Starting at the root repeatedly take the leftmost untraveled edge until you arrive at a leaf which should be a child 2 Include this child in the average max and min calculations 3 One at a time go back up the edges until you reach a vertex that hasn t had all of its outgoing edges traveled 4 If you get back to the root and cannot find an untraveled edge you are done Otherwise return to step 1 CSCI 1900 7 Discrete structures Searching hees e Page 7 Vertices Numbered in Order of Visits Neighborhood famlllES CSCI 1900 7 Discrete swucturs searching Trees 7 Page 8 Preorder Search This methodical pattern of traversing a tree is called a preorder search Assume v is the root of a binary positional tree T Each vertex ofthis tree has at most a lett vertex vL and a right vertex vR If eithervL orvR have ofSpring then they are subtrees of T and a search can be performed ofthem to By viewin a tree this way then the search method we described in earlier slides can be performed using a recursive algorithm applied to each vertex The recursive algorithm is repeatedly applied until every leaf has been reached CSCI 1900 7 Discrete structures Searching hees e Page 9 Vertices Visited in Alphabetical Order Using Preorder Search CSCI 1900 705ch structures searching hes Jaye 11 Preorder Search Algorithm A preorder search of a tree has the following three steps 1 Visit the root 2 Search the left subtree if it exists 3 Search the right subtree if it exists The term search in steps 2 and 3 implies that we apply all three steps to the subtree beginning with step 1 CSCI 1900eDiscrete swucturs searching hes Jaye 10 Prefix or Polish Form Binary tree representing a b x i d 2 2 Preorder search produces X a b i d2 CSCI 1900eDiscrete swucturs searching hes Jaye 12 Polish Form continued Allows us to write complex arithmetic expressions without using parenthesis Expression is evaluated by performing following steps Move left to right until you find a string of the form ny where F is the symbol for a binary operation and x and y are numbers Evaluate x Fy and substitute answer for string Fx Repeat starting at beginning of string again CSCI 1900 7 Discrete Structures searching hes e Page 11 Polish Form Example 1 gtlt 64522 1S pattern 64 2 gtlt2522 2quot pattern22 3 gtlt251 3rd pattern51 4 gtlt26 4m patterngtlt26 5 12 6 4gtlt52212 CSCI 1900 7 Discrete sumturs searching hes e Page 14 lnorder and Postorder Searches Preorder search gets its name from the fact that the operator that joins two items is evaluated first eg the binary operation 6 4 is visited in the order 6 4 lnorder search evaluates the expression as it is written eg the binary operation 6 4 is visited in the order 6 4 Postorder search evaluates the operator after the elements are read eg the binary operation 6 4 is visited in the order 6 4 CSCI 1900 ensues Structures searching hes Jaye 1s lnorder Search Algorithm An lnorder search of a tree has the following three steps 1 Search the left subtree if it exists 2 Visit the root 3 Search the right subtree if it exists CSCI 1900eoiscrete sumturs searching hes Jaye 1s Postorder Search Algorithm A postorder search of a tree has the following three steps 1 Search the left subtree if it exists 2 Search the right subtree if it exists 3 Visit the root CSCI 1900 ensues Structures searching hes Jaye 17 Evaluation of Tree Using lnorder Search Resulting string DCBFEGAIJHKL CSCI 1900eoiscrete sumturs searching hes Jaye 1s Evaluation of Tree Using Postorder Search Resulting string DCFGEBJILKHA CSCI 1900 7 Discrete Structures searching hes 7 Page 19 Postfix or Reverse Polish Form Binary tree representing a b x c d 2 2 Inorder search produces a b 1 d2 X Infix Form Binary tree representing a b x 1 d 2 Inorder search produces a b X c d 2 Unfortunately without parenthesis we can t o anything with this expression CSCI 1900 7 Discrete sumturs searching hes 7 Page 20 Reverse Polish Form continued Allows us to write complex arithmetic expressions without using parenthesis Expression is evaluated by performing following steps Move left to right until you find a string of the form XyF where F is the symbol for a binary operation and X and y are numbers Evaluate X Fy and substitute answer for string X F Repeat starting at beginning of string again CSCI 19007Drscrete sumturs searching hes 7Page 22 CSCI 1900 7Discrete Structures searching hes 7Page 21 Reverse Polish Form Example From lefttoright evaluate xyF first 1 21 342x 1S pattern121 21342x 2quotdpattern42 3 132gtlt 3 dpattern132 4 15X 4 hpattern115x 55 2 1x3425 CSCI 1900 7Discrete Structures searching hes 7Page 21 Converting an Ordered ntree to a Positional Binary Tree An ordered ntree where some vertices have more than two offspring can be converted to a positional binary tree This allows easier computer representation with methods such as linked lists A process exists forthis conversion that works on any finite tree CSCI 19007Drscrete sumturs searching hes 7Page 24 Process to Convert Ordered ntree to Positional Binary Tree Starting at the root the first or A leftmost offspring of a vertex remains the leftmost vertex in the binary tree The first sibling to the right of the leftmost vertex becomes the right offspring of the leftmost vertex Subsequent siblings ecome the right offspring in succession until last sibling is converted CSCI 1900 7 Discrete Structures searching nees 7 Page 25 Conversion Example CSCI 1900 7 Discrete sumruns searching nees 7 Page 26 Conversion Example Preorder search Le tree ABEFCGJKLHD Right tree ABEFCGJKLHD CSCI 1900 705ch Structures searching nees 7Page 27 CSCI 1900 Discrete Structures Functions Reading Kolman Section 51 CSCI 1900 7 Discrete structures Funcnoris 7 Page 1 Domain and Range of a Relation The following definitions assume R is a relation from A to B DomR subset ofA representing elements of A the make sense for R This is called the domain of R RanR subset of B that lists all second elements of R This is called the range of R CSCI 1900 7 Discrete swuctures Funcnoris 7 Page 2 Functions A function fis a relation from A to B where each element ofA that is in the domain off maps to exactly one element b in B Denoted fa b o If an element a is not in the domain off then fa Q CSCI 1900 7 Discrete structures Funcnoris 7 Page 1 Functions continued Also called mappings or transformations because they can be viewed as rules that assign each element ofA to a single element of B E Elem ents Elem ents of B of A CSCI 1900 7 Discrete swuctures Funcnoris 7 Page 4 Functions continued Since fis a relation then it is a subset of the Cartesian Product A X Even though there might be multiple sequence pairs that have the same element b no two sequence pairs may have the same element a CSCI 1900 7 Discrete structures Funcnoris 7 Page 5 Functions Represented with Formulas It may be possible to represent a function with a formula Example fx x2 mapping from Z to N Since function is a relation which is a subset of the Cartesian product then it doesn t need to be represented with a formula A function mayjust be a list of sequenced pairs CSCI 1900 7 Discrete swuctures Funcnoris 7 Page is Functions not Representable with Formulas Example A mapping from one finite set to another Aa b c d and B 4 6 7 a 3 4 b16l016ldl 4 Example Membership functions fa 0 if a is even and 1 if a is odd A 2 and B 01 CSCI 1900 7 Discrete structures Funcnoris 7 Page 7 Examples of Labeled Digraphs Distances between cities vertices are cities edges are distances between cities Organizational Charts vertices are employees Trouble shooting flow chart State diagrams CSCI 1900 7 Discrete structures Funcnoris 7 Page 9 Identity function The identity function is a function on A Denoted 1A Defined by 1Aa a 1A is represented as a subset of A x A with the identity matrix CSCI 1900 7 Discrete structures Funcnons 7 Page 1 1 Labeled Digraphs A labeled digraph is a digraph in which the vertices or the edges or both are labelled with information from a set A labeled digraph can be represented with functions CSCI 1900 7 Discrete smictures Funcnoris 7 Page 8 Labeled Digraphs continued If V is the set of vertices and L is the set of labels of a labelled digraph then the labelling of V can be specified by a function f V 9 L where for each v e V fv is the label we wish to attach If E is the set of edges and L is the set of labels of a labelled digraph then the labelling of Ecan be specified to be a function g E 9 L where for each e e E ge is the label we wish to attach to v CSCI 1900 7 Discrete smictures Functions 7 Page 10 Composition If f A 9 B and g B 9 C then the composition of fand g 9 7 is a relation Let a e Domg f g fa gala lf fa maps to exactly one element say b E B then 9fa 91 lfgb also maps to exactly one element sayc E C a c Thus for each a E A g fa maps to exactly one element ofC and g f is a function CSCI 1900 7 Discrete smictures Functions 7Page 12 Special types of functions fis everywhere de ned if Domf A fis onto if Ranf B fis onetoone if it is impossible to have fa fa39 if a e a39 ie if fa fa39 then a a39 o f A 9 B is invertible if its inverse function fquot is also a function Note 1 quot is simply the reversing ofthe ordered pairs CSCI 1900 7 Discrete structures Funcnons e Page 11 Theorems of Functions Let 1 A9 B be a function iquot1 is a function from B to A if and only if fis onetoone If fquot is a function then the function iquot1 is also onetoone fquot is everywhere defined if and only if fis onto fquot is onto if and only if fis everywhere defined CSCI 1900 7 Discrete swuctures Functions 7 Page 14 Another Theorem of Functions If fis everywhere defined onetoone and onto then fis a onetoone correspondence between A amp B Thus fis invertible and iquot1 is a onetoone correspondence between B amp A CSCI 1900 7 Discrete structures Funcnons e Page 15 More Theorems of Functions Let fbe any function 1B 7 f f 1A f o If fis a onetoone correspondence between A and B then 2 1 7 1A 7 2 1 15 Let f A 9 B and g B 9 C be invertible 9 2 is invertible 9 0quot 0 g39l CSCI 1900 7 Discrete swuctures Functions 7 Page 15 Finite sets Let A and B both be finite sets with the same number of elements If f A 9 B is everywhere defined then If fis oneto one then fis onto If fis onto then fis onetoone CSCI 1900 7 Discrete structures Funcnons e Page 1 7 CSCI 1900 Discrete Structures Integers Reading Kolman Section 14 CSCI 1900 7 Discrete structures Integers 7 Page 1 Divisibility If one integer n divides into a second integer m without producing a remainder then we say that n divides m Denoted n m o If one integer n does not divide evenly into a second integer m ie mn produces a remainder then we say that n does not divide m Denoted ner CSCI 1900 7 Discrete swuctures Integers 7 Page 2 Some Properties of Divisibility If n m then there exists a q such that m qxn The absolute values of both q and n are less than the absolute value of m ie n lt m and q lt m Examples 4 24 24 4x6 and both 4 and 6 are less than 24 5135135 5x27 and both 5 and 27 are less than 135 Simple properties of divisibility proofs on page 21 lfalbanda cthena lfalbanda cwherebgtcthen abc faboracthenabc lfabandbcthenac CSCI 1900 7 Discrete structures Integers 7 Page 1 Prime Numbers A number p is called prime ifthe only positive integers that divide p are p and 1 Examples of prime numbers 2 3 5 7 11 and 13 There is a science to determining prime numbers The following slides present some computer algorithms that can be used to determine if a number ngt1 is prime CSCI 1900 7 Discrete swuctures Integers 7 Page 4 Basic Primer Number Algorithm 1 First check if n2 If it is n is prime Otherwise proceed to step 2 Checkto see if each integer k is a divisor of n where 1ltkn1 If none of the values of k are divisors of n then n is prime M CSCI 1900 7 Discrete structures Integers 7 Page 5 Better Prime Number Algorithm Note that if nmk then either m or k is less than xn Therefore we don39t need to check for values of k greater than xn 1 First check if n2 If it is n is prime Otherwise proceed to step 2 2 Check to see if each integer k is a divisor of n where 1ltk n If none of the values of k are divisors of n then n is prime CSCI 1900 7 Discrete swuctures Integers 7 Page is Even Better Prime Number Algorithm Note that if k n and k is even then 2 n Therefore if 2 does not divide n then no even number can be a divisorof n lfa b and b c then a c 1 First check if n2 If it is n is prime Otherwise proceed to step 2 2 Check if 2 n If so n is not prime Otherwise proceed to step 3 3 Check to see if each odd integer k is a divisor of n where 1ltk5 n If none of the values of k are divisors of n then n is prime CSCI 1900 7 Discrete structures Integers 7 Page 7 Even2 Better Prime Number Algorithm Note that if k n and d k then d n Therefore if d does not divide n then no multiple of d can be a divisor of n 1 First check if n2 If it is n is prime Otherwise proceed to step 2 Use a sequence k 235 7 11 13 17 up to xn to check if k n If none are the values of k are divisors of n then n is prime Note that list is a list of prime numbers N CSCI 1900 7 Discrete swuctures Integers 7 Page 8 Factoring a Number into its Primes Dividing a number into its multiples over and over again until the multiples cannot be divided any longer shows us that any number can eventually be broken down into prime numbers Examples 9 33 32 24 83 2223 233 315 3105 3335 3357 3257 Basically this means that any number can be broken into multiples of prime numbers CSCI 1900 7 Discrete structures Integers 7 Page 9 Factoring into Primes continued Each row ofthe table below presents a different number factored into its primes The numbers in the columns representt e number ofeach particular prime can be factored out ofeach original value 2 3 5 7 11 13 17 5 40 2 3 1 0 0 0 0 85 0 0 1 0 0 0 1 96 5 1 0 0 0 0 0 3 1 5 0 2 1 1 0 0 0 CSCI 1900 7 Discrete swuctures Innegeis 7 Page 10 Factoring into Primes continued Every positive integer n gt 1 can be broken into multiples of prime numbers n p1k1p2k2p3k3p4k4 psks P1ltP2ltP3ltp4ltltps Methods for Factoring 2 n 9 If least significant digit of n is divisible by 2 ie n is even then 2 divides n 3 n 9 If the sum of all the digits of n down to a single digit equals 3 6 or 9 then 3 divides n Forexample is 17587623 divisible by 3 1758762339 3912 1239YESI 3divides17587623 CSCI 1900 7 Discrete structures Integers 7 Page 1 1 CSCI 1900 7 Discrete swuctures Innegeis 7 Page 12 Methods for Factoring continued Does 7 divide n Remove least significant digit one s place from n and multiply it by two Subtract the doubled numberfrom the remaining digits lf result is divisible by 7 then original number was divisible by 7 Repeat if unable to determine from result CSCI 1900 7 Discrete structures Integers e Page 11 Methods for Factoring continued Examples of checking for divisibility by 7 o18769187 12175917 107 49239492 6486948 1236x 34461 a 3446 2 3444 a 344 8336933 1221 CSCI 1900 7 Discrete swuctures Innegers e Page 14 Methods for Factoring continued Does 11 divide n Starting with the most significant digit of n adding the first digit subtracting the next digit adding the third digit subtracting the fourth and so on If the result is 0 or a multiple of 11 then the original number is divisible by 11 Repeat if unable to determine from result CSCI 1900 7 Discrete structures Integers e Page 15 Methods for factoring continued Examples of checking for divisibility by 11 o28531167061192 85 31 16 70 61 1 27904892 79 04 80 CSCI 1900 7 Discrete swuctures Innegers e Page 15 Methods for Factoring continued Does 13 divide n Delete the last digit one s place from n Subtract nine times the deleted digit from the remaining number If what is left is divisible by 13 then so is the original number Repeat if unable to determine from result CSCI 1900 7 Discrete structures Integers e Page 1 7 General Observation of Integers If n and m are integers and n gt 0 we can write m qn rfor integers q and rwith 0 5 r lt n o For specific integers m and n there is only one set of values for q and for r fr 0 then m is a multiple of n ie n m CSCI 1900 7 Discrete swuctures Innegers e Page 18 Examples of m qn r Ifn is3and m is 16 then 1653 1 so q5andr1 lfnis10andmis3then30103so q0andr3 lfnis5andmis 11then 11 35 4soq 3andr4 integers 7 Page 19 CSCI 1900 7 Discrete structures GCD Example Find the GOD of 540 and 315 54022335 315 32 5 7 540 and 315 share the divisors 3 32 5 35 and 325 Look at it as the number of possible ways to combine 3 3 and 5 The largest is the GOD 9 325 45 31545 7 and 5404512 Greatest Common Divisor lfa b and kare in Z and k aand k b we say that k is a common divisor Ifd is the largest such k d is called the greatest common divisor GCD dis a multiple of every k ie every k divides d CSCI 1900 7 Discrete suuctures Irinegers 7 Page 20 Theorems of the GOD Assume dis GCDa b d sa tb for some integers s and t s and t are not necessarily positive lf c is any other common divisor of a and b then c d lfd is the GCDa b then d a and d b Assume d is the GCDa b If c a and c b then c d There is a horrendous proof of these theorems on page 22 of our textbook You are not responsible for this proof integers 7Page 22 CSCI 1900 7 Discrete structures Integers 7 Page 21 GCD Theorem If a and b are in Z agtb then GCDab GCDa aib lf c divides a and b it divides aib this is from the earlier divides theorems Since b aab aab then a common divisor of a and aib also divides a and b Since all c that divide a or b must also divide b and bia then they have the same complete set of divisors and therefore the same GCD CSCI 1900 7 Discrete structures Integers 7 Page 21 CSCI 1900 7 Discrete suuctures Euclidean Algorithm The Euclidean Algorithm is a recursive algorithm that can be used to find GCD a b It is based on the fact that for any two integers a gt b there exists a k and rsuch that a kb r Since ifa b and a c then a b c then we know that the GOD ab must also divide r Therefore the GOD ab GCDbr CSCI 1900 7 Discrete suuctures Irinegers 7 Page 24 Euclidean Algorithm Process Fortwo integers a and b where a gt b gt 0 a kb r where k is inZand 0 r lt b If r 0 then b a and bthe is GCDa b If r I 0 then if some integer n divides a and b then it must also divide r Similarly if n divides and r then it must divide a Go back to top substituting b for a and r for b Repeat until rn 0 and kn will be GCD CSCI 1900 7 Discrete structures Integers e Page 25 Least Common Multiple Ifa b and kare in Z and a k b k we say that k is a common multiple of a and b The smallest such k call it c is called the least common multiple or LCM of a and b We write c LCMab CSCI 1900 7 Discrete swuctures Innegers e Page 26 Deriving the LCM We can obtain LCM from a b and GCDab For any integers a and b we can write a p l p2a2 mpkak and b p1b1p2b2mpkbk GCDaYb p1mlnalbl p2rnlria2b2 pkrnlnakbk LenNab meaxalbl pZmaxa2b2 pkrnaxakbk Sine lt Ekggmaybchnlab menial p2aZb2 a Pi P1 P252 p2b2 mpkak pkbk a Therefore LCMab abGCDab CSCI 1900 7 Discrete structures Integers e Page 27 Modn function If 2 is a nonnegative integer the modn function fnz is defined as fnz rif z qn r For example f314 2 because 14 43 2 f7153 6 because 153 217 6 CSCI 1900 7 Discrete swuctures Innegers e Page 28 Representation of integers We are used to decimal but in reality it is only one of many ways to describe an integer We say that a decimal value is the base 10 expansion of nquot or the decimal expansion of nquot If bgt1 is an integer then every positive integer n can be uniquely expressed in the form n dkbk dwbM dmbKZ dbl dob0 where05dlt b i0 1 k CSCI 1900 7 Discrete structures Integers e Page 29 Proof that There is Exactly One Base Expansion Proof is on bottom of page 27 Basis of proof is that n dkbk r If dk gt b then k was not the largest non negative integer so that bk 5 n If r b then dk isn t large enough Go back to 1 replacing n with r This time remember that k k1 because rmust be less than bk Repeat until k0 CSCI 1900 7 Discrete swuctures Innegers e Page 30 Quick way to determine base b expansion of n Note that do is the remainder after dividing n by b Note also that once n is divided by b quotient is made up of nrb dobw dwbh2 dmbh3 d1 Therefore we can go back to step 1 to determine 1 CSCI 1900 7 Discrete structures Integers e Page 11 Example Determine base 5 expansion of decimal 432 432 865 2 remainder is do digit 86 175 1 remainder is d1 digit 17 35 2 remainder is d2 digit 3 0 5 3 remainder is d3 digit 43210 32125 Verify this using powers of 5 expansion 32125 353 252 151 250 3125 225 15 21 375 50 5 2 423 CSCI 1900 7 Discrete swuctures Innegeis e Page 2 Example Determine base 8 expansion of decimal 704 704 888 0 remainder is do digit 88 118 0 remainder is d1 digit 11 18 3 remainder is d2 digit 1 08 1 remainderis d3 digit 70410 13008 Verify this using powers of 8 expansion 32125 183 382 081 080 1512 364 08 01 512 192 7041o CSCI 1900 7 Discrete structures Integers e Page 11 CSCI 1900 Discrete Structures Properties of Relations Reading Kolman Section 4142 cscr 1900 7 Discrete structures Reranoris 7 Page 1 Cartesian Product If A1 A2 Am are nonempty sets then the Cartesian Product ofthem is the set of all ordered mtuples a1 a2 am where ai e A i 1 2 m Denoted A1gtlt A2gtlt gtlt Am a1 a2 am ai e A i 1 2 m cscr 1900 7 Discrete swuctures Reranons 7 Page 2 Cartesian Product Example IfA1 2 3and Ba b c findAx B o A X B 1 a 1b 1 c 2a 2b 20 38 3J3 30 cscr 1900 7 Discrete structures Reranoris 7 Page 1 Using Matrices to Denote Cartesian Product For Cartesian Product of two sets you can use a matrix to find the sets Example Assume A 1 2 3 and B a b c The table below represents A X B a b c 1 11a 11b 10 2 21a 2 b 2 C 3 31a 3 b 3 C cscr 1900 7 Discrete swuctures Reranons 7 Page 4 Cardinality of Cartesian Product The cardinality ofthe Cartesian Product equals the product ofthe cardinality of all of the sets A1xA2xxAmA1A2Am cscr 1900 7 Discrete structures Reranoris 7 Page 5 Subsets ofthe Cartesian Product Many ofthe results of operations on sets produce subsets of the Cartesian Product set Relational database Each column in a database table can be considered a set Each row is an mtuple of the elements from each column or set No two rows should be alike cscr 1900 7 Discrete swuctures Reranons 7 Page is Relations A relation R is a subset of a Cartesian Product that uses a definition to state whether an mtuple is a member of the subset or not Terminology Relation R fromA to B R g A X B Denoted x R y where x e A and y e B and x has a relation with y o If x does not have a relation with y denoted ny CSCI 1900 7 Discrete structures Reianoris 7 Page 7 Relation Example A is the set of all students and B is the set of all courses A relation R may be defined as the course is required Paul Giblock R CSCI 2710 Danny Camper at CSCI 2710 CSCI 1900 7 Discrete swuctures Reianoris 7 Page 8 Relations Across Same Set Relations may be from one set to the same set ie A B Terminology Relation R on A R g A X A CSCI 1900 7 Discrete structures Reianoris 7 Page 9 Relation on a Single Set Example A is the set of all courses A relation R may be defined as the course is a prerequisite CSCI 2150 R CSCI 3400 o R CSCI 2150 CSCI 3400 CSCI 1710 CSCI 2910 CSCI 2800 CSCI 2910 CSCI 1900 7 Discrete swuctures Relations 7 Page 10 Example Features of Digital Cameras Megapixels lt2 3 to 4 gt5 battery life lt200 shots 200 to 400 shots gt400 shots optical zoom none 2X to 3X 4X or better storage capacity lt32 MB 32MB to 128MB gt128MB price Z CSCI 1900 7 Discrete structures Reianoris 7 Page 1 1 Digital Camera Example continued Possible relations might be Priced below X above a certain megapixels a combination of price below X and optical zoom of 4X or better CSCI 1900 7 Discrete swuctures Relations 7 Page 12 Theorems of Relations Let R be a relation from A to B and let A1 and A2 be subsets of A 7 Iwa A2 then RA1 RA2 RUM U A2 RUM U RUM RUM A A2 2 RUM o RUM Let R and S be relations from A to B If Ra 8a forall a in A then R S CSCI 1900 7 Discrete structures Reianons 7 Page 1 Matrix of a Relation We can represent a relation between two finite sets with a matrix MR mu where 1 if ai bl e R miquot 0ifaibje R CSCI 1900 7 Discrete swuctures Relations 7 Page 14 Example of Using a Matrix to Denote a Relation Using the previous example where A 1 2 3 and B a b c The matrix below represents the relation R 1 a 1 c 2 c 3 a 31 b a b c 1 1 0 1 2 0 0 1 3 1 1 0 CSCI 1900 7 Discrete structures Reianons 7 Page 15 Digraph of a Relation Let R be a relation on A We can represent R pictorially as follows Each element ofA is a circle called a vertex If a is related to a then draw an arrow from the vertex a to the vertex aJ ln degree number of arrows coming into a vertex Out degree number of arrows coming out of a vertex CSCI 1900 7 Discrete swuctures Relations 7 Page 15 Representing a Relation The following three representations depict the same relation on A 1 3 R 1l 11132131312l3l3 1 0 1 0 0 1 0 1 1 CSCI 1900 7 Discrete structures Reianons 7 Page 1 7 CSCI 1900 Discrete Structures Permutations Reading Kolman Section 31 CSCI 1900 7 Discrete structures Permutatiors 7Page 1 Types of Sequences from a Set There are a number of different ways to create a sequence from a set Any order duplicates allowed Any order no duplicates allowed Order matters duplicates allowed Order matters no duplicates allowed CSCI 1900 7 Discrete structures Permutations 7 Page J Sequences Derived from a Set Assume we have a set A containing n items Examples include alphabet decimal digits playing cards etc We can produce sequences from each of these sets CSCI 1900 7 Discrete swuctures Permutanons 7 Page 2 Classifying RealWorld Sequences Determine size of set A and classify each of the following as one ofthe previously listed types of sequences oFive card stud poker Windows XP CD Phone numbers Key 0 es in a oLlcense plates presidential election Codes for 5digit CSCI door locks oLotto numbers oBinary numbers CSCI 19007Discrete swuctures Permutanons 7Page4 Multiplication Principle of Counting The first type of sequence we will look at is where duplicates are allowed and their order matters Supposed that two tasks T1 and T2 must be performed in sequence If T can be performed in n ways and for each ofthese ways T2 can be performed in n2 ways then the sequence T1T2 can be performed in n1n2 ways CSCI 1900 7 Discrete structures Permutations 7 Page 5 Multiplication Principle continued Extended previous example to T1 T2 Solution becomes n1n2nk CSCI 1900 7 Discrete swuctures Permutanons 7 Page 5 Examples of Multiplication Principle 8 character passwords First digit must be a letter Any character afterthat can be a letter or a number 2636 36 36 36 36 36 36 2037468266496 Windows XP2000 software keys 25 characters of letters or numbers 3625 CSCI 1900 7 Discrete structures Permutations 7 Page 7 More Examples of Multiplication Principle License plates ofthe form ABC 123 2626 26 10 10 10 17576000 Phone numbers Three digit area code cannot begin with 0 Three digit exchange cannot begin with 0 910 10 9 1010 10 10 10 10 8100000000 CSCI 1900 7 Discrete swuctures Permutanons 7 Page 8 Calculation ofthe Number of Subsets LetA be a set with n elements how many subsets does A have Each element may either be included or not included In section 13 we talked about the characteristic function which defines membership in a set based on a universal set Example 3456 A 12 B2 4 6 fA 110000 fE 01 0101 CSCI 1900 7 Discrete structures Permutations 7 Page 9 Calculation ofthe Number of Subsets continued Every subset ofA can be defined with a characteristic function of n elements where each element is a 1 or a 0 le each element has 2 possible values Therefore there are 2 2 2 2 2quot possible characteristic functions CSCI 1900 7 Discrete swuctures Permutations 7 Page 10 Permutations The next type of sequence we will look at is where duplicates are not allowed and their order matters Assume A is a set of n elements Suppose we want to make a sequence S of length rwhere 1 5 r5 n CSCI 1900 7 Discrete structures Permunanons 7 Page 1 1 Multiplication Principle Versus Permutations lf repeated elements are allowed how many different sequences can we make Process Each time we select an element forthe next element in the sequence 8 we have n to choose from This gives us n n n n nr possible hoices CSCI 1900 7 Discrete swuctures Permutations 7 Page 12 Multiplication Principle Versus Permutations continued Suppose repeated elements are not allowed how many different sequences can we make Process The first selection T7 provides n choices Each time we select an element after that Tk where kgt1 there is one less than there was for the previous selection k 1 The last choice T has n r 1 n r 1 choices This gives us nn 1n 2n r 1 CSCI 1900 7 Discrete structures Permunanons e Page 11 Factorial For rn quotP7 nP nn 1n 2 21 This number is also written as n and is read n factorial quotP can be written in terms of factorials nP nn 1n 2n r 1 nn 1n 2 n HP HP nn r Permutations Notation quotP is called number of permutations of n objects taken rat a time Word scramble How many 4 letterwords can be made from the letters in Gllbreath without duplicate letters 9P4 9876 3024 Example how many 4dlglt Ple can be created for the 5 button CSCI door locks 5P4 5432 120 Would adding a fifth digit give us more Ple CSCI 1900 7 Discrete swuctures Permutations e Page 14 Distinguishable Permutations from a Set with Repeated Elements 0 If the set from which a sequence is being derived has duplicate elements eg a b d d g h r r r s t then straight permutations will actually count some sequences multiple times Example How many words can be made from the letters in Tarnoff Problem the f s cannot be distinguished eg aorf cannot be distinguished from aorf CSCI 1900 7 Discrete structures Permunanons e Page 15 Distinguishable Permutations from a Set with Repeated Elements Number of distinguishable permutations that can be formed from a collection of n objects where the first object appears k1 times the second object k2 times and so on is n k1l kzlu k1 wherek1 k2 k1n CSCI 1900 7 Discrete structures Permunanons e Page 1 7 CSCI 1900 7 Discrete swuctures Permutations e Page 15 Example How many distinguishable words can be formed from the letters of JEFF Solution n 4 k 1 ks 1 kf 2 nlkjl kel kfl 4l1l 1l 2 12 List JEFF JFEF JFFE EJFF EFJF EFFJ FJEF FEJF FJFE FEFJ FFJE and FFEJ CSCI 1900 7 Discrete swuctures Permutatlors ePage 1s Example How many distinguishable words can be formed from the letters of MISSISSIPPI Solution n11km1ki4ks4kp2 nlkn ki ks kp Ill1 4 4 2 34650 InClass Exercises How many ways can you sort a deck of 52 cards Compute the number of 4digit ATM PINs where duplicate digits are allowed How many ways can the letters in the word TARNOFF be arranged CSCI 1900 7 Discrete Structures Permunanons e Page 19 CSCI 1900 7 Discrete swunures Permutatms e Page 20 Brain Teaser CSCI 1900 Assume you are driving with your child and Discrete Structures heshe is screaming for the milk out of his happy meal You haven t cleaned out the car in a while so there are 9 milk bottles rolling around on the floorboards under yourfeet one full 8 half full and a bit foul Assuming you can pick up more than one bottle at a time in each hand using your hands as balance scales how many balances will it take for you to find the full bottle Trees Reading Kolman Section 71 CSCI 1900 7 Discrete structures riees 7 Page 1 CSCI 1900 7 Discrete swuctures nees 7 Page 2 Trees Our Definition Trees Their Definition We need a way to describe a tree specifically Let A be a set and let Tbe a relation on A a rooted tree We say that T is a tree if there is a vertex First a rooted tree has a single root v0 which is a v0 with the property that there exists a vertex with absolutely no edges coming into it in unique path in Tfrom v0 to every other degree 0f V0 0 vertex in A but no path frOm V0 to V0 Every othervertex v in the tree has exactly one path to it from v0 indegree of v 1 There may be any number of paths coming out from any vertex Denoted Tv0 Koman Busby and Ross p 254 CSCI 1900 7 Discrete structures riees 7 Page J CSCI 1900 7 Discrete swuctures nees 7 Page 4 Trees Characteristics Examples of Trees lf Tis a relation that is also a tree then T must have the following characteristics There are no cycles in T V0 is the only root ofT Using the definitions given above determine which of the following examples are trees and which are not CSCI 1900 7 Discrete structures riees 7 Page 5 CSCI 1900 7 Discrete swuctures nees 7 Page is Is this a tree mass rPige 7 Is this a tree was csci 1500 4mm Structures rPigeE csci 1300 immmswmms Is this a tree mass rPige 5 Is this a tree Microso s troubleshooting wizard csci 1500 4mm Structures mass 7 Pigs in csci 1300 immmswmms Is this a tree for 1 o o 256 for 3 o to 16 array1j 1000a 3 next next 1 Is this a tree csci 1500 4mm Structures mass 7 Figs 2 TmsrPige M csci 1300 immmswmms Definitions Levels all of the vertices located n edges from v0 are said to be at level n lLevel2 1 iLevel3 cscr 1900 7 Discrete structures Trees 7 Page 11 More Definitions A vertex v is considered the parent of all of the vertices connected to it by edges leaving v o A vertex v is considered the offspring of the vertex connected to the single edge entering v o A vertex v is considered the sibling of all vertices at the same level with the same parent cscr 1900 7 Discrete swucturas Trees 7 Page 14 More Definitions A vertex v2 is considered a descendant of a vertex v1 ifthere is a path from v1 to v2 The height of a tree is the number of the largest level The vertices of a tree that have no offspring are considered leaves lfthe vertices of a level of a tree can be ordered from left to right then the tree is an ordered tree cscr 1900 7 Discrete structures Trees 7 Page 15 More Definitions If every vertex of a tree has at most n offspring then the tree is considered an ntree If every vertex of a tree with offspring has exactly n offspring then the tree is considered a complete ntree When n2 this is called a binary tree cscr 1900 7 Discrete swucturas Trees 7 Page 15 Examples 1 lfthe set A a b c d e represents all of the vertices for a tree T what is the maximum height of T What is the minimum height of T 2 lfthe set A a b c d e represents all of the vertices for a tree T and T is a complete binary tree what is the maximum height of T cscr 1900 7 Discrete structures Trees 7 Page 1 7 More Examples 3 If every path from the root of a complete 4tree has 3 levels how many leaves does this tree have 4 What is n for the following ntree for i O to 256 for j O to 16 arrayij 10001 j next j next 1 cscr 1900 7 Discrete swucturas Trees 7 Page 18 One More Example 5 Let T be a complete ntree with 125 leaves a What are the possible values of n b What are the possible values for the height of T CSCI 1900 7 Discrete Structures nees 7 Page 19 CSCI 1900 Discrete Structures Minimal Spanning Trees Reading Kolman Section 75 cscr W age 1 InClass Exercise A small startup City 1 City 2 Mileage airline wants to Cleveland Philadelphia 400 PFOVld elche to Cleveland Detroit 200 the 5 Cmes m the C eve and Chicago 350 table t0 the r39ght39 C eve and Pittsburg 150 A W39ng f r mult39l le 31iacephia Detroit 600 e 9 39ghtsl 31iacephia Chicago 700 determine all of the direct ights that 1lacephla Pttsburg 300 would be needed in Detroit Chicago 300 order to service a Detroit Pttsburg 300 five cities Chicago Pittsburg 450 Source http vvvvvv usembassymalaysla org mydlstarlEE mml cscr 1900 7 Discrete S ucmrs Minimal Spanning nee 7 Pay 2 Undirected Graph If you recall from our discussion on types of relations a symmetric relation is one that for every relation ab that is contained in R the relation ba is also in R Ifthe relation is represented with a matrix this means that the matrix is symmetric across the main diagonal In the digraph of a symmetric relation every edge is bidirectional ie there is no defined direction cscr W age J Connected Relation A relation is connected if for every a and b in R there is a path from a to b o It is easierto see a connected relation using a digraph than it is to describe in using words Connected NDtCDrlrlEEIEd e 555 m Minimal panting irees e P3994 Spanning Tree Textbook definition If R is a symmetric connected relation on a set A we say that a tree T on A is a spanning tree for R if T is a tree with exactly the same veltices as R and which can be obtained from R by deleting some edges of R p 275 Basically a undirected spanning tree is one that connects all n elements ofA with n1 edges To make a cycle connecting n elements more than n1 edges will be needed Therefore there are no cycles cscr W age 5 Weighted Graph In the past we have represented a undirected graph with unlabeled edges It can also be represented with a symmetric binary matrix 555 m Minimal panting irees e Page 5 Weighted Graph continued By giving the edges a numeric value indicating some parameter in the relation between two vertices we have created a weighted tree Weighted Graph continued We can still use matrix notation to represent a weighted graph Replace the 1 s used to represent an edge with the edges weight A 0 indicates no edge E a ll uaam Ebljuv CSCI W Dage 7 555 m mmma panting trees 7 Page 8 Back to lnClass Exercise Not drawn to scale Detruit Cleveland 433 W F39hlladelphla Chicago 45D 3 F39lttsburg CSCI W Dage 9 Minimal Spanning Tree Assume T represents a spanning tree for an undirected graph The total weight ofthe spanning tree T is the sum of all ofthe weights of all ofthe edges of T o The ones with the minimum total weight are called the minimal spanning trees As suggested by the s in the above definition there may be a number of minimal spanning trees for a particular undirected graph with the same total weight 555 W a Algorithms for Determining the Minimal Spanning Tree There are two algorithms presented in our textbookfor determining the minimal spanning tree of an undirected graph that is connected and weighted Prim s Algorithm process of stepping from vertex to vertex Kruskal s Algoritm searching through edges for minimum weights 555 w a Prim s Algorithm From textbook p 281 Let R be a symmetric connected relation with n vertices 1 Choose a vertex v1 of R Let V vi and E r 2 Choose a nearest neighbor v of Vthat is adjacent to v v e V and for which the edge v v does not form a cycle with members of E Add v to Vand add v vto E Repeat Step 2 until E n 1 Then V contains all n vertices of R and E contains the edges of a minimal spanning tree for R 0quot 555 W a Prim s Algorithm in English The goal is to one at a time include a new vertex by adding a new edge without creating a cycle Pick any vertex to start From it pickthe edge with the lowest weight As you add vertices you will add possible edges to follow to new vertices Pickthe edge with the lowest weight to go to a new vertex without creating a cycle 555 W e a 1 lnClass Exercise 1st edge Pick any starting point Detroit Pick edge with lowest weight 200 Cleveland Detrult ZEIEI Cleveland 555 W e a u lnClass Exercise 2nd edge Pick any edge connected to Cleveland or Detroit that doesn t create a cycle 150 Pittsburg D etru ir Plttsburg 555 W e a lnClass Exercise 3rd edge Pick any edge connected to Cleveland Detroit or Pittsburg that doesn t create a cycle 300 Philadelphia Detreir Phlladelphla Pittsburg 555 W e a lnClass Exercise 4th edge Pick any edge connected to Cleveland Detroit Pittsburg or Philadelphia that doesn t create a cycle 300 Chicago This gives us 4 edges D etru ir Phlladelphla Chlcagu Plttsburg 555 W e a a Kruskal s Algorithm From textbook p 284 Let R be a symmetric connected relation with n vertices and let S 61 e2 e3 ek be the set of all weighted edges of R Choose an edge e in S of least weight Let E e7 Replace S with S e7 Select an edge e in S of least weight that will not make a cycle with members of E Replace Ewith E u e and S with S e Repeat Step 2 until E n 1 N 0 555 W e a a Kruskal s Algorithm in English The goal is to one at a time include a new edge without creating a cycle Start by picking the edge with the lowest weight Continue to pick new edges without creating a cycle Edges do not necessarily have to be connected Stop when you have n1 edges 555 w e a lnClass Exercise 1st edge First edge picked is lowest value of 150 Cleveland to Pittsburg Cleveland F39lttsburg 555 W e an lnClass Exercise 2nd edge Next lowest edge is 200 Cleveland to Detroit Detrult F39lttsburg 555 w e a lnClass Exercise 3rd edge There are a few edges of 300 but Detroit to Pittsburg cannot be selected because it would create a cycle We go with Pittsburg to Philadelphia Detrult F39hlladelphla F39lttsburg 555 W e lnClass Exercise 4th edge The next lowest edge that doesn t create a cycle is 300 edge from Detroit to Chicago This is the 4 h edge D etru it F39hlladelphla Chlcagu F39lttsburg 555 w e 1 CSCI 1900 Discrete Structures Sequences Reading Kolman Section 13 CSCI 1900 7 Discrete structures sequences 7 Page 1 Sequence A sequence is a list of objects arranged in a definite order Difference between set and sequence A set has no order and no duplicated elements A sequence has a specific order and elements may be duplicated Nomenclature a1 a2 a CSCI 1900 7 Discrete swuctures sequences 7 Page 2 Sequence Examples 1 2 3 2 2 3 1 is a sequence but not a set The sequences 1 2 3 2 2 3 1 and 2 2 1 3 are made from elements of the set 1 2 3 o The sequences 1 2 3 2 2 3 1 and 2 1 3 2 2 3 1 only switch two elements but that alone makes them unequal CSCI 1900 7 Discrete structures sequences 7 Page J Types of Sequences Sequence may stop after n steps nite or go on for ever in nite Formulas can be used to describe sequences Recursive Explicit CSCI 1900 7 Discrete swuctures sequences 7 Page 4 Recursive Sequences In a recursive sequence the next item in the sequence is determined from previous values Difficult to determine say 100m element since previous 99 need to be determined first Example a1 1 a2 2 an an1 an2 CSCI 1900 7 Discrete structures sequences 7 Page 5 Explicit Sequences In an explicit sequence the nth item is determined by a formula depending only on n Easier to determine any element Example an 2xn CSCI 1900 7 Discrete swuctures sequences 7 Page is Strings Sequences can be made up of characters too Example W a k e u p Removing the commas and you get a string Wake up Strings best illustrate difference between sequences and sets a b a b a b a is a sequence ie is a string The corresponding set is a b CSCI 1900 7Discrete structures sequences 7 Page 7 Linear Array Principles of sequences can be applied to computers specifically arrays There are some differences though Sequence Wellde ned Modi cation of any element or its order creates new ce Array May not have all elements initialized Modi cation ofarray by so ware may occur Even ifthe array has variable length we re ultimately limited to nite length CSCI 1900 7 Discrete swucturas sequences 7 Page 8 Characteristic Functions A characteristic function is a function defining membership in a set f 1 ifXEA X A o ifxeA Example for the set A 1 4 6 131 1 132 0 133 0 134 1 etc CSCI 1900 7 Discrete structures sequences 7 Page 9 Programming Example Characteristic functions may look unfamiliar but consider the following code if insert conditional statement here retur else return 0 Example A x x gt 4 if x gt 4 return 1 else return 0 CSCI 1900 7 Discrete swucturas sequences 7 Page 10 Properties of Characteristic Functions Characteristic functions of subsets satisfy the following properties proofs are on page 15 of textbook fA B fAfB that is fA Bx fAxfBx for all x Ao B A B that is fAUBx fAx fBx fAxfBx for all x fAB fA f 2fAfB that is fABx fAx fBx 2fAxfBx for all x CSCI 1900 7 Discrete structures sequences 7 Page 1 1 Proving Characteristic Function Properties Alternate way of doing proof is to enumerate all four cases and see how the result comes out Example Prove fAnB fAfB a e B b fAa 0 fBa 0 fAa gtlt fBa 0 X 0 0 fA Ba fAb 0 fBb 1 fAb gtlt fBb 0 X 1 0 fA Bb fAC 1 fBC 0 730 gtlt fBC 1 X 0 0 fA Bc fAd 1 fBd 1 fAd gtlt fBd 1 X 1 1 fA Bd CSCI 1900 7 Discrete swucturas sequences 7 Page 12 Representing Sets with a Computer Rememberthat sets have no order and no duplicated elements The general need to assign each element in a set to a memory location gives it order in a computer We can use the characteristic function to define a set using a computer csci 1900 7 Discrete structures sequences 7 Page 11 Representing Sets with a Computer continued Assume U defines a finite universal set U x X2i X3 i We can use characteristic function to represent subsets of fAx is a sequence of 1 s and Us with the same number of elements as fAx 1 is in position if corresponding element of U x is a membero A fAx 0 is in position if corresponding element of U x is not a membero csci 1900 7 Discrete swuctures sequences 7 Page 14 Representing Sets with a Computer Example 39 U0123456789 fAx101001 1001 39 A0 256 9 csci 1900 7 Discrete structures sequences 7 Page 15 More Properties of Sequences Any set with n elements can be arranged as a sequence of length h but notvice versa This is because sets have no order and duplicates are not allowed Each subset can be identified with its characteristic function as a sequence of 1 s and 0 s Characteristic function for universal set U is a sequence of all ones csci 1900 7 Discrete swuctures sequences 7 Page 15 Countable and Uncountable A set is countable if it corresponds to some sequence Members of set can be arranged in a list Elements have position All finite sets are countable Not all infinite sets are countable and are therefore uncountable Best example is real numbers Eg what comes a er123534 csci 1900 7 Discrete structures sequences 7 Page 1 7 Strings and Regular Expressions Given a set A the set A consists ofall nite sequences of elements 0 Example A alphabet a b c d e f g h i j k l m n o p q r s t u v w x yz Aquot words the nite sequences words in A are not written with commas A contains allpossible words even those that are unpronounceable or make no sense such as prsartkc The empty sequence or emptystring is represented with A csci 1900 7 Discrete swuctures sequences 7 Page 18 Catenation Two strings may be joined into a single string Assume w 3323354sn and w2 1121314tk The catenation of w and w2 is the sequence 5523334snt121314 1k Notation catenation of w and w2 is written as ww2 or ww2 CSCI 1900 7 Discrete structures sequences 7 Page 19 Some Properties of Catenation If ww2 are elements of Aquot then ww2 is an element of Aquot wAwandAww A subset B ofAquot has its own set B which contains sentences made up from the words of A For example B John Jane swims runs well quickly slowly is a subset ofA where A alphabet The element Jane swims quickly is an element of Bquot CSCI 1900 7 Discrete suuctures sequences 7 Page 20 Regular expressions The following is from httpIetextlibvirginiaeduhelpsheetsregexhtml quotRegular expressions trace back to the work ofan American mathematician b the name ofStephen Kleene one ofthe most in uential gures in the developmentoftheoreticalcomputerscience o arches the is formally knovim as a 39Kleene CSCI 1900 7 Discrete structures sequences 7 Page 21 Regular Expressions continued A regular expression on a set A is a recursive formula for a sequence It is made up ofthe elements ofA and the symbols v A The symbol A is a regular expression lfx E A the symbol x is a regular expression lfo and 3 are regular expressions then the expression up is regular lfo and 3 are regular expressions then the expression 0 v 3 is regular lfo is a regular expression then the expression of is regular CSCI 1900 7 Discrete suuctures sequences 7 Page 22 Regular Expressions continued A regular expression overA corresponds to a subset of Aquot This is called a regular subset of Aquot or just regular set These subsets are built based on the rules presented on the next two slides You may want to use page 18 in the textbook as a reference in case I got one of these wrong CSCI 1900 7 Discrete structures sequences 7 Page 21 Rules of Regular Expressions The expression A corresponds to the set A where A is the empty string in Aquot If XeA then the regular expression x corresponds to the set x If on and 3 are regular expressions corresponding to the subsets M and N ofAquot then up corresponds to MN st s e M and t e N Therefore MN is the set of all catenations o strings in Mwith strings in N CSCI 1900 7 Discrete suuctures sequences 7 Page 24 Rules of Regular Expressions continued If the regular expressions on and 3 correspond to the subsets M and N ofAquot then on v 3 corresponds to M u N If the regular expression on corresponds to the subset M of Aquot then 00 corresponds to the set Mquot Note that M is a set of strings from A Elements from M are finite sequences of such strings and thus may themselves be interpreted as strings from A Note also that we always have As M CSCI 1900 7 Discrete Structures sequences 7 Page 25 CSCI 1900 Discrete Structures Logical Operations Reading Kolman Section 21 cscr 19w 7 Discrete structures Logical Operanoris 7 Page 1 Statement of Proposition Statement of proposition a declarative sentence that is either true or false but not both Examples The earth is round statement that is true 235 statement that is true Do you speak English This is a question not a statement cscr 1900 7 Discrete swuctures L ogicar Operanoris 7 Page 2 More Examples of Statements of Proposition 3x5 is a declarative sentence but not a statement since it is true orfalse depending on the value 0 x Take two aspirins is a command not a statement The temperature on the surface of the planet Venus is 800 F is a declarative statement of whose truth is unknown to us The sun will come out tomorrow a statement that is eithertrue orfalse but not both although we will have to wait until tomorrow to determine cscr 19w 7 Discrete structures Logical Operanoris 7 Page 1 Logical Connectives and Compound Statements x y z denote variables that can represent real num ers p q r denote prepositional variables that can be replaced by statements p The sun is shining today q It is cold cscr 1900 7 Discrete swuctures L ogicar Operanoris 7 Page 4 Negation pr is a statement the negation ofp is the statement not p Denoted p pr is true p is false pr is false p is true p is not actually connective ie it doesn t join two of anything not is a unary operation forthe collection of statements and p is a statement ifp is cscr 19w 7 Discrete structures Logical Operanoris 7 Page 5 Examples of Negation pr 23 gt1 then If p 23 1 o If 7 It is cold then q It is not the case that it is cold ie It is not cold cscr 1900 7 Discrete swuctures L ogicar Operanoris 7 Page 5 Conjunction If p and q are statements then the conjunction of p and q is the compound statement p and q Denoted pAq pAq is true only if both p and q are true Example p ETSU parking permits are expensive q ETSU has plenty of parking PAC 7 csci 1900 7 Discrete structures Logical Operanoris 7 Page 7 Exclusive Disjunction If p and q are statements then the exclusive disjunction is the compound statement either p or q may be true but both are not true at the same time Example p It is daytime q It is night time pvq in the exclusive sense 2 cscI 1900 7 Discrete structures Logical Operanoris 7 Page 9 Exclusive versus Inclusive Depending on the circumstances some disjunctions are inclusive and some of exclusive Examples of Inclusive I have a dogquot or l have a cat It is warm outsidequot or It is rainingquot Examples of Exclusive Today is eitherTuesday or it is Thursday Pat is either male orfemale csci 1900 7 Discrete structures L ogicai Operanoris 7 Page 1 1 Disjunction If p and q are statements then the disjunction of p and q is the compound statement p or q Denoted pvq pvq is true if either p or q are true Example p I am a male q lam under 40 years old PVC 7 cscI 1900 7 Discrete swuctures L ogicai Operanoris 7 Page 8 Inclusive Disjunction If p and q are statements then the inclusive disjunction is the compound statement either p or q may be true or they may both be true at the same time Example p It is cold q It is night time pvq in the inclusive sense 2 cscI 1900 7 Discrete swuctures L ogicaI Operations 7 Page 10 Compound Statements A compound statement is a statement made from other statements For n individual propositions there are 2n possible combinations of truth values A truth table contains 2 rows identifying the truth values for the statement represented by the table Use parenthesis to denote order of precedence has precedence over cscI 1900 7 Discrete swuctures L ogicaI Operations 7 Page 12 Truth Tables are Important Tools for this Material CSCI 1900 7 Discrete structures L ogicai Operanoris 7 Page 1 Compound Statement Example I0 A q v p p q qu p pAqvp T T T F T T F F F F F T F T T F F F T T cscr 1900 7 Discrete swuctures L ogicar Operations 7 Page 14 Quantifiers Back in Section 11 a set was defined X PX For an element t to be a member of the set Pt must evaluate to true Px is called a predicate or a propositional function CSCI 1900 7 Discrete structures L ogicai Operanoris 7 Page 15 Computer Science Functions if Px then execute certain steps while Qx do specified actions cscr 1900 7 Discrete swuctures L ogicar Operations 7 Page 15 Universal quanti cation of a predicate Px Universal quantification of predicate Px Forall values ofx Px is true Denoted Vx Px The symbol V is called the universal quantifier The order in which multiple quantifications are considered does not affect the truth value eg Vx Vy Pxy E Vy Vx Pxy CSCI 1900 7 Discrete structures L ogicai Operanoris 7 Page 1 7 Examples Px x x This predicate makes sense for all real num ers x The universal quantification of Px Vx Px is a true statement because for all real numbers x x Qx x1lt4 Vx Qx is a false statement because for example Q5 is not true cscr 1900 7 Discrete swuctures L ogicar Operations 7 Page 18 Existential quanti cation of a predicate Px Existential quantification of a predicate Px is the statement There exists a value of x for which Px is true Denoted 3x Px Existential quantification may be applied to several variables in a predicate The order in which multiple quantifications are considered does not affect the truth value CSCI 1900 7 Discrete structures L ogicai Operanoris a Page 19 Applying both universal and existential quanti cation Order of application does matter Example Let A and B be h x n matrices The statement VA 3B A B In Reads for every A there is a B such that A B I H n Prove by coming up for equations for bH and bU jzi Now reverse the order 3B VA A B In Reads there exists a B such that for all A A B n THIS IS FALSE CSCI 1900 7 Discrete swuctures L ogicai Operations 7 Page 20 Assigning Quanti cation to Proposition Let p Vx Px The negation of p is false when p is true and true when p is false For p to be false there must be at least one value of x for which Px is false Thus p is false if 3x Px is true lf 3x Px is false then for every x Px is false that is Vx Px is true Okay what exactly did the previous slide say Assume a statement is made that for all x Px is true If we can find one case that is not true then the statement is false If we cannot find one case that is not true then the statement is true Example V positive integers n Pn n2 41h 41 is a prime number This is false because 3 an integer resulting in a nonprime value ie in such that Pn is false CSCI 1900 7 Discrete structures L ogicai Operanoris a Page 21 CSCI 1900 7 Discrete swuctures L ogicaI Operations 7 Page 22

### 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

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

#### "I made $350 in just two days after posting my first study guide."

#### "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.