QUESTION 1

In a Binary Search Tree (BST), the predecessor of a node x is defined as the node with the largest key smaller than x.key. Write a pseudocode that returns the predecessor of a node x. Assume all keys in the tree are distinct. What is the worst-case running time of your algorithm?

QUESTION 2

Consider the binary search tree (BST) below, where each node has a label. Note that the label is NOT the key. The keys satisfy the BST property. Assume that all the keys are distinct.

QUESTION 3

Let T be a binary search tree (BST) with n keys. Select all the statements below which are TRUE.

• If T is a perfectly balanced BST (all leaves have the same depth), then the depth of all nodes is O(lg n)

• The height of T is O(lgn)

• Tree-insert, tree-delete, and tree-search have the worst-case running time O(n)

• INORDER-TREE-WALK(T.root) prints the keys in monotonically increading order

QUESTION 4

Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is p = < 7, 2, 8, 4, 5 >. Show the m and s tables and the printing of an optimal parenthesization. Use the algorithm learned in class.

QUESTION 5

Consider the matrix chain A2A3A4, where A2 has dimension 10 × 20, A3 has dimension 40 × 60 and A4 has dimension 60 × 10. Which of the following parenthesizations require the minimum number of scalar multiplications?

• This chain of matrices cannot be parenthesized because the sequence of matrices is incompatible

• All parenthesizations have the same number of scalar multiplications

• ((A2A3)A4)

• (A2(A3(A4))

2019-01-18T12:23:19+00:00
Programming