UNIT-IV

Greedy Method, Basic Traversal and search Techniques

Dr P Muralidhar, Associate Professor

Dr P Muralidhar, Associate Professor
Greedy Method

• It is a straight forward design technique.

• These problems have n inputs and require us to obtain a subset that
satisfies some constraints.
• Any subset that satisfies some constraints.
• Any subset that satisfies these constraints is called a feasible solution.
• Find the feasible solution that maximizes or minimizes a given
objective function, is called an optimal solution.

Dr P Muralidhar, Associate Professor

• Devise an algorithm that works in stages, considering one input at a
time.
• At each stage, a decision is made regarding whether a particular input
is an optimal solution.
• This is done by considering the inputs in an order determined by
some selection procedure. If the inclusion of the next input into the
partially constructed optimal solution will result in an infeasible
solution, then this input is not added to partial solution. Other wise it
is added.
• Some algorithms result in generating suboptimal solutions. This
version of greedy technique is called subset paradigm.

Dr P Muralidhar, Associate Professor

Greedy Method

Dr P Muralidhar, Associate Professor

JOB SEQUENCING WITH DEADLINES
• Given a set of n jobs.
• Only one machine is available for processing job.
• Associated with job i is an integer deadline di >0 and a profit pi >0
• For any job i the profit pi is earned iff the job is completed by its
deadline.
• To complete a job, one has to process the job on a machine for one
unit of time.
• A feasible solution for this problem is a subset J of jobs such that each
Job in this subset can be completed by its deadline

Dr P Muralidhar, Associate Professor

• A feasible solution for this problem is a subset J of jobs such that each
Job in this subset can be completed by its deadline.
• The value of a feasible solution J is the sum of the profits of the jobs
in J, or
• An optimal solution is a feasible solution with maximum value.

Dr P Muralidhar, Associate Professor

Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
Efficient Feasibility Check
• To determine whether a set of jobs J is a feasible solution, the naive
approach would involve checking all possible permutations of the jobs in J to
find at least one order where all jobs can meet their deadlines.
• Order by Non-Decreasing Deadlines: Sort jobs in J so that jobs with earlier
deadlines are scheduled first.
• Check Each Job in the Sorted Order: For each job iq (where 1≤q≤k), assign it
the earliest available time slot. If the job can be scheduled within its
deadline, it is feasible; otherwise, it’s not.
• The job iq will be assigned to time slot q, meaning the earliest time slot available
when job iq is scheduled is q.
• If q≤di, the job iq meets its deadline. If q>di​​, then job iq cannot be completed by its
deadline in this sequence, making J infeasible.
Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
Find and Weighted Union

Dr P Muralidhar, Associate Professor

Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
KNAPSACK PROBLEM
• Apply the greedy method to solve the knapsack problem.
• Given n objects and a knapsack or bag
• Object i has a weight wi and a knapsack has a capacity m
• If a fraction xi 0<=xi<=1 of object i is placed into the knapsack, then the
profit of pixi is earned.
• Total weight of all chosen Objects to be atmost m
where profits and weights are
positive numbers
The feasible solution is < x1, x2, x3,… xn>
• The

Dr P Muralidhar, Associate Professor

This means that objects are considered in order of the ratio Pi/wi.

Dr P Muralidhar, Associate Professor

Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
• If the objects have already been sorted into non-increasing order of
Pi/wi, then function Greedy Knapsack obtains solutions correspond
into this strategy
• Time Complexity is O(n).

Dr P Muralidhar, Associate Professor

MINIMUM-COST SPANNING TREES

Dr P Muralidhar, Associate Professor

Applications
• They can be used to obtain an independent set of circuit equations for
an electric network.
• Kirchoff's second law is used on each cycle to obtain a circuit
equation.

Dr P Muralidhar, Associate Professor

