MSMC 203: Data Structure

MSMC 204: Design and Analysis of Algorithm

Ganga Ram

DST-Centre for Interdisciplinary Mathematical Sciences

Institute of Science, Banaras Hindu University

gangaiitr11@gmail.com; gangacims@bhu.ac.in

G.R. BHU
FDE 1 / 43
 Syllabus for MSMC 203: Data Structure:
Introduction: Basic terminology, data organization, concept of operations on data
structures traversing, search ing, inserting, deleting, Arrays, pointers and records,
Mathematical background to create and analysze programs.

Linked lists: Introduction, representation of linked list in memory, traversing a linked

list, searching a linked list, memory allocation, insertion and deletion in linked list,
header linked list, two way lists.

Stacks and queues Recursion: Operation on Stacks and queues.

Trees: Definition, binary trees, representing binary trees in memory, traversing binary
search trees, searching, inserting and deleting in binary search trees.

Hashing: hash tables, Hash functions, table overflow, Hash table implementation,
analysis. AVLsearch trees, m-way search trees, B trees, Heap

G.R. BHU
FDE 2 / 43
 Books Recommended for MSMC 203: Data Structure:
Jonathan L Gross, Jay Yellen, Handbook of Graph Theory, 2003.
N. Deo, Graph Theory with Applications to Engineering and Computer Science, PHI.
Richard A. Brualdi, Introductory Combinatorics, Prentice Hall, 4 edition, 2004.
Kenneth H. Rosen, Discrete Mathematics, Tata McGraw Hill.
G. Chartrand and L. Lesniak, Graphs and Digraphs, Chapman & Hall/CRC, 4
edition, 2004.
Bondy J.A. and U.S. R. Murty, Graph Theory with Applications, The Macmillan
Press Ltd. 1976.
E. Balaguruswamy, C Programming and Data Structures with C, McGraw Hill, 2013.
G. L. Heileman, Data Structures, Algorithms and Object Oriented Programming,
Tata McGraw Hill, 1996.
M. T. Goodrich and R. Tamassia, Data Structures and Algorithms in JAVA, Wiley,
2006
A.V. Aho and J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley, 1983.

G.R. BHU
FDE 3 / 43
 Syllabus for MSMC 204: Design and Analysis of Algorithm:
Introduction to algorithms and its importance, mathematical foundations; growth
functions, complexity analysis of algorithms, summations, recurrences, sorting
algorithms design and analysis: Insertion sort, divide and conquer, merge sort, heap
sort, radix sorting.

Hast table, B-trees, Binomial Heaps, Fibonacci Heaps.

Dynamic Programming: Introduction, Matrix chain multiplication, Greedy

Algorithms,

Elementary Graph algorithms: Minimum spaning trees, Single source shortest path,
all pair shortest path.

String matching: Robin-Karp algorithm, Knuth-Morris Pratt algorithm, Algorithm

for parallel computers, par allelism, the PRAM models, simple PRAM algorithms, P
and NP class, some NP-complete problems.

G.R. BHU
FDE 4 / 43
 Books Recommended for MSMC 204: Design and Analysis of Algorithm:
Thomas H.Cormas H. Cormen, Charles E. Leiserson, R.L. Rivest, Introduction to
Algorithms, Prentice Hall of India Publications, New-Delhi, 2009.
Sara Baase and Allen Van Gelder, Computer Algorithms: Introduction to Design and
Analysis, Pearson Edu cation (Singapore) Pvt. Ltd. New Delhi, 2002.
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, The Design and Analysis of
Computer Algorithms. Pearson Education (Singapore) Pvt. Ltd New Delhi, 2002.

G.R. BHU
FDE 5 / 43
 Motivational Problems

Königsberg Bridge Problem:1 The East Prussian city of Königsberg occupied both
banks of the River Pregel and the island of Kneiphof, lying in the river at a point where
the river branches into two parts. There were seven bridges that spanned various sections
of the river. This problem, asks whether there is a route that crosses each of these
bridges exactly once.

1 Narsingh deo:Graph Theory with Applications to Engineering &Computer Science, Dover Publications, inc.

Mineola, New York-1974.

G.R. BHU
FDE 6 / 43
 Electric network Problem: 2 We have an electric network with e elements (edges) and
