Data Str Algrm Anl
Data Str Algrm Anl CSC 517
Popular in Course
Popular in ComputerScienence
This 36 page Class Notes was uploaded by Ms. Nathen O'Keefe on Thursday September 17, 2015. The Class Notes belongs to CSC 517 at University of Miami taught by Staff in Fall. Since its upload, it has received 24 views. For similar materials see /class/205767/csc-517-university-of-miami in ComputerScienence at University of Miami.
Reviews for Data Str Algrm Anl
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/17/15
Fourier transforms Burton Rosenberg 5 December 2003 Revised 5 December 2008 Overview This is an introduction to fast fourier transform for Algorithms CS 517 It is intended to be simple but not too simple It takes a mathematically sophisticated approach De nition of the Fourier transform Let aj lj 0 n 7 1 be 71 samples of a function Although these are generally real numbers they could be complex numbers The Fourier Transform associates to the set of samples a set of complex numbers ak l k 0 n 7 1 called the Fourier coe cients A function can be represented either by its samples or by its fourier coefficients As samples it is represented as a weighted sum of functions ej lj 0 n 7 1 called the sample basis 1 ifj k 6739 0 else The function is also represented as a weighted sum of functions Xk l k 0 n 7 1 called the fourier basis H my Emirn c0s27rjkn isin27rjkn The two representations give the same function Therefore the fourier transform is summarized by the equality n71 n71 171 2 ika Z 757 k0 j0 The scale factor 1n is needed because the functions Xk of the fourier basis are bigger then the ej in the sample basis The factor compensates for this Each side of the equality is a function We are representing a function without explicitly showing the free variable we are writing 1 instead of To evaluate the right hand side at a particular value k k O n 7 1 we apply the evaluation to each component function and sum n71 Z W j0 Hence the name sample basis the 57 glue together samples into a function where the weight a of 5739 is the value of the function sampled at j n71 Za alk ak j0 k The left hand side evaluation gives n71 n71 H n71 17 22ka 17 Zakemkn 1712ampkcos27rjknisin27rjkn k0 k0 k0 This could be read as the superposition of overtones of the fundamental complex sine wave cos kwj i sin kwj with w 27rn the overtones generated by k O n 7 1 and j being the point of sampling 2k is the complex weight of the k th overtone in the superposition Calculation of the Fourier transform A function can be represented as a sum of samples in the sample basis or a superposition of overtones in the fourier basis Each representation has its strengths Represented in the sampling basis is natural when a signal is sampled or reconstructed Represented in the fourier basis is more useful when the function is modi ed for instance when a sound signal is equalized or echo cancelled To use both representations it is necessary to preform the transformation and its inverse That is from the samples aj to calculate the coefficients 7 and from the coefficients 2k to calculate the samples aj Given the fourier coefficients the samples are easy to recover evaluate both sides of the equation at j n71 aj Z 343527 ij k0 This can be written as a polynomial n71 y 71ngtZakyk k0 and Li fw7 where w is the principal n th root of unity to 527W Think of f as a surface in complex space described by a n 7 1 degree polynomial It is entirely determined by its values on the n th roots of unity It is also entirely determined by its 71 coefficients The Fourier transform is the passage between these two descriptions We can think of constructing the surface from the coefficients and then recovering the aj or we can think of constraining that the surface pass through the Li at w7 and then see what are the resulting values of the coefficients It is not as easy however to derive the polynomial s coefficients from its values on the roots of unity than it is to simply evaluate a given polynomial at the roots of unity However the special structure of the roots of unity gives a strange duality 7 we can nearly interchange the role of the coefficients and the values of the polynomial at the roots of unity The polynomial n71 I 9y 2 WM j0 gives the values of 2k when evaluated at w k note carefully the negative sign in the exponent We prove this Since aj fw7 then 9w k ZHWW M ak because the sum of powers of a root of unity is zero unless the root of unity in question is one Lemma 1 Letw 527W be the principal n th root of unity Then n71 k Zwkj 71 quJ 1 I 0 else 70 Proof Denote the sum by S S wkS because we are only causing a renaming of the index 3 j 1 lfwk 7g 1 this implies S 0 Fast implementations the FFT We have established that the fourier transform of a sequence of n complex numbers is the evaluation of a polynomial at the n powers of the principal n th root of unity This can be accomplished simply in time nz by n evaluations where each evaluation is done in time n using Homer s rule n71 y Zajyj a0 ya1 ya2 y Maria yanil j0 the Fast Fourier transform performs all these evaluations in time nlog Write f as the sum of even and odd powers and factor a y from the odd power sum y a0 1292 ya1 1392 My yfoy where y yz Assuming 71 even f0 and f5 are both degree 712 7 1 degree polynomials to be evaluated at the 712 powers of the principal 712 th root of unity Since w2n2j wnww 41127 and tun27 74117 we can write the above as M rewindw 7W2 75ltw7gtw770ltwgt whereLD w2 and forj 07127 1 The recursive algorithm is now evident for the case 71 2 a pure power of two Given a0 MA take the FFT of a0 a2 anq and 11013 an1 by recursively evaluating these 71271 degree polynomials 71271 71271 My 2 any My Z a271yj j0 j0 at the powers of the 712 th root of unity LE 57W bi 10802727 Ci 100027 then combine 1 I 611739 bj w cg39 Ali4H bj 7 411707 where w 527W and j O 712 7 1 The combining step takes linear time so the recursion for run time is T71 2T712 071 so T71 07110g71 Although this recursive description is complete implementable and simple application to hardware will require a non recursive description This is an instance of a simple recursive algorithm whose non recursive equivalent is complicated due to the tricky reindexing of variables It is organized around the butterfly circuit which is a three input two output circuit Cmo m1 w y0y1 yo 0w17y1 900w1 There are 0971 layers of such butter y circuits one for each level of recursion and 712 circuits in each layer to preform the combining The tricky part is getting the right inputs to each circuit Example calculation The 71 th root of of unity is denoted wn 527W The notation of this section gives the powers of roots 0 unity as the zeroth the rst etc w0w1 w 1 so the second roots of unity wg are ordered as 1 71 and the fourth roots 4114 as 11 7171 The conjugate roots are 412 711 and J4 1717124 To walk through the fourier transform of the corresponding sample sets7 two and four7 we have7 30 a0a1 1 a0a1y A 7 y 1 a1 7 aoial yii 20 aoa2a1a3 241 31 a07a2a1i7a3i y i a0a1ya2y2a3y3 22 aoa27a1ia3 2471 33 a07a27a1ia3i y7i and the return trip7 amp0amp1a0a1a0a12a0 241 a0a1y amp0amp1a0a1a0a12a1 y1 amp0amp1amp2amp34a0 241 A A A 2 A 37 amp0amp2iamp1amp34a1 244 a0a1ya2y a3y 7 amp0amp1amp2amp34a2 y1 amp07amp27iamp1 7amp3 4a3 y i Graphs 0f overtones The powers of the roots of unity were described as overtones of a fundamental sinewave of frequency w 27r7i7 eszkn cos kwj isin kwj We illustrate this with graphs for the case n 6 A connection with the Nyquist sampling limit is also noted Draw the six roots of unity in the complex plane The principal sixth root is w 1 We can make a table giving the real part x coordinate of an that is7 the k th sample of the j th overtone Fit a cosine wave through these points For the zero th overtone7 we have a at line For the rst overtone we have one period of a cosine For the second overtone7 it s perhaps not so clear7 but we have samples of two periods of a cosine three samples per period For the third7 we have samples of three periods of a cosine This is easy7 we have exactly two samples per period7 at its to 1 and its bottom 71 After this7 the samples seem to repeat The fourth looks like the second7 the fth like the rst However7 if we were to also look at the imaginary part7 we would see that they are distinguishable For instance7 the rst overtone the rst sample is positive but for the fth it is negative However7 it is not possible to represent a wave with frequency faster than two samples per period After this7 the waves fold back7 matching waves with progressively slower frequencies This is aliasing which begins at two samples per period7 which is the Nyquist limit Introduction to Algorithms March 18 2004 Massachusetts Institute of Technology 6046J18410J Professors Erik Demaine and Sha Goldwasser Handout 14 Lecture Notes on Skip Lists Lecture 12 March 18 2004 Erik Demaine o Balanced tree structures we know at this point B trees redblack trees treaps 0 Could you implement them right now Probably with time but without looking up any details in a book 0 Skip lists are a simple randomized structure you ll never forget Starting from scratch 0 Initial goal just searches 7 ignore updates InsertDelete for now 0 Simplest data structure linked list 0 Sorted linked list 801 time o 2 sorted linked lists Each element can appear in 1 or both lists How to speed up search Idea Express and local subway lines Example 23 50 59 66 79 86 103 110 116 125 What is this sequence values are express stops others are normal stops Can quickly jump from express stop to next express stop or from any stop to next normal stop Represented as two linked lists one for express stops and one for all stops 6 la a Every element is in linked list 2 LL2 some elements also in linked list 1 LL1 Link equal elements between the two levels To search rst search in LLl until about to go too far then go down and search in LL2 2 Handout 14 Lecture Notes on Skip Lists Cost lenLL2 quot lenLL1 lenLL1 Minimized when n lenLL1 gt lenLL12 n gt lenLL1 gt search cost 2x Resulting 2level structure isq ni l isq ni H isq ni H isq ni H isq ni o 3 linked lists 3 o k linked lists k 7 o lgn linked lists lgn 1gquot n lgn 71mgquot lgn 2 Becomes like a binary tree 14 E 14 SVl OFI L751 110 ED50 m H Example Search for 72 i Level 1 14 too small 79 too big go down 14 Level 2 14 too small 50 too small 79 too big go down 50 Level 3 50 too small 66 too small 79 too big go down 66 Level 4 66 too small 72 spot on Handout 14 Lecture Notes on Skip Lists 3 Insert 0 New element should certainly be added to bottommost level Invariant Bottommost list contains all elements 0 Which other lists should it be added to Is this the entire balance issue all over again 0 Idea Flip a coin With what probability should it go to the next level To mimic a balanced binary tree we d like half of the elements to advance to the next tobottommost level So when you insert an element ip a fair coin If heads add element to next level up and ip another coin repeat 0 Thus on average 12 the elements go up 1 level 14 the elements go up 2 levels 18 the elements go up 3 levels Etc 0 Thus approximately even Example 0 Get out a real coin and try an example 0 You should put a special value 00 at the beginning of each list and always promote this special value to the highest level of promotion 0 This forces the leftmost element to be present in every list which is necessary for searching many coins are ipped Isn t this easy 0 The result is a skip list 0 It probably isn t as balanced as the ideal con gurations drawn above 0 It s clearly good on average 0 Claim it s really really good almost always Handout 14 Lecture Notes on Skip Lists Analysis Claim of With High Probability Theorem With high probability every search costs lg n in a skip list with n elements What do we need to do to prove this Calculate the probability and show that it s high We need to de ne the notion of with high probability this is a powerful technical notion used throughout randomized algorithms Informal de nition An event occurs with high probability if for any a Z 1 there is an appropriate choice of constants for which E occurs with probability at least 1 01713 In reality the constant hidden within lg n in the theorem statement actually depends on c Precise de nition A parameterized event ECt occurs with high probability if for any a Z 1 EC occurs with probability at least 1 fa71a where ca is a constant depending only on a The term 01 71 or more precisely fa71a is called the error probability The idea is that the error probability can be made very very very small by setting a to something big eg 100 Analysis Warmup Lemma With high probability skip list with n elements has 01g 71 levels In fact the number of levels is log 71 but we only need an upper bound Proof Prelement 1 is in more than clgn levels 12C gquot 171 Recall Boole s inequality union bound PrE1 U E2 U 39 39 39 U En S PrE1 PrEg 39 39 39 PrEn Applying this inequality Prany element is in more than clgn levels 3 n 171 171 1 Thus error probability is polynomially small and exponent a c 1 can be made arbitrarily large by appropriate choice of constant in level bound of 01g n Handout 14 Lecture Notes on Skip Lists 5 Analysis Proof of Theorem 0 Cool idea Analyze search backwardsifrom leaf to root Search starts at leaf element in bottommost level At each node visited If node wasn t promoted higher got TAILS here then we go came from left If node wasn t promoted higher got HEADS here then we go came from top Search stops at root oftree 0 Know height is 01g n with high probability say it s clgn 0 Thus the number of up moves is at most clg n with high probability 0 Thus search cost is at most the following quantity How many times do we need to ip a coin to get clg 71 heads 0 Intuitively lg 71 Analysis Coin Flipping 0 Claim Number of ips till i lgn heads is lg n with high probability 0 Again constant in lg n bound will depend on a 0 Proof of claim Say we make 10ilgn ips When are there at least 0 lg 71 heads 1 1 clgn 1 chgn Prexactly clgn heads H orders heads tails HHHTTT v5 HTHTHT chgn Prat most clgn heads overestimate tails on orders Michael s deathbed formula even on your deathbed if someone gives you a bino mial and says simplify you should know this Recall bounds on 6 Handout 14 Lecture Notes on Skip Lists Applying this formula to the previous equation 10ilgn 196 71g 71 2 elOclgn Mgquot 1 96quot clgn 1 chgn 1 clgn 7 0e 2 1 chgn Prat most 0 lg 71 heads I 2lg10eclgn 21glOe 9Clgn 2 algn 171Ct The point here is that as 10 gt 00 a 9 lg108 gt 00 independent of for all i 0 End of proof of claim and theorem Acknowledgments The mysterious Michael is Michael Bender at SUNY Stony Brook This lecture is based on discussions with him Skip Lists A Probabilistic Alternative to Balanced Trees Skip lists are a alata structure that can be useal in place of balanceal trees Skip lists use probabilistic balancing rather than strictly enforced balancing anal as a result the algorithms for insertion anal deletion in skip lists are much simpler anal significantly faster than equivalent algorithms for balanceal trees William Pugh Binary trees can be used for representing abstract data types such as dictionaries and ordered lists They work well when the elements are inserted in a random order Some sequences of operations such as inserting the elements in order produce degenerate data structures that give very poor performance If it were possible to randomly perrnute the list of items to be in serted trees would work well with high probability for any in put sequence In most cases queries must be answered on line so randomly perrnuting the input is impractical Balanced tree algorithms rearrange the tree as operations are performed to maintain certain balance conditions and assure good perfor mance Skip lists are a probabilistic alternative to balanced trees Skip lists are balanced by consulting a random number gen erator Although skip lists have bad worstcase performance no input sequence consistently produces the worstcase per formance much like quicksort when the pivot element is cho sen randomly It is very unlikely a skip list data structure will be signi cantly unbalanced eg for a dictionary ofmore than 250 elements the chance that a search will take more than 3 times the expected time is less than one in a million Skip lists have balance properties similar to that of search trees built by random insertions yet do not require insertions to be random Balancing a data structure probabilistically is easier than explicitly maintaining the balance For many applications skip lists are a more natural representation than trees also leading to simpler algorithms The simplicity of skip list algo rithms makes them easier to implement and provides signi cant constant factor speed improvements over balanced tree and selfadjusting tree algorithms Skip lists are also very space ef cient They can easily be con gured to require an average of l 13 pointers per element or even less and do not require balance or priority information to be stored with each node SIGP LISTS We might need to examine every node of the list when search ing a linkedlist Figure la If the list is stored in sorted order and every other node of the list also has a pointer to the node two ahead it in the list Figure lb we have to examine no more than rt2l 1 nodes where n is the length ofthe list Also giving every fourth node a pointer four ahead Figure le requires that no more tlranlrI4l 2 nodes be examined If every 2quot1h node has a pointer 2i nodes ahead Figure 1d the number of nodes that must be examined can be reduced to llog2 nl while only doubling the number of pointers This data structure could be used for fast searching but insertion and deletion would be impractical A node that has k forward pointers is called a level k node If every 2quot1h node has a pointer 2i nodes ahead then levels of nodes are distributed in a simple pattern 50 are level 1 25 are level 2 125 are level 3 and so on What would happen if the levels of nodes were chosen randomly but in the same roportions eg as in Figure 1e A node s iLh forward pointer instead of pointing 2quot 1 nodes ahead points to the next node of level i or higher Insertions or deletions would require only local modi cations the level of a node chosen randomly when the node is inserted need never change Some arrangements of levels would give poor execution times but we will see that such arrangements are rare Because these data structures are linked lists with extra pointers that skip over intermediate nodes I named them skip lists SIGP LIST ALGORITHJVIS This section gives algorithms to search for insert and delete elements in a dictionary or symbol table The Search opera tion returns the contents of the value associated with the de sired key or failure if the key is not present The Insert opera tion associates a speci ed key with a new value inserting the key if it had not already been present The Delete operation deletes the speci ed key It is easy to support additional oper ations such as nd the minimum key or nd the next key Each element is represented by a node the level of which is chosen randomly when the node is inserted without regard for the number of elements in the data structure A level i node has i forward pointers indexed l throughi We do not need to store the level of a node in the node Levels are capped at some appropriate constant MaxLevel The level of a list is the maximum level currently in the list or 1 if the list is empty The header of a list has forward pointers at levels one through MaxLevel The forward pointers of the header at levels higher than the current maximum level of the list point to NIL FIGURE 1 Linked lists with additional pointers Initialization An element NIL is allocated and given a key greater than any legal key All levels of all skip lists are terminated with NIL A new list is initialized so that the the level of the list is equal to l and all forward pointers of the list s header point to NIL Search Algorithm We search for an element by traversing forward pointers that do not overshoot the node containing the element being searched for Figure 2 When no more progress can be made at the current level of forward pointers the search moves down to the next level When we can make no more progress at level 1 we must be immediately in front of the node that contains the desired element if it is in the list Insertion and Deletion Algorithms To insert or delete a node we simply search and splice as shown in Figure 3 Figure 4 gives algorithms for insertion and deletion A vector update is maintained so that when the search is complete and we are ready to perform the splice updatei contains a pointer to the rightmost node of level i or higher that is to the left of the location of the inser tiondeletion If an insertion generates a node with a level greater than Searchlist searchKey x listaheader loop invariant xakey lt searehKey fori listalevel downto1 do while xafonNardi gtkey lt searchKey do x xaforward W xakey lt searehKey Sxaforward akey x xaforwardfl if xakey searchKey then return xavalue else return failure FIGURE 2 Skip list search algorithm the previous maximum level of the list we update the maxi mum level of the list and initialize the appropriate portions of the update vector A er each deletion we check if we have deleted the maximum element of the list and if so decrease the maximum level of the list Choosing a Random Level Initially we discussed a probability distribution where half of the nodes that have level i pointers also have level il point ers To get away from magic constants we say that a fraction p of the nodes with level i pointers also have level il point ers for our original discussion p 12 Levels are generated randomly by an algorithm equivalent to the one in Figure 5 Levels are generated without reference to the number of ele ments in the list At what level do we start a search De ning Ln In a skip list of 16 elements generated witle l2 we might happen to have 9 elements of level 1 3 elements of level 2 3 elements oflevel 3 and 1 element oflevel 14 this would be very unlikely but it could happen How should we handle this If we use the standard algorithm and start our search at level 14 we will do a lot ofuseless work Where should we start the search Our analysis suggests that ideally we would start a search at the level L where we expect lp nodes This happens whenL loglp n Since we will be referring frequently to this formula we will use Ln to denote loglp n There are a number of solutions to the problem of deciding how to handle the case where there is an element with an unusually large level in the list Don t worry be happy Simply start a search at the highest level present in the list As we will see in our analysis the probability that the maximum level in a list of n elements is signi cantly larger thanLn is very small Starting a search at the maximum level in the list does not add more than a small constant to the expected search time This is the approach used in the algorithms described in this paper Search path updatei gtforwardi list after insertion updated pointers in grey FIGURE 3 Pictorial description of steps involved in performing an insertion Use less than you are given Although an element may con tain room for 14 pointers we don t need to use all 14 We can choose to utilize only Ln levels There are a number of ways to implement this but they all complicate the algo rithms and do not noticeably improve performance so this approach is not recommended F ix the dice If we generate a random level that is more than one greater than the current maximum level in the list we simply use one plus the current maximum level in the list as the level of the new node In practice and intuitively this change seems to work well However it totally destroys our ability to analyze the resulting algorithms since the level of a node is no longer completely random Programmers should probably feel free to implement this purists should avoid it Determining MaxLevel Since we can safely cap levels at Ln we should choose MaxLevel LN where N is an upper bound on the number ofelements in a skip list lfp 12 usinthrxLevel 16 is appropriate for data structures containing up to 216 elements ANALYSIS OF SIGP LIST ALGORITHJVIS The time required to execute the Search Delete and Insert operations is dominated by the time required to search for the appropriate element For the Insert and Delete operations there is an additional cost proportional to the level of the node being inserted or deleted The time required to nd an element is proportional to the length of the search path which is de termined by the pattern in which elements with different levels appear as we traverse the list Probabilistic Philosophy The structure of a skip list is determined only by the number randomLevelO lvl l randomO that returns a random value in 01 while randomo lt p and M lt MaxLevel do lvl lvl 1 return v lnsertlist searchKey newValue local update l MaxLevel x listaheader fori listalevel downto1 do while xafonNardi gtkey lt searchKey do x xaforward xakey lt searchKey Sxaforward jakey updatei x x xaforwarclfl if xakey searchKey then xavalue newValue else lvl randomLevelO if lvl gt listalevel then fori listalevel l to lvl do updatei listaheader listalevel lvl x makeNoclelvl searchKey value fori 1 to level do xaforward updateiaforwardi updateiaforwardi x Deletelist searchKey local update l MaxLevel x listaheader fori listalevel downto1 do while xafonNardi gtkey lt searchKey do x xaforward updatei x x xaforwarclfl if xakey searchKey then fori 1 to listalevel do if updateiaforwardi x then break updateiaforwardi xaforward freex while listalevel gt 1 and istaheaderaforwardlistalevel NIL do listalevel listalevel l FIGURE 5 Algorithm to calculate a random level FIGURE 4 Skip List insertion and deletion algorithms elements in the skip list and the results of consulting the ran dom number generator The sequence of operations that pro duced the current skip list does not matter We assume an ad versarial user does not have access to the levels of nodes otherwise he could create situations with worstcase running times by deleting all nodes that were not level 1 The probabilities of poor running times for successive op erations on the same data structure are NOT independent two successive searches for the same element will both take ex actly the same time More will be said about this later Analysis of expected search cost We analyze the search path backwards travelling up and to the le Although the levels of nodes in the list are known and xed when the search is performed we act as if the level of a node is being determined only when it is observed while backtracking the search path At any particular point in the climb we are at a situation similar to situation a in Figure 6 7 we are at the im forward pointer of a node x and we have no knowledge about the levels of nodes to the le of x or about the level of x other than that the level of x must be at least 139 Assume the x is not the header the is equivalent to assuming the list extends in nitely to the le If the level of x is equal to i then we are in situation b lfthe level ofx is greater than i then we are in situation 0 The probability that we are in situation c is p Each time we are in situation c we climb up alevel Let Ck the expected cost ie length of a search path that climbs up k levels in an in nite list CO 0 Ck lip cost in situation b p cost in situation 0 By substituting and simplifying we get 000 117 1 t C10 tr 1 t CIHD Ck lp Ckil Ck kp Our assumption that the list is in nite is a pessimistic as sumption When we bump into the header in our backwards climb we simply climb up it without performing any le ward movements This gives us an upper bound of Ln7lp on the expected length of the path that climbs from level 1 to level Ln in a list of n elements We use this analysis go up to level Ln and use a different analysis technique for the rest of the journey The number of leftward movements remaining is bounded by the number of elements of level Ln or higher in the entire list which has an expected value of Up We also move upwards from level Ln to the maximum level in the list The probability that the maximum level of the list is a greater than kis equal to 14lipk39quot which is at most npk We can calculate the expected maximum level is at most Ln llip Putting our results together we nd Toml expected cost to climb out of a list of n elements SLnp 1117 which is Olog n Number of comparisons Our result is an analysis of the length ofthe search path The number of comparisons required is one plus the length of the search path a comparison is performed for each position in the search path the length of the search path is the num ber of hops between positions in the search path Probabilistic Analysis It is also possible to analyze the probability distribution of search costs The probabilistic analysis is somewhat more complicated see box From the probabilistic analysis we can calculate an upper bound on the probability that the actual cost of a search exceeds the expected cost by more than a speci ed ratio Some results of this analysis are shown in Figure 8 Choosing 11 Table 1 gives the relative times and space requirements for different values of p Decreasing p also increases the variabil situation 17 Still need to climb k levels from here Need to climb k levels from here Need to climb only k l levels from here situation c FIGURE 6 Possible situations in backwards traversal of the search path i ofrunning times If lp is a power of2 it will be easy to generate a random level from a stream of random bits it re quires an average of log2 lplip random bits to generate a random level Since some of the constant overheads are re lated to Ln rather than Lnp choosing p 14 rather than 12 slightly improves the constant factors of the speed of the algorithms as well I suggest that a value of 14 be used forp unless the variability of running times is a primary concern in which casep should be 12 Sequences of operations The expected total time for a sequence of operations is equal to the sum of the expected times of each of the operations in the sequence Thus the expected time for any sequence of m searches in a data structure that contains n elements is Om log n However the pattern of searches affects the probability distribution of the actual time to perform the entire sequence of operations If we search for the same item twice in the same data structure both searches will take exactly the same amount of time Thus the variance of the total time will be four times the variance ofa single search lfthe search times for two ele ments are independent the variance of the total time is equal to the sum ofthe variances ofthe individual searches Searchng for the same element over and over again maxi mizes the variance ALTERNATIVE DATA STRUCTURES Balancedtrees eg AVL trees Knu73 Wir76 and self adjusting trees ST85 canbe used for the same problems as skip lists All three techniques have performance bounds of the same order A choice among these schemes involves sev eral factors the dif culty of implementing the algorithms constant factors type of bound amortized probabilistic or worstcase and performance on a nonuniform distribution of queries Implementation dif culty For most applications implementers generally agree skip lists are signi cantly easier to implement than either balanced tree algorithms or selfadjusting tree algorithms Normalized search Avg of pointers p times ie normalized per no e LquotP 116 1110 12 1 2 1e 094 158 14 1 133 18 133 114 16 2 107 TABLE 1 7 Relative search speed and space requirements depending on the value of p Constant factors Constant factors can make a signi cant difference in the practical application of an algorithm This is particularly true for sublinear algorithms For example assume that algo rithmsA and B both require Olog n time to process a query but thatB is twice as fast asA in the time algorithmA takes to process a query on a data set of size n algorithm B can pro cess a query on a data set of size n2 There are two important but qualitatively different contri butions to the constant factors of an algori First the in herent complexity of the algorithm places a lower bound on an 39 39 S quotJ39 39i trees are arranged as searches are performed39 this imposes a signi cant overhead on any implementation of selfadjusting trees Skip list algorithms seem to have very low inherent constantfactor overheads the inner loop of the deletion algorithm for skip lists compiles to just six instructions on the 68020 Second if the algorithm is complex rograrnrners are de terred from implementing optimizations For example bal anced tree algorithms are normally described using recursive insert and delete procedures since that is the most simple and intuitive method of describing the algorithms A recursive in sert or delete procedure incurs a procedure call overhead By using nonrecursive insert and delete procedures some of this overhead can be eliminated However the complexity of non recursive algorithms for insertion and deletion in a balanced tree is intimidating and this complexity deters most program mers from eliminating recursion in these routines Skip list al miuu u re 10 4 Prob 0 p 14 n 10395 p12 pl2n4096 107 p l2n65536 10398 I 10399 30 Ratio of actual cost to expected cost FIGURE 8 This graph shows a plot of an upper bound on the probability of a search taking substantially longer than expected The vertical axis show the probability that the length of the search path for a search exceeds the average length by more than the ratio on the horizontal axis For example for p 12 and n 4096 the probability that the search path will be more than three times the expected length is less than one in 200 million This graph was calculated using our probabilistic upper bound recursive 273 trees Selfadjustin g trees topdown splaying bottomup splaying 0054 msec 105 015msec 30 049msec 96 39 Search Time Insertion Time Deletion Time Skip lists 0051 msec 10 0065 msec 10 0059 msec 10 nonrecursiveAIZ trees 0046 msec 091 010 msec 155 0085 msec 146 021msec 32 021 msec 365 016msec 25 051 msec 78 018msec 31 053msec 90 Table 2 Timings of implementations of different algorithms gorithms are already nonrecursive and they are simple enough that programmers are not deterred from performing optimizations Table 2 compares the performance of implementations of skip lists and four other techniques All implementations were optimized for ef ciency The AVL tree algorithms were writ ten by James Macropol of Contel and based on those in Wir76 The 273 tree algorithms are based on those presented in AHU83 Several other existing balanced tree packages were timed and found to be much slower than the results pre sented below The selfadjusting tree algorithms are based on those presented in ST85 The times in this table re ect the CPU time on a Sun360 to perform an operation in a data structure containing 215 elements with integer keys The val ues in parenthesis show the results relative to the skip list time The times for insertion and deletion do not include the time for memory management e g in C programs calls to malloc an ee Note that skip lists perform more comparisons than other methods the skip list algorithms presented here require an average of Lnp llip 1 comparisons For tests using real numbers as keys skip lists were slightly slower than the nonrecursive AVL tree algorithms and search in a skip list was slightly slower than search in a 273 tree insertion and deletion using the skip list algorithms was still faster than us ing the recursive 273 tree algorithms If comparisons are very expensive it is possible to change the algorithms so that we never compare the search key against the key of a node more than once during a search For p 12 this produces an upper bound on the expected number of comparisons of 72 32 log n This modi cation is discussed in Pug89b Type of performance bound These three classes of algorithm have different kinds of per formance bounds Balanced trees have worstcase time bounds selfadjusting trees have amortized time bounds and skip lists have probabilistic time bounds With selfadjusting trees an individual operation can take On time but the time bound always holds over a long sequence of operations For skip lists any operation or sequence of operations can take longer than expected although the probability of any opera tion taking signi cantly longer than expected is negligible In certain realtime applications we must be assured that an operation will complete within a certain time bound For such applications selfadjusting trees may be undesirable since they can take signi cantly longer on an individual oper ation than expected eg an individual search can take On time instead of Olog n time For realtime systems skip lists may be usable if an adequate safety margin is provided the chance that a search in a skip lists containing 1000 ele ments takes more than 5 times the expected time is about 1 in 1018 Nonuniform query distribution Selfadjusting trees have the property that they adjust to non uniform query distributions Since skip lists are faster than selfadjusting trees by a signi cant constant factor when a uniform query distribution is encountered selfadjusting tree are faster than skip lists only for highly skewed distributions We could attempt to devise selfadjusting skip lists However there seems little practical motivation to tamper with the sim plicity and fast performance of skip lists in an application where highly skewed distributions are expected either self adjusting trees or a skip list augmented by a cache may be preferable Pug90 ADDITIONAL WORK ON SIGP LISTS I have described a set of algorithms that allow multiple pro cessors to concurrently update a skip list in shared memory Pug89a This algorithms are much simpler than concurrent balanced tree algorithms They allow an unlimited number of readers and n busy writers in a skip list of n elements with very little lock contention Using skip lists it is easy to do most all the sorts of op erations you might wish to do with a balanced tree such as use search ngers merge skip lists and allow ranking operations eg determine the k element of a skip list Pug89b Tom Papadakis Ian Munro and Patricio Poblette PMP90 have done an exact analysis of the expected search time in a skip list The upper bound described in this paper is close to their exact bound39 the techniques they needed to use to derive an exact analysis are very complicated and sophisticated Their exact analysis shows that for p 12 and p 14 the upper bound given in this paper on the expected cost of a search is not more than 2 comparisons more than the exact expected cost I have adapted idea of probabilistic balancing to some other problems arising both in data structures and in incre mental computation PT88 We can generate the level of a node based on the result of applying a hash function to the element as opposed to using a random number generator This results in a scheme where for any set S there is a unique data structure that represents S and with high probability the data structure is approximately balanced If we combine this idea with an applicative ie persistent probabilistically bal anced data structure and a scheme such as hashedconsing A1178 which allows constanttime structural equality tests of applicative data structures we get a number of interesting properties such as constanttime equality tests for the repre sentations of sequences This scheme also has a number of applications for incremental computation Since skip lists are somewhat awkward to make applicative a probabilistically balanced tree scheme is used RELATED WORK James Discroll pointed out that R Spmgnoli suggested a method ofrandomly balancing search trees in 1981 Spr81 With Sprugnoli s approach the state of the data structure is not independent of the sequence of operations which built it This makes it much harder or impossible to formally analyze his algorithms Sprugnoli gives empirical evidence that his al gorithm has good expected performance but no theoretical re sults A randomized data structure for ordered sets is described in BLLSS86 However a search using that data structure re quires On12 expected time Cecilia Aragon and Rairnund Seidel describe a probabilis tically balanced search trees scheme AC89 The discuss how to adapt their data structure to nonuniform query distri butions SOURCE CODE AVAILABILITY Skip list source code libraries for both C and Pascal are avail able for anonymous rp from ftp cs umd edu C ON C LUSION S From a theoretical point of view there is no need for skip lists Balanced trees can do everything that can be done with skip lists and have good worstcase time bounds unlike skip lists However implementing balanced trees is an exacting task and as a result balanced tree algorithms are rarely imple mented except as part of a programming assignment in a data structures class Skip lists are a simple data structure that can be used in place of balanced trees for most applications Skip lists algo rithms are very easy to implement extend and modify Skip lists are about as fast as highly optimized balanced tree algo rithms and are substantially faster than casually implemented balanced tree algorithms ACKNOWLEDGEMENTS Thanks to the referees for their helpful comments Special thanks to all those people who supplied enthusiasm and en couragement during the years in which I struggled to get this work published especially Alan Demers Tim Teitelbaum and Doug cllroy This work was partially supported by an ATampT Bell Labs Fellowship and by NSF grant CCRi 8908900 REFEREN C ES AC89 Aragon Cecilia and Raimund Seidel Randomized Search Trees Proceedings of the 30th Ann IEEE Symp on Foundations of Computer Science pp 5407545 October 1989 AHU83 Aho A Hopcro J and Ullman J Data Structures and Algorithms AddisonWesley Publishing Company 1983 A1178 John Allen Anatomy ofLISP McGraw Hill Book Company NY 1978 BLLSS86 Knu73 PMP90 PT89 Pug89a Pug89b Pug90 Spr81 srss Wir76 Bentley J F T Leighton MF Lepley D Stanat and Steele A Randomized Data Structure For Ordered Sets MITLCS Technical Memo 297 May 1986 Knuth D Sorting and Searching The Art of Computer Programming Vol 3 AddisonWesley Publishing Company 1973 Papadakis Thomas Ian Munro and Patricio Poblette xact Analysis of Expected Search Cost in Skip Lists Tech Report 7777 Dept of Computer Science Univ of Waterloo January 1990 Pugh W and T Teitelbaum Incremental Computation via Function Caching Proc of the Sixteenth conference on the Principles of Programming Languages 1989 Pugh W Concurrent Maintenance of Skip Lists Tech Report TRCSZZZZ Dept of Computer Science University of Maryland College Park 1989 Pugh W Whateveryou might want to do using Balanced Trees you can do it faster and more simply using Skip Lists Tech Report CSrTR72286 Dept of Computer Science University of Maryland College Park July 1989 Pugh W Slow Optimally Balanced Search Strategies vs Cached Fast Uniforrnly Balanced Search Strategies to appear in Information Processing Letters Sprugnoli R Randomly Balanced Binary Trees Calcolo V17 1981 pp 99117 Sleator D and R Tarjan SelfAdjusting Binary Search Trees Journal ofthe ACM Vol 32 No 3 July 1985 pp 65 2666 Wirth N Algorithms Data Structures Programs PrenticeHall 1976 PROBABILISTIC ANALYSIS In addition to analyzing the expected performance of skip lists we can also analyze the probabilistic performance of skip lists This will allow us to calculate the probability that an operation takes longer than a speci ed time This analysis is based on the same ideas as our analysis of the expected cost so that analysis should be understood rst A random variable has a xed but unpredictable value and a predictable probability distribution and average If X is a random variable Prob X t denotes the probability thatX equals t and Prob X gt t denotes the probability thatX is greater than t For example ifX is the number obtained by throwing a unbiased die Prob X gt 3 12 It is o en preferable to nd simple upper bounds on values whose exact value is dif cult to calculate To discuss upper bounds on random variables we need to de ne a partial or dering and equality on the probability distributions of non negative random variables Definitions Pmb and Spmb LetX and Y be nonnegative independent random variables typically X and Y would denote the time to execute algorithms A X andAY We de ne X Sprob Yto be true if and only iffor any value t the probability thatX exceeds t is less than the probability that Y exceeds t More formally XPr0inffV t ProbXgt t Prob Ygtt and XSPminffV tProbXgt z SProb rm D For example the graph in Figure 7shows the probability distribution of three random variables X Y and Z Since the probability distribution curve forX is completely under the curves for Y and ZXSPr0b Y andXSPmb Z Since the probability curves for Y and Z intersect neither Y Sprob Z nor Z Sprob Y Since the expected value of a random variableX is simply the area under the curve ProbX gt t ifX Sprob Y then the average ofX is less than or equal to the average of Y We make use of two probability distributions De nition binomial distributions 7 Bt p Let t be a nonnegative integer and p be a probability The term Bt p denotes a random variable equal to the number of successes seen in a series of t independent random trials where the probability of a success in a trial is p The average and variance ofBtp are tp and tpl 7p respectively I Definition negative binomial distributionsi NBS Let s be a nonnegative integer and p be a probability The term NBs p denotes a random variable equal to the number of failures seen before the Sm success in a series of random independent trials where the probability of a success in a trial is p The average and variance of NBs p are slipp and slippz respectively I ProbXgtt ProbYgtt ProbZgtt Prob 0 I FIGURE 7 7 Plots of three probability distributions Probabilistic analysis of search cost The number of leftward movements we need to make before we move up a level in an in nite list has a negative binomial distribution it is the number of failures situations b s we see before we see the rst success situation e in a series of independent random trials where the probability of success is p Using the probabilistic notation introduced above Cost to climb one level in an in nite list prob 1 NB1gtP We can sum the costs of climbing each level to get the total cost to climb up to level Ln Cost to climb to level Ln in an in nite list prob Ln 1 NBLn LP Our assumption that the list is in nite is a pessimistic assumption Cost to climb to level Ln in a list of n elements Sprob Ln 1 NBLn LP Once we have climbed to level Ln the number of leftward movements is bounded by the number of elements of level Ln or greater in a list of n elements The number 0 elements of level Ln or greater in a list of n elements is a random variable ofthe form Bn lnp Let M be a random variable corresponding to the maximum level in a list of n elements The probability that the level ofa node is greater than kispk so Prob Mgt k 17 17715 lt npk Since npk p HW and Prob NBl lip l gt i we get an probabilistic upper bound ofM Spmb L61 NBl lip 1 Note that the average ofLn NB1 l 7p l isLn llip This gives a probabilistic upper bound on the cost once we have reached level Ln ofBn lnp Ln NBl l 7p l 7Ln Combining our results to get a probabilistic upper bound on the total length ofthe search path ie cost of the entire search total cost to climb out of a list of n elements Sprobalo 1NBQIquot 1gtPBquotgt 1MP NB1 1 p 1 The expected value of our upper bound is equal to Ln1Ln11r7r7 1P P1 P 1 LquotP 11 Pgt which is the same as our previously calculated upper bound on the expected cost of a search The variance of our upper bound is Ln11r72r72 1 1nPP P1 P2 lt 177Lnr7 P1 P2 2P 1Pz Figure 8 show a plot of an upper bound on the probability of an actual search taking substantially longer than average based on our probabilistic upper bound 1 0 Lecture 20 CSC517 Data Structures and Algorithms Spring 2005 Dr Christian A Duncan csc517 mai1csmiamiedu Announcements 0 Homework 8 Due Thursday April 14 R512C53C54R61R62R64 o Practicum Program 5 Due Thursday April 14 0 Warning These notes are just a rough outline The Graph Basics 0 Easy chapter so we will cover the basics but you must READ this chapter Most of the terminology should be familiar from either CSC220 or MTH309 0 Graphs represent relationships between objects vertices nodes objects edges arcs relationships 0 Graphs comes in several avors including 7 directed edges have a direction u 7gt v 7 undirected edges have no direction uv 7 mixed combination of both directed and undirected edges 7 Note sometimes directed edges are still written as ab so long as it is understood that ab does not imply ba 0 Some examples of Graphs 7 Communication network directed undirected or mixed Is the communication oneway or twoway 7 6degrees of Kevin Bacon Undirected Two actors a and b have an edge a b if they have appeared in the same movie 7 Flight patterns Directed Two airports a and b have an edge a 7gt b if there is a ight from a to b 7 Streets in a city map Mixed Directed and undirected edges are oneway and twoway streets respectively with vertices being intersections 0 Basic Terminology 7 A graph is often written as G V E where V is a set of vertices and E is a set of edges with endpoints from these vertices 7 The number of vertices in the graph is typically written as n 7 The number of edges is m 7 endpoints For an edge uv u and 1 represent the endpoints 7 origindestination if edge is directed they represent start and end endpoints 7 adjacentneighbors Two vertices are adjacent neighbors if there is an edge connecting them 7 incident An edge uv is incident to two vertices u and v 7 outgoingincoming edges In a directed graph we classify the directed edges incident to a vertex u as either outgoing leaving from u eg u 7gt v or incoming entering u eg 1 7gt u 7 degree The degree of a vertex u is the number of edges incident to u It is often written as du or In a directed graph we often separate the indegree and outdegree as and outv 7 degree The degree of a graph is the maximum degree among all of its vertices 7 A Simple Graph is a graph with no multi edges or selfloops That is there is at most one edge u v for any pair of vertices and there is no edge of the form u o Evev dv 2m The sum of the degrees of every vertex equals twice the number of edges Why 0 For directed graphs Evev Evev outv in That is the sum of the in degrees is the same as the outdegrees is the same as the number of edges Why 0 For simple undirected graphs m S nn 7 l2 o For simple directed graphs m S nn 7 1 o More advanced terminology 7 Path sequence of alternating vertices each edge incident to vertex before and after it Sometimes written as a sequence of vertices with the condition that neighboring vertices have a directed edge between them 7 Cycle A closed path starts and ends at the same place 7 Simple Path No duplicated vertex except the end in a cycle 7 Directed pathcycle Uses directed edges 7 Subgraph Vertices and edges are subsets of G V Often written as H E G 7 When subgraphs or multiple graphs are introduced often necessary to talk about the vertices and edges of the various graphs Eg VG VH EG and 7 Spanning subgraph Vertices are all the same as in G just the edges are a subset of E 7 Connected graph A graph G is connected if for any two vertices uv E VG there exists a path between them 7 Connected components A connected component of G is a maximal connected subgraph of G 7 Number of Connected Components often of interest when talking about graphs 7 Forest This is a graph without cycles for undirected graphsl Note it is called a forest because it is a collection of trees 7 Tree A connected forest that is a forest with only one connected component 7 Rooted tree versus Free tree In graph theory trees generally do not have speci ed roots and should then be considered free trees However in some cases like when it is a data structure on a tree there is a designated root In Chapter 6 and 7 our trees should generally be considered free trees 7 Spanning tree A spanning subgraph of G that is also a free tree 0 Read 611 on your own It discussed the Graph ADT Just the various methods that the book uses to interact with a graph 0 You should also read 62 which discusses some basic means of storing graphs The three main ways are 7 Edge list Store all edges in a single list UGHl 7 Adjacency list Each vertex lists its edges Usually stored as a linked list per vertex but could be other containers 7 Adjacency matrix In the simplest form it is an twodimensional array where an entry ij is 1 if there is an edge between vertex number i and vertex number j and 0 if there is not Note the numbering is just a means of listing the vertices in some order 7 Think about the size requirements of each structure with respect to the number of vertices n and edges m as well as the time taken to perform various operations from the ADT 7 Sparse versus dense graphs Although there is no exact delineation between the two conceptually a sparse graph is a graph with few edges eg relative to the number of vertices whereas a dense graph has many edges eg with respect to the number of vertices 3 Searching a Graph In many algorithms we will need to visit the edges of a graph in some order Similar to traversing the vertices and edges of a tree from before this more general process is called traversing a graph Two of the most common ways to traverse a graph are using depth rst search DFS and breadth rst search BFS Depth rst search is similar to the preorder traversals of regular trees Essentially one visits a node and then all of its unvisited neighbors DFSu mark u as visited for each edge e uv E E edges incident to u if v is not marked visited mark edge u v as forward discovery edge DFSv Note Edges not marked forward are called back edges The DFS as described is a recursive algorithm but it can also be done iteratively using a Stack In either case what is the running time of this algorithm with respect to n and m If we do an iterative algorithm and instead use a Queue we get the BFS algorithm In this case we visit all nodes in increasing distance from a start node u BFSs 7 3 mark 8 as visited while Q is not empty u 7 QAPOPO for each edge e u v E E if e is unexplored if v is not marked visited mark v as visited Qinsertv mark 6 as forward discovery edge else mark 6 as a cross edge Note this is just a rough sketch of the algorithm and differs in some details to the books One property of both of these is that the set of discovery edges forms a spanning tree DFS or BFS of the connected subgraph of G containing the start vertex 8 What are the running times of these algorithms Answer On m which should be quite easy to see These searches lead to some simple algorithms for determining certain graph properties Finding all of the connected components of a given graph can be done by running DFS on all unvisited vertices FindConnectedComponents G i lt7 0 for each node v E V if v is unvz sz ted DFSv marking these visited vertices as component i i lt7 i 1 Asymptotic Order Notation Burton Rosenberg September 10 2007 Introduction We carefully develop the notations which measure the asymptotic growth of functions The intuition is to group functions into function classes based on its growth shape The most used such grouping is 0f big oh of f where a function f serves as a model for an entire collection of functions the set 0f including all functions growing not faster than the function f De nition 1 BigOh Let f X a Y be a function g X gt Yl mmc gt 0 st Vm Z zocfm Z 9m Z 0 By abuse of notation g E 0f is written 9 0f rather than the more correct 9 E 0f The phrase 0f g77 has no meaning In general the sets X and Y are the sets of real numbers integers or naturals according to the situation Computer science is interested in functions which give only positive values or less drastically functions which eventually assume only positive values There is some long term simplicity in adopting this restriction although short term it requires additional de nitions and care De nition 2 Eventually Nonnegative Positive A function f X a Y is eventually non negative if there exists an m0 such that for all m 2 0 Z 0 The function is eventually positive if there exists an m0 such that for all m 2 0 gt 0 Theorem 1 If f is not eventually non negative is empty If f is eventually non negative then 0 0f and is therefore non empty Every element of is eventually non negative The function 0 X a Y is the zero function de ned as 0z 0 for all m In general any constant C can be viewed as a function of constant value C There is a related but stronger notion for the classi cation of functions LittleOh of f Whereas a function in 0f is bounded above by the function f a function in 0f is increasingly insigni cant to the function f De nition 3 LittleOh Let f X a Y be a function 0f gXgtYchgt03m0gt0 st VmZmo gtgx 20 Theorem 2 ff is not eventually positive 0f is empty ff is eventually positive then 0 0f and 0f is therefore non empty Every element of 0f is eventually non negative Note that while 00 is not empty it contains all functions that are eventually zero 00 is empty So the converse of the following theorem is not true Theorem 3 LittleOh is Stronger than BigOh Ifg 0f then 9 Of Proving a function in Of requires demonstrating mo and c satisfying the de nition For some demonstrations the function is so strongly a member of Of that the subtleties of Big Oh are a waste of time The class of functions 0f littleoh of f has stronger demands hence sim pler demonstrations A function in 0f is also in Of so one use of Little Oh is to provide demonstrations for Big Oh Theorem 4 Analytic De nition of LittleOh Let f X a Y be eventually positive Let g X gt Y be eventually non negative Then 9 0f if and only if 11330 gowns a 0 Example 1 logz Use L Hopital s rule to show log zz a 0 This gives logz 0a and therefore logz In the same way it can be shown that n logn On15 for any real 6 gt 0 Example 2 For 3 gt k gt 0 zk 0m7 hence zk 0z7 Order Properties of the Notation The order notation arranges functions from smaller to larger reminiscent ofthe ordering of numbers from smaller to larger In this analogy Big Oh is non strict inequality 9 Of can be interpreted as g g 1 Likewise LittleOh is strict inequality 9 0f is similar to g lt 1 Given three functions fg and h we expect that ordering is transitive if h g g and g g 1 then h g f The is indeed true for order notation Theorem 5 Transitivity Ifh 09 andg Of then It Of If h 09 and g 0f then h 0f Big Oh and Little Oh express non strict and strict less than Other notations express non strict and strict greater than De nition 4 BigOmega Let f X a Y be a function QfgXgtYl30cgt0 st VmZzo gmZCfZO Theorem 6 If f is not euentually non negatiue is empty Euery function in is euen tually non negatiue 90 is the collection of all euentually non negatiue functions De nition 5 LittleOmega Let f X a Y be a function wfgXgtYchgt03m0gt0 st VmZmo gxgtcfm20 Theorem 7 If f is not euentually non negatiue is empty Euery function in is euentu ally positiue w0 is the collection of all euentually positiue functions We claim that these de nitions are the appropriate anti symmetric variants of Big and LittleOh Theorem 8 antisymmetry g 0f exactly when f g 0f exactly when f Mg Given the anti symmetry theorems concerning Big and Little Oh can be quickly reestablished for Big and Little Omega Corollary 9 Strength Ifg wf then 9 Corollary 10 Transitivity Ifh 99 andg 9f then It Ifh wg andg wf then h The following theorem illustrates the strictness versus non strictness of the various notations Theorem 11 Re exivity Let f be eventually non negative Then f 0f and f Hence the intersection is non empty In contrast the intersection of 0f and is always empty In particular neither 0f nor contains The intersection of 0f and 9f produce the class f the class of functions sharing the asymptotic growth of f Just as x g y and y g z implies z y g 0f and f 09 implies g f since f 09 can be transformed to g 9f so 9 is in the intersection De nition 6 Theta Let f X a Y be a function gXgtYl3xmc1c2 gt0 st VmZmo c1fx 29x Zc2fm 20 Theorem 12 g if and only ifg and f 09 The set is the intersection of 0m and no The sets de ned by Theta form equivalence classes Equivalence classes are de ned by a relation which is re exive symmetric and transitive Corollary 13 Equivalence Properties The relation 9 enjoys the following properties 1 quotf 439 Iffi39s quot u u Wat f f 2 Symmetry Ifg then f g 3 Transitive If h g and g then h We close this section with a warning concerning the ordering of functions Functions have greater complexity than numbers The ordering of numbers by size leaves little room for variety Given two numbers one is the smaller or if not the numbers are the same Consider these functions 0 if z is even f5 1 else 0 if as is odd fow T 1 else Neither of these functions is Big Oh the other By order of growth these two functions are incom mensurable But see an exercise in the class text for variant de nitions which avoid this Example 3 Show n1 0a andm Oamb fora gt 0 Conclude that afmbf 9agmbg for afag gt 0 Often the simplest function of a 9 class lends its name to the class These functions would be described as The Order of an Approximation The order notation can be used to notate a function whose shape is not known exactly but to an approximation suitable for the purpose The Harmonic series is the sum of the reciprocals of rst n integers Since logz is the integral of 1z it is not surprising that the Harmonic series should approximate the log V L H Zli lnn 01 i1 This equation tells us that the approximation is perfect with the addition of an unknown 01 error function That is Hn lnn en for some en 01 In general the presence of the order notation inside an expression on the right hand side of an equality indicates that some speci c function makes the equality true however the most we know or care to know about that function is that it is a member of a certain order class E iciency of Algorithms The efficiency of an algorithm is given by the order of growth in run time with respect to input size For instance numerous simple sorting routines essentially compare all elements pairwise in the course of sorting For n elements this makes 0n2 comparisons and this places a bound on runtime Suppose two algorithms are composed The output of algorithm A with run time fA is the input to algorithm B with run time f3 What is the efficiency of the combined algorithm Assuming the rst algorithm leaves the size unchanged it is fA fBz This theorem allows for simpli cation Theorem 14 Let 9192 and a1a2 be non negatiue constants Then algl 0292 Suppose we would like to calculate the mode of z numbers that is the value which occurs most often This can be accomplished by sorting the numbers and then sweeping through the sorted numbers keeping track of the longest run of consecutive equal values If the sorting is done in time fAm 0z2 and the sweep is done in time fBm 0z the entire algorithm runs in time fAW 15390 0amp5 ln this algorithm sorting is the bottle neck Improve the sort to 0zlogz eg using mergesort and immediately the entire algorithm improves to 0zlog The moral of the story when an algorithm can be broken down into a sequence of sub algorithms the sub algorithm with largest run time rules the runtime of the combined algorithm It should be intuitive that dil admd ad11z a0 0md for ad gt 0 It is actually a bit of a mess to prove due to the fact that for i lt at some or all of the a might be negative Theorem 15 If f and g 09 then fg 0fg Given this theorem a fairly neat way about a proof is the factorization dil I 90 admd 1 2aiadlidgt i0 followed by showing 1 2aiadzi d 01 A little more work gives the matching 9 bound Corollary 16 Let x ow with ad gt 0 Then f GM Example 4 A quick summary of our results so far 0lt1ltlogzltmltzlogzltz15ltz2ltz3lt An algorithm running with any of these run times is consider feasible It runs in polynomial time that is 0mk for some k Algorithms taking strictly more time than polynomial are consider infeasible Theorem 17 mk 0am for any k and any a gt 1 Example 5 Our hierarchy continues z2ltm3ltlt2ltewltltzltz1210 1lt2116lt2 lt An algorithm taking more than polynomial time such as an exponential time algorithm running in 02m is considered infeasible The reason for this is that small changes in input size increase computation time greatly In practice any useful algorithm will be applied to increasingly complex problems Due to the growth rate computation power will not keep up with the demands of problem size For all practical purposes then the problem in not solvable by this algorithm Exponential time algorithms sometimes invoke the following very simple strategy try all possible combinations of outputs and pick the one that s correct77 Here is an exponential time algorithm for sorting a pack of cards There are 52 cards They can be rearranged into 52 orders Try all orderings one by one until the correct one appears To give the reader an idea of the inefficiency of this method it wouldn t be much less efficient to sort cards by repeatedly shuf ing them each time looking to see if the cards just happened to fall in order This should give an intuition to the practical infeasibility of exponential time algorithms Exercises H Give proofs for all theorems and corollaries given in these notes to Give proofs for the examples given in these notes 03 Prove or disprove if 91 92 91 and a1 a2 are positive constants then algl aggg F Prove or disprove if f 91 and g 99 then f g Mfg U Prove or disprove if f 0f and g 09 then f and g are both 0f g a Give the analogous analytic de nition for 9 which agrees with the transpose symmetry of o and 2 Warning the limit requires that the denominator be eventually positive Lectures 16 17 CSC517 Data Structures and Algorithms Spring 2005 Dr Christian A Duncan csc517 mai1csmiamiedu 1 Announcements 0 Homework 6 Due Today 0 Homework 7 Due Thursday April 7 R51 R 52 RSA R 511 C51 C52 Extra Credit 0510 0 Warning These notes like many others have not been proofread whatsoeverlll 2 Lecture 16 In Lecture 16 we also covered the remainder of the UnionFind algorithm and analysis dealing with log n performance and covered the Ackermann7s function a bit Unfortunately I do not have notes typed up for this part of the lecture 3 Optimization Problems and the Greedy Approach to Solving Them Optimization problems 0 A set of constraints rules con guration space 0 An objective function goal 0 Find a solution that does not violate the constraints rules and that either maximizes or minimizes the given object function goal These type of problems appear everywhere In fact there is an entire branch of Mathematics Operations Research dedicated to solving these problems The Knapsack problem is one simple but fundamental optimization problem 0 Imagine backpacking in the Alps and discovering a cave lled with valuable jewels Obviously you d like to take all of it with you but your knapsack has a weight limit W so you have to be picky on which ones you choose Some jewels are worth more than others In the fractional knapsack problem you also have a pickax so you can break the jewels into smaller pieces and take only a portion of it In the 01 knapsack problem you do not or breaking a jewel up destroys its value completely What is the optimal strategy and how long does it take to nd the set of jewel fragments to take We consider the fractional knapsack rst using a greedy approach 0 Greedy strategies mean just that when optimizing you try to be as greedy as possible in your next selection In this case we pick the most valuable jewel rst place it in the knapsack or if it won t all t we place as much as possible and then repeat with the remaining jewels o Suprisingly this simple strategy is optimal assuming we are talking about valuable correctly One jewel may be worth 100 but weigh 10 kilograms while another may be worth 90 but weigh only 1 kilogram Clearly we would want the lighter one rst That is we value the jewels based on their bene t to weight ratio Let us formalize this problem more 0 Given a set of n items of weight wi and bene t bi and a knapsack with maximum weight limit W we wish to determine the weight of each item I that we place in the knapsack Maximize ELI Use vi biwi Subject to ngigw forlgign 21 Ii 3 W 0 Solution Place all the item into a priority queue with priority equal to its value vi Let W be the amount of weight remaining in knapsack Repeat the following Extract the one with highest priority call it i If wi S W set I wi take all of it otherwise set I W take as much as you can t Repeat until W 0 or there are no items left 0 Time Creating the priority queue as a heap takes 0n time We then do 0n extractions each taking Olog n time So the total time taken is Onlog Correctness See the book for details on the proof of why the greedy strategy works here but essentially it lies on the fact that if there are two items 239 and j such that i is worth more than j vi gt vj and such that not all of i was taken but some ofj was taken lt wi and zj gt 0 then we could increase our pro t and keep the same weight by just taking a little more of z and a little less of zj Thus the most valuable items are fully chosen before lesser valuable items This problem can actually be solved in On time using a modi cation of binary search and the quick select algorithm But you ll have to think about that one as an exercise Task Scheduling 0 Given n tasks with speci c start 3139 and nish times assign each task to a speci c machine such that no machine performs two tasks at the same time and one uses the fewest number of machines possible 0 Solution Greedy again Arrange each task by start time and start with one machine Take the next start time s in the task list if there is a machine available that is not busy assign the task to that machine otherwise add a new machine and assign the task to that machine In either case the assigned machine is busy until 0 Time taken Can be implemented in On log n time but that is a homework problem 0 Correctness See the book but the idea centers around a simple argument If k machines were used look at the time t the kt machine was created At that point there were k 7 1 items that had nish times greater than t or else there would have been a machine free and there was one task with a start time equal to t There is no way to schedule these k tasks in fewer than k machines 0 This argument is often called the pigezmhole problem Is it possible to place n 1 pigeons in n holes without two pigeons being in the same hole 4 The Master Theorem tool for solving recurrences Many problems in computer science are solved by breaking the problem into smaller pieces solving the smaller pieces and then combining them to get the nal solution This approach known as divideand conquer was recently discussed in sorting both mergesort and quicksort used this approach In general this approach yields a recurrence relation on the problem that is then used to determine the running time The recurrence relation usually takes a form like 5 if n lt d T01 Tn1 T012 Tnk fn if n 2 d We have already discussed several general ways to solve these problems which are reviewed in Chapter 0 Substitution method Expand the recurrence repeatedly o Recursion tree Create a tree and analyze time per level and number of levels 0 Induction Start with an educated guess to the running time and prove it is correct with induction For this one pay attention to Example 54 which shows an example where a very reasonable and close guess fails One very very useful tool deals with speci c types of recurrences of the following form Tlt 7 c if n lt d n aTnb fn if n 2 d where d 2 l a gt 0 c gt 0 b gt 1 and gt 0 for n 2 d The solution to this recurrence has a nice theorem associated with it called the Master Theorem that analyzes the function with respect to the function nlogb a 1 If there is a small constant e gt 0 such that is Onl gba 5 then Tn is nbgba 2 If there is a constant k 2 0 such that is nl gba logk n then Tn is nl gba logl61 3 If there are small constants e gt 0 and 6 lt 1 such that is 9nl gba5 and afnb S for n 2 d then Tn is The book has several examples page 269 We shall look at some of these in class In particular look at Example 511 which uses a substitution technique to solve the problem 41 Integer Multiplication This problem deals with doing mathematical operations on big integers That is the numbers are represented with n bits rather than a constant number Here I J and I 7 J take 0n time but basic multiplication strategies makes I J take 0n2 time Using divideand conquer we can surprisingly do better 0 Divide I and J into higher and lowerorder bits Ih Il Jh and Jl o I Ih2n2 I J Jh2n2 J1 o Multiplying a number by 2k takes 0k steps shift the bits 0 I J Ih2n2 1 Jh2n2 J IthZ Ith2n2 IhJ nQ IlJl o A multiplication of n bits is divided into 4 submultiplications of size n2 bits followed by 3 additions taking at most cn steps 0 What is the recurrence we get Tn 4Tn2 an 0 Applying the Master theorem we see it is n2 That didn t help 0 Need to reduce the number of recursive calls somehowl 0 1h 7 Il J 7 Jh 1th 7 1sz 7 Ith Nb 0 Using this we see I J Duh h i ll Jh Jl Ith IlJllTLQ IlJl o This version only has 3 products we need to compute Because Ith and 1 appear twice we can compute just once and use it twice in the additions 0 So the recurrence now becomes Tn 3Tn2 on o The Master theorem shows that this is nlogz 3 or Onl585 42 Matrix Multiplication Here you should read the book for the details but in general 0 Given two n X n matrices X and Y 0 Want to determine Z XY which the traditional way takes ng time 0 Using a breakdown similar to integer multiplication we get a recurrence of Tn 8Tn2 Im2 which is ng by the Master theorem 0 Strassenls Algorithm reorganizes the steps so that the recurrence is Tn 7Tn2 Im2 which is nbg or 0n2808 time 5 Dynamic Programming memoizing things helps Unfortunately I did not have time to write notes for this section but hopefully we shall have time to cover it in class Skiplists Burton Rosenberg November 15 2004 Skiplists are a randomized data structure supporting logarithmic time searching It is a linked list of nodes each node included in layers zero up to k where k is chosen randomly with a geometric distribution when the node is inserted In practice a coin is ipped and the node is inserted into the next layer up for as long as the coin ip yields heads With a coin of bias p this means that about a fraction p of nodes are ltered from layer k and linked together in layer k 1 The unchosen nodes are skipped over Typically p is chosen to be a constant and the result is log 71 layers for a skiplist of n nodes both in expectation and with high probability This is proven below Given that a skiplist as k layers the search time is calculated by considering the backwards process of climbing out77 of a skiplist from the found node Each backward step is either to a node on the same level or upwards a level with a Bernoulli distribution of probability p Hence the number of nodes is distributed as the number of trials before the k th success This is distributed according to the negative binomial distribution giving a search time of log Suppose X are iid geometric random variables and Y maxX1 Xn By independence Pm M71302 k i177nPX1 W 7 171W EYn ZPYngt k2171iqkn39 kZO kZO Because 1 7 z is convex upwards and tangent to the line 1 7 mm at zero 1 7 z 2 1 7 7m If we set logn 10g1q7 then qm 171 and 171iqm1j 11iqjn 171761739 61 With high probability Yn will be am or less for all 04 gt 1 130 gt am1717 qma71mn S qa71m 1na71 We can therefore break up the sum7 m z i i Wz WZ i 7W W k0 kZO 73921 m 21 Zq k0 21 m1m
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'