We will investigate two different greedy algorithms for minimum spanning trees, Prim’s algorithm and Kruskal’s algorithm. Each uses a different locally optimal property. 프림 알고리즘 대신 크러스컬 알고리즘을 이용해도 최소
Consider 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 i
A simple example illustrates the greedy approach. Joe, the sales clerk, often encounters the problem of giving change for a purchase. Customers usually don’t want to receive a lot of coins. For exampl
Charles 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
Our goal is to organize the keys in a binary search tree so that the average time it takes to locate a key is minimized. In general, we cannot find an optimal binary search tree by considering all bin
Consider the multiplication of the following four matrices. $$A \quad\times\quad B \quad\times\quad C \quad\times\quad D \\(20\times2) \ (2\times30) \ (30\times12) \ (12\times8)$$ A(B(CD)) (30×12×8)
The principle of optimality is said to apply in a problem if an optimal solution to an instance of a problem always contains optimal solutions to all substances. If the principle of optimality applies
A common problem encountered by air travelers is the determination of the shortest way to fly from one city to another when a direct flight does not exist. Next we develop an algorithm that solves thi
$$\begin{align}{n \choose k} &= \frac{n!}{k!(n-k)!} \quad for \ 0 \leq k \leq n&. \\{n \choose k} &=\begin{cases} {n-1 \choose k-1} + {n-1 \choose k} &\text{0 < $k$ < $n$} \\
The divide and conquer algorithm works in problems such as Mergesort, where the smaller instances are unrelated. However, in problems such as nth Fibonacci term, the smaller instances are related. For