DESIGN AND ANALYSIS OF ALGORITHMS - Duke University

1 CPS 230 DESIGN AND ANALYSISOF ALGORITHMSFall 2008 Instructor:Herbert EdelsbrunnerTeaching Assistant:Zhiqiang GuCPS 230 Fall Semester of 2008 Table of Contents1 Introduction3 IDESIGNTECHNIQUES42 Divide-and-Conquer53 Prune-and-Search84 Dynamic Programming115 Greedy Algorithms14 First Homework Assignment17 IISEARCHING186 Binary Search Trees197 Red-Black Trees228 Amortized Analysis269 Splay Trees29 Second Homework Assignment33 IIIPRIORITIZING3410 Heaps and Heapsort3511 Fibonacci Heaps3812 Solving Recurrence Relations41 Third Homework Assignment44 IVGRAPHALGORITHMS4513 Graph Search4614 Shortest Paths5015 Minimum Spanning Trees5316 Union-Find56 Fourth Homework Assignment60 VTOPOLOGICALALGORITHMS6117 Geometric Graphs6218 Surfaces6519 Homology68 Fifth Homework Assignment72 VIGEOMETRICALGORITHMS7320 Plane-Sweep7421 Delaunay Triangulations7722 Alpha Shapes81 Sixth Homework Assignment84 VIINP-COMPLETENESS8523 Easy and Hard Problems8624NP-Complete Problems8925 Approximation Algorithms92 Seventh Homework

2 Assignment9521 meet twice a week, on Tuesdays andThursdays, from 1:15 to 2:30pm, in room D106 course material will be deliveredin the two weekly lectures. A written record of the lec-tures will be available on the web, usually a day after thelecture. The web also contains other information, such ashomework assignments, solutions, useful links, etc. Themain supporting text Structures and Network , book focuses on fundamental data structures andgraph ALGORITHMS , and additional topics covered in thecourse can be found in the lecture notes or other texts inalgorithms such asKLEINBERG Ed-ucation, will be a final exam (covering thematerial of the entire semester) and a midterm (at the be-ginning of October), You may want to freshen up yourmath skills before going into this course. The weightingof exams and homework used to determine your grades ishomework35%,midterm25%,final40%.

3 Have seven homeworks scheduledthroughout this semester, one per main topic covered inthe course. The solutions to each homework are due oneand a half weeks after the assignment. More precisely,they are due at the beginning of the third lecture after theassignment. The seventh homework may help you preparefor the final exam and solutions will not be 1. The solution to any one homework question mustfit on a single page (together with the statement of theproblem).Rule 2. The discussion of questions and solutions beforethe due date is not discouraged, but you must formu-late your own 3. The deadline for turning in solutions is 10 min-utes after the beginning of the lecture on the due main topics to be covered in this courseareI DESIGN Techniques;II Searching;III Prioritizing;IV Graph ALGORITHMS ;V Topological ALGORITHMS ;VI Geometric ALGORITHMS ;VII emphasis will be on algorithmdesignand on algo-rithmanalysis.

4 For the ANALYSIS , we frequently need ba-sic mathematical tools. Think of ANALYSIS as the measure-ment of the quality of your DESIGN . Just like you use yoursense of taste to check your cooking, you should get intothe habit of using algorithm ANALYSIS to justify DESIGN de-cisions when you write an algorithm or a computer pro-gram. This is a necessary step to reach the next level inmastering the art of programming. I encourage you to im-plement new ALGORITHMS and to compare the experimentalperformance of your program with the theoretical predic-tion gained through Programming5 Greedy AlgorithmsFirst Homework Assignment42 Divide-and-ConquerWe use quicksort as an example for an algorithm that fol-lows the divide-and-conquer paradigm. It has the repu-tation of being the fasted comparison-based sorting algo-rithm. Indeed it is very fast on the average but can be slowfor some input, unless precautions are follows the general paradigmof divide-and-conquer, which means itdividesthe un-sorted array into two, itrecurseson the two pieces, and itfinallycombinesthe two sorted pieces to obtain the sortedarray.

5 An interesting feature of quicksort is that the dividestep separates small from large items. As a consequence,combining the sorted pieces happens automatically with-out doing anything (int ,r)if < rthenm=SPLIT( ,r);QUICKSORT( ,m 1);QUICKSORT(m+ 1,r) assume the items are stored inA[ 1]. The arrayis sorted by calling QUICKSORT(0,n 1). performance of quicksort depends heav-ily on the performance of the split operation. The effect ofsplitting from toris: x=A[ ]is moved to its correct location atA[m]; no item inA[ ..m 1]is larger thanx; no item inA[m+ ]is smaller 1 illustrates the process with an example. The nineitems are split by moving a pointerifrom left to rightand another pointerjfrom right to left. The process stopswheniandjcross. To get splitting right is a bit delicate,in particular in special cases. Make sure the algorithm iscorrect for (i)xis smallest item, (ii)xis largest item, (iii)all items are the (int ,r)x=A[ ];i= ;j=r+ 1;repeat repeati++ untilx A[i];repeatj-- untilx A[j];ifi < jthenSWAP(i,j)endifuntili j;SWAP( ,j); 1: First,iandjstop at items 9 and 1, which are thenswapped.

