Computer Science Algorithms, Divide and Conquer.

PROBLEM:

Fractals are geometric patterns that can arise from recursively drawing the same figure. They arise surprisingly often in nature. One example is the Barnsley fern that can be seen in the first image below. Another nice example can be found in the branches of a tree. Fractal patterns even appear inside our own body. The last image depicts a mold of the insides of our lungs.

It turns out fractal patterns are good for respiratory systems for both humans and plants due to the large surface area resulting from the fractal.

Draw the following simplified model of a tree fractal which uses the following rule: A line segment will have two smaller line segments appended to the top of it as in the following

(a) Image from Wikipedia (b) Image from Fractal Foundation (c) Image from Fractal Foundation b b d a The line segments (b,c),(6, d) are each 1/3 the length of (a,b), and are added perpendic- ularly with respect to the line segment (a,b). Note that in the next iteration, the rule would be applied to the line segment (b,c) and separately to the line segment (b,d). 1. Each point is given by two coordinates, for example a = (ar, ay). Give formulas for the points c, d given the points a and b. 38 Hint: Given a and b, the point c is obtained as b+ (1/3) M (6 - a) where M= = 6 :-) 2. Write a recursive algorithm to draw the tree curve on a screen with nx n pixels with initial points a = (n/2, 1) and b = (n/2, n/2). The bottom left point is (1,1). You algorithm may use the function DRAW-LINE(X,Y) which draws a line segment between points X and Y in constant time, no matter the length. 3. Analyze the running time of your algorithm. Write down the recursion tree, the depth of the tree, the cost per level, and analyze the total cost. 39 (a) Image from Wikipedia (b) Image from Fractal Foundation (c) Image from Fractal Foundation b b d a The line segments (b,c),(6, d) are each 1/3 the length of (a,b), and are added perpendic- ularly with respect to the line segment (a,b). Note that in the next iteration, the rule would be applied to the line segment (b,c) and separately to the line segment (b,d). 1. Each point is given by two coordinates, for example a = (ar, ay). Give formulas for the points c, d given the points a and b. 38 Hint: Given a and b, the point c is obtained as b+ (1/3) M (6 - a) where M= = 6 :-) 2. Write a recursive algorithm to draw the tree curve on a screen with nx n pixels with initial points a = (n/2, 1) and b = (n/2, n/2). The bottom left point is (1,1). You algorithm may use the function DRAW-LINE(X,Y) which draws a line segment between points X and Y in constant time, no matter the length. 3. Analyze the running time of your algorithm. Write down the recursion tree, the depth of the tree, the cost per level, and analyze the total cost. 39