Hash Table

If we have a table organization and a search technique which retrieve the key in a single access ,it would be very efficient. To do so, the position of the key in the table should not depend upon the other keys but the location should be calculated on the basis of the key itself .Such an organization and search technique is called hashing .

In hashing the address or location of an identifier X is obtained by using some function f(X) which gives address of X in a table.

HASHING TERMINOLOGY
Hash function :- A function that transforms a key X into a table index is called a hash function.

Hash address:- The address of X computed by the hash function is called the hash address or home address of X.

Hash Table :- The memory available to maintain the symbol table is sequential . This is referred to as hash table .

Bucket :- Each hash table is partitioned into b buckets ht[0]......ht[b-1].
Each bucket is capable of holding 's' records . Thus , a bucket consists of 's' slots. When s=1 , each bucket can hold 1 record.
The function f(X) maps and identifier X into one of the 'b' buckets i.e. from 0 to b-1.

Synonyms :- Usually , the total number of possible values for identifier X is much larger  than the hash table size. Therefore the hash function f(X) must map several identifiers into the same bucket .
Two identifiers I1 and I2 are synonyms  if   f(I1) = f(I2)

Collision :- When two non identical identifiers are mapped into the same bucket , a collision is said to occur , i.e. f(I1)= f(I2). Hence all synonyms occupy the same bucket.

Overflow :- An overflow is said to occur when an identifier gets mapped onto a full bucket.
When s=1 ,i.e. ,a bucket contains only one record ,collision and overflow occur simultaneously . Such a situation is called a Hash clash.

Load factor :- If n is the total number of identifiers in the table and t is the table size , the load factor is : lf = n/t
It represents the fraction of the table that is occupied .

HASHING FUNCTION
A hashing function f transforms an identifier X  into a bucket address in the hash table .The desirable properties of such a function are as follows.
i.  It should be easily computable .
ii. It should minimize the number of collisions .
iii. The hash function should compute the address,which depends on all or most of the characters in the identifier .
iv.  It should yield uniform bucket addresses for random inputs . Such a function is called a uniform hash function.
Several uniform hash functions are in use some of them are
1 Mid Square
2 Division
3 Folding
4 Digit Analysis

Templates in C++

C++ supports a mechanism known as template to implement the concept of generic programming .

Templates allows us to generate a family of classes or a family of functions to handle different types.

Template classes and functions eliminate code duplication for different types and thus make the program development easier and more manageable.

We can use multiple parameters in both the class templates and function templates.

A specific class created from a class template is called a template class and the process of creating a template class is known as instantiation. Similarly, a specific function created from a function template is called a template function.

Like other functions, template functions can be overloaded.

Member functions of a class template must be defined as function templates using the parameters of the class template.

We may also use non - type parameters such basic or derived data types as arguments templates.

Congestion in networking

What is congestion?
Congestion is traffic.
Interference of two or more packets .
Reasons:-  Sending packets the same time.

Definition:  Congestion is a situation in which number of packets in network is greater than capacity of network or channel.

Total load > Capacity of channel  ,
is the main reason of congestion

Effect of congestion :-
Two main factors are affected by congestion
1) Delay versus load.
2) Throughput versus load.

When load is less than network capacity delay is permission and vice versa .
Delay depends on propagation delay and transmission delay .
propagation time , transmission time, buffer time
Congestion is directly  proportional to Delay
and
Congestion is directly proportional to Load

Throughput:-
Number of packets successfully delivered is called throughput .
Throughput is inversely proportional to congestion

When less congestion all packets will be successfully delivered means high throughput.

causes of congestion :
If number of packets are same .
If buffer capacity is less .
Insufficient memory buffer .
Slow processor .
Low bandwidth (capacity ) line if channel.
Failed router or processor .
If there is excess traffic to some specific host .

Congestion control:
It refers to technique and mechanism that can either defend congestion or remove congestion .

Two main types of congestion control :
1 ) Open loop ( prevention )
2 ) Closed loop ( removal ) the collision

