MARC record from Internet Archive

LEADER: 11431cam 2200709 i 4500
001 ocn960841613
003 OCoLC
005 20210804113019.0
008 160921t20172017enka b 001 0 eng
010 $a 2016041654
040 $aDLC$beng$erda$cDLC$dBTCTA$dOCLCF$dOCLCO$dSEA$dYDX$dOCLCO$dCHVBK$dOCLCO$dEQO$dDHA$dOCLCQ$dUX0$dAU@$dUKMGB$dOCLCQ$dCDN
015 $aGBB6K3612$2bnb
016 7 $a018140964$2Uk
019 $a999472452
020 $a9781107154889$qhardcover
020 $a110715488X$qhardcover
035 $a(OCoLC)960841613$z(OCoLC)999472452
042 $apcc
050 00 $aQA274$b.M574 2017
082 00 $a518/.1$223
084 $a519.2$223
100 1 $aMitzenmacher, Michael,$d1969-$eauthor.
245 10 $aProbability and computing :$brandomization and probabilistic techniques in algorithms and data analysis /$cMichael Mitzenmacher, Eli Upfal.
250 $aSecond edition.
264 1 $aCambridge, United Kingdom ;$aNew York, NY :$bCambridge University Press,$c2017.
264 4 $c©2017
300 $axx, 467 pages :$billustrations ;$c27 cm
336 $atext$btxt$2rdacontent
337 $aunmediated$bn$2rdamedia
338 $avolume$bnc$2rdacarrier
520 $a"Greatly expanded, this new edition requires only an elementary background in discrete mathematics and offers a comprehensive introduction to the role of randomization and probabilistic techniques in modern computer science. Newly added chapters and sections cover topics including normal distributions, sample complexity, VC dimension, Rademacher complexity, power laws and related distributions, cuckoo hashing, and the Lovasz Local Lemma. Material relevant to machine learning and big data analysis enables students to learn modern techniques and applications. Among the many new exercises and examples are programming-related exercises that provide students with excellent training in solving relevant problems. This book provides an indispensable teaching tool to accompany a one- or two-semester course for advanced undergraduate students in computer science and applied mathematics"--$cProvided by publisher.
504 $aIncludes bibliographical references and index.
505 0 $aMachine generated contents note: 1.1.Application: Verifying Polynomial Identities -- 1.2.Axioms of Probability -- 1.3.Application: Verifying Matrix Multiplication -- 1.4.Application: Naïve Bayesian Classifier -- 1.5.Application: A Randomized Min-Cut Algorithm -- 1.6.Exercises -- 2.1.Random Variables and Expectation -- 2.1.1.Linearity of Expectations -- 2.1.2.Jensen's Inequality -- 2.2.The Bernoulli and Binomial Random Variables -- 2.3.Conditional Expectation -- 2.4.The Geometric Distribution -- 2.4.1.Example: Coupon Collector's Problem -- 2.5.Application: The Expected Run-Time of Quicksort -- 2.6.Exercises -- 3.1.Markov's Inequality -- 3.2.Variance and Moments of a Random Variable -- 3.2.1.Example: Variance of a Binomial Random Variable -- 3.3.Chebyshev's Inequality -- 3.3.1.Example: Coupon Collector's Problem -- 3.4.Median and Mean -- 3.5.Application: A Randomized Algorithm for Computing the Median -- 3.5.1.The Algorithm -- 3.5.2.Analysis of the Algorithm -- 3.6.Exercises
505 0 $aNote continued: 4.1.Moment Generating Functions -- 4.2.Deriving and Applying Chernoff Bounds -- 4.2.1.Chernoff Bounds for the Sum of Poisson Trials -- 4.2.2.Example: Coin Flips -- 4.2.3.Application: Estimating a Parameter -- 4.3.Better Bounds for Some Special Cases -- 4.4.Application: Set Balancing -- 4.5.The Hoeffding Bound -- 4.6.Application: Packet Routing in Sparse Networks -- 4.6.1.Permutation Routing on the Hypercube -- 4.6.2.Permutation Routing on the Butterfly -- 4.7.Exercises -- 5.1.Example: The Birthday Paradox -- 5.2.Balls into Bins -- 5.2.1.The Balls-and-Bins Model -- 5.2.2.Application: Bucket Sort -- 5.3.The Poisson Distribution -- 5.3.1.Limit of the Binomial Distribution -- 5.4.The Poisson Approximation -- 5.4.1.Example: Coupon Collector's Problem, Revisited -- 5.5.Application: Hashing -- 5.5.1.Chain Hashing -- 5.5.2.Hashing: Bit Strings -- 5.5.3.Bloom Filters -- 5.5.4.Breaking Symmetry -- 5.6.Random Graphs -- 5.6.1.Random Graph Models
505 0 $aNote continued: 5.6.2.Application: Hamiltonian Cycles in Random Graphs -- 5.7.Exercises -- 5.8.An Exploratory Assignment -- 6.1.The Basic Counting Argument -- 6.2.The Expectation Argument -- 6.2.1.Application: Finding a Large Cut -- 6.2.2.Application: Maximum Satisfiability -- 6.3.Derandomization Using Conditional Expectations -- 6.4.Sample and Modify -- 6.4.1.Application: Independent Sets -- 6.4.2.Application: Graphs with Large Girth -- 6.5.The Second Moment Method -- 6.5.1.Application: Threshold Behavior in Random Graphs -- 6.6.The Conditional Expectation Inequality -- 6.7.The Lovasz Local Lemma -- 6.7.1.Application: Edge-Disjoint Paths -- 6.7.2.Application: Satisfiability -- 6.8.Explicit Constructions Using the Local Lemma -- 6.8.1.Application: A Satisfiability Algorithm -- 6.9.Lovasz Local Lemma: The General Case -- 6.10.The Algorithmic Lovasz Local Lemma -- 6.11.Exercises -- 7.1.Markov Chains: Definitions and Representations
505 0 $aNote continued: 7.1.1.Application: A Randomized Algorithm for 2-Satisfiability -- 7.1.2.Application: A Randomized Algorithm for 3-Satisfiability -- 7.2.Classification of States -- 7.2.1.Example: The Gambler's Ruin -- 7.3.Stationary Distributions -- 7.3.1.Example: A Simple Queue -- 7.4.Random Walks on Undirected Graphs -- 7.4.1.Application: An s-t Connectivity Algorithm -- 7.5.Parrondo's Paradox -- 7.6.Exercises -- 8.1.Continuous Random Variables -- 8.1.1.Probability Distributions in R -- 8.1.2.Joint Distributions and Conditional Probability -- 8.2.The Uniform Distribution -- 8.2.1.Additional Properties of the Uniform Distribution -- 8.3.The Exponential Distribution -- 8.3.1.Additional Properties of the Exponential Distribution -- 8.3.2.Example: Balls and Bins with Feedback -- 8.4.The Poisson Process -- 8.4.1.Interarrival Distribution -- 8.4.2.Combining and Splitting Poisson Processes -- 8.4.3.Conditional Arrival Time Distribution
505 0 $aNote continued: 8.5.Continuous Time Markov Processes -- 8.6.Example: Markovian Queues -- 8.6.1.M/M/1 Queue in Equilibrium -- 8.6.2.M/M/1/K Queue in Equilibrium -- 8.6.3.The Number of Customers in an M/M/infinity Queue -- 8.7.Exercises -- 9.1.The Normal Distribution -- 9.1.1.The Standard Normal Distribution -- 9.1.2.The General Univariate Normal Distribution -- 9.1.3.The Moment Generating Function -- 9.2.Limit of the Binomial Distribution -- 9.3.The Central Limit Theorem -- 9.4.Multivariate Normal Distributions -- 9.4.1.Properties of the Multivariate Normal Distribution -- 9.5.Application: Generating Normally Distributed Random Values -- 9.6.Maximum Likelihood Point Estimates -- 9.7.Application: EM Algorithm For a Mixture of Gaussians -- 9.8.Exercises -- 10.1.The Entropy Function -- 10.2.Entropy and Binomial Coefficients -- 10.3.Entropy: A Measure of Randomness -- 10.4.Compression -- 10.5.Coding: Shannon's Theorem -- 10.6.Exercises -- 11.1.The Monte Carlo Method
505 0 $aNote continued: 11.2.Application: The DNF Counting Problem -- 11.2.1.The Naive Approach -- 11.2.2.A Fully Polynomial Randomized Scheme for DNF Counting -- 11.3.From Approximate Sampling to Approximate Counting -- 11.4.The Markov Chain Monte Carlo Method -- 11.4.1.The Metropolis Algorithm -- 11.5.Exercises -- 11.6.An Exploratory Assignment on Minimum Spanning Trees -- 12.1.Variation Distance and Mixing Time -- 12.2.Coupling -- 12.2.1.Example: Shuffling Cards -- 12.2.2.Example: Random Walks on the Hypercube -- 12.2.3.Example: Independent Sets of Fixed Size -- 12.3.Application: Variation Distance Is Nonincreasing -- 12.4.Geometric Convergence -- 12.5.Application: Approximately Sampling Proper Colorings -- 12.6.Path Coupling -- 12.7.Exercises -- 13.1.Martingales -- 13.2.Stopping Times -- 13.2.1.Example: A Ballot Theorem -- 13.3.Wald's Equation -- 13.4.Tail Inequalities for Martingales -- 13.5.Applications of the Azuma-Hoeffding Inequality -- 13.5.1.General Formalization
505 0 $aNote continued: 13.5.2.Application: Pattern Matching -- 13.5.3.Application: Balls and Bins -- 13.5.4.Application: Chromatic Number -- 13.6.Exercises -- 14.1.The Learning Setting -- 14.2.VC Dimension -- 14.2.1.Additional Examples of VC Dimension -- 14.2.2.Growth Function -- 14.2.3.VC dimension component bounds -- 14.2.4.c-nets and c-samples -- 14.3.The c-net Theorem -- 14.4.Application: PAC Learning -- 14.5.The c-sample Theorem -- 14.5.1.Application: Agnostic Learning -- 14.5.2.Application: Data Mining -- 14.6.Rademacher Complexity -- 14.6.1.Rademacher Complexity and Sample Error -- 14.6.2.Estimating the Rademacher Complexity -- 14.6.3.Application: Agnostic Learning of a Binary Classification -- 14.7.Exercises -- 15.1.Pairwise Independence -- 15.1.1.Example: A Construction of Pairwise Independent Bits -- 15.1.2.Application: Derandomizing an Algorithm for Large Cuts -- 15.1.3.Example: Constructing Pairwise Independent Values Modulo a Prime
505 0 $aNote continued: 15.2.Chebyshev's Inequality for Pairwise Independent Variables -- 15.2.1.Application: Sampling Using Fewer Random Bits -- 15.3.Universal Families of Hash Functions -- 15.3.1.Example: A 2-Universal Family of Hash Functions -- 15.3.2.Example: A Strongly 2-Universal Family of Hash Functions -- 15.3.3.Application: Perfect Hashing -- 15.4.Application: Finding Heavy Hitters in Data Streams -- 15.5.Exercises -- 16.1.Power Law Distributions: Basic Definitions and Properties -- 16.2.Power Laws in Language -- 16.2.1.Zipf's Law and Other Examples -- 16.2.2.Languages via Optimization -- 16.2.3.Monkeys Typing Randomly -- 16.3.Preferential Attachment -- 16.3.1.A Formal Version -- 16.4.Using the Power Law in Algorithm Analysis -- 16.5.Other Related Distributions -- 16.5.1.Lognormal Distributions -- 16.5.2.Power Law with Exponential Cutoff -- 16.6.Exercises -- 17.1.The Power of Two Choices -- 17.1.1.The Upper Bound -- 17.2.Two Choices: The Lower Bound
505 0 $aNote continued: 17.3.Applications of the Power of Two Choices -- 17.3.1.Hashing -- 17.3.2.Dynamic Resource Allocation -- 17.4.Cuckoo Hashing -- 17.5.Extending Cuckoo Hashing -- 17.5.1.Cuckoo Hashing with Deletions -- 17.5.2.Handling Failures -- 17.5.3.More Choices and Bigger Bins -- 17.6.Exercises.
650 0 $aAlgorithms.
650 0 $aProbabilities.
650 0 $aStochastic analysis.
650 7 $aAlgorithms.$2fast$0(OCoLC)fst00805020
650 7 $aProbabilities.$2fast$0(OCoLC)fst01077737
650 7 $aStochastic analysis.$2fast$0(OCoLC)fst01133499
650 7 $aAlgorithmentheorie$2gnd
650 7 $aStochastische Analysis$2gnd
650 7 $aWahrscheinlichkeitstheorie$2gnd
700 1 $aUpfal, Eli,$d1954-$eauthor.
856 42 $3Contributor biographical information$uhttps://www.loc.gov/catdir/enhancements/fy1618/2016041654-b.html
856 42 $3Publisher description$uhttps://www.loc.gov/catdir/enhancements/fy1618/2016041654-d.html
856 41 $3Table of contents only$uhttps://www.loc.gov/catdir/enhancements/fy1618/2016041654-t.html
938 $aYBP Library Services$bYANK$n13053385
938 $aBaker and Taylor$bBTCP$nBK0019680299
029 1 $aCHVBK$b488624665
029 1 $aCHBIS$b010807063
029 1 $aUKMGB$b018140964
029 1 $aDKDLA$b820030-katalog:2200933
994 $aZ0$bP4A
948 $hNO HOLDINGS IN P4A - 105 OTHER HOLDINGS