11CSC-2259 Discrete StructuresKonstantin BuschLouisiana State UniversityK. Busch - LSUKaynaklar 16.02.2019 K. Busch - LSU ders notlarından çevirilmiştir2web.ogu.edu.tr/egulbandilar2Topics to be covered• Logic and Proofs• Sets, Functions, Sequences, Sums• Integers, Matrices• Induction, Recursion• Counting• Discrete Probability• GraphsK. Busch - LSU 3Binary Arithmetic4Decimal Digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 Binary Digits: 0, 1 Numbers: 9, 28, 211, etcNumbers: 1001, 11100, 11010011, etc(also known as bits)K. Busch - LSU35Binary1001918212020210123Decimal9K. Busch - LSU6Binary Addition Binary Multiplication1001 (9)+ 1 1 (3)------1100 (12)1001 (9)x 1 1 (3)------1001+ 1001---------11011 (27)K. Busch - LSU47xyzxyzxzGatesAND ORNOTxyz000010100111ANDBinary Logicxyz000011101111ORxz0110NOTK. Busch - LSU8An arbitrary binary function is implementedwith NOT, AND, and OR gatesyxxxfn),,,(21y1x2x2xnx…NOTANDORK. Busch - LSU59Propositional LogicProposition: a declarative sentence which is either True or FalseExamples:Today is Wednesday (False)Today it Snows (False)1+1 = 2 (True)1+1 = 1 (False)H20 = water (True)K. Busch - LSU10Propositions can be combined usingthe binary operators AND, OR, NOTWe can map to binary values: True = 1False = 0))(()( cbaqp Example:K. Busch - LSU611TrueTrueTrueTrueFalseFalseFalseTrueTrueFalseFalseTruexyyx Implicationx implies y“You get a computer science degree only if you are a computer science major”You get a computer science degree:x:yYou are a computer science majoryx K. Busch - LSU12TrueTrueTrueTrueFalseFalseFalseTrueFalseFalseFalseTruexyyx Bi-conditionalx if and only if y“There is a received phone call if and only if there is a phone ring”:x:yThere is a received phone callThere is a phone ringyx K. Busch - LSU713SetsSet is a collection of elements:Real numbers RIntegers ZEmpty Set Students in this roomK. Busch - LSU14Subset}5,4,3,2,1{}4,2{ Basic Set Operations24135Union}5,4,3,2,1{}5,4,2{}3,2,1{ 24135K. Busch - LSU815Intersection}2{}5,4,2{}3,2,1{ 24135Complement}5,3,2{}4,1{ }5,4,3,2,1{universeK. Busch - LSU16DeMorgan’s LawsBABA BABA K. Busch - LSU917Inclusion-ExclusionABC|CBA| |||||| |||||| ||CBCABACBACBAK. Busch - LSU18PowersetsContains all subsets of a set}}3,2,1{},3,1{},3,2{},2,1{},3{},2{},1{,{Q}3,2,1{A||2||AQ Powerset of AK. Busch - LSU1019CountingSuppose we are given four objects: a, b, c, dHow many ways are there to order the objects?4321!4 a,b,c,db,a,c,da,b,d,cb,a,d,c … and so onK. Busch - LSU20CombinationsGiven a set S with n elementshow many subsets exist with m elements? )!(!!mnmnmnExample:3)!23(!2!323}3,1{},3,2{},2,1{ }3,2,1{SK. Busch - LSU1121Sterling’s Approximationnennn2!K. Busch - LSU22ProbabilitiesWhat is the probability the a dice gives 5?Sample space = {1,2,3,4,5,6}Event set = {5}K. Busch - LSU61space sample of Sizesetevent of Size{5})obability(Pr 1223What is the probability that two dice give the same number?23Sample Space = {{1,1},{1,2},{1,3}, …., {6,5}, {6,6}}Event set = {{1,1},{2,2},{3,3},{4,4},{5,5},{6,6}}K. Busch - LSU366space sample of Sizesetevent of Sizenumber}) {sameobability(Pr 24Randomized AlgorithmsQuicksort(A):If ( |A| == 1)return the one item in AElsep = RandomElement(A)L = elements less than pH = elements higher than pB = Quicksort(L)C = Quicksort(H)return(BC)K. Busch - LSU1325Graph TheoryK. Busch - LSUMiamiAtlantaNew YorkBostonChicagoBaton RougeLas VegasSan FranciscoLos Angeles2000 miles1500 miles1500150010002000700150030080070015001000100080026Shortest Path from Los Angeles to BostonK. Busch - LSUBostonLos Angeles20001500150015001000200070015003008007001500100010008001427Maximum number of edges in a graphwith nodes:22)1()!2(!2!22nnnnnnnClique with five nodes5n10edgesnK. Busch - LSU28Other interesting graphsBipartite GraphTreesK. Busch - LSU1529Recursion)1()(  nfnnf1)1(2)(  nfnfBasis1)1( f1)1( fBasisnnnf  )1(4321)( Sum of arithmetic sequenceSum of geometric sequence)1(321022222)(nnf K. Busch - LSU30nnfnf 22)( )2(1)(  nfnfnf1)1( f1)1(,0)0(  ffFibonacci numbersBasisDivide and conquer algorithms (Quicksort)K. Busch - LSU1631InductionContradictionPigeonhole principleProof TechniquesK. Busch - LSU322)1()(nnnfProof by InductionInduction Basis:2)11(11)1(fInduction Hypothesis:2)1()1(nnnf2)1(22)1()1()(2nnnnnnnnfnnfInduction Step:)1()(  nfnnfProve:K. Busch - LSU1733Proof by Contradiction2is irrationalSupposenm2( and have no common divisor greater than 1 )mn222nmm2is evenm is even2 n2= 4k2n2= 2k2n is evenm=2kContradictionK. Busch -