DECREASE AND CONQUER TECHNIQUE

As divide-and-conquer approach is already discussed, which include following

steps: Divide the problem into a number of sub problems that are smaller instances of the same
problem. Conquer the sub problems by solving them recursively.

Decrease and conquer is a technique used to solve problems by reducing the size of the input
data at each step of the solution process. This technique is similar to divide-and-conquer, in that it
breaks down a problem into smaller sub problems, but the difference is that in decrease-and-
conquer, the size of the input data is reduced at each step. The technique is used when it’s easier
to solve a smaller version of the problem, and the solution to the smaller problem can be used to
find the solution to the original problem.

IMPLEMENTATION OF DECREASE AND CONQUER

This approach can be either implemented as top-down or bottom-up. Top-down
approach: It always leads to the recursive implementation of the problem. Bottom-up approach: It
is usually implemented in iterative way, starting with a solution to the smallest instance of the
problem.

Variations of Decrease and Conquer:

There are three major variations of decrease-and-conquer:
1. Decrease by a constant
2. Decrease by a constant factor
3. Variable size decrease

Decrease by a Constant: In this variation, the size of an instance is reduced by the same constant
on each iteration of the algorithm. Typically, this constant is equal to one, although other
constant size reductions do happen occasionally. Below are example problems:
 Insertion sort
 Graph search algorithms: DFS, BFS
 Topological sorting
 Algorithms for generating permutations, subsets

Decrease by a Constant factor: This technique suggests reducing a problem instance by the same
constant factor on each iteration of the algorithm. In most applications, this constant factor is
equal to two. A reduction by a factor other than two is especially rare. Decrease by a constant
factor algorithms are very efficient especially when the factor is greater than 2 as in the fake-coin
problem. Below are example problems:
 Binary search
 Fake-coin problems
 Russian peasant multiplication
Variable-Size-Decrease: In this variation, the size-reduction pattern varies from one iteration of
an algorithm to another. As, in problem of finding god of two number though the value of the
second argument is always smaller on the right-hand side than on the left-hand side, it decreases
neither by a constant nor by a constant factor. Below are example problems:
Computing median and selection problem.
 Interpolation Search
 Euclid’s algorithm
There may be a case that problem can be solved by decrease-by-constant as well as decrease-by-factor variations,
but the implementations can be either recursive or iterative. The iterative implementations may require more
coding effort; however, they avoid the overload that accompanies recursion
 UNIT 5 - GRAPHS

The Graph ADT Introduction

Definition
Graph representation
Elementary graph operations BFS, DFS
Introduction to Graphs

Graph is a non linear data structure; A map is a well-known example of a graph. In a map various connections are
made between the cities. The cities are connected via roads, railway lines and aerial network. We can assume that
the graph is the interconnection of cities by roads. Euler used graph theory to solve Seven Bridges of Königsberg
problem. Is there a possible way to traverse every bridge exactly once – Euler Tour

Figure: Section of the river Pregal in Koenigsberg and Euler's graph.

Defining the degree of a vertex to be the number of edges incident to it, Euler showed that there is a walk starting
at any vertex, going through each edge exactly once and terminating at the start vertex iff the degree of each,
vertex is even. A walk which does this is called Eulerian. There is no Eulerian walk for the Koenigsberg bridge
problem as all four vertices are of odd degree.

A graph contains a set of points known as nodes (or vertices) and set of links known as edges (or Arcs) which
connects the vertices.

A graph is defined as Graph is a collection of vertices and arcs which connects vertices in the graph. A graph G is
represented as G = ( V , E ), where V is set of vertices and E is set of edges.

Example: graph G can be defined as G = ( V , E ) Where V = {A,B,C,D,E} and

E = {(A,B),(A,C)(A,D),(B,D),(C,D),(B,E),(E,D)}. This is a graph with 5 vertices and 6 edges.

Graph Terminology

[Link] : An individual data element of a graph is called as Vertex. Vertex is also known as node. In above
example graph, A, B, C, D & E are known as vertices.

[Link] : An edge is a connecting link between two vertices. Edge is also known as Arc. An edge is represented as
(starting Vertex, ending Vertex).

