### Consider the binary tree shown Indicate how the algorithm will number the nodes by tracing the algorithmâ€™s execution on the tree.

**INSTRUCTIONS TO CANDIDATES**
###### ANSWER ALL QUESTIONS

Homework Assignment 2

Answer each of the questions below and submit your answers as a PDF document through Canvas by the due date. You may submit a scanned handwritten document from this assignment, but do not choose a very high resolution (above 300dpi) and scan all pages as portrait.

- Consider the following recursive algorithm:

Algorithm Traverse(b: BinaryTree): set global count to 1

if b is empty return

Traverse(b left subtree) mark root with count increment count Traverse(b right subtree) return

Answer the following questions

- What are the base or terminating statements of the algorithm?
- What are the recursive statements of the algorithm?
- What statements perform the non-recursive work of the algorithm?
- Consider the binary tree shown Indicate how the algorithm will number the nodes by tracing the algorithm’s execution on the tree.
- Consider the function (f (n)=4 x4−50 x3−1000 ) . Find the lower asymptotic bound ( Ω(g) ) and show that g is the lower bound using the definition of Ω (find a constant c>0 such that f (n)>g (n) for all n >n 0 for some constant n0> 0 . Then use the method of limits to show that f ∈Ω(g) .
- Consider the algorithm below:

Algorithm X(b : BinaryTree) if b is empty

return 0

lc = X( left subtree of b) rc = X( right subtree of b) return lc + rc + 1

Prove that this algorithm returns the number of nodes in the binary tree using induction.

- Find closed form solutions (solutions that do not have the summation symbol) for the following series. Use the basic series solutions in Chapter 1 of your textbook

## Related Questions

##### Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

##### The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

##### Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

##### SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1
Project 1
Introduction - the SeaPort Project series
For this set of projects for the course, we wish to simulate some of the aspects of a number of

##### Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1
Project 2
Introduction - the SeaPort Project series
For this set of projects for the course, we wish to simulate some of the aspects of a number of