CMSC 341 -- Fall 2004 -- Project 3 Questions

Copy this file into your directory and edit it to add your answers
to the following questions about project 3.

These questions count for 10% of your project grade.

1. (5 points)

   What is the computational complexity (in O() terms) of your code
   for finding a tree by name?  Why? Given all of the data structures
   that we have considered to this point in the class, what is the
   best possible computational complexity that can be achieved?  How?

2. (5 points)

   Recall that for full binary trees there is a relationship between
   internal path length (IPL) and external path length (ELP).  For a
   full binary tree with NI internal nodes, it is the case that EPL =
   IPL + 2NI.  Give an INTUITIVE explanation for why that is the case.
   Do not recapitulate the proof in the lecture notes.  Hint: Think
   about what IPL is, and then think about why adding 2NI to IPL
   yields EPL for full binary trees in particular.