Basic ConceptA 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 this and similar problems. First, let’s informally review some graph theory. Prerequisite Knowledge: Graph Theoryvertex, node: 정점edge, arc: 이음선directed graph, digraph: 방향 그래프weight: 가중치sim..

Basic ConceptThe binomial coefficient is given by$$ \begin{pmatrix}n\\k\end{pmatrix}=_nC_k=\frac{n!}{k!\left(n-k\right)!} \text{ for } 0 \le k\le n.$$ For values of n and k that are not small, we cannot compute the binomial coefficient directly from this definition because n! is very large even for moderate values of n. We can eliminate the need to compute n! or k! by using this recursive pro..

Basic ConceptThe 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. In problems where the smaller instances are related, a divide-and conquer algorithm often ends up repeatedly solving common instances, and the result is a very inefficient algorithm. Recal..

Basic ConceptQuicksort is similar to Mergesort in that the sort is accomplished by dividing the array into two partitions and then sorting each partition recursively. However, in quicksort, the array is partitioned by placing all items smaller than some pivot item before that item and all items larger than the pivot item after it. The pivot item can be any item, and for convenience we will simpl..

Basic ConceptA process related to sorting is merging. By two-way merging we mean combining two sorted arrays into one sorted array. By repeatedly applying the merging procedure, we sort an array. For example, to sort an array of 16 items, we can divide it into two subarrays, each of size 8, sort the two subarrays, and then merge them to produce the sorted array. In the same way, each subarray of..

Basic ConceptBinary Search locates a key x in a stored nondecreasing order array by first comparing x with the middle item of the array. If they are equal, the algorithm is done. If not, the array is divided into two subarrays, one containing all the items to the left of the middle item and the other containing all the items to the right. If x is smaller than the middle item, this procedure is t..