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.