In above graph, the link between vertices A and B is represented as (A,B).

Edges are three types:

[Link] Edge - An undirected edge is a bidirectional edge. If there is an undirected edge between vertices A
and B then edge (A , B) is equal to edge (B , A).

[Link] Edge - A directed edge is a unidirectional edge. If there is a directed edge between vertices A and B
then edge (A , B) is not equal to edge (B , A).

1
[Link] Edge - A weighted edge is an edge with cost on it.

Types of Graphs

[Link] Graph

A graph with only undirected edges is said to be undirected graph.

[Link] Graph

A graph with only directed edges is said to be directed graph.

[Link] Graph

A graph in which any V node is adjacent to all other nodes present in the graph is known as a complete graph. An
undirected graph contains the edges that are equal to edges = n(n-1)/2 where n is the number of vertices present in
the graph. The following figure shows a complete graph.

[Link] Graph

Regular graph is the graph in which nodes are adjacent to each other, i.e., each node is accessible from any other
node.

[Link] Graph

A graph having cycle is called cycle graph. In this case the first and last nodes are the same. A closed simple path
is a cycle.

2
[Link] Graph

A graph without cycle is called acyclic graphs.

7. Weighted Graph

A graph is said to be weighted if there are some non negative value assigned to each edges of the graph. The
value is equal to the length between two vertices. Weighted graph is also called a network.

Outgoing Edge

A directed edge is said to be outgoing edge on its orign vertex.

Incoming Edge

A directed edge is said to be incoming edge on its destination vertex.

Degree

Total number of edges connected to a vertex is said to be degree of that vertex.

Indegree

Total number of incoming edges connected to a vertex is said to be indegree of that vertex.

Outdegree

Total number of outgoing edges connected to a vertex is said to be outdegree of that vertex.

Parallel edges or Multiple edges

If there are two undirected edges to have the same end vertices, and for two directed edges to have the same
origin and the same destination. Such edges are called parallel edges or multiple edges.

Self-loop

An edge (undirected or directed) is a self-loop if its two endpoints coincide.

Simple Graph

A graph is said to be simple if there are no parallel and self-loop edges.

3
Adjacent nodes

When there is an edge from one node to another then these nodes are called adjacent nodes.
Incidence

In an undirected graph the edge between v1 and v2 is incident on node v1 and v2.
Walk

A walk is defined as a finite alternating sequence of vertices and edges, beginning and ending with vertices, such
that each edge is incident with the vertices preceding and following it.
Closed walk

A walk which is to begin and end at the same vertex is called close walk. Otherwise it is an open walk.

If e1,e2,e3,and e4 be the edges of pair of vertices (v1,v2),(v2,v4),(v4,v3) and (v3,v1) respectively ,then v1 e1 v2
e2 v4 e3 v3 e4 v1 be its closed walk or circuit.

Path

A open walk in which no vertex appears more than once is called a path.

If e1 and e2 be the two edges between the pair of vertices (v1,v3) and (v1,v2) respectively, then v3 e1 v1 e2 v2 be
its path.
Length of a path

The number of edges in a path is called the length of that path. In the following, the length of the path is 3.

An open walk Graph

Circuit

A closed walk in which no vertex (except the initial and the final vertex) appears more than once is called a
circuit.
A circuit having three vertices and three edges.

4
Sub Graph

A graph S is said to be a sub graph of a graph G if all the vertices and all the edges of S are in G, and each edge of
S has the same end vertices in S as in G. A subgraph of G is a graph G’ such that V(G’)  V(G) and E(G’) 
E(G)

Connected Graph

A graph G is said to be connected if there is at least one path between every pair of vertices in G. Otherwise,G is
disconnected.

A connected graph G A disconnected graph G

This graph is disconnected because the vertex v1 is not connected with the other vertices of the graph.

Degree

In an undirected graph, the number of edges connected to a node is called the degree of that node or the degree of
a node is the number of edges incident on it.

In the above graph, degree of vertex v1 is 1, degree of vertex v2 is 3, degree of v3 and v4 is 2 in a connected
graph.

Indegree

The indegree of a node is the number of edges connecting to that node or in other words edges incident to it.