n nodes (vertices), what is the minimum number of elements we must remove to
eliminate all circuits in the network?

2 Narsingh deo:Graph Theory with Applications to Engineering &Computer Science, Dover Publications, inc.

Mineola, New York-1974.

G.R. BHU
FDE 7 / 43
 Chinese Postman Problem: A postman start from his post office in a town to deliver
his letters and returns to his starting point every day. What routs should he take so that
he visits each road at least once and the total distance covered is least.

G.R. BHU
FDE 8 / 43
 Travelling Salesman Problem: A salesman is required to visit a number of cities.
What is the route he should take if he has to start at his home city, visit each city exactly
once and then return home travelling the minimum distance.

G.R. BHU
FDE 9 / 43
 A puzzle with multicolored cubes/Instant Insanity Puzzle: The six faces of every
four cube are variously colored blue (B), green (G), red (R), or white (W). Is it possible to
stack the cubes one on top of another to form a column such that no color appears twice
on any of the four sides of this column?

G.R. BHU
FDE 10 / 43
 Agriculture Farming Problem: If we have a farm consisting of some walled plots of
land, and these plots are full of water, how many walls will have to be broken so that all
the water can be drained out?

G.R. BHU
FDE 11 / 43
 Some Special graphs3

3 https://www.eet-china.com/mp/a173006.html
G.R. BHU
FDE 12 / 43
 What is a graph?4

⇒ Graphical representation of data structure known as graph.

⇒ A collection G = (V , E , Φ) of sets V and E and a relation Φ,

V is called the set of vertices
E is called the collection of edges
Φ is a relation means each edge has either one or two vertices associated with
ordered or un-ordered pair of vertices and these vertices are called end points is
called a graph.
The number of vertices in a graph G is called order of a graph and notation |V (G )| = n.
The number of edges in a graph G is called size of a graph and notation |E (G )| = m.

4 Narsingh deo:Graph Theory with Applications to Engineering &Computer Science, Dover Publications, inc.

Mineola, New York-1974.

G.R. BHU
FDE 13 / 43
 Example-1: V = {v1 , v2 , v3 }; E = {e1 , e2 , e3 }; Φ ⇒ e1 = (v1 , v2 ), e2 = (v2 , v3 ), e3 = (v1 , v3 )

v1 e1 v2

e3 e2

v3

G.R. BHU
FDE 14 / 43
 Example2:

G.R. BHU
FDE 15 / 43
 Example-3:

e7

v3 e5 v4

e2
e3 e4 v5 v6

e6

v1 e1 v2

G.R. BHU
FDE 16 / 43
 Types of Graphs: We have following types

Finite and infinite Graph:

Directed and undirected Graph:
Underlaying Graph:
Mixed Graph:
Simple Graph:
Trivial and Non-trivial Graph:
Null/Empty Graph:
General/Pseudo Graph:
Multi Graph:
Weighted Graph:

G.R. BHU
FDE 17 / 43
 Vertex Incident: A vertex is incident with an edge if the vertex is one of the endpoints
of that edge.

Adjacent Vertex/Simple Adjacency: If they are joined by exactly one edge.

Adjacent Edges: Those two edges that have an end point in common.

Proper Edge: It is an edge that joint/connect two distinct vertices.

Multiple Edges/Parallel Edges: It is a collection of two or more edges having identical

ends points.

Multiplicity: It is the number of edges between a pair of vertices say u and v .

Self Loop: It is an edge that joint/connect a single end point to itself.

G.R. BHU
FDE 18 / 43
 New graph from old graph:
Subgraph Method:
1 Subgraph
2 Proper Subgraph
3 Spanning Subgraph
Operational Method:
4 Primary/Uniry
5 Second/Binary

G.R. BHU
FDE 19 / 43
 Degree of vertex

Degree of a vertex: The degree of v is the number of edges incident with v . If v is a

vertex of a simple graph G of order n, then

0 ≤ deg (v ) ≤ n − 1.

Series Edges: If their comman vertex is of degree two.

Even and odd Vertices: A vertex in a graph G is even or odd, according to whether its
degree in G is even or odd.

Isolated Vertex: A vertex of degree 0.

Pendant Vertex/leaf/end or edge: A vertex of degree 1 is an end-vertex or a leaf. An

edge incident with an end-vertex is called a pendant edge.

