Basic ConceptConsider the problem of removing edges from a connected, weighted, undirected graph G to form a subgraph such that all the vertices remain connected and the sum of the weights on the remaining edges is as small as possible. Such a problem has numerous applications.Road construction: want to connect a set of cities with a minimum amount of road.Telecommunications: want to use a minim..

Basic ConceptCharles Dicken’s classic character Ebenezer Scrooge may well be the most greedy person ever, fictional or real. Recall that Scrooge never considered the past or future. Each day his only drive was to greedily grab as much gold as he could. After the Ghost of Christmas Past reminded him of the past and the Ghost of Christmas Future warned him of the future, he changed his greedy ways..

Basic ConceptPrerequisite Knowledge: Binary Search Treebinary search tree: A binary tree of items (ordinarily called keys), that come from an ordered set, such thatEach node contain one key.The keys in the right subtree of a given node are greater than or equal to the key in that tree.The keys in the left subtree of a given node are less than or equal to the key in that tree.left subtree: For an..

Basic ConceptConsider the multiplication of the following four maxtrices. $$A \quad\times\quad B \quad\times\quad C \quad\times\quad D$$$$20\times 2 \qquad 2\times 30 \qquad 30\times 12 \qquad 12\times 8$$ There are five different orders in which we can multiply four matrices, each possibly resulting in a different number of elementary multiplications. The third order is the optimal order for m..

An Intuitive Introduction to OrderBelow table shows that eventually the quadratic term dominates this function. That is, the values of the other terms eventually become insignificant compared with the values of the quadratic term. Therefore, although the function is not a pure quadratic function, we can classify it with the pure quadratic functions. This means that if some algorithm has this tim..

Complexity AnalysisInput sizeFor many algorithms, it is easy to find a reasonable measure of the size of the input, which we call the input size. For Example consider Sequential Search, Add Array Members, Exchange Sort, and Binary Search. In all these algorithms, n, the number of items in the array, is a simple measure of the size of the input. Therefore, we can call n the input size. Example 배열..