Brief Definition Dynamic programming refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using dynamic programming. The main idea is to store the results of sub-problems to avoid re-computing. How to Solve Decide State A state can be uniquely defined by a set of parameters Define Transition »
Definition and Glossary Strings are everywhere. Text information always requires string process. A String is a sequence of characters. String Sort LSD key-indexed counting, from right to left MSD recursive method, left to right Three-way string quicksort adapt quicksort to MSD string sorting by using 3-way partitioning on the leading character of the keys, moving to the next character on only the middle subarray Tries A search tree, composed of nodes that contain links that are either null or references to other nodes. »
Definition and Glossary A graph is a set of vertices and a collection of edges that each connect a pair of vertices. A path in a graph is a sequence of vertices connected by edges. A graph is connected if there is a path from every vertex to every other vertex in the graph. A cycle is a path with at least one edge whose first and last vertices are the same. »
General Definition of Trees A tree consists of a set of nodes and a set of edges that connect pairs of nodes. A tree is either empty or consists of a root and zero or more subtrees, each of which is also a tree. # Binary Tree Illustration class Tree: def __init__(self, value): self.key = value self.left = None self.right = None Tree Traversals Preorder Visit the root node first, then recursively do a preorder traversal of the left subtree, followed by a recursive preorder traversal of the right subtree. »