A NAND tree is a complete binary tree with the following properties: Each leaf node...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
A NAND tree is a complete binary tree with the following properties: • Each leaf node is labeled either 0 or 1. • All internal nodes are NAND gates. A NAND gate is a logic gate that takes in two inputs and evaluates to 0 if both its inputs are 1 and to 1 if either input is 0. We can evaluate a NAND tree by computing the value of the top-level NAND gate in the tree. which will evaluate either to 0 or to 1. (If the tree is a single leaf, the tree evaluates to the value of that leaf.) For example, the left and right trees below evaluate to 1; the middle tree evaluates to 0: Here is a simple recursive algorithm for evaluating a NAND tree: • If the tree is a single leaf node, return the value of that node. • Otherwise, recursively evaluate the left and right subtrees, then apply the NAND operator to both of those values. This algorithm takes O(n) time to evaluate a NAND tree with n leaf nodes. We can improve this algorithm using short-circuiting. If one subtree of node v evaluates to 0, then v must evaluate to 1 because 0 NAND 0= 1 and 0 NAND 1=1. Therefore, we don't need to evaluate v's other subtree. This gives the following algorithm, which we'll call the left-first algorithm: • If the tree is a single leaf node, return the value of that node. Otherwise: • Recursively evaluate the left subtree. . If it evaluates to 0, return 1. Otherwise, recursively evaluate the right subtree. If it evaluates to 0, return 1; otherwise return 0. In many cases, the left-first algorithm runs faster than the O(n)-time naive algorithm. However, it is possible to construct NAND trees for which the left-first algorithm runs in time (n). i. (8 Points) Design an algorithm that creates a NAND tree T with n=2* leaf nodes such that the left-first algorithm never short-circuits when evaluating T. Your algorithm should run in time polynomial in n. Then: • Describe your algorithm. • Prove that your algorithm produces a tree I with n leaves such that the left-first algo- rithm never short-circuits when evaluating T. Prove your algorithm runs in time polynomial in n. Since the left-first algorithm never short-circuits on inputs produced by your algorithm, the left- first algorithm has a worst-case runtime of O(n). 4/6 More generally, any deterministic algorithm for evaluating a NAND tree will have at least one in- put that causes it to run in (n) time, but you don't need to prove this. Despite the (n) worst-case for deterministic evaluation algorithms, there is a simple randomized algorithm for evaluating NAND trees that, on expectation, does less than O(n) work. The idea is simple: use the same algorithm as above, but choose which subtree to evaluate first uniformly at random. We'll call this the random-first algorithm. More concretely: • If the tree is a single leaf node, return the value of that node. • Otherwise: • Choose one of the subtrees of the root at random and evaluate it. . If the value is 0, return 1. • Otherwise, recursively evaluate the other subtree. If the value is 0, return 1; otherwise return 0. To determine the runtime of the random-first algorithm, we will introduce two recurrence rela- tions. Let To(n) be the expected runtime of the random-first algorithm on a tree with n leaf nodes assuming the root evaluates to 0. Let Ti(n) be the expected runtime of the random-first algorithm on a tree with n leaf nodes assuming the root evaluates to 1. ii. (6 Points) Prove that the following recurrence relations for To(n) and Ti(n) are correct: To(1) ≤0(1) To(n) ≤2T1(n/2) + (1) Ti(1) ≤0(1) Ti(n) ≤T1(n/2) + To(n/2) + (1) iii. (6 Points) It turns out that Ti(n) ≤ To(n), though it's somewhat difficult to formally estab- lish this. Using this fact, prove that To(n) = O(n) for some < 1. You can assume n = 4* for some natural number k. (Hint: Write To(n) in terms of itself.) Your result from (iii) proves that the random-first algorithm has expected sublinear runtime on all inputs, since Ti(n) ≤ To(n) = O(n) = o(n). This is one of a few known problems where the best randomized algorithm is more efficient on expectation than the best deterministic algorithm in the worst case. The last part of this problem explores this question: what happens if you try to evaluate a ran- domly-chosen NAND tree? The result is surprising. Let's say a random NAND tree with n=2* leaves is a NAND tree where each leaf is independently assigned a value of 0 or 1 uniformly at random. iv. (4 Points) Let Po(n) denote the probability that a random NAND tree with n leaves evalu- ates to 0 and Pi(n) denote the probability that a random NAND tree with n leaves evalu- ates to 1. Write recurrence relations for Po(n) and Pi(n) and briefly explain why your re- currences are correct. The recurrence relations you came up with in (iv) can't be solved using the techniques we've de- veloped in this course, but you can easily write a short computer program to determine their val- ues by writing out n = 2* and evaluating the recurrence for increasing values of k. If you do, you'll find that when k≥ 15, Po(n) is extremely close to 1 if k is even and Pi(n) is extremely close to 1 if k is odd. Consequently, the algorithm "return the height of the tree modulo 2" returns the right answer with high probability in time (log n), even though it never actually evaluates the tree! A NAND tree is a complete binary tree with the following properties: • Each leaf node is labeled either 0 or 1. • All internal nodes are NAND gates. A NAND gate is a logic gate that takes in two inputs and evaluates to 0 if both its inputs are 1 and to 1 if either input is 0. We can evaluate a NAND tree by computing the value of the top-level NAND gate in the tree. which will evaluate either to 0 or to 1. (If the tree is a single leaf, the tree evaluates to the value of that leaf.) For example, the left and right trees below evaluate to 1; the middle tree evaluates to 0: Here is a simple recursive algorithm for evaluating a NAND tree: • If the tree is a single leaf node, return the value of that node. • Otherwise, recursively evaluate the left and right subtrees, then apply the NAND operator to both of those values. This algorithm takes O(n) time to evaluate a NAND tree with n leaf nodes. We can improve this algorithm using short-circuiting. If one subtree of node v evaluates to 0, then v must evaluate to 1 because 0 NAND 0= 1 and 0 NAND 1=1. Therefore, we don't need to evaluate v's other subtree. This gives the following algorithm, which we'll call the left-first algorithm: • If the tree is a single leaf node, return the value of that node. Otherwise: • Recursively evaluate the left subtree. . If it evaluates to 0, return 1. Otherwise, recursively evaluate the right subtree. If it evaluates to 0, return 1; otherwise return 0. In many cases, the left-first algorithm runs faster than the O(n)-time naive algorithm. However, it is possible to construct NAND trees for which the left-first algorithm runs in time (n). i. (8 Points) Design an algorithm that creates a NAND tree T with n=2* leaf nodes such that the left-first algorithm never short-circuits when evaluating T. Your algorithm should run in time polynomial in n. Then: • Describe your algorithm. • Prove that your algorithm produces a tree I with n leaves such that the left-first algo- rithm never short-circuits when evaluating T. Prove your algorithm runs in time polynomial in n. Since the left-first algorithm never short-circuits on inputs produced by your algorithm, the left- first algorithm has a worst-case runtime of O(n). 4/6 More generally, any deterministic algorithm for evaluating a NAND tree will have at least one in- put that causes it to run in (n) time, but you don't need to prove this. Despite the (n) worst-case for deterministic evaluation algorithms, there is a simple randomized algorithm for evaluating NAND trees that, on expectation, does less than O(n) work. The idea is simple: use the same algorithm as above, but choose which subtree to evaluate first uniformly at random. We'll call this the random-first algorithm. More concretely: • If the tree is a single leaf node, return the value of that node. • Otherwise: • Choose one of the subtrees of the root at random and evaluate it. . If the value is 0, return 1. • Otherwise, recursively evaluate the other subtree. If the value is 0, return 1; otherwise return 0. To determine the runtime of the random-first algorithm, we will introduce two recurrence rela- tions. Let To(n) be the expected runtime of the random-first algorithm on a tree with n leaf nodes assuming the root evaluates to 0. Let Ti(n) be the expected runtime of the random-first algorithm on a tree with n leaf nodes assuming the root evaluates to 1. ii. (6 Points) Prove that the following recurrence relations for To(n) and Ti(n) are correct: To(1) ≤0(1) To(n) ≤2T1(n/2) + (1) Ti(1) ≤0(1) Ti(n) ≤T1(n/2) + To(n/2) + (1) iii. (6 Points) It turns out that Ti(n) ≤ To(n), though it's somewhat difficult to formally estab- lish this. Using this fact, prove that To(n) = O(n) for some < 1. You can assume n = 4* for some natural number k. (Hint: Write To(n) in terms of itself.) Your result from (iii) proves that the random-first algorithm has expected sublinear runtime on all inputs, since Ti(n) ≤ To(n) = O(n) = o(n). This is one of a few known problems where the best randomized algorithm is more efficient on expectation than the best deterministic algorithm in the worst case. The last part of this problem explores this question: what happens if you try to evaluate a ran- domly-chosen NAND tree? The result is surprising. Let's say a random NAND tree with n=2* leaves is a NAND tree where each leaf is independently assigned a value of 0 or 1 uniformly at random. iv. (4 Points) Let Po(n) denote the probability that a random NAND tree with n leaves evalu- ates to 0 and Pi(n) denote the probability that a random NAND tree with n leaves evalu- ates to 1. Write recurrence relations for Po(n) and Pi(n) and briefly explain why your re- currences are correct. The recurrence relations you came up with in (iv) can't be solved using the techniques we've de- veloped in this course, but you can easily write a short computer program to determine their val- ues by writing out n = 2* and evaluating the recurrence for increasing values of k. If you do, you'll find that when k≥ 15, Po(n) is extremely close to 1 if k is even and Pi(n) is extremely close to 1 if k is odd. Consequently, the algorithm "return the height of the tree modulo 2" returns the right answer with high probability in time (log n), even though it never actually evaluates the tree!
Expert Answer:
Answer rating: 100% (QA)
i 8 Points Design an algorithm that creates a NAND tree T with n 2k leaf nodes such that the leftfirst algorithm never shortcircuits when evaluating T Your algorithm should run in time polynomial in n ... View the full answer
Related Book For
Data Structures and Algorithm Analysis in Java
ISBN: 978-0132576277
3rd edition
Authors: Mark A. Weiss
Posted Date:
Students also viewed these computer engineering questions
-
In Verilog code, create a calculator that takes in two 16-bit inputs, and an operator. Perform the operation depending on the operator (add, subtract, multiply, divide), and display the output using...
-
Two binary trees are similar if they are both empty or both nonempty and have similar left and right subtrees. Write a method to decide whether two binary trees are similar. What is the running time...
-
All molecules left before minute 5. We follow four individually labeled molecules and record the minute ti when molecule I leaves the cell. For example, if ti = 1, t2 = 3, t3 = 6, and t4 = 2, the...
-
On December 31, 2021, L Inc. had a $1,600,000 note payable outstanding, due July 31, 2022. L borrowed the money to finance construction of a new plant. L planned to refinance the note by issuing...
-
Explain why it is important to look at a goods real price as opposed to its nominal, or absolute, price.
-
Compute the mean for the followingnumbers. 7 -2 5 9 03 -6 7 -5 28
-
The primary purpose of using a certification authority in electronic commerce is to: a. Ensure both the vendor and customer choose secure private keys b. Provide a banking facility for both the...
-
Julia Price is now in her late 30s and has always wanted children. She has arranged to adopt two siblings from overseas, ages 2 and 4. Julia is happy that she earns enough money to support the...
-
Describe your subnetting design? Use private IP addresses. Specify the network address, subnet mask, range of host addresses, and broadcast address for each subnet.
-
The Scottsville Textile Mill1 produces five different fabrics. Each fabric can be woven on one or more of the mills 38 looms. The sales departments forecast of demand for the next month is shown in...
-
Romberg's integration is used to 9. approximate f(x)dz. a If R1,1 = 8 and R2.2 = 4, then R2,1 is . 3 O b. 7 . O C. 5. O d. 1
-
Audit reporting processses inclusive of "what the report would be against and to whom the report may be accessible to by what methods" and rmore clarification about audit reporting ?
-
The Office Costs in the office were getting out of control and the company appointed a new office manager to identify and sort out the problems. Her task was to put together a report for senior...
-
If A transfers a building with a value of $ 5 0 0 , 0 0 0 and a basis of $ 6 0 0 , 0 0 0 in exchange for 1 0 0 shares of a corporation's stock. What are the tax consequences of the transfer to Brenda...
-
Firms typically have many ideas for projects and need to make informed decisions regarding which projects to take on. One way to decide which project(s) to move forward with is by calculating the...
-
Abecd Accounting, Inc. sells accounting textbooks. The following information summarizes Abecd Accounting's operating activities for the year: Merchandise Inventory, January 1 $ 1 2 , 0 0 0...
-
Find power series and write in sigma notation. f ( x ) = ( 1 + x ) 2 1
-
How do the principles of (a) Physical controls and (b) Documentation controls apply to cash disbursements?
-
By changing the potential function, it is possible to prove different bounds for splaying. Let the weight function W(i) be some function assigned to each node in the tree, and let S(i) be the sum of...
-
Sort 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 using quicksort with median-of-three partitioning and a cutoff of 3.
-
Show that the amortized bound of O(logN) for the skew heap operations described in the text cannot be converted to a worst-case bound, by giving a sequence of operations that lead to a merge...
-
Figure 4. 14 suggests that we can assign each feature vector \(\boldsymbol{x}\) in the iris data set to one of two clusters, based on the value of \(\boldsymbol{u}_{1}^{\top} \boldsymbol{x}\), where...
-
Chelsea Manufacturing, Inc., operates a plant that produces its own regionally marketed Super Salad Dressing. The dressing is produced in two processes, blending and bottling. In the Blending...
-
Salanger Manufacturing Corporation produces a dandruff shampoo in three consecutive processes. The costs of Department 1 for June 2019 were as follows: Department 1 handled the following units during...
Summary Of Preliminary Vital Statistics For Maryland 1938 1st Edition - ISBN: 1013659961 - Free Book
Study smarter with the SolutionInn App