Properties of Spanning Trees
• Spanning trees arises from the property that a spanning tree is a
minimal subgraph G‘ of G such that V(G')= V(G).
• Any connected graph with n vertices must have at least n-1 edges and
all connected graphs with n -1 edges are trees

Dr P Muralidhar, Associate Professor

Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
Prims algorithm
• A greedy method to obtain a minimum-cost spanning tree builds this tree
edge by edge.
• The next edge to include is chosen according to some optimization criterion.
• The simplest such criterion is to choose an edge that results in a minimum
increase in the sum of the costs of the edges so far included.
• There are two possible ways to interpret this criterion
• In the first, the set of edges so far selected form a tree. Thus, if A is the set of
edges selected so far, then A forms a tree.
• The next edge(u,v) to be included in A is a minimum-cost edge not in A with
the property that A U {(u,v)}is also a tree

Dr P Muralidhar, Associate Professor

• The algorithm will start with a tree that includes only a minimum-cost edge of G.
• Then, edges are added to this tree one by one.
• The next edge(i,j) to be added is such that i is a vertex already included in the
tree, j is a vertex not yet included and the cost of (i,j), cost[i,j], minimum among
all edges (k,l) such that vertex k is in the tree and vertex I is not in the tree.
• To determine this edge(i,j) efficiently, we associate with each vertex j not yet
included in the tree a value near[j].
• The value near [j] is a vertex in the tree such that cost[j], near[j] is minimum
among all choices for near[j].
• We define near[j]= 0 for all vertices j that are already in the tree. The next edge
to include is defined by the vertex j such that near[j]!= 0 (j not already in the tree)
and cost[j], near[j] is minimum.
• Time required for Prim algorithm is O(n2).

Dr P Muralidhar, Associate Professor

Dr P Muralidhar, Associate Professor
Kruskal‘s Algorithm

Dr P Muralidhar, Associate Professor

• Initially E is the set of all edges in G.
• The only functions we wish to perform on this set are
• (1) determine an edge with minimum cost and
• (2) delete this edge.
• Both these functions can be performed efficiently if the edges in E are
maintained as a sorted sequential list.
• It is not essential to sort all the edges so long as the next edge can be
determined easily.

Dr P Muralidhar, Associate Professor

• G should be grouped together in such a way that one can easily
determine whether the Vertices v and w are already connected by the
earlier selection of edges.
• If they are, then the edge(v, w) is to be discarded.
• If they are not, then {v, w) is to be added to t.
• One possible grouping is to place all vertices in the same connected
component of t into a set (all connected components of t will also be
trees).
• Then, two vertices v and w are connected in t iff they are in the same
set.

Dr P Muralidhar, Associate Professor

Dr P Muralidhar, Associate Professor
Find the Minimum Spanning Tree

Dr P Muralidhar, Associate Professor

SINGLE-SOURCE SHORTEST PATHS
• Graphs can be used to represent the highway structure of a state or
country with vertices representing cities and edges representing
sections of highway.
• The edges can then be assigned weights which may be either the
distance between the two cities connected by the edge or the
average time to drive along that section of highway.
• A motorist wishing to drive from city A to B would be interested in
answers to the following question

Dr P Muralidhar, Associate Professor

• Is there a path from A to B?
• If there is more than one path from A to B, which is the shortest path?

Dr P Muralidhar, Associate Professor

• The length of a path is now defined to be the sum of the weights of
the edges on that path.
• The starting vertex of the path is referred to as the source, and the
last vertex the destination.
• Consider, we are given a directed graph G = (V,E),a weighting function
Cost for the edges of G, and a source vertex vq. The problem is to
determine the shortest paths from vq to all the remaining verticesof
G. It is assumed that all the weights are positive. The shortest path
between vo and some other node v is an ordering among a subset of
the edges. Hence this problem fits the ordering paradigm.

Dr P Muralidhar, Associate Professor

Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
Dr P Muralidhar, Associate Professor
Find the single source shortest path

Dr P Muralidhar, Associate Professor

BASIC TRAVERSAL AND SEARCH
TECHNIQUES
• The techniques are divided into two categories
• First one is applicable to binary trees
• The second one is application to graphs
• During a traversal or search the fields of a node may be used several times. It
may be necessary to distinguish certain uses of the fields of a node.
• During these uses, the node is said to be visited.
• Visiting a node may involve printing out its data field, evaluating the operation
specified by the node in the case of a binary tree representing an expression,
setting a mark bit to one or zero,and so on.
• Since we are describing traversals and searches of trees and graphs
independently of their application, we use the term "visited“.
Dr P Muralidhar, Associate Professor
Traversing the binary tree
• One that arises frequently is traversing a tree, or visiting each node in
the tree exactly once.
• A traversal produces a linear order for the information in a tree.
• This linear order may be familiar and useful.
• When traversing a binary tree, we want to treat each node and its
subtrees in the same fashion. If we let L, D, and R stand for moving
left, printing the data, and moving right when at a node, then there
are six possible combinations of traversal: LDR, LRD, DLR, DRL, RDL,
and RLD.
• If we adopt the convention that we traverse left before right, then
only three traversals remain: LDR, LRD, and DLR. These we assign the
names inorder, postorder,and preorder.
Dr P Muralidhar, Associate Professor
Techniques for Binary Trees

Dr P Muralidhar, Associate Professor

Dr P Muralidhar, Associate Professor
Binary tree traversal

Inorder is FDHGIBEAC.
Preorder ABDFGHIEC and
Post Order FHIGDEBCA

Dr P Muralidhar, Associate Professor

Techniques for Graphs
• The given graph G = (V, E) such that this path starts at vertex v and
ends at vertex u.
• A more general form is to determine for a given starting vertex v V all
vertices u such that there is a path from v to u.

Dr P Muralidhar, Associate Professor

Breadth First Search and Traversal
• In breadth first search we start at a vertex v and mark it as having
been reached(visited).
• The vertex v is at this time said to be unexplored.
• A vertex is said to have been explored by an algorithm when the
algorithm has visited all vertices adjacent from it.
• All unvisited vertices adjacent from v are visited next.
• These are new unexplored vertices.
• Vertex v has now been explored.

Dr P Muralidhar, Associate Professor

• The newly visited vertices haven't been explored and are put onto the
end of a list of unexplored vertices.
• The first vertex on this list is the next to be explored.
• Exploration continues until no unexplored vertex is left.
• The list of unexplored vertices operates as a queue and can be
represented using any of the standard queue representations

Dr P Muralidhar, Associate Professor

Dr P Muralidhar, Associate Professor
Breadth first search

Dr P Muralidhar, Associate Professor

Dr P Muralidhar, Associate Professor
Depth First Search and Traversal

Dr P Muralidhar, Associate Professor

In BFS, the vertices get visited in the order 1,2, 3,4, 5, 6, 7, 8

In DFS, the vertices being visited in the order 1,2, 4, 8, 5, 6, 3,7

Dr P Muralidhar, Associate Professor

Connected Components
• If G is a connected undirected graph, then all vertices of G will get
visited on the first call to BFS.

Dr P Muralidhar, Associate Professor

BiConnected Components
• A vertex v in a connected graph G is an articulation point if and only if
the deletion of vertex v together with all edges incident to v
disconnects the graph into two or more nonempty components.

Dr P Muralidhar, Associate Professor

• A graph G is biconnected if and only if it contains no articulation
points
• The presence of articulation points in a connected graph can be an
undesirable feature in many cases.
• For example, if G represent as communication network with the
vertices representing communication stations and the edges
communication lines.
• Edges communication lines, then the failure of a communication
station i that is an articulation point would result in the loss of
communication to points other than i too.

Dr P Muralidhar, Associate Professor

• we develop an efficient algorithm to test whether a connected graph
is biconnected. For the case of graphs that are not biconnected, this
algorithm will identify all the articulation points.
• Once it has been determined that a connected graphG is not
biconnected it, may be desirable to determine a set of edges whose
inclusion makes the graph biconnected.
• Determining such a set of edges is facilitated if we know the maximal
subgraphs of G that are biconnected.
• G'= (V',E')is a maximal biconnected subgraph of G if and only if G has
no biconnected subgraph G" = (V", E”) such that V V" and E' E". A
maximal biconnected subgraph is a biconnected component

Dr P Muralidhar, Associate Professor

• Two biconnected components can have at most one vertex in
common and this vertex is an articulation point.

Dr P Muralidhar, Associate Professor