A Subset of the URM Language; FA and NFA This Note turns to a special case of the URM program- ming language that we call Finite Automata, for short FA. This part presents almost a balance of How To and Limitations of Computing topics. Main feature of the latter will be the so-called “Pump- ing […]
EECS 70 Discrete Mathematics and Probability Theory Fall 2020 Geometric and Poisson Distributions Note 19 Recall our basic probabilistic experiment of tossing a biased coin n times. This is a very simple model, yet surprisingly powerful. Many important probability distributions that are widely used to model real-world phenomena can be derived from looking at this
EECS 70 Discrete Mathematics and Probability Theory Fall 2020 Two Killer Applications: Hashing and Load Balancing Note 18 In this note, we will see that the simple balls-and-bins process can be used to model a surprising range of phenomena. Recall that in this process we distribute k balls into n bins, where each ball is
EECS 70 Discrete Mathematics and Probability Theory Fall 2020 Continuous Probability Distributions Note 20 Up to now we have focused exclusively on discrete sample spaces Ω, where the number of sample points ω ∈ Ω is either finite or countably infinite (such as the integers). As a consequence, we have only been able to talk
EECS 70 Discrete Mathematics and Probability Theory Fall 2020 Finite Markov Chains Note 21 These notes explain the theory of finite Markov chains. For CS70, we do not cover the proofs that are discussed in Appendix 2. Introduction Markov chains are models of random motion in a finite or countable set. These models are powerful
EECS 70 Discrete Mathematics and Probability Theory Fall 2020 1 Mathematical Induction Note 3 Introduction. In this note, we introduce the proof technique of mathematical induction. Induction is a powerful tool which is used to establish that a statement holds for all natural numbers. Of course, there are infinitely many natural numbers — induction provides
EECS 70 Discrete Mathematics and Probability Theory Fall 2020 1 Proofs Note 2 In science, evidence is accumulated through experiments to assert the validity of a statement. Mathematics, in contrast, aims for a more absolute level of certainty. A mathematical proof provides a means for guar- anteeing that a statement is true. Proofs are very
EECS 70 Discrete Mathematics and Probability Theory Fall 2020 Review of Sets and Mathematical Notation Note 0 A set is a well defined collection of objects. These objects are called elements or members of the set, and they can be anything, including numbers, letters, people, cities, and even other sets. By convention, sets are usually
EECS 70 Discrete Mathematics and Probability Theory Fall 2020 1 Propositional Logic Note 1 In order to be fluent in working with mathematical statements, you need to understand the basic framework of the language of mathematics. This first lecture, we will start by learning about what logical forms math- ematical theorems may take, and how
EECS 70 Discrete Mathematics and Probability Theory Fall 2020 1 Graph Theory: An Introduction Note 5 One of the fundamental ideas is the notion of abstraction: capturing the essence or the core of some complex situation by a simple model. This sense of abstraction as the heart of approximate modeling is something that we use