Algorithms Design

1. Divide and Conquer Algorithms

1.1. Essential Schematic

Given a function to compute on N inputs, the divide-and-conquer strategy suggests splitting
the inputs into k distinct subsets, 1<k<=N yielding k subproblems. These subproblems must
be solved and then a method must be found to combine subsolutions into a solution of the
whole.

1.2. Control Abstraction of Divide and Conquer Algorithms

Control abstraction refers to a procedure whose flow of control is clear but whose primary
operations are specified by other procedures whose precise meanings are left undefined.

V Pathak
1.3. Balancing
1.4. Min_Max Problem solution with Divide and Conquer

Divide and Conquer- Matrix Multiplication

X+Y N^2

AE+BG 2T(N/2)+ (N/2)^2

AF+BH 2T(N/2)+ (N/2)^2
CE+DG 2T(N/2)+ (N/2)^2
CF+DH 2T(N/2)+ (N/2)^2
Total = 8T(N/2)+ 4 (N/2)^2 =8T(N/2)+ N^2 = Theta(N^3)

V Pathak
V Pathak
Divide And conquer => Large Integers Multiplication

V Pathak
Divide And conquer => O(n) time Selection/ Finding k-th Smallest item/ Finding
Median [Ref: Cormen pg 220 ]

V Pathak
V Pathak
Transform (Divide) and conquer
The maximum-subarray problem – Cormen page 68

Transformation- Instead of looking at daily price, consider the day-wise change in price.

V Pathak
Divide and Conquer Solution

V Pathak
Time Complexity

V Pathak
DnC

V Pathak
In – Place Merge-Sort
Merge(A,l,m,u)
• Maintain two pointers which point to start of the segments which have to be
merged.
• Compare the elements at which the pointers are present.
• If element1 < element2 then element1 is at right position, simply
increase pointer1.
• Else shift all the elements between element1 and element2(including element1
but excluding element2) right by 1 and then place the element2 in the previous
place (i.e. before shifting right) of element1. Increment all the pointers by 1.

V Pathak
Time Complexity of above approach is O(n2) because merge is O(n 2). Time
complexity of standard merge sort is less, O(n Log n).

// C++ program in-place Merge Sort

#include <bits/stdc++.h>
using namespace std;

// Merges two subarrays of arr[].

// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
// Inplace Implementation
void merge(int arr[], int start, int mid, int end)
{
int start2 = mid + 1;

// If the direct merge is already sorted

if (arr[mid] <= arr[start2]) {
return;
}

// Two pointers to maintain start

// of both arrays to merge
while (start <= mid && start2 <= end) {

// If element 1 is in right place

if (arr[start] <= arr[start2]) {
start++;
}
else {
int value = arr[start2];
int index = start2;

// Shift all the elements between element 1

// element 2, right by 1.
while (index != start) {
arr[index] = arr[index - 1];
index--;
}
arr[start] = value;

// Update all the pointers

start++;
mid++;
start2++;
}
}
}

/* l is for left index and r is right index of the

sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
if (l < r) {

V Pathak
 // Same as (l + r) / 2, but avoids overflow
// for large l and r
int m = l + (r - l) / 2;

// Sort first and second halves

mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);

merge(arr, l, m, r);
}
}

/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray(int A[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}

/* Driver program to test above functions */

int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);

mergeSort(arr, 0, arr_size - 1);

printArray(arr, arr_size);
return 0;
}

[Link]

For integer types, merge sort can be made inplace using some mathematics trick
of modulus and division. That means storing two elements value at one index and
can be extracted using modulus and division.
First we have to find a value greater than all the elements of the array. Now we
can store the original value as modulus and the second value as division. Suppose
we want to store arr[i] and arr[j] both at index i(means in arr[i]). First we have to
find a ‘maxval’ greater than both arr[i] and arr[j]. Now we can store as arr[i] =
arr[i] + arr[j]*maxval. Now arr[i]%maxval will give the original value of arr[i]
and arr[i]/maxval will give the value of arr[j]. So below is the implementation on
merge sort.

V Pathak
Greedy Algorithm

V Pathak
V Pathak
Greedy Job Scheduling

