Problem Set 2: Introduction to Algorithms

# Problem Set 2: Introduction to Algorithms ###### tags: `MIT` `6.006` `algorithm` :::success - contributed by < `TYChan6028` > - problem set: [Fractal rendering, digital circuit simulation](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/assignments/MIT6_006F11_ps2.pdf) - course website: [MIT 6.006 Introduction to Algorithms, Fall 2011](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/) ::: ## Problem 2-1. Fractal Rendering ```graphviz digraph snowflake { node [shape=box] edge [style=dashed] // n = -1 sf [label="SNOWFLAKE (n)"] // n = 0 sfe1 [label="SNOWFLAKE-EDGE (n)"] sfe2 [label="SNOWFLAKE-EDGE (n)"] sfe3 [label="SNOWFLAKE-EDGE (n)"] // n = 1 sfe11 [label="n - 1"] sfe12 [label="n - 1"] sfe13 [label="n - 1"] sfe14 [label="n - 1"] sfe21 [label="n - 1"] sfe22 [label="n - 1"] sfe23 [label="n - 1"] sfe24 [label="n - 1"] sfe31 [label="n - 1"] sfe32 [label="n - 1"] sfe33 [label="n - 1"] sfe34 [label="n - 1"] // n = k sfek1 [label="⋮",shape=plaintext] sfek2 [label="⋮",shape=plaintext] // n = k + 1 sfek11 [label=0] sfek12 [label=0] sfek13 [label=0] sfek14 [label=0] sfek21 [label=0] sfek22 [label=0] sfek23 [label=0] sfek24 [label=0] // levels lvl1 [label="level -1",shape=plaintext] lvl2 [label="level 0",shape=plaintext] lvl3 [label="level 1",shape=plaintext] lvln [label="level N",shape=plaintext] // recursion tree sf->{sfe1 sfe2 sfe3} sfe1->{sfe11 sfe12 sfe13 sfe14} sfe2->{sfe21 sfe22 sfe23 sfe24} sfe3->{sfe31 sfe32 sfe33 sfe34} sfe13->sfek1 [style=invis] sfe32->sfek2 [style=invis] sfek1->{sfek11 sfek12 sfek13 sfek14} sfek2->{sfek21 sfek22 sfek23 sfek24} {rank=same;sfe1 sfe2 sfe3} {rank=same;sf lvl1} {rank=same;sfe1 lvl2} {rank=same;sfe11 lvl3} {rank=same;sfek11 lvln} } ``` ### 1. 3D hardware-accelerated rendering #### a. What is the height of the recursion tree for rendering a snowflake of LoD $n$? The height of the recursion tree $=$ # of edges on the longest downward path from level $0$ $\rightarrow$ level $n$. Answer: ==2. $n$== #### b. How many nodes are there in the recursion tree at level $i$, for $0 \leq i \leq n$? Each node makes 4 recursive calls, so the number of nodes at level $i=$ (# of initial edges) $\times$ (# of calls per node) ^ (levels) $= 3 \cdot 4^i$. Answer: ==4. $3 \cdot 4^i$== #### c. What is the asymptotic rendering time (triangle count) for a node in the recursion tree at level $i$, for $0 \leq i < n$? No matter the level of the node, each node renders 1 triangle. Answer: ==2. $\Theta(1)$== #### d. What is the asymptotic rendering time (triangle count) at each level $i$ of the recursion tree, for $0 \leq i < n$? The asymptotic rendering time $=$ (# of nodes at level $i$) $\times$ (rendering time per node) $=(3 \cdot 4^i) \times \Theta(1)=\Theta(4^i)$. Answer: ==4. $\Theta(4^i)$== #### e. What is the total asymptotic cost for the CPU, when rendering a snowflake with LoD $n$ using 3D hardware-accelerated rendering? The total asymptotic cost $=$ (# of nodes until level $n$) $\times$ (rendering time per node) $=(3 \cdot \sum_{i=0}^{n-1} 4^i) \times \Theta(1)=\frac{3(4^n-1)}{4-1} \times \Theta(1)=\Theta(4^n)$ Answer: ==4. $\Theta(4^n)$== ### 2. 2D hardware-accelerated rendering #### f. What is the height of the recursion tree for rendering a snowflake of LoD $n$ using 2D hardware-accelerated rendering? Answer: ==2. $n$== #### g. How many nodes are there in the recursion tree at level $i$, for $0 \leq i \leq n$? Answer: ==4. $3 \cdot 4^i$== #### h. What is the asymptotic rendering time (line segment count) for a node in the recursion tree at level $i$, for $0 \leq i < n$? No matter the level of the node, each node renders 2 lines (i.e. 3 vertices). Answer: ==2. $\Theta(1)$== :::danger **Correction:** 0 I thought adding the 2 new vertices to the list of coordinates counted as "rendering". I misunderstood. Hence no rendering is performed and the cost is $0$. ::: #### i. What is the asymptotic rendering time (line segment count) for a node in the last level $n$ of the recursion tree? The termination condition is triggered at level $n$, so no lines are drawn. Answer: ==1. $0$== :::danger **Correction:** $\Theta(1)$ At level $n$, 1 straight line is drawn per node. Hence the time complexity is $\Theta(1)$. ::: #### j. What is the asymptotic rendering time (line segment count) at each level $i$ of the recursion tree, for $0 \leq i < n$? The asymptotic rendering time $=$ (# of nodes at level $i$) $\times$ (rendering time per node) $=(3 \cdot 4^i) \times \Theta(1)=\Theta(4^i)$. Answer: ==4. $\Theta(4^i)$== :::danger **Correction:** 0 ::: #### k. What is the asymptotic rendering time (line segment count) at the last level $n$ in the recursion tree? No rendering calls are made at level $n$, so the asymptotic rendering time is $\Theta(1)$. Answer: ==1. $\Theta(1)$== :::danger **Correction:** $\Theta(4^n)$ (# of nodes at level $n$) $\times$ (rendering time per node) $= (3 \cdot 4^n) \times \Theta(1) = \Theta(4^n)$ ::: #### i. What is the total asymptotic cost for the CPU, when rendering a snowflake with LoD n using 2D hardware-accelerated rendering? The total asymptotic cost $=$ (# of nodes until level $n$) $\times$ (rendering time per node) $=(3 \cdot \sum_{i=0}^{n-1} 4^i) \times \Theta(1)=\frac{3(4^n-1)}{4-1} \times \Theta(1)=\Theta(4^n)$ Answer: ==4. $\Theta(4^n)$== :::warning (# of nodes until level $n$) $\times$ (rendering time per node) $=(3 \cdot 4^i) \times 0 + \Theta(4^n)=\Theta(4^n)$. ::: ### 3. 2D software rendering #### m. What is the height of the recursion tree for rendering a snowflake of LoD $n$? Answer: ==2. $n$== #### n. How many nodes are there in the recursion tree at level $i$, for $0 \leq i \leq n$? Answer: ==4. $3 \cdot 4^i$== #### o. What is the asymptotic rendering time (line segment length) for a node in the recursion tree at level $i$, for $0 \leq i < n$? Assume that the sides of the initial triangle have length $1$. Rendering is only performed at the last level, so the cost is 0. Answer: ==1. $0$== #### p. What is the asymptotic rendering time (line segment length) for a node in the last level $n$ of the recursion tree?