Algorithm Design techniques

Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the
next piece that offers the most obvious and immediate benefit. So the problems where choosing
locally optimal also leads to global solution are best fit for Greedy.

Our first example to illustrate greedy algorithms is a scheduling problem called interval
scheduling. The idea is we have a collection of jobs (tasks) to schedule on some machine, and
each job j has a given start time sj and a given finish time fj . If two jobs overlap, we can‟t
schedule them both. Our goal is to schedule as many jobs as possible on our machine.
Example: Suppose the jobs are the following 5 intervals: [1, 3], [2, 4], [3, 5], [4, 6], [5, 7].
Then, best is to schedule the three jobs [1, 3], [3, 5], [5, 7]. Any other solution will schedule
at most two jobs. Let‟s now consider several greedy algorithms that do not work. Let‟s see if
we can find counterexamples for each. For terminology, let‟s call a job a “candidate job” if it
has not yet been scheduled and does not conflict with any already-scheduled job. Algorithms
that do not work: Starting from the empty schedule, so long as at least one candidate job
exists,

• Always add in the shortest candidate job.

• Always add in the candidate job with the earliest start time.

• Always add in the candidate job with the fewest conflicts with other candidate jobs. Now,
let‟s give an algorithm that works, and prove correctness for it. 1 An algorithm that works:
Starting from the empty schedule, so long as at least one candidate job exists,

• Always add in the candidate job with the earliest finish time

Huffman codes:

Huffman coding is a form of data compression used to send text more compactly. The high-
level idea is the following. Suppose that you have an alphabet with some number of
characters, and your text consists of sequences of letters from that alphabet. For instance,
let‟s imagine we have 128 characters, like ASCII. We could use 7 bits to encode each one,
since 27 = 128. However, if some characters are used more frequently than others, we might
1
be better off with an encoding that uses fewer bits for the frequent characters and more bits
for the less frequent characters. This could give us a savings overall. One important technical
point when we go to encodings that use a different number of bits per character is we want
our encoding to be prefix-free. This means that no character can have an encoding that is a
prefix of some other character‟s encoding. E.g., if we use 010 for the letter “a”, then we can‟t
use 01 for the letter “b”: otherwise, we wouldn‟t know when one letter ends and the next one
begins. One way to think of prefix-free encodings is that we are viewing our characters as
leaves in a binary tree, where each edge is labeled by a 0 or a 1. Let‟s say that from any
internal node, the left branch is 0 and the right branch is 1. For example, suppose we have
four letters, “a”, “b”, “c”, and “d”. We could use a balanced binary tree with 00 for “a”, 01
for “b”, 10 for “c”, and 11 for “d” or an unbalanced tree, say 0 for “a”, 10 for “b”, 110 for
“c”, and 111 for “d”. This would be a savings if “a” is very common – more common than
“c” and “d” combined.

Suppose we know the frequency of every letter in our alphabet. That is, in a sequence σ of
characters, we know the fraction fi of them that will be letter i (where f1 + f2 + ... = 1). What
tree will minimize the total number of bits needed to encode σ? This is a Huffman code.
Huffman code problem: • Given: frequencies fi for each letter i in the alphabet. • Goal: output
the tree that minimizes the number of bits needed to encode a string in which letters appear in
proportion to their given frequencies. Building up intuition: Suppose we have fi > fj , what
does this tell us about where letters i and j are in the optimal tree? Can it be the case that i is
strictly deeper in the tree than j? No. Why not? (Could just swap them). Can the optimal tree
have just a single deepest leaf? No. Why not? If there was, you could move it up to its parent
and have a better tree. In fact, this reasoning also tells us that every leaf at the bottom level of
the tree must have a sibling leaf. Claim: consider two sibling leaves at the bottom level of an
optimal tree. We may assume without loss of generality that they contain the two least
frequent letters.

Huffman code algorithm.

Given frequencies f1, ..., fn for the n letters in our alphabet:

• Find the two least-frequent letters i and j.

• Replace i and j with a single letter ij of frequency fij = fi + fj .

2
• Recursively solve the new problem, obtaining a tree Tn−1.

