Definition 3.5 (Baase & Van Gelder) 605.621 Page 1 of 3 An Improved Method for Generating Recursion Trees
Baase and Van Gelder define an algorithm for generating a recursion tree. First let’s look at the algorithm they defined. Then we’ll repeat our work with Figure 4.5 using the notation Baase and Van Gelder suggest. I believe that this notation makes the manual construction of recursion trees less error- prone for students.
Definition 3.5 (Baase and Van Gelder) Recursion tree rules
1. The work copy of the recurrence equation uses a different variable from the original copy; it is called the auxiliary variable. Let k be the auxiliary variable for the purposes of discussion. The left side of the original copy of the recurrence equation (let’s assume it is T(n)) becomes the size field of the root node for the recursion tree.
2. A node has two fields: size and non-recursive cost. An incomplete node has a value for its size field, but not for its non-recursive cost.
3. The process of determining the non-recursive cost field and the children of an incomplete node is called the expansion of that node. We take the size field in the node to be expanded and substitute it for the auxiliary variable k in our work copy of the recurrence equation. The resulting terms containing T on the right side of that equation become children of the node being expanded; all remaining terms become that node’s non-recursive cost
4. If you have generated a recursion tree to its base case, expanding a base case size gives the non- recursive cost field and no children. (usually assume base case cost of one)
In any subtree of the recursion tree, the following equation holds:
Equation 3.7 (Baase and Van Gelder) 𝑠𝑖𝑧𝑒 𝑓𝑖𝑒𝑙𝑑 𝑜𝑓 𝑟𝑜𝑜𝑡 =
∑ 𝑛𝑜𝑛𝑟𝑒𝑐𝑢𝑟𝑠𝑖𝑣𝑒 𝑐𝑜𝑠𝑡 𝑜𝑓 𝑒𝑥𝑝𝑎𝑛𝑑𝑒𝑑 𝑛𝑜𝑑𝑒𝑠 + ∑ 𝑠𝑖𝑧𝑒 𝑓𝑖𝑒𝑙𝑑𝑠 𝑜𝑓 𝑖𝑛𝑐𝑜𝑚𝑝𝑙𝑒𝑡𝑒 𝑛𝑜𝑑𝑒𝑠
An example of using the Baase and Van Gelder approach is given in the following two pages.
Source For Improved Recursion Tree
Computer Algorithms: Introduction to Design and Analysis, Third Edition, Sara Baase and Allen Van Gelder, Addison Wesley Longman, 2000.
[no eBook available but the book is in print in the Sheridan Libraries QA76.9.A43 B33 2000 and QA76.6 .B251 1978]
Algorithm is Baase and Van Gelder, Section 3.7 Recursion Trees pages 134-137
CS Help, Email: tutorcs@163.com
Definition 3.5 (Baase & Van Gelder) 605.621 Page 2 of 3
浙大学霸代写 加微信 cstutorcs
Definition 3.5 (Baase & Van Gelder) 605.621 Page 3 of 3
程序代写 CS代考 加微信: cstutorcs