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
If possible, we should avoid divide-and-conquer in the following two cases: An instance of size n is divided into or more instances each almost of size n. // n th Fibonacci Term (Recursive)fib(n) = f
Quicksort 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 partitione
A 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. Example The steps