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...
-
Refer to the data in Exercise 85 for Waterloo Storage Products. Assume in this exercise that the company uses absorption costing. In exercise: Nits in beginning inventory. . . . . . . . . . . . . . ....
-
Jordan took a business trip from New York to Denver. She spent two days in travel, conducted business for nine days, and visited friends for five days. She incurred the following expenses: Airfare. $...
-
a. Begin with the data from \(n=185\) countries throughout the world that have valid (nonmissing) life expectancies. Plot the life expectancy versus the gross domestic product and private...
-
Maria Garcia is a CPA whose firm has prepared the tax returns of Stanley Corporation for many years. A review of Stanleys last three tax returns by a new staff accountant, who has been assigned to...
-
The Alberta Plumbing Company (APC) operates a plumbing repair business, with branches located throughout the province of Alberta. They saw improved performance in the volume of repairs in the month...
-
Determine vo and the required PIV rating of each diode for the configuration of Fig. 2.168. 100 V Ideal diodes -100 V 2.2 k
-
Why did Airborne sell out to DHL in 2003? Why do you think that DHL was unable to grow its U.S. market share, and subsequently exited the market in 2009? Read the case study Airborne Express:...
-
The star Betelgeuse is about half as hot as the Sun and about 1 2 0 , 0 0 0 1 2 0 , 0 0 0 times as luminous ( ( radiates 1 2 0 , 0 0 0 1 2 0 , 0 0 0 times as much power ( = ( = energy per unit time )...
-
The Nelson Company has $1,485,000 in current assets and $495,000 in current liabilities. Its initial inventory level is $330,000, and it will raise funds as additional notes payable and use them to...
-
Harry Draco Ltd manufactures laboratory equipment that requires a highly skilled labour force. The management has been experiencing inexplicable variances in terms of labour efficiency for quite some...
-
If the earnings per share of a company is $3.85 and the earnings yield is 2.5%, what is the price per share? $154.00 $64.94 $1.54 HE 1111
-
Calculating permeate flux and concentration. Calculate the quantity and quality of water produced by a single RO membrane element (permeate concentration, observed rejection and recovery) given the...
-
i += 1 E) None of the abov Q3-3) If x=41.536 What will be the output of the expression print("%.2f" %x) A) 41.536 ) 41.53 C) 41.00 D) 41%.2 = 41.54 None of the left tout: 6?
-
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...
-
Attach LEDs to your system bus so that you can monitor its activity. For example, use an LED to monitor the read/write line on the bus.
-
Describe the role of these signals in a bus: a. R/W b. data ready c. clock
-
Draw a UML sequence diagram that shows a four-cycle handshake between a bus master and a device.
Study smarter with the SolutionInn App