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.

1. 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

1. What are the base or terminating statements of the algorithm?
2. What are the recursive statements of the algorithm?
3. What statements perform the non-recursive work of the algorithm?
4. Consider the binary tree shown Indicate how the algorithm will number the nodes by tracing the algorithm’s execution on the tree.
5. 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) .
6. 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.

4. 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 

Attachments:

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