G.R. BHU
FDE 20 / 43
 Connect-ness of graph

Walk/trail: A finite alternating sequence of vertices and edges, beginning and ending
with vertices such that each edge is incident with vertices preceding and following it.
No edge appear more then once vertex may be repeat.
Vertices with which a walk begins and ends are called its terminal vertices.
Number of edges in the walk is called length of walk:
Closed walk: If the terminal vertices of walk is same then the walk is called closed walk.

Open walk: If terminal vertices are different then walk are called open walk.

Circuit/polygon/cycle: A closed walk in which no vertices appear more then once.

Path: An open walk in which no vertices appear more then once.

G.R. BHU
FDE 21 / 43
 Connected graph: If there is a walk/path between every pair of vertices.

Disconnected graph: If there is no walk/path between any pair of vertices.

Component: A disconnected graph consists two or more connected subgraphs called

components.

G.R. BHU
FDE 22 / 43
 Shortest Path in a connected graph: A path of least length between two given
vertices in weighted graph.

Shortest-path Algorithms:

There are different types of shortest-path problems. Most frequently encountered among
these are the following five
1 Shortest path between two specified vertices. (Dijkstra, Bellman Ford)
2 Shortest paths between all pairs of vertices. (Floyd-Warshall)
3 Shortest paths from a specified vertex to all others.
4 Shortest path between specified vertices that passes through specified vertices.
5 The second, third, and so on, shortest paths.

G.R. BHU
FDE 23 / 43
G.R. BHU
FDE 24 / 43
G.R. BHU
FDE 25 / 43
G.R. BHU
FDE 26 / 43
G.R. BHU
FDE 27 / 43
 Trees in Graph

Trees: A connected graph without circuit.

Tree of a graph: A subgraph which is a tree

Leaf/Pandent Vertex: If deg (v ) = 1.

Tree edge and non-tree edge: If it is the edge of a tree.

Frontier Edge: A non-tree edge with one end point in tree T and one endpoint not in
tree T .

Theorem: A tree with n vertices has n − 1 edges.

G.R. BHU
FDE 28 / 43
 Rooted Tree

Root: A particular one vertex of a tree which is distinguished from all the other vertices
and every edge is reached from that particular vertex to other vertices is called a root in
tree.
Rooted tree: A tree with root is called a rooted tree.
Terminology used for rooted tree
Parent: The parent of v (v is not root) is a unique vertex u such that there is a
direct edge from u to v and
Child: v is called child of u.
Siblings: Vertices with the same parent.
Ancestors: The ancestors of v (v is not root) are the vertices in the path from the
root to this vertex.
Descendant: Vertices that have v as an ancestor.
Leaf: The vertex has no children.
Internal Vertices: Vertices that have children.

G.R. BHU
FDE 29 / 43
 Binary Trees: If every internal vertex has no more than 2 children.

Full Binary Trees:A binary tree is defined as a tree in which there is exactly one vertex
of degree two, and each of the remaining vertices is of degree one or three

Obviously, we are talking about trees with three or more vertices.

The vertex of degree two is distinct from all other vertices, this vertex serves as a root.

Properties of binary trees

The number of vertices n in a full binary tree is always odd.
n+1
Let p be the number of pendant vertices in a full binary tree T . Then p =
2

G.R. BHU
FDE 30 / 43
 Level of a vertex v (L): The length of the unique path from the root to this vertex v .

Height: The maximum of the levels of the vertices e.i. length of the longest path from the
root.

Balanced: All the leaves are at levels L or L − 1.

More Properties of binary trees

Minimum possible height of an n-vertex full binary tree is dlog2 (n + 1) − 1e, where dne
denotes the smallest integer greater than or equal to n.
n−1
Maximum possible height of an n-vertex full binary tree is .
2
Labeled Graph: A graph in which each vertex is assigned a unique name or label (i.e.,
no two vertices have the same label).

G.R. BHU
FDE 31 / 43
 The m− ary tree: If every internal vertex has no more than m children.

Full m− ary tree: If every internal vertex has exactly m children.

Note: If m = 2 then m− ary tree is called binary tree.

Sub rooted tree: A subgraph of a rooted tree.

Ordered rooted tree: The children of each internal vertices are ordered from left to
right.

