18CSC201J

DATA STRUCTURES AND

ALGORITHMS
UNIT 5
Prepared by

Dr. M.Ferni Ukrit

Dr. C. Amuthadevi
Dr. S. K. Lavanya
Dr.Praveena Akki
Dr.Varun Kumar
SYLLABUS
• Graph Terminology -Traversal
• Topological Sorting, Minimum Spanning Tree, Prim’s Algorithm
• Minimum Spanning Tree- Kruskal Algorithm- Network Flow problem
• Shortest Path Algorithm-Introduction- Dijikstra’s Algorithm
• Hashing –Introductions- Hash Functions
• Hashing- Collision Avoidance- Separate Chaining
• Open Addressing- Linear Probing
• Quadratic Probing- Double hashing
• Rehashing- Extensible Hashing
Introduction to ADT Graphs
What is a graph?
• A data structure that consists of a set of nodes
(vertices) and a set of edges that relate the nodes
to each other
• The set of edges describes relationships among
the vertices
Formal definition of graphs
• A graph G is defined as follows:
G=(V,E)
V(G): a finite, nonempty set of vertices
E(G): a set of edges (pairs of vertices)
Directed vs. undirected graphs
• When the edges in a graph have no direction, the
graph is called undirected
Directed vs. undirected graphs (cont.)
• When the edges in a graph have a direction, the
graph is called directed (or digraph)

Warning: if the graph is

directed, the order of the
vertices in each edge is
important !!

