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.