decision trees

From the work of some sorting algorithms, we can derive a decision tree.  A decision tree can be visualized as nodes for each comparison and left and right sub-trees for yes or no choices. Each execution of an algorithm gives a downward path in the tree. Worst-case time is lower-bounded by longest downward path (height) in this binary tree. A tree of height h has at most 2h leaves. If a tree has L leaves, then its height is at least log L.

Greedy algorithms have no general recipe. In general, greedy algorithms assume that there is an objective function f(x1, x2, …, xn) to optimize ( say maximize) that depends on some choices. Second, there is a way to estimate the contribution of each choice to the final value but without taking into account how our choices will constrain later choices. Finally, the algorithm is greedy if it still makes the choice with the best contribution. Greedy algorithm is frequently not the best choice but sometimes it is.

There are cases of algorithm problems when nothing is better than trying out all possibilities. This is especially helpful when the number of possibilities is bounded. For example we can use exhaustive search to find elements of a maximum independent set in a graph. A maximum independent set is one in which no two vertices have a connecting edge. Independent set is NP-complete.

Courtesy study material  uploaded by Peter Gacs, Boston university.