E(Graph2) = {(1,3) (3,1) (5,9) (9,11) (5,7)

Trees vs graphs
• Trees are special cases of graphs!!
Graph terminology

• Adjacent nodes: two nodes are adjacent if they

are connected by an edge

5 is adjacent to 7
7 is adjacent from 5

• Path: a sequence of vertices that connect two

nodes in a graph
• Complete graph: a graph in which every vertex is
directly connected to every other vertex
Graph terminology (cont.)
• What is the number of edges in a complete
directed graph with N vertices?
N * (N-1)
Graph terminology (cont.)
• What is the number of edges in a complete
undirected graph with N vertices?
N * (N-1) / 2
Graph terminology (cont.)
• Weighted graph: a graph in which each edge
carries a value
 Graph terminology (cont.)
Degree
• The number of edges incident on a vertex determines its degree. The
degree of the vertex is written as degree (v). The in degree of the
vertex V is the number of edges entering into vertex V. Similarly the
out degree of the vertex V is the number of edges existing fro that
vertex V.
 ADT for 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
incident 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 14
Implementation of ADT Graphs
Graph implementation
• Array-based implementation
• A 1D array is used to represent the vertices
• A 2D array (adjacency matrix) is used to
represent the edges
Array-based implementation
Graph implementation (cont.)
• Linked-list implementation
• A 1D array is used to represent the vertices
• A list is used for each vertex v which contains
the vertices which are adjacent from v
(adjacency list)
Linked-list implementation
Adjacency matrix vs. adjacency list
representation
• Adjacency matrix
• Good for dense graphs --|E|~O(|V|2)
• Memory requirements: O(|V| + |E| ) = O(|V|2 )
• Connectivity between two vertices can be tested quickly
• Adjacency list
• Good for sparse graphs -- |E|~O(|V|)
• Memory requirements: O(|V| + |E|)=O(|V|)
• Vertices adjacent to another vertex can be found quickly
Representation of Graph
• Graph can be represented by Adjacency Matrix and Adjacency List.
• Adjacency Matrix Representation
• The adjacency matrix A for a graph G=(V,E) with n vertices in an n x n matrix , such that
• Aij = 1, if there is an edge Vi to Vj
• Aij = 0, if there is no edge
 Adjacency Matrix-Pros and Cons

Pros:
• Simple to implement
• Easy and fast to tell if a pair (i,j) is an edge: simply check if A[i][j] is 1 or
0
Cons:
• No matter how few edges the graph has, the matrix takes O(n2) in
memory
 Adjacency List Representation
• In this representation we store a graph as a linked structure. We store all the vertices in a list
for each vertex; we have a linked list of its adjacency vertices.

3 1 2
0 0
1 2 3 0

1 2 0
1 2 1 3 0

0 1 2
2
3
Adjacency List-Pros and Cons
Pros:
• Saves on space (memory): the representation takes as many
memory words as there are nodes and edge.
Cons:
• It can take up to O(n) time to determine if a pair of nodes (i,j) is an
edge: one would have to search the linked list L[i], which takes time
proportional to the length of L[i].
Graph specification based on adjacency
matrix representation
const int NULL_EDGE = 0;
template<class VertexType> private:
int numVertices;
class GraphType {
int maxVertices;
public: VertexType* vertices;
GraphType(int); int **edges;
~GraphType(); bool* marks;
};
void MakeEmpty();
bool IsEmpty() const;
bool IsFull() const;
void AddVertex(VertexType);
void AddEdge(VertexType, VertexType, int);
int WeightIs(VertexType, VertexType);
void GetToVertices(VertexType, QueType<VertexType>&);
void ClearMarks();
void MarkVertex(VertexType); (continues)
bool IsMarked(VertexType) const;
template<class VertexType> void GraphType<VertexType>::AddVertex(VertexType vertex)
GraphType<VertexType>::GraphType(int maxV) {
{ vertices[numVertices] = vertex;
numVertices = 0;
maxVertices = maxV; for(int index = 0; index < numVertices; index++) {
vertices = new VertexType[maxV]; edges[numVertices][index] = NULL_EDGE;
edges = new int[maxV]; edges[index][numVertices] = NULL_EDGE;

for(int i = 0; i < maxV; i++) }

edges[i] = new int[maxV];

numVertices++;
marks = new bool[maxV];
}
}
template<class VertexType>
template<class VertexType>
GraphType<VertexType>::~GraphType()
void GraphType<VertexType>::AddEdge(VertexType fromVertex,
{
VertexType toVertex, int weight)
delete [ ] vertices;
{
for(int i = 0; i < maxVertices; i++) int row;
delete [ ] edges[i]; int column;
delete [ ] edges;
delete [ ] marks; row = IndexIs(vertices, fromVertex);
} col = IndexIs(vertices, toVertex);
edges[row][col] = weight; (continues)
}
template<class VertexType>
int GraphType<VertexType>::WeightIs(VertexType fromVertex,
VertexType toVertex) {
int row;
int column;
row = IndexIs(vertices, fromVertex);
col = IndexIs(vertices, toVertex);
return edges[row][col];
}

Pseudocode for creating Adjacency matrix

1. Create a matrix A of size NxN and initialise it with zero.
2. Iterate over each given edge of the form (u,v) and assign 1 to A[u][v]. Also,
If graph is undirected then assign 1 to A[v][u].
Review Questions
1. Draw a directed graph with five vertices and seven edges. Exactly one of the
edges should be a loop, and do not have any multiple edges.
2. Draw an undirected graph with five edges and four vertices. The vertices
should be called v1, v2, v3 and v4--and there must be a path of length three
from v1 to v4. Draw a squiggly line along this path from v1 to v4.
3. Draw the edge lists that correspond to the graph from the previous question.
4. What are the benefits of using an external iterator as opposed to an internal
iterator?
Traversal
GRAPH TRAVERSAL

• A graph traversal is a systematic way of visiting the

nodes in a specific order .
There are two types of graph traversal namely
• Breadth First Search
• Depth First Search
Breadth First Search(BFS)

• BFS of a graph G starts from an unvisited vertex u.

• BFS uses a queue data structure to keep track of the order of nodes whose
adjacent nodes are to be visited.
Steps
• Choose any node in the graph, designate it as source node and mark it as
visited.
• Using the adjacency matrix of the graph find all the unvisited adjacent
nodes to the search node and enqueue them into the queue Q
• Then the node is dequeued from the queue. Mark that node as visited and
designate it as the new search node.
• Repeat step 2 and 3 using the new search node.
• This process continues until the queue Q which keeps track of the adjacent
nodes is empty.
 Breadth First Search(BFS)

Breadth-First Search Algorithm:

STEPS:
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 non-visited adjacent vertices of the vertex which is at front of
the Queue and insert them into the Queue.
Step 4 - When there is no new vertex to be visited from the vertex which is at front
of the Queue then delete that vertex.
Step 5 - Repeat steps 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
Breadth First Search(BFS) Algorithm
Example 1

• Let A be the source vertex. Mark it as visited.

• Find the adjacent unvisited vertices of A and enqueue it into the queue.
Here B and C are adjacent nodes of A and B and C are enqueued
 Example 1(continued)

• Then the vertex B is dequeued and its adjacency vertices C and D are
taken from the adjacency matrix for enqueuing. Since vertex C is already
in the queue, vertex D alone is enqueue

Here B is dequeued and D is enqueued

• Then the vertex C is dequeued and its adjacent vertices A, B and D are
found out. Since the vertices A and B are already visited and vertex D is
also in the queue, no enqueue operation takes place.
Continued-
 EXAMPLE-2
Breadth-First Search Algorithm:
Continued-
Continued-
Continued-
Continued-
Features of Breadth-First Search Algorithm:
• Space complexity
• In the breadth-first search algorithm, all the nodes at a particular level must
be saved until their child nodes in the next level have been generated.
• The space complexity is therefore proportional to the number of nodes at the
deepest level of the graph. Given a graph with branching factor b (number
of children at each node) and depth d, the asymptotic space complexity is
the number of nodes at the deepest level O(bd).
• Time complexity
• In the worst case, breadth-first search has to traverse through all paths to all
possible nodes, thus the time complexity of this algorithm asymptotically
approaches O(bd).
• However, the time complexity can also be expressed as O( | E | + | V | ),
since every vertex and every edge will be explored in the worst case.
Application of BFS
• GPS Navigation systems
• Computer Networks
• Face book
 Applications of Breadth-First Search
Algorithm:

• Breadth-first search can be used to solve many problems such as:

• Finding all connected components in a graph G.
• Finding all nodes within an individual connected component.
• Finding the shortest path between two nodes, u and v, of an unweighted
graph.
• Finding the shortest path between two nodes, u and v, of a weighted graph .
Depth First Search (DFS)
• DFS works by selecting one vertex V of G as a start vertex; V is marked visited. Then each
unvisited vertex adjacent to V is searched in turn using DFS recursively.
Steps
• Choose any node in the graph. Designate it as the search node and mark it as
visited.
• Using the adjacency matrix of the graph, find a node adjacent to the search node
that has not be visited yet. Designate this as the new search node and mark it as
visited.
• Repeat step 2 using the new search node. If no nodes satisfying (2) can be found
return to the previous search node and continue from there.
• When a return to the previous search node in (3) is impossible, the search from
the originally chosen search node is complete.
• If the graph still contains unvisited nodes, choose any node that has not been visited and repeat
step 1 through 4.
Depth-first Search Algorithm:
• The depth-first search algorithm progresses by expanding the starting node of G
and then going deeper and deeper until the goal node is found, or until a node that
has no children is encountered. When a dead-end is reached, the algorithm
backtracks, returning to the most recent node that has not been completely
explored.
• In other words, depth-first search begins at a starting node A which becomes the
current node. Then, it examines each node N along a path P which begins at A. That
is, we process a neighbor of A, then a neighbor of neighbor of A, and so on.
Depth-first Search Algorithm:
• During the execution of the algorithm, if we reach a path that has a node N that has
already been processed, then we backtrack to the current node. Otherwise, the
unvisited (unprocessed) node becomes the current node.
• This technique is used for searching a vertex in a graph.
• It produces a spanning tree as a final result.
• Spanning tree is a graph without any loops.
• Here we use Stack data structure with maximum size of total number of vertices in
the graph.
Depth-first Search Algorithm:
 EXAMPLE-1
Depth-first Search Algorithm:
Consider the graph and find the spanning tree,
Depth-first Search Algorithm:
Depth-first Search Algorithm:
Depth-first Search Algorithm:
FS-iterative (G, s): //Where G is graph and s is source vertex
let S be stack
S.push( s ) //Inserting s in stack
mark s as visited.
while ( S is not empty):
//Pop a vertex from stack to visit next
v = S.top( )
S.pop( )
//Push all the neighbours of v in stack that are not visited
for all neighbours w of v in Graph G:
if w is not visited :
S.push( w )
mark w as visited
DFS-recursive(G, s):
mark s as visited
for all neighbours w of s in Graph G:
if w is not visited:
DFS-recursive(G, w)
Features of Depth-First Search Algorithm
Space complexity The space complexity of a depth-first search is lower than that
of a breadth-first search.
Time complexity The time complexity of a depth-first search is proportional to the
number of vertices plus the number of edges in the graphs that are traversed. The
time complexity can be
given as (O(|V| + |E|)).
Completeness Depth-first search is said to be a complete algorithm. If there is a
solution, depth-first search will find it regardless of the kind of graph. But in case
of an infinite graph, where there is no possible solution, it will diverge.
Applications of DFS
• Detecting cycle in a graph
• Path Finding
• Solving puzzles with only one solution, such as mazes
Applications of Depth-First Search Algorithm
Depth-first search is useful for:
• Finding a path between two specified nodes, u and v, of an unweighted
graph.
• Finding a path between two specified nodes, u and v, of a weighted
graph.
• Finding whether a graph is connected or not.
• Computing the spanning tree of a connected graph.
Exercise
Find BFS and DFS Traversal ordering of nodes for the following
graph.
Topological sorting
Ordering a graph
• Suppose we have a directed acyclic graph (DAG) of
courses, and we want to find an order in which the courses
can be taken.
• Must take all prereqs before you can take a given course.
Example:
• [142, 143, 140, 154, 341, 374, 331, 403, 311, 332, 344,
312, 351, 333, 352, 373, 414, 410, 417, 413, 415]
• There might be more than one allowable ordering.
• How can we find a valid ordering of the vertices?
31 37 37 41
1 14 4 3 4
33 35 35
31 34 3 1 2 41
2 2 33
4 33 34 14
3 41 41 7
1 1 0
40 14 3
15 0 41
3 2
4 5
Topological Sort
• topological sort: Given a digraph G = (V, E), a total
ordering of G's vertices such that for every edge (v, w) in E,
vertex v precedes w in the ordering. Examples:
• determining the order to recalculate updated cells in a
spreadsheet
• finding an order to recompile files that have dependencies
• (any problem of finding an order to perform tasks with dependencies)
37 41
31 37
4 4
1 14 35 35 3
33 3
31 34 1 2
2 41
2 4 33 33
34 14 7
1 3 41
1 0 41
40 14 3
15 0 41
3 2
4 5
Topo sort example
• How many valid topological sort orderings can you find for
the vertices in the graph below?
• [A, B, C, D, E, F], [A, B, C, D, F, E],
• [A, B, D, C, E, F], [A, B, D, C, F, E], C
• [B, A, C, D, E, F], [B, A, C, D, F, E], F
E
• [B, A, D, C, E, F], [B, A, D, C, F, E], B
• [B, C, A, D, E, F], [B, C, A, D, F, E],
• ... D

• What if there were a new vertex G unconnected to the others?

Topo sort: Algorithm 1
• function topologicalSort():
• ordering := { }.
• Repeat until graph is empty:
• Find a vertex v with in-degree of 0 (no incoming edges).
• (If there is no such vertex, the graph cannot be sorted; stop.)
• Delete v and all of its
outgoing edges from the graph. C
• ordering += v .
F
B E

A
Topo sort example
• function topologicalSort():
• ordering := { }.
• Repeat until graph is empty:
• Find a vertex v with in-degree of 0 (no incoming edges).
• (If there is no such vertex, the graph cannot be sorted; stop.)
• Delete v and all of its
outgoing edges from the graph. C
• ordering += v .
F
B E
• ordering = { B }

A
Topo sort example
• function topologicalSort():
• ordering := { }.
• Repeat until graph is empty:
• Find a vertex v with in-degree of 0 (no incoming edges).
• (If there is no such vertex, the graph cannot be sorted; stop.)
• Delete v and all of its
outgoing edges from the graph. C
• ordering += v .
F
B E
• ordering = { B, C }

A
Topo sort example
• function topologicalSort():
• ordering := { }.
• Repeat until graph is empty:
• Find a vertex v with in-degree of 0 (no incoming edges).
• (If there is no such vertex, the graph cannot be sorted; stop.)
• Delete v and all of its
outgoing edges from the graph. C
• ordering += v .
F
B E
• ordering = { B, C, A }

A
Topo sort example
• function topologicalSort():
• ordering := { }.
• Repeat until graph is empty:
• Find a vertex v with in-degree of 0 (no incoming edges).
• (If there is no such vertex, the graph cannot be sorted; stop.)
• Delete v and all of its
outgoing edges from the graph. C
• ordering += v .
F
B E
• ordering = { B, C, A, D }

A
Topo sort example
• function topologicalSort():
• ordering := { }.
• Repeat until graph is empty:
• Find a vertex v with in-degree of 0 (no incoming edges).
• (If there is no such vertex, the graph cannot be sorted; stop.)
• Delete v and all of its
outgoing edges from the graph. C
• ordering += v .
F
B E
• ordering = { B, C, A, D, F }

A
Topo sort example
• function topologicalSort():
• ordering := { }.
• Repeat until graph is empty:
• Find a vertex v with in-degree of 0 (no incoming edges).
• (If there is no such vertex, the graph cannot be sorted; stop.)
• Delete v and all of its
outgoing edges from the graph. C
• ordering += v .
F
B E
• ordering = { B, C, A, D, F, E }

A
Revised algorithm
• We don't want to literally delete vertices and edges from
the graph while trying to topological sort it; so let's revise
the algorithm:
• map := {each vertex → its in-degree}.
• queue := {all vertices with in-degree = 0}.
• ordering := { }.
• Repeat until queue is empty:
• Dequeue the first vertex v from the queue.
• ordering += v.
• Decrease the in-degree of all v's neighbors by 1 in the map.
• queue += {any neighbors whose in-degree is now 0}.
• If all vertices are processed, success.
Otherwise, there is a cycle.
Topo sort example 2
• function topologicalSort():
• map := {each vertex → its in-degree}. C
• queue := {all vertices with in-degree = 0}. F
• ordering := { }. B E
• Repeat until queue is empty:
• Dequeue the first vertex v from the queue.
• ordering += v.
D
• Decrease the in-degree of all v's
neighbors by 1 in the map. A
• queue += {any neighbors whose in-degree is now 0}.

• map := { A=0, B=0, C=1, D=2, E=2, F=2 }

• queue := { B, A }
• ordering := { }
Topo sort example 2
• function topologicalSort():
• map := {each vertex → its in-degree}. C
• queue := {all vertices with in-degree = 0}. F
• ordering := { }. B E
• Repeat until queue is empty:
• Dequeue the first vertex v from the queue. // B
• ordering += v.
D
• Decrease the in-degree of all v's // C, D
neighbors by 1 in the map. A
• queue += {any neighbors whose in-degree is now 0}.

• map := { A=0, B=0, C=0, D=1, E=2, F=2 }

• queue := { A, C }
• ordering := { B }
Topo sort example 2
• function topologicalSort():
• map := {each vertex → its in-degree}. C
• queue := {all vertices with in-degree = 0}. F
• ordering := { }. B E
• Repeat until queue is empty:
• Dequeue the first vertex v from the queue. // A
• ordering += v.
D
• Decrease the in-degree of all v's // D
neighbors by 1 in the map. A
• queue += {any neighbors whose in-degree is now 0}.

• map := { A=0, B=0, C=0, D=0, E=2, F=2 }

• queue := { C, D }
• ordering := { B, A }
Topo sort example 2
• function topologicalSort():
• map := {each vertex → its in-degree}. C
• queue := {all vertices with in-degree = 0}. F
• ordering := { }. B E
• Repeat until queue is empty:
• Dequeue the first vertex v from the queue. // C
• ordering += v.
D
• Decrease the in-degree of all v's // E, F
neighbors by 1 in the map. A
• queue += {any neighbors whose in-degree is now 0}.

• map := { A=0, B=0, C=0, D=0, E=1, F=1 }

• queue := { D }
• ordering := { B, A, C }
Topo sort example 2
• function topologicalSort():
• map := {each vertex → its in-degree}. C
• queue := {all vertices with in-degree = 0}. F
• ordering := { }. B E
• Repeat until queue is empty:
• Dequeue the first vertex v from the queue. // D
• ordering += v.
D
• Decrease the in-degree of all v's // F, E
neighbors by 1 in the map. A
• queue += {any neighbors whose in-degree is now 0}.

• map := { A=0, B=0, C=0, D=0, E=0, F=0 }

• queue := { F, E }
• ordering := { B, A, C, D }
Topo sort example 2
• function topologicalSort():
• map := {each vertex → its in-degree}. C
• queue := {all vertices with in-degree = 0}. F
• ordering := { }. B E
• Repeat until queue is empty:
• Dequeue the first vertex v from the queue. // F
• ordering += v.
D
• Decrease the in-degree of all v's // none
neighbors by 1 in the map. A
• queue += {any neighbors whose in-degree is now 0}.

• map := { A=0, B=0, C=0, D=0, E=0, F=0 }

• queue := { E }
• ordering := { B, A, C, D, F }
Topo sort example 2
• function topologicalSort():
• map := {each vertex → its in-degree}. C
• queue := {all vertices with in-degree = 0}. F
• ordering := { }. B E
• Repeat until queue is empty:
• Dequeue the first vertex v from the queue. // E
• ordering += v.
D
• Decrease the in-degree of all v's // none
neighbors by 1 in the map. A
• queue += {any neighbors whose in-degree is now 0}.

• map := { A=0, B=0, C=0, D=0, E=0, F=0 }

• queue := { }
• ordering := { B, A, C, D, F, E }
Topo sort runtime
• What is the runtime of our topological sort algorithm?
• (with an "adjacency map" graph internal representation)

• function topologicalSort():
• map := {each vertex → its in-degree}. // O(V)
• queue := {all vertices with in-degree = 0}.
• ordering := { }.
• Repeat until queue is empty: // O(V)
• Dequeue the first vertex v from the queue. // O(1)
• ordering += v. // O(1)
• Decrease the in-degree of all v's // O(E) for all passes
neighbors by 1 in the map.
• queue += {any neighbors whose in-degree is now 0}.

• Overall: O(V + E) ; essentially O(V) time on a sparse graph (fast!)

Review Questions
1.Topological sort can be applied to which of the following graphs?
a) Undirected Cyclic Graphs b) Directed Cyclic Graphs
c) Undirected Acyclic Graphs d) Directed Acyclic Graphs

