Discrete Math for CS
Discrete Math for CS ECS 020
Popular in Course
Popular in Engineering Computer Science
This 24 page Class Notes was uploaded by Ashleigh Dare on Tuesday September 8, 2015. The Class Notes belongs to ECS 020 at University of California - Davis taught by Staff in Fall. Since its upload, it has received 53 views. For similar materials see /class/191701/ecs-020-university-of-california-davis in Engineering Computer Science at University of California - Davis.
Reviews for Discrete Math for CS
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/08/15
TODAY Lecture 1 3312009 Notes for ECS 20 Prof Martel 1 Introduction 2 Some Example Problems 1 Introduction Prof Chip Martel and TA Nick Leaf introduced The course homepage is wwwcsucdaviseduma1tel20 A course information sheet is there and you need to read it Problem Set 1 is will go out on Thursday Helpful Background Some math background sophistication Basic programming knowledge 0 Discrete mathematics deals with finite and countably infinite sets 0 Some branches of discrete mathematics are 959 Combinatorics how to count things how to make combinatorial objects that have desired properties Graph theory points and twoelements subsets of them Logic Set theory Probability again routinely treated in discrete math classes but only when we assume that the underlying probability space is finite or countably in nite And much more Course Goals Learn to describe things in precise Math language De ne precisely what programs can do Proof techniques applications to proving programs do what they are intended to Program timespace analysis determine timespace usage Think recursively 2 Some Example Problems Example 1 Find the following sum 12 100 or more generally l2 11 Solution This problem can be Viewed algebraically by writing the list of numbers forwards and backwards ie 2 n l n n nl 2 nlnl nlnl which is nn 1 Since this result is really twice the sum we are looking for it follows that l2nnnl2 Example 2 The Towers of Hanoi l l l l l A B C Five rings of increasing diameter are placed on peg A The pegs must be moved from A to C using the following rules 39 Only the topmost ring on a peg can be moved 39 A bigger ring cannot be placed on a smaller one Problem Find a function that describes the least number of moves needed to solve the problem when you have n rings How many moves do you think it takes to move the five rings One student knew that the answer is 31 We want a formula that specifies a number of moves that is both 39 Suf cient there is a solution to the game using this number of moves 39 Necessary no solution can use fewer moves than this Solution First let s define what we re interested in Let Tn The minimum number of moves needed to move the n rings from peg A to peg C obeying the rules of the game Actually this isn t good We need to generalize the definition to do the job So instead let Tn The minimum number of moves needed to move n rings from some one specified peg to some other specified peg obeying the rules of the game Suf ciency Think recursively Assume a black box algorithm can move the rst n 1 rings from any peg to any other peg Solving the problem this way requires that the first n 1 rings be moved then the largest ring be moved once then the smaller rings be moved on to the largest ring This number of moves can be represented by TH E Tn1l Tn1 2Tn1 l Necessity Now we have to reason about any algorithm that solves the puzzle Any solution must move the largest ring to the nal peg for the very last time That takes one move But before that happened we had to get the nl rings that were formerly on top of the start peg and move them off to a free peg That takes at least Tn1 moves After we got the biggest ring to its destination peg we had to move the nl smaller rings from the free peg where they were at to the nal peg That takes at least Tn1 moves So all in all any solution needs to spend at least TH 2 1 Tn1 Tn1 2TH 1 moves Putting together the two inequalities we have that Tn 2TH l We know that in order to move zero rings to their nal location requires zero moves so To 0 Using this as our base value we can then determine that T1 T2 T3 T4 T5 Tn l 3 7 15 31 2n 1 apparently One way to get the general formula is by repeated substitution T 2 Tn1 1 2 2 Tn2 1 1 22Tn2 1 2 22 2 T3 1 1 223Tn31 24 2 01 222 2 1 222 2 3912 71 Binary Representation Example 2 Prove that X 2 is irrational see page 2 of the text for de nitions of R Z Q and N De nition X E R is rational in the set Q ifX pq for some integers p and q E Z q i 0 X E R is irrational if it is not rational Note if in de nitions mean if and only if or eXactly when Here we prove by contradiction Assume for contradiction that X is rational ie X pq for some integers p and q q i 0 Without a loss of generality it can be assumed that either p is odd or q is odd if they re both even cross out the common factors of 2 until one of the numbers is odd Additionally an odd number squared is still an odd number 2 pq square both sides gt 2 pzq2 multiply through by the denominator a 2q2 p2 From this we know that p is even because the square of an odd number is odd why So we can write p 2j for somej E Z and substituting 2j for p in above we get 2q2 202 gt 2qz 412 gt qz 2jz so by the same reasoning as before q must be odd The contradiction is that we have now shown both p and q are even but we assumed at least one was odd We can conclude that our original assumption is wrong x 2 is not equal to any pq so is not rational which by de nition means that it is irrational Example 3 We claim that 5 shuf es of a deck of cards is not enough to randomize the cards Here by shuf es I mean the usual ri e shuf e For example for a simple deck of 8 cards 1 2 3 4 5 6 7 8 the shuf e breaks it into two groups the top and bottom eg l 2 3 4 and 5 6 7 8 though they need not be equal and interleaves the two groups e g l 5 6 3 7 4 8 to get a new order Even though we won t define what it means to randomize the cards clearly a deck cannot be well randomized unless you can get any resulting sequence of cards including for example the sequence 52 51 3 21 A stronger requirement we won t use is that each of the 52 different orders is equally likely to be produced We are going to show that 5 shuf es of this deck will never transform the specified starting sequence to the specified final sequence So it can t do a good job of mixing the deck More next class Lecture 13 5142009 Announcements Ps7 out Ps6 Midterm solutions out Midterm back median 75 about a low B 1 Infinite Sets Reviewwrap up We showed that the Integers and Rationals Z and Q though infinite are countable in a sense the lowest level of infinity The reals or PN are uncountable but at the next level while PR or P PN are at a higher level of infinity 2 The Pigeonhole Principle Counting 54 If N pigeons roost in n holes Ngtn then some two pigeons share a hole Restated if f A gt B where A and B are finite sets AgtB the f is NOT injective Ex 0 Any room with 3 or more people has some two of the same gender Ex 1 20 people at a party some two have the same number of friends we assume quotfriendsquot is symmetricquot number of friends proof 018 or 119 Ex 2 Given five points inside the square whose side is of length 2 prove that two are within sqrt2 of each other Soln divide square into four 1 x 1 cells Diameter of each cell sqrt2 Ex 3 In any list of 10 integers a1 a10 there39s a string of consecutive numbers whose sum is divisible by 10 Consider al a1 a2 a1 a 2 a 10 If any of these divisible by10 done Otherwise each is congruent to 1 9 mod 10 so two are congruent to the same thing eg 6 mod 5 a4 a 5 6 mod 5 a1 a2 a3 a 1 a 2 a3 But then a4 a5 0 mod 10 Ex 4 In any room of 6 people there are 3 mutual friends or 3 mutual strangers Ramsey theorem Remove person 1 5 people left Put into two pots friends with 1 non friends with 1 One has at least three people If three friends of 1 Case A some two know each other DONE Case B no two know each other DONE If three non friends of 1 Case C Some two of these 3 don t know each other gt those two and 1 are 3 mutual stangers Case D Each pair know each other so we have 3 mutual friends Difficult Puzzle not discussed in class What is the minimum number of people that must assemble in a room such that there will be at least n friends or n non friends Rnn R44 18 1955 R55 open known to be between 43 1989 and 49 1995 R1010 open and not tightly determined at all range 798 1986 23556 2002 The above example uses the quotStrong form of Pigeonhole principle If f A gt B A and B finite sets then some point in B will have at least lceil AB rceil preimages under f Book form if kn1 pigeons and in n holes some hole has at least k1 pigeons for k a positive integer 3 Induction and recursion and analysis recursive programs EXAMPLE 1 Sam39s Dept Store sells enveloped in packages of 5 and 12 Prove that for any ngt 44 the store can sell you exactly n envelopes Try it 44 212 45 45 95 46 312 25 9 9 SUPPOSE it is possible to buy k envelopes for some kge44 SHOW it is possible to buy k1 envelopes If purchasing at least seven packets of 5 trade them for three packets of 12 75 gt 312 35 36 If lt7 packets of 5 ie lt6 packets of 5 so at most 30 of the envelopes are in packets of 5 so there are gt 44 30 14 envelopes being bought in packets of 12 so gt 2 two packets of twelve So take two of the packets of 12 and trade them for 5 packets of 5 212 gt 55 24 25 This is an example of an exchange argument often used on proofs of solution methods Principle of mathematical induction review To prove a proposition Pn for all integers ngt n0 1 Prove Pn0 Basis 2 Prove that Pk gt Pk1 for all k gt n0 inductive step Inductive hypothesis initially make n01 Example Binary Search Suppose we have a sorted list of n numbers in an array A1n and we want to find if a number X is in this list Last lecture we describe an On linear search algorithm here we give an improved method Binary SearchXA low highLooks for X in Alowhigh Start 0ltlow 5 high 5 n Ifigtj Return not foundquot range of A is empty Middle ij 2j IfAMiddle X Return Middle If AMiddle lt X low 6 Middle1 X not in A1Middle If AMiddle gtX high 6 Middle l X not in AMiddlehigh Binary SearchXAlowhigh End To start call Binary SearchXA1n Example A 3510 16 30 60 90 X10 Low1 high 7 Middle 824 A4 16 gt 10 so high middle 13 Middle 132 2 A25 lt 10 so low middle 1 3 Middle 3323 A3 10X return 3 Suppose X 12 Only differs in last step 10 lt X so low 6 4 Next call is to BSXA 43 so 4gt3 and return quotnot foundquot Analysis of Run time We can assume that each iteration of the program not including the recursive call in the last line takes constant time that is it does not depend on n Thus to get the big Theta run time we only need to count the number of calls Let Tn be the maximum number of calls for an array of size n Finish next time and proof of correctness Lecture 9 4282009 Announcements P55 out today Review Problems not to be turned in Ps4 solutions out tomorrow Midterm Tues May 539 Open Book and Notes Coverage through relations today Discussion this Friday Review session run by me Bring questions Relations Continued Re exive X R X for all X Symmetric X R y gt y R X for all Xy Transitive X R y and y R X gt X R z for all X y z l Equivalence classes quotients if R has all three properties R is said to be an equivalence relation 28 Important definition If R is an equivalence relation on A X A then X denotes the set of all elements related to X X X XRX We call X the equivalence class or block ofX The set of all equivalence classes of A with respect to a relation R is denoted AR quotquotient set of A by Rquot or quotA mod Rquot Claim every equivalence relation partitions the universe into its blocks What does this mean Recall we de ned a partitioning of the set A Def Ai i in I is a partition of A if each Ai is nonempty their union is A and they are pairwise disjoint Note you can talk about the blocks being related to one another by R X R y iff X R y Welldefined Now go back to prior examples and identify the blocks in each case Proposition Let R be an equivalence relation on a set A Then the blocks of R are a partition of A Thm 26 in book Proof Every element X of A is in the claimed partition X E X Suppose that X and y intersect I need to argue that they are identical So suppose there eXists a st a E X and a E y I must show that X y So suppose b in X Must show bE y bin X gtXRbistrue gtbRXistrue know XRaistruegtbRaistruegt aRbistrue know aRyistruegtyRaistruegtbeistruegtbiny Suppose b in y Must show b in X EXactly analogous Proposition Suppose you have a partition Ai iE I of A Then this determines a equivalence relation in the natural way X R y iff X E Ai and y E Ai for some i Go back to prior eXamples and identify the blocks EXample 1 alpha E beta if alpha beta regular eXpressions denoting the same language gt each block is the set of regular eXpressions denoting the same language Can you think of a quotcanonicalquot name for each block Could use the lexicographically first regular expression in a block Sounds hard to find the canonical name for a block that is given alpha find the name of alpha Example 2 strings X and y are equivalent if they have the same length gt blocks are the strings of a given length Canonical name 0 Example 3 Fix a DEA like the one we looked at for even as and even b s xy if they go to the same state under M YES gt blocks do a small example like the DEA that checks if inputs and outputs have the same length NOT done in class Example 4 given a regular language L sayxEy if xz inLiffyz ianorallz What are the blocks Example 5 words x and y are equivalent if they are anagrams of each other R is a relation on words in a dictionary Example trap tarp part rapt in the same equivalence class gt blocks are the words that anagram to each other Canonical name alphabetically first word part or could be letters in alphabetical order aprt NOTE the later is not in the set of words Example 6 For integers ab a b IFF a mod m b mod m IFF m ab m NOT DONE In Class Example 7 Let U be the set of people x B y have the same birthday What are the blocks of UB How many elements are there in UB 366 NOT DONE In Class Example 8 Let R be the set of real numbers xy if lfloor x rfloor lfloor y rfloor What are the blocks What would be a quotcanonical elementquot name for each block Example 9 Let R be the set of real number xy if X lfloor X rfloor y lfloor y rfloor What are the blocks What would be a quotcanonical elementquot name for each block Real values in the range 1 l 2 Closures of Relations 27 Given a relation we sometimes want to FORCE it to be re exive or symmetric or transitive or any combination of these We do this by adding just enough extra pairs to get the property Draw a picture for the transitive closure of a directed graph Draw a picture for reflexivetransitive closure Def The transitive closure of a relation R on A x A is the smallest relation R that contains A and is transitive claim this is well defined there is a unique smallest relation R that contains A x A and is transitive In fact it is the intersection of all relations R that are transitive and contain A Procedure to find the transitive closure quotadd in all shortcutsquot In the graphtheoretic realization of the relation R just add an arc ac whenever you have an ab and a bc but lack an ac Example 1 Do it with a graph Example 2 An infinite set example Suppose i R il for all i in Z Transitive closure is what Lecture 10 4302009 Announcements P55 out Review Problems not to be turned in Ps4 solutions out P55 Solutions out later today and Sample midterm solutions Midterm Tues May 539 Open Book and Notes Coverage through relations today Discussion this Friday Review session run by me Bring questions Definition A function f is a relation on A X B such that there is one and only one pair a R b for every a EA We write bfa to mean that ab Ef Just one way to do it we could have defined functions as the primitive and used the function to define the relation putting in a pair afa for every a EA We call A the domain of f Domf We call B the codomain or target of f Note that this does not mean the set b fab for some a in A That is a different and important st called the Range or image of f Denote it fA Example 1 Domain123 fa a 2 Domf 123 fA 149 codomain unclear might be N might be R Example 2 Domain students in this class bX birthdays encoded as 112 X 131 bphil 731 bellen 41 Example 3 f R gt R defined by fX X2 is it a function Represent it as a graph Two functions f and g are equal fg if their domains and ranges are equal and fX gX for all X in Domf Function composition f o g fAgtB gBgtC then g o f A gt C is de ned by g 0 tX gfX Kind of quotbackwardsquot notation but fairly traditional Some algebrists will reverse it X f o g quotfunction operates on the leftquot Some computer scientists like to denote functions by quotlambda eXpressionsquot To say that f is the function that maps X to XAZ we write f lambda X X2 Here X is just a formal variable lambda X X2 lambda y y2 The domain is not eXplicitly Functions don t have to be de ned on numbers of course X maps 2 gt N hdX the rst character of the string X Xg emptystring tlX all but the first character of X define how when Xemptystring dimA the dimensions of the matriX A regarded as a pair of natural numbers Def fA gt B is injective or onetoone if fXfY gt Xy Def fA gt B is surjective or onto if the image is the codomain for all b in B there eXists a in A fab Def fA gt B is bijective ltol and onto if f is inj ective and surj ective Example fX Xl on N ll not onto fX Xl on Z 11 onto fX 2X on N ll not onto fX 2X on R ll onto fX XAZ on R not ll not onto fXyXyonNXN not ll onto fX X etc fX l oor X r oor fX lceil X rceil fX X mod n X an b where a is an integer and b in 0nl f regular eXpressions gt regular eXpressions falpha leX first regular eXpression the language of which is alpha not ll not onto fMl if M is a DFA and LM is infinite 0 otherwise Sometimes a little tricky to see if a function is 11 onto fX 3X mod 4 bijective fX 3X mod 5 not bijective Make a table If fX y we say that X is a preimage of y Does every point in the codomain have a preimage No only points in the image Does every point in the image have one preimage No only if it s an inj ective function Does every point the in the domain have an image Yes that s required by a function Might it have two images No only one So if you do have an bijective function f A gt B the function fquotl B gt A is well defined fquotl y the unique X such that fx y Example fx expx e x Draw picture What s the domain R What s the image 06 f ty Is it 11 on this image YES What s its inverse eXy X1ny Example fx x eX y draw it On what domain does the inverse exists answer 0inf1nity Could you define a larger portion of the curve on which the inverse exists Yes le infinity Graph the function Take its derivative to see that it vanishes at l when the function takes on the value le How would you find the inverse f391 2 for example x eX 2 Binary search 3 Important functions 1cei1 X rceil l oor X r oor a mod b IXI eX Review of properties of logs logab loga logb logab logcb logca eab eab ax ay 2 ainy Draw picture of y 1gX 4 Comparing functions Which is bigger X3 or 2quot Nor formal meaning we know it depends on X But there is some sense in which ZAX seems bigger Draw graphs Lecture 12 5122009 Announcements Ps7 out today Ps6 Midterm solutions out soon Midterm info on Web page Midterm back 12 Asymptotics review Og f N gt R eXists C N st fn lt C gn for all ngt N g f N gt R eXists cC N st c gn lt fn lt C gn for all ngt N Example TrueFalse If f is nAZ then f is OnAZ TRUE n O2An NO n OnAn YES Truth n ne n sqrtn Claim Hn 11 12 ln Olg n Draw picture Upperbound by l integralln lXdX l lnn Olg n show Could I write Olog n Sure Olog n Olg n following not done in class Compute the asymptotic running time of the following algorithm Given a formula phi decide if phi is satisfiable by trying all possible truth assignments Suppose phi has n variables and takes in bits to write down Answer Need to try 2An ta How long to try teach Om All together Om 2An One reason asymptotic notation handy OnAZ OnAZ OnAZ OnAZ OnA3 OnA3 On log n On On log n etc A reason we use asymptotic notation model independence How long does the following code take to run for searching for X in an array A for i1 to n do If AiX Returni Return not foun Takes at most cl n c2 where cl is the work to do one iteration of the for loop and c2 is the maX time for the final retum The total time is On Faster algorithms can do this in Ologn time or even Ol if we can preprocess the array A How long to sort by selection sort repeatedly find the smallest remaining element OnAZ Already enough to distinguish from more sophisticated algorithms 2 How big is that infinity 37 in book Puzzle Which are there more of natural number or integers Mathematicians answer they are the same Not because they are both infinite but because there is a bijective function f N gt E Recall eg fX lceil X2 rceil if X is odd X2 l if X is even Is there a bij ective function from E to N Answer 1 yes automatic from above Answer 2 yes fX 2X if X even 2X1 ifX is odd Puzzle is there a bijective function from N to N X N or equivalently to Q Technique quotDovetailingquot Consider a 2D matrix with the numbers 12 on the top and right aXis Label the 11 entry 1 then the 12 entry 2 and the 21 entry 3 going top to bottom along the diagonal going from right to left Then for the next diagonal give 13 22 31 456 respectively Continue on each diagonal Definition Let A and B be sets We say that A is equinumerous to B A B if there is a bijection f from A to B Definitions not all of these below were done in class A set is finite if it is equinumerous to In 1n for some n E N A set is infinite if it is not finite A set is countably infinite it is equinumerous to N A set is countable if it is finite or countably infinite A set is uncountable if it is not countable Proposition is an equivalence relation Proposition Q is countably infinite Proposition if A and B are countable then so is A X B and A u B Theorem PN is uncountable the powerset of the natural numbers Proof Suppose for contradiction that PN were countable say PN A1 A2 We construct a subset B of N as follows B contains iE iff i is not in Ai Now B is a subset of N so it must be in the enumeration say B A j But is j E B jEBiffjnotEAjB Contradiction Definition For sets A B write A1e B if there exists a onetoone function f A gt B Theorem CantorSchrquotoderBernstein not done in class IfA1eB andB1eA thenAB
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'