CSC 2259 Discrete Structures Konstantin Busch Louisiana State University K Busch LSU 1 Kaynaklar web ogu edu tr egulbandilar 16 02 2019 K Busch LSU ders notlar ndan evirilmi tir 2 1 Topics to be covered Logic and Proofs Sets Functions Sequences Sums Integers Matrices Induction Recursion Counting Discrete Probability Graphs K Busch LSU 3 Binary Arithmetic Decimal Digits 0 1 2 3 4 5 6 7 8 9 Numbers 9 28 211 etc Binary Digits 0 1 also known as bits Numbers 1001 11100 11010011 etc K Busch LSU 4 2 Binary 1001 Decimal 9 K Busch LSU 5 Binary Addition Binary Multiplication 1001 9 1 1 3 1100 12 1001 9 x 1 1 3 1001 1001 11011 27 K Busch LSU 6 3 918212020210123 Binary Logic AND x y z 0 0 0 0 1 0 1 0 0 1 1 1 OR x y z 0 0 0 0 1 1 1 0 1 1 1 1 NOT x z 0 1 1 0 Gates AND OR K Busch LSU NOT 7 An arbitrary binary function is implemented with NOT AND and OR gates OR NOT AND K Busch LSU 8 4 xyzxyzxzyxxxfn 21 y1x2x2xnx Propositional Logic Proposition a declarative sentence which is either True or False Examples Today is Wednesday False Today it Snows False 1 1 2 True 1 1 1 False H20 water True K Busch LSU 9 We can map to binary values True 1 False 0 Propositions can be combined using the binary operators AND OR NOT Example K Busch LSU 10 5 cbaqp Implication True True False False True True False False True False True True x implies y You get a computer science degree only if you are a computer science major You get a computer science degree You are a computer science major K Busch LSU 11 Bi conditional True True False False True False True True False False False True x if and only if y There is a received phone call if and only if there is a phone ring There is a received phone call There is a phone ring K Busch LSU 12 6 xyyx x yyx xyyx x yyx Sets Set is a collection of elements Real numbers R Integers Z Empty Set Students in this room K Busch LSU 13 Basic Set Operations 1 2 4 3 5 Subset Union 1 3 2 4 5 K Busch LSU 14 7 5 4 3 2 1 4 2 5 4 3 2 1 5 4 2 3 2 1 Intersection 1 3 2 4 5 Complement universe K Busch LSU 15 DeMorgan s Laws K Busch LSU 16 8 2 5 4 2 3 2 1 5 3 2 4 1 5 4 3 2 1 BABA BABA Inclusion Exclusion A B C K Busch LSU 17 Powersets Contains all subsets of a set Powerset of A K Busch LSU 18 9 CBA CBCABACBACBA 3 2 1 3 1 3 2 2 1 3 2 1 Q 3 2 1 A 2 AQ Counting Suppose we are given four objects a b c d How many ways are there to order the objects a b c d b a c d a b d c b a d c and so on K Busch LSU 19 Combinations Given a set S with n elements how many subsets exist with m elements Example K Busch LSU 20 10 4321 4 mnmnmn 3 23 2 323 3 1 3 2 2 1 3 2 1 S Sterling s Approximation K Busch LSU 21 Probabilities What is the probability the a dice gives 5 Event set 5 Sample space 1 2 3 4 5 6 K Busch LSU 22 11 nennn 2 61space sample of Sizesetevent of Size 5 obability Pr What is the probability that two dice give the same number Event set 1 1 2 2 3 3 4 4 5 5 6 6 Sample Space 1 1 1 2 1 3 6 5 6 6 K Busch LSU 23 23 Randomized Algorithms Quicksort A If A 1 return the one item in A Else p RandomElement A L elements less than p H elements higher than p B Quicksort L C Quicksort H return BC K Busch LSU 24 12 366space sample of Sizesetevent of Sizenumber sameobability Pr Graph Theory San Francisco Chicago 1500 miles 2000 miles 800 1500 1500 700 Las Vegas 1000 1000 1500 2000 1000 Baton Rouge 1500 Los Angeles Boston 300 New York 800 Atlanta 700 Miami K Busch LSU 25 Shortest Path from Los Angeles to Boston 700 1000 2000 800 1500 1000 1500 2000 Boston 1500 1500 1000 1500 300 800 700 Los Angeles K Busch LSU 26 13 Maximum number of edges in a graph with nodes Clique with five nodes K Busch LSU 27 Other interesting graphs Trees Bipartite Graph K Busch LSU 28 14 22 1 2 2 22nnnnnnn 5 n10 edgesn Recursion Sum of arithmetic sequence Basis Basis Sum of geometric sequence K Busch LSU 29 Fibonacci numbers Basis Divide and conquer algorithms Quicksort K Busch LSU 30 15 1 nfnnf1 1 2 nfnf1 1 f1 1 fnnnf 1 4321 1 321022222 nnf nnfnf 22 2 1 nfnfnf1 1 f1 1 0 0 ff Proof Techniques Induction Contradiction Pigeonhole principle K Busch LSU 31 Proof by Induction Prove Induction Basis Induction Hypothesis Induction Step K Busch LSU 32 16 2 1 nnnf2 11 11 1 f2 1 1 nnnf 2 1 22 1 1 2 nnnnnnnnfnnf 1 nfnnf Proof by Contradiction is irrational Suppose and have no common divisor greater than 1 m2 is even m 2k m is even 2 n2 4k2 n2 2k2 n is even K Busch LSU Contradiction 33 17 2nm 2mn222nm