2. Most Efficient Time Complexity of Topological Sorting is? (V – number of vertices, E – number of
edges)
a) O(V + E) b) O(V) c) O(E) d) O(V*E)

3. In most of the cases, topological sort starts from a node which has ___
a) Maximum Degree b) Minimum Degree c) Any degree d) Zero Degree

4. Topological sort of a Directed Acyclic graph is?

a) Always unique b) Always Not unique c) Sometimes unique and sometimes not unique d) Always
unique if graph has even number of vertices
Minimum Spanning Tree
Introduction
Spanning Tree
• A tree (i.e., connected, acyclic graph) which contains all the
vertices of the graph
Minimum Spanning Tree
• Spanning tree with the minimum sum of weights
• The minimum spanning tree is a tree because it is acyclic, it
is spanning because it covers every vertex, and it
is minimum because it covers with minimum cost.
8 7
b c d
4 9
2
a 11 i 4 14 e
7 6
8 10
g g f
1 2
Properties of Minimum Spanning Trees
• Minimum spanning tree is not unique

• MST has no cycles – see why:

-We can take out an edge of a cycle, and still have the vertices
connected while reducing the cost
• # of edges in a MST:
|V| - 1
 Applications of MST

Minimum spanning tree has direct application in the design of networks.

It is used in algorithms approximating the travelling salesman problem,
multi-terminal minimum cut problem and minimum-cost weighted
perfect matching. Other practical applications are:

1.Cluster Analysis
2.Handwriting recognition
3.Image segmentation
Applications of MST

• Find the least expensive way to connect a set of cities, terminals,

computers, etc.
 Example
Problem b
8
c
7
d
• A town has a set of houses 4
2
9

and a set of roads a 11 i 4 14 e

• A road connects 2 and only 8
7 6
10
2 houses h
1
g
2
f

• A road connecting houses u and v has a repair

cost w(u, v)

Goal: Repair enough (and no more) roads such that:

1. Everyone stays connected
i.e., can reach every house from all other houses
2. Total repair cost is minimum
Minimum Spanning Trees
• A connected, undirected graph:
-Vertices = houses, Edges = roads
• A weight w(u, v) on each edge (u, v) in E
8 7
Find T ⊆ E such that: b c d
4 9
2
1. T connects all vertices a i 4 e

2. w(T) = Σ(u,v)T w(u, v) is h

1
g
2
f

minimized
Growing a MST – Generic Approach
• Grow a set A of edges (initially
8 7
empty) b c d
4 9
2
• Incrementally add edges to A a 11 i 14 e
4
such that they would belong 8
7 6
10
h g f
to a MST 1 2

Idea: add only “safe” edges

–An edge (u, v) is safe for A if
and only if A ∪ {(u, v)} is also a
subset of some MST
Generic MST algorithm
1. A ← ∅
2. while A is not a spanning tree
3. do find an edge (u, v) that is safe for A
8 7
b c d
4. A ← A ∪ {(u, v)} 4 9
2
5. return A a 11 i 4 14 e
7 6
8 10
h g f
1 2

• How do we find safe edges?

Finding Safe Edges
8 7 V-S
b c d
• Let’s look at edge (h, g) 4
2
9

