Trees, Recurrence Relations and Algorithmic Complexity: every key term you need (+ practice quiz)
25 flashcard terms for Discrete Mathematics Topic 8, written to match the course framework. Study them here, then drill them as interactive flashcards, or test yourself with the 15-question quiz — free, no account needed.
A connected graph containing no cycles. On n vertices it always has exactly n minus one edges, and adding any new edge creates exactly one cycle.
Forest
A graph with no cycles that need not be connected, so it is a disjoint collection of trees. Its edge count is the vertex count minus the number of components.
Rooted tree
A tree with one vertex singled out as the root, which orients every edge away from it and gives each other vertex a unique parent and a well defined depth.
Leaf and internal vertex
A leaf is a vertex with no children in a rooted tree, while an internal vertex has at least one. Counting leaves against internal vertices constrains the shape of the tree.
Height of a tree
The greatest depth of any vertex, measured as the number of edges from the root. Balanced structures keep the height near the logarithm of the vertex count.
Binary tree
A rooted tree in which each vertex has at most two children, distinguished as left and right. A full version requires each internal vertex to have exactly two.
Binary search tree
A binary tree whose ordering keeps smaller keys in the left subtree and larger keys in the right, so lookup follows one root to leaf route rather than scanning everything.
Tree traversal
A systematic visit of every vertex of a rooted tree. Preorder handles a vertex before its subtrees, inorder between them, and postorder after both.
Spanning tree
A subgraph that is a tree and includes every vertex of a connected graph. Every connected graph has at least one, and searching the graph produces one automatically.
Minimum spanning tree
A spanning tree of a weighted graph whose total edge weight is as small as possible. Greedy choices succeed here, which is unusual among optimisation problems.
Kruskal algorithm
A greedy method that sorts edges by weight and adds each one unless it would close a cycle, using a disjoint set structure to detect that condition quickly.
Prim algorithm
A greedy method that grows a single tree from a starting vertex, repeatedly attaching the cheapest edge leaving the current tree, which suits dense graphs with a priority queue.
Breadth first search
A traversal exploring all vertices at one distance before moving further out, using a queue. On unweighted graphs it yields shortest paths from the start vertex.
Depth first search
A traversal following one route as far as possible before backtracking, using a stack or recursion. It underlies cycle detection and topological ordering.
Topological ordering
A linear arrangement of the vertices of a directed acyclic graph placing every edge's tail before its head. Such an ordering exists exactly when there are no directed cycles.
Huffman coding
A greedy construction of an optimal prefix free binary code that repeatedly merges the two least frequent symbols, giving shorter codes to more frequent symbols.
Recurrence relation
An equation defining each term of a sequence using earlier terms, together with enough initial values to pin the sequence down uniquely.
Initial conditions
The explicitly given starting terms of a recursively defined sequence. Without them a recurrence describes a whole family of sequences rather than one.
Linear homogeneous recurrence
A recurrence in which each term is a fixed linear combination of a fixed number of previous terms with no extra additive function attached.
Characteristic equation
The polynomial obtained by substituting a geometric trial solution into a linear homogeneous recurrence. Its roots build the general closed form, with repeated roots needing polynomial factors.
Fibonacci recurrence
The rule that each term is the sum of the two before it, with two given starting values. Its characteristic roots involve the golden ratio, which governs its growth rate.
Divide and conquer recurrence
A recurrence describing an algorithm that splits a problem into subproblems of a fraction of the size, solves them, and combines the results with additional work.
Master theorem
A rule giving the growth rate of a divide and conquer recurrence by comparing the combining work with the number of subproblems raised to the appropriate root. It requires a regular split and a well behaved combining cost.
Big O notation
An upper bound on growth rate, saying a function is eventually at most a constant multiple of another. Big Omega gives a lower bound and Big Theta gives a matched bound.
Complexity classes P and NP
P holds problems solvable in polynomial time and NP holds those whose proposed solutions can be checked in polynomial time. Whether the two are equal remains unresolved.