Homework 5 is due on Wednesday, July 14th.

0. Read Chapter 10. Indicating in at most three sentences one or more of the following: the passage in the reading— including its page number—you:

- Found most difficult
- Found most surprising
- Would like to have discussed in the next lecture

1. Design an algorithm that reconstruct a tree from its preorder and inorder traversals.

2. Let T be a tree with n vertices. How many connected component are there when:

a, p edges are removed (p<n-1).

b, p vertices are removed (p<n).

If the number of connected components can not be counted, explain why.

3. Count the number of leaves of a complete binary tree of height h.

4. Discuss the A* algorithm and compare that to Depth first search and Breadth first search.

5. The Eucledian Minimum Spanning tree is is a minimum spanning tree of a set of *n* points in ℝ^{d}, where the weight of the edge between each pair of points is the distance between those two points. Give an algorithm for computing the Euclidean Minimum Spanning tree.

### Like this:

Like Loading...

Filed under: Uncategorized |

## Leave a Reply