a 11 i 14 e
- Is it safe for A initially? 7 6
4
8 10
• Later on: S h
1
g
2
f

- Let S ⊂ V be any set of vertices that includes h but not g (so

that g is in V - S)
- In any MST, there has to be one edge (at least) that connects S
with V - S
- Why not choose the edge with minimum weight (h,g)?
Prim’s Algorithm
One node is picked as a root and an edge is added (i.e) an associated
vertex is added to the tree, until all the vertices are present in the tree
with |V| - 1 edges
i)One node is picked as a root node (u) from the given connected
graph.
ii)At each stage choose a new vertex v from u, by considering an edge
(u,v) with minimum cost among all edges from u, where u is already
in the tree ad v is not in the tree.
iii)The prims algorithm table is constructed with three parameters.
cost. They are
Prim’s Algorithm
✔known – known vertex i.e., processed vertex is indicated by 1.
Unknown vertex is indicated by zero.
✔ dv - Weight of the shortest arc connecting v to the known vertex.
✔ pv - It contains last vertex (i.e.,) current vertex to cause a change
in dv.

iv. After selecting the vertex v, the update rule is applied for each
unknown w adjacent to v. The rule is dw = min (dw , Cw,v), that is more
than one path exist between v to w then d w is updated with minimum
cost.
Prim’s Algorithm Example
1.v1 is selected as initial node in the
spanning tree and construct initial
configuration of the table.
v Known dv pv

V1 0 0 0

V2 0 ∞ 0

V3 0 ∞ 0

V4 0 ∞ 0

V5 0 ∞ 0

V6 0 ∞ 0

V7 0 ∞ 0
 Prim’s Algorithm Example
2.v1 is declared as known vertex. Then its adjacent vertices v2, v3, v4 are updated.
v Known dv pv
T[v2].dist = min(T[v2].dist, Cv1,v2) = min (∞ ,2) = 2
V1 1 0 0
T[v3].dist = min(T[v3].dist, Cv1,v3) = min (∞ ,4) = 2
V2 0 2 V1

T[v4].dist = min(T[v4].dist, Cv1,v4) = min (∞ ,1) = 2 V3 V1

0 4

V4 0 1 V1

V5 0 ∞ 0

V6 0 ∞ 0

V7 0 ∞ 0
 Prim’s Algorithm Example
3. Among all adjacent vertices V2, V3, V4. V1 -> V4 distance is small. So V4 is selected and
declared as known vertex. Its adjacent vertices distance are updated.
• V1 is not examined because it is known vertex.
• No change in V2 , because it has dv = 2 and the edge cost from V 4 -> V2 = 3.

T[v3].dist = min(T[v3].dist, Cv4,v3) = min (4 ,2) = 2

v Known dv pv

T[v5].dist = min(T[v5].dist, Cv4,v5) = min (∞ ,7) = 7 V1 1 0 0

T[v6].dist = min(T[v6].dist, Cv4,v6 ) = min (∞ ,8) = 8 V2 0 2 0

V3 0 2 0
T[v7].dist = min(T[v7].dist, Cv4,v7 ) = min (∞ ,4) = 4
V4 1 1 0

V5 0 7 0

V6 0 8 0

V7 0 4 0
 Prim’s Algorithm Example
4. Among all either we can select v2, or
v3 whose dv = 2, smallest among v5, v6 and v7.
• v2 is declared as known vertex.
• Its adjacent vertices are v1, v4 and v5. v1, v Known dv pv

v4 V1 1 0 0
are known vertex, no change in their dv V2 V1
1 2
value.
T[v5].dist = min(T[v5].dist, Cv2,v5) = min V3 0 2 V4

(7 ,10) = 7 V4 1 1 V1

V5 0 7 V4

V6 0 8 V4

V7 0 4 V4
 Prim’s Algorithm Example
5. Among all vertices v3‟s dv value is lower so v3 is selected. v3‟s adjacent
vertices are v1, v4 and v6. No changes in v1 and v4.

T[v6].dist = min(T[v6].dist, Cv3,v6) = min (8 ,5) = 5

 Prim’s Algorithm Example
6. Among v5, v6, v7, v7‟s dv value is lesser, so v7 is selected. Its adjacent
vertices are v4, v4, and v6. No change in v4.
v Known dv pv

T[v5].dist = min(T[v5].dist, Cv7,v5) = min (7,6) = 6 V1 1 0 0

T[v6].dist = min(T[v6].dist, Cv7,v6) = min (5,1) = 1
V2 1 2 V1

V3 1 2 V4

V4 1 1 V1

V5 0 6 V7

V6 0 1 V7

V7 1 4 V4
 Prim’s Algorithm Example

7. Among v5 and v6, v6 is declared as known vertex. v6‟s adjacent vertices

are v3, v4, and v7, no change in dv value, all are known vertices
 Prim’s Algorithm Example
v Known dv pv

V1 1 0 0
8. Finally v5 is declared as known vertex. Its
adjacent vertices are v2, v4, and v7, no change in V2 1 2 V1

dv value, all are known vertices. V3 1 2 V4

V4 1 1 V1
The minimum cost of spanning tree is 16.
V5 1 6 V7

Algorithm Analysis V6 1 1 V7

The running time is O(|V|2) in case of adjacency V7 1 4 V4

list and O(|E| log |V|) in case of binary heap.

 Routine for prim’s Algorithm

void prims(Table T)
{
vertex v, w;
for( i=1; i<=Numvertex; i++) {
T[i]. known = False;
T[i] . Dist = Infinity;
T[i]. path = 0; }
for(;;) { //let v be the start vertex with the smallest distance T[v] . Dist = 0;
T[v]. known = true;
for each w adjacent to v if(!T[w] . known)
{
T[w] . Dist = Min(T[w]. Dist, Cv,w);

T[w]. path = v; } }
}
Exercise
Convert the graph given below to minimum spanning
tree using prims algorithm.
Review Questions

1. Consider a complete graph G with 4 vertices. The graph G has

____ spanning trees.
2. Every graph has ______Minimum Spanning Trees.
3. Prim’s Algorithm is preferred when the graph is ____and there
are ____number of edges in the graph.
4.The time complexity of prims algorithm when there are large
number of edges in the graph is ______.
Kruskal’s Algorithm

Input : Graph with V edges

Output : Minimum Spanning tree with V-1 edges

Step 1. Sort all the edges in non-decreasing order of their weight.

Step 2. Pick the smallest edge. Check if it forms a cycle with the
spanning tree formed so far. If cycle is not formed, include this
edge. Else, discard it.
Step 3. Repeat step#2 until there are (V-1) edges in the spanning
tree.
Example

3 4
2 3 4
4 5
2
9
5 6
1
1
12
8 10
7 8 9
7

The graph contains 9 vertices and 11 edges. So, the minimum spanning tree
formed will be having (9 – 1) = 8 edges.
 Weight Source Destination
Sort the weights of the graph 1 8 5
2 3 5
3 2 3
4 1 2
4 3 4
5 4 6
7 7 8
8 1 7
9 5 6
10 8 9
12 9 6
 Now pick all edges one by one from sorted list of edges

Weigh Source Destination

t

1 8 5
2 3 5
3 2 3
4 1 2
4 3 4
5 4 6
7 7 8
8 1 7
9 5 6
10 8 9
12 9 6
Weight Source Destination

1 8 5
2 3 5
3 2 3
4 1 2
4 3 4
5 4 6
7 7 8
8 1 7
9 5 6
10 8 9
12 9 6
Weight Source Destinatio
n

1 8 5
2 3 5
3 2 3
4 1 2
4 3 4
5 4 6
7 7 8
8 1 7
9 5 6
10 8 9
12 9 6
Weight Source Destination

1 8 5
2 3 5
3 2 3
4 1 2
4 3 4
5 4 6
7 7 8
8 1 7
9 5 6
10 8 9
12 9 6
Weight Source Destination

1 8 5
2 3 5
3 2 3
4 1 2
4 3 4
5 4 6
7 7 8
8 1 7
9 5 6
10 8 9
12 9 6
Weight Sourc Destination
e

1 8 5
2 3 5
3 2 3
4 1 2
4 3 4
5 4 6
7 7 8
8 1 7
9 5 6
10 8 9
12 9 6
Weight Source Destinatio
n

1 8 5
2 3 5
3 2 3
4 1 2
4 3 4
5 4 6
7 7 8
8 1 7
9 5 6
10 8 9
12 9 6
Weigh Source Destinatio
t n

1 8 5
2 3 5
3 2 3
4 1 2
4 3 4
5 4 6
7 7 8 Cycle is formed because of weight 8. hence it is discarded.
8 1 7
9 5 6
10 8 9
12 9 6
Weigh Source Destination
t

