Try It Now
| Site: | Saylor Academy |
| Course: | CS202: Discrete Structures |
| Book: | Try It Now |
| Printed by: | Guest user |
| Date: | Tuesday, April 23, 2024, 9:34 PM |
Description
Work these exercises to see how well you understand this material.
Exercises
- Suppose that an undirected tree has diameter d and that you would like to select a vertex of the tree as a root so that the resulting rooted tree has the smallest depth possible. How would such a root be selected and what would be the depth of the tree (in terms of d)?
- Suppose that information on buildings is arranged in records with five fields: the name of the building, its location, its owner, its height, and its floor space. The location and owner fields are records that include all of the information that you would expect, such as street, city, and state, together with the owner's name (first, middle, last) in the owner field. Draw a rooted tree to describe this type of record.
Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.
Solutions
- Answer: Locate any simple path of length d and locate the vertex in position ⌈d/2⌉ on the path. The tree rooted at that vertex will have a depth of ⌈d/2⌉, which is minimal.
- Answer:
