WARSHALL’S ALGORITHM

WARSHALL’S ALGORITHM

SOURCE CODE:


#include “ stdio.h “
#include “ conio.h “
void main()
{
int n,i,j,k,p[10][10],a[10][10];
clrscr();
printf("Enter The Number Of Nodes: ");
scanf("%d",&n);

for(i=0;i < n;i++)
{
printf("\n");
for(j=0;j < n;j++)
{
scanf("%d",&a[i][j]);
}
}
for(i=0;i < n;i++)
{
for(j=0;j < n;j++)
{
if(a[i][j]==0)
p[i][j]=0;
else
p[i][j]=1;
}
}
for(k=0;k < n;k++)
{
for(i=0;i < n;i++)
{
for(j=0;j < n;j++)
{
p[i][j]=p[i][j]||(p[i][k]&&p[k][j]);
}
}
}
printf("\n");
for(i=0;i < n;i++)
{
for(j=0;j < n;j++)
{
printf("%d ",p[i][j]);
}
printf("\n");
}
getch();
}



OUTPUT:


Enter The Number Of Nodes: 4

0
1
0
0

0
0
0
1

0
0
0
0

1
0
1
0

1 1 1 1
1 1 1 1
0 0 0 0

HUFFMAN ALGORTHAM

HUFFMAN ALGORTHAM

CODING:

#include ” stdio.h “
#include “ conio.h “
#define true 1
#define false 0
#define MAXBITS 50
#define MAXSYMBS MAXBITS
#define MAXNODES 2*MAXSYMBS-1
struct codetype
{
int bits[MAXBITS];
int startpos;
};
struct nodetype
{
int frequency;
int parent;
int isleft;
};
void pqinsert(int);
int pqmindelete();
struct nodetype node[MAXNODES];
void main()
{
struct codetype cd,code[MAXSYMBS];
int i;
int no_of_symbols;
int nextavilnode;
int bitcounter;
int leftnode,rightnode;
int root;
int thisnode;
char symbol,alphabet[MAXSYMBS];
clrscr();
for(i=0;i < MAXSYMBS;i++)
{
alphabet[i]=' ';
}
printf("Enter the no-of-symbols:");
scanf("\n%d",&no_of_symbols);
printf("\nEnter the symbol and frequency:");
for(i=0;i < no_of_symbols;i++)
{
scanf("%s%d",&symbol,&node[i].frequency);
pqinsert(i);
alphabet[i]=symbol;
}



for(nextavilnode=no_of_symbols;nextavilnode < 2*no_of_symbols-
1;nextavilnode++)
{
leftnode=pqmindelete();
rightnode=pqmindelete();
node[leftnode].parent=nextavilnode;
node[rightnode].parent=nextavilnode;
node[leftnode].isleft=true;
node[rightnode].isleft=false;
node[nextavilnode].frequency=node[leftnode].frequency+node[rightnode].
frequency;
pqinsert(nextavilnode);
}
root=pqmindelete();
for(i=0;i < no_of_symbols;i++)
{
cd.startpos=MAXBITS;
thisnode=i;
while(thisnode!=root)
{
--cd.startpos;
cd.bits[cd.startpos]=node[thisnode].isleft?0:1;
thisnode=node[thisnode].parent;
}
for(bitcounter=cd.startpos;bitcounter < MAXBITS;bitcounter++)
{
code[i].bits[bitcounter]=cd.bits[bitcounter];
}
code[i].startpos=cd.startpos;
}
printf("\nSymbols Frequency AssignBits");
for(i=0;i < no_of_symbols;i++)
{
printf("\n%c\t%d\t\t",alphabet[i],node[i].frequency);
for(bitcounter=code[i].startpos;bitcounter < MAXBITS;bitcounter++)
{
printf("%d",code[i].bits[bitcounter]);
}
Printf("\n");
}
getch();
}
int rootnodes=-1;
void pqinsert(int which)
{
int thisnode,previous;
if(rootnodes==-1)
{
node[which].parent=-1;
rootnodes=which;
}
else
{
thisnode=rootnodes;
previous=-1;

while(thisnode!=-1&&node[thisnode].frequency < node[which].frequency)
{
previous=thisnode;
thisnode=node[thisnode].parent;
}
node[which].parent=thisnode;
if(previous!=-1)
{
node[previous].parent=which;
}
else
{
rootnodes=which;
}
}
}
int pqmindelete()
{
int thisnode=rootnodes;
rootnodes=node[thisnode].parent;
return thisnode;
}








OUTPUT:

Enter the no-of-symbols:4

Enter the symbol and frequency:
S 21
H 28
A 11
M 7

Symbols Frequency AssignBits
S 21 11

H 28 0

A 11 101

M 7 100

Implementation of Queues

Linked Implementation of Queues
The items are deleted from the front of a queue and inserted at the rear. A pointer to the first element of a list represent the front of the queue. Another pointer to the last element of the list represent the rear of the queue. If (empty(q))
{
Printf(“Queue underflow”);
Exit(1);
}
P=q.front;
X=info(p);
q.front=next(p) ;
if(q.front == null)
q.rear = null;
freenode(p);
return(x);
The operation insert(q,x) is implemented by
P = getnode();
Info(p) = x;
Next(p) = null;
If (q.rear == null)
q.front = p;
else
next(q.rear) = p;
q.rear = p;

Linked Implementation of Queues

Linked Implementation of Queues

The items are deleted from the front of a queue and inserted at the rear. A pointer to the first element of a list represent the front of the queue. Another pointer to the last element of the list represent the rear of the queue.

If (empty(q))

{

Printf(“Queue underflow”);

Exit(1);

}

P=q.front;

X=info(p);

q.front=next(p) ;

if(q.front == null)

q.rear = null;

freenode(p);

return(x);

The operation insert(q,x) is implemented by

P = getnode();

Info(p) = x;

Next(p) = null;

If (q.rear == null)

q.front = p;

else

next(q.rear) = p;

q.rear = p;

Array implementation of lists

Array implementation of lists

A list is simply a collection of nodes, the nodes cannot be ordered by the array ordering; each contain within itself a pointer to its successor. Thus a group of 500 nodes might be declared as an array node as follows.

#define NUMNODES 500

Struct nodetype

{

Int info, next;

};

Struct nodetype node[NUMNODES];

Limitations of the Array Implementation

Under the array implementation, a fixed set of nodes represented by an array is established at the start of execution.

The number of nodes that are needed often cannot be predicted when a program is written.

The number of nodes are declared must remain allocated to the program throughout its execution.

The solution to this problem is to allow nodes that are dynamic rather than static.

Allocating and Freeing Dynamic Variables

Allocating and Freeing Dynamic Variables

If X is any object, &X is a pointers to help implement dynamic linked lists.
In C a pointer variable to an integer can be created by the declaration

Int *p;

Once a variable p has been declared as a pointer to a specific type of object, it must be possible to dynamically create an object of that specific type and assign its address to p.

Malloc dynamically allocates a portion of memory and returns a pointer to an item.

Pi = (int *) malloc(sizeof(int));

Pr = (float *)malloc(sizeof(float));



Linked list using Dynamic variables

The capability of dynamically allocating and freeing a variable.

Struct node
{
Int info;
Struct node * next;
};


Tydedef struct node *NODEPTR;

NODEPTR p;

P=getnode();

NODEPTR getnode()
{
NODEPTR p;
P = (NODEPTR) malloc(sizeof(struct node));
Return(p);
}


Freenode(p);

Circular List

Circular List

The stack as a Circular List

Empty(pstack)

NODEPTR 8pstack;
{
Return((*pstack == NULL) ? TRUE : FALSE);
}




Push(pstack, x)

NODEPTR *pstack;
Int x;
{
NODEPTR P;
P = getnode();
p->info = x;
if (empty(pstack) == TRUE)
*pstack = p;
Else
p->next = (*pstack)->next;
(*pstack) -> next = p;
}



Pop(pstack)

NODEPTR *pstack;
{
Int x;
NODEPTR p;
If (empty(pstack) == TRUE)
{
Printf(“stack underflow”);
Exit(1);
}
P=(*pstack) -> next;
X=p->info;
If ( p == *pstack)
*pstack = NULL;
Else
(*pstack) - > next = p->next;
Freenode(p);
Return(x);
}

Data Structures Lab Manual

Lab Manual Algorithms

Program List


1. Stack using Arrays

2. STACK using Linked List

3. Queues using Arrays

4. Queue using Linked List

5. Tree Traversal

6. Merge sort

7. Graph using DFS

8. Graph Traversal using BFS

9. Warshall’s Algorithm

10. Dijkstra’s Algorithm

11. Huffman Algorithm

12. Insertion sort

Stack using Arrays

Representation of Stack using Arrays

Algorithm:

Step 1: Create a push operation with one argument, the element to be added

Step 2: Create a POP function with one argument, the address of the element to store the popped operation

Step 3: Create a function PEEK with one argument, the address of the element of store the top value

Step 4: Create a function ISEMPTY with no argument for stack empty condition

Step 5: Create a function ISFULL for checking for stack full.

Step 6: Sop the program execution

STACK using Linked List

Representation of STACK using Linked List

Algorithm:


Step 1: Create a structure with data and Link field

Step 2: Allocate the memory for the new node

Step 3: Insert the value into the new node using PUSH operation

Step 4: Release the allocated memory for deleting the item from the structure

Step 5: Create a function to retrieve the contents from the Top of the Stack

Step 6: Create a function for display the items from the stack.

Step 7: Create a function for Is Empty condition

Step 8: Create a function for Is Full condition.

Step 9: Create a function to count the number of nodes in the stack.

Step 10 : Stop the execution.

Queues using Arrays

Queues using Arrays

Algorithm


Step 1: Create a function Enqueue() with two arguments

Step 2: Assign the new element in the array by increasing the Rear variable.

Step 3: Create a function Dequeue with two arguments

Step 4: Increment the Front variable by 1.

Step 5: Create a function Isempty with no arguments

Step 6: Check whether the front pointer and rear is equal to zero.

Step 7: If true, the queue is empty otherwise not empty.

Step 8: Create a function Isfull to check whether the queue is full or not.

Step 10 : Stop the execution.

Queue using Linked List

Representation of Queue using Linked List

Algorithm:

Step 1: Create a structure with data and link field.

Step 2: Allocate a memory for the new node using a getnode().

Step 3: Insert the item into the queue

Step 4: Delete the node by releasing the memory of the node.

Step 5: create a function to retrieve the contents from the top of the queue.

Step 6: Display the contents of the queue by traversing through the queue.

Step 7: Stop the execution.

Tree Traversal

Binary Search Tree Traversal

Aim : To create a binary search tree and do the following traversal

Algorithm :

Preorder Traversal

preorder(node)
print node.value
if node.left ≠ null then preorder(node.left)

if node.right ≠ null then preorder(node.right)

Inorder Traversal

inorder(node)
if node.left ≠ null then inorder(node.left)
print node.value
if node.right ≠ null then inorder(node.right)

Post Order Traversal

postorder(node)
if node.left ≠ null then postorder(node.left)
if node.right ≠ null then postorder(node.right)
print node.value

Merge sort

Merge sort

Aim : To sort the given elements using Merge Sort

Algorithm:

function merge_sort(m)
var list left, right, result
if length(m) < = 1
return m
var middle = length(m) / 2 - 1
for each x in m up to middle
add x to left
for each x in m after middle
add x to right

left = merge_sort(left)
right = merge_sort(right)
if left.last_item > right.first_item
result = merge(left, right)
else
result = append(left, right)
return result

function merge(left,right)
var list result
while length(left) > 0 and length(right) > 0
if first(left) < = first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
end while
if length(left) > 0
append left to result
else
append right to result
return result

Graph using DFS

Depth-first search

Aim : Program to traverse a graph using DFS

Algorithm:

Step 1: consider that the DFS is beginning from the starting vertex A. Process the vertex A and mark it as visited.

Step 2: Using the adjacency matrix of the graph find the vertex along the path which begins vertex A, that has not been visited yet. Process the vertex and consider this as the new vertex and mark the vertex as visited.

Step 3: Repeat Step 2 using the new search vertex. If no vertices back track to the previous node and continue the search from there.

Step 4: When backtracking to the previous search node in step 3 is impossible, the search from the originally chosen search node is complete.

Step 5: If the graph still contains unvisited nodes, choose any vertex that has not been visited and repeat step 1 to 4.

Graph Traversal using BFS

Breadth-first search

Aim : Program to demonstrate Graph Traversal using BFS

Algorithm:

Step 1: Consider any vertex in the graph. Process the vertex A and mark it as visited.

Step 2: Using the adjacency matrix of the graph proceed to the next vertex which has an edge connection wise the vertex considered in step 1.

Step 3: Backtrack to the vertex considered in step 1 descend along an edge towards an unvisited vertex and mark the new vertex as visited

Step 4: Repeat step3 until all vertices adjacent to the node in step 1 have been marked as visited.

Step 5: Stop the execution

Warshall’s Algorithm

Aim : To create a program to find the shortest path in a given graph using Warshall’s Algorithm.

Algorithm :

