• 1. (a) Show that there are at most [n/2h+1] nodes of height h in any n-element binary heap. (b) Illustrate the operation of Build-Max-Heap on the array A =< 7, 5, 19, 8, 86, 17, 8, 20, 11 >, using a tree representation of the heap. (c) A d-ary heap is similar to a binary heap, except that nodes have d children instead of two children. Justify your answers to the questions below. i. What is the height of the tree representing a d-ary heap with n elements? ii. What is the time taken for a delete-max operation in a d-ary heap? How does it compare with that for a binary heap? 2. (a) A complete k-ary tree is a k-ary tree in which all leaves have the same depth and all internal nodes have degree k. Derive a formula for the number of nodes in a complete k-ary tree of height h. Justify your answer. (b) Suppose we are given the outputs of the preorder and inorder traversals of the nodes of a binary tree. Can the binary tree structure be constructed from these outputs? If yes, explain how. If no, explain why not. (Note: The binary tree to be constructed is not restricted to be a binary search tree.) You can assume the values of the nodes are all distinct. 3. (a) Perform depth-first search on the following graph; whenever there is a choice of vertices, pick the one that is numerically smaller. Classify each edge as a tree edge, forward edge, back edge, or cross edge, and give the discovery and finish time of each vertex. 1 5 4 2 6 3 7 (b) Find a topological sort of the directed acyclic graph above. Draw the vertices in topo- logical order, along with all edges of the graph. (c) Does the graph above have a unique topological sort? If yes, justify your answer. If no, identify alternative topological sorts with justification.

• 1. (a) Show that there are at most [n/2h+1] nodes of height h in any n-element binary heap. (b) Illustrate the operation of Build-Max-Heap on the array A =< 7, 5, 19, 8, 86, 17, 8, 20, 11 >, using a tree representation of the heap. (c) A d-ary heap is similar to a binary heap, except that nodes have d children instead of two children. Justify your answers to the questions below. i. What is the height of the tree representing a d-ary heap with n elements? ii. What is the time taken for a delete-max operation in a d-ary heap? How does it compare with that for a binary heap? 2. (a) A complete k-ary tree is a k-ary tree in which all leaves have the same depth and all internal nodes have degree k. Derive a formula for the number of nodes in a complete k-ary tree of height h. Justify your answer. (b) Suppose we are given the outputs of the preorder and inorder traversals of the nodes of a binary tree. Can the binary tree structure be constructed from these outputs? If yes, explain how. If no, explain why not. (Note: The binary tree to be constructed is not restricted to be a binary search tree.) You can assume the values of the nodes are all distinct. 3. (a) Perform depth-first search on the following graph; whenever there is a choice of vertices, pick the one that is numerically smaller. Classify each edge as a tree edge, forward edge, back edge, or cross edge, and give the discovery and finish time of each vertex. 1 5 4 2 6 3 7 (b) Find a topological sort of the directed acyclic graph above. Draw the vertices in topo- logical order, along with all edges of the graph. (c) Does the graph above have a unique topological sort? If yes, justify your answer. If no, identify alternative topological sorts with justification.