In the above graph,the indegree of vertices v1, v3 is 2, indegree of vertices v2, v5 is 1 and indegree of v4 is zero.
5
Outdegree

The outdegree of a node (or vertex) is the number of edges going outside from that node or in other words the

ADT of Graph:

Structure Graph is

objects: a nonempty set of vertices and a set of undirected edges, where each edge is a pair of vertices

functions: for all graph  Graph, v, v1 and v2  Vertices

Graph Create()::=return an empty graph

Graph InsertVertex(graph, v)::= return a graph with v inserted. v has no edge.

Graph InsertEdge(graph, v1,v2)::= return a graph with new edge between v1 and v2

Graph DeleteVertex(graph, v)::= return a graph in which v and all edges incident to it are removed

Graph DeleteEdge(graph, v1, v2)::=return a graph in which the edge (v1, v2) is removed

Boolean IsEmpty(graph)::= if (graph==empty graph) return TRUE else return FALSE

List Adjacent(graph,v)::= return a list of all vertices that are adjacent to v

Graph Representations

Graph data structure is represented using following representations

1. Adjacency Matrix

2. Adjacency List

3. Adjacency Multilists

[Link] Matrix

In this representation, graph can be represented using a matrix of size total number of vertices by total number of
vertices; means if a graph with 4 vertices can be represented using a matrix of 4X4 size.

In this matrix, rows and columns both represent vertices.

This matrix is filled with either 1 or 0. Here, 1 represents there is an edge from row vertex to column vertex and 0
represents there is no edge from row vertex to column vertex.

Adjacency Matrix : let G = (V, E) with n vertices, n  1. The adjacency matrix of G is a 2-dimensional n  n
matrix, A, A(i, j) = 1 iff (vi, vj) E(G) (vi, vj for a diagraph), A(i, j) = 0 otherwise.

example : for undirected graph

For a Directed graph

6
The adjacency matrix for an undirected graph is symmetric; the adjacency matrix for a digraph need not be
symmetric.

Merits of Adjacency Matrix:

From the adjacency matrix, to determine the connection of vertices is easy

n 1
The degree of a vertex is  adj _ mat[i][ j ]
j 0

For a digraph, the row sum is the out_degree, while the column sum is the in_degree
n 1 n 1
ind (vi )   A[ j , i ] outd (vi )   A[i, j ]
j 0 j 0
The space needed to represent a graph using adjacency matrix is n2 bits. To identify the edges in a graph,
adjacency matrices will require at least O(n2) time.

2. Adjacency List

In this representation, every vertex of graph contains list of its adjacent vertices. The n rows of the adjacency
matrix are represented as n chains. The nodes in chain I represent the vertices that are adjacent to vertex i.

It can be represented in two forms. In one form, array is used to store n vertices and chain is used to store its
adjacencies. Example:

So that we can access the adjacency list for any vertex in O(1) time. Adjlist[i] is a pointer to to first node in the
adjacency list for vertex i. Structure is

#define MAX_VERTICES 50
typedef struct node *node_pointer;
typedef struct node {
int vertex;
struct node *link;
};
node_pointer graph[MAX_VERTICES];
int n=0; /* vertices currently in use */

Another type of representation is given below.

example: consider the following directed graph representation implemented using linked list

7
This representation can also be implemented using array

Sequential representation of adjacency list is

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
9 11 13 15 17 18 20 22 23 2 1 3 0 0 3 1 2 5 6 4 5 7 6

Graph

Instead of chains, we can use sequential representation into an integer array with size n+2e+1. For 0<=i<n,
Array[i] gives starting point of the list for vertex I, and array[n] is set to n+2e+1. The adjacent vertices of node I
are stored sequentially from array[i].

For an undirected graph with n vertices and e edges, linked adjacency list requires an array of size n and 2e chain
nodes. For a directed graph, the number of list nodes is only e. the out degree of any vertex may be determined by
counting the number of nodes in its adjacency list. To find in-degree of vertex v, we have to traverse complete
list.

To avoid this, inverse adjacency list is used which contain in-degree.

[Link] Multilists

