CSE 326

HW 2

Related reading: Chapters 3 & 4

Due date: Monday, April 16, 2001 in class

Total points: 40 points + 5 possible extra credit points

Homework #2

  1. In lecture #4 we discussed the stretchy array implementation of a stack. Suppose instead of doubling the size of the array when Push would otherwise cause an overflow, the array is increased in size by a constant amount:

    2. maxsize = maxsize + 10

    Give an amortized analysis (upper bound, big-Oh) of the cost of Push (averaged over a sequence of n pushes). Assume maxsize is initially 0. The analysis will consist of the following steps:

    (a) How many stretches are made for n pushes?

    (b) What is the total time to perform n pushes, counting both the regular pushes and those that cause a stretch? (Hint: recall the formula for evaluating an arithmetic series.)

    (c) What is the amortized time per push?

     

  2. Assume a binary tree in which the leaf nodes hold integer numbers and the non-leaf nodes hold the binary operations ‘+’, ‘-‘, ‘*’, and ‘/’.
  1. Provide an algorithm that, when given the root of a tree, evaluates the expression represented by the tree.
  2. Provide an algorithm that, when given the root of a tree, outputs a program which evaluates the expression represented by the tree. The program should consist just of instructions of the form ‘var = integer’, ‘var = var + var’, ‘var = var - var’, ‘var = var * var’, and ‘var = var / var’, where each ‘var’ stands for a variable name.

 

3. Consider the following AVL tree.

Show the modified tree under each of the following operations (show any intermediate steps). Note: The two operations are independent; each of them starts from the above tree.
  1. Deletion of the key 4
  2. Insertion of the key 16.

 

4. Let the height of a tree be the number of nodes in the longest path from the root to the leaves.

  1. Provide a recursive algorithm that when given a binary tree determines the height of the tree.
  2. What are the time and space complexities of your algorithm (Note: you cannot assume that the tree is balanced)?
  3. What are the time and space complexities of your algorithm, if only AVL trees are allowed?
  4. Extra Credit: A more efficient algorithm can be used to determine the height of a tree when the input is known to be an AVL tree (it is more efficient in some cases, not all). Provide such an algorithm.