Network+ Guide to Networks by Tamara Dean

Networking பற்றி அறிந்துகொள்ள அருமையான புத்தகம் ebook வடிவில்

Download Network+ Ebook

Advertisements

ECE 202 Unit IV Notes

In this Unit, The following points are Discussed:

  • Classification of memories
  • RAM organization – Write operation –Read operation
  • Memory cycle – Timing wave forms
  • Memory decoding – Memory expansion
  • Static RAM Cell – Bipolar RAM cell – MOSFET RAM cell – Dynamic RAM cell
  • ROM organization – PROM –EPROM – EEPROM – EAPROM

Download ECE 202 Unit 4 Notes

Download ECE 202 Programmable Logic Devices

CSE 255 Unit V Graph Notes

Dear Students,

In this Unit 5, we have discussed the following Sorting Techniques:

  • Topological Sort
  • Shortest-path Algorithms
  • Dijkstra’s Algorithm
  • Minimum Spanning Tree
  • Kruskal’s Algorithm
  • Prim’s Algorithm
  • Depth-First Search
  • Breadth-First Search
  • Applications of Depth-First Search
  • Undirected Graphs – Bi Connectivity
  • NP-Completeness Problem

Download Graph PPT

Download Graph Notes

Hope this may helpful to u..

Thank you.

Array Implementation of List ADT

Array Implementation of List ADT

Program:

#include
#include
int a[20],i,n;
void create(int);
void display();
void insert(int,int);
void delet(int);
int search(int);
void makeempty();
void main()
{ int op=1,ch,x,p,k;
do
{
printf(“enter your choice\n\n”);
printf(“1.Creation\n”);
printf(“2.Display\n”);
printf(“3.Insertion\n”);
printf(“4.Deletion by position\n”);
printf(“5. Deletion by element\n”);
printf(“6.Search\n”);
printf(“7. Find Kth\n”);
printf(“8. FindNext\n”);
printf(“9. Find Previous\n”);
printf(“10. MakeEmpty\n”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“enter the number of elements\n”);
scanf(“%d”,&n);
create(n);
break;
case 2:
display();
break;
case 3:
printf(“enter the element to be inserted\n”);
scanf(“%d”,&x);
printf(“Enter the position”);
scanf(“%d”,&p);
insert(p,x);
break;
case 4:
printf(“Enter the position to be deleted “);
scanf(“%d”,&p);
delet(p);
break;
case 5:
printf(“Enter the element to be deleted\n”);
scanf(“%d”,&x);
p=search(x);
if(p==0)
printf(“The element is not found \n”);
else
delet(p);
break;
case 6:
printf(“enter element to search”);
scanf(“%d”,&x);
p=search(x);
if(p==0)
printf(“The element is not found \n”);
else
printf(“the variable is found in position: %d\n”,p);
break;
case 7:
printf(“Enter the value of k “);
scanf(“%d”,&k);
if(k>n)
printf(“no such position\n”);
else
printf(“%d “,a[k-1]);break;
case 8:
printf(“Enter the element “);
scanf(“%d”,&x);
p=search(x);
if(p==0)
printf(“The element is not found\n”);
else
{
if(p==n)
printf(“It is the last element. There is no next value \n”);
else
printf(“%d “,a[p]);
}break;
case 9:
printf(“Enter the element “);
scanf(“%d”,&x);
p=search(x);
if(p==0)
printf(“The element is not found\n”);
else
{
if(p==1)
printf(“Its the first element.Thereis no previousvalue\n”);
else
printf(“%d “,a[p-2]);
}break;
case 10:
makeempty();
break;
}
printf(“Enter 0 to quit and 1 to continue “);
scanf(“%d”,&op);
}while(op);
}

void create(int n)
{ for(i=0;i<n;i++)
{
printf(“enter the element”);
scanf(“%d”,&a[i]);
}
}

void display()
{ if(n==0)
printf(“array is empty\n”);
for(i=0;in+1)
printf(“Cannot insert element “);
else
{
n++;
for(i=n-1;i>=p;i–-)
{
a[i]=a[i-1];
}
a[p-1]=x;
}
}

