Introduction to Algorithms: 6.006Massachusetts Institute of Technology September 15, 2011Professors Erik Demaine and Srini Devadas Problem Set 2Problem Set 2Both theory and programming questions are due Tuesday, September 27 at 11:59PM.Please download the .zip archive for this problem set, and refer to the README.txt file forinstructions on preparing your solutions.Remember, your goal is to communicate. Full credit will be given only to a correct solutionwhich is described clearly. Convoluted and obtuse descriptions might receive low marks, evenwhen they are correct. Also, aim for concise solutions, as it will save you time spent on write-ups,and also help you conceptualize the key idea of the problem.We will provide the solutions to the problem set 10 hours after the problem set is due, whichyou will use to find any errors in the proof that you submitted. You will need to submit a critique ofyour solutions by Thursday, September 29th, 11:59PM. Your grade will be based on both yoursolutions and your critique of the solutions.Problem 2-1. [40 points] Fractal RenderingYou landed a consulting gig with Gopple, who is about to introduce a new line of mobile phoneswith Retina HD displays, which are based on unicorn e-ink and thus have infinite resolution. Thehigh-level executives heard that fractals have infinite levels of detail, and decreed that the newphones’ background will be the Koch snowflake (Figure 1).Figure 1: The Koch snowflake fractal, rendered at Level of Detail (LoD) 0 through 5.Unfortunately, the phone’s processor (CPU) and the graphics chip (GPU) powering the display donot have infinite processing power, so the Koch fractal cannot be rendered in infinite detail. Goppleengineers will stop the recursion at a fixed depth n in order to cap the processing requirement. Forexample, at n = 0, the fractal is just a triangle. Because higher depths result in more detaileddrawing, this depth is usually called the Level of Detail (LoD).The Koch snowflake at LoD n can be drawn using an algorithm following the sketch below:2 Problem Set 2SNOWFLAKE(n)1 e1, e2, e3= edges of an equilateral triangle with side length 12 SNOWFLAKE-EDGE(e1, n)3 SNOWFLAKE-EDGE(e2, n)4 SNOWFLAKE-EDGE(e3, n)SNOWFLAKE-EDGE(edge, n)1 if n==02 edge is an edge on the snowflake3 else4 e1, e2, e3= split edge in 3 equal parts5 SNOWFLAKE-EDGE(e1, n − 1)6 f2, g2= edges of an equilateral triangle whose 3rd edge is e2, pointing outside the snowflake7 ∆(f2, g2, e2) is a triangle on the snowflake’s surface8 SNOWFLAKE-EDGE(f2, n − 1)9 SNOWFLAKE-EDGE(g2, n − 1)10 SNOWFLAKE-EDGE(e3, n − 1)The sketch above should be sufficient for solving this problem. If you are curious about the missingdetails, you may download and unpack the problem set’s .zip archive, and read the CoffeeScriptimplementation in fractal/src/fractal.coffee.In this problem, you will explore the computational requirements of four different methods forrendering the fractal, as a function of the LoD n. For the purpose of the analysis, consider therecursive calls to SNOWFLAKE-EDGE; do not count the main call to SNOWFLAKE as part of therecursion tree. (You can think of it as a super-root node at a special level -1, but it behaves differ-ently from all other levels, so we do not include it in the tree.) Thus, the recursion tree is actuallya forest of trees, though we still refer to the entire forest as the “recursion tree”. The root calls toSNOWFLAKE-EDGE are all at level 0.Gopple’s engineers have prepared a prototype of the Koch fractal drawing software, which you canuse to gain a better understanding of the problem. To use the prototype, download and unpack theproblem set’s .zip archive, and use Google Chrome to open fractal/bin/fractal.html.First, in 3D hardware-accelerated rendering (e.g., iPhone), surfaces are broken down into triangles(Figure 2). The CPU compiles a list of coordinates for the triangles’ vertices, and the GPU isresponsible for producing the final image. So, from the CPU’s perspective, rendering a trianglecosts the same, no matter what its surface area is, and the time for rendering the snowflake fractalis proportional to the number of triangles in its decomposition.(a) [1 point] What is the height of the recursion tree for rendering a snowflake of LoD n?1. log n2. nProblem Set 2 3Figure 2: Koch snowflake drawn with triangles.3. 3 n4. 4 n(b) [2 points] How many nodes are there in the recursion tree at level i, for 0 ≤ i ≤ n?1. 3i2. 4i3. 4i+14. 3 · 4i(c) [1 point] What is the asymptotic rendering time (triangle count) for a node in therecursion tree at level i, for 0 ≤ i < n?1. 02. Θ(1)3. Θ(19i)4. Θ(13i)(d) [1 point] What is the asymptotic rendering time (triangle count) at each level i of therecursion tree, for 0 ≤ i < n?1. 02. Θ(49i)3. Θ(3i)4. Θ(4i)(e) [2 points] What is the total asymptotic cost for the CPU, when rendering a snowflakewith LoD n using 3D hardware-accelerated rendering?1. Θ(1)2. Θ(n)3. Θ(43n)4. Θ(4n)4 Problem Set 2Second, when using 2D hardware-accelerated rendering, the surfaces’ outlines are broken downinto open or closed paths (list of connected line segments). For example, our snowflake is oneclosed path composed of straight lines. The CPU compiles the list of cooordinates in each path tobe drawn, and sends it to the GPU, which renders the final image. This approach is also used fortalking to high-end toys such as laser cutters and plotters.(f) [1 point] What is the height of the recursion tree for rendering a snowflake of LoD nusing 2D hardware-accelerated rendering?1. log n2. n3. 3 n4. 4 n(g) [1 point] How many nodes are there in the recursion tree at level i, for 0 ≤ i ≤ n?1. 3i2. 4i3. 4i+14. 3 · 4i(h) [1 point] What is the asymptotic rendering time (line segment count) for a node in therecursion tree at level i, for 0 ≤ i < n?1. 02. Θ(1)3. Θ(19i)4. Θ(13i)(i) [1 point] What is the asymptotic rendering time (line segment count) for a node in thelast level n of the recursion tree?1. 02. Θ(1)3. Θ(19n)4. Θ(13n)(j) [1 point] What is the asymptotic rendering time (line segment count) at each level iof the recursion tree, for 0 ≤ i < n?1. 02. Θ(49i)3. Θ(3i)4. Θ(4i)(k) [1 point] What is the asymptotic rendering time (line segment count) at the last leveln in the recursion tree?Problem Set 2 51. Θ(1)2. Θ(n)3. Θ(43n)4. Θ(4n)(l) [1 point] What is the total asymptotic cost for the CPU, when rendering a snowflakewith LoD n using 2D hardware-accelerated
View Full Document
Unlocking...