ASSIGNMENT
OF ADVANCED DATA STUCTURE
Question No 1. Define data structure?
Explain different types of data structures?
DATA STRUCTURE:
In computer science, a data structure is a particular
way of organizing data in a computer so that it can be used efficiently. Data
structures provide a means to manage large amounts of data efficiently for uses
such as large databases and internet indexing services. Usually, efficient data
structures are key to designing efficient algorithms. Some formal design methods
and programming languages emphasize data structures, rather than algorithms, as
the key organizing factor in software design. Storing and retrieving can be
carried out on data stored in both main memory and in secondary memory.4Data
structures are generally based on the ability of a computer to fetch and store
data at any place in its memory, specified by a pointer – a bit string,
representing a memory address, that can be itself stored in memory and manipulated by the program. Thus,
the array and record data structures are based on computing the addresses of
data items with arithmetic operations; while the linked data structures are
based on storing addresses of data items within the structure itself. Many data
structures use both principles, sometimes combined in non-trivial ways (as in
XOR linking).
The implementation of a data structure usually requires
writing a set of procedures that create and manipulate instances of that
structure. The efficiency of a data structure cannot be analyzed separately from
those operations. This observation motivates the theoretical concept of an
abstract data type, a data structure that is defined indirectly by the
operations that may be performed on it, and the mathematical properties of
those operations (including their space and time cost).
DIFFERENT TYPES OF DATA STRUCTURE:
1.
Lists: A group of similar items with
connectivity to the previous or/and next data items.
2.
Arrays: A set of homogeneous values.
3.
Records: A set of fields, where each field
consists of data belongs to one data type.
4.
Trees: A data structure where the data is
organized in a hierarchical structure. This type of data structure follows the
sorted order of insertion, deletion and modification of data items.
5.
Tables: Data is persisted in the form of
rows and columns. These are similar to records, where the result or
manipulation of data is reflected for the whole table.
Question No 2. Explain the different
types of binary tree with suitable diagrams.
Binary
Trees
|
We
extend the concept of linked data structures to structure containing nodes
with more than one self-referenced field. A binary tree is made of nodes,
where each node contains a "left" reference, a "right"
reference, and a data element. The topmost node in the tree is called the root.
Every
node (excluding a root) in a tree is connected by a directed edge from
exactly one other node. This node is called a parent. On the other hand, each
node can be connected to arbitrary number of nodes, called children. Nodes
with no children are called leaves, or external nodes. Nodes which are not
leaves are called internal nodes. Nodes with the same parent are called
siblings.
|
|
More tree terminology:
- The depth of a
node is the number of edges from the root to the node.
- The height of a
node is the number of edges from the node to the deepest leaf.
- The height of a
tree is a height of the root.
- A full binary
tree.is a binary tree in which each node has exactly zero or two children.
- A complete
binary tree is a binary tree, which is completely filled, with the
possible exception of the bottom level, which is filled from left to
right.
A complete binary tree is very special tree, it provides the best
possible ratio between the number of nodes and the height. The height h of a
complete binary tree with N nodes is at most O(log N). We can easily prove this
by counting nodes on each level, starting with the root, assuming that each level
has the maximum number of nodes:
n = 1 + 2 + 4 + ... + 2h-1 + 2h = 2h+1
- 1
Solving this with respect to h, we obtain
h = O(log n)
where the big-O notation hides some superfluous details.
Traversals
A traversal is a process that visits all the nodes in the tree.
Since a tree is a nonlinear data structure, there is no unique traversal. We
will consider several traversal algorithms with we group in the following two
kinds
- depth-first
traversal
- breadth-first
traversal
There are three different types of depth-first traversals, :
- PreOrder
traversal - visit the parent first and then left and right children;
- InOrder
traversal - visit the left child, then the parent and the right child;
- Post Order
traversal - visit left child, then the right child and then the parent;
There is only one kind of breadth-first traversal--the level order
traversal. This traversal visits nodes by levels from top to bottom and from
left to right.
|
As
an example consider the following tree and its four traversals:
PreOrder - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3 InOrder - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11 PostOrder - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8 LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2 |
|
In the next picture we demonstarte the order of node visitation.
Number 1 denote the first node in a particular traversal and 7 denote the last
node.
These common traversals can be represented as a single algorithm
by assuming that we visit each node three times. An Euler tour is
a walk around the binary tree where each edge is treated as a wall, which you
cannot cross. In this walk each node will be visited either on the left, or
under the below, or on the right. The Euler tour in which we visit nodes on the
left produces a preorder traversal. When we visit nodes from the below, we get
an inorder traversal. And when we visit nodes on the right, we get a postorder
traversal.
Binary Search Trees
We consider a particular kind of a binary tree called a Binary
Search Tree (BST). The basic idea behind this data structure is to have such a
storing repository that provides the efficient way of data sorting, searching
and retriving.
|
|
A
BST is a binary tree where nodes are ordered in the following way:
In
the following tree all nodes in the left subtree of 10 have keys < 10
while all nodes in the right subtree > 10. Because both the left and right
subtrees of a BST are again search trees; the above definition is recursively
applied to all internal nodes:
|
Insertion
The insertion procedure is quite similar to searching. We start at
the root and recursively go down the tree searching for a location in a BST to
insert a new node. If the element to be inserted is already in the tree, we are
done (we do not insert duplicates). The new node will always replace a NULL
reference.
Exercise. Given a sequence of numbers:
11, 6, 8, 19, 4, 10, 5, 17, 43, 49, 31
Draw a binary search tree by inserting the above numbers from left
to right.
Searching
Searching in a BST always starts at the root. We
compare a data stored at the root with the key we are searching for (let us
call it as toSearch). If the node does not contain the key we
proceed either to the left or right child depending upon comparison. If the
result of comparison is negative we go to the left child, otherwise - to the
right child. The recursive structure of a BST yields a recursive algorithm.
Searching in a BST has O(h) worst-case runtime complexity, where h
is the height of the tree. Since s binary search tree with n nodes has a
minimum of O(log n) levels, it takes at least O(log n) comparisons to find a
particular node. Unfortunately, a binary serch tree can degenerate to a linked
list, reducing the search time to O(n).
Deletion
Deletion is somewhat more tricky than insertion. There are several
cases to consider. A node to be deleted (let us call it as toDelete)
- is not in a
tree;
- is a leaf;
- has only one
child;
- has two
children.
Deletion of an internal node with two children is less
straightforward. If we delete such a node, we split a tree into two subtrees
and therefore, some children of the internal node won't be accessible after
deletion. In the picture below we delete 8:
Deletion starategy is the following: replace the node being
deleted with the largest node in the left subtree and then delete that largest
node. By symmetry, the node being deleted can be swapped with the smallest node
is the right subtree.
Question No .3 Explain in detail
about Adjacency matrix.
ADJACANCY MATIX:
In mathematics and computer science, an adjacency
matrix is a means of representing which vertices (or nodes) of a graph are
adjacent to which other vertices. Another matrix representation for a graph is
the incidence matrix.
Specifically, the adjacency matrix of a finite graph G
on n vertices is the n × n matrix where the non-diagonal entry aij is the
number of edges from vertex i to vertex j, and the diagonal entry aii,
depending on the convention, is either once or twice the number of edges
(loops) from vertex i to itself. Undirected graphs often use the latter
convention of counting loops twice, whereas directed graphs typically use the
former convention. There exists a unique adjacency matrix for each isomorphism
class of graphs (up to permuting rows and columns), and it is not the adjacency
matrix of any other isomorphism class of graphs. In the special case of a
finite simple graph, the adjacency matrix is a (0,1)-matrix with zeros on its
diagonal. If the graph is undirected, the adjacency matrix is symmetric.
The relationship between a graph and the eigenvalues
and eigenvectors of its adjacency matrix is studied in spectral graph theory.
The adjacency matrix, sometimes also called the
connection matrix, of a simple labeled graph is a matrix with
rows and columns labeled by graph vertices,
with a 1 or 0 in position
according to whether
and
are adjacent or
not. For a simple graph with no self-loops, the adjacency matrix must have 0s
on the diagonal. For an undirected
graph, the adjacency matrix is symmetric.
Since the labels of a graph may be permuted without changing the
underlying graph being represented, there are in general multiple possible
adjacency matrices for a given graph. In particular, the number
of distinct adjacency matrices for a graph
with vertex count
andautomorphism group order
is given by
|
|
where
is the number or permutations of vertex labels. The
illustration above shows the
possible adjacency matrices of the cycle graph
.
The adjacency matrix of a graph can be computed in Mathematica using AdjacencyMatrix[g], AdjacencyMatrix[g] in
the Mathematica packageGraphUtilities` , or
using ToAdjacencyMatrix[g] in
the Mathematica package Combinatorica` (as a full
matrix).
Question No 4. Explain
in detail about topological sorting
Topological sorting:-
(sometimes
abbreviated topsort or toposort) or topological ordering of a directed graph is
a linear ordering of its vertices such that for every directed edge uv from
vertex u to vertex v, u comes before v in the ordering. For instance, the
vertices of the graph may represent tasks to be performed, and the edges may
represent constraints that one task must be performed before another; in this
application, a topological ordering is just a valid sequence for the tasks. A
topological ordering is possible if and only if the graph has no directed
cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least
one topological ordering, and algorithms are known for constructing a
topological ordering of any DAG in linear time.
Topological Sorting vs Depth First
Traversal (DFS):
In DFS, we print a vertex and then recursively call DFS
for its adjacent vertices. In topological sorting, we need to print a vertex
before its adjacent vertices. For example, in the given graph, the vertex ‘5’
should be printed before vertex ‘0’, but unlike DFS, the vertex ‘4’ should also
be printed before vertex ‘0’. So Topological sorting is different from DFS. For
example, a DFS of the above graph is “5 2 3 1 0 4?, but it is not a topological
sorting
Algorithm to find Topological Sorting:
We recommend to first see implementation of DFS here.
We can modify DFS to find Topological Sorting of a graph. In DFS, we start from
a vertex, we first print it and then recursively call DFS for its adjacent
vertices. In topological sorting, we use a temporary stack. We don’t print the
vertex immediately, we first recursively call topological sorting for all its
adjacent vertices, then push it to a stack. Finally, print contents of stack.
Note that a vertex is pushed to stack only when all of its adjacent vertices
(and their adjacent vertices and so on) are already in stack.
Following is C++ implementation of topological sorting.
Please see the code for Depth First Traversal for a disconnected Graph and note
the differences between the second code given there and the below code.
// A C++ program to print topological sorting of a DAG
#include<iostream>
#include <list>
#include <stack>
using namespace std;
// A function
used by topologicalSort
void
topologicalSortUtil(int v, bool visited[], stack<int> &Stack);
public:
Graph(int
V); // Constructor
// prints a
Topological Sort of the complete graph
void
topologicalSort();
};
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
// A recursive function used by topologicalSort
void Graph::topologicalSortUtil(int v, bool visited[],
stack<int> &Stack)
{
// Mark the
current node as visited.
visited[v] =
true;
// Recur for
all the vertices adjacent to this vertex
list<int>::iterator i;
for (i =
adj[v].begin(); i != adj[v].end(); ++i)
if
(!visited[*i])
topologicalSortUtil(*i, visited, Stack);
// Push
current vertex to stack which stores result
Stack.push(v);
}
// The function to do Topological Sort. It uses
recursive topologicalSortUtil()
void Graph::topologicalSort()
{
stack<int> Stack;
// Mark all
the vertices as not visited
bool *visited
= new bool[V];
for (int i =
0; i < V; i++)
visited[i] = false;
// Call the
recursive helper function to store Topological Sort
// starting
from all vertices one by one
for (int i =
0; i < V; i++)
if
(visited[i] == false)
topologicalSortUtil(i, visited, Stack);
// Print
contents of stack
while
(Stack.empty() == false)
{
cout
<< Stack.top() << " ";
Stack.pop();
}
}
// Driver program to test above functions
int main()
{
// Create a
graph given in the above diagram
Graph g(6);
g.addEdge(5,
2);
g.addEdge(5,
0);
g.addEdge(4,
0);
g.addEdge(4,
1);
g.addEdge(2,
3);
g.addEdge(3,
1);
cout <<
"Following is a Topological Sort of the given graph \n";
g.topologicalSort();
return 0;
}
Question No 5. Explain
1. Fixed block storage allocation.
2. Variable block storage allocation
FIXED BLOCK STORAGE ALLOCATION:
The simplest general purpose dynamic allocation
mechanism of all requires that all of the available storage be divided into
equal sized blocks. When this is done, the size field on the allocate and
deallocate requests is not very meaningful, since only one size is available.
If the user requests more than this amount, the request will fail; if the user
requests less and there are any free blocks, the request will be successful and
an entire block will be allocated no matter how little memory the user actually
requests.
The heap manager must maintain enough information to
determine which blocks in the heap are free at any time. Typically, this information
will be stored in the form of a linked list, where the first word of each free
block holds the address of the next free block. As with chained resolution of
forward references (see Figure 4.10 through Figure 4.14), there is a problem
with representing the end of the free list. Throughout this section, this
problem will be ignored, and the symbol NULL, standing for an illegal or
reserved pointer value, will be used; it should be remembered that there are
occasional contexts where there are no reserved addresses, requiring a more
complex solution to the problem of marking the end of a list.
When writing a heap manager in assembly language or
other low-level languages, where there is no difference between pointers and
integers, it is natural to think of memory as one big array in which it is
perfectly appropriate to do arithmetic on array indices. In higher level
languages, where the type system discourages or even prevents this, we could
take two approaches to explaining such algorithms. One approach is to explain
the algorithm in terms of a large array of integers, M, with integer memory
addresses. Another is to use pointers with carefully documented and very unsafe
conversions between integer and pointer types.
VARIABLE BLOCK STORAGE ALLOCATION:
In computer programming, an automatic variable is a
variable which is allocated and deallocated automatically when program flow
enters and leaves the variable's context. This primarily applies to
lexically-scoped variables, where the context is the lexical context,
particularly the function or block in which a variable is defined. Note that
inside a function call within a context, a variable moves out of scope (is
inaccessible to the called function) but is not deallocated, coming back in
scope when the function returns.
The term local variable is usually synonymous with
automatic variable, since these are the same thing in many programming
languages, but local is more general – most local variables are automatic local
variables, but static local variables also exist, notably in C. For a static
local variable, the allocation is static (the lifetime is the entire program
execution), not automatic, but it is only in scope during the execution of the
function.
Automatic variables may be allocated in the stack frame
of the procedure in which they are declared; this has the useful effect of
allowing recursion and re-entrancy. (For efficiency, the optimizer will try to
allocate some of these variables in processor registers.)
Question No 6. What is the use of external
Storage Devices? Explain any two external storage devices
External storage Devices:-
comprises devices that temporarily store information
for transporting[citation needed] from computer to computer. Such devices are
not permanently fixed inside a computer.
Semiconductor memories are not sufficient to provide
the whole storage capacity required in computers. The major limitation in using
semiconductor memories is the cost per bit of the stored information. So to
fulfill the large storage requirements of computers, magnetic disks, optical
disks are generally used.
Advantages of external storage[edit]
External storage devices provides additional storage
other than that available in computer.
Data can be transported easily from one place to
another.
It is useful to store software and data that is not
needed frequently.
External storage also works as data back up.
This back up may prove useful at times such as fire or
theft because important data is not lost.
Types of external storage[edit]
Magnetic storage[edit]
Cassette tape
Floppy disk
Optical storage[edit]
Optical media are the media that use laser light
technology for data storage and retrieval.
Optical storage devices
CD[edit]
CD stands for Compact Disc. The speed is much lesser
than a hard disk. The storage capacity is 700 MB. Types of CDs include:
CD-ROM: It is Compact Disc Read Only Memory. It can be
read only.
CD-Recordables: It was invented in 1990s. Using CD-R,
it is possible to write data once on a disc. These are write once, read many
disks.
CD-ReWritables: There is a limit on how many times a
CD-RW can be written. Presently this limit is 1000 times. CD-RW drives are
compatible with CD-ROM and CD-R.
DVD[edit]
DVD stands for Digital Versatile Disc. Its speed is
much faster than CD but not as fast as hard disk. The standard DVD-5 technology
has a storage capacity of 4.7 GB. The storage capacity changes with the
standard used. Its storage capacity (4.7 GB) is much higher than a CD (700 MB).
It is achieved by a number of design changes.
Solid state storage[edit]
Flash memory is a solid state memory. It was invented
in 1980s by Toshiba. A flash memory is a particular type of EEPROM
(Electrically Erasable Programmable Read Only Memory). It is a no-volatile
memory. It retains the stored information without requiring a power source.It
is called as solid state memory because it has no moving parts. Flash memory is
different from the regular EEPROM. In case of EEPROM data are erased one byte
at a time which makes it extremely slower. On the other hand data stored in
flash memory can be erased in blocks. That’s why it gets a name “flash memory”
because the chip is organised in such a way that a block of memory cells can be
erased at a single time or “flash”.
Advantages of flash memory[edit]
It has no moving parts and is therefore very durable
and less susceptible to mechanical damages.
It is small in size and light in weight. Hence it is
extensively used in portable devices.
Flash memory transfers data at a faster rate.
As erasing of information in blocks is possible, flash
memories are useful in devices where frequent updating of data is required
Disadvantages of flash memory[edit]
The cost of flash memory is high as compared to hard
disk. Memory card (for example, CompactFlash) with a 192MB capacity typically
costs more than a hard drive with a capacity of 40 GB.
The storage capacity of a flash memory is far less than
a hard disk.
Flash memory devices[edit]
Memory card: Memory cards are flash memory storage
media used to store digital information in many electronics products. The types
of memory cards include CompactFlash, PCMCIA, secure digital card, multimedia
card, memory stick etc.
Memory stick: Sony introduced memory stick standard in
1998. Memory stick is an integrated circuit designed to serve as a storage and
transfer medium for digital data. It can store data in various form as text,
graphics, digital images etc. transfer of data is possible between devices
having memory stick slots. Memory sticks are available in various storage sizes
ranging from 4MB to 64GB. The dimensions of a memory stick are 50mm long,
21.5mm wide and 2.8mm thick (in case of pro format). The transfer speed of
memory stick is 160 Mbit/s.
………………………………………………………………………………………………………………………………………………………………………
Nice dost
ReplyDelete