1 8 5
2 3 5
3 2 3
4 1 2
4 3 4
5 4 6
7 7 8
8 1 7
9 5 6 Cycle is formed because of weight 9. hence it is discarded .
10 8 9
12 9 6
Weight Source Destinatio
n

1 8 5
2 3 5
3 2 3
4 1 2
4 3 4
5 4 6
7 7 8
8 1 7
9 5 6 Cycle is formed because of weight 12. hence it is discarded .
10 8 9
12 9 6
Weight Source Destination

1 8 5
2 3 5
3 2 3
4 1 2
4 3 4
5 4 6
7 7 8
8 1 7
9 5 6
10 8 9
Cycle is formed because of weight 12. hence it is discarded.
12 9 6
 3 4
2 3 4
5
4
2
6
1 5

1
10
7 8 9
7

Minimum Spanning tree generated by Kruskal’s algorithm

Kruskal’s Algorithm
void kruskal( graph G ) {
int EdgesAccepted;
DisjSet S;
PriorityQueue H; vertex u, v; SetType uset, vset; Edge e;
Initialize( S ); // form a single node tree
ReadGraphIntoHeapArray( G, H );
BuildHeap( H );
EdgesAccepted = 0;
while( EdgesAccepted < NumVertex-1 )
{
e = DeleteMin( H ); // Selection of minimum edge
uset = Find( u, S );
vset = Find( v, S );
if( uset != vset ) {
/* accept the edge */ EdgesAccepted++; SetUnion( S, uset, vset );
} }}
Exercise
Convert the graph given below to minimum spanning tree using
kruskals algorithm.
Review Questions

1.Kruskal’s Algorithm is preferred when the graph is ____and there

are ____number of edges in the graph.
2.If all the edge weights are not distinct, then prims and kruskals
algorithms _____ always produce the same MST.
3. The cost of both the MSTs produced by prims and kruskals
algorithm would always be _____.
4. Let ‘m’ and ‘n’ be the number of edges and vertices in a graph G,
respectively. The time complexity of the kruskals algorithm is
______.
Shortest Path Problem
Single-Source Shortest Path Problem - The problem of finding
shortest paths from a source vertex v to all other vertices in the
graph.
Applications
- Maps (Map Quest, Google Maps)
- Routing Systems
Dijkstra's algorithm
Dijkstra's algorithm - is a solution to the single-source shortest
path problem in graph theory.

Works on both directed and undirected graphs. However, all

edges must have nonnegative weights.

Input: Weighted graph G={E,V} and source vertex v∈V, such

that all edge weights are nonnegative

Output: Lengths of shortest paths (or the shortest paths

themselves) from a given source vertex v∈V to all other vertices
Dijkstra's algorithm
Procedure
• It uses greedy technique.
• It proceeds in stages.
• It selects a vertex v, which has the smallest d v among all the unknown
vertices and declares the shortest path from s to v is known.
• The remainder consists of updating the value of dw.
• We should dw = dv + Cv, w, if the new value for dw would an improvement.
❖ Dijkstra’s algorithm can be implemented using list with a time complexity of
O(v2).
❖ When a binary heap is used for implementation then time complexity can be
reduced to O(E log V).
 DIJKSTRA’S ALGORITHM- Example

v Known dv pv

V1 1 0 0
V2 0 ∞ 0

V3 0 ∞ 0

V4 0 ∞ 0
V1 is taken as source
V5 0 ∞ 0

V6 0 ∞ 0

V7 0 ∞ 0
 DIJKSTRA’S ALGORITHM-Example

v Known dv pv

V1 1 0 0

V2 0 2 V1

V3 0 ∞ 0

V4 0 1 V1

V5 0 ∞ 0

2. Now V1 is known vertex, marked as 1. Its adjacent vertices are v 2, v4, pv and dv V6 0 ∞ 0

values are updated. V7 0 ∞ 0

T[v2].dist = Min(T[v2].dist,T[v1].dist + Cv1, v2)=Min(α, 0+2)=2

T[v4].dist = Min(T[v4].dist,T[v1].dist + Cv1, v2)=Min(α, 0+1)=1

DIJKSTRA’S ALGORITHM- Example
• 3. Select the vertex with minimum distance away v 2 and v4 . v4 is marked as known vertex. Its adjacent vertices are
v3, v5, v6 and v7 .
• T[v3]. dist = Min (T[v3].dist, T[v4].dist + Cv4, v3) = Min (α , 1+2) = 3
•
• T[v5]. dist = Min (T[v5].dist, T[v4].dist + Cv4, v5) = Min (α , 1+2) = 3
•
• T[v6]. dist = Min (T[v6].dist, T[v4].dist + Cv4, v6) = Min (α , 1+8) = 9
•
• T[v7]. dist = Min (T[v7].dist, T[v4].dist + Cv4, v7) = Min (α , 1+4) = 5
 DIJKSTRA’S ALGORITHM- Example

• 4. Select the vertex which is shortest distance from source v 1. v2 is smallest one. v2 is marked
as known vertex. Its adjacent vertices are v4 ad v5. The distance from v1 to v4 and v5 through
v2 is more comparing with previous value of dv. No change in dv and pv value.
v Known dv pv

V1 1 0 0

V2 1 2 V1

V3 0 3 V4

V4 1 1 V1

V5 0 3 V4

V6 0 9 V4

V7 0 5 V4
DIJKSTRA’S ALGORITHM- Example
• 5. Select the smallest vertex from source. v 3 and v5 are smallest one. Adjacent vertices for v 3 is v1 and v6. v1 is source
• there is no change in dv and pv
• T[v6]. dist = Min (T[v6].dist, T[v3].dist + Cv3, v6) = Min (9 , 3+5) = 8
• dv and pv values are updated. Adjacent vertices for v 5 is v7. No change in dv and pv value.
DIJKSTRA’S ALGORITHM- Example
• 6. Next smallest vertex v7. Its adjacent vertex is v6. T[v6]. dist = Min (T[v6].dist, T[v7].dist +
Cv7, v6) = Min (8 , 5+1) = 6
• dv and pv values are updated.
v Known dv pv

V1 1 0 0
V2 1 2 V1

V3 1 3 V4

V4 1 1 V1

V5 1 3 V4

V6 0 6 V7

V7 1 5 V4
DIJKSTRA’S ALGORITHM- Example
• 7. The last vertex v6 is declared as known. No adjacent vertices for v 6. No updation in the table.
• The shortest distance from source v1 to all vertices. v1 -> v2 = 2
• v1 -> v3 = 3 v1 -> v4 = 1 v1 -> v5 = 3 v1 -> v6 = 6 v1 -> v7 = 5

• Algorithm Analysis
•

• Time complexity of this algorithm

•

• O(|E| + |V|2 ) = O(|V|2 )

 Routine for prim’s Algorithm

void Dijkstra(Table T)
{
Vertex v, w; for( ; ;)
{
v = smallest unknown distance vertex;
if( v = = NotAVertex) break;
T[v]. kown = True;
for each w adjacent to v if(!T[w].known)
if(T[v].Dist + Cvw < T[w]. Dist)
{/* update w*/
Decrease(T[w]. Dist to T[v].Dist + Cvw);
T[w]. path = v;
}} }
Exercise
Using Dijkstra’s Algorithm, find the shortest distance from source
vertex ‘S’ to remaining vertices in the following graph
Review Questions

1. Dijkstra’s Algorithm is used to solve _____________ problems.

2. ___________is the most commonly used data structure for
implementing Dijkstra’s Algorithm.
3. __________ is the time complexity of Dijkstra's algorithm.
4. Dijkstra’s Algorithm cannot be applied on ______________
graph.
5. Dijkstra’s Algorithm is based on _______________ approach.
Applications of graphs
•Google maps uses graphs for building transportation systems, where
intersection of two(or more) roads are considered to be a vertex and the
road connecting two vertices is considered to be an edge, thus their
navigation system is based on the algorithm to calculate the shortest
path between two vertices.

•In Facebook, users are considered to be the vertices and if they are
friends then there is an edge running between them. Facebook’s Friend
suggestion algorithm uses graph theory. Facebook is an example
of undirected graph.
Applications of graphs
•In World Wide Web, web pages are considered to be the vertices.
There is an edge from a page u to other page v if there is a link of
page v on page u. This is an example of Directed graph. It was the
basic idea behind Google Page Ranking Algorithm.

•In Operating System, we come across the Resource Allocation

Graph where each process and resources are considered to be
vertices. Edges are drawn from resources to the allocated process, or
from requesting process to the requested resource. If this leads to
any formation of a cycle then a deadlock will occur.
Network Flow Problem
Introduction
A type of network optimization problem
Arise in many different contexts :

