Files:
File organization is done to
have a
1. Ease of retrieval
2. Convenience of updates
3. Economy of storage
4. Reliability
5. Security
6. Integrity
Commonly used Files Organizations
1. Sequential: Stored & fetched
as they appear.
2. Relative: Will have a fixed
place & records have to be
placed that order only.
3. Direct: Same as relative except
the key value need not be integer.
4. Indexed Sequential: A n index
is added to sequential file &
sequence is imposed.
5. Indexed: Just as indexed sequential
but without sequence, it can have
multiple indexes.
ü Static Indexing
ü Dynamic indexing
Graph:
A Graph G consists of a set V
of vertices and a set E of edges
as G=(V, E). V is a finite &
non-empty set of vertices. E is
a set of pairs of vertices.
In Directed Graph the direction between two nodes
is not same, i.e. G (v, w) !=
G(w, v).
Vertex v1 is said to be adjacent
to a vertex v2, iff there exists
edge (v1, v2) or (v2, v1).
A Cycle is a
path in which first & last
vertices are the same.
A graph is called connected if
there exists a path from any vertex
to any other vertex.
A Digraph, the path is called
directed path and a cycle as directed
cycle. A digraph is called strongly
connected, if there is a directed
path from any vertex to any other
vertex. The number of edges for
a node is known as Degree.
Indegree is the incoming direction
to a node & outdegree is the
outgoing direction from a node.
A graph can be represented by
1. Adjacent Matrix
Dis ad: It takes O(n^2) space
to represent a graph with n vertices
It takes n^2 time to solve the
graph problem
2. Adjacent List, with the help
of liked list. It takes only O
(V+E) to represent.
Graph can be traversed using
1. Depth first search (DFS),
implemented using a stack.
2. Breadth first search (BFS),
implemented using a Queue.
A path having a minimum weight
between two vertices is known
as shortest path, in which the
weight is always a non-negative
number. Length of the path is
the sum of the weights on that
path.
A single source vertex &
we seek a shortest path from this
source vertex V to every other
vertex of the graph is known as Single source shortest
path.
A structure
1. The vertex is set is same
as that of Graph G
2. The edge set is a subset of
G(E)
3. There is no cycle.
Such a structure is called Spanning
tree. A tree T is a spanning
tree of a connected graph
G(V, E) such that
1. every vertex of G belongs
to an edge in T
2. The edges in T form a tree.
A technique of building a spanning
tree with minimum cost & weight
is known as Minimum Spanning
tree.
Shortest path trees are
Rooted and minimum spanning trees
are free trees.
To build the MST we use Kruskal’s
method.
Searching & Sorting
Searching a key value in a set
of entities using two ways
1. Linear Search
2. Binary Search
Sorting of records are done
at two different levels
1. Internal
ü Insertion Sort
ü Bubble sort
ü Quick sort
ü 2-Way Merge Sort
ü Heap Sort.
2. External
ü Balanced Merged sorts
ü Random using Runs
ü K-way merging
ü Using Buffering. |