In the adjacency-list representation of an undirected graph each edge (u, v) is represented by two entries one on
the list for u and the other on tht list for v. As we shall see in some situations it is necessary to be able to determin
ie ~ nd enty for a particular edge and mark that edg as having been examined. This can be accomplished easily
if the adjacency lists are actually maintained as multilists (i.e., lists in which nodes may be shared among several
lists). For each edge there will be exactly one node but this node will be in two lists (i.e. the adjacency lists for
each of the two nodes to which it is incident).
For adjacency multilists, node structure is
typedef struct edge *edge_pointer;
typedef struct edge {
short int marked;
int vertex1, vertex2;
edge_pointer path1, path2;
};
edge_pointer graph[MAX_VERTICES];
8
Lists: vertex 0: N0->N1->N2, vertex 1: N0->N3->N4
vertex 2: N1->N3->N5, vertex 3: N2->N4->N5

Figure: Adjacency multilists for given graph

4. Weighted edges

In many applications the edges of a graph have weights assigned to them. These weights may represent the
distance from one vertex to another or the cost of going from one; vertex to an adjacent vertex In these
applications the adjacency matrix entries A [i][j] would keep this information too. When adjacency lists are used
the weight information may be kept in the list’nodes by including an additional field weight. A graph with
weighted edges is called a network.

ELEMENTARY GRAPH OPERATIONS

Given a graph G = (V E) and a vertex v in V(G) we wish to visit all vertices in G that are reachable from v (i.e.,
all vertices that are connected to v). We shall look at two ways of doing this: depth-first search and breadth-first
search. Although these methods work on both directed and undirected graphs the following discussion assumes
that the graphs are undirected.

Depth-First Search

 Begin the search by visiting the start vertex v

o If v has an unvisited neighbor, traverse it recursively
o Otherwise, backtrack
 Time complexity
o Adjacency list: O(|E|)
o Adjacency matrix: O(|V|2)

We begin by visiting the start vertex v. Next an unvisited vertex w adjacent to v is selected, and a depth-first
search from w is initiated. When a vertex u is reached such that all its adjacent vertices have been visited, we back
up to the last vertex visited that has an unvisited vertex w adjacent to it and initiate a depth-first search from w.
The search terminates when no unvisited vertex can be reached from any of the visited vertices.

DFS traversal of a graph, produces a spanning tree as final result. Spanning Tree is a graph without any loops.
We use Stack data structure with maximum size of total number of vertices in the graph to implement DFS

9
traversal of a graph.

We use the following steps to implement DFS traversal...

Step 1: Define a Stack of size total number of vertices in the graph.

Step 2: Select any vertex as starting point for traversal. Visit that vertex and push it on to the Stack.

Step 3: Visit any one of the adjacent vertex of the verex which is at top of the stack which is not visited and push
it on to the stack.

Step 4: Repeat step 3 until there are no new vertex to be visit from the vertex on top of the stack.

Step 5: When there is no new vertex to be visit then use back tracking and pop one vertex from the stack.

Step 6: Repeat steps 3, 4 and 5 until stack becomes Empty.

Step 7: When stack becomes Empty, then produce final spanning tree by removing unused edges from the graph

This function is best described recursively as in Program.

#define FALSE 0
#define TRUE 1
int visited[MAX_VERTICES];
void dfs(int v)
{
node_pointer w;
visited[v]= TRUE;
printf(“%d”, v);
for (w=graph[v]; w; w=w->link)
if (!visited[w->vertex])
dfs(w->vertex);
}
Consider the graph G of Figure 6.16(a), which is represented by its adjacency lists as in Figure 6.16(b). If a depth-
first search is initiated from vertex 0 then the vertices of G are visited in the following order: 0 1 3 7 4 5 2 6.
Since DFS(O) visits all vertices that can be reached from 0 the vertices visited, together with all edges in
G incident to these vertices form a connected component of G.

Figure: Graph and its adjacency list representation, DFS spanning tree