V Pathak
Input: Four Jobs with following deadlines and profits

JobID Deadline Profit

a 4 20

b 1 10

c 1 40

d 1 30

Output: Following is maximum profit sequence of jobs

c, a

Input: Five Jobs with following deadlines and profits

JobID Deadline Profit

a 2 100

b 1 19

c 2 27

d 1 25

e 3 15

Output: Following is maximum profit sequence of jobs

c, a, e

V Pathak
Greedy – Single Source Shortest Path -Dijkstra’s Algorithm

V Pathak
V Pathak
Greedy Algorithm- Bellman-Ford Shortest Path Algorithm
The Bellman-Ford algorithm solves the single-source shortest-paths problem in the general case in
which edge weights may be negative. Given a weighted, directed graph G = <V, E> with source s
and weight function w : E ->R, the Bellman-Ford algorithm returns a boolean value indicating whether
or not there is a negative-weight cycle that is reachable from the source. If there is such a cycle, the
algorithm indicates that no solution exists. If there is no such cycle, the algorithm produces the
shortest paths and their weights.

V Pathak
i=1
Traverse edges in the order, say- (t, x), (t, y), (t,z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y)

i=2 Traverse edges in the order, say- (t, x), (t, y), (t,z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y)

i=3 .. 4 Traverse edges in the order, say- (t, x), (t, y), (t,z), (x, t), (y, x), (y, z), (z, x), (z, s), (s, t), (s, y)

V Pathak
Greedy Algorithm – Minimum Spanning Tree (MST) - Prim’s Algorithm

MST-PRIM(G, w, r) Binary-Heap
1 for each u ∈ G.V V
2 [Link] ← ∞ V
3 u.π ← NIL V
4 [Link] ← 0 V
5 Q ← G.V 1
6 while Q ≠ Ø V
7 u ← EXTRACT-MIN(Q) O(Vlog V)
8 for each v ∈ [Link][u] 2E
9 if v ∈ Q and w(u,v) < [Link] 2E
10 v.π ← u 2E
11 [Link] ← w(u, v) O(log V)
Total O(Vlog V + Elog V)= O(Elog V)

This is asymptotically the same as for our implementation of Kruskal’s algorithm.

We can improve the asymptotic running time of Prim’s algorithm by using Fibonacci heaps. If a Fibonacci heap
holds |V| elements, an EXTRACT-MIN operation takes O(lgV) amortized time and a DECREASE-KEY operation
(to implement line 11) takes O(1) amortized time. Therefore, if we use a Fibonacci heap to implement the min-
priority queue Q, the running time of Prim’s algorithm improves to O(E + V lgV)

V Pathak
Minimum Spanning Tree (MST) - Kruskal’s Algorithm

V Pathak
 Generic MST Algorithm
Red rule.
• Let C be a cycle with no red arcs. Select an uncolored arc of C of max weight and color it red.
Blue rule.
• Let D be a cut with no blue arcs. Select an uncolored arc in D of min weight and color it blue.
Greedy algorithm.

• Apply the red and blue rules (non-deterministically!) until all arcs are colored. The blue arcs form a
MST; Can stop once n-1 arcs colored blue.

Kruskal’s Algorithm
Sort edges weights in ascending order
c1  c2  ...  cm.
S = 
for each v  V
UFmake-set(v)
for i = 1 to m
(v,w) = ei
if (UFfind-set(v)  UFfind-set(w))
S  S  {i}
UFunion(v, w)
sorting – O (n log n)
union-find – O (m  (m, n))

V Pathak
# recursively
def find(p):
if root[p]!=p:
root[p] = find(root[p])
return root[p]

def uFind(u,v):
u_root = find(u)
v_root = find(v)
if rank[u_root]>rank[v_root]:
root[v_root] = u_root
elif rank[u_root]<rank[v_root]:
root[u_root] = v_root
else:
root[v_root] = u_root
rank[u_root] += 1

[Link]