Networks: routing as many packets as possible on a given network.

Transportation: sending as many trucks as possible, where roads have
limits on the number of trucks per unit time
Bridges: destroying (?!) some bridges to disconnect s from t,
while minimizing the cost of destroying the bridges.
Problem
Settings: Given a directed graph G = (V, E), where each edge e is
associated with its capacity c(e) > 0.
Two special nodes source s and sink t are given (s ƒ= t).

Problem: Maximize the total amount of flow from s to t subject to two

constraints.
Flow on edge e doesn’t exceed c(e).
For every node v ƒ= s, t, incoming flow is equal to outgoing flow.
 Network Flow Example (from CLRS)

Capacities

Maximum flow (of 23 total

units)
Alternate Formulation: Minimum Cut
We want to remove some edges from the graph such that after removing the edges,
there is no path from s to t.
The cost of removing e is equal to its capacity c(e).
The minimum cut problem is to find a cut with minimum total cost.

Theorem: (maximum flow) = (minimum cut)

Minimum Cut Example

Capacities

Minimum Cut (red edges are

removed)
Flow Decomposition

Any valid flow can be decomposed into flow paths and circulations

– s → a → b → t: 11
– s → c → a → b → t: 1
– s → c → d → b → t: 7
– s → c → d → t: 4
Flow Decomposition

Given a weighted, directed graph G=(V,E)

Treat the edge weights as capacities
How much can we flow through the graph?

A B 11
7 H
3 5
2 12 6
9
C G 6
4 11
10 13
20 I
D 4 E
Flow Decomposition

Start flow at 0
“While there’s room for more flow, push more flow across the
network!”
While there’s some path from s to t, none of whose edges are saturated
Push more flow along the path until some edge is saturated

Called an “augmenting path”

How do we know there’s still room?

Construct a residual graph:

Same vertices.
Edge weights are the “leftover” capacity on the edges.
If there is a path s€t at all, then there is still room.
 Example1
Initial graph – no flow

B C
3 4
1
A D
2
4
2
2
E F

Flow /
Capacity
Example1

Include the residual capacities

0/2
B C
0/3 2
0/4
4
3 0/1
A 2 0/2 1 D
2 0/4
0/2 4
0/2
E F
2

Flow / Capacity
Residual Capacity
Example1

Augment along ABFD by 1 unit (which saturates BF)

0/2
B C
2
1/3 0/4
4
2 1/1
A 2 0/2 0 D
2 1/4
0/2 3
0/2
E F
2
Example1

Augment along ABEFD (which saturates BE and EF)

0/2
B C
3/3 2 0/4
4
0 1/1
A 0 2/2 0 D
2 3/4
0/2 2/2 1
E F
0

Flow / Capacity
Residual Capacity
Hash Functions
The total possible number of hash functions for n items assigned to m
positions in a table (n < m) is mn.
The number of perfect hash functions is equal to the number
(m−n )!
With 50 elements and a 100-position array, we would have a total of
10050 hash functions and about 1094 perfect hash functions (about 1 in a
million).
Most of the perfect hashes are impractical and cannot be expressed in a
simple formula.
Hash Functions(Contd...)
Division
Hash functions must guarantee that the value they produce is a valid index to the table
A fairly easy way to ensure this is to use modular division, and divide the keys by the size
of the table, so

h(K) = K mod TSize where TSize = sizeof(table)

This works best if the table size is a prime number, but if not, we can
use h(K) = (K mod p) mod TSize for a prime p > Tsize

However, nonprimes work well for the divisor provided they do not have any prime factors
less than 20.
The division method is frequently used when little is known about the keys
Hash Function Contd...
Folding
In folding, the keys are divided into parts which are then combined (or “folded”)
together and often transformed into the address.
Two types of folding are used, shift folding and boundary folding
In shift folding, the parts are placed underneath each other and then processed (for
example, by adding).
Using a Social Security number, say 123-45-6789, we can divide it into three parts -
123, 456, and 789 – and add them to get 1368.
This can then be divided modulo TSize to get the address
With boundary folding, the key is visualized as being written on a piece of paper
and folded on the boundaries between the parts.
Hash Functions Contd...
Folding (continued)
The result is that alternating parts of the key are reversed, so the Social Security
number part would be 123, 654, 789, totaling 1566.
As can be seen, in both versions, the key is divided into even length parts of
some fixed size, plus any leftover digits.
Then these are added together and the result is divided modulo the table size
Consequently this is very fast and efficient, especially if bit strings are used
instead of numbers.
With character strings, one approach is to exclusively-or the individual character
together and use the result.
In this way, h(“abcd”) = “a” ⋁ “b” ⋁ “c” ⋁ “d”
Hash Function Contd...
Folding (continued)
However, this is limited, because it will only generate values between 0 and
127.
A better approach is to use chunks of characters, where each chunk has as
many characters as bytes in an integer.
On the IBM PC, integers are often 2 bytes long, so h(“abcd”) = “ab” ⋁
“cd”, which would then be divided modulo Tsize.
Hash Function Contd...
Mid-Square Function
In the mid-square approach, the numeric value of the key is squared and the
middle part is extracted to serve as the address.
If the key is non-numeric, some type of preprocessing needs to be done to create a
numeric value, such as folding.
Since the entire key participates in generating the address, there is a better chance
of generating different addresses for different keys.
So if the key is 3121, 31212 = 9,740,641, and if the table has 1000 locations,
h(3121) = 406, which is the middle part of 31212.
In application, powers of two are more efficient for the table size and the middle
of the bit string of the square of the key is used.
Assuming a table size of 1024, 31212 is represented by the bit string
1001010 0101000010 1100001, and the key, 322, is in italics.
Hash Functions Contd...
Extraction
In the extraction approach, the address is derived by using a portion of the key.
Using the SSN 123-45-6789, we could use the first four digits, 1234, the last four
6789, or the first two combined with the last two 1289.
Other combinations are also possible, but each time only a portion of the key is
used.
With careful choice of digits, this may be sufficient for address generation.
For example, some universities give international students ID numbers beginning
with 999; ISBNs start with digits representing the publisher
So these could be excluded from the address generation if the nature
of the data is appropriately limited.
Hash Functions Contd...
Radix Transformation

With radix transformation, the key is transformed into a different base

For instance, if K is 345 in decimal, its value in base 9 is 423.
This result is then divided modulo TSize, and the resulting value becomes the
address top which K is hashed.
The drawback to this approach is collisions cannot be avoided.
For example, if TSize is 100, then although 345 and 245 in decimal will not
collide, 345 and 264 will because 264 is 323 in base nine.
Since 345 is 423, these two values will collide when divided modulo 100.
Hash Function Contd...
Universal Hash Functions
When little is known about the keys, a universal class of hash functions can be
used.
Functions are universal when a randomly chosen member of the class will be
expected to distribute a sample evenly, guaranteeing low collisions.
This idea was first considered by Larry Carter and Mark Wegman in 1979.
Instead of using a defined hash function, for which a bad set of keys may exist with
many collisions, we select a hash function randomly from a family of hash
functions! This is a real-time decision.
H is called universal if no distinct pair of keys are mapped to the same position in
the table by a function chosen at random from h with aprobability of 1 / Tsize.
This basically means there is one chance in TSize that two randomly chosen keys
collide when hashed with a randomly chosen function.
Hash Fuctions Contd...

Universal Hash Functions (continued)

– One example of such a class of functions is defined for a prime
number
p > |keys| and random numbers a and b.
H = {ha,b(K): ha,b(K) = ((aK+b) mod p) mod TSize and 0 ≤ a, b < p}

Another class of functions is for keys considered as sequences of bytes,

K = K0K1 … Kr-1
Hash Table

Constant time accesses!

A hash table is an array of some fixed size, usually a prime
number.
hash table
General idea:
0
hash function:

h(K)

…
key space (e.g., integers, strings)
TableSize –1
Hash Table

key space = integers 0

TableSize = 10 1
2
h(K) = K mod 10 3
Insert: 7, 18, 41, 94 4
5
6
7
8
9
Hash Table contd...

key space = integers

TableSize = 6 0
1
h(K) = K mod 6 2
Insert: 7, 18, 41, 34 3
4
5
Hash Table contd...

simple/fast to compute,
Avoid collisions
have keys distributed evenly among cells.
Collision Resolution
Collision: when two keys map to the same location in the hash table.
Two ways to resolve collisions:
Separate Chaining
Open Addressing (linear probing, quadratic probing, double hashing)

Open Addressing:

The efficiency of different open addressing techniques depends on the size of

the table and number of elements in the table.
 Collision Resolution contd...
● Open Addressing (continued)