1) Open loop :-
1. It is either handled by source or destination .
2. Retransmission property.
3. Use of sliding window protocol .example Selectivity.
4. Use of piggy bank acknowledgement .
5. Decision of discarding policy.

2. Closed loop congestion :-
Removal of congestion
1 by using CSMA policy
2 monitoring the system for congestion .
3 dynamically increase buffer capacity
4 if congestion detect at any point inform to all routers within that path
5 dynamically decides the router or path.

 

Microcontroller

A microcontroller is  a complete microprocessor system ,containing of microprocessor ,limited amount of ROM RAM and parallel I/O ports ,built on a single integrated circuit .
Microcontroller is in fact a microcomputer ,but it is called so because it is used to perform control functions .
Expanded features of 8052 over 8051 microcontroller are as follows:
a) ROM  :- Microcontroller 8052 has 8 KB bytes onboard ROM or EPROM whereas 8051 has 4 KB  bytes  of ROM .
b)  RAM  :-    Microcontroller 8052 has 256 bytes of onboard RAM whereas 8051 has 128 bytes of RAM.
c)   Time event counter :- 8052 has an extra 16 bit time event counter whereas 8051 has a dual 16 bit time event counter.

C Program to Create Employee Record and Update it

    /*

     * C Program to Create Employee Record and Update it

     */

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define size 200

     struct emp
    {

        int id;
        char *name;
    }*emp1, *emp3;

    
    void display();
    void create();
    void update();

    
    FILE *fp, *fp1;
    int count = 0;
    

    void main(int argc, char **argv)

    {
        int i, n, ch;
   

        printf("1] Create a Record\n");
        printf("2] Display Records\n");
        printf("3] Update Records\n");
        printf("4] Exit");
        while (1)

        {
            printf("\nEnter your choice : ");
            scanf("%d", &ch);
            switch (ch)
            {
            case 1:   

                fp = fopen(argv[1], "a");
                create();
                break;

            case 2:   

                fp1 = fopen(argv[1],"rb");
                display();
                break;

            case 3:   

                fp1 = fopen(argv[1], "r+");
                update();
                break;

            case 4:
                exit(0);

            }

        }

    }

    

    /* To create an employee record */

    void create()

    {
        int i;

        char *p;

        emp1 = (struct emp *)malloc(sizeof(struct emp));
        emp1->name = (char *)malloc((size)*(sizeof(char)));
        printf("Enter name of employee : ");
        scanf(" %[^\n]s", emp1->name);
        printf("Enter emp id : ");
        scanf(" %d", &emp1->id);
        fwrite(&emp1->id, sizeof(emp1->id), 1, fp);
        fwrite(emp1->name, size, 1, fp);
        count++;   // count to number of entries of records
        fclose(fp);
    }

    
    /* Display the records in the file */

    void display()

    {   

        emp3=(struct emp *)malloc(1*sizeof(struct emp));   
        emp3->name=(char *)malloc(size*sizeof(char));
        int i = 1;
  

        if (fp1 == NULL)   
            printf("\nFile not opened for reading");
        while (i <= count)

        {
            fread(&emp3->id, sizeof(emp3->id), 1, fp1);
            fread(emp3->name, size, 1, fp1);
            printf("\n%d %s",emp3->id,emp3->name);
            i++;

        }

        fclose(fp1);
        free(emp3->name);
        free(emp3);

    }
   

    void update()

    {
        int id, flag = 0, i = 1;

        char s[size];

      if (fp1 == NULL)

        {
            printf("File cant be opened");
            return;

        }

        printf("Enter employee id to update : ");
        scanf("%d", &id);
        emp3 = (struct emp *)malloc(1*sizeof(struct emp));
            emp3->name=(char *)malloc(size*sizeof(char));
        while(i<=count)

        {   

            fread(&emp3->id, sizeof(emp3->id), 1, fp1);

            fread(emp3->name,size,1,fp1);

            if (id == emp3->id)

            {

                printf("Enter new name of emplyee to update : ");   

                scanf(" %[^\n]s", s);

                fseek(fp1, -204L, SEEK_CUR);

                fwrite(&emp3->id, sizeof(emp3->id), 1, fp1);

                fwrite(s, size, 1, fp1);

                flag = 1;

                break;

            }

            i++;

        }

        if (flag != 1)

        {

            printf("No employee record found");

            flag = 0;

        }

        fclose(fp1);

        free(emp3->name);        /* to free allocated memory */

        free(emp3);

    }