void delet(int p)
{
if(p>n)
printf(“no element in that position\n”);
else
{
for(i=p-1;i<n;i++)
a[i]=a[i+1];
n–-;
printf(“The element is deleted\n”);
}
}

int search(int x)
{
int pos=0;
for(i=0;i<n;i++)
{
if(a[i]==x)

pos=i+1;

}
return pos;
}

void makeempty()
{
printf(“Are you sure u want to make empty?; \n press 1 for yes & 0 for no\n");
scanf(“%d”,&n);
if(n==1)
{
for(i=0;i<n;i++)
a[i]=0;
}
printf(“Now the array is empty \n”);
}

Sorting – Heap Sort

Heap Sorting

Method and Algorithm

Heap sorting process:

First of all organizing the whole data to be sorted as a binary tree i.e. heap. And after that implement heap sorting.

Step 1: (How to data organizing as binary tree?)

Remember only 2 rule:

Rule:1.

The parent node must be greater then child node.
If parent node is not greater then to child node not replace it with parent node. And if binary tree is large then, if relaceing child node(now its parent node) is greater then to great-parent node then its also is replace the great-parent node.

Rule:2.

New element always insert in left side and after right side of parent node.
If left side of parent element has already element then new element would be insert in right side. And if right side of parent node has already element then new element will be insert in left side.

Step 2: (How to perform heap sorting:)

Remove the topmost element(largest element) and replace it with the rightmost element.
Step 3:
Repeat steps 1 and 2 untill all elements is not sorted.

Heap Sorting method/process by example:

max heap : 80 , 32 , 31 , 110 , 50 , 40 , 120

<img src=”https://mrajacse.files.wordpress.com/2012/09/heap-sort-1.jpg”&gt;

<img alt=”” src=”https://mrajacse.files.wordpress.com/2012/09/heap-sort-1.jpg&#8221; />

<img src=”https://mrajacse.files.wordpress.com/2012/09/heap-sort-1.jpg&#8221; alt=”Smiley face” height=”42″ width=”42″>

<img alt=src=””>

Step1:
80

Step2:  
80
/      \
32      31
Step3:  
80                                         80                                    110
/     \                                     /     \                                 /       \
   32         31       ==>        110       31          ==>        80       31
   /                                            /                                        /
110                                       32                                      32
Step4:
110
/      \
80        31
/    \
32      5
Step5:
            110                                         110
/      \                                      /       \
80       31         ==>           80         40
/    \       /                               /   \        /
32   50  40                           32   50  31
Step6:
              110                                              110                                      120
/         \                                         /         \                                  /        \
80         40             ==>          80          120      ==>         80         110
/     \       /    \                             /    \         /    \                     /     \      /    \
32    50  31   120                     32     50  31     40             32    50 31    40————————————————————————————-(1)
120 [1]
/                      \
80 [2]               110 [3]
/         \              /           \
32 [4]   50 [5] 31 [6]   40 [7]// [1],[2],[3],[4],[5],[6],[7]: Index number
// Now applying step 2(perform heap sorting)
// Replace the topmost element with the rightmost element.

(2)
40                                             110
/      \             Heaping             /       \
80       110        =====>        80          40
/   \       /    \                           /    \       /    \
32    50 31    120                  32     50   31    120

(3)

//now replace 110 with rightmost element i.e. 31 because 120 had been sorted.
        31                                                           80                                                                     80
/            \           Heaping                     /           \                        Heaping                   /        \
80           40        ======>            31               40                 ======>            50         40
/    \          /    \                                     /     \            /    \                                              /    \        /   \
32   50  110   120                           32     50   110    120                                     32    31  110  120
(4)
//now replace 80 with rightmost element i.e. 31 because 110, 120 had been sorted.          31                                                 50                                                  50
/      \             Heaping              /        \           Heaping                   /     \
50       40          ======>         31          40        ======>          32      40
/    \      /   \                                /     \       /     \                             /    \     /     \
32     80  110  120                      32     80     110    120                31     80  110   120(5)
//now replace 50 with rightmost element i.e. 31 because 80, 110, 120 had been sorted.31                                                              40
/        \            Heaping                       /          \
32           40        ======>              32             31
/     \        /    \                                       /    \          /     \
  50     80    110    120                        50     80   110    120(6)
//now replace 40 with rightmost element i.e. 31 because 50, 80, 110, 120 had been sorted.31                                                       32
/     \           Heaping                        /         \
32      40        ======>                   31           40
/    \     /    \                                    /    \        /    \
50   80   110   120                       50    80  110    120(7)
//now replace 32 with rightmost element i.e. 31 because 40, 50, 80, 110, 120 had been sorted.                     31
                 /        \
              32          40
            /     \       /      \
         50     80   110    120Now all elements are sorted: 31 , 32 , 40 , 50 , 80 , 110 , 120

Program:

#include<stdio.h>
#include<conio.h>
void manage(int *, int);
void heapsort(int *, int, int);
int main()
{
int arr[20];
int i,j,size,tmp,k;
printf(“\n\t——- Heap sorting method ——-\n\n”);
printf(“Enter the number of elements to sort : “);
scanf(“%d”,&size);
for(i=1; i<=size; i++)
{
printf(“Enter %d element : “,i);
scanf(“%d”,&arr[i]);
manage(arr,i);
}
j=size;
for(i=1; i<=j; i++)
{
tmp=arr[1];
arr[1]=arr[size];
arr[size]=tmp;
size–;
heapsort(arr,1,size);
}
printf(“\n\t——- Heap sorted elements ——-\n\n”);
size=j;
for(i=1; i<=size; i++)
printf(“%d “,arr[i]);
getch();
return 0;
}void manage(int *arr, int i)
{
int tmp;
tmp=arr[i];
while((i>1)&&(arr[i/2]<tmp))
{
arr[i]=arr[i/2];
i=i/2;
}
arr[i]=tmp;
}void heapsort(int *arr, int i, int size)
{
int tmp,j;
tmp=arr[i];
j=i*2;
while(j<=size)
{
if((j<size)&&(arr[j]<arr[j+1]))
j++;
if(arr[j]<arr[j/2])
  break;
arr[j/2]=arr[j];
j=j*2;
}
arr[j/2]=tmp;
}

 

Quick sorting

Quick sort is a divide and conquer algorithm. Its divided large list in mainly three parts:

1.     Elements less than pivot element.

2.     Pivot element.

3.     Elements greater than pivot element.

Where pivot as middle element of large list. Let’s understand through example:

List : 3  7  8  5  2  1  9  5  4

In above list assume 4 is pivot element so rewrite list as:

3   1   2   4   5    8   9   5   7

Here, we set the pivot element(4) which has in left side elements are less than and right hand side elements are greater than. Now you think, how’s arrange the less than and greater than elements? Be patient, you get answer soon.

Now let’s start understand the concept of quick sort. The steps are:

1.    Pick a pivot element.

2.    Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with     values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final     position. This is called the partition operation.

3.    Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

        The base case of the recursion are lists of size zero or one, which never need to be sorted
Example of quick sort process:

Program:

#include<stdio.h>

#include<conio.h>
void qsort(int arr[20], int fst, int last);
int main()
{
    int arr[30];
    int i,size;
    printf(“Enter total no. of the elements : “);
    scanf(“%d”,&size);
    printf(“Enter total %d elements : \n”,size);
    for(i=0; i<size; i++)
         scanf(“%d”,&arr[i]);
    qsort(arr,0,size-1);
    printf(“Quick sorted elements are as  : \n”);
    for(i=0; i<size; i++)
    printf(“%d\t”,arr[i]);
getch();
    return 0;
}
void qsort(int arr[20], int fst, int last)
{
    int i,j,pivot,tmp;
    if(fst<last)
     {
          pivot=fst;
          i=fst;
          j=last;
          while(i<j)
                    {
                         while(arr[i]<=arr[pivot] && i<last)
                          i++;
                          while(arr[j]>arr[pivot])
                          j–;
                         if(i<j)
                           {
                                 tmp=arr[i];
                                 arr[i]=arr[j];
                                arr[j]=tmp;
                           }
                    }
                  tmp=arr[pivot];
                  arr[pivot]=arr[j];
                  arr[j]=tmp;
                  qsort(arr,fst,j-1);
                  qsort(arr,j+1,last);
              }
}