Laynetworks  
Web laynetworks.com Google
Home | Site Map | Tell a friends
Management Tutorials
Download
Tutorials
History
Computer Science
Networking
OS - Linux and Unix
Source Code
Script & Languages
Protocols
Glossary
IGNOU
Quiz
About Us
Contact Us
Feedback
 
Sign up for our Email Newsletter
 
Get Paid for Your Tech Turorials / Tips

 

 

Home > Computer Science > Computer Fundamentals
 
CS 01 CS 02 CS 03 CS 04 CS 05 CS 06 CS 07 CS 08 CS 09 CS 10 CS 11 CS 12 CS 13 CS 14 CS 15 CS 16 CS 17
 
Computer Fundamentals
 

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.

 
Top  
Back Next
 
Donation | Useful links | Link to Laynetworks.com | Legal | SharePoint Development
Copyright © 2000-2010 Lay Networks All rights reserved.