V Pathak
Greedy Algorithms- Practice Exercises
1. Which is true for a connected graph? – a) |E| = O(|V|) b) |V| = O(|E|) [hint: |E| >= |V|]
c) log(|E|)= O(log|V|) d)log|V| = O(log|E|) [hint: |E| < |V|^2]
2. Optimal Merge Patterns and Huffman encoding
3. Optimal storage on tapes
4. ...

**Additional Reading
**When does greedy method return an optimal solution? – Matroid Theory
[ref – Cormen ch 16.4]

V Pathak
MST Problem as Matroid problem

Dynamic Programming versus Greedy Method

Dynamic programming is a bottom-up technique. Dynamic programming applies Bellman’s
Principle of Optimality. It ensures optimality of each decision with regard to optimality of all
subsequent decisions. Hence the outcome is a global optimal solution.
Greedy method is a hill-climbing approach based on immediate (local) best subsolutions. Hence
the outcome may be a local optimal solution.

Dynamic Programming versus Divide and Conquer

[Brassard & Bratley page 142] Dynamic programming is a bottom-up technique applied to solve
optimization problems and other multistage problems. We usually start with the smallest, and
hence the simplest, subinstances. By combining their solutions, we obtain the answers to subinstances
of increasing size, until finally we arrive at the solution of the original instance.

V Pathak
Divide-and-conquer, on the other hand, is a top-down method. When a problem is solved by
divide-and-conquer, we immediately attack the complete instance, which we then divide into
smaller and smaller subinstances as the algorithm progresses.
[…
Counter Examples of Dynamic Progamming!!
[Brassard & Bratley page144] Dynamic programming method can be applied only if the principle of
optimality applies i.e. “in an optimal sequence of decisions, each subsequence must also be optimal”. But
this principle doesnot always apply.
Example2: The principle of optimality does not apply to the problem of finding the longest simple
path between two cities. This is due to the fact that one cannot in general splice two simple paths together
and expect to obtain a simple path. (A path is simple if it never passes through the same place twice.
Without this restriction the longest path might be an infinite loop.)

Example2: If the shortest route from Montreal to Toronto goes via Kingston, then that part of the
journey from Montreal to Kingston must also follow the shortest route between these two cities : the principle
of optimality applies.
However, if the fastest way to drive from Montreal to Toronto takes us first to Kingston, it does not follow
that we should drive from Montreal to Kingston as quickly as possible : if we use too much petrol on the
first half of the trip, maybe we have to stop to fill up somewhere on the second half, losing more time than
we gained by driving hard. The subtrips Montreal-Kingston and Kingston-Toronto are not independent,
and the principle of optimality does not apply.

Restated Principle of Optimality- “ the optimal solution to any nontrivial instance is a combination of
optimal solutions to some of its subinstances ”

Versus Divide and Conquer- In Example2, it is not immediately obvious that the subinstance
consisting of finding the shortest route from Montreal to Ottawa is irrelevant to the shortest route from
Montreal to Toronto. This difficulty prevents us from using a divide-and-conquer approach that would
start from the original instance and recursively find optimal solutions precisely to those relevant
subinstances. Instead, dynamic programming efficiently solves every possible subinstance in order to figure
out which are in fact relevant, and only then are these combined into an optimal solution to the original instance.
…]

V Pathak
 Dynamic Programming
Fibonacci sequence[edit]
Here is a naïve implementation of a function finding the nth member of the Fibonacci sequence, based
directly on the mathematical definition:

function fib(n)
if n <= 1 return n
return fib(n − 1) + fib(n − 2)

Notice that if we call, say, fib(5), we produce a call tree that calls the function on the same value
many different times. In larger examples, many more values of fib, or subproblems, are recalculated,
leading to an exponential time algorithm.

Top-down approach: First break the problem into subproblems and then calculate and store values.
requires only O(n) time instead of exponential time (but requires O(n) space):

var m := map(0 → 0, 1 → 1)
function fib(n)
if key n is not in map m
m[n] := fib(n − 1) + fib(n − 2)
return m[n]

This technique of saving values that have already been calculated is called memoization;

Bottom-up approach: Calculate the smaller values of fib first, then build larger values from them.
This method also uses O(n) time since it contains a loop that repeats n − 1 times, but it only takes
constant (O(1)) space, in contrast to the top-down approach which requires O(n) space to store the map.

