Applied Computer Science
Format: PDF / Kindle (mobi) / ePub
Illuminating complex data is not easy. In particular, when conclusions inﬂuence a political decision we must guard against what Orwell observed: “The great enemy of clear language is insincerity.” The same holds for graphics where a picture’s worth a thousand words either sincerely spoken or not. Of course Minard did not use a computer in the nineteenth century but our focus will be on images that are either impossible to produce without a computer or at least very much easier with one. S.
Doubling of iteration count sharpens features. Parallel Load Balancing In the case of interactive zooming we must take special care not to draw the image too inefﬁciently. For instance, if the putpixel command is accidentally placed inside our inner-most loop, and if the itemconﬁgure command is placed inside any loop, then runtime may increase by as much as a factor of 1000 (!). Also, if we zoom in on a small enough region then we will need to increase the maximum iteration count so that the
O O O O X X X X X X O O O O X X X O X X X X - X X O X O O O O X X X X X X O X X X X X O - O O O O O O O X O X O O O O O X X O - X X X O O O O O O O O O O O X X X - O O O O O O O X X X X O O O O O O X O X O O O O X O O O X X O X O O O O O O O X - X X X O O X X O O X X X X X O O X X O - X O O O X O O O X O X O X X O O O O X X X O O O O X X X X X X X X X O X X X O X X O O O O X O X X X X X X X O X X X X - O O O X X X O X X X X O O - O O O O O O O O X O O O O O O O X O O O O O O O O X X
1, a tail recursion that translates into code using just a loop and a list. 5.2 Runtime Analysis 127 Code Listing 5.10: The “classic” recursive implementation. # def F(n): if n==1 or n==2: return 1 else: return F(n-1)+F(n-2) # two recursive calls # Code Listing 5.11: Tail recursion and a form of “inchworming.” # def F(n,k,next,prev): if n==k: return prev else: return F(n,k+1,next+prev,next) # fibn=F(n,1,1,1) # base case specified when called # Runtime Comparison 14 Runtime, seconds 12
search, only the marked pixels are checked and all other pixels are classiﬁed automatically. Right: quadtree, a similar idea in 2-D where only the corners of each box are checked. In general our goal is to localize calculations for larger sizes along the edge of the circle, where they matter. 12 In-Out Checks, percentage binary search quadtree 10 8 6 4 2 0 500 1000 1500 2000 2500 3000 Size of Image File, pixels per side 3500 Fig. 2.5: Divide-and-conquer savings. For the previous size m =