for(i=0; i < MAXNODES; ++i)
for(j=0; j < MAXNODES; ++j)
path[i][j]=path k-1[i][j] (path k-1[i][k] && path k-1[k][j]);


for(i=0; i < MAXNODES; ++i)
for(j=0; j < MAXNODES; ++j)
path k[i][j] = path k-1[i][j];
for(i=0;i < MAXNODES; ++i)
if(path k-1[i][k] == TRUE)
for(j=0;j < MAXNODES; ++j)
path k[i][j] = path k-1[i][j] path k-1[k][j];

Dijkstra’s Algorithm

Aim: To create a program to find the shortest path in a given graph using Dijkstra’s Algorithm.

Algorithm :

function Dijkstra(Graph, source):
for each vertex v in Graph:
dist[v] := infinity
previous[v] := undefined
dist[source] := 0
Q := the set of all nodes in Graph
while Q is not empty: // The main loop
u := vertex in Q with smallest dist[]
if dist[u] = infinity:
break
remove u from Q
for each neighbor v of u:
alt := dist[u] + dist_between(u, v)
if alt < dist[v]:
dist[v] := alt
previous[v] := u
return previous[]

Huffman Algorithm

Aim : Program for performing the Huffman Algorithm

Algorithm:


For(i=0;i < n; i++)
{
P=maketree(frequency[i]);
Position[i] = p;
Pqinsert(rootnodes, p);
}
While (root nodes contain more than one item)
{
P1=pqmindelete(rootnodes);
P2=pqmindelete(rootnodes);
P=maketree ( info (p1) + info (p2));
Setleft(p, p1);
Setright (p, p2);
Pqinsert(rootnodes, p);}

Root= pqmindelete(rootnodes);
For(i=0;i < n;i++)
{
P=position[i];
Code[i]=the null bit string;
While (p!= root)
{
If(isleft (P))
Code[i]= 0 followed by code[i];
Else
Code[i] = 1 followed by code[i];
P=father(p);
}
}

Insertion sort

Aim: Program to sort the given numbers using Insertion sort.

Algorithm:

insertionSort(array A)

begin
for i := 1 to length[A] - 1 do
begin
value := A[i];
j := i - 1;
while j >= 0 and A[j] > value do
begin
A[j + 1] := A[j];
j := j - 1;
end;
A[j + 1] := value;
end;
end;

INFIX, POSTFIX, AND PREFIX

INFIX
POSTFIX
PREFIX

A major application that illustrates the different types of stacks and the various operations and functions defined upon them.

A + B à Infix
+ AB à prefix
AB+ à postfix

A + (B * C)
A + (BC*)
A(BC*)+
ABC * +

The following is the order of precedence (highest to lowest)

Exponentiation

Multiplication / division
Addition / subtraction

Infix

A+B
A + B – C
(A+B) * (C – D)
A $ B * C – D + E / F / (G + H)

postfix

AB+
AB + C –
AB+ CD- *
AB$C*D-EF / GH + / +

Prefix

+AB
- + ABC
* + AB – CD
+ - * $ ABCD / / EF + GH


Evaluating a postfix Expression

Algorithm:

Opndstk = the empty stack;
While ( not end of input)
{
Symb = next input character;
If ( symb is an operator)
Push(opndstk, symb);
Else
{
Opnd2 = pop(opndstk);
Opnd1 = pop(opndstk);
Value = result of applying symb to opnd1 and opnd2;
Push(opndstk, value);
}
}
Return(pop(opndstk));


Example:

6 2 3 + - 3 8 2 / + * 2 $ 3 +

Garbage Collection

Routine for Garbage Collection

# include"stdio.h"
# include"conio.h"
# include"iostrem.h"
struct cell
{
int mark:1;
struct cell *c[2];}
struct cell *free;
struct cell heap[HEAPSIZE];
struct cell *roots[ROOTS];

/* Initially all cells are on free list. Use c[0] to link members of free list. */
void init_heap()
{
for (i=0; i < HEAPSIZE-1; i++)
heap[i].c[0] = &(heap[i+1]);
heap[HEAPSIZE-1].c[0] = 0;
free = &(heap[0]);
}