function fib(n)
if n = 0
return 0
else
var previousFib := 0, currentFib := 1
repeat n − 1 times // loop is skipped if n = 1
var newFib := previousFib + currentFib
previousFib := currentFib
currentFib := newFib
return currentFib

V Pathak
Calculating Binomial Coefficient
In mathematics, the binomial coefficients are the positive integers that occur as coefficients in
the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers n ≥ k ≥ 0 and is
written (𝑛𝑘) It is the coefficient of the xk term in the polynomial expansion of the binomial power (1 + x)n,
and is given by the formula
𝑛!
(𝑛𝑘) =
𝑘!(𝑛−𝑘)!

For example, the fourth power of 1 + x is

(1 + 𝑥)4 = (40)𝑥 0 + (41)𝑥 1 + (42)𝑥 2 + (43)𝑥 3 + (44)𝑥 4 = 1 + 4𝑥 + 6𝑥 2 + 4𝑥 3 + 𝑥 4
4 4!
and the binomial coefficient (2) = = 6 is the coefficient of the x2 term.
4! 2!

Arranging the numbers (𝑛0), (𝑛1), … , (𝑛 𝑛

) in successive rows for n=0,1,2,… gives a triangular array
called Pascal's triangle, satisfying the recurrence relation
𝑛 𝑛−1 𝑛−1
( )=( )+( )
𝑘 𝑘−1 𝑘