• Replace the leaf in Tn−1 containing ij with an internal node whose children are leaves
containing i and j.

Example: Suppose we have five letters a,b,c,d,e with frequencies fa = 0.45, fb = 0.20, fc =
0.15, fd = 0.1, fe = 0.1. The algorithm will first merge d and e, replacing them with de of
frequncy fde = 0.2. We now enter our recursive call, and merge c with either b or de – let‟s
say we merge c with b, replacing them with bc of frequency fbc = 0.35. Next we merge bc
with de, replacing them with bcde of frequency fbcde = 0.55. Finally, we merge a with bcde
and are done. The tree in the end looks like this: * / \ a * / \ * * / \ / \ b c d e 3 At this point we
need to answer two questions: (1) does this really find the best tree, and (2) how much time
does the algorithm take? That is, is it correct and what is its running time? Let‟s look at
running time first and then analyze correctness (usually you want to do this in the other order,
since running time isn‟t so important if the algorithm doesn‟t give you the right answer but
it‟s easier to consider running time first here).

Divide And Conquer

This technique can be divided into the following three parts:
1. Divide: This involves dividing the problem into some sub problem.
2. Conquer: Sub problem by calling recursively until sub problem solved.
3. Combine: The Sub problem Solved so that we will get find problem solution.

The following are some standard algorithms that follows Divide and Conquer algorithm.

1. Binary Search is a searching algorithm. In each step, the algorithm compares the
input element x with the value of the middle element in array. If the values match,
return the index of the middle. Otherwise, if x is less than the middle element, then the
algorithm recurs for left side of middle element, else recurs for the right side of the
middle element.
2. Quicksort is a sorting algorithm. The algorithm picks a pivot element, rearranges the
array elements in such a way that all elements smaller than the picked pivot element
move to left side of pivot, and all greater elements move to right side. Finally, the
algorithm recursively sorts the subarrays on left and right of pivot element.

3
 3. Merge Sort is also a sorting algorithm. The algorithm divides the array in two halves,
recursively sorts them and finally merges the two sorted halves.
4. Closest Pair of Points The problem is to find the closest pair of points in a set of
points in x-y plane. The problem can be solved in O(n^2) time by calculating distances
of every pair of points and comparing the distances to find the minimum. The Divide
and Conquer algorithm solves the problem in O(nLogn) time.
5. Strassen’s Algorithm is an efficient algorithm to multiply two matrices. A simple
method to multiply two matrices need 3 nested loops and is O(n^3). Strassen‟s
algorithm multiplies two matrices in O(n^2.8974) time.
6. Cooley–Tukey Fast Fourier Transform (FFT) algorithm is the most common
algorithm for FFT. It is a divide and conquer algorithm which works in O(nlogn) time.
7. Karatsuba algorithm for fast multiplication it does multiplication of two n-digit
numbers in at most
The general formula of divide and conquer is:

Closest Pair of Points using Divide and Conquer algorithm

We are given an array of n points in the plane, and the problem is to find out the closest pair of
points in the array. This problem arises in a number of applications. For example, in air-traffic
control, you may want to monitor planes that come too close together, since this may indicate a
possible collision. Recall the following formula for distance between two points p and q.

The Brute force solution is O(n^2), compute the distance between each pair and return the
smallest. We can calculate the smallest distance in O(nLogn) time using Divide and Conquer
strategy. In this post, a O(n x (Logn)^2) approach is discussed. We will be discussing a
O(nLogn) approach in a separate post.

Algorithm
Following are the detailed steps of a O(n (Logn)^2) algortihm.
Input: An array of n points P[]
Output: The smallest distance between two points in the given array.
As a pre-processing step, the input array is sorted according to x coordinates.

4
1) Find the middle point in the sorted array, we can take P[n/2] as middle point.
2) Divide the given array in two halves. The first subarray contains points from P[0] to P[n/2].
The second subarray contains points from P[n/2+1] to P[n-1].
3) Recursively find the smallest distances in both subarrays. Let the distances be dl and dr. Find
the minimum of dl and dr. Let the minimum be d.