Analysis or DFS:
When G is represented by its adjacency lists, the vertices w adjacent to v can be determined by following a chain
of links. Since DFS examines each node in the adjacency lists at most once and there are 2e list nodes the time to
complete the search is O(e). If G is represented by its adjacency matrix then the time to determine all
vertices adjacent to v is O(n). Since at most n vertices are visited the total time is O(n2).
Breadth-First Search
In a breadth-first search, we begin by visiting the start vertex v. Next all unvisited vertices adjacent to v are
visited. Unvisited vertices adjacent to these newly visited vertices are then visited and so on. Algorithm BFS
(Program 6.2) gives the details.
typedef struct queue *queue_pointer;
typedef struct queue {
int vertex;

10
 queue_pointer link;
};
void addq(queue_pointer *,
queue_pointer *, int);
int deleteq(queue_pointer *);
void bfs(int v)
{
node_pointer w;
queue_pointer front, rear;
front = rear = NULL;
printf(“%d”, v);
visited[v] = TRUE;
addq(&front, &rear, v);
while (front) {
v= deleteq(&front);
for (w=graph[v]; w; w=w->link)
if (!visited[w->vertex]) {
printf(“%d”, w->vertex);
addq(&front, &rear, w->vertex);
visited[w->vertex] = TRUE;
}
}
}
Steps:
BFS traversal of a graph, produces a spanning tree as final result. Spanning Tree is a graph without any loops. We
use Queue data structure with maximum size of total number of vertices in the graph to implement BFS traversal
of a graph.

We use the following steps to implement BFS traversal...

Step 1: Define a Queue of size total number of vertices in the graph.
Step 2: Select any vertex as starting point for traversal. Visit that vertex and insert it into the Queue.
Step 3: Visit all the adjacent vertices of the vertex which is at front of the Queue which is not visited and insert
them into the Queue.
Step 4: When there is no new vertex to be visit from the vertex at front of the Queue then delete that vertex from
the Queue.
Step 5: Repeat step 3 and 4 until queue becomes empty.
Step 6: When queue becomes Empty, then produce final spanning tree by removing unused edges from the graph
Analysis Of BFS:
Each visited vertex enters the queue exactly once. So the while loop is iterated at most n times If an adjacency
matrix is used the loop takes O(n) time for each vertex visited. The total time is therefore, O(n2). If adjacency lists
are used the loop has a total cost of d0 + … + dn-1 = O(e), where d is the degree of vertex i. As in the case of DFS
all visited vertices together with all edges incident to them, form a connected component of G.
[Link] Components
If G is an undirected graph, then one can determine whether or not it is connected by simply making a call to
either DFS or BFS and then determining if there is any unvisited vertex. The connected components of a graph
may be obtained by making repeated calls to either DFS(v) or BFS(v); where v is a vertex that has not yet been
visited. This leads to function Connected(Program 6.3), which determines the connected components of G. The
algorithm uses DFS (BFS may be used instead if desired). The computing time is not affected. Function
connected –Output outputs all vertices visited in the most recent invocation of DFS together with all edges
incident on these vertices.
void connected(void){
for (i=0; i<n; i++) {
if (!visited[i]) {
dfs(i);
printf(“\n”); } }}
Analysis of Components:
If G is represented by its adjacency lists, then the total time taken by dfs is O(e). Since the for loops take O(n)
time, the total time to generate all the Connected components is O(n+e). If adjacency matrices are used,then the
time required is O(n2)
11
12
13
[Link]

14
 Analysis and Design of Algorithms (BCS401)

Module-4
Dynamic Programming
4.1 The General
Method Definition
Dynamic programming (DP) is a general algorithm design technique for solving
problems with overlapping sub-problems. This technique was invented by American
mathematician Richard Bellman in 1950s.

Key Idea
The key idea is to save answers of overlapping smaller sub-problems to avoid re-
computation.
Dynamic Programming Properties
An instance is solved using the solutions for smaller instances.
The solutions for a smaller instance might be needed multipl
multiple times, so store
their results in a table.
Thus each smaller instance is solved only once.
Additional space is used to save time.

Dynamic Programming vs. Divide & Conquer

LIKE divide & conquer, dynamic programming solves problems by combining
solutions to sub-problems. UNLIKE divide & conquer, sub-problems are NOT
independent in dynamic programming.

Divide & Conquer Dynamic Programming

