Problem 1:

a) Prove via Mathematical Induction: 2ⁿ⁺² >= 2n + 5; n>=1.

b) Prove via Mathematical Induction: n² < 2ⁿ for n 5.

c) Prove via Mathematical Induction 4ⁿ¹ > n² for n 3.

Problem 2:

Give the pseudo-code for the Heapify procedure in a Heap Sort Algorithm and state the running time?

Problem 3:

Give the pseudo-code for deleting an element in a binary tree, binary search tree and a binary max heap data structure. Discuss the worst case running time for your pseudo code. Include the find operation code for all operations.

Problem 4:

Give the pseudo-code for inserting an item d as child of a vertex v in a list stored in the following node representation (v=nil to make a new root).

data

Parent pointer

Left child pointer

Right child pointer