Advice on the Writing Projects for Chapter 8

1. You can probably find something useful in [BiLl]. Also, take a look at [WhCl].

2. Consult books on data structures and/or algorithms, such as [GoBa], [Kr], or [Ma2]. The Emacs LISP library implements AVL-trees, and C++ code for implementing this data structure is also available on the Web. In addition, here is a site that gives a demonstration. (These sites were found by doing a search for the words "AVL" and "tree.")

3. There is a relevant article in [De2], pp. 290-295. As in the previous Writing Project, you should try doing a search for the phrase "quad tree," and you should consult a data structures book, such as ones listed there.

4. See hints for Writing Project 2.

5. Two interesting articles are [McCh] and [Me]. See also data structures textbooks, such as [St], and the suggestions in Writing Project 2. There is a nice Web site on this topic, with animation.

6. An elementary exposition can be found in [Gr2]. See also algorithm or data structures texts, such as [Sm], and the suggestions in Writing Project 2. The most complete source on games is [BeCo], which takes you far beyond trees.

7. See books on parallel processing, such as [Le2], to learn what meshes of trees are and how they are applied. Here is a research paper on the topic.

8. Books are beginning to appear in this new field; see [Ma5], for instance, or search in amazon.com.

9. This problem is much more difficult than the plain minimum spanning tree problem. You may have to go to the research literature here (search the Mathematical Reviews database on keywords "spanning tree" and "constrained" or "degree"). For more general hints on minimum spanning trees, see the suggestions for Writing Project 11.

10. Any good data structures or algorithms book would have loads of material on this topic, including those mentioned in Writing Projects 2, 5, and 6 (or others given in the reference list). See also volume 3 of Knuth's classic [Kn]. You can also find some nice demonstrations of sorting algorithms (here, here, or here) and, of course, lots of other relevant information, on the Web.

11. See the article [GrHe]. Incidentally, a Web search for the phrase "minimum spanning tree" is likely to turn up some good sources of information on this topic, such as demonstrations.

12. See books on random graph theory ([Bo2] or [Pa]), or the article [Ti]. A Web search for the phrase "random tree" might turn up something, as well. A maze is a tree of sorts, and this Web site draws random mazes.