CSSE 230
Data Structures and Algorithm Analysis

Homework 8  - 36 points

Reading (optional)

(Towards the Reading grade) In our textbook, read 9.1-9.6 (the zybooks "assignment" called "Reading for HW8").

This reading is mostly about graph applications, which complements the lectures nicely.

Additionally, section 9.9, though not required, may be useful to you when doing GraphSurfing Milestone 2.

To Be Turned In

Submit to the drop box.

  1. (16 points) For this problem, consider the two main ways of implementing a graph: adjacency lists, or adjacency matrix.
    1. Of the two implementations, which would be more efficient at removing an edge from the graph? Explain your answer by describing what must be done in each of the two implementations, and giving the asymptotic running times.
    2. Of the two implementations, which would be more efficient at removing an vertex from the graph? Explain your answer by describing what must be done in each of the two implementations, and giving the asymptotic running times.
  2. (20 points) In this problem, we consider completely full binary trees with N nodes and height H 
                      (so that N = 2H+1 – 1 )
    1. (10 points) Draw trees of height 1, 2, and 3, and for each, calculate N, H, and the sum of the heights of every node.
    2. (10 points) Organize this information in a table and discover a formula for the sum of the heights of a complete tree in terms of N and H.
    3. (0 points, optional) If you want to show off your skills, prove this formula using induction. Our "standard" binary tree induction approach based on the subtrees (using the definition that a non-empty binary tree has a root plus left and right subtrees) works well here.