1. Partitions a problem into independent 1. Partitions a problem into
smaller sub-problems
problems overlapping sub-problems

2. store solutions of sub-

2. Stores solutions of sub-
problems. (Identical sub-problems
problems: thus avoids
may arise - results in the same
calculations of same quantity
computations are performed
twice
repeatedly.)
3. Bottom up algorithms: in which
3. Top down algorithms: which logically the smallest sub-problems are
progresses from the initial instance explicitly solved first and the
down to the smallest sub-instances via results of these used to construct
intermediate sub-instances. solutions to progressively larger
sub-instances

Dynamic Programming vs. Divide & Conquer: EXAMPLE

Computing Fibonacci Numbers

66
 Analysis and Design of Algorithms (BCS401)

1. Using standard recursive formula:

0 if n=0
F(n) = 1 if n=1
F(n-1) + F(n-2) if n >1

Algorithm F(n)
// Computes the nth Fibonacci number recursively by using its definitions
// Input: A non-negative integer n
// Output: The nth Fibonacci
number if n==0 || n==1 then
return n
else
return F(n-1) + F(n-2)

Algorithm F(n): Analysis

Is too expensive as it has repeated calculation of smaller Fibonacci numbers.
Exponential order of growth.

F(n)
F(n-1) + F(n-2)
F(n-2) + F(n-3) F(n-3)
3) + F(n-4)
F(n

2. Using Dynamic Programming:

Algorithm F(n)
// Computes the nth Fibonacci number by using dynamic programming method
// Input: A non-negative integer n
// Output: The nth Fibonacci
number A[0] 0
A[1] 1
for i 2 to n do
A[i] A[i-1] + A[i-2]
return A[n]

Algorithm F(n): Analysis

Since it caches previously computed values, saves time from
repeated computations of same sub-instance
Linear order of growth
Rules of Dynamic Programming
1. OPTIMAL SUB-STRUCTURE: An optimal solution to a problem
contains optimal solutions to sub-problems

67
 Analysis and Design of Algorithms (BCS401)

2. OVERLAPPING SUB-PROBLEMS: A recursive solution contains a

number of distinct sub-problems repeated many times
3. BOTTOM UP FASHION: Computes the solution in a bottom-up fashion in
the final step

Three basic components of Dynamic Programming solution

The development of a dynamic programming algorithm must have the following
three basic components
1. A recurrence relation
2. A tabular computation
3. A backtracking procedure

Example Problems that can be solved using Dynamic Programming

method
1. Computing binomial co-efficient
2. Compute the longest common subsequence
3. Warsha algorithm for transitive closure
4. algorithm for all-pairs shortest paths
5. Some instances of difficult discrete optimization problems like knapsack
problem traveling salesperson problem
4.2 Algorithm

Some useful definitions:

Directed Graph: A graph whose every edge is directed is called directed
graph OR digraph
Adjacency matrix: The adjacency matrix A = {aij} of a directed graph is
the boolean matrix that has
o 1 - if there is a directed edge from ith vertex to the jth vertex
o 0 - Otherwise
Transitive Closure: Transitive closure of a directed graph with n vertices can
be defined as the n-by-n matrix T={tij}, in which the elements in the ith row

n) and the jth j n) is 1 if there exists a nontrivial directed path