Problem: -

Using the hash function ‘key mod 7’, insert the following sequence of keys in the hash
table-
50, 700, 76, 85, 92, 73 and 101
Use linear probing technique for collision resolution.

Solution-
The given sequence of keys will be inserted in the hash table as-
Contd...

Step-01:
● Draw an empty hash table.
● For the given hash function, the possible range of hash values is [0, 6].
● So, draw an empty hash table consisting of 7 buckets as-
Contd...
Step-02:

● Insert the given keys in the hash table one by one.

● The first key to be inserted in the hash table = 50.
● Bucket of the hash table to which key 50 maps = 50 mod 7 = 1.
● So, key 50 will be inserted in bucket-1 of the hash table as-
Contd...

Step-03:

● The next key to be inserted in the hash table = 700.

● Bucket of the hash table to which key 700 maps = 700 mod 7 = 0.
● So, key 700 will be inserted in bucket-0 of the hash table as-
Step-04:

● The next key to be inserted in the hash table = 76.

● Bucket of the hash table to which key 76 maps = 76 mod 7 = 6.
● So, key 76 will be inserted in bucket-6 of the hash table as-
Step-05:
The next key to be inserted in the hash table = 85.
● Bucket of the hash table to which key 85 maps = 85 mod 7 = 1.
● Since bucket-1 is already occupied, so collision occurs.
● To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found.
● The first empty bucket is bucket-2.
● So, key 85 will be inserted in bucket-2 of the hash table as-
Step-06:

● The next key to be inserted in the hash table = 92.

● Bucket of the hash table to which key 92 maps = 92 mod 7 = 1.
● Since bucket-1 is already occupied, so collision occurs.
● To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found.
● The first empty bucket is bucket-3.
● So, key 92 will be inserted in bucket-3 of the hash table as-
Step-07:

● The next key to be inserted in the hash table = 73.

● Bucket of the hash table to which key 73 maps = 73 mod 7 = 3.
● Since bucket-3 is already occupied, so collision occurs.
● To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found.
● The first empty bucket is bucket-4.
● So, key 73 will be inserted in bucket-4 of the hash table as-
Contd...

Step -08:

● The next key to be inserted in the hash table = 101.

● Bucket of the hash table to which key 101 maps = 101 mod 7 = 3.
● Since bucket-3 is already occupied, so collision occurs.
● To handle the collision, linear probing technique keeps probing linearly until an empty bucket is found.
● The first empty bucket is bucket-5.
● So, key 101 will be inserted in bucket-5 of the hash table as-
Collision Resolution contd...
Chaining
In chaining, the keys are not stored in the table, but in the info portion of a linked
list of nodes associated with each table position.
This technique is called separate chaining, and the table is called a scatter table.
This was the table never overflows, as the lists are extended when new keys arrive,
as can be seen in Figure.
This is very fast for short lists, but as they increase in size, performance can
degrade sharply.
Gains in performance can be made if the lists are ordered so unsuccessful searches
don’t traverse the entire list, or by using self- organizing linked lists.
This approach requires additional space for the pointers, so if there are a large
number of keys involved, space requirements can be high.
Collision Resolution Contd...
Bucket Addressing
Yet another approach to collision handling is to store all the colliding
elements in the same position in the table.
This is done by allocating a block of space, called a bucket, with each
address
Each bucket is capable of storing multiple items.
However, even with buckets, we cannot avoid collisions, because buckets can
fill up, requiring items to be stored elsewhere.
If open addressing is incorporated into the design, the item can be stored in
the next bucket if space is available, using linear probing.
 Deletion
Bucket Addressing (continued)

Collisions can be stored in an overflow area, in which case the bucket

includes a field to indicate if a search should consider that area or not
If used with chaining, the field could indicate the beginning of the list in the overflow
area associated with the bucket.
 Deletion contd...
A solution to this is to leave the deleted keys in the table with some type of indicator that the
keys are not valid.
This way, searches for elements won’t terminate prematurely.
When new keys are inserted, they can overwrite the marked keys.
Deletion contd...

A drawback is if the table becomes overloaded with deleted records, slowing

down search times, because open addressing requires testing each element
● So the table needs to be purged periodically by moving undeleted
elements to cells occupied by deleted elements
● Those cells containing deleted elements not overwritten can
then be marked as available
Perfect Hash Functions
All the examples we’ve considered to this point have assumed the data being hashed
is not completely known.
Consequently, the hashing that took place only coincidentally turned out to be ideal
in that collisions were avoided.
The majority of the time collisions had to be resolved because of conflicting keys.
In addition, the number of keys is usually not known in advance, so the table size
had to be large enough.
Table size also played a role in the number of collisions; larger tables had fewer
collisions if the hash took this into account.
All these factors were the result of not knowing ahead of time about the body of
data to be hashed.
Perfect Hash Functions...
Therefore the hash function was developed first and then the data was
processed into the table.
In a number of cases, though, the data is known in advance, and the hash
function can be derived after the fact.
This function may turn out to be a perfect hash if items hash on the first try.
Additionally, if the function uses only as many cells as are available in the
table with no empty cells left after the hash, it is called a minimal perfect
hash function.
Minimal perfect hash functions avoid the need for collision resolution and
also avoid wasting table space.
Perfect hash functions contd...
Processing fixed bodies of data occurs frequently in a variety of applications.
Dictionaries and tables of reserved words in compilers are among several
examples.
Creating perfect hash functions requires a great deal of work.
Such functions are rare; as we saw earlier, for 50 elements in a 100-position
array, only 1 function in a million is perfect.
All the other functions will lead to collisions.

Book has examples on Cichelli’s Method and FHCD for minimal perfect
hash functions for small number of strings.
Hash Functions for Extendible Files

While rehashing adds flexibility to hashing by allowing for dynamic

expansion of the has table, it has drawbacks.
In particular, the entire process comes to a halt while the new table(s) are
created and the values rehashed to the new table.
The time required for this may be unacceptable in many cases.
An alternative approach is to expand the table rather than replace it, and only
allow for local rehashing and local changes.
This approach won’t work with arrays, because expanding an array can’t be
done by simply adding locations to the end
However, it can be managed if the data is kept in a file.
 Hash Functions for Extendible Files
(continued)
There are some hashing techniques that take into account variable sizes of tables
or files.
These fall into two groups: directory and directoryless.
In directory schemes, a directory or index of keys controls access to the keys
themselves.
There are a number of techniques that fall into this category.
Expandable hashing, developed by Gary D. Knott in 1971
Dynamic hashing, developed by Per-Âke Larson in 1978
Extendible hashing, developed by Ronald Fagin and others in 1979
All of these distribute keys among buckets in similar ways
The structure of the directory or index is the main difference Skipping details, see
book for more.
 Review Questions

1. The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10
using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant
hash table?
2. Consider the table below which shows the cost of allocating 5 jobs to 5 machines.

Machine
A B C D EF
Job 1 22 30 26 16 2
2 27 29 28 20 32
3 33 25 21 29 23
4 24 24 30 19 26
5 30 33 32 37 31
Which jobs should be allocated to which machines so as to minimise the total cost?
Collision
If two more keys hashes to the same index, the corresponding records cannot be
stored in the same location. This condition is known as collision.
Characteristics of Good Hashing Function:
 It should be Simple to compute.
 Number of Collision should be less while placing record in Hash Table.
 Hash function with no collision is called as
Perfect hash function.
 Hash Function should produce keys which are distributed uniformly in hash
table.
 The hash function should depend upon every bit of the key. Thus the hash
function that simply extracts the portion of a key is not suitable
Review Questions
What is the best definition of a collision in a hash table?
a) Two entries are identical except for their keys
b) Two entries with different data have the exact same key
c) Two entries with different keys have the same exact hash value
d) Two entries with the exact same key have different hash values

What is the search complexity in direct addressing?

a. O(n)
b. O(logn)
c. O(nlogn)
d. O(1)
Collision Resolution Strategies / Techniques (CRT)
If collision occurs, it should be handled or overcome by applying some
technique. Such technique is called CRT.
There are a number of collision resolution techniques, but the most
popular are:
 Separate chaining (Open Hashing)
 Open addressing. (Closed Hashing)
1. Linear Probing
2. Quadratic Probing
3. Double Hashing
Separate Chaining
Separate chaining (Open Hashing)
• Open addressing / probing is carried out for insertion into fixed size
hash tables (hash tables with 1 or more buckets).

• If the index given by the hash function is occupied, then increment

the table position by some number.
Separate chaining (Open Hashing)

• Implemented using singly linked list concept.

• Pointer (ptr) field is added to each record.
• When collision occurs, a separate chaining is maintained for
colliding data.
• Element inserted in front of the list.
H (key) =key % table size
Two major operations are there:-
 Insert
 Find
