# DMMR: Study guide for Chapter 11 of the textbook by K. Rosen

## STUDY all of SECTION 11.1, the parts of Section 11.2 on Decision Trees, and definition of spanning tree and minimum spanning tree from section 11.4 and 11.5, and Prim's algorithm.

#### Key concepts. (This is not a complete list of all the content.)

• Section 11.1: trees, rooted trees, rooted ordered trees; \$m\$-ary trees, full \$m\$-ary trees, and complete \$m\$-ary trees; various counting properties and counting relationships (rooted) (\$m\$-ary) trees.
• Section 11.2: only study the subsection on Decision trees and the applications using counting properties of trees.
• Section 11.3: NOT COVERED (this material is covered in other informatics courses)
• Section 11.4: the definition of a spanning tree for a connected graph, and the proof that every connected graph has one; (We skipped the material on depth-first and breath-first search: this is covered in other Informatics courses.)
• Section 11.5: minimum spanning trees, and Prim's algorithm (we covered Prim's algorithm only briefly, without proof of correctness)

#### Parts of Chapter 11 that were NOT covered in this course

Most of Section 10.2, except for Decision Trees, which were covered; All of Section 10.3; Most of section 10.4, except for definition of spanning trees; in Section 11.5 the parts relating to Kruskal's algorithm, and the proof of correctness of Prim's algorithm, were not covered.

 Informatics Forum, 10 Crichton Street, Edinburgh, EH8 9AB, Scotland, UK Tel: +44 131 651 5661, Fax: +44 131 651 1426, E-mail: school-office@inf.ed.ac.uk Please contact our webadmin with any comments or corrections. Logging and Cookies Unless explicitly stated otherwise, all material is copyright © The University of Edinburgh