(i.e., a directed path of a positive length) from the ith vertex to the jth vertex,
otherwise tij is 0.
The transitive closure provides reach ability information about a digraph.
Computing Transitive Closure:
We can perform DFS/BFS starting at each vertex
Performs traversal starting at the ith vertex.
Gives information about the vertices reachable from the ith vertex
Drawback: This method traverses the same graph several times.
Efficiency : (O(n(n+m))
Alternatively, we can use dynamic programming: the Algorithm
Underlying idea of algorithm:
Let A denote the initial boolean matrix.

68
CS6402 Design and Analysis of Algorithms Unit III 3.1

UNIT III DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE

3.1 COMPUTING A BINOMIAL COEFFICIENT

Dynamic Programming Binomial Coefficients

Dynamic Programming was invented by Richard Bellman, 1950. It is a very general
technique for solving optimization problems.
Dynamic Programming requires:
1. Problem divided into overlapping sub-problems
2. Sub-problem can be represented by a table
3. Principle of optimality, recursive relation between smaller and larger problems
Compared to a brute force recursive algorithm that could run exponential, the dynamic
programming algorithm runs typically in quadratic time. The recursive algorithm ran in exponential
time while the iterative algorithm ran in linear time.
Computing a Binomial Coefficient
Computing binomial coefficients is non optimization problem but can be solved using
dynamic programming.
Binomial coefficients are represented by C(n, k) =n! / (k! (n-k)!) or (��) and can be used to
represent the coefficients of a binomial:
(a + b)n = C(n, 0)anb0 + . . . + C(n, k)an-kbk + . . . + C(n, n) a0bn
The recursive relation is defined by the prior power
C(n, k) = C(n-1, k-1) + C(n-1, k) for n > k > 0 with initial Condition C(n, 0) = C(n, n) = 1
Dynamic algorithm constructs a nxk table, with the first column and diagonal filled out using the
Initial Condition. Construct the table:
k
0 1 2 ... k-1 k
0 1
1 1 1
2 1 2 1
n ...
k 1 1
...
n-1 1 C(n-1, k-1) C(n-1, k)
n 1 C(n, k)
The table is then filled out iteratively, row by row using the recursive relation.
Algorithm Binomial(n, k)
for i ← 0 to n do // fill out the table row wise
for i = 0 to min(i, k) do
if j==0 or j==i then C[i, j] ← 1 // Initial Condition
else C[i, j] ← C[i-1, j-1] + C[i-1, j] // recursive relation
return C[n, k]
CS6402 Design and Analysis of Algorithms Unit III 3.2

The cost of the algorithm is filing out the table. Addition is the basic operation. Because k ≤ n, the
sum needs to be split into two parts because only the half the table needs to be filled out
for i <k and remaining part of the table is filled out across the entire row.

A(n, k) = sum for upper triangle + sum for the lower rectangle
= ∑i=1k ∑j=1i-1 1 + ∑i=1n ∑j=1k 1
= ∑i=1k (i-1) + ∑i=1n k
= (k-1)k/2 + k(n-k) ϵ Θ(nk)
Time efficiency: Θ(nk)
Space efficiency: Θ(nk)

Example: Relation of binomial coefficients and pascal’s triangle.

A formula for computing binomial coefficients is this:

Using an identity called Pascal's Formula a recursive formulation for it looks like this:

This construction forms Each number in the triangle is the sum of the two numbers directly above
it.

Finding a binomial coefficient is as simple as a lookup in Pascal's Triangle.

Example: (x+y)7 = 1•x7y0+7•x6y1+21•x5y2+35•x4y3+35•x3y4+21•x2y5+7•x1y6+1•x0y7

= x7+7x6y+21x5y2+35x4y3+35x3y4+21x2y5+7xy6+y7
CS6402 Design and Analysis of Algorithms Unit III 3.14

Only 11 out of 20 nontrivial values (i.e., not those in row 0 or in column 0) have been
computed. Just one nontrivial entry, V (1, 2), is retrieved rather than being recomputed. For larger
instances, the proportion of such entries can be significantly larger.

3.5 GREEDY TECHNIQUE

The greedy approach suggests constructing a solution through a sequence of steps, each
expanding a partially constructed solution obtained so far, until a complete solution to the problem
is reached. On each step and this is the central point of this technique.

The choice made must be:

 feasible, i.e., it has to satisfy the problem’s constraints
 locally optimal, i.e., it has to be the best local choice among all feasible choices available on
that step
 irrevocable, i.e., once made, it cannot be changed on subsequent steps of the algorithm

Greedy Technique algorithms are:

 Prim’s algorithm
 Kruskal's Algorithm
 Dijkstra's Algorithm
 Huffman Trees

Two classic algorithms for the minimum spanning tree problem: Prim’s algorithm and
Kruskal’s algorithm. They solve the same problem by applying the greedy approach in two
different ways, and both of them always yield an optimal solution.

Another classic algorithm named Dijkstra’s algorithm used to find the shortest-path in a
weighted graph problem solved by Greedy Technique . Huffman codes is an important data
compression method that can be interpreted as an application of the greedy technique.

The first way is one of the common ways to do the proof for Greedy Technique is by
mathematical induction.

The second way to prove optimality of a greedy algorithm is to show that on each step it does
at least as well as any other algorithm could in advancing toward the problem’s goal.

Example: find the minimum number of moves needed for a chess knight to go from one corner of a
100 × 100 board to the diagonally opposite corner. (The knight’s moves are L-shaped jumps: two
squares horizontally or vertically followed by one square in the perpendicular direction.)

A greedy solution is clear here: jump as close to the goal as possible on each move. Thus, if
its start and finish squares are (1,1) and (100, 100), respectively, a sequence of 66 moves such as
(1, 1) − (3, 2) − (4, 4) − . . . − (97, 97) − (99, 98) − (100, 100) solves the problem(The number k of
two-move advances can be obtained from the equation 1+ 3k = 100).
CS6402 Design and Analysis of Algorithms Unit III 3.15

Why is this a minimum-move solution? Because if we measure the distance to the goal by
the Manhattan distance, which is the sum of the difference between the row numbers and the
difference between the column numbers of two squares in question, the greedy algorithm decreases
it by 3 on each move.

The third way is simply to show that the final result obtained by a greedy algorithm is
optimal based on the algorithm’s output rather than the way it operates.

Example: Consider the problem of placing the maximum number of chips on an 8 × 8 board so that
no two chips are placed on the same or adjacent vertically, horizontally, or diagonally.

FIGURE 3.12 (a) Placement of 16 chips on non-adjacent squares. (b) Partition of the board
proving impossibility of placing more than 16 chips.

It is impossible to place more than one chip in each of these squares, which implies that the
total number of nonadjacent chips on the board cannot exceed 16.

3.6 PRIM’S ALGORITHM

A spanning tree of an undirected connected graph is its connected acyclic subgraph (i.e., a
tree) that contains all the vertices of the graph. If such a graph has weights assigned to its edges, a
minimum spanning tree is its spanning tree of the smallest weight, where the weight of a tree is
defined as the sum of the weights on all its edges. The minimum spanning tree problem is the
problem of finding a minimum spanning tree for a given weighted connected graph.

FIGURE 3.13 Graph and its spanning trees, with T1 being the minimum spanning tree.

The minimum spanning tree is illustrated in Figure 3. If we were to try constructing a

minimum spanning tree by exhaustive search, we would face two serious obstacles. First, the
number of spanning trees grows exponentially with the graph size (at least for dense graphs).
Second, generating all spanning trees for a given graph is not easy; in fact, it is more difficult than
finding a minimum spanning tree for a weighted graph.
CS6402 Design and Analysis of Algorithms Unit III 3.16

Prim’s algorithm constructs a minimum spanning tree through a sequence of expanding

subtrees. The initial subtree in such a sequence consists of a single vertex selected arbitrarily from
the set V of the graph’s vertices. On each iteration, the algorithm expands the current tree in the
greedy manner by simply attaching to it the nearest vertex not in that tree. The algorithm stops after
all the graph’s vertices have been included in the tree being constructed.

ALGORITHM Prim(G)
//Prim’s algorithm for constructing a minimum spanning tree
//Input: A weighted connected graph G = {V, E}
//Output: ET, the set of edges composing a minimum spanning tree of G
VT←{v0} //the set of tree vertices can be initialized with any vertex
ET←Φ
for i ←1 to |V| − 1 do
find a minimum-weight edge e∗ = (v∗, u∗) among all the edges (v, u)
such that v is in VT and u is in V − VT
VT←VT∪ {u*}
ET←ET∪ {e*}
return ET

If a graph is represented by its adjacency lists and the priority queue is implemented as a
min-heap, the running time of the algorithm is O(|E| log |V |) in a connected graph, where |V| − 1≤
|E|.
CS6402 Design and Analysis of Algorithms Unit III 3.17

FIGURE 3.14 Application of Prim’s algorithm. The parenthesized labels of a vertex in the middle
column indicate the nearest tree vertex and edge weight; selected vertices and edges are in bold.