Separate chaining (Open Hashing)
Separate chaining (Open Hashing)
Separate chaining (Open Hashing)
Separate chaining (Open Hashing)
Separate chaining (Open Hashing)-
Example
if two keys map to same value, chained together, Initial Hash Table
with size=10
chaining of elements will be done by SLL

Initial Table: Size =10

Hashing operation is mod operation
Separate chaining (Open Hashing)
Separate chaining (Open Hashing)
Separate chaining (Open Hashing)
Separate chaining (Open Hashing)
Separate chaining (Open Hashing)
Separate chaining (Open Hashing)

In simple chaining, load factor is the average number of elements

stored in a chain, and is given by the ratio of number of elements stored
to the number of slots in the array.
Separate chaining (Open Hashing)

Advantages
1. More number of elements can be inserted using array of Link List
Disadvantages
1. It requires more pointers, which occupies more memory space.
2.Search takes time. Since it takes time to evaluate Hash Function and
also to traverse the List
Review Questions

What data organization method is used in hash tables?

a) Stack b) Array c) Linked list d) Queue

In a hash table of size 10, where is element 7 placed?

a) 6 b) 7 c) 17 d) 16

Which of the following operations are done in a hash table?

a) Insert only b) Search only c) Insert and search
d) Replace
Open Addressing
Open Addressing - Closed Hashing
Collision resolution technique: When collision occurs, alternative cells are tried
until empty cells are found.
Types:-
 Linear Probing
 Quadratic Probing
 Double Hashing
Hash function : H(key) = key % table size.
Insert Operation
1. To insert a key; Use the hash function to identify the list to which the element
should be inserted.
2. Then traverse the list to check whether the element is already present.
3. If exists, increment the count.
4. Else the new element is placed at the front of the list.
1.Linear Probing
Easiest method to handle collision. Apply the hash function
H (key) = key % table size
Hi(X)=(Hash(X)+F(i))mod Tablesize, where F(i)=i.
How to Probe?
first probe – given a key k, hash to H(key)
second probe – if H(key)+f(1) is occupied, try H(key)+f(2) and so
forth.
Probing Properties:
The ith probe is to (H (key) +f (i)) %table size.
If i reaches size-1, the probe has failed.
Depending on f (i), the probe may fail sooner. Long sequences of probe
are costly.
Linear Probing- Example
Example: - Input data is :89 18 49 58 69; Tablesize=10
1.H(89) =89%10 =9 , therefore 89 is stored in position 9.
2. H(18) =18%10 =8,therefore 18 is stored in position 8.
3. H(49) =49%10 =9 ((colloids with value 89 stored in position 9. .So try for next
free cell using formula 2))
i=1, h1(49) = (H(49)+1)%10
= (9 +1)%10 =10%10 =0, therefore 49 is stored in position 0.
4. H(58) =58%10 =8 ((colloids with 18 stored in position 8))
i=1, h1(58) = (H(58) +1)%10
= (8+1) %10 =9%10 =9 =>Again collision
i=2, h2(58) =(H(58)+2)%10
=(8+2)%10 =10%10
=0 =>Again collision
Linear Probing- Example

i=3, h2(58) =(H(58)+3)%10

=(8+3)%10 =11%10
= 1, therefore 58 will be stored in position 1.
Linear Probing- Another Example
2.Quadratic Probing

• To resolve the primary clustering problem, quadratic probing can be

used. With quadratic probing, rather than always moving one spot,
move i ^ 2 spots from the point of collision, where i is the number of
attempts to resolve the collision.
• Another collision resolution method which distributes items more
evenly
• From the original index H, if the slot is filled, try cells H+1 ^ 2,
H+2 ^ 2, H+3 ^ 2,.., H + i ^ 2 with wrap-around.
Hi(X)=(Hash(X)+F(i))mod Tablesize, F(i)=i^2
Hi(X)=(Hash(X)+ i^2)mod Tablesize
2.Quadratic Probing Example
2.Quadratic Probing –Another Example

h0(23) = (23 % 7) % 7 = 2
h0(13) = (13 % 7) % 7 = 6
h0(21) = (21 % 7) % 7 = 0
h0(14) = (14 % 7) % 7 = 0 collision
h1(14) = (0 + 1^2) % 7 = 1
h0(7) = (7 % 7) % 7 = 0 collision
h1(7) = (0 + 1^2) % 7 = 1 collision
h-1(7) = (0 – 1^2) % 7 = -1
NORMALIZE: (-1 + 7) % 7 = 6 collision
h2(7) = (0 + 2^2) % 7 = 4
h0(8) = (8 % 7)%7 = 1 collision
h1(8) = (1 + 1^2) % 7 = 2 collision
h-1(8) = (1 – 1^2) % 7 = 0 collision
h2(8) = (1 + 2^2) % 7 = 5
h0(15) = (15 % 7)%7 = 1 collision Quadratic probing is better than
h1(15) = (1 + 1^2) % 7 = 2 collision linear probing because it
h-1(15) = (1 – 1^2) % 7 = 0 collision
h2(15) = (1 + 2^2) % 7 = 5 collision eliminates primary clustering.
h-2(15) = (1 – 2^2) % 7 = -3
NORMALIZE: (-3 + 7) % 7 = 4 collision
2. Quadratic Probing

Limitation:
• at most half of the table can be used as alternative locations to
resolve collisions.
• This means that once the table is more than half full, it's difficult to
find an empty spot. This new problem is known as secondary
clustering because elements that hash to the same hash key will
always probe the same alternative cells.
3.Double Hashing
• Double hashing uses the idea of applying a second hash function to the
key when a collision occurs. The result of the second hash function will
be the number of positions forms the point of collision to insert.
There are a couple of requirements for the second function:
• It must never evaluate to 0 must make sure that all cells can be probed.
Hi(X)=(Hash(X)+i*Hash2(X))mod Tablesize
• A popular second hash function is:
Hash2 (key) = R - (key % R) where R is a prime number that is
smaller than the size of the table.
3.Double Hashing -Example
Review Questions

1. Double hashing is one of the best methods available for open

addressing.
a) True
b) False
2. What is the hash function used in Double Hashing?
a) (h1(k) – i*h2(k))mod m
b) h1(k) + h2(k)
c) (h1(k) + i*h2(k))mod m
d) (h1(k) + h2(k))mod m
Rehashing
Rehashing
The new size of the hash table:
• should also be prime
• will be used to calculate the new insertion spot (hence the name rehashing)
• This is a very expensive operation! O(N) since there are N elements to rehash
and the table size is roughly 2N. This is ok though since it doesn't happen that
often.
The question becomes when should the rehashing be applied?
• once the table becomes half full
• once an insertion fails
• once a specific load factor has been reached, where load factor is the ratio of the
number of elements in the hash table to the table size
Review Questions
A technique for direct search is------------
a) Binary Search b) Linear Search c) Tree Search d) Hashing

Consider a hash table of size seven, with starting index zero, and a hash function
(3x + 4)mod7. Assuming the hash table is initially empty, which of the following is
the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table
using closed hashing? Note that ‘_’ denotes an empty location in the table.
a) 8, _, _, _, _, _, 10
b) 1, 8, 10, _, _, _, 3
c) 1, _, _, _, _, _,3
d) 1, 10, 8, _, _, _, 3
Extendible Hashing
• Extendible Hashing is a mechanism for altering the size of the hash
table to accommodate new entries when buckets overflow.
• Common strategy in internal hashing is to double the hash table and
rehash each entry.
• However, this technique is slow, because writing all pages to disk is
too expensive. Therefore, instead of doubling the whole hash table, we
use a directory of pointers to buckets, and double the number of
buckets by doubling the directory, splitting just the bucket that
overflows.
• Since the directory is much smaller than the file, doubling it is much
cheaper. Only one page of keys and pointers is split.
Extendible Hashing
Extendible hashing is a type of hash system which treats a hash as a
bit string and uses a trie for bucket lookup. Because of the
hierarchical nature of the system, re-hashing is an incremental operation
(done one bucket at a time, as needed).
Extendible hashing - Example
Extendible hashing - Example
Extendible hashing - Example
Extendible hashing - Example
Review Questions

Extendible hashing is a ___________________disk-based index

structure which implements a hashing scheme utilizing a directory
a) dynamically updateable b) static

What is the load factor?

a) Average array size b) Average key size c) Average chain length
d) Average hash table length
References:
1. A.V.Aho, J.E Hopcroft , J.D.Ullman, Data structures and Algorithms, Pearson Education, 2003
2. Reema Thareja, Data Structures Using C, 1st ed., Oxford Higher Education, 2011