4) From the above 3 steps, we have an upper bound d of minimum distance. Now we need to
consider the pairs such that one point in pair is from the left half and the other is from the right
half. Consider the vertical line passing through P[n/2] and find all points whose x coordinate is
closer than d to the middle vertical line. Build an array strip[] of all such points.
Backtracking is an algorithmic-technique for solving problems recursively by trying to build a
solution incrementally, one piece at a time, removing those solutions that fail to satisfy the
constraints of the problem at any point of time (by time, here, is referred to the time elapsed till
reaching any level of the search tree).

Backtracking can be defined as a general algorithmic technique that considers searching every
possible combination in order to solve a computational problem.

There are three types of problems in backtracking –

5
 1. Decision Problem – In this, we search for a feasible solution.
2. Optimization Problem – In this, we search for the best solution.
3. Enumeration Problem – In this, we find all feasible solutions.

How to determine if a problem can be solved using Backtracking?

Generally, every constraint satisfaction problem which has clear and well-defined constraints
on any objective solution, that incrementally builds candidate to the solution and abandons a
candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be
completed to a valid solution, can be solved by Backtracking. However, most of the problems
that are discussed, can be solved using other known algorithms like Dynamic
Programming or Greedy Algorithms in logarithmic, linear, linear-logarithmic time complexity
in order of input size, and therefore, outshine the backtracking algorithm in every respect (since
backtracking algorithms are generally exponential in both time and space). However, a few
problems still remain, that only have backtracking algorithms to solve them until now.
Consider a situation that you have three boxes in front of you and only one of them has a gold
coin in it but you do not know which one. So, in order to get the coin, you will have to open all
of the boxes one by one. You will first check the first box, if it does not contain the coin, you
will have to close it and check the second box and so on until you find the coin. This is what
backtracking is, that is solving all sub-problems one by one in order to reach the best possible
solution.

Consider the below example to understand the Backtracking approach more formally,

Given an instance of any computational problem and data corresponding to the

instance, all the constraints that need to be satisfied in order to solve the problem are

represented by . A backtracking algorithm will then work as follows:

The Algorithm begins to build up a solution, starting with an empty solution set . S = {}

1. Add to the first move that is still left (All possible moves are added to one by
one). This now creates a new sub-tree in the search tree of the algorithm.

2. Check if satisfies each of the constraints in .

 If Yes, then the sub-tree is “eligible” to add more “children”.
6
  Else, the entire sub-tree is useless, so recurs back to step 1 using

argument .
3. In the event of “eligibility” of the newly formed sub-tree , recurs back to step 1,

using argument .

4. If the check for returns that it is a solution for the entire data . Output
and terminate the program.
If not, then return that no solution is possible with the current and hence discard it.
Pseudo Code for Backtracking :
1. Recursive backtracking solution.
2. void findSolutions(n, other params) :

3. if (found a solution) :

4. solutionsFound = solutionsFound + 1;

5. displaySolution();

6. if (solutionsFound >= solutionTarget) :

7. [Link](0);

8. return

9.

10. for (val = first to last) :

11. if (isValid(val, n)) :

12. applyValue(val, n);

13. findSolutions(n+1, other params);

14. removeValue(val, n);

15. Finding whether a solution exists or not

16. boolean findSolutions(n, other params) :

17. if (found a solution) :

18. displaySolution();

7
 19. return true;

20.

21. for (val = first to last) :

22. if (isValid(val, n)) :

23. applyValue(val, n);

24. if (findSolutions(n+1, other params))

25. return true;

26. removeValue(val, n);

27. return false;

Let us try to solve a standard Backtracking problem, N-Queen Problem.

The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two
queens attack each other. For example, following is a solution for 4 Queen problem.

The expected output is a binary matrix which has 1s for the blocks where queens are placed.
For example, following is the output matrix for the above 4 queen solution.

{ 0, 1, 0, 0}

{ 0, 0, 0, 1}

{ 1, 0, 0, 0}

{ 0, 0, 1, 0}

