Discrete Structures for Computer Science: Counting ...

1 Discrete Structures for Computer Science: Counting , Recursion, and ProbabilityMichiel SmidSchool of Computer ScienceCarleton UniversityOttawa, 22, 2019 ContentsPrefacevii1 Ramsey Theory .. Sperner s Theorem .. The Quick-Sort Algorithm ..52 Mathematical Basic Concepts .. Proof Techniques .. proofs .. proofs .. proofs .. by contradiction .. by induction .. examples of proofs .. Asymptotic Notation .. Logarithms .. Exercises .. 233 The Product Rule .. Bitstrings of Lengthn.. Functions .. Books on Shelves .. The Bijection Rule.

2 The Complement Rule .. The Sum Rule .. The Principle of Inclusion and Exclusion .. Permutations and Binomial Coefficients .. Examples .. s Binomial Theorem .. Combinatorial Proofs .. Pascal s Triangle .. More Counting Problems .. the Letters of a Word .. Solutions of Linear Equations .. The Pigeonhole Principle .. India Pale Ale .. Sequences Containing Divisible Numbers .. Long Monotone Subsequences .. There are Infinitely Many Primes .. Exercises .. 594 Recursive Functions .. Fibonacci Numbers.

3 00-Free Bitstrings .. A Recursively Defined Set .. A Gossip Problem .. Euclid s Algorithm .. Modulo Operation .. Algorithm .. Running Time .. The Merge-Sort Algorithm .. of AlgorithmMergeSort.. Time of AlgorithmMergeSort.. Computing the Closest Pair .. Basic Approach .. Recursive Algorithm .. Counting Regions when Cutting a Circle .. Polynomial Upper Bound onRn.. Recurrence Relation forRn.. the Recurrence Relation .. the Recurrence Relation .. Exercises .. 125 Contentsv5 Discrete Anonymous Broadcasting .. Probability Spaces.

4 Basic Rules of Probability .. Uniform Probability Spaces .. Probability of Getting a Full House .. The Birthday Paradox .. Balls into Boxes .. The Big Box Problem .. Probability of Finding the Big Box .. The Monty Hall Problem .. Conditional Probability .. s Children .. a Die .. and Flip or Roll .. The Law of Total Probability .. a Coin and Rolling Dice .. Please Take a Seat .. Determiningpn,kUsing a Recurrence Relation .. Determiningpn,kby Modifying the Algorithm .. Independent Events .. Rolling Two Dice .. A Basic Property of Independent Events.

5 Pairwise and Mutually Independent Events .. Describing Events by Logical Propositions .. Flipping a Coin and Rolling a Die .. Flipping Coins .. The Probability of a Circuit Failing .. Choosing a Random Element in a Linked List .. Long Runs in Random Bitstrings .. Infinite Probability Spaces .. Infinite Series .. Who Flips the First Heads .. Who Flips the Second Heads .. Exercises .. 231viContents6 Random Variables and Random Variables .. Three Coins .. Variables and Events .. Independent Random Variables .. Distribution Functions .. Expected Values.

6 Examples .. the Expected Values of Comparable Ran-dom Variables .. Alternative Expression for the Expected Value .. Linearity of Expectation .. The Geometric Distribution .. the Expected Value .. The Binomial Distribution .. the Expected Value .. the Linearity of Expectation .. Indicator Random Variables .. in Random Bitstrings .. Elements in Prefixes of Random Permutations the Harmonic Number .. The Insertion-Sort Algorithm .. The Quick-Sort Algorithm .. Skip Lists .. AlgorithmSearch.. AlgorithmsInsertandDelete.. Analysis of Skip Lists.

7 Exercises .. 3297 The Probabilistic Large Bipartite Subgraphs .. Ramsey Theory .. Sperner s Theorem .. The Jaccard Distance between Finite Sets .. First Proof .. Second Proof .. Planar Graphs and the Crossing Lemma .. Graphs .. Crossing Number of a Graph .. Exercises .. 391viiiContentsPrefaceThis is a free textbook for an undergraduate course on Discrete Structuresfor Computer Science students, which I have been teaching at Carleton Uni-versity since the fall term of 2013. The material is offered as the second-yearcourse COMP 2804 ( Discrete Structures II). Students are assumed to havetaken COMP 1805 ( Discrete Structures I)

8 , which covers mathematical rea-soning, basic proof techniques, sets, functions, relations, basic graph theory,asymptotic notation, and a 12-week term with three hours of classes per week, I cover mostof the material in this book, except for Chapter 2, which has been includedso that students can review the material from COMP 2 is largely taken from the free textbookIntroduction to Theoryof Computationby Anil Maheshwari and Michiel Smid, which is available ~michiel/TheoryOfComputation/Please let me know if you find errors, typos, simpler proofs, comments,omissions, or if you think that some parts of the book need improvement.

9 XChapter 1 IntroductionIn this chapter, we introduce some problems that will be solved later in thisbook. Along the way, we recall some notions from Discrete mathematics thatyou are assumed to be familiar with. These notions are reviewed in moredetail in Chapter Ramsey TheoryRamsey Theory studies problems of the following form: How many elementsof a given type must there be so that we can guarantee that some propertyholds? In this section, we consider the case when the elements are peopleand the property is there is a large group of friends or there is a large groupof strangers .Theorem any group of six people, there are three friends, , three people who know each other, or three strangers, , three people, none of which knows the other order to prove this theorem, we denote the six people byP1,P2.

10 , two peoplePiandPjare eitherfriendsorstrangers. We define thecomplete graphG= (V,E) with vertex setV={Pi: 1 i 6}and edge setE={PiPj: 1 i < j 6}.2 Chapter that|V|= 6 and|E|= 15. We draw each edgePiPjas a straight-linesegment according to the following rule: IfPiandPjare friends, then the edgePiPjis drawn as asolidsegment. IfPiandPjare strangers, then the edgePiPjis drawn as the example below,P3andP5are friends, whereasP1andP3are that a group of three friends corresponds to a solid triangle inthe graphG, whereas a group of three strangers corresponds to a dashedtriangle. In the example above, there is no solid triangle and, thus, thereis no group of three friends.