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.