8
Backtracking Algorithm: The idea is to place queens one by one in different columns, starting
from the leftmost column. When we place a queen in a column, we check for clashes with
already placed queens. In the current column, if we find a row for which there is no clash, we
mark this row and column as part of the solution. If we do not find such a row due to clashes
then we backtrack and return false.
1) Start in the leftmost column

2) If all queens are placed

return true

3) Try all rows in the current column. Do following for every tried row.

a) If the queen can be placed safely in this row then mark this [row,

column] as part of the solution and recursively check if placing

queen here leads to a solution.

b) If placing the queen in [row, column] leads to a solution then return

true.

c) If placing queen doesn't lead to a solution then unmark this [row,

column] (Backtrack) and go to step (a) to try other rows.

3) If all rows have been tried and nothing worked, return false to trigger

backtracking.

You may refer to the article on Backtracking | Set 3 (N Queen Problem) for complete
implementation of the above approach.
More Backtracking Problems:
 Backtracking | Set 1 (The Knight‟s tour problem)
 Backtracking | Set 2 (Rat in a Maze)
 Backtracking | Set 4 (Subset Sum)
 Backtracking | Set 5 (m Coloring Problem)
 –> Click Here for More

9
5) Sort the array strip[] according to y coordinates. This step is O(nLogn). It can be optimized
to O(n) by recursively sorting and merging.
6) Find the smallest distance in strip[]. This is tricky. From the first look, it seems to be a
O(n^2) step, but it is actually O(n). It can be proved geometrically that for every point in the
strip, we only need to check at most 7 points after it (note that strip is sorted according to Y
coordinate). See this for more analysis.

7) Finally return the minimum of d and distance calculated in the above step (step 6)

Dynamic Programming

Matrix Chain Multiplication

Given a sequence of matrices, find the most efficient way to multiply these matrices together.
The problem is not actually to perform the multiplications, but merely to decide in which order
to perform the [Link] have many options to multiply a chain of matrices because
matrix multiplication is associative. In other words, no matter how we parenthesize the product,
the result will be the same. For example, if we had four matrices A, B, C, and D, we would
have:

10
(ABC)D = (AB)(CD) = A(BCD) = ....

However, the order in which we parenthesize the product affects the number of simple
arithmetic operations needed to compute the product, or the efficiency. For example, suppose A
is a 10 × 30 matrix, B is a 30 × 5 matrix, and C is a 5 × 60 matrix. Then,

(AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations

A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.

Clearly the first parenthesization requires less number of operations.

Given an array p[] which represents the chain of matrices such that the ith matrix Ai is of
dimension p[i-1] x p[i]. We need to write a function MatrixChainOrder() that should return the
minimum number of multiplications needed to multiply the chain.

Input: p[] = {40, 20, 30, 10, 30}

Output: 26000
There are 4 matrices of dimensions 40x20, 20x30, 30x10 and 10x30. Let the input 4 matrices
be A, B, C and D. The minimum number of multiplications are obtained by putting
parenthesis in following way
(A(BC))D --> 20*30*10 + 40*20*10 + 40*10*30

Input: p[] = {10, 20, 30, 40, 30}

Output: 30000
There are 4 matrices of dimensions 10x20, 20x30, 30x40 and 40x30.
Let the input 4 matrices be A, B, C and D. The minimum number of
multiplications are obtained by putting parenthesis in following way
((AB)C)D --> 10*20*30 + 10*30*40 + 10*40*30

Input: p[] = {10, 20, 30}

Output: 6000
There are only two matrices of dimensions 10x20 and 20x30. So there is only one way to
multiply the matrices, cost of which is 10*20*30

11
 1) Optimal Substructure:

A simple solution is to place parenthesis at all possible places, calculate the cost for each
placement and return the minimum value. In a chain of matrices of size n, we can place the first
set of parenthesis in n-1 ways. For example, if the given chain is of 4 matrices. let the chain be
ABCD, then there are 3 ways to place first set of parenthesis outer side: (A)(BCD), (AB)(CD)
and (ABC)(D). So when we place a set of parenthesis, we divide the problem into subproblems
of smaller size. Therefore, the problem has optimal substructure property and can be easily
solved using recursion.
Minimum number of multiplication needed to multiply a chain of size n = Minimum of all n-1
placements (these placements create subproblems of smaller size)