G.R. BHU
FDE 32 / 43
 Traversal in Ordered Rooted Tree

Tree traversal: A systematic method for visiting every vertex of an ordered rooted tree is
called traversal algorithm.
Let T be an ordered rooted tree with root r . If T consists only of r , then r is pre-order or
in-order,or post-order. Otherwise, suppose that T1 , T2 , (1), Tn are the subtrees at r from
left to right. Then
Pre-order: begins by visiting r . It continues by traversing T1 in pre-order, then T2 in
pre-order, and so on, un-till Tn is traversed in pre-order.
In-order: begins by traversing T1 in-order, then visiting r . It continues by traversing
T2 in in-order, then T3 in in-order,and so on, un-till Tn is traversed in in-order.
Post-order: begins by traversing T1 post-order, then T2 in post-order, and so on and
then Tn in post-order, and ends by visiting r .

G.R. BHU
FDE 33 / 43
 v1

v2 v3 v4

v5 v6 v7 v8 v9

v10 v11 v12 v13

v14 v15 v16

G.R. BHU
FDE 34 / 43
 Some complicated expressions, such as compound propositions, arithmetic expressions, and
combinations of sets using the ordered rooted tree.

Types of form Notations:

Infix form: We obtain the infix form of an expression by traversing its binary tree in
in-order.
Prefix form (Polish notation): We obtain the prefix form of an expression by
traversing its binary tree in pre-order.
Postfix form (Reverse Polish notation): We obtain the postfix form of an
expression by traversing its binary tree in post-order.

G.R. BHU
FDE 35 / 43
 Spanning Tree/skeleton/ scaffolding/maximal tree subgraph A tree T is called a
spanning tree of a connected graph G if T is a subgraph of G and T contains all vertices of
G. i.e
V (T ) = V (G ), T ⊆ G
Spanning forest: A disconnected graph G with k component is called spanning forest if
it has k spanning tree. i.e
X
V (Ti ) = V (G ), i = 1, 2, . . . k

Branch: An edge of a spanning tree.

Chord/tie/link: An edge of a graph G that is not in a spanning tree.

G.R. BHU
FDE 36 / 43
 Finding a spanning tree: If G has no circuit, it is its own spanning tree. If G has a
circuit, delete an edge from the circuit. This will still leave the graph connected. If there
are more circuits, repeat the operation till an edge from the last circuit is deletedleaving a
connected, circuit-free graph that contains all the vertices of G.

G.R. BHU
FDE 37 / 43
 Algorithm for finding spanning tree: We have following algorithm
Depth-first search/Backtracking
Breadth-first search

G H J K

A B C D E

F I

G.R. BHU
FDE 38 / 43
 Minimal spanning tree or shortest spanning tree or shortest distance spanning
tree: A spanning tree with the smallest weight in a weighted graph is called a shortest
spanning tree or shortest-distance spanning tree or minimal spanning tree.
Kruskal’s Algorithm: List all edges of the graph G in order of nondecreasing
weight. Next, select a smallest edge of G. Then for each successive step select (from
all remaining edges of G) another smallest edge that makes no circuit with the
previously selected edges. Continue until n - 1 edges have been selected, and these
edges will constitute the desired shortest spanning tree.

G.R. BHU
FDE 39 / 43
 v2 4 v4

2 5

3 v5 1 v6

6 3 6

v1 2 v3

G.R. BHU
FDE 40 / 43
 Prim’s Algorithm: Start from vertex v1 and connect it to its nearest neighbor (i.e.,
to the vertex which has the smallest entry in row 1 of the table), say vk . Now
consider v1 and vk as one subgraph, and connect this subgraph to its closest neighbor
(i.e., to a vertex other than v1and vk that has the smallest entry among all entries in
rows 1 and k). Let this new vertex be vi . Next regard the tree with vertices v1 , vk ,
and vi as one subgraph, and continue the process until all n vertices have been
connected by n - 1 edges.

G.R. BHU
FDE 41 / 43
 How to express a graphs computationally

Adjacency Matrix: An n by n matrix X (G ) = [aij ] of a graph with no parrel edge

defined as

aij = 1 if there is an edge ith and jth vertex

= 0 otherwise

G.R. BHU
FDE 42 / 43
 Questions/Query ?

G.R. BHU
FDE 43 / 43