Honors Course in Classical Civilization
Honors Course in Classical Civilization CLASSIC H195
Popular in Course
Popular in Classical Studies
This 4 page Class Notes was uploaded by Mrs. Adela Rohan on Thursday October 22, 2015. The Class Notes belongs to CLASSIC H195 at University of California - Berkeley taught by Staff in Fall. Since its upload, it has received 31 views. For similar materials see /class/226633/classic-h195-university-of-california-berkeley in Classical Studies at University of California - Berkeley.
Reviews for Honors Course in Classical Civilization
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/22/15
UC Berkeley 7 08273 Parallel and Distributed Theory Lecture 1 Professor Satish Rao January 20 2009 Lecturer Satish Rao Last revised Lecture 1 1 Outline 1 Load Balancing We will discuss the randomized load balancing strategies and their analysis We will teach the relevant probability for the analysis In particular count ing the union bound and Chernoff bounds I Parallel Algorithms Here we discuss basic techniques for parallelizing algorithms in a model that only is concerned with concurrency and not so much with locality a PRAM de nition Basic algorithms list ranking etc Reductions to list ranking In parallel algorithms using a black box algorithm that embodies the parallelism is quite useful List ranking is one widely useful such black box It is quite similar I believe to map reduce b De nition of NC P completeness Reductions This is classic complexity as applied to parallelism and gives conditional limits on the inherent parallelism available in certain computations c Advanced algorithms Distributed Coloring Matching For Distributed Color ing the task is to break symetry The techniques here will ironically also be useful for reducing communication costs as discussed later in the course The Matching algorithm is beatiful combinatorics and randomized analysis where the rather in uential Isolation Lemma77 was introduced to computer science to my knowledge 9quot Routing scheduling a Butter ies routing off line Benes Routing b Valiant routing in Butter ies Randomized strategy for avoiding bad tra ic pat terns Bounded queues To prove results for bounded queues is quite an inter esting theoretical endeavor which leads to a somewhat counter intuitive though interesting strategy for switching c Path selection in arbitrary networks Use linear programming randomized rounding for approximation There is a variant of the expert s algorithm here d Scheduling in networks Lovasz local lemma This starts with analysis of problems with scheduling the ow of packets in a networks includes a discussion of on line strategies and also includes the analysis of an approach that yields the optimal bounds 4 Distributed Algorithms Notes for Lecture 1 January 20 2009 2 a Byzantine Generals This shows how to reach agreement in a distributed system in the presense of a rather large fraction of bad agents b Algorithms for distributed models Eg e icient shortest route computations 5 Game Theory 99 Nash s Theorem Proof using Brower s xed pt theorem Beautiful stu U Congestion games Price of Anarchy More modern stuff discussing the cost of game theoretic behavior to the utility of a system A O v Arrows theorem There is no ranking scheme that acheives three natural prop erties How s that for a lesson A 1 v On line auctions More modern material discussing how to deal with on line auctions 6 Partitioning Algorithms a Spectral methods The approach along with intuition about the classical result called Cheeger s inequality which gives one provable bounds on the performance of these methods b Linear Programming based methods Approximation algorithm based on opti mization algorithms for graph partitioning 7 Object Location a Distributed Hash Tables Chord CANN b Locality Based Solutions for special graphs Tapestry c Graph Decomposition based solutions Approximate shortest path data struc tures 2 Load Balancing You have m jobs to be distributed into n bins How do you distribute them approximately equally Duh Evenly spread the jobs maximum load is mn within plus or minus 1 Ok let s examine algorithms that use a lot less information 1 Randomly select a bin 2 Randomly select two bins choose least loaded What is an upper bound on the maximum load for strategy 1 Strategy 2 We assume for today that m Isn t n the upper boundII Oh yes Not what I mean What bound is the max load almost always under Or with a very small probability the max load is greater than what Note probability for today is just counting Ok what is the probability of a ush in a ve card poker hand Notes for Lecture 1 January 20 2009 3 4 153 52 5 Oh yes now that we have we note that S meMk For independent events the probabilities multiply What is the probability of 4 heads in a row with an unbiased coin 1 24 So now that we are experts with probability Let s upper bound the probability that any bin has load greater than k We can just enumerate all the situations where any bin has load more than k and divide by 71 How do we count these situations Yuck OK let s just look at one bin What is the probability that its load is greater than k Zlt gt lt17 1W lt Zlt gt l 2 n n 7 l 2 n 39 22k 22k We can bound this by ekk This If we choose k gt 2elogn this is bounded by 1712 So now we know any one bin is pretty unlikely to have load greater than 2elogn But we wanted a bound for all bins Another concept in probability The probability of A or B is at most the probability of A plus the probability of B Or moi1 3 2 13414 This is called the union bound and we use it often in computer science So the proba bility that any bin has load greater than 2elogn is at most ln Question 1 Show that with high probability that the max load is at most Olog n log log What about strategy 2 What is the max load 7111 Oh shut up Ok any guesses Better by a constant factor Maybe as good as OW Hmmm Let s try to analyze this First we consider throwing only 718 balls into n bins We de ne a graph on n nodes where an edge is de ned for each ball according to its two choices of bins to look at That is if the rst ball examines bins 1 and 9 the graph contains an edge 19 What is the average degree of this graph 14 What is the maximum degree of this graph with high probability Certainly Olog What is the maximum size of any component Well any size k component must have k 7 1 internal edges What is the probability that there is some component of size gt k with k 7 1 edges The probability is less than 71 718 k 2k k k 7 1 n r This is less than 7162 Choosing k gt 2 log828 n ensures that this event happens with probability less than 1 So we have the following claim Notes for Lecture 1 January 20 2009 4 CLAIM 1 The maximum component size is Ologn with high probability Now7 we examine a more subtle concept or at least a generalization of what we did above What is the maximum internal degree of any subset S of nodes Let us consider k sized subsets The probability that the internal degree is greater than 6 is at most 33gt 32 5613 This can be bounded by 628714 as long as n is say bigger than some constant Thus7 we have the following claim CLAIM 2 With high probability the average internal degree of every subset is at most 6 We process the graph by iteratively removing all nodes and incident edges with re maining degree less than 12 How many iterations does this take Consider each connected component separately At least half the nodes have degree less than 12 by the claim above and thinking about a statement of the form that everyone can t be better than average Since the component is of size Olog n7 all the nodes and edges are removed in Olog log 71 iterations Cool