2) Overlapping Subproblems

Following is a recursive implementation that simply follows the above optimal substructure
property.

/* A naive recursive implementation that simply

follows the above optimal substructure property */
#include <limits.h>
#include <stdio.h>

// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n

int MatrixChainOrder(int p[], int i, int j)
{
if (i == j)
return 0;
int k;
int min = INT_MAX;
int count;

12
 // place parenthesis at different places between first
// and last matrix, recursively calculate count of
// multiplications for each parenthesis placement and
// return the minimum count
for (k = i; k < j; k++)
{
count = MatrixChainOrder(p, i, k)
+ MatrixChainOrder(p, k + 1, j)
+ p[i - 1] * p[k] * p[j];

if (count < min)

min = count;
}

// Return minimum count

return min;
}

// Driver code
int main()
{
int arr[] = { 1, 2, 3, 4, 3 };
int n = sizeof(arr) / sizeof(arr[0]);

printf("Minimum number of multiplications is %d ",

MatrixChainOrder(arr, 1, n - 1));

getchar();
return 0;
}
Output
Minimum number of multiplications is 30
13
The time complexity of the above naive recursive approach is exponential. It should be noted
that the above function computes the same subproblems again and again. See the following
recursion tree for a matrix chain of size 4. The function MatrixChainOrder(p, 3, 4) is called two
times. We can see that there are many subproblems being called more than once.

Since same suproblems are called again, this problem has Overlapping Subprolems property.
So Matrix Chain Multiplication problem has both properties (see this and this) of a dynamic
programming problem. Like other typical Dynamic Programming(DP) problems,
recomputations of same subproblems can be avoided by constructing a temporary array m[][] in
bottom up manner.

Dynamic Programming Solution

Following is the implementation of the Matrix Chain Multiplication problem using Dynamic
Programming
// C++ program using memoization
#include <bits/stdc++.h>
using namespace std;
int dp[100][100];

14
// Function for matrix chain multiplication
int matrixChainMemoised(int* p, int i, int j)
{
if (i == j)
{
return 0;
}
if (dp[i][j] != -1)
{
return dp[i][j];
}
dp[i][j] = INT_MAX;
for (int k = i; k < j; k++)
{
dp[i][j] = min(
dp[i][j], matrixChainMemoised(p, i, k)
+ matrixChainMemoised(p, k + 1, j)
+ p[i - 1] * p[k] * p[j]);
}
return dp[i][j];
}
int MatrixChainOrder(int* p, int n)
{
int i = 1, j = n - 1;
return matrixChainMemoised(p, i, j);
}

// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
15
 memset(dp, -1, sizeof dp);

cout << "Minimum number of multiplications is "

<< MatrixChainOrder(arr, n);
}

Output
Minimum number of multiplications is 18

#include <limits.h>
#include <stdio.h>

// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n

int MatrixChainOrder(int p[], int n)
{

/* For simplicity of the program,

one extra row and one
extra column are allocated in m[][].
0th row and 0th
column of m[][] are not used */
int m[n][n];

int i, j, k, L, q;

/* m[i, j] = Minimum number of

scalar multiplications
needed to compute the matrix
A[i]A[i+1]...A[j] =
A[i..j] where dimension of A[i]
is p[i-1] x p[i] */

// cost is zero when multiplying one matrix.

16
 for (i = 1; i < n; i++)
m[i][i] = 0;

// L is chain length.
for (L = 2; L < n; L++) {
for (i = 1; i < n - L + 1; i++)
{
j = i + L - 1;
m[i][j] = INT_MAX;
for (k = i; k <= j - 1; k++)
{
// q = cost/scalar multiplications
q = m[i][k] + m[k + 1][j]
+ p[i - 1] * p[k] * p[j];
if (q < m[i][j])
m[i][j] = q;
}
}
}

return m[1][n - 1];

}