struct cell *allocate()
{
struct cell *a;
if (!free) { /* no more room => */
gc(); /* try gc */
if (!free) /* still no more room */
die();
};
a = free;
free = free->c[0];
return a;


void gc()
{
for (i = 0; i < ROOTS; i++)
mark(roots[i]);
sweep();
}

void mark(struct cell *cell)
{
if (!cell->mark)
{
cell->mark = 1;
mark(cell->c[0]);
mark(cell->c[1]);
}
}

void sweep()
{
for (i = 0; i < HEAPSIZE; i++)
if (heap[i].mark)
heap[i].mark = 0;
else
{
heap[i].c[0] = free;
free = &(heap[i]);
}
}

Copying Collection

Suitable routine for copying collection

struct cell
{
struct cell *c[2];
}

struct cell space[2][HALFSIZE];
struct cell *roots[ROOTS];
struct cell *free = &(space[0][0]);
struct cell *end = &(space[0][HALFSIZE]);
int from_space = 0;
int to_space = 1;
struct cell *allocate()
{
if (free == end) { /* no room */
gc();
if (free == end) /* still no room */
die();
};
return free++;
}

gc()
{
int i;
struct cell *scan = &(space[to_space][0]);
free = scan;
for (i = 0 ; i < ROOTS; i++)
roots[i] = forward(roots[i]);

while (scan < free)
{
scan->c[0] = forward(scan->c[0]);
scan->c[1] = forward(scan->c[1]);
scan++;
};
from_space = 1-from_space;
to_space = 1-to_space;
end = *(space[from_space][HALFSIZE]);
}

struct cell *forward(struct cell *p)
{
if (p >=&(space[from_space][0]) && p < &(space[from_space][HALFSIZE]))
if (p->c[0] >= &(space[to_space][0]) && p->c[0] < &(space[to_space][HALFSIZE]))
return p->c[0];

else
{
*free = *p;
p->c[0] = free++;
return p->c[0];
}
else return p;
}

ALGORITHM Mark and sweep

5.7.2.4.1 ALGORITHM : Mark and sweep

// The first tracing garbage collection algorithm.
// The mark-sweep algorithm is invoked when the mutator requests memory but there is
// insufficient free space.
// The mutator is stopped while the mark-sweep is executed.
// Mark phase: Identifies all reachable objects by setting a mark
// Sweep phase: Reclaims garbage objects

function DFS(x) {
if (x is a heap pointer)
if (x is not marked)
{
mark x
for(i = 1; i <= │x│; i++)
DFS(x,f1)
}
}

function Mark() {
for each (v in a stack frame)
DFS(V)
}
function Sweep() {
p = first address in heap
while (p < last address in heap)
{
if (p is marked)
unmark p;
else
{
p. f1 = freelist
freelist = p
}

p = p + sizeof(p)
}
}

Collections And Compaction

5.8 Collections And Compaction

Once the memory locations of a given system have been marked appropriately, the collection phase may begin. The purpose of the phase is to return to available memory all those locations that were previously garbage. (Not used by any program but unavailable to any user) It is easy to pass through memory sequentially, examine each node in turn, and return unmarked nodes to available storage.

5.8.1 Stop And Copy Algorithm

Garbage collection approach that collects garbage and defragments the heap is called stop and copy. In stop and copy garbage collection algorithm, the heap is divided into two separate regions/spaces. At any point in time, all dynamically allocated object instances reside in only one of the two regions the active region. The other, inactive region is unoccupied.

Copying garbage collection does not really “collect” garbage. Rather, it moves all the live objects into one area, and the rest of the heap is available which is only garbage. Garbage collection in these systems is only implicit. While mark and compact collectors 3 use a separate marking phase that traverses the live data, copying collectors integrate the traversal of the data and the copying process, so that most objects need only be traversed once. Objects are moved to the contiguous destination area as they are reached by the traversal. The work needed is proportional to the amount of live data.

18a. A simple semi region garbage collector before garbage collection

When running program demands an allocation that will not fit in the unused area of the current region (semi space) or if the memory in the active region is exhausted, the program is suspended or stopped and the garbage collection algorithm is invoked to reclaim space. The stop and copy algorithm copies all of the live objects from the active region to the inactive region. As each object is copied, all references contained in that object are updated to reflect the new locations of the referenced objects.

Stop and Copy garbage collection

Before and after Stop and copy garbage collection

For convenience, we can view each region as a separate heap and we shall refer to them as activeHeap and inactiveHeap. When the stop-and-copy algorithm is invoked, it copies all live objects from the activeHeap to the inactiveHeap. It does so by invoking the copy method given below starting at reach root:

for each root variable r

r = copy (r, inactiveHeap);

swap (activeHeap, inactiveHeap);

The copy method is complicated by the fact that it needs to update all object references contained in the objects as it copies those objects. In order to facilitate this, we record in every object a reference to its copy. That is, we add a special field to each object called forward which is a reference to the copy of this object.

The recursive copy method given below, copies a given object and all the objects indirectly accessible from the given object to the destination heap. When the forward field of an object is null, it indicates that the given object has not yet been copied. In this case, the method creates a new instance of the object class in the destination heap. Then, the fields of the object are copied one-by-one. If the field is a primitive type, the value of that field is copied. However, if the field refers to another object, the copy method calls itself recursively to copy that object.

If the copy method is invoked for an object whose forward field is non-null, that object has already been copied and the forward field refers to the copy of that object in the destination heap. In that case, the copy method simply returns a reference to the previously copied object.

The following figure shows the execution of the stop-and-copy garbage collection algorithm. When the algorithm is invoked and before any objects have been copied, the forward field of every object in the active region is null as shown in figure 19(a).

The figure 19(b) shows a copy of object A, called A', has been created in the inactive region, and the forward field of A refers to A'.

Since A refers to B, the next object copied is object B. As shown in Figure 19(c), fragmentation is eliminated by allocating storage for B' immediately next to A'. Next, object C is copied. Notice that C refers to A, but A has already been copied. Object C' obtains its reference to A' from the forward field of A as shown in Figure 19(d).

questi

questions

questions

questions

questions

questions

ALGORITHM for Stop and Copy

5.8.1.1 ALGORITHM

Stop and Copy

Object copy (Object p, Heap destination)

if (p == null)
return null;
if (p.forward == null)

q = destination.newInstance (p.class);
p.forward = q;

for each field f in p

if (f is a primitive type)
q.f = p.f;
else
q.f = copy (p.f, destination);

q.forward = null;
return p.forward;



Further Issues

1. Distinguishing pointers from integers.
2. Handling records of variable size.
3. Finding the root set.
4. Avoiding repeated copying of permanently live data.
5. Avoiding nasty pauses during collection.

The stop and copy algorithm incurs two costs

First cost is the algorithm requires that all live objects be copied every time garbage collection is invoked. If an application program has a large memory, the time required to copy all objects could be quite significant.

A second cost associated with stop-and-copy is that it requires twice as much memory as the program actually uses. When garbage collection is finished, at least half of the memory space is unused.

Variations of Garbage Collection

5.8.2 Variations of Garbage Collection

There are number of recently discovered variations of the garbage collection system just presented. In the traditional schemes we have considered, the applications programs function as long as space availability of the system satisfies certain criteria (These criteria May relate to the total amount of free space available the number and size of contiguous memory location available, the amount of memory requested since the lost garbage collection space, so forth) When these criteria are no longer met, all application programs halt and the system directs its resources to garbage collection. Once the collection has completed, the application program may resume execution from the point at which they were interrupted.

In some situation, however, that is not satisfactory. Applications that are executing in real time cannot be halted while the system is performing garbage collection. In this circumstance it is usually necessary to dedicate a separate processor devoted exclusively to the garbage collection. When the system signal that garbage collection must be performed, the separate processor begin executing concurrently with the applications programs. Because of this simultaneous execution it is necessary to guarantee that node that are in the process of being acquired for use by an application program are not mistakenly return to the available pool by the calculator. Avoiding such a problem is not a trivial process. Systems that allow the collection process to proceed simultaneously with the application program use “on-the-fly” garbage collection.

Another subject of interest deals with minimizing the cost of reclaiming unused space. In the methods we have discussed, the cost of reclaiming any portion of storage is the same as the cost of reclaiming any other portion (of the same size) Recently attention of storage is proportional to its lifetime. It has been shown empirically that some portions of memory are required for smaller time intervals than are others and that requests for portions of memory with smaller lifetime acquires more frequently than do request for portions of memory with longer lifetime. Thus, by reducing the cost of retrieving portions of memory require for short time periods that the expense of the cost of retrieving portions of memory with longer life spans, the overall cost of the garbage collection process will be reduced.

The process of garbage collection is also applied to reclaiming unused space in secondary device (For example, a disk). Although the concept of allocation and freeing space is the same (that is, space may be requested or released by a program) algorithms that manage space such devices often cannot be translated efficiently from the their counterparts that manipulated main memory. The reason for this is that the cost of accessing any location in main memory is the same as that of accessing any other locations in main memory. In secondary storage, on the other hand, the cost depends on the locations of storage that is currently being accessed as well as the location we desire to access. It is very efficient to access a portion of secondary storage that is in the same block that is now being accessed; to access the location in a different block may involve expensive disk seeks.