computer Algorithm

Prof. Pitts CS557A: Algorithms Fall 2019

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

a. What are the base or terminating statements of the algorithm?

b. What are the recursive statements of the algorithm?

c. What statements perform the non-recursive work of the algorithm?

d. Consider the binary tree shown below. Indicate how the algorithm will number the nodes by tracing the

algorithm’s execution on the tree.

2. 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) .

3. 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 (or try this website

https://www.math.uh.edu/~ilya/class/useful_summations.pdf)

a. ∑ i=0

n

(i 2 +i+1)

b. ∑ i=0

n

ij

c. ∑ i=0

n/2

i

1/1