// Driver code
int main()
{
int arr[] = { 1, 2, 3, 4 };
int size = sizeof(arr) / sizeof(arr[0]);

printf("Minimum number of multiplications is %d ",

MatrixChainOrder(arr, size));

getchar();
17
 return 0;
}
Output
Minimum number of multiplications is 18

Time Complexity: O(n3 )

Auxiliary Space: O(n2)

Matrix Chain Multiplication (A O(N^2) Solution)

Optimal Binary Search Tree

Given a sorted array keys[0.. n-1] of search keys and an array freq[0.. n-1] of frequency counts,
where freq[i] is the number of searches to keys[i]. Construct a binary search tree of all keys
such that the total cost of all the searches is as small as possible.
Let us first define the cost of a BST. The cost of a BST node is level of that node multiplied by
its frequency. Level of root is 1.

Examples:
Input: keys[] = {10, 12}, freq[] = {34, 50}

There can be following two possible BSTs

10 12

\ /

12 10

I II

Frequency of searches of 10 and 12 are 34 and 50 respectively.

The cost of tree I is 34*1 + 50*2 = 134

The cost of tree II is 50*1 + 34*2 = 118

18
Input: keys[] = {10, 12, 20}, freq[] = {34, 8, 50}

There can be following possible BSTs

10 12 20 10 20

\ / \ / \ /

12 10 20 12 20 10

\ / / \

20 10 12 12

I II III IV V

Among all possible BSTs, cost of the fifth BST is minimum.

Cost of the fifth BST is 1*50 + 2*34 + 3*8 = 142

1) Optimal Substructure:
The optimal cost for freq[i..j] can be recursively calculated using following formula.
We need to calculate optCost(0, n-1) to find the result. The idea of above formula is simple, we
one by one try all nodes as root (r varies from i to j in second term). When we make rth node as
root, we recursively calculate optimal cost from i to r-1 and r+1 to j. We add sum of
frequencies from i to j (see first term in the above formula), this is added because every search
will go through root and one comparison will be done for every search.
2) Overlapping Subproblems

// A naive recursive implementation of optimal binary

// search tree problem

#include <stdio.h>

#include <limits.h>

// A utility function to get sum of array elements

19
// freq[i] to freq[j]

int sum(int freq[], int i, int j);

// A recursive function to calculate cost of optimal

// binary search tree

int optCost(int freq[], int i, int j)

// Base cases

if (j < i) // no elements in this subarray

return 0;

if (j == i) // one element in this subarray

return freq[i];

// Get sum of freq[i], freq[i+1], ... freq[j]

int fsum = sum(freq, i, j);

// Initialize minimum value

int min = INT_MAX;

// One by one consider all elements as root and

// recursively find cost of the BST, compare the

// cost with min and update min if needed

20
 for (int r = i; r <= j; ++r)

int cost = optCost(freq, i, r-1) +

optCost(freq, r+1, j);

if (cost < min)

min = cost;

// Return minimum value

return min + fsum;

// The main function that calculates minimum cost of

// a Binary Search Tree. It mainly uses optCost() to

// find the optimal cost.

int optimalSearchTree(int keys[], int freq[], int n)

// Here array keys[] is assumed to be sorted in

// increasing order. If keys[] is not sorted, then

// add code to sort keys, and rearrange freq[]

// accordingly.

return optCost(freq, 0, n-1);

21
}

// A utility function to get sum of array elements

// freq[i] to freq[j]

int sum(int freq[], int i, int j)

int s = 0;

for (int k = i; k <=j; k++)

s += freq[k];

return s;

// Driver program to test above functions

int main()

int keys[] = {10, 12, 20};

int freq[] = {34, 8, 50};

int n = sizeof(keys)/sizeof(keys[0]);

printf("Cost of Optimal BST is %d ",

optimalSearchTree(keys, freq, n));

return 0;

22
Output:

Cost of Optimal BST is 142

Time complexity of the above naive recursive approach is exponential. It should be noted that
the above function computes the same subproblems again and again. We can see many
subproblems being repeated in the following recursion tree for freq[1..4].

