# 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.