Discrete Math for CS
Discrete Math for CS ECS 020
Popular in Course
Popular in Engineering Computer Science
This 7 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 Phillip Rogaway in Fall. Since its upload, it has received 44 views. For similar materials see /class/187709/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.
Date Created: 09/08/15
Lecture 1 Notes for ECS 20 Prof Rogaway Scribe Blake T TODAY 1 Introduction 2 Some Example Problems 3 Sentential Logic but we didn t get to this 1 Introduction Prof Phil Rogaway introduced himself The TAs Tung and MinEu introduced themselves The course homepage is wwwcsucdavisedurogaway A course information sheet is there and you need to read it Problem Set 1 is due on Monday see the course information sheet 0 Discrete mathematics deals with finite and countably infinite sets 0 Seems to be a term rarely used by mathematicians who say what the are doing more specifically 0 Some branches of discrete mathematics are 0 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 normally dealt with in a class like this but much modern set theory is not dealing with finite or countably infinite sets Probability again routinely treated in discrete math classes but only when we assume that the underlying probability space is finite or countably infinite 0 And much more Helpful Techniques for Solving Discrete Math Problems Generalize the problem in the right way Introduce variables eg substituting n for 100 in EX 0 Group terms cleverly e g the algebraic analysis of EX 0 Name the things that you are interested in Think recursively Solve small cases by hand and look for emerging patterns Substitute repeatedly to simplify recurrence relations Use contradiction this is demonstrated in EX 2 908994P N 9 Follow your nose often only one natural path to go down eg EX 2 2 Some Example Problems Example 0 Find the following sum 1 2 100 or more generally 1 2 n Solution This problem can be Viewed algebraically by writing the list of numbers forwards and backwards ie 2 nl n n nl 2 11 1n 1 n ln 1 which is nn 1 Since this result is really twice the sum we are looking for it follows that l2nnnl2 This example can also be solved geometrically by writing twice 1 2 n points in the following way n points n5 in the picture 9696969696 969696960 96969600 9696000 960000 n 1 points n5 in the picture So he total number of points is n n 1 2 which is the sum we are after Example 1 The Towers of Hanoi l 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 0 Only the topmost ring on a peg can be moved 0 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 Nobody guessed it or figured it out Rogaway claims that the answer is 31 We want a formula that specifies a number of moves that is both 0 Suf cient there is a solution to the game using this number of moves 0 Necessary no solution can use fewer moves than this Solution First let s de ne 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 de nition to do the job So instead let Tn The minimum number of moves needed to move n rings from some one speci ed peg to some other speci ed 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 rst 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 Tn1 l 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 Tm 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 2Tn1 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 Tn 2 Tm 1 2 2 Tn2 1 1 22Tn2 1 2 222T3111223T3124 2 01 222 2 1 222 2 12 71 Binary Representation Example 2 Prove that X 2 is irrational De nition X E R is rational 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 gt 2qz p2 From this we know that p is even because the square of an odd number is odd why But then q is odd because we know that at least one ofp and q is odd So we can write p 2j for somej E Z and q2i1forsomei Z a 2 2i 12 21392 gt 2i 12 2f gt 4i2 4i 1 2j2 gt4i2i1 2 N The contradiction is that an odd number the LHS can equal an even number the RHS We can conclude that our original assumption is wrong x 2 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 Prof Rogaway demonstrates one with an imaginary deck Assume a starting sequence of 1 2 3 51 52 Even though we won t de ne 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 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 We didn t finish doing this but we introduced an idea corrected in these notes that Prof Rogaway claimed would help To illustrate the idea let s look at a small deck of cards say 8 cards that for example happens to be in the order S 36721845 This sequences contains four subsequences of successive integers namely Q 345 an 678 an 1 an 2 llCL These are called the rising sequences of S A rising sequence R from S is a sequence of successive integers that appear as a not necessarily consecutive subsequence of S anal that has the property that it cannot be extended either to the left or to the right while remaining a sequence of successive integers appearing as a subsequence of S In other words a rising sequence in S is any maximal 39 J ofS 39 quot of 39 integers We re interested in how many rising sequences it takes to cover some given sequence S For the example above the answer was 4 Once we remove the rising sequence 345 we are left with 67218 then we might remove the rising sequence 678 and we ll be left with 21 then we might remove the rising sequence 2 and we ll have just 1 left and then we d have to remove 1 and we d be done No matter what order you remove the rising sequences from S they ll always be 4 of them to remove until you exhaust S That s because the rising sequences of S are uniquely determined by S To see this note that if you name a number i in S then there s going to be a unique rising sequence containing iithe one determined in the obvious way by going to the left and right from i and grabbing whatever you can How many rising sequences does it take to cover the sequence 1 2 51 52 That s easy just 1 Namely S itself is a rising sequence that covers S How many rising sequences does it take to cover the sequence 52 51 2 1 That s the other end ofthe spectrum 52 Each rising sequence is just a single number i Now what on earth does any of this rising sequence stuff have to do with proving that ve shuf es is inadequate to randomize a deck of cards We ll nd out next time