Program to sort numbers using counting sort and save the o/p in a file using FILE handling

/*********************************************************************
* Program to sort numbers using counting sort and save
* the o/p in a file using FILE handling
**********************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 500
void selection(int elements[], int maxsize);
int elements[MAXSIZE],maxsize;
void main()
{
int i;
FILE *f;
printf("\nHow many elements you want to sort: ");
scanf("%d",&maxsize);
printf("\nEnter the values one by one: ");
for (i = 0; i < maxsize; i++)
{
printf ("\nEnter element %i :",i);
scanf("%d",&elements[i]);
}
f=fopen("a.txt","w");
if(f==NULL)
{
printf("\nUnable to write in to the file\n");
exit(1);
}
//fprintf(f,"\nArray before sorting:\n");
//for (i = 0; i < maxsize; i++)
//fprintf(f,"[%i], ",elements[i]);
//fprintf (f,"\n");
selection(elements,maxsize);
//fprintf(f,"\nArray after sorting:\n");
fprintf(f,"\nSorted order is:\n");
for (i = 0; i < maxsize; i++)
fprintf(f,"[%i], ", elements[i]);
}


void selection(int elements[], int array_size)
{
int i, j, k;
int min, temp;
for (i = 0; i < maxsize-1; i++)
{
min = i;
for (j = i+1; j < maxsize; j++)
{
if (elements[j] < elements[min])
min = j;
}
temp = elements[i];
elements[i] = elements[min];
elements[min] = temp;
}
}

Javascript Program

 1) EVENT DRIVEN CLIENT SIDE SCRIPT.

STEP 1 – EVENT.HTML

<html>

<head>

<title> Event driven </title>

</head>

<body>

<input type=”button” value=”Colors” OnMouseOver=window.setTimeout(“f1()”,1200);>

<script language=”javaScript”>

function f1()

{

document.bgColor=”orange”;

window.setTimeout(“f2()”,1200);

}

function f2()

{

document.bgColor=”white”;

window.setTimeout(“f3()”,1200);

}

function f3()

{

document.bgColor=”green”;

window.setTimeout(“f4()”,1200);

}

function f4()

{

document.bgColor=”purple”;

window.setTimeout(“f6()”,1200);

}

function f5()

{

document.bgColor=”cyan”;

window.setTimeout(“f6()”,1200);

}

function f6()

{

document.bgColor=”brown”;

window.setTimeout(“f7()”,1200);

}

function f7()

{

document.bgColor=”orange”;

window.setTimeout(“f1()”,1200);

f1();

}

</script>

</body>

</html>

STEP 2 – EVENT1.HTML

<html>

<head>

<title> Event driven </title>

</head>

<body onLoad=window.setTimeout(“f1()”,1200);>

<H1> This changesbackground color autometically </H1>

<script language=”javaScript”>

function f1()

{

document.bgColor=”orange”;

window.setTimeout(“f2()”,1200);

}

function f2()

{

document.bgColor=”white”;

window.setTimeout(“f3()”,1200);

}

function f3()

{

document.bgColor=”green”;

window.setTimeout(“f4()”,1200);

}

function f4()

{

document.bgColor=”purple”;

window.setTimeout(“f6()”,1200);

}

function f5()

{

document.bgColor=”cyan”;

window.setTimeout(“f6()”,1200);

}

function f6()

{

document.bgColor=”brown”;

window.setTimeout(“f7()”,1200);

}

function f7()

{

document.bgColor=”orange”;

window.setTimeout(“f1()”,1200);

f1();

}

</script>

</body>

</html>

STEP 1 - OUTPUT

STEP 2 - OUTPUT

This Changes background color automatically

2)TELEPHONE NUMBER AND SALARY AMOUNT VALIDATION

 <html>

<head>

<title> email </title>

<script language="JavaScript">

function validate()

{

if(telno()&&salamt())

{

alert("Acceptable");

}

else

{

alert("Not Acceptable");

}

function telno()

{ s=document.check.tel.value;

if(s==""||s.length<6||s.length>10 || isNaN(s))

{

alert("Invalid telephone number");

document.check.tel.value=" ";

document.check.tel.focus();

return false;

}

else

{ return true; }

}

function salamt()

{ s=document.check.sal.value;

if(s=="" || s.length<4 || s.length>10 || isNaN(s))

{

alert("Invalid salary.");

document.check.sal.value=" ";

document.check.sal.focus();

return false;

}

var dot=s.indexOf(".")

if((dot!=-1)&&(s.charAt(dot+3)!=""))

{

alert("Enter salary upto 2 decimal places.");

document.check.sal.value=" ";

document.check.sal.focus();

return false;

}

else

{ return true; }

}

}

</script>

</head>

<body>

<form name=check>

Enter your telephone number <input type=text name=tel> <br>

Enter your salary <input type=text name=sal> <br>

<input type=button value="submit" onClick=validate();>

</form>

</body>

</html>

 

Enter your telephone number

Enter your salary

 

3)USERNAME AND PASSWORD VALIDATION USING JAVASCRIPT.

 

<html>

<head>

<title> email </title>

<script language="JavaScript">

function validate()

{

if(user()&&pword())

{

alert("Acceptable");

}

else

{

alert("Not Acceptable");

}

function user()

{ s=document.check.uname.value;

if(s==""||s.length<6||s.length>10)

{

alert("Uername should be more than 6 and less than 10 char.");

document.check.uname.value=" ";

document.check.uname.focus();

return false;

}

for(i=0;i<s.length;i++)

{

var ch=s.charAt(i);

if((ch<'a'||ch>'z') && (ch<'A'||ch>'Z') && (ch<'0'||ch>'9'))

{

alert("Uername accepts letters and digits.");

document.check.uname.value=" ";

document.check.uname.focus();

return false;

}

else

{ return true; }

}

}

function pword()

{ s=document.check.pass.value;

if(s==""||s.length<6||s.length>10)

{

alert("Password should be more than 6 and less than 10 char.");

document.check.pass.value=" ";

document.check.pass.focus();

return false;

}

for(i=0;i<s.length;i++)

{

var ch=s.charAt(i);

if((ch<'a'||ch>'z') && (ch<'A'||ch>'Z') && (ch<'0'||ch>'9'))

{

alert("Password accepts letters and digits.");

document.check.pass.value=" ";

document.check.pass.focus();

return false;

}

else

{ return true; }

}

}

}

</script>

</head>

<body>

<form name=check>

Enter username: <input type=text name=uname> <br>

Enter password : <input type=text name=pass><br>

<input type=button value="submit" onClick=validate();>

</form>

</body>

</html>

 

OUTPUT

Enter username

 

Enter password

 

4)  E-MAIL ADDRESS VALIDATION USING JAVASCRIPT.

 

<html>

<head>

<title> email </title>

<script language="JavaScript">

function validate()

{

m=document.mail.email.value;

apos=m.indexOf("@");

dotpos=m.indexOf(".");

rat=m.indexOf("@",apos+1);

if(apos<1||dotpos-apos<2||rat!=-1)

{

alert("Not a valid e-mail address");

}

else

{ alert(" valid e-mail address");

}

}

</script>

</head>

<body>

<form name=mail>

Enter your E-mail address :<input type=text name=email> <br>

<input type=button value="check email" onClick=validate();>

</form>

</body>

</html>

OUTPUT

Enter your E-mail addresss