Since same suproblems are called again, this problem has Overlapping Subprolems property.
So optimal BST problem has both properties (see this and this) of a dynamic programming
problem. Like other typical Dynamic Programming(DP) problems, recomputations of same
subproblems can be avoided by constructing a temporary array cost[][] in bottom up manner.

Dynamic Programming Solution

Following is C/C++ implementation for optimal BST problem using Dynamic Programming.
We use an auxiliary array cost[n][n] to store the solutions of subproblems. cost[0][n-1] will
hold the final result. The challenge in implementation is, all diagonal values must be filled first,
then the values which lie on the line just above the diagonal. In other words, we must first fill
all cost[i][i] values, then all cost[i][i+1] values, then all cost[i][i+2] values. So how to fill the
2D array in such manner> The idea used in the implementation is same as Matrix Chain
Multiplication problem, we use a variable „L‟ for chain length and increment „L‟, one by one.
We calculate column number „j‟ using the values of „i‟ and „L‟.

23
// Dynamic Programming code for Optimal Binary Search

// Tree Problem

#include <stdio.h>

#include <limits.h>

// A utility function to get sum of array elements

// freq[i] to freq[j]

int sum(int freq[], int i, int j);

/* A Dynamic Programming based function that calculates

minimum cost of a Binary Search Tree. */

int optimalSearchTree(int keys[], int freq[], int n)

/* Create an auxiliary 2D matrix to store results

of subproblems */

int cost[n][n];

/* cost[i][j] = Optimal cost of binary search tree

that can be formed from keys[i] to keys[j].

cost[0][n-1] will store the resultant cost */

// For a single key, cost is equal to frequency of the key

24
for (int i = 0; i < n; i++)

cost[i][i] = freq[i];

// Now we need to consider chains of length 2, 3, ... .

// L is chain length.

for (int L=2; L<=n; L++)

// i is row number in cost[][]

for (int i=0; i<=n-L+1; i++)

// Get column number j from row number i and

// chain length L

int j = i+L-1;

cost[i][j] = INT_MAX;

// Try making all keys in interval keys[i..j] as root

for (int r=i; r<=j; r++)

// c = cost when keys[r] becomes root of this subtree

int c = ((r > i)? cost[i][r-1]:0) +

((r < j)? cost[r+1][j]:0) +

sum(freq, i, j);

25
 if (c < cost[i][j])

cost[i][j] = c;

return cost[0][n-1];

// A utility function to get sum of array elements

// freq[i] to freq[j]

int sum(int freq[], int i, int j)

int s = 0;

for (int k = i; k <=j; k++)

s += freq[k];

return s;

// Driver program to test above functions

int main()

int keys[] = {10, 12, 20};

26
 int freq[] = {34, 8, 50};

int n = sizeof(keys)/sizeof(keys[0]);

printf("Cost of Optimal BST is %d ",

optimalSearchTree(keys, freq, n));

return 0;

Output:

Cost of Optimal BST is 142

Notes
1) The time complexity of the above solution is O(n^4). The time complexity can be easily
reduced to O(n^3) by pre-calculating sum of frequencies instead of calling sum() again and
again.
2) In the above solutions, we have computed optimal cost only. The solutions can be easily
modified to store the structure of BSTs also. We can create another auxiliary array of size n to
store the structure of tree. All we need to do is, store the chosen „r‟ in the innermost loop.

All Pairs Shortest Path problem

The Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem. The problem
is to find shortest distances between every pair of vertices in a given edge weighted directed
Graph.
Example:
Input:
graph[][] = { {0, 5, INF, 10},
{INF, 0, 3, INF},
{INF, INF, 0, 1},
{INF, INF, INF, 0} }

27
which represents the following graph
10
(0)------->(3)
| /|\
5| |
| |1
\|/ |
(1)------->(2)
3
Note that the value of graph[i][j] is 0 if i is equal to j
And graph[i][j] is INF (infinite) if there is no edge from vertex i to j.

Output:
Shortest distance matrix
0 5 8 9
INF 0 3 4
INF INF 0 1
INF INF INF 0
Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.

