Course Code : CS-62
Course Title : ‘C’ Programming & Data Structure
Assignment Number : BCA (2)-62/Assignment/ 2009
Maximum Marks : 25
Last Date of Submission : 30th April, 2009/30th October, 2009
There are four questions in this assignment. Answer all the questions. You may use illustrations and diagrams to enhance your explanations.
BCA MCA Bsc B tech CS information technology
final year project
Q.1 What is a Data Structure? Explain its need? (5 marks)
Q.2 Write a program in ‘C’ language for the multiplication of two matrices using pointers. (10 marks)
Q.3 What is a Directed Graph? Write an algorithm to find whether a Directed Graph is connected or not. (5 marks)
Q.4 Explain the process of converting a Tree to a Binary Tree.
(5 marks)
Q.1 What is a Data Structure? Explain its need?
Ans-1
Data Structure
In computer science, a data structure is a way of storing data in a computer so that it can
be used efficiently. Often a carefully chosen data structure will allow the most efficient
algorithm to be used. The choice of the data structure often begins from the choice of an
abstract data type. A well-designed data structure allows a variety of critical operations to
be performed, using as few resources, both execution time and memory space, as
possible. Data structures are implemented using the data types, references and operations
on them provided by a programming language .
Different kinds of data structures are suited to different kinds of applications, and some
are highly specialized to certain tasks. For example, B-trees are particularly well-suited
for implementation of databases, while routing tables rely on networks of machines to
function.
Common data structures:
Array
Stacks
Queues
Linked lists
Trees
Graphs
A data structure is a specialized format for organizing and storing data. General data
structure types include the array, the file, the record, the table, the tree, and so on. Any
data structure is designed to organize data to suit a specific purpose so that it can be
accessed and worked with in appropriate ways. In computer programming, a data
structure may be selected or designed to store data for the purpose of working on it with
various algorithms.
Different kinds of data structures are suited to different kinds of applications, and some
are highly specialized to certain tasks. For example, B-trees are particularly well-suited
for implementation of databases, while networks of machines rely on routing tables to
function.
In the design of many types of computer program, the choice of data structures is a
primary design consideration. Experience in building large systems has shown that the
difficulty of implementation and the quality and performance of the final result depends
heavily on choosing the best data structure. After the data structures are chosen, the
algorithms to be used often become relatively obvious. Sometimes things work in the
opposite direction — data structures are chosen because certain key tasks have algorithms
that work best with particular data structures. In either case, the choice of appropriate
data structures is crucial.
Q.2 Write a program in ‘C’ language for the multiplication of two matrices using pointers.
Ans-2
Q.3 What is a Directed Graph? Write an algorithm to find whether a Directed Graph is connected or not.
Ans-3
A graph in which each graph edge is replaced by a directed graph edge, also called a digraph. A directed
graph having no multiple edges or loops (corresponding to a binary adjacency matrix with 0s on the
diagonal) is called a simple directed graph. A complete graph in which each edge is bidirected is called a
complete directed graph. A directed graph having no symmetric pair of directed edges (i.e., no bidirected
edges) is called an oriented graph. A complete oriented graph (i.e., a directed graph in which each pair of
nodes is joined by a single edge having a unique direction) is called a tournament.
If is an undirected connected graph, then one can always direct the circuit graph edges of and leave the
separating edges undirected so that there is a directed path from any node to another. Such a graph is said
to be transitive if the adjacency relation is transitive.
In an undirected graph G, two vertices u and v are called connected if G contains a path
from u to v. Otherwise, they are called disconnected. A graph is called connected if
every pair of distinct vertices in the graph is connected and disconnected otherwise.
A graph is called k-vertex-connected or k-edge-connected if removal of k or more
vertices (respectively, edges) makes the graph disconnected. A k-vertex-connected graph
is often called simply k-connected.
A directed graph is called weakly connected if replacing all of its directed edges with
undirected edges produces a connected (undirected) graph. It is strongly connected or
strong if it contains a directed path from u to v and a directed path from v to u for every
pair of vertices u,v.
To determine whether a graph is connected (or not) can be done eciently with a BFS or
DFS from any vertex. If the tree generated has the same number of vertices as the graph
then it is connected. For digraphs we first create an underlying (undirected) graph before
searching. We can use the following extended class for converting digraphs to graphs.
public class uGraph extends Graph
{
public uGraph() { super(); }
public uGraph(uGraph G) { super(G); }
public uGraph(Graph G)
{
super(G);
int n = order();
// create underlying graph by adding symmetric edges
//
for (int i=0; i
for (int j=i+1; j
{
if (isArc(i,j)) super.addArc(j,i);
else
if (isArc(j,i)) super.addArc(i,j);
}
}
// public uGraph(BufferedReader) - use base class directly.
// redefine size for undirected graph
//
public int size() { return super.size()/2; }
// ... also directed edge methods need fixing
// (would like to privatize them but java doesn't allow it)
//
public void addArc(int i, int j) { super.addEdge(i,j); }
public void removeArc(int i, int j) { super.removeEdge(i,j); }
//public boolean isArc(int i, int j) { return super.isArc(i,j); }
}
static public boolean isConnected(uGraph G)
{
int[] tmp = new int[G.order()];
return BFS(G,0,tmp) == G.order();
}
static public boolean isConnected(Graph G) // for underlying graph
{
uGraph G2 = new uGraph(G);
return isConnected(G2);
}
Q.4 Explain the process of converting a Tree to a Binary Tree.
Ans-4
Converting a Tree to a Binary Tree
a binary tree is a tree data structure in which each node has at most two children.
Typically the child nodes are called left and right. Binary trees are commonly used to
implement binary search trees and binary heaps.
There is a one-to-one mapping between general ordered trees and binary trees, which in
particular is used by Lisp to represent general ordered trees as binary trees. Each node N
in the ordered tree corresponds to a node N' in the binary tree; the left child of N' is the
node corresponding to the first child of N, and the right child of N' is the node
corresponding to N 's next sibling --- that is, the next node in order among the children of
the parent of N. This binary tree representation of a general order tree, is sometimes also
referred to as a First-Child/Next-Sibling binary tree, or a Doubly-Chained Tree, or a
Filial-Heir chain.
One way of thinking about this is that each node's children are in a linked list, chained
together with their right fields, and the node only has a pointer to the beginning or head
of this list, through its left field.
For example, in the tree on the left, A has the 6 children {B,C,D,E,F,G}. It can be
converted into the binary tree on the right.
The binary tree can be thought of as the original tree tilted sideways, with the black left
edges representing first child and the blue right edges representing next sibling. The
leaves of the tree on the left would be written in Lisp as:
(((N O) I J) C D ((P) (Q)) F (M))
which would be implemented in memory as the binary tree on the right, without any
letters on those nodes that have a left child
Course Title : ‘C’ Programming & Data Structure
Assignment Number : BCA (2)-62/Assignment/ 2009
Maximum Marks : 25
Last Date of Submission : 30th April, 2009/30th October, 2009
There are four questions in this assignment. Answer all the questions. You may use illustrations and diagrams to enhance your explanations.
BCA MCA Bsc B tech CS information technology
final year project
Q.1 What is a Data Structure? Explain its need? (5 marks)
Q.2 Write a program in ‘C’ language for the multiplication of two matrices using pointers. (10 marks)
Q.3 What is a Directed Graph? Write an algorithm to find whether a Directed Graph is connected or not. (5 marks)
Q.4 Explain the process of converting a Tree to a Binary Tree.
(5 marks)
Q.1 What is a Data Structure? Explain its need?
Ans-1
Data Structure
In computer science, a data structure is a way of storing data in a computer so that it can
be used efficiently. Often a carefully chosen data structure will allow the most efficient
algorithm to be used. The choice of the data structure often begins from the choice of an
abstract data type. A well-designed data structure allows a variety of critical operations to
be performed, using as few resources, both execution time and memory space, as
possible. Data structures are implemented using the data types, references and operations
on them provided by a programming language .
Different kinds of data structures are suited to different kinds of applications, and some
are highly specialized to certain tasks. For example, B-trees are particularly well-suited
for implementation of databases, while routing tables rely on networks of machines to
function.
Common data structures:
Array
Stacks
Queues
Linked lists
Trees
Graphs
A data structure is a specialized format for organizing and storing data. General data
structure types include the array, the file, the record, the table, the tree, and so on. Any
data structure is designed to organize data to suit a specific purpose so that it can be
accessed and worked with in appropriate ways. In computer programming, a data
structure may be selected or designed to store data for the purpose of working on it with
various algorithms.
Different kinds of data structures are suited to different kinds of applications, and some
are highly specialized to certain tasks. For example, B-trees are particularly well-suited
for implementation of databases, while networks of machines rely on routing tables to
function.
In the design of many types of computer program, the choice of data structures is a
primary design consideration. Experience in building large systems has shown that the
difficulty of implementation and the quality and performance of the final result depends
heavily on choosing the best data structure. After the data structures are chosen, the
algorithms to be used often become relatively obvious. Sometimes things work in the
opposite direction — data structures are chosen because certain key tasks have algorithms
that work best with particular data structures. In either case, the choice of appropriate
data structures is crucial.
Q.2 Write a program in ‘C’ language for the multiplication of two matrices using pointers.
Ans-2
Q.3 What is a Directed Graph? Write an algorithm to find whether a Directed Graph is connected or not.
Ans-3
A graph in which each graph edge is replaced by a directed graph edge, also called a digraph. A directed
graph having no multiple edges or loops (corresponding to a binary adjacency matrix with 0s on the
diagonal) is called a simple directed graph. A complete graph in which each edge is bidirected is called a
complete directed graph. A directed graph having no symmetric pair of directed edges (i.e., no bidirected
edges) is called an oriented graph. A complete oriented graph (i.e., a directed graph in which each pair of
nodes is joined by a single edge having a unique direction) is called a tournament.
If is an undirected connected graph, then one can always direct the circuit graph edges of and leave the
separating edges undirected so that there is a directed path from any node to another. Such a graph is said
to be transitive if the adjacency relation is transitive.
In an undirected graph G, two vertices u and v are called connected if G contains a path
from u to v. Otherwise, they are called disconnected. A graph is called connected if
every pair of distinct vertices in the graph is connected and disconnected otherwise.
A graph is called k-vertex-connected or k-edge-connected if removal of k or more
vertices (respectively, edges) makes the graph disconnected. A k-vertex-connected graph
is often called simply k-connected.
A directed graph is called weakly connected if replacing all of its directed edges with
undirected edges produces a connected (undirected) graph. It is strongly connected or
strong if it contains a directed path from u to v and a directed path from v to u for every
pair of vertices u,v.
To determine whether a graph is connected (or not) can be done eciently with a BFS or
DFS from any vertex. If the tree generated has the same number of vertices as the graph
then it is connected. For digraphs we first create an underlying (undirected) graph before
searching. We can use the following extended class for converting digraphs to graphs.
public class uGraph extends Graph
{
public uGraph() { super(); }
public uGraph(uGraph G) { super(G); }
public uGraph(Graph G)
{
super(G);
int n = order();
// create underlying graph by adding symmetric edges
//
for (int i=0; i
for (int j=i+1; j
{
if (isArc(i,j)) super.addArc(j,i);
else
if (isArc(j,i)) super.addArc(i,j);
}
}
// public uGraph(BufferedReader) - use base class directly.
// redefine size for undirected graph
//
public int size() { return super.size()/2; }
// ... also directed edge methods need fixing
// (would like to privatize them but java doesn't allow it)
//
public void addArc(int i, int j) { super.addEdge(i,j); }
public void removeArc(int i, int j) { super.removeEdge(i,j); }
//public boolean isArc(int i, int j) { return super.isArc(i,j); }
}
static public boolean isConnected(uGraph G)
{
int[] tmp = new int[G.order()];
return BFS(G,0,tmp) == G.order();
}
static public boolean isConnected(Graph G) // for underlying graph
{
uGraph G2 = new uGraph(G);
return isConnected(G2);
}
Q.4 Explain the process of converting a Tree to a Binary Tree.
Ans-4
Converting a Tree to a Binary Tree
a binary tree is a tree data structure in which each node has at most two children.
Typically the child nodes are called left and right. Binary trees are commonly used to
implement binary search trees and binary heaps.
There is a one-to-one mapping between general ordered trees and binary trees, which in
particular is used by Lisp to represent general ordered trees as binary trees. Each node N
in the ordered tree corresponds to a node N' in the binary tree; the left child of N' is the
node corresponding to the first child of N, and the right child of N' is the node
corresponding to N 's next sibling --- that is, the next node in order among the children of
the parent of N. This binary tree representation of a general order tree, is sometimes also
referred to as a First-Child/Next-Sibling binary tree, or a Doubly-Chained Tree, or a
Filial-Heir chain.
One way of thinking about this is that each node's children are in a linked list, chained
together with their right fields, and the node only has a pointer to the beginning or head
of this list, through its left field.
For example, in the tree on the left, A has the 6 children {B,C,D,E,F,G}. It can be
converted into the binary tree on the right.
The binary tree can be thought of as the original tree tilted sideways, with the black left
edges representing first child and the blue right edges representing next sibling. The
leaves of the tree on the left would be written in Lisp as:
(((N O) I J) C D ((P) (Q)) F (M))
which would be implemented in memory as the binary tree on the right, without any
letters on those nodes that have a left child
