Introduction to Algorithms 6 006 Massachusetts Institute of Technology Professors Erik Demaine and Srini Devadas September 15 2011 Problem Set 2 Problem Set 2 Both 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 for instructions on preparing your solutions Remember your goal is to communicate Full credit will be given only to a correct solution which is described clearly Convoluted and obtuse descriptions might receive low marks even when 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 which you will use to find any errors in the proof that you submitted You will need to submit a critique of your solutions by Thursday September 29th 11 59PM Your grade will be based on both your solutions and your critique of the solutions Problem 2 1 40 points Fractal Rendering You landed a consulting gig with Gopple who is about to introduce a new line of mobile phones with Retina HD displays which are based on unicorn e ink and thus have infinite resolution The high level executives heard that fractals have infinite levels of detail and decreed that the new phones 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 do not have infinite processing power so the Koch fractal cannot be rendered in infinite detail Gopple engineers will stop the recursion at a fixed depth n in order to cap the processing requirement For example at n 0 the fractal is just a triangle Because higher depths result in more detailed drawing 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 2 S NOWFLAKE n 1 e1 e2 e3 edges of an equilateral triangle with side length 1 2 S NOWFLAKE E DGE e1 n 3 S NOWFLAKE E DGE e2 n 4 S NOWFLAKE E DGE e3 n S NOWFLAKE E DGE edge n 1 if n 0 2 edge is an edge on the snowflake 3 else 4 e1 e2 e3 split edge in 3 equal parts 5 S NOWFLAKE E DGE e1 n 1 6 f2 g2 edges of an equilateral triangle whose 3rd edge is e2 pointing outside the snowflake 7 f2 g2 e2 is a triangle on the snowflake s surface 8 S NOWFLAKE E DGE f2 n 1 9 S NOWFLAKE E DGE g2 n 1 10 S NOWFLAKE E DGE e3 n 1 The sketch above should be sufficient for solving this problem If you are curious about the missing details you may download and unpack the problem set s zip archive and read the CoffeeScript implementation in fractal src fractal coffee In this problem you will explore the computational requirements of four different methods for rendering the fractal as a function of the LoD n For the purpose of the analysis consider the recursive calls to S NOWFLAKE E DGE do not count the main call to S NOWFLAKE as part of the recursion tree You can think of it as a super root node at a special level 1 but it behaves differently from all other levels so we do not include it in the tree Thus the recursion tree is actually a forest of trees though we still refer to the entire forest as the recursion tree The root calls to S NOWFLAKE E DGE are all at level 0 Gopple s engineers have prepared a prototype of the Koch fractal drawing software which you can use to gain a better understanding of the problem To use the prototype download and unpack the problem 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 is responsible for producing the final image So from the CPU s perspective rendering a triangle costs the same no matter what its surface area is and the time for rendering the snowflake fractal is 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 n 2 n Problem Set 2 3 Figure 2 Koch snowflake drawn with triangles 3 3 n 4 4 n b 2 points How many nodes are there in the recursion tree at level i for 0 i n 1 2 3 4 3i 4i 4i 1 3 4i c 1 point What is the asymptotic rendering time triangle count for a node in the recursion tree at level i for 0 i n 1 0 2 1 i 3 19 i 4 13 d 1 point What is the asymptotic rendering time triangle count at each level i of the recursion tree for 0 i n 1 2 3 4 0 i 49 3i 4i e 2 points What is the total asymptotic cost for the CPU when rendering a snowflake with LoD n using 3D hardware accelerated rendering 1 2 3 4 1 n n 43 4n 4 Problem Set 2 Second when using 2D hardware accelerated rendering the surfaces outlines are broken down into open or closed paths list of connected line segments For example our snowflake is one closed path composed of straight lines The CPU compiles the list of cooordinates in each path to be drawn and sends it to the GPU which renders the final image This approach is also used for talking 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 n using 2D hardware accelerated rendering 1 2 3 4 log n n 3n 4n g 1 point How many nodes are there in the recursion tree at level i for 0 i n 1 2 3 4 3i 4i 4i 1 3 4i h 1 point What is the asymptotic rendering time line segment count for a node in the recursion tree at level i for 0 i n 1 0 2 1 i 3 19 i 4 13 i 1 point What is the asymptotic rendering time line segment count for a node in the last level n of the recursion tree 1 2 3 4 0 1 n 19 n 13 j 1 point What is the asymptotic rendering time line segment count at each level i of the recursion tree for 0 i n 1 2 3 4 0 i 49 3i 4i k 1 point What is the asymptotic rendering time line segment count at the last level n …
View Full Document
Unlocking...