Homework 7, Fundamental Algorithms, Fall 97

Due Date: Monday, October 27.

1. Consider a tree in which each internal node has c or more children, where c is a constant integer of value 2 or more. Show that the number of internal nodes, I, in the tree and the number of leaves, L, are related by the formula: L-1 >= (c-1)I.
Hint: Use tokens. How many tokens should a leaf receive, and what do you do with the tokens?

2. Consider a tree in which each node is colored either red or green. You are allowed to cut edges in this tree. Your goal is to choose the subset of edges to cut so that the resulting subtree rooted at the original root r has the largest possible excess of red over green nodes (possibly, this excess is negative). Design an algorithm to compute this excess.
Hint. Compute this for every node in the tree. How do you decide whether to cut an edge?

Problems 2.12, 4.16. (See back of text, pages 399-405).

Course Home Page

cole@cs.nyu.edu (Richard Cole)
Last modified: Oct 19, 1997