The binomial coefficients can be arranged to form Pascal's triangle, in which each entry is the sum of the
two immediately above. [Ref: [Link]

V Pathak
[Brassard & Bratley page 143]
In the recursive implementation, many values of C(i,j), i<n, j<k are calculated
repeatedly.
If we use a table of intermediate results (memorization), we obtain more efficient
algorithm. This can in fact be done using a vector of length k representing the current
line, instead of storing a matrix. The vector is updated left to right. Thus this can be
completed in time O(nk) and space O(k).

The binomial coefficients can be arranged to form Pascal's triangle, in which each entry is the sum of the two
immediately above. [Ref: [Link]

V Pathak
// A Dynamic Programming based solution that uses
// table C[][] to calculate the Binomial Coefficient
#include <bits/stdc++.h>
using namespace std;

// Prototype of a utility function that

// returns minimum of two integers
int min(int a, int b);

// Returns value of Binomial Coefficient C(n, k)

int binomialCoeff(int n, int k)
{
int C[n + 1][k + 1];
int i, j;

// Caculate value of Binomial Coefficient in bottom up manner

for (i = 0; i <= n; i++) {
for (j = 0; j <= min(i, k); j++) {
// Base Cases
if (j == 0 || j == i)
C[i][j] = 1;
// Calculate value using previously stored values
else
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}

return C[n][k];
}

// A utility function to return

// minimum of two integers
int min(int a, int b) { return (a < b) ? a : b; }

// Driver Code
int main()
{
int n = 5, k = 2;
cout << "Value of C[" << n << "][" << k << "] is "
<< binomialCoeff(n, k);
}

// [[Link]

V Pathak
The World Series (CA419)
Imagine a competition in which two teams A and B play not more than 2n -1 games, the winner
being the first team to achieve n victories. We assume that there are no tied games, that the results
of each match are independent, and that for any given match there is a constant probability p
that team A will be the winner and hence a constant probability q = 1 -p that team B will win.
Let P (i, j) be the probability that team A will win the series given that they still need i more
victories to achieve this, whereas team B still needs j more victories if they are to win.

P(i,j)=pP(i-1,j)+qP(i,j-1) i,j ≥ 1
function P (i, j)
if i = 0 then return 1
else if j = 0 then return 0
else return pP (i -1, j) + qP (i, j -1)

To speed up the algorithm, we compute similar to Pascal's triangle: we declare an array of the
appropriate size and then fill in the entries. However, instead of filling the array line by line, we
work diagonal by diagonal.

Teams A and B compete in a series of games.

• The winner is the first team to win n games.
• The series ends as soon as the winner is decided.
• At most 2n–1 games are played.
• Input : let p[k] = probability that team A wins the kth game, 1 ≤ k ≤ 2n–1,
• Output: P(i, j) = probability that the series reaches a situation where
team A wins exactly i games and team B wins exactly j games, 0 ≤ i ≤ n and
0≤j≤n

V Pathak
Recursive formula:
P(0, 0) = 1
P(n, n) = 0
P(i, 0) = P(i–1, 0)*p[i], for i>0
P(0, j) = P(0, j–1)*(1–p[j]), for j>0
P(n, j) = P(n–1, j)*p[n+j], for j<n
P(i, n) = P(i, n–1)*(1–p[i+n]), for i<n
P(i, j) = P(i–1, j)*p[i+j] + P(i, j–1)*(1–p[i+j]), for 0<i<n and 0<j<n

Dynamic Programming based Solution

function series (n , p )
array P[0..n,0..n]
for i  0 to n do
for j  0 to n do
if (i==0 && j==0)
P[i][j] = 1;
else if (i==n && j==n)
P[i][j] = 0;
else if ((i>0 && j==0) ||
(i==n && j<n))
P[i][j] = P[i–1][j]*p[i+j];
else if ((i==0 && j>0) || (i<n && j==n))
P[i][j] = P[i][j–1]*(1–p[i+j]);
else
P[i][j] = P[i–1][j]*p[i+j] + P[i][j–1]*(1–p[i+j]);
return P [n, n ]

X[3][2] = X[3–1][2]*p[3+2] + X[3][2–1]*(1–p[3+2])

= X[2][2]*p[5] + X[3][1]*(1–p[5])
= (.38)*(.7) + (.25)*(.3) = .341

V Pathak
Coin Change Problem (CA419)
To minimize the number of U.S. coins needed to make change for a given amount, we can repeatedly
select the largest-denomination coin that is not larger than the amount that remains. A greedy approach
provides an optimal solution for many such problems much more quickly than would a dynamic-
programming approach. But we cannot always easily tell whether a greedy approach will be effective.
[Cormen ch16.4 provide matroid theory, which provides a mathematical basis that can help us to
show that a greedy algorithm yields an optimal solution.]

Recursive Solution

def recMC(coinValueList,change):
minCoins = change
if change in coinValueList:
return 1
else:
for i in [c for c in coinValueList if c <= change]:
numCoins = 1 + recMC(coinValueList,change-i)
if numCoins < minCoins:
minCoins = numCoins
return minCoins
print(recMC([1,5,10,25],63))

Dynamic Programming with Memoization (table-lookup)

[[Link]

V Pathak
F [0] ← 0
for i ← 1 to n do
t emp ← ∞; j ← 1
while j ≤ m and i ≥ D[j ] do
t emp ← min(F [i − D[j ]], t emp) j ← j + 1
F [i] ← t emp + 1
return F [n]

[[Link]

V Pathak
Principle of Optimality

V Pathak
Dynamic Programming -0/1 Knapsack Problem

V Pathak
V Pathak
Q. m = 7 kg
(w1, w2, w3, w4) = (3,4,6,2)
(p1, p2, p3, p4) = (15,20,32,10)
Greedy (p/w) -> <0010>: 32 (local optimal)
But apparently better feasible solution -> <1100>:35 (global optimal)

V Pathak
DP- TSP

V Pathak
V Pathak
DP – All pair Shortest Path and Transitive Closure of a Directed Graph and
All Pair Shortest Path

V Pathak
V Pathak
Transitive Closure of Graph- Application of Floyd- Warshall Algorithm
Transitive closure of a directed graph (Warshall’s Algorithm)
Given a directed graph G =<V, E> with vertex set V ={1, 2, …, n}, determine whether G
contains a path from i to j for all vertex pairs i, j V. We define the transitive closure of G as
the graph G*= <V,E*>, where E*={(i, j) : there is a path from vertex i to vertex j in G}
One way to compute the transitive closure of a graph in (n3) time is to assign a weight of 1
to each edge of E and run the Floyd-Warshall algorithm. If there is a path from vertex i to

vertex j, we get dij < n. Otherwise, we get dij =1.

Alternative way is to substitute logical OR for the min operation and logical AND for
the + operation in the Floyd- Warshall Algorithm.

V Pathak
DP- Matrix Chain Multiplication (CA419)

V Pathak
DP- OBST

V Pathak
V Pathak
OBST Algorithm and Time Complexity consideration
[ref- Cormen pg 402]

V Pathak
Dynamic Programming- Longest Common Substring (LCS)

V Pathak
V Pathak
Memoization – e.g. Rod Cutting Problem
[ref: Cormen pg 387] There is an alternative approach to dynamic programming that often offers the efficiency
of the bottom-up dynamic programming approach while maintaining a top-down strategy. A memoized
recursive algorithm maintains an entry in a table for the solution to each subproblem. Each table entry initially
contains a special value to indicate that the entry has yet to be filled in. When the subproblem is first encountered
as the recursive algorithm unfolds, its solution is computed and then stored in the table. Each subsequent time
that we encounter this subproblem, we simply look up the value stored in the table and
return it. [ e.g. memorized version of Fibonacci series]

The rod-cutting problem is the following. Given a rod of length n inches and a table of prices pi for i =1, 2, …,
n, determine the maximum revenue rn obtainable by cutting up the rod and selling the pieces. Note that if the
price pn for a rod of length n is large enough, an optimal solution may require no cutting at all.

Length i 1 2 3 4 5 6 7 8 9 10
Price pi 1 5 8 9 10 17 17 20 24 30

Consider the case when n =4. Figure below shows all the ways to cut up a rod of 4 inches in length, including
the way with no cuts at all. We see that cutting a 4-inch rod into two 2-inch pieces produces revenue p2 + p2 =
5 + 5 =10, which is optimal.

We can cut up a rod of length n in 2n-1 different ways, since we have an independent option of cutting, or not
cutting, at distance i inches from the left end, for i = 1, 2, …, n-1

V Pathak
CUT-ROD(p, n)
1 if n == 0
2 return 0
3 q =-ꝏ
4 for i = 1 to n
5 q = max(q, p[i] + CUT-ROD(p, n – i))
6 return q
Length i 1 2 3 4
Price pi 1 5 8 9

Dynamic Programming based Rod-cutting

The first approach is top-down with memoization.2 In this approach, we write the procedure
recursively in a natural manner, but modified to save the result of each subproblem (usually in
an array or hash table). The procedure now first checks to see whether it has previously solved
this subproblem. If so, it returns the saved value, saving further computation at this level; if
not, the procedure computes the value in the usual manner. We say that the recursive procedure
has been memoized; it “remembers” what results it has computed previously.
The second approach is the bottom-up method. This approach typically depends on some
natural notion of the “size” of a subproblem, such that solving any particular subproblem
depends only on solving “smaller” subproblems. We sort the subproblems by size and solve
them in size order, smallest first. When solving a particular subproblem, we have already
solved all of the smaller subproblems its solution depends upon, and we have saved their
solutions. We solve each subproblem only once, and when we first see it, we have already
solved all of its prerequisite subproblems.

These two approaches yield algorithms with the same asymptotic running time, except in
unusual circumstances where the top-down approach does not actually recurse to examine all
possible subproblems. The bottom-up approach often has much better constant factors, since
it has less overhead for procedure calls.

V Pathak
MEMOIZED-CUT-ROD (p, n)
1 let r[0.. n] be a new array
2 for i = 0 to n
3 r[i] =-ꝏ
4 return MEMOIZED-CUT-ROD-AUX(p, n, r)
Refer to the subgraph –
Steps taken = 1 (for node 1) + 2 ( for node 2) + 3 (for node 3) + 4(for node 4)

 1+2+3+4+…+n <= cn^2

V Pathak
Backtracking

V Pathak
V Pathak
BackTracking- Sum of Subsets problem

V Pathak
V Pathak
Branch and Bound

V Pathak
V Pathak
V Pathak
V Pathak
V Pathak
V Pathak
V Pathak
V Pathak
MCAII Module 5: Graph
BFS

V Pathak
DFS

Determine path of shortest length to any node in graph from a given source

V Pathak
Branch and Bound- Assignment Problem
Let there be N workers and N jobs. Any worker can be assigned to perform any job, incurring some cost that
may vary depending on the work-job assignment. It is required to perform all jobs by assigning exactly one
worker to each job and exactly one job to each agent in such a way that the total cost of the assignment is
minimized
Example:
Job1 Job2 Job3 Job4
A 9 2 7 8
B 6 4 3 7
C 5 8 1 8
D 7 6 9 4

Brute-Force Solution
We generate all possible job assignments and for each such assignment, we compute its cost and return the least
cost assignment. Since the solution is a permutation of N jobs, its complexity is O(N!)

Branch and Bound Solution

Determining cost function- As shown above, two approaches to select cost function
1. For each worker- select job of minimum cost from the list of unassigned jobs (minimum entry from each
row)
2. For each job- select worker of minimum cost from the list of unassigned workers (minimum entry from
each column)

Solution using Approach 1. Row-wise minimum selection

Step1: Select min-cost job for worker A (min-of-row1) => i.e. [A,Job2] ➔ So row1, column2 becomes
unavailable for further steps. Similarly repeat for each worker B,C,D
Job1 Job2 Job3 Job4 Job1 Job2 Job3 Job4
A 9 2 7 8 A 9 2 7 8
B 6 4 3 7 B 6 4 3 7
C 5 8 1 8 C 5 8 1 8
D 7 6 9 4 D 7 6 9 4

Job1 Job2 Job3 Job4 Job1 Job2 Job3 Job4

A 9 2 7 8 A 9 2 7 8
B 6 4 3 7 B 6 4 3 7
C 5 8 1 8 ➔ C 5 8 1 8
D 7 6 9 4 D 7 6 9 4

V Pathak
 Job1 Job2 Job3 Job4 Job1 Job2 Job3 Job4
A 9 2 7 8 A 7 0 5 6
B 6 4 3 7 B 3 1 0 4
C 5 8 1 8 C 4 7 0 7
D 7 6 9 4 D 3 2 5 0
Original matrix Reduced matrix => 𝐶̂ (1) = 2 + 3 + 5 + 4

(complete solution space tree- would be traversed if FIFO B&B applied)

A➔2 cost =2 A➔2, B➔1 cost =2+6

Job1 Job2 Job3 Job4 Job1 Job2 Job3 Job4
A 9 2 7 8 A 9 2 7 8
B 6 4 3 7 B 6 4 3 7
C 5 8 1 8 C 5 8 1 8
D 7 6 9 4 D 7 6 9 4

A➔2, B➔1, C➔3, cost =2+6+1 A➔2, B➔1, C➔3, D➔4 cost =2+6+1+4=13
Job1 Job2 Job3 Job4 Job1 Job2 Job3 Job4
A 9 2 7 8 A 9 2 7 8
B 6 4 3 7 B 6 4 3 7
C 5 8 1 8 C 5 8 1 8
D 7 6 9 4 D 7 6 9 4

Instead of following FIFO order, we choose a live node with least cost (use LC/Heap B&B).
We may not get optimal solution ( A➔2, B➔1, C➔3, D➔4) by following node with least
promising cost (A➔2, B➔3, C➔1, D➔4), but it will provide very good chance of getting
the search to an answer node quickly.

V Pathak
Module V-

V Pathak
V Pathak
V Pathak
A problem is in the class NPC if it is in NP and is as hard as any problem in NP.
A problem is NP-hard if all problems in NP are polynomial time reducible to it,
even though it may not be in NP itself.

If a polynomial time algorithm exists for any of these problems, all problems in
NP would be polynomial time solvable. These problems are called NP-complete.
The phenomenon of NP-completeness is important for both theoretical and
practical reasons.

V Pathak
Definition of NP-Completeness
A language B is NP-complete if it satisfies two conditions

• B is in NP

• Every A in NP is polynomial time reducible to B.

If a language satisfies the second property, but not necessarily the first one, the
language B is known as NP-Hard. Informally, a search problem B is NP-
Hard if there exists some NP-Complete problem A that Turing reduces to B.

The problem in NP-Hard cannot be solved in polynomial time, until P = NP. If a

problem is proved to be NPC, there is no need to waste time on trying to find an
efficient algorithm for it. Instead, we can focus on design approximation
algorithm.

NP-Complete Problems
Following are some NP-Complete problems, for which no polynomial time
algorithm is known.

• Determining whether a graph has a Hamiltonian cycle

• Determining whether a Boolean formula is satisfiable, etc.

NP-Hard Problems
The following problems are NP-Hard

• The circuit-satisfiability problem

• Set Cover

• Vertex Cover

• Travelling Salesman Problem

In this context, now we will discuss TSP is NP-Complete

TSP is NP-Complete
The traveling salesman problem consists of a salesman and a set of cities. The
salesman has to visit each one of the cities starting from a certain one and
returning to the same city. The challenge of the problem is that the traveling
salesman wants to minimize the total length of the trip

V Pathak
Proof
To prove TSP is NP-Complete, first we have to prove that TSP belongs to
NP. In TSP, we find a tour and check that the tour contains each vertex once.
Then the total cost of the edges of the tour is calculated. Finally, we check if the
cost is minimum. This can be completed in polynomial time. Thus TSP belongs
to NP.

Secondly, we have to prove that TSP is NP-hard. To prove this, one way is to
show that Hamiltonian cycle ≤p TSP (as we know that the Hamiltonian cycle
problem is NPcomplete).

Assume G = (V, E) to be an instance of Hamiltonian cycle.

Hence, an instance of TSP is constructed. We create the complete graph G' =

(V, E'), where
E′={(i,j):i,j ∈ V and i≠j}
Thus, the cost function is defined as follows −
t(i,j)= 0 if(i,j) ∈ E
1 otherwise
Now, suppose that a Hamiltonian cycle h exists in G. It is clear that the cost of
each edge in h is 0 in G' as each edge belongs to E. Therefore, h has a cost
of 0 in G'. Thus, if graph G has a Hamiltonian cycle, then graph G' has a tour
of 0 cost.

Conversely, we assume that G' has a tour h' of cost at most 0. The cost of edges
in E' are 0 and 1 by definition. Hence, each edge must have a cost of 0 as the
cost of h' is 0. We therefore conclude that h' contains only edges in E.

We have thus proven that G has a Hamiltonian cycle, if and only if G' has a tour
of cost at most 0. TSP is NP-complete.

SAT, 3-SAT, Independent Set and NP-Complete

Satis_ability (SAT)
Given a set of clauses C1, …, Ck over variables X = {x1, …, xn} is there a satisfying
assignment?
Satis_ability (3-SAT)
Given a set of clauses C1, …, Ck , each of length 3, over variables X = {x1, …, xn} is there a
satisfying assignment?

V Pathak
Cook-Levin Theorem- 3-SAT is NP-complete
Idea of the proof: encode the workings of a Nondeterministic Turing machine for an instance I of problem X
2 NP as a SAT formula so that the formula is satis_able if and only if the nondeterministic Turing machine
would accept instance I .
3-SAT ≤p Independent Set
Proof. Suppose we have an algorithm to solve Independent Set, how can we use it to
solve 3-SAT?
To solve 3-SAT:
_ you have to choose a term from each clause to set to true,
_ but you can't set both xi and xi to true.

This graph has an independent set of size k i_ the formula is satisfiable.

Proof. =) If the formula is satis_able, there is at least one true literal in each clause.
Let S be a set of one such true literal from each clause. jSj = k and no two nodes in S
are connected by an edge.
=) If the graph has an independent set S of size k, we know that it has one node from
each \clause triangle." Set those terms to true. This is possible because no 2 are
negations of each other.

SAT ≤p Hamiltonian Cycle

V Pathak
 I 3 I 8 7 3
3 I 1 4 I 1
I 1 I 2 I 1
8 4 2 I 3 2
7 I I 3 I 3 =10

I 0 I 5 4
2 I 0 3 I
I 0 I 1 I
6 2 0 I 1
4 I I 0 I

2 1 =3

V Pathak
V Pathak