6 Second,iandjcross and the pivot, 7, is swapped withitem cases (i) and (iii) are ok but case (ii) requires astopper atA[r+ 1]. This stopper must be an item at leastas large asx. Ifr < n 1this stopper is automaticallygiven. Forr=n 1, we create such a stopper by settingA[n] = + .Running actions taken by quicksort can beexpressed using a binary tree: each (internal) node repre-sents a call and displays the length of the subarray; seeFigure 2. The worst case occurs whenAis already 2: The total amount of time is proportional to the sumof lengths, which are the numbers of nodes in the correspondingsubtrees. In the displayed case this sum is this case the tree degenerates to a list without branch-ing. The sum of lengths can be described by the followingrecurrence relation:T(n) =n+T(n 1) =nXi=1i= n+ 12 .The running time in the worst case is therefore in O(n2).In the best case the tree is completely balanced and thesum of lengths is described by the recurrence relationT(n) =n+ 2 T n 12.

7 5If we assumen= 2k 1we can rewrite the relation asU(k) = (2k 1) + 2 U(k 1)= (2k 1) + 2(2k 1 1) +..+ 2k 1(2 1)=k 2k k 1Xi=02i= 2k k (2k 1)= (n+ 1) log2(n+ 1) running time in the best case is therefore inO(nlogn). of the drawbacks of quicksort, asdescribed until now, is that it is slow on rather commonalmost sorted sequences. The reason are pivots that tendto create unbalanced splittings. Such pivots tend to oc-cur in practice more often than one might expect. Hu-man and often also machine generated data is frequentlybiased towards certain distributions (in this case, permuta-tions), and it has been said that 80% of the time or more,sorting is done on either already sorted or almost sortedfiles. Such situations can often be helped by transferringthe algorithm s dependence on the input data to internallymade random choices. In this particular case, we use ran-domization to make the choice of the pivot independent ofthe input data.

8 Assume RANDOM( ,r)returns an integerp [ ,r]with uniform probability:Prob[RANDOM( ,r) =p] =1r + 1for each p r. In other words, eachp [ ,r]isequally likely. The following algorithm splits the arraywith a random pivot:intRSPLIT(int ,r)p=RANDOM( ,r); SWAP( ,p);returnSPLIT( ,r).We get arandomizedimplementation by substitutingRSPLITfor SPLIT. The behavior of this version of quick-sort depends onp, which is produced by a random assume that the items inA[ 1]are pairwise different. The pivot splitsAintoA[ 1], A[m], A[m+ 1].By assumption on functionRSPLIT, the probability foreachm [0,n 1]is1n. Therefore the average sumof array lengths split by QUICKSORTisT(n) =n+1n n 1Xm=0(T(m) +T(n m 1)).To simplify, we multiply withnand obtain a second rela-tion by substitutingn 1forn:n T(n) =n2+ 2 n 1Xi=0T(i),(1)(n 1) T(n 1) = (n 1)2+ 2 n 2Xi=0T(i).(2)Next we subtract (2) from (1), we divide byn(n+ 1), weuse repeated substitution to expressT(n)as a sum, andfinally split the sum in two:T(n)n+ 1=T(n 1)n+2n 1n(n+ 1)=T(n 2)n 1+2n 3(n 1)n+2n 1n(n+ 1)=nXi=12i 1i(i+ 1)= 2 nXi=11i+ 1 nXi=11i(i+ 1).

9 Bounding the second sum is solved directlyby transformation to a telescoping series:nXi=11i(i+ 1)=nXi=1 1i 1i+ 1 = 1 1n+ first sum is bounded from above by the integral of1xforxranging from 1 ton+ 1; see Figure 3. The sumof1i+1is the sum of areas of the shaded rectangles, andbecause all rectangles lie below the graph of1xwe get abound for the total rectangle area:nXi=11i+ 1<Zn+11dxx= ln(n+ 1).6xx1/4321 Figure 3: The areas of the rectangles are the terms in the sum,and the total rectangle area is bounded by the integral from 1throughn+ plug this bound back into the expression for the aver-age running time:T(n)<(n+ 1) nXi=12i+ 1<2 (n+ 1) ln(n+ 1)=2log2e (n+ 1) log2(n+ 1).In words, the running time of quicksort in the average caseis only a factor of about2/log2e= thanin the best case. This also implies that the worst case can-not happen very often, for else the average performancewould be drawback of quicksort is the recur-sion stack, which can reach a size of (n)entries.

10 Thiscan be improved by always first sorting the smaller sideand simultaneously removing the tail-recursion:voidQUICKSORT(int ,r)i= ;j=r;whilei < jdom=RSPLIT(i,j);ifm i < j mthenQUICKSORT(i,m 1);i=m+ 1elseQUICKSORT(m+ 1,j);j=m each recursive call to QUICKSORT, the length of the ar-ray is at most half the length of the array in the precedingcall. This implies that at any moment of time the stackcontains no more than1 + log2nentries. Note that with-out removal of the tail-recursion, the stack can reach (n)entries even if the smaller side is sorted incorporates two DESIGN tech-niques to efficiently sortnnumbers: divide-and-conquerfor reducing large to small problems and randomizationfor avoiding the sensitivity to worst-case inputs. The av-erage running time of quicksort is in O(nlogn)and theextra amount of memory it requires is in O(logn). Forthe deterministic version , the average is over alln!