Floyd Warshall Algorithm

We initialize the solution matrix same as the input graph matrix as a first step. Then we update
the solution matrix by considering all vertices as an intermediate vertex. The idea is to one by
one pick all vertices and updates all shortest paths which include the picked vertex as an
intermediate vertex in the shortest path. When we pick vertex number k as an intermediate
vertex, we already have considered vertices {0, 1, 2, .. k-1} as intermediate vertices. For every
pair (i, j) of the source and destination vertices respectively, there are two possible cases.
1) k is not an intermediate vertex in shortest path from i to j. We keep the value of dist[i][j] as it
is.

28
2) k is an intermediate vertex in shortest path from i to j. We update the value of dist[i][j] as
dist[i][k] + dist[k][j] if dist[i][j] > dist[i][k] + dist[k][j]
The following figure shows the above optimal substructure property in the all-pairs shortest
path problem.

// C Program for Floyd Warshall Algorithm

#include<stdio.h>

// Number of vertices in the graph

#define V 4

/* Define Infinite as a large enough value. This value will be used

for vertices not connected to each other */

#define INF 99999

29
// A function to print the solution matrix

void printSolution(int dist[][V]);

// Solves the all-pairs shortest path problem using Floyd Warshall algorithm

void floydWarshall (int graph[][V])

/* dist[][] will be the output matrix that will finally have the shortest

distances between every pair of vertices */

int dist[V][V], i, j, k;

/* Initialize the solution matrix same as input graph matrix. Or

we can say the initial values of shortest distances are based

on shortest paths considering no intermediate vertex. */

for (i = 0; i < V; i++)

for (j = 0; j < V; j++)

dist[i][j] = graph[i][j];

/* Add all vertices one by one to the set of intermediate vertices.

---> Before start of an iteration, we have shortest distances between all

pairs of vertices such that the shortest distances consider only the

vertices in set {0, 1, 2, .. k-1} as intermediate vertices.

----> After the end of an iteration, vertex no. k is added to the set of

30
 intermediate vertices and the set becomes {0, 1, 2, .. k} */

for (k = 0; k < V; k++)

// Pick all vertices as source one by one

for (i = 0; i < V; i++)

// Pick all vertices as destination for the

// above picked source

for (j = 0; j < V; j++)

// If vertex k is on the shortest path from

// i to j, then update the value of dist[i][j]

if (dist[i][k] + dist[k][j] < dist[i][j])

dist[i][j] = dist[i][k] + dist[k][j];

// Print the shortest distance matrix

printSolution(dist);

31
/* A utility function to print solution */

void printSolution(int dist[][V])

printf ("The following matrix shows the shortest distances"

" between every pair of vertices \n");

for (int i = 0; i < V; i++)

for (int j = 0; j < V; j++)

if (dist[i][j] == INF)

printf("%7s", "INF");

else

printf ("%7d", dist[i][j]);

printf("\n");

// driver program to test above function

int main()

/* Let us create the following weighted graph

32
 10

(0)------->(3)

| /|\

5| |

| |1

\|/ |

(1)------->(2)

3 */

int graph[V][V] = { {0, 5, INF, 10},

{INF, 0, 3, INF},

{INF, INF, 0, 1},

{INF, INF, INF, 0}

};

// Print the solution

floydWarshall(graph);

return 0;

Output:
Following matrix shows the shortest distances between every pair of vertices

0 5 8 9

INF 0 3 4

INF INF 0 1

33
 INF INF INF 0

Time Complexity: O(V^3)

The above program only prints the shortest distances. We can modify the solution to print the
shortest paths also by storing the predecessor information in a separate 2D matrix.
Also, the value of INF can be taken as INT_MAX from limits.h to make sure that we handle
maximum possible value. When we take INF as INT_MAX, we need to change the if condition
in the above program to avoid arithmetic overflow.

#include

#define INF INT_MAX

..........................

if ( dist[i][k] != INF &&

dist[k][j] != INF &&

dist[i][k] + dist[k][j] < dist[i][j]

dist[i][j] = dist[i][k] + dist[k][j];

...........................

34