Formal Logic & Discrete Math
Formal Logic & Discrete Math MATH 221
Popular in Course
Popular in Mathematics (M)
This 70 page Class Notes was uploaded by Dr. Cleo Wunsch on Thursday October 15, 2015. The Class Notes belongs to MATH 221 at New Mexico Institute of Mining and Technology taught by Josef Brown in Fall. Since its upload, it has received 12 views. For similar materials see /class/223627/math-221-new-mexico-institute-of-mining-and-technology in Mathematics (M) at New Mexico Institute of Mining and Technology.
Reviews for Formal Logic & Discrete Math
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/15/15
MATH 221 Formal Logic and Discrete Mathematics Debugging is twice as hard as writing the code in the first place Therefore if you write the code as cleverly as possible you are by de nition not smart enough to debug it Brian W Kernighan Table Of Contents Chapter 1 Logic and Proofs 1 Chapter 2 Sets functions and sums 13 Chapter 3 Algorithms the integers and matrices 20 Chapter 4 lnducti on and recursion 35 Chapter 5 Counting 44 Chapter 9 Graphs 50 Chapter 10 Trees 61 Chapter 1 Logic and Proofs Section I Propositional logic proposition a declarative statement that is either true or false but not both p q r s typically represent a proposition Logical Operators negation not p read not p true when p is false connectives conjunction p A q read p and q true when both p and q are true disjunction p v q read p or q true when either p or q are true exclusive or p Bq read p Xor q true when p A q F but p v q T conditional implication p gt q read p implies q true when p F or p A q T biconditional biimplication p gt q read p if and only ifq true when p gt q T and q gt p T Important Conditional Constructs statement p gt q contrapositive q gt p statement p gt q converse q gt p statement p gt q inverse p gt q Order of operations 1 2 3 4v 5 gt 6lt gt Truth Tables Truth tables start with a systematic and exhaustive list of the possible truth values for each proposition typically followed by the resulting truth value of the compound propositions leading ultimately to the nal truth value Example p v q gt r There are three variables simple propositions There is a compound or the negation of r and the complete statement P pvq pvq gt r T T F F F F F T T Bit strings consist of a sequence of 039s and 139s each of which is a bit The length of the string is the number of bits By convention 1 denotes true and 0 denotes false Bitwise operations require stings of the same length the propositions are evaluated on bits in corresponding positions in the strings Example 0 1 1 1 String 1 1 0 1 1 String 2 0 0 1 1 And 1 1 1 1 Or 1 1 0 0 Xor HW 18 rst determine p and q a Promotion p Wash Car q If you want to get promoted then you must wash the boss s car b Winds p thaw q If the winds are from the south then there is a spring thaw c Bought p warranty q If you bought the computer less than a year ago then the warranty is good d Cheats p caught q If Willy cheats then he gets caught e Access p pay q If you access the website then you must pay a subscription fee f Know p elected q Ifyou know the right people then you will be elected g Boat p sick q If Carol is on a boat then she gets seasick 46 13 actual r 11 p gtr39F T p gt r F c enote truth teller and r denote truthful response to question b If a truth teller is asked do you tell the truth the response is yes If a liar is asked the same question the answer will also be yes So ask either one what would you say if I asked you if you tell the truth The truth teller still says yes but the liar must now say no 62 Truth table approach Let each be denoted by their rst initial The rst compound proposition that is false removes that combination bi Q A H K R V KorH RxorV ifAthen R V and K ornotVand not K ithhen A and K Truth T T T T T TRUE FALSE TRUE TRUE TRUE FALSE T T T T F TRUE TRUE TRUE FALSE TRUE FALSE T T T F T TRUE TRUE FALSE TRUE TRUE FALSE T T T F F TRUE FALSE FALSE FALSE TRUE FALSE T T F T T TRUE FALSE TRUE FALSE FALSE FALSE T T F T F TRUE TRUE TRUE TRUE FALSE FALSE T T F F T TRUE TRUE FALSE FALSE FALSE FALSE T T F F F TRUE FALSE FALSE TRUE FALSE FALSE T F T T T TRUE FALSE TRUE TRUE TRUE FALSE T F T T F TRUE TRUE TRUE FALSE TRUE FALSE T F T F T TRUE TRUE FALSE TRUE TRUE FALSE T F T F F TRUE FALSE FALSE FALSE TRUE FALSE T F F T T FALSE FALSE TRUE FALSE TRUE FALSE T F F T F FALSE TRUE TRUE TRUE TRUE FALSE T F F F T FALSE TRUE FALSE FALSE TRUE FALSE T F F F F FALSE FALSE FALSE TRUE TRUE FALSE F T T T T TRUE FALSE TRUE TRUE FALSE FALSE F T T T F TRUE TRUE TRUE FALSE FALSE FALSE F T T F T TRUE TRUE TRUE TRUE FALSE FALSE F T T F F TRUE FALSE TRUE FALSE FALSE FALSE F T F T T TRUE FALSE TRUE FALSE FALSE FALSE F T F T F TRUE TRUE TRUE TRUE FALSE FALSE F T F F T TRUE TRUE TRUE FALSE FALSE FALSE F T F F F TRUE FALSE TRUE TRUE FALSE FALSE F F T T T TRUE FALSE TRUE TRUE TRUE FALSE F F T T F TRUE TRUE TRUE FALSE TRUE FALSE F F T F T TRUE TRUE TRUE TRUE TRUE TRUE F F T F F TRUE FALSE TRUE FALSE TRUE FALSE F F F T T FALSE FALSE TRUE FALSE TRUE FALSE F F F T F FALSE TRUE TRUE TRUE TRUE FALSE F F F F T FALSE TRUE TRUE FALSE TRUE FALSE F F F F F FALSE FALSE TRUE TRUE TRUE FALSE Section 2 Propositional equivalences Compound Proposition is an expression formed from propositional variables and logical operators tautology CP always true contradiction CP always false contingency CP neither a tautology nor a contradiction Logical equivalence occurs when two propositions have the same truth values in all conditions The notation is p E q and a consequence of equivalence is the fact that p gt q is a tautology An equivalent structure for p gt q is p v q which is illustrated in the truth table below V To show that the biconditional of these is a tautology we use the equivalence we just showed Since either both are false in which case the negation of one is sufficient to make an or statement true or both are true in which case the negation of one is not sufficient to make an or statement false Some important logical equivalences Equivalence Name Equivalence Name PATEP pvqerpvqu Identity Associative PVFP pAqArEpqr PVTET pvqArEpvqpvr Domination Distributive pAFF pAquEpAqvpr prEp J pAqE p q pApEp r pvqE p q DeMorgans u up E p Double Negation pVp qE p Ab pquqvp I pAquEp sorptlon Commutat1ve pAqEqu pv pET pA pEF Negation E V PVqE P gtq l7qu P gt 39q p gtq Epwq p gtqp gtr Ep gt qAr p gtqvp gtr Ep gt qu p gtV q gtr E qu gtr p gtV V q gtr E pAq gtr Z7qu P99 q gtP Z7qu PAq EPA 399 Example Showthat p gtq gtr p gtq gtr P q V p gtq gtr p gt q gtr Method 2 use known equivalences p gtq gtrE up gtqvr p gtq gtrE pvq gtr p gtqerpA qvr pvq gtrE pv qu pA qerrvpArv q pv quE pvrv q rv p p39p gtq gtrp gtq gtr HW 57 Assign variables directory database open 9 p monitor in closed state 9 q system in initial state 9 r Write the conditional statement r gt p gt q Write the equivalent with disjunctions and negations r v p v q Translate to English either the system should be in its initial state or the directory database should not be opened or the monitor should be in a closed state But your book really wants a single conditional note where the quotnotquot is If the data base is open then either the system should be in its initial state or the monitor should be put in a closed state TOC Section 3 Predicatcs and quantifich A predicate is an assertion made about a variable which is neither true nor false until a value is assigned to the variable at which time the assertion becomes a logical proposition A propositional function takes the form of a function with a variable for the argument a predicate for the mapping criterion When the variable has been assigned a value the function takes on the value of either True or False Propositional functions may take on more than one variable Quantifiers modify predicates by expressing the extent to which the predicate is to be applied to the domain Two primary quantifiers are the universal denoted v and the existential El The universal quantifier states that the predicate will yield the same output regardless of the input provided the input is valid while the existential quantifier merely claims that there is some valid input which will produce the claimed output The area of logic that treats predicates and quantifiers is called predicate calculus Given a universal quantifier one only needs to find a single counterexample to show that the statement is false Given an existential quantifier a single example suffices to show that the statement is true Quantifiers may be employed to give the exact number of x s which satisfy a propositional function One such is uniqueness it is represented by placing an exclamation mark after the existence symbol When quantifiers are applied to a variable it is said to be bound When not bound a variable is free Statements involving predicates and quantifiers are logically equivalent iff they have the same truth value no matter what 1 J39 are F39 J J and J39 of domain Negation of quantifiers Negation Equivalent ExPx Vx Px VxPx EIx P x HW 12 Qxxlgt2x er a Q0 9T b Q19 T c Q19 F d EIxQx9T e VxQx 9F f EIx Qx 9T g Vx Qx 9F 18 a Elex a P 2vP 1vP0vP1vP2 b VxPx a P 2P lP0PlP2 c EIx Px a P 2v P 1v P0v P1v P2 d Vx Px a P 2A P 1A P0A P1A P2 e ExPx a P 2A P 1A P0A P1A P2 f VxPx a P 2v P 1v P0 v P1v P2 TOC Section 4 Nested quantifiers A quanti er is nested if it is in the scope of another quanti er eg VxElyltx y 0 Order is not commutative Statement Meaning Vx v yP x y PXy is true for all X y Vy v xP x y Vx yP X y For every X there is at least one y which makes PXy true ElJCVJP X y There is at least one X which makes PXy true for every y ElJEDP X y There is at least one X y pair that makes PXy true xy2 F xy yx F y 0 gt xyl F x2y2 2x4y5 F F 39 z xy 2 T 33 Rewrite so negation appears only within predicates a Vx v yPxy E EIxEIy Pxy b VyExPxy E EIny Pxy c VnyPxyv Qxy E EIxEIy Pxy Qxy d ExEly Pxy VxVyQxy E VxVyPxyv EIxEIy Qxy e VxEszPx y z EleyPxyz E ExVyElz Pxyzv VzEIy Pxyz TOC Section 5 Rules of inference An argument is a sequence of statements premises which lead to a conclusion An argument is valid when the truth of the premises assures the truth of the conclusion The notion of an argument form is that the premises are propositions as is the conclusion When the truth of the premises imply the truth of the conclusion it is the form not the assignment of variables that make the argument valid General Inference Rule Tautology Name P P gtq pAp gtq gtq modusponens q q i g A p gt 9 gt 39P modus tollens p P gt q w r 10 gt q q gt 0 gt P gt V hypothetical syllogism p gt r P V q p P V q mp gt q disjunctive syllogism q p P gt p v q addition apvq p A ql gt P simpli cation P q pAq gtP9 conjunction apAq P V q pvqA 39PVV gtQVV resolution aqu Remember that p gt q E p v q This means the implication is true when p is false no matter what value q takes on Assuming that p must be true because q is is a fallacy known as af rming the conclusion By the same token assuming that q must be false because p is false is equally invalid a fallacy known as denying the hypothesis Inference and Quanti ers Rule Name VxPx Pc universal instantiation 136 for an arbitrary 0 universal generalization existential instantiation existential generalization HW 6 Assign variables r 9 it rains f9 it is foggy s 9 sailing race is held 1 9 life saving demo is on and t 9 trophy is awarded Form logical propositions rv f gtSl s gtt t Construct a valid argument 0 V 9f 9 S 1 premise t premise 0 V 9f 9 S simpli cation 0 V 9f 9f premise S at premise u V V 9f E V f modus tollens 0 V 9f 9 I hypothetical syllogism 16 a Let PX mean X is enrolled in the university Let QX mean X has lived in a dormitory VxP x gt Q x Q Mia Universal modus tollens valid P Mia b Let PX mean X is a convertible and QX mean X is fun to drive VxP x gt Qx P Isaac Denying the hypothesis not valid Q Isaac c Let PX mean X is an action movie and QX mean that Quincy likes X VxP x gt Qx QEight Men Out Af rming the conclusion not valid PEight Men Out T 0C Section 6 Introduction to proofs A theorem is a statement which can be proven to be true propositions are theorems considered to be less important A proof for a theorem is a valid argument the conclusion of which establishes the truth of the theorem Often included in proofs are axioms or postulates statements assumed to be true without proof Often these are definitions Complicated proofs are sometimes broken up into smaller proofs modules called lemmas Theorems which can be established as the direct consequence of the truth of another theorem are corollaries and statements which are thought to be true but which are not yet proven are called conjectures The words obviously and clearly should be avoided in a proof They bring no real information to the reader except perhaps some insight into the ego of the author Generally it is neither clear nor obvious but surely we must be in awe of anyone for whom it is Brown 39s Maxim If you have completed more than three steps in a proof with out mentioning a definition you are probably doing it wrong Some forms ofproof for theorems ofthe form VxP x gt Qx Direct Begin by assuming that PX is true and then show that QX must be Show that the sum of two odd integers is even Statement 2 P q is even since 2k j l is even Contraposition A direct proof ofthe contrapositive that is since p gt q E q gt p assume that quotnot qquot is true then show that quotnot pquot must also be true Show that ifn is an integer and n3 5 is odd then n is even n3 5odd gt n even E n odd gt n3 5even n3 5 8k3 12k2 6k 1 5 By de nition of exponents 8kg 12k2 6k 1 5 28k3 12k2 6k 2 Distributive property ofmultiplication over add1tlon 2 8k3 12k2 6k 2 an even integer De nition of even integer 113 5odd gt n even Contraposition Contradiction Assume that what you are trying to prove is false then show that this leads to a contradiction r3rl0 gtr ED Lemma 1 Ifk is an integer then 2k l is odd 2k 1 2k 2 l 2k l 1 Lemma 1 is used in the following Lemmas Lemma 2 If p is an odd integer then pH is an odd integer when n is a positive integer 2k lquot 2kquotMm 12k 12nf22kz4 n2k1quot11quot quot 1 n n by the B1nom1al Theorem But th1s 1s equal to 22 2quotquot 1kquot 1 1 1 whlch 1s odd 10 1 Lemma 3 pr and q are both odd then pq is odd 2k l2j l 2j2k l 2k 1 202k l k 1 which is odd Lemma 4 If p q and r are all three odd integers then the sum of the three is odd 2kl2j l2ml2kj m l 1 Lemma 5 pr is even and q is odd then p q is odd 2k 2j l 2k j 1 both sides Lemmas 2 5 Lemmas 2 5 De nition of odd I p and q are integers but neither odd nor even I I I r e D I I HW 8 Ifn is a perfect square then n 2 is not BWOC 5 n b2 and n 2 a2 where a and b are both integers greater than zero by de nition of perfect square This means a2 b2 2 equivalently a ba b 2 Since n 2 gt n it follows that a gt b so a b is a positive integer as is a b Since 1 and 2 are the only positive integers whose product is 2 a b l and a b 2 But this implies 2a 3 or a 32 which is not an integer T 0C Section 7 Proof methods and strategy Additional methods of proofs Exhaustive proof or proof by cases enumerates every possible configuration that p can take then shows that all of them imply q One of the most important of these is trichotomy the fact that all real numbers belong to one ofthree categories r lt 0 r 0 r gt 0 WLOG without loss of generality is a shortcut that claims when assignment of values is arbitrary we may assume whichever assignment we want For example to prove that a b is odd if a and b are not both odd WLOG we can assume that the two cases a odd b even and a even b odd are equivalent and so let a be odd and b even Existence proofs require that some X exist so that Px is true If such an X can be found our proof is constructive It is sometimes the case that it can be proved that such an X exists but not possible or convenient to find a specific case Uniqueness proofs require that an X exists that meets our requirements and that everything that meets our requirements can be shown to be that same X When constructing a proof it must be shown ultimately that the premises lead to the conclusion Quite often it is more convenient to start at the conclusion and work backwards Provided that we can simply reverse the path of this train of thought the proof is valid Recall the deltaepsilon proofs in calculus used to show that a limit existed we needed to show that when X was no farther from quotaquot than delta that this forced fx to be no farther from the limit as X approached quotaquot than epsilon Choosing delta is very problematic unless we start at the conclusion Just remember to put the line of your proof in the correct order before you present the proof Be on the lookout for counterexamples whenever you are asked if a statement is true For example is it true that cosx2 2 cos2x for 0 S X S 27 We know that cos7r 1 so if x J then LHS lt RHS since the minimum value for RHS is zero A single counterexample is sufficient we need not show that the claim is always false merely that it is not always true HW 5 Proving the triangle inequality can be approached by taking 9 cases trichotomy requires three choices for X and three for y This list can be reduced WLOG to 6 cases Of these one is vacuous and two re trivial a a 1 0 33 5 we pick two arbitrary rational numbers with common denominator WLOG 3 lt T S I Q 2 b 2 Since i lt 1 it follows E lt 2 b J5 a 7 2 is irrational should not be hard We can assume that we already know J2 is irrational C lt By de mtion a and b are integers so prov1ng that x T 0C Chapter 2 Sets functions sequences and sums Section 1 Sets A set is an unordered collection of objects called elements We will use uppercase letters to denote sets and lower case letters to denote the elements Some notation used with sets Symbol Meaning Symbol Meaning Erfgeg h elements In the x e S X is an element of S set builder notation the pipe means such that S Kl requirements Q Used to denote the empty set Some important sets Name rational numbers El p E D q e D l 9 not A superscript of quot or quotquot indicates the positives or negatives only By de ning q as an element of the positive integers we have avoided division by zero and have not excluded any rational numbers Sets are considered equal iff they have the same elements The set U denotes the universal set that is the set containing all elements of interest in a particular inquiry Subsets and proper subsets refer to sets which are contained in other sets If all of the elements in A are also elements of B then A is a subset of B written A g B IfB has at least one element not contained in A and A is a subset of B then A is a proper subset of B writtenA C B The empty set is considered a subset of every set and every set is considered a subset of itself The cardinality of a set refers to the number of distinct elements in the set it is written 8 The power set of any given set is the set of all subsets of that set This includes the empty set and the set itself Since sets are not ordered we use ntuples when order matters These look much like n dimensional points Equality of ntuples occurs when all of the corresponding elements are equal Cartesian Product of two sets is a binary operation on two sets which results in the set of ordered pairs in which every element in the first set is paired with every element in the second set Example A 1 a cat and B 2 dog A x B 1 2 1 dog a 2 a dog cat 2 cat dog This can be extended to multiple sets by taking the first element of the first set followed by every possible combination of the remaining sets each of which follows the same protocol as in the binary case The truth set for P where P is a predicate is the subset T of the domain of P so thatx e T gt Px is true HW 15 Use contradiction suppose x is an element of A but not an element of C By definition it cannot be an element of B since B is a subset of C But it must be since A is a subset of B 7 28 In Excel this is easy by hand use a table to make it easier SetA SetB SetC X X C TOC Section 2 Set operations Symbolic Representation De nition Name AUB xlxeAvxeB Union A B xi xeAAxEB Intersection AB xlxeAAx B Difference Z xl x A Complement IA UBI AB A03 Identity Name Idem Name AU A Id ft AUBUCAUBUC A t AnUzA en1y AnltBnCgtltAnBgtnC ssoc1alve AUUU D t AnltBuCgtltAnBgtultAncgt Mb t om1na lon 1s r1 u we A AUBnCAUBnAUC A A A A B A E U Idempotent L n De Morgan A NA A A 13 A UB AUBBUA C H AuAnBA Ab f AnBanA ommualve AnltAUBgtA sorplon AuAU A A Complementation Complement A H A Q Unions and intersections may be indexed to indicate the use of more than two sets Bitstring representation assumes some arbitrary ordering of Uquot Strings of length n are then formed so that a 1 in the j3911 position indicates that the j3911 element of U is included A zero indicates that it is not Example LetU 1 2 3 4 5 6 7 8 LetA 1 2 3 5 8 9 1110 1001 Let B 1 4 910010000 HW 14 Use a Venn Diagram 48 Problems such as this are often made easier by writing the first few sets aA1l23 A234 A3345 MW mm bA101 A02 A303 yaw q 440 1 60141 D in 01 alUA1 loo Al T 0C Section 3 Functions The term function assigns elements from one set the domain to a single element of another set the range This is stated symbolically as a b where a e A the domain and b e B the range Other ways of describing this is a is the preimage a is the image f is a mapping or a transformation ofA to B The set B is the codomain where the set 3 b l Ebgfx b is the range If we take f D gt D where f x x2 the reals are the codomain but there are elements in the reals which are not in the range Two functions f and g are considered equal iff they have the same domain codomain and Vx e Domainfx g A function is onetoone or an injection ifffa gt a b A function is referred to as onto or a snrjection if every element in the codomain is the image of some element in the domain A bijection is both onetoone and onto When a function f is a bijection there eXists another function f 391 called the inverse so that fab gtf391ba The oor function round down assigns the largest integer less than or equal to X the ceiling function assigns the smallest integer greater than or equal to X Floor LxJ example L39J 3 note that oor and greatest integer are the same Ceiling l x l example l 3l 4 Factorial ngt 0 gt n i 01 11 HW 14 Remember that the domain and codomain are the integers a We can show that 2m n will give all the odd integers if n is one and all of the even inters if n is zero and zero ifm and n are both zero b All perfect squares end in either 0 l 4 5 6 or 9 As a result no integer ending in a 7 will be a function value c See a d If either m or n is zero we have all of the integers e This is a subset ofpart b 29 Start with the de nitions then establish that the requisite memberships must exist 34 Start by explicitly writing fgx and gfx M Section 4 Sequences and summations A sequence is an ordered set of objects as such it can be thought of as a function from the integers to the set When the elements of an in nite set can be so listed it is said to be countable Geometric sequence 61 arar2arquot Arithmetic sequence 61 a d a 261 a n d A finite sequence is called a string Problems that involve discovering a generating function for a sequence that is some function where f n an are equivocal No matter how many initial values are given infinitely many functions may produce those first n values Example Let S 1 2 3 Possible functions 3 Z 44 WW n4 FD 3 53 125 11 51 Summation notation is used to indicate the sum of a sequence It requires an index lower limit upper limit and a function that generates the elements of the sequence Example 4 211392 3139 The index variable 139 acts as a counter It takes on the integers starting with the lower 11 limit and proceeds to the upper limit As the index variable takes on these values they are substituted into the sequence generating lnction these values are treated as terms to be added iltiZ3igtltlgtz 3lt1gtlt2gt2 3lt2gtlt3gt2 3lt3gtlt4gt23lt4gtl0 1 Changing the index of a summation is illustrated by ailai k Double sums are a way of allowing two variables to take on predetermined values Consider the situation where the rows and columns of a checkerboard are assigned numeric values 1 through 8 A rule is assigned where the loser of a bet is required to place on each square the sum of 3r 2c dollars How much is the payoff of this bet worth r1 51 r1 iicmzc i283r228c i24r72 24281r576864576 1440 51 1 r1 r1 n1 ika xlt1 1 k2 nl62nl 160 k1 a term a onetoone An infinite set with this property is said to be countably infrnite Such a set has cardinality of N0 x pronounced aleph null To show that the positive rationals are countable consider arranging them in rows where the first row has all rationals with a denominator of one the second two etc A zigzag pattern from the upper left passes through all rationals in a clearly defined sequence By the same token the negative rationals are countable By straightening the two zigzags and placing the negatives on top we can create another zigzag that combines the two If we start with zero before commencing this last zigzag we have all of the rationals and motivation for the fact that the union of two countable sets is also countable To show that the reals are not countable start by assuming that they are then considering only the interval 0 1 list them r1 05111 06112 05113 r2 06121 05122 06123 r3 06131 06132 05133 r4 06141 05142 06143 Now if we make the following rule r 0611 0612 0513 4 d at 4 d1 5 d 4 This systematically creates a number different in at least one decimal place from all of the other numbers 7 HW 8 To determine a polynomial of degree n it is sufficient to provide n 1 points think of the sequence as the points 13 25 and 37 where the xvalue is the term number 14 The notation 2 f jimplies that every element of S is used exactly once to create a term in jES the sum 32 Creating a function f n 3 n e D which produces the set in question is sufficient to show countability 40 Let B b1b2b3bn andA a1a2a3an by definition ofcountable C clc203cn C 2171 b1 and Cl a The subscripts for c are all of the odd integers b and all of the even integers a T 0C Chapter 3 Algorithms the integers and matrices Section 1 Algorithms An algorithm is a finite set of instructions for performing a computation or solving a problem While your text uses pseudocode for its examples I will use TI83 programming language where possible It is very similar in that the language is very intuitive but for those with this kind of calculator it will actually run The indentation is to make it easier to read Function Y9 is reserved as intX the oor function and Y0 is reserved as XgtintXintX the ceiling function The TI programming language requires an quotEndquot statement for the fornext loops ifthenelse and the while constructs The TI 8639s 8939s and 92 s have some differences in their syntax and the way functions are treated You should consult your manual if these programs do not work on your machine The ability to program your calculator is not a course requirement Many of the algorithms discussed can be duplicated with built in functions the object is to get a better feel for how algorithms work their structure and their size The algorithm below is a very simple algorithm designed to nd the largest item in a list Input is performed by entering the desired numbers into a list the output is performed in the display step Max If a list of numbers is stored in L1 this algorithm will find the largest value in the list L1l sto M ForI2dimL1 If L1IgtM Then L1I sto M End End Disp M Stop A ow chart like the one above is very useful in organizing your thoughts and assuring that your algorithm performs as expected The parallelograms are data I use them to indicate data in and data out the rectangles are processes and the diamonds are decisions Some things that all good algorithms have in common are InputOutput clarity correctness finite number of steps finite amount of time and generality Using the nomenclature of your book It Input a specified set of initial valuesconditions Only Output a subset of values from a solution set Does Definiteness each step is precisely de ned Computations Correctness the output values are valid for the given input For Finiteness the number of steps from input to output are finite Eager Effectiveness each step is possible to execute and can be done in a nite time frame Geeks Generality the algorithm should be applicable to other problems of the same form The last requirement is exible the others are not Linear Search If a list of numbers is stored in L1 this algorithm will nd the position of a given value or report that the item is not found dimL1 sto K I sto I Input quotDesired NumquotN While IltK and L1 1mm II sto I End If L1 I N Then DispquotNum In Pos quotI Else DispquotNum Not Foundquot End Stop If there are no repeated entries this search displays the position of the number If there are repeated entries this algorithm returns the first position the desired number is in It also makes provision for the possibility that the number is not in the list The binary search will reduce the number of steps but it requires that the entries be sorted before implementing the search Some sorting algorithms will be considered later Binary Search If a sorted list of numbers is stored in L1 this algorithm will find the position of a given value or report that the item is not found 0 sto Input quotDesired NumquotN I sto I dimL1 sto J While IltJ YgIJ2 sto M If NgtL1 M DispquotNum At Pos quotI Else DispquotNum Not Foundquot End Stop Sorting routines are common in many applications These algorithms are often not as efficient as they could be in order to make them easier to understand They should be rigorously tested to ensure that they are correct in all situations before being implemented Bubble Sort If a list of numbers is stored in L1 this algorithm will sort the list in ascending order dimL1 sto N For 11N l For JlN I If L1 J gt L1Jl L1Jl sto L L1J sto L1Jl L sto L1J End End Stop Insertion Sort If a list of numbers is stored in L1 this algorithm will sort the list in ascending order dimL1 sto N For 12N L1I sto M For JlI L1J sto T If MltT Then M sto L1J T sto M End M sto L1 1 End End Stop Greedy Algorithms In optimization problems it is sometimes the case that when given multiple choices the best choice is always the largest choice or smallest depending on the situation An example is the greedy change algorithm which seeks to minimize the number of coins by always selecting the largest possible coin without exceeding the appropriate amount of change Greedy Change Maker For a given amount of change some positive integer less than 100 this algorithm will determine the fewest number of coins The list Coin is set up as 25 10 5 l 0 sto S 4 sto dimLA Fi 1 1 0 LA Input quotInt lt 100 quotN ForIl4 While NZLCMNI SLCMNIsto S N LCMNIsto N LAI1 sto LAI End End Disp quotQuartersquot LA1 Pause Disp quotDimesquot LA2 Paus Disp quotNickelsquot LA3 Pause Disp quotPenniesquot LA4 Stop HW 2 a since the input is n e D l then 71 is replaced with 2n this algorithm is not nite b eventually we have a step 10 so this algorithm is not effective c no value assigned to 139 lacks de niteness d also lacks de niteness no rule assigned for decision between a and b 23 Input the two lists let D ldomainl and R lrangel L1 domain L2 range Does the function Y1 map L1 onto L2 0 sto S dimL1 sto D dimL2 sto R For 11r O sto P ForJld If Y1ltL1ltJgtgt L2ltIgt Then 1 sto P End End SP sto S End If SltR Then Disp quotNot Ontoquot Else Disp quotOntoquot End Stop TOC Section 2 The growth of functions For more information see httpenwikipediaorgwikiBigioinotation httpwwwperlmonksorgnode id573l38 Let f and g be functions from either the reals or the integers to the reals If x gt k gt S C lg where C gt 0 then we say that the functionfis Big0 ofg The constants C and k are called witnesses to this BigO relationship The quotOquot in BigO refers to order in this case giving some sense of the order of magnitude What we are looking for is some kind of bound or asymptote that we can use to assess the number of steps in an algorithm Since the idea is to get some sense of the magnitude we want g to be as small as possible and as simple as possible When dealing with polynomial functions BigO is simply the x to the largest exponent in the polynomial For simplicity let us assume that we are dealing with strictly positive functions or functions which are ultimately positive Let g x Axquot stuff and letfx Bxquot other stuff limgx Huex B B 1221 ltxgt21 2gltxgt While this is not rigorous it suggests that provided C gt BA there should be a number kto serve as the required witnesses The factorial 71 is BigO to nquot and logn is BigO to nlogn This is determined by noticing that the factorial is l234 n lt nnnn n Similarly since 71 lt 2quot we can determine that logn is BigO to n Given two functions which are BigO to two other functions the sum of the two will be BigO to the larger of the original Big039s The product of two functions will be BigO to the product of their respective Big0 s Example fx x3 x2 logxlogx l l7logx l9x3 2 In the first factor of the first term x3 is the limiting portion In the second factor of the first term log x is the limiting portion The first term is therefore limited by x3 logx the product of these two The second term of the function is also limited by x3 logx so the BigO is 3 logx since the sum is the maX ofthe two Two other notations are the BigOmega and BigTheta The BigOmega notation replaces the less than or equal in the BigO with a greater than or equal While the BigO serves as an upper bound the BigOmega serves as a lower bound When a function can be found which will work as both a BigO and a BigOmega it is called BigTheta Different constants C may be needed for establishing the upper and lower bounds but the same constant k should suffice fx x215x2 lx l kl C1l C2E x gt k gt f x S x2 l x gt k gt x Z x2 flt gt 2 The function f is both BigO and BigOmega X2 so we say it is BigTheta X2 HW 2 Use the notion of the largest fastest growing portion is the only relevant portion a X S X2 yes b X2 S X2 yes c logX S X so XlogX S X2 d X4 2 X2 no e eventually X gt 2 no f the oor and ceiling functions are always within 1 of X so their product is not much different than X2 yes 24 A single witness works kCOCQ a 110l b 331 c l205 d ll025 T 0C Section 3 Complexity of algorithms The compleXity of an algorithm is usually considered in two dimensions space the computer memory required and time the number of calculations required For our purposes we will consider the number of comparisons made The algorithm for finding the largest element in a set of n elements will serve as an eXample MaX If a list of numbers is stored in L1 this algorithm will find the largest value in the list L1l sto M Then L1I sto M End End Disp M Stop Since we assign the first element to the temporary position of maX we need only deal with 711 elements Two comparisons are made for each pass through the loop the first is to determine if the end of the loop has been reached and the second is to see if the current element should become the new contender for max There is one comparison for end of loop that returns a yes thus no corresponding test for new max This gives 2n l l or 211 l comparisons This gives us complexity of n The highlighted lines indicate a comparison is made Algorithms such as the above always run through the entire sequence there is no option for early completion Other algorithms are able to stop as soon as the required conditions are met For these algorithms we sometimes look at worst case and average case The linear search algorithm is a good example of an algorithm with variable stopping time If we restrict our focus to those cases where the desired number is in the list somewhere then the worst case is when the desired number is in the last position Linear Search If a list of numbers is stored in L1 this algorithm will nd the position of a given value or report that the item is not found dimL1 sto K l sto I Input quotDesired NumquotN Whilel l and C 11 sto I End If L lr H T en DispquotNum In Pos quot1 Else DispquotNum Not Foundquot End Stop As shown by the highlighted portions two comparisons are needed to see if the loop is still in force and one additional comparison is needed to determine what to report when the loop is terminated If the desired item is in the nth position 2n 1 comparisons are required If we assume that any position is just as likely then we should take the arithmetic mean to nd the average complexity 3572n1 2462nn 2123nn n n n 2123nn n2 n n While it is true that n 2 is usually smaller than 2n 1 both of these are n Sorting is by nature a more complex task than searching The sorts that we have looked at are nz The most common complexity levels are linear factorial Problems which are deemed solvable in worst case time are called tractable those which are not are called intractable Some problems are simply not solvable There is a speci c class of problems which are called NPcomplete These are problems are not determined but if any of them can be solved by a worstcase polynomial time algorithm then all of them can Page 198 of your text has a table showing the length of time required to complete an algorithm for the last six levels of complexity in the previous table for various input sizes Of interest is how fast exponential and factorial algorithms exceed reasonable time expectations HW 26 Greedy Change Maker For a given amount of change some positive integer less than 100 this algorithm will determine the fewest number of coins The list Coin is set up as 25 10 5 l 0 sto S 4 sto dimLA Fi 1 1 O LA Input quotInt lt 100 quotN SLCMNI sto S N LCMNIsto N LAI1 sto LAI End End Disp quotQuartersquot LA1 Pause Disp quotDimesquot LA2 Pause Disp quotNickelsquot LA3 Pause Disp quotPenniesquot LA4 Stop There will be a total of five comparisons on the ForLoop the last of which will terminate the loop Since the smallest coin has value of 1 there will be at most n1 opportunities for the WhileLoop to make a comparison Worst case scenario n6 comparisons On TOC Section 4 Integers and division If a and b are both integers we say a divides b or a is a factor of b if there is an integer c so that ac b We write this alb Division Algorithm if a and d are integers d gt 0 then there are unique integers q and r such that adqr0 r d Examples Two examples will suf ce although by trichotomy we could have the following cases a d result 8 14 114 div 8 614m0d 8 rst example a 14 d 8 q l r 6 0 unde ned WLOG second example 0 zero 0 0 unde ned 0 zero 8l 14 2 14 div 8 2 14 mod 8 secondexample a14 618 q2 r2 0 unde ned WLOG rst example Note that we have de ned the remainder to be positive so we do not get q l r 6 For reasons which I can only assume are aesthetic it is considered good form to make the denominator positive Thus in modular arithmetic where we are only interested in the remainder we always assume a positive divisor The notation for this type of arithmetic is quota mod bquot Where a represents the remainder and b represent the divisor By de nition two integers are considered equivalent under modulo m m a positive integer if mla b This equivalence is called congruence Theorem 1 Let a b and c be integers 139 albAalc gtalbc n Vcalb gtalb E11 iii al bAblc gtalc Theorem 3 Let a and b be integers and m a positive integer a E bmodm lt gt amodm bmodm Theorem 4 Let m be a positive integer aEbmodmlt gtElkeD 3abkm Theorem 5 Let m be a positive integer 61 E bmodmc E dmodm gt acE bdmodmac E bdmodm Applications Hashing functions take some input perform some manipulation and return an output The remainder from integer division is a potential hashing function If the output is to be a storage location the divisor should be equal to the number of locations A collision occurs when a hashing function sends more than one input value to the same output value Psendorandom number generation can be performed by using a recursive function but it is easy to start repeating quickly with small divisors Cryptography is another application but the functions used must be invertible or the message is not decodable HW If the mod function is not built in to your calculator this might be useful Recall the oor function is stored in Y9 Input quotDividend quotA Input quotDivisor quotB YgAB sto Q A BQ sto R DiSp quotQ R quot QIR Stop TOC Section 5 Primes and greatest common divisors Primes and the sieve of Eratosthenes Theorem 1 FTA Every positive integer is either prime or it can be written as the product of primes Theorem 2 If n is a composite integer then n has a prime divisor less than or equal to the square root of n Theorem 3 There are in nitely many primes BWOC 5 P p1 p2 p3 pn is the set of all primes Let s 1H p1 If s is a composite then there is a prime that divides s But this number would 11 also divide s Hp l f 11 Theorem 4 PNT The ratio of the number of primes not exceeding X and XlnX approaches one as X goes to in nity Thus the odds of a randomly selected positive integer being prime is llnn Some open problems The existence of any prime number generating function Goldbach39s Conjecture that every odd integer greater than 5 is the sum of three primes and Euler39s response that this is equivalent to every even integer greater than 2 is the sum of two primes In nitely many primes of the form n2 l n an integer Twin Prime conjecture in nitely many primes of the form p an p 2 The greatest common divisor of two numbers a and b is the number g such that if f is any other number that divides both a and b g gt f Two numbers are called relatively prime if their gcd is 1 Given a set of integers it is pairwise relatively prime if any two elements not equal to each other are relatively prime The least common multiple m of two integers a and b is the smallest integer such that aim and blm HW l4b Recall V1 n1 k Clr Zar r 0l k0 r l The sum of the proper divisors for 2 1 2p 1 will include 20 through 2F391 and 20 2p 1 through 2p392 2p l as terms These two sums are both geometric and t the form above 26 Writing the two integers as gcmj and gcmk should help 31 nn ln 2 n3 3n2 2n Consider that n is either even or n is odd Ifn is zero the proof is trivial II Section 6 Integers and algorithm Theorem 1 If b is a positive integer greater than 1 and n is a positive integer then there is a unique representation of n using b as the base We are most familiar with base ten but other bases have been used the French word for 80 quatre vingt four twentys suggests that at one time a base 20 system was used in Europe The Babylonians used a base 60 system In computer science binary octal and hexadecimal systems are all employed for some purpose or another This routine will quotconvertquot a base 10 positive integer into its constituent parts in another base The values for each place are stored in L1 The function Y9 used in the program is the oor function defined previously The first position is the 1 s position the second is the b s position etc ClrList L1 Input quotInt To Cnvrt quotN Input quotBase quotB N sto Q l sto K While Q O 9 Wu 913 gt sto L1ltKgt YgQB sto Q Kl sto K End Stop Converting from binary to Hex is performed by grouping the binary bits into groups of four bits nibbles Insert leading zeros if necessary on the last nibble Each of these nibbles when translated is the appropriate value for that place Example Binary 0001 1101 0000 1111 0101 Hex 1 D 0 IF 5 An adding algorithm in binary A is stored in L1 B in L2 and A B in L3 As before the place values increase as the order in the list increases 0 sto C dimL1 sto N Nl sto dimL3 ForIlN y9 L1IL2IC2 sto D L1IL2IC 2D sto L3 I D sto C End C sto L3I Stop For simplicity add leading zeros as needed to make the two addends the same length This algorithm is On whether looking at adds or comparisons A multiplication algorithm can be constructed using the pattern for multiplication as we currently know it in base ten The actual multiplication is very straightforward 0 0 1 10110 x 101 10110 shiftO 00000 shift1 10110 shift2 1101110 sum ml The number of shifts required when the multiplier has 71 digits is 2139 This makes the 0 complexity Onz As seen previously the sums are performed On making the entire algorithm 2 n Your book also provides an algorithm for finding the quotient and remainder for the division of two integers as well as modular exponentiation The Euclidean Algorithm for finding the gcd of two integers is a good example of working smarter rather than harder Suppose that we have two integers a and b WLOG a lt b If we find the quotient of b divided by a to be ad r it follows that any integer which divides both a and b must also divide both a and r These being smaller than the original pair of integers pose a simpler problem Repeat as needed until r is zero Example Find the gcd of 1529 and 14038 Using the mod program developed earlier 14039 91529 278 1529 5278 139 278 2139 0 The gcd is 139 HW 20 11644 mod 645 the hard 5 0 45145 8 0 391 4512mod645 203401mod645 226 9 1 1 2262mod645 51076mod645 121 11644 mod 645 l The table above was completed by programming the algorithm for the TI83 and inserting a pause and display step at the end of the loop 30105 lmodll 10k E 1k modll TOC Section 8 Matrices The dimensions of a matrix are given by number of rows number of columns Two matrices with the same dimension may be added by adding the corresponding elements Matrix addition is commutative Matrix multiplication is n0t commutative Matrix multiplication requires the following A jkakJ C N to multiply A and B B must have the same number of rows as A has columns The resulting matrix will have as many rows as A and as many columns as B cw Z a b j the element in the i j position of the resulting matrix C is the sum of the products of the elements in row i of A and column j of B Matrix multiplication is associative A square matrix n X n consisting of 1 s when the row and column number are equal and 0 s elsewhere is called the identity matrix of order n If A is an m by n matrix AIn ImA A When dealing with a square matrix an exponent is understood to mean repeated multiplication or the identity matrix when the exponent is zero The matrix operation transpose is indicated by a superscript t and is the result of interchanging the rows and columns Example all a2 a3 a1 b1 cl A b1 b2 b3 A a2 b2 c2 0 c c a b c 1 2 u A matrix is said to be symmetric if it is equal to its transpose A zerome matrix is a matrix whose entries consist of 0 s and 1 s When a matrix of this form is used to represent a discrete structure the Boolean operators and v are used with a l acting as True and a 0 as False A v B called the join is the result of an element by element or A B called the meet is the result of an element by element and The Boolean product of A and B also requires that B have the same number of rows as A has columns Its result also will have the same number of rows as A and the same number of columns as B The Boolean product of A and B is symbolized by AD B it differs from an ordinary product in that the multiplication is replaced with the and operator and the addition is replaced with the or operator Store zeroone matrices of the appropriate size in A and B The Boolean product will be stored in Input A Rows M Input B Cols N Input B Rows K MN sto dimC For IIM ForJIN O sto CIJ ForQlK ClIJ or AHLQ and BlQJ stO ClIJ End End End Stop Finding the product of two n by n matrices Boolean or otherwise is typically an algorithm with complexity 0n3 HW 14 Let A and B both be n by n matrices Consider the two cases for element position in the resultant matrix Case 1 off diagonal that is row i and columnj i j WLOG i ltj then cij aublj aizsz ai3b3j ainbnj For any given term if aik 0 then bkj 0 since i ltj This means all ofthe off diagonal entries are zero Case 2 on diagonal that is row i and columnj i j The entry for ckk ai1b1j aizsz ai3b3j akkbkk ainbnj Since i j all terms will be zero except for the intersection ofrow and column where the term will be the product of the two diagonal entries M Chapter 4 Induction and recursion Section 1 Mathematical induction Mathematical induction is a method of proving that some statement is true for all n where n is an integer by the following Pl Vn Ifn gt Pnl gt Vn En In plain language we know that no matter what value we pick for n if what we claim is true for that value then our claim will also be true for the next value We also know that our claim is true when n is 1 What we have accomplished is a one to one mapping of our claim to the positive integers Whenever we can perform such a mapping of truth values for the premise we are interested in induction is a reasonable method for demonstrating that our premise is always true This method uses the terminology basis step to describe that our premise is true for 71 equal to l and inductive step to describe the demonstration that truth for 71 implies truth for n 1 Example Show that the sum of the rst 71 odd positive integers is n2 l nl gtS1 ll2 True Basis step 2 By assumption the sum of the rst 71 1 odd integers will be M2 2n l l Inductive step 3 n22nl ln22nlnl2 In the example above we have showed that our premise was valid for n l as our basis step What is important is that we show that our formula works for the rst case whether that is n l or some other number Example 1 I Prove that Hi Our basis step will be to show that this is true for n 3 rather than one 13 3 1 2 3 Hi 3 quot 13 1 I Assume Hi i 13 2 quot1n n1 gz Enl 2 Of equal importance to proving equality is proving inequality Induction is valid for this purpose as well Example Prove that for n gt 6 3quot lt 71 Here we are not only considering an inequality but also a basis step that starts at a number other than one 37 2187 lt 5040 7 Since ngt 6 nlgt3 3quot13quot3 lt nn1n1 It should be noted that induction is a great way to determine if something is true it is generally speaking not a good method for determining what that something might be For example we have formulas for determining the n3911 partial sums of arithmetic and geometric sequences Induction can be used to demonstrate that these formulas are valid but the use of induction presumes that we already have a formula at hand how can we show that when something is true for n that it must be true for n 1 when we do not have that something in the first place Example Consider the sum 26 23quot While it has some of the characteristics of an arithmetic series a 11 constant plus some value it is not arithmetic in that we do not add the same value to each term It also has some of the characteristics of a geometric series each term has a multiplication by a half But the entire term is not multiplied by 12 so it is not geometric We may believe that we n n 1 ar a k can split this into two sums one Z c no and the other 2 ar We can then use k1 k0 V induction to see if we are correct 623quotIZ16IZ173 I H H 173 H I Emile 6n28lj 2 2 We now have an assumption which we can prove or disprove with induction 623quot 6n8 23 1 n l we get 10 The basis step is established If the induction hypothesis is true then 623quot 6n8 23 quot 62339quot 6n8 23 quot623 quot 6n18 2H Our assumption is correct Induction proofs about sets are still proofs about sets This means that we will most likely be making claims about membership of the elements Consider the following two situations Prove that if andB B B are sets such that A QB forjl2n then 1 2939 n n UA QUE 1 11 The basis step merely requires that A1 be contained in or equal to B1 This is given as true in the statement of the problem Assuming that the premise is true for n leaves us having to show that it is true for n 1 To do this we consider membership in the left hand side and show that it must imply membership in the right hand side n1 Let a e UA j1 Case 1 a e UA a 6 U3 by assumption 1 1 n n1 a 6 U3 gt a 6 U3 by de nition of union 1 11 Case2 aeA n1 gtaeB n1 by initial premise 6163 quot1 n1 gt a 6 U3 by de nition of union 1 Prove that if 1411421411 and B are sets then m juB W U3 1 11 For n 1 this is simplyA1 UB A1 UB true Forn2 A1 AJUB UB l2 UB by the distributive law AJJUB Aj AMUB by de nition ltAgtnAmuBfjltAuBgt 11 HW 30 n1 n32n3 313 n132ltn1 Write the portion in the box as our assumption plus something T 0C Section 2 Strong induction and well ordering In simple induction we start with a basis step in which we show that our premise is true for n equal to some starting value typically one We then show that whenever our premise is true for some value k that it must also be true for k 1 For strong induction we must show that when our premise is true for all numbers less than k that it must be true for k 1 Strong induction is sometimes known as complete induction or the second principle of induction Two examples from the book should illustrate Example 1 The match game is a game where two piles of matches are laid side by side Players take turns removing as many matches as they want from one pile or the other If both piles initially have the same number of matches then the second player has a winning strategy The basis step when n is 1 is true The first player is forced to take the match in one of the piles leaving only one match left for the second player The induction step requires that we provide a winning strategy for n 2 through n k which guarantees a winning strategy for n k 1 Player 2 duplicates player 1 s move If player 1 leaves k matches in pile 1 then player 2 leaves k matches in pile 2 Ultimately player 1 either leaves 1 match in pile 1 or no matches If player 1 leaves 1 match so does player 2 This brings us to the basis step which has been established If player 1 removes pile 1 then player 2 removes pile 2 winning the game Now if there are k 1 matches in each pile player 2 follows the same strategy outlined above for the first k matches leading to the basis step Example 2 Prove that every amount of postage of 12 or more can be formed using only 4 and 5 stamps The basis step is established by the fact that three 4 stamps will make 12 We can make 13 15 by replacing a 4 stamp with a 5 stamp For the inductive step we assume that PO is true for 12 Sj S k where k 2 15 Since Pk3 is true 12 S k 7 3 S 15 we need only add a 4 stamp and we have Pk 1 The notion of well ordering is that every nonempty set of nonnegative integers has a least element we 00 0600 6060600 COO 606060600 0600 3 3 3 3 3 3 3 6 9101213151618 At this point replace three 3 s with a 10 to add 1 Replace six 3 s with two 10 s to add 2 or add another 3 to add 3 So all of the listed positive integers and all positive integers greater than 18 can be formed with only 3 s and 10 s TOC Section 3 Recursive de nitions and structural induction A recursively de ned function provides a function value for the 03911 term then de nes fn in terms of fn 7 1 Sometimes it requires the first k terms to be provided then fk l is given in terms of fl through fk A good example of this is the Fibonacci numbers Some recursive sequences are given below Arithmetic 7 an an1 d Geometric 7 an an1r Fibonacci 7 fn fn1 fnz given f0 0 f1 l n 234 Functions of this type are called well defined which is to say that its values are found with no ambiguity Sets may also be defined recursively Sometimes it is specifically mentioned that only the basis elements and those elements found by applying the recursion formula This is known as an exclusion rule We will assume that the exclusion rule is operative without specifying it Example Let 2 be the set of symbols 0 1 Let Z be a set of strings formed by concatenation ofthese symbols using the following rule The empty string is an element of Z Ifw is in Z and x is in 2 then wx is in Z Omit trees structural and generalized induction HW 12 Recall that f0 0 24 c Let S be a set containing the integers thus all of the constant polynomials If pX is in S then XpX n is in S T 0C Chapter 5 Counting Section I The basics of counting The two most basic counting principals are the product and the sum rules The product rule is employed when a task may be represented as a sequence of choices each with c possiblities The total number of possibilities for the completed task is given as H01 11 When using the product rule care should be given in determining whether or not the choices are independent For instance if we are assigning ID s to accounts with each ID assigned there is one less available to assign If we are picking digits for an ID number there are ten available for each position This notion is useful when counting the number of steps performed in a nested loop The following code has been written to find the sum below 4 5 Z 2039 139 11 11 0 sto S For I l 4 For J l 10 S I I sto S End End Disp S Stop In the outer loop there are four valid values for I in the inner loop there are ten valid values for J This means there will be forty times that the code S I I sto S will be implemented When tasks are selected from one of a variety of sets of tasks each with ni choices then the sum N rule is in play It states the number of possibilities will be 2 n where N is the number of sets 11 The significant difference is that the product rule applies to a sequence of tasks whereas the sum rule applies to a single simple task Some counting problems will require that both rules be employed and some will require that you be aware of multiple counting Example How rnany nurnber between 1 and 100 inelusive are divisible by either 2 3 5 or 77 wt i r u a i divisible by 3 and or 5 and or 7 Ifwe just rnade a list ofdivisible by 2 divisible by 3 divisible 39 quotquotquotquot 7w 394 394 L 11 39 39 Thisisanove eount The eorreet answeris 7s HW a Note the lowest integer to examine is 1 and the largest is 999 bf lused Excel to get the following values 1R1 s l T 1U1V1W1X1V1Z1 n seven eleven mud seven eleven pvud 1 El El El sum 142 SD 12 2 El El El 3 El El El 4 El El El 5 El El El 13 El El El 7 1 El El E El El El 9 El El El 10 El El El 11 u 1 u 12 El El El 13 1FR 1471NTR147111D 1FR 14111NTR 1411111D S14 T14 n r r r r i r u divisionifitis al 39 39 quot 39 39 ifquot t 39 integers divisible by either seven or eleven The eolurnn prod is the product It will be a 1 onlyifboth are a l A sirnple Venn diagrarn should sort out the various divisibility eategories g r 1 Case 1 single digit 1 double digit 1 triple digit 1 1 product rule 1 9 1 9 9 1 998 While there are 10 uh 39 i h You may want to eount the odds then subtraet 39v 39L 11217 39 39 m L and n ofthern have a single elernent 53 There ar 39 39 39 39 39 linear and circularIfd1e arrangernentis eireular we would need to specify a rotation direetion or that direetion did not rnatter What we want in this case is a linear string where the string is to be read from left to right Consider the four cases i a is in the first position ii a is in the second position iii a is in the third position iv a is in the fourth position TOC Section 2 The pigeonhole principle The pigeonhole principle simply states that if you have more than k objects and only k boxes then at least one box has more than one object The generalized pigeonhole principle states that if N N objects are placed 1nto k boxes then there 1s at least one box w1th at least objects A proof by contradiction is provided in your text Recall that the ceiling function provides an integer as its output If all k of the boxes had one fewer objects then we see that k llIlltk IJIJN iii ken The most common type of question requiring the use of the pigeonhole principle is of the form what is the minimum number of objects required to guarantee at least r of these objects must be in one ofthe k boxes Example How many cards from a standard deck of 52 must be selected to guarantee at least three cards of the same suit are chosen There are four suits in a standard deck these will correspond to the k boxes that is k 4 We want to find N so that 3 gt gt 2 gt N gt 8 Nine cards suffice While the concept is simple sometimes the implementation is not HW 30 N 100000000 k 99999999 31 N677 k38 TOC Section 3 Permutations and combinations Permutations refer to arrangements of objects In terms of permutations abcd is distinct from acdb even though the two strings are composed of the same elements When counting permutations we use the multiplication rule Consider the following situation in 2007 23869 people entered the Boston Marathon Of these 3223 did not start the race for one reason or another Of those who started 308 did not nish If we wished to make a top 10 list of those who nished how many possible lists would we need to make if we wanted to have every possible list There are 20338 possible choices for the number one position 20337 for number two and l n r number that we will ultimately arrange Depending on the author permutations are indicated by nPr or Pnr The rst notation matches the syntax for the TI calculators The latter is more in keeping with a multivariate function and is what you text uses Remember that 0 is equal to one by definition so if we are arranging the entire set n there will be n ways to do this so on The general rule is where n is the total number from which we pick and r is the Combinations are concerned with which elements are to be included not with what order the elements will appear If we were interested in knowing who was in the top ten list but not in where they appeared in the list it might occur to us that if we had all of the permutations then we would have in effect every combination represented by all of its permutations Thus from the Boston Marathon example above for any distinct group often people there are 10 permutations for that group Dividing by the number of permutations for each group will give the number of n I n groups combinations The general formula is n39 39 39 The LHS J is read n r r n r r choose r This is what Pascal was really up to when he derived the binomial theorem The choose comes from the fact that this tells us how many distinct ways r objects can be chosen n from a set n The notations J nCr and Cnr all refer to combinations r By the way there are l208l5 l38846398l468ll54670562780037639564800 permutations for a top ten list of the 2007 Boston Marathon but only 33293413482803722l15l7490785598555346 combinations HW 12 This problem deals with combinations in pa1t a we are choosing how many ways to pick three positions out of twelve to contain a one In part b we add the combinations for no l s one 1 two 1 s and three l s In part c we could do the same thing or we could subtract from 212 total number of bitstrings of length twelve the values we don t want 22 Look at example seven in the text T 0C Section 4 Binomial coefficients The Binomial Theorem states that if x and y are variables then quot n n n n n x n xw j xquot x39quot1 xquot39l quot l y y lo I y ln Jy Using the formula for combinations as the coef cient makes sense in that we know that the sum of the exponents in each term will be n We need to choose how many ways j of these n can be assigned to y with the rest assigned to x This is a combination This becomes a little less clear when we expand a binomial where the variables in the binomial have coef cients other than one Example Find the coef cient of the 4Lh term in the expansion of 2x 3 y7 The rst thing to remember is that we start counting with the 0111 term so the 43911 term will be 72x 3y3 352 33 15120 3 Some interesting results can be obtained from the Binomial Theorem when we remember what the constituent parts are k 1 12 1 2 3quot 0 Corollaryl ZJVW k01k1 11 11 2quot Corollary2 gig 0k kZ1k1H 0 Uk UH 11n 11quot 0 l J quotJ n n n n n Corollary3 221k 16 ka w 160 160 Despite its name Pascal s Triangle was lmown to the Chinese as early as the means of generating binomial coef cients d as ch once methods for solving quadratic and cubic equations were lmown was usedto generalize these methods to higher roots Jia Xian who livedin the eleventh century is attributed with writing the triangle out to the oth row andidentifying the method we lmow today of generating it The triangle was used by Pascal and F es er The une misfortunes o this famous gambler were the origin ofan algebraic approach to mnhahilitv a 7 me ne arier 39 39 always betting small favorable odds on getting at 39 39 to e ulddiethen tit u uuuulc tosses This theme was taken up by James Bernoulli c 1712 and later mathematical writers who turned 39 39 quot 39 39 39 39 quot11 est tres bon men e39spritquot wrote 39 quotmais quel dnmmm quotHe s a fun guy but alas no mathemeticianquot Pascal 5 Identity quotEIJ IMZJ A r counting the same set of objects only in different ways is given below IfT is a set with n 1 elements and a is one of those elements and S is the set T with the element a removed from it we will note that there are n 1 subsets of T that contain k elements the LHS Now a subset of T with k elements can have a in it along with k 7 1 other elements 631 of this or it did not have a in it and was merely k elements chosen from n The sum of these sum because these are independent and or is the RHS Some other identities are m n 1 m n r H r k k 211 quot n 2 n k k 71 1 Z k rl H r The proofs for these are given in your text and are easy to follow HW l9 n1 n1 n1 kk n L n nknl kn n k 1k 1ln kk n1 kk nknl kn nknl k n1 kk n1 kk nknl k nnl n1 kk n1 kk n n1 n1 n1 n1 kknS 1 kk k J 28 a Suppose you had a group of n men and another group of n women and you wished to pick 2n n two people from this collection of Zn people 2 J You could choose two men 2 or two n n n n women also 2 or you could choose one of each This 1s 22n2 b Use the same approach as in 19 above T 0C Section 5 Generalized permutations and combinations We are referring to permutations and combinations when repetition of elements is allowed as being the general case Previously there were no repetitions For permutations we again employ the product rule since we no longer decrease the available pool by one as we progress through the various positions the formula for rpermutations from a set of n objects is nr The rule for combinations is slightly less obvious For a set with n elements from which we will choose r with repetitions allowed we will use the formula corresponding to Cn r 7 l r Your text describes the process of making this decision in terms of stars and bars With n 7 1 bars we can partition an interval into n bins In each of these bins we will place the number of stars equivalent to the number of times we choose to repeat the selection of the item contained in that bin In example two we are faced with a bowl containing three types of fruit from which we are to choose four pieces While we are choosing from a set of fruits and repetitions we are still actually choosing four things The n in this problem is three the r is four so the solution is C3 4 7 l 3 or C6 3 which equals 15 Permutations with indistinguishable objects such as strings containing repeated letters or I H711 11 elements into k categories each of which has ni elements For the first n1 elements we can choose from the entire n locations for the next n elements we only have n 7 n1 places to choose from etc numbers eg license plates use the formula The notation here is that we can sort our n Some counting problems resolve themselves to the equivalent problem of choosing boxes in which we will place objects We may consider the case ofboxes and objects which can be distinguished or which are indistinguishable The problem of n distinguishable objects and k distinguishable boxes is the same as permutations of n objects in which the objects are partitioned into k categories with repetitions of the objects in each category The problem of n indistinguishable objects with k distinguishable boxes is the same as the combinations with repetitions The problem of distinguishable objects and indistinguishable boxes is much more complex The notion of Stirling numbers is employed in this sort of problem Let Sn j denote the number of ways to distribute n distinguishable objects into j indistinguishable boxes so that no box is k empty Ifwe allow as many as k 7 1 boxes to be empty then we have 2 Sn jpossibilities 11 The Sn j denotes the Stirling number and is defined as follows MlFig QM 239 Finally n indistinguishable objects into k indistinguishable boxes resolves itself into a kpartition of n that is finding the integer sums so that we have no more than k integers and no fewer than one integer such that the sum of these integers nonnegative is n There is no nice formula for this number We will require that the integers as read from left to right be nonincreasing HW 16 a If all the X s are greater than 1 this means they are all at least 2 Subtracting two from each integer on the left and 12 from the right gives the problem of nonnegative integers whose sum is 17 This is C6 17 1 17 b d Look at the restrictions as eliminating possible nonnegative integers n is 6 r is what is left after eliminating the integers 54 This asks for the partitions of 5 into at most 3 parts They are enumerated below 123 There are five such partitions T 0C Chapter 9 Graphs Section 1 Graphs and graph models A graph is a set of vertices sometimes called nodes and a set of edges arcs that connect the vertices The use of straight lines or curved lines overlapping lines or nonoverlapping is only important aesthetically While some graphs cannot be drawn on paper without overlapping the edges what is important is that the connections between vertices be accurate A graph is a visual representation of the relationships between a set of objects Graphs may be employed as a method of identifying patterns that might not be apparent when the information is displayed by other means As an example of this suppose ten people are at a party Alice Betty Charles David Eric Frank Gail Helen Irene and James An observer records whom each person talks to over the course of the party Using this information we want to see if any patterns emerge A tabular representation of this data is presented Find the name in the row an X in the column indicates that the person in that row talked to the person in that column By looking at the table we see that James talked to everyone The rest of the people talked to two or more other people Letting the people represent nodes and edges represent conversations we obtain the graph below A C J H The letters are the rst letters of the person s name The dots represent the person The lines indicate conversations between two people James talking to everyone kind of clutters the picture but in the table and the graph it is easy to see who is hosting the party Lets take James out of the graph and see what happens A C The graph with James removed allows us to see that there are three cliques at the party 0 Alice Eric and Gail 0 Betty Charles and David 0 Helen and Irene Frank seems to be the odd duck He talked to one member of each group but did not appear to get accepted by any group He also talked to himself Maybe Frank was actually providing security and was really talking into a hidden microphone to his backup Or perhaps Frank was muttering to himself after being snubbed by yet another group While the visual appeal of graphs is a major draw we can infer a lot from graphs mathematically as well First we need to establish some de nitions A simple graph is a graph in which there is no more than one edge between the same two vertices The edges do not have any implied direction of travel and will not connect any vertex to itself A multigraph differs from the simple graph in that it does allow for redundant edges between vertices It also will not allow loops The pseudograph builds on the multigraph by allowing loops A digraph has directed edges Often edges are referred to by the pair of vertices that they connect In a digraph this is an ordered pair Start End Some graphs have been used sufficiently often to merit their own specialized names nodes 7 species nodes 7 people nodes 7 people nodes 7 actors RoundRobin Collaboration nodes 7 teams nodes 7 people nodes 7 phone numbers nodes 7 web pages nodes 7 tasks nodes 7 cities HW 12 Since the graph is not directed uRv 9 vRu thus the relation is symmetric The presence of loops at every vertex guarantees uRu therefore the relation is re exive 13e x xlt0 A1rHltrlto Afr oqa qua A x xgt71 A n TOC Sec nn 2 Graph 01anng andth types nfgmphx rnerdent to orrnerdentfrom the vemees The dzgnze of a vertex degv rs the number of edges rnerdent to rt Note that a loop eontrrbutes to the degree ofavertex twree onee upon leavrng then agam upon retumrng The Handxhaking Theorem m an undreeted graph wrth e edges Zdegv 22 Your text v an even number of vemces of odd degree ndtn ml ntmthe termrnal rt tn dtr t d rnh gemegdeemetat graph Some speera1 srmple graphs are the complete Lycle andwhzelgraphs The eomp1ete graph rs formed by p1aerng edges as needed so that any two V 39 vertrees are adjacent va rs the number of veruees then the number of edges rs men2 Complete graphs are referedto as K where Krs usedto denote eomp1ete andn denotes the number ofvemces A If we remove the interior edges we have a cycle Cycles have exactly the same number of edges as vertices but need at least three ofeach for the name to make any sense The same notation as above is used with the exception that C is used for cycle C5 is shown on the right The wheel is formed by inserting a central vertex with edges serving as spokes from this hub to the exterior vertices most of which do not look like what we commonly consider as a cube Q is a s1ngle ed connecting vertices labeled 0 and 1 To increase the order to Q2 copy Q1 so that you now have two graphs with a single edge connecting vertices labeled 0 and 1 On one of them insert a leading 0 to the names ofthe vertices on the other a leading 1 Connect the vertices that match except for the leading digit See page 602 of your text Another specialized graph is the ncube We can think of the ncube as a progression of graphs ge A bipartite graph consists of two distinct sets of vertices Edges are usedto connect vertices from one set to the other We sometimes consider complete cases of the bipartite graph by which we mean every vertex in set A is connected by an edge to very vertex in set E Assigning jobs to employees could be modeled with a bipartite graph LAN s may be modeled with stars cycles or wheels Sub graphs like subsets are formed by taking part or all of an existing graph A proper sub graph is not a simple copy We say that we have taken the union of two graphs when we have added any new vertices and edges contained in one to the other HW 36 Part ofthis problem is solved by the socalled Handshaking theorem if 2 dx mod2 0 then 11 the graph is not possible Another part is avoiding multiple edges The sum of the degrees is 15 therefore no graph is possible The sum of the degrees is 21 therefore no graph is possible All six vertices have degree 2 a cycle is one possible graph The sum of the degrees is 15 therefore no graph is possible The sum of the degrees is 14 therefore a graph may be possible One such graph is 5amp883 git C9 The sum of the degrees is even Since all vertices have a degree of 1 the graph will not be connected Three pairs of vertices with one edge joining them will form the graph g Again we have an even sum so a graph may be possible In fact the graph below is one example xriL h The sum is 20 so a graph may be possible There is a problem however with the size of the degrees With 6 vertices we cannot have two with degree 5 and still have a simple graph The rst may neighbor the remaining ve but the second vertex with degree ve will also have to neighbor the other ve But one of the other ve has degree 1 TOC Section 3 Representing graphs and graph isomorphism Other than simply drawing the graph a graph may be represented by a list of edges vavb where the edges are identi ed by the vertices they connect Alternatively an adjacency list could be used These methods are appropriate for graphs without multiple edges With minor modi cations they could be adapted to multigraphs as well For the graph shown at right the edge list is A B C AB AB BC 13D CD DE EF 1 Since the edge AB is the same as BA it need not be repeated The adjacency list for the graph is D A I F E Every vertex is listed with a complete list of those other vertices to which it is adjacent This means that all adjacencies are repeated If the graph is directed the edges in the edge listing will be ordered pairs v0vt and the adjacency list will have as the left hand column a list of initial vertices The adjacency matrix is an n by n matrix n being the number of vertices with one row and one column reserved for each vertex The cell in the i row and j3911 column will be an integer indicating the number of edges connecting vertices i and j If there are no loops in the graph the main diagonal will always consist of zeros The adjacency matrix for the graph above is F 0 0 0 0 l 0 Considering that the labels for the vertices are arbitrary an adjacency matrix is not necessarily unique Irrespective of the ordering of the vertices whether loops and or multiple edges are allowed all adjacency matrices are symmetric Another matrix representation for a graph is the incidence matrix For this representation the edges are listed as columns the vertices as rows If an edge is incident to a vertex a one denotes it Every column will thus have two ones and the rest zeros The exception to this is when the edge is a loop If an edge is a loop then there will be a single one in that column A graph G1 is said to be isomorphic to G2 if there exists a bijection f which maps the vertices in G1 to the vertices in G2 fv1 vz such that if a and b are adjacent in G1 then fa and fb are adjacent in G2 Properties preserved by isomorphism are referred to as graph invariant these include adjacency degree the number of vertices connectedness and the number of edges If we can determine the correspondence between the vertices then the adjacency matrices for the two graphs will be identical A a v b B C I D E i e A f The graphs are isomorphic The function has been stated explicitly and the adjacency matrices are identical when the RHG is ordered by fv The two graphs on the right have the same number of edges and vertices The degrees ofthe vertices in the graph on the left correspond to the degrees of the vertices on the right but the two vertices with degree four in the LHG are adjacent while those in the RHG are not These two graphs are not isomorphic Consider the following two cases Let fA c fF d fB a fC b fD e fE f F100110 10010 TOC Section 4 Connectivity A walk is a sequence of edges such that any two successive edges in the sequence share a vertex aka node The walk is also considered to include all the vertices nodes incident to those edges making it a subgraph A trek is a walk that does not backtrack ie no two successive edges are the same A trail is a walk where all edges are distinct and all vertices By distinct we mean that no edges or vertices are repeated A path is a walk where all edges are distinct but vertices may be repeated A circuit is a path that ends on the same vertex from which it started A graph is connected if all vertices can be joined by a path and is disconnected if at least two vertices may not be joined by a path Components of a graph are the connected portions of a disconnected graph as well as any isolated vertices A bridge or cut edge is an edge which if removed would cause the graph to become disconnected When dealing with a directed graph we have two notions of connectedness A digraph is strongly connected if for any two vertices in a graph there is a path from one to the other and vice versa A digraph is weakly connected if there is a path between any two vertices when the directions are removed from the edges Paths and circuits are invariant under isomorphisms The number of paths between two vertices in a graph can be obtained using the adjacency matrix If you want the number of paths of length r between v1 and vz then look at the entry in the cell corresponding to the intersection of the two vertices in Ar Your text provides a proof by induction for this result HW You should be able to do these without help TOC Section 5 Euler and Hamilton paths The Seven Bridges of Konigsberg In Konigsberg Germany a river ran through the city such that in its center was an island and after passing the island the river broke into two parts Seven bridges were built so that the people of the city could get from one part to another crusslng each budge exactly unee Answenng ths quesuunls Leunhzrd Euler a Swlss R m qu wdwhl H mm Euler39s appmachtu ths pmblem was u change the way we represent it He declded cu let the land masses berepresented by nu es and me ndges by arcs wluen cunnectthenudes Thls was pmbably the rst a I useufgrzph Lheurymsulvmgapmblem Euler xfuslgmph Lhzaran Ifany venex has an udd degree llnen it has nu Euler Clrcult exlsts E men n Euler Path exlsts exlsts Au suchEmuPathmuststm at am uf39hz addvemces andend am v1th Example amnaagmaa Canm A D J H FE EA A n3 Ec CD DE EC c1 1G GE EF m GI 1H HG an Th2 xededgzs are what arapasvaaas cause was Emu rasassa an m edgzs math1 ma39hzmancmntumdhs anmnanta ms vaunes In a cannec39zd graph at my edge 5 aavsxsa everywnzx Wm be sud 5 n passbxs ta wst everywan mmmaavsnagsmysagsv mm cmb dam mmme mamas way xsxt pamb eta ndthz shattean am mHamdmnfachedhls nucnnmmdnspmblem Hamdmn39s mgml wk an sxegmdwasmundedas agams mdhz snldxt as mchm atvyandgame manurasaasa 1n xsasan gam uf Ex u A was snldm Jacques mdsms makers ufhlgm quahlychzss 5215 m as andpntemedm Lmaamnxzsy Th2 gams xsnlntedm BusesmgmsTmpaamsm sass amaaays tmmnlagy a asks fax a Hamdmman mam a cmmn gsph The game was a mug and snld v M sapass We havetwathzmemsthatmaybe ufsame mp m answering lms quesum mac39s mexe39s Dinn x RIMInacmnzcudgsphthhmeeaxmmewmcesxfeauhvemxxsadgacenna alleasthalfufthz xemmnmgvemces 39hm39hz gaphhas aHarmltmcxrmL Dn x mm Ina camzned gaphwnh39hxee 91mm vemces ms sum af39he degees uf mme ufmna acemvemcesxs gsamman a equal Oath mxnber ufvemces 39hm39hz gaphhasaxxamnm mm HW 20 a b c 4 4 d e Each vertex has the same indegree as outdegree the underlying undirected graph has all even degree vertices An Euler circuit should exist Start with a must go to d From d go to b then return to d Next to e to b and back Then e to c c to b and back to a adbdebecba TOC Section 6 Shortestpath problem In this section we look at weighted graphs that is we will apply values to the edges These values may be associated with length cost risk or some other quanti able variable If we think of summing the values assigned to the edges as we follow our pathcircuit then it is possible to ask for the path that generates the smallest sum The premise for these questions is that the important thing is the vertices the edges are only important in that they enable us to visit the vertices For simplicity let us assume that the edge values are distance In the late 1950 s a Dutch mathematician Edsger Dijkstra proposed an iterative algorithm that would nd the shortest path between two vertices The gist of his algorithm is to start at the beginning of the path proceed to nd the shortest path to a next vertex then to a vertex with one intervening vertex etc until the end of the path is reached The algorithm he proposed will nd the shortest path between two vertices in a connected simple undirected graph The complexity of this algorithm is 0n2 where n is the number of vertices in the graph When this problem is escalated to nding the shortest circuit the complexity increases to n 7 l2 Basically the solution is to list all such circuits then sort by length to nd the shortest A certain deli delivers sandwiches every day to ve businesses Jones King39s Landry39s Martin s and Novak s Since the delivery person must follow the streets the distances between points are the number of blocks traveled What is the shortest path that will start and end at the deli visiting all ve businesses The map is on the next page Using the taxicab metric we obtain the following graph J K 6 T 4 L 34 5 39 Deli 5 N M 4 With siX vertices there are 120 paths Distribution of Le ngths Number of Circuits 24 26 2B 30 32 34 36 40 Le ngth of Circuit In reality there are only 60 There are two circuits that tie for best DJKMN LD and DKMNLJD It only took me a little over an hour and a half to discover this Adding just one more vertex would have made this problem six times as big In short problems of this type known as the traveling salesman problem are NPcomplete that is they are not solvable in polynomial time There are a host of algorithms which nd approximations Two of these are nearest neighbor and cheapest link These are both greedy algorithms The nearest neighbor method simply says of all the available options take the closest To improve on this try each of the vertices as the starting point Once you have a circuit you can start anywhere Nearest Neighbor on the Deli Problem 0 From the deli the nearest neighbor is Jones 3 From Jones the nearest neighbor is King s 6 From King s Martin s 4 From Martin s Novak s 4 From there we are forced Landry s 3 0 Then back to the deli 4 Total journey 24 The cheapest link connects the two closest then the next etc until a circuit is formed The only requirement is that the nal path be a circuit Cheapest Link on the Deli Problem 0 Deli to Jones 3 Deli to King s 3 Novak s to Landry s 3 Martin s to King s 4 Martin s to Novak s 4 This leaves King s to Jones 6 The circuit is complete and we end up with another 24 the real optimum The two examples we looked at both gave us the optimum solution Neither one is guaranteed to perform that well all of the time In fact often the best you will get is around 80 or so of the true optimum TOC Chapter 10 Trees Section I Introduction to trees A tree is a simple connected graph with no circuits By definition a tree may not have multiple edges or loops A disconnected graph with trees as all of its components is called a forest If an undirected graph is a tree there is a unique simple path between any two vertices A rooted tree is a tree with one vertex designated as the root All edges are considered to be directed away from the root Designations for the vertices in a rooted tree are somewhat genealogical A path directed away from the root would start with a parent and continue through a child to subsequent descendants A vertex with no children is called a leaf those with children are considered to be internal A subtree of a tree may be formed by designating any vertex as the root of this subtree then keeping all descendants of that vertex and any edges incident to them A rooted tree is called m ary if every internal vertex has no more than m children and full mary trees are those in which all internal vertices have exactly m children A rooted tree is considered ordered if the children are arranged in order from left to right When these are binary the children are referred to as left and right Trees have applications ranging from modeling chemical compounds Bernoulli Trials organizational structures and many others Properties of Trees 0 All trees with n vertices have n 7 1 edges 0 A full mary tree with i internal vertices contains n mi 1 vertices o A full mary tree with n vertices has i n 7 1m internal vertices and l m 7 ln 1m leaves A full mary tree with i internal vertices has 1 m 7 li 1 leaves A full mary tree with 1 leaves has n ml 7 1m1 vertices and i l 7 1m 7 1 internal vertices The level of a vertex in a rooted tree is the length of the unique path from the root to that vertex The height of a rooted tree is the maximum level in that tree A rooted mary tree of height h is called balanced if all leaves are at levels h or h 7 1 There are at most mh leaves in an mary tree of height h TOC Section 2 Application of trees Binary Search Trees are useful for storing and subsequently retrieving items in a list It must be possible to form an ordering for the items in the list A recursive procedure for building a binary search tree is given below Start with an initial vertex the root The first item in the list is assigned to the root To add subsequent items start with the root if the new item is less than the root move to the left else move to the right When the item is less and no left child exists it is inserted as a left child Similarly on the right An example is perhaps the best way to ensure that the algorithm is understood The integers 1 through 18 were randomly shuf ed They appear in the order that they are to be inserted into abinary tree 9 17 12 7 16 6 2 13 4 10 8 5 14 11 15 1 3 18 The first integer 9 will be assigned as the key value for the root Since 17 is larger than 9 it will be assigned as the key to the right child Next is 12 from the root we move to the right 12 gt 9 The right child has no children and 12 lt 17 so 12 becomes the left child of 17 The next integer is 7 From the root we move left 7 lt 9 There are no left children so 7 is assigned to that position The final tree is shown below To retrieve an item we use similar reasoning as we do in placing an item Suppose we are looking for 11 Since 11 is bigger than 9 we go to the right On the right we find 17 11 lt 17 go left To the left we f1nd1211lt12 go left To the left of 12 is 10 Since 11 is larger than 10 we look to the right and find the value Decision Trees Another type of mary tree is the decision tree This tree models a sequence of decisions which lead ultimately to a decision This type of decision can be anything from successive weighing to find a counterfeit coin to sorting values A binary sort is of the form new element is either less than or greater than reference element This type of sorting is at least Logn complexity in terms of comparisons and is Qnlogn Pre x Codes In an attempt to save memory and reduce transmittal time a scheme could be employed which would assign unique prefixes to characters More commonly used characters would then be assigned shorter prefixes A simple method is to use 1 s as the prefixes and a zero to denote the end of the prefix Thus 0 might be a letter but not 1 For that matter not 11 or any sequence of 1 s other than the last letter in the list Huffman Coding Huffman Coding is the result of a greedy algorithm employed to turn a forest into a tree Weights are assigned to nodes characters based on the relative frequencies First the two smallest are joined by creating a new root node and assigning the larger to the left and the smaller to the right The sum of these two is now assigned to the root of the treelet The edges are assigned 0 s if going to the left and 1 s if going to the right The final label is the sequence of 0 s and 1 s formed by following the path from root to desired character Game Trees A tree that starts with the opening position of a game as its root and then proceeds to enumerate all subsequent possible moves as sequential levels is a game tree Trees of this nature may have their vertices labeled to show the payoff for the players if they follow the so called minmax strategy TOC Section 3 Tree transversal A UniversalAddress System is a method for completely ordering the vertices of a rooted tree Begin by labeling the root as 0 At level 1 assign integer values starting with 1 on the left and increase by one as you move to the right Recursively de ne the vertices by appending n for vertices further down The tree shown below would consist of the following vertices 0 1 2 3 1112 21 31 32 211 212 321 Algorithms designed to systematically visit every vertex in a tree are called traversal algorithm One such algorithm is the preorder traversal Preorder traversal starts at the root then moves from left to right exhausting the subtrees as it goes In the tree above the preorder traversal would be 0 1 11 12 2 21 211 212 3 31 32 321 Inorder transversal starts at the root but if there are subtrees it will exhaust them in order by pursuing the subtree on the left then coming back to the root then the next subtree to the right For the tree above 11 1 12 0 211 21 212 2 31 3 321 32 Postorder transversal moves from left to right exhausting the vertices from the bottom before visiting the root The tree above would yield 11 12 1 211 212 21 2 31 321 32 3 0 Your text provides the pseudocode algorithms for these three transversals on pages 716 and 718 The use of ordered rooted trees for storage leads to an equivalence of order of operations If we let internal vertices be operations and leaves be operands then we can evaluate the subtrees from left to right Trees used for this purpose result in expressions that are referred to as in x pre x or post x depending on the transversal scheme being used Infix notation will sometimes require the use of parenthesis to avoid ambiguity Pre x Polish notation and postfix reverse Polish notation do not require parenthesis The trees themselves are not ambiguous however The binary tree representing the right hand root from the quadratic formula 71 xb b2 7 4x ax C 2 x a is given below Start on the lowest level as you perform the indicated operations replace the vertex containing the operator with the result of the operation 9 b E Reading in x expressions are no problem since we must include parenthesis to avoid ambiguity Reading pre x and post x expressions simply require starting from the right for pre x and starting from the le for post x To help see this we write the pre x expression for the above tree AAb2gtltgtlt4acl2gtlt a To read this start at the right and move in until you nd an operator Apply this operator to the two values just to its right We nd a multiplication which we apply to the values 2 and a At this point we have the expression AAb2gtltgtlt4acl2 2a We divide l by 2 XleAb2gtltgtlt4ac052a We multiply 4 and a XleAb2 gtlt4ac05 2a We multiply 4a and c XleAb24ac052a We raise b to the power of2 Xlebz4ac 05 2a We subtract 4ac from b2 X l b A bZ4ac 05 2a Parenthesis inserted to avoid confusion We raise the parenthetic quantity to the 12 power X l b bl4ac05 2a We multiply 71 and b b bl4ac0395 2a We add the radical to 7b b bl4ac0395 2a We divide by 2a When dealing with postfrx expressions start at the left and move in to the first operator Apply that operator to the two values immediately to its left TOC Section 4 Spanning trees When a graph is a tree with no isolated vertices it is a spanning tree One method of making a spanning tree is by starting with a simple connected graph and removing edges those edges that are part of a circuit but are not bridges Alternatively we could build the tree so that no circuits are formed One such method depth rst picks some arbitrary vertex as the root of the tree then follows the longest path possible from this root Vertices that are not included require backtracking to the first vertex from which there exists a path that will not produce a circuit For the graph below we can construct a spanning tree by assigning A to the root and generate the path A B D G K I H E F We can see that the vertices C J and L have been omitted Backing up the path we find an edge from E to J which does not create a circuit so we add it Backing up one more vertex to H we see that the remaining two vertices may be added with out forming a circuit The edges selected are called the tree edges and the remaining edges are called back edges Spanning trees formed in this way are not unique One reason is that the root is chosen arbitrarily another is that no serious effort is used to make the longest possible path from that root Typically we start with an adjacency list and progress sequentially to the first vertex adjacent to the current one nrn III XOUUJ L Another method for creating spanning trees is the breadth rst method As in the previous method the choice of the root is arbitrary but once it is assigned all vertices adjacent are added along with the edges incident so long as no circuit is formed These vertices are arbitrarily ordered then in order the same process is followed Using the same graph as before with the arbitrary ordering of children being alphabetic we nd the tree given below Different trees may be obtained by changing the ordering of the children If we had reversed the ordering of the children there would have been an edge from C to D rather than from B to D When the underlying graph is directed these two methods may well produce only a spanning forest TOC Section 5 Minimum spanning trees The notion of a minimum spanning tree only makes sense when the edges are weighted These weights may represent any quantifiable value but quite often refer to distance time or cost Two different algorithms are explored in your text Prim s and Kruskal s Prim s algorithm starts by selecting the edge with the smallest weight and the two vertices incident to it Successively add edges of minimum weight that are incident to vertices which are already in the tree and do not form a circuit Kruskal s algorithm does not require that the tree be a connected graph until the last step Kruskal simply requires that the smallest edge be included provided it does not form a circuit The table below gives the lengths of the edges in a completely connected graph Dist Using Prim s Algorithm we would start with edge B D since it is the shortest Proceeding with the algorithm we obtain the tree below since 391 edges are added only to vertices already in the graph I have numbered quot2 B the edges to indicate the order in which they were added The nal tree 1 A has a weight of 28 While Kruskal s Algorithm also 0 D 2 guarantees us a minimum spanning tree it may not 3 4 B be the same tree as we found with Prim s algorithm E F 1 We also start with edge B D since it is the 3 a Y D smallest Again the edges are labeled in the order C 39 39 G H 39 3 in which they were added The tree is not the same 2 F but the overall sum of the edges is the same With E this particular graph we get the same spanning tree the only difference in 2 I 2 the two is the order in which the edges are added C G H The two algorithms we have considered will give the minimum spanning tree when we require our tree to be a subset of a given graph It may not provide the minimum network for the given vertices if the vertices are placed geometrically to represent physical locations You may have a minimal spanning tree for your graph but if a smaller tree can be made by inserting additional vertices you don t have a minimal network It may seem strange but sometimes having more can lead to getting less There are circumstances where it is possible to get a smaller network by inserting additional vertices These vertices are optimally located at what are called Steiner points Jakob Steiner 1796 1863 was a geometer who discovered this property of the relationship between location and distance between a collection ofpoints He is pictured below A good example of the use of Steiner points is the graph consisting of vertices that form an equilateral triangle with legs of 500 miles each The minimal spanning tree is 1000 miles If we allowed ourselves the ability to create additional vertices and edges as needed we could construct a much smaller network Pictured below we find the three original vertices each 500 miles apart If we only allow ourselves the option o connecting the vertices with edges we have a tree of total weight 1000 miles By inserting a fourth vertex so that the angle between the three edges is 120 degrees we have a network of about 866 miles This is a considerable savings This is also the minimal network for connecting the three poinm 500 288 58 500 To find a Steiner point a Start with three vertices Consider them the vertices of a triangle Only if all of the interior angles of the triangle are less than 120 is there a Steiner point If any angle is greater than 120 then the minimum network is the minimum spanning tree Construct an equilateral triangle using the longest original leg external to the original tri le Construct a circle that circumscribes this new triangle Draw a line connecting the two triangle s apexes The Steiner point is the intersection of this line and the circle The black dots represent the original points The green dot is added to form the triangle external to the original three The circle circumscribes these three points The red dot is the Steiner point What is gained by using a Steiner point at best the difference between the minimum spanning tree and the shortest network is 134 Often it is less than 5 What do we lose by looking for these points In a large network there are a lot of possible Steiner points to look for in fact the number grows at a factorial rate Add to this the relative complexity of finding the points algebraically and we have greatly added to the complexity of specifying our tree Oddly enough we can let soap deal with all of these issues Suppose you build a model of the vertices using two pieces of Plexiglas held about an inch apart with dowels The dowels are to be positioned exactly where the vertices should be Use an appropriate scale for the model so that the dowels are no closer than one or two inches from each other Dip this apparatus in a soap solution The bubbles that form between the dowels will form a network that passes through one set of Steiner points There is no guarantee that this will be the optimum set but it will beat the MST TOC