The Impact Of Classroom Management On St

Data structures and Algorithms Data structure is a particular way of organizing and storing data in a computer so that it can be accessed and modified efficiently. Different data structures are Stack, Queues, Linked Lists, Arrays, Trees, and Graphs etc.

Operations performed on Data Structures: The data in the data structures are processed by certain operations. The particular data structure chosen largely depends on the frequency of the operation that needs to be performed on the data structure.  Traversing: Visiting the data elements in DS (Data Structures)  Searching: Finding the particular data element in DS  Insertion: Inserting the data into data structure  Deletion: Removing a data element  Sorting: Arranging data in an order i.e. Ascending/ descending order  Merging: Combining elements of two similar data structures to form a new data structure of the same type.

Stack A stack is a linier list in which insertion and deletion operations are performed at only one end of the list. Thus you are able to insert as well as delete the element from only one end of the stack.

Since insertion and deletion operations are performed at same end, the element which is inserted Last is first to delete. So Stack is also known as Last In First Out (LIFO). Consider a stack of plates at dinner counter. The person who comes for dinner takes off the plate which is at top of the stack. After washing the plates the waiter places the washed plates on the top of the stack. So the plate that is placed last is first take by person. Operations Performed on Stack There are two main operations that can be performed on stack. Push operation and Pop operation. PUSH Operation The process of inserting an element into stack is known as PUSH operation. In order to insert an element into stack first we have to check weather free space is available in the stack or not. If stack is full then we can not insert an element into stack. If value of TOP variable is greater then or equal to SIZE – 1 then Stack is full. This condition is known as “Overflow”. If stack is not overflow then we can insert an element into stack. First we have to increment the value of variable TOP by one and then insert an element into stack.

Algorithm for Push operation Step 1: If TOP >= SIZE – 1 then Write “Stack is Overflow” Step 2: TOP = TOP + 1 Step 3: STACK [TOP] = X POP Operation The process of deleting an element from stack is known as POP operation. In order to delete an element from stack first we have to check weather stack is empty or not. If stack is empty then we can not delete an element from stack. This condition is known as “Underflow”. If value of TOP variable is -1 then stack is empty. So we can not delete an element

from stack. If stack is not underflow then we can delete topmost element from stack. After deleting topmost element from stack, we have to decrement the value of TOP by one, so that it can point to the next topmost element in the stack.

Linked list Linked list is a collection of Nodes. Each node having two parts. First part represents value of the node and second part represents an address of the next node. If Next node is not present then it contains NULL value. Consider Following Presentation of Linked List:

Algorithm for pop operation Step 1: If TOP = -1 then Write “Stack is Underflow” Step 2: Return STACK [TOP] Step 3: TOP = TOP - 1 Step 2: If FIRST = NULL then NEW_NODE -> INFO = X NEW_NODE -> LINK = NULL FIRST = NEW_NODE Else NEW_NODE -> INFO = X NEW_NODE -> LINK = FIRST FIRST = NEW_NODE Step 3: Exit

Insert New Node at end of Linked List In above presentation FIRST is a pointer which always contains an address of first node in the linked list. If linked list is empty then value of FIRST pointer is NULL. In Linked List nodes are logically adjacent but physically not adjacent to each other. Because address of first node is 2000, address of second node is 2010 and address of third node is 2002. Thus in Linked List memory is not allocated sequentially to each node. There are four types of Linked list: (1) Singly Linked List (2) Doubly Linked List (3) Singly Circular Linked List (4) Doubly Circular Linked List Insert New Node at beginning of Linked List

Algorithm to Insert New Node at beginning of Linked List: Step 1: If AVAIL=NULL then Write “Availability Stack is Empty” Else NEW_NODE=AVAIL AVAIL = AVAIL->LINK

In order to insert a new node at the end of the list we have to follows the below steps: (1) First we have to check weather free node is available in the Availability Stack or not. If free node is available then we can allocate memory to new node. (2) After creating new node we have to check weather linked list is empty or not. We have two possibilities: (A) Linked List is empty (FIRST=NULL). In this case the newly created node becomes the first node of linked list. (B) Linked List is not empty (FIRST ≠ NULL). In this case we have to traverse from first node to last node in the list and insert new node at the end of linked list.

Algorithm to Insert New Node at end of Linked List Step 1: If AVAIL=NULL then Write “Availability Stack is Empty” Else NEW_NODE = AVAIL AVAIL = AVAIL -> LINK Step 2: If FIRST = NULL then

NEW_NODE -> INFO = X NEW_NODE -> LINK = NULL FIRST = NEW_NODE Else NEW_NODE -> INFO = X NEW_NODE -> LINK = NULL SAVE = FIRST Repeat while SAVE->LINK ≠ NULL SAVE = SAVE->LINK SAVE->LINK = NEW_NODE Step 3: Exit

Binary Search Algorithm: Step 1 − Start searching data from middle of the list. Step 2 − If it is a match, return the index of the item, and exit. Step 3 − If it is not a match, probe position. Step 4 − Divide the list using probing formula and find the new midle. Step 5 − If data is greater than middle, search in higher sub-list. Step 6 − If data is smaller than middle, search in lower sub-list. Step 7 − Repeat until match.

Sequential Search Algorithm: Step Step Step Step Step Step step Step Step

1: 2: 3: 4: 5: 6: 8 7: 8:

Set i to 1 if i > n then go to step 7 if A[i] = x then go to step 6 Set i to i + 1 Go to Step 2 Print Element x Found at index i and go to Print element not found Exit

Bubble Sort Algorithm 1- begin BubbleSort(list) 2- for all elements of list 3- if list[i] > list[i+1] 4- swap(list[i], list[i+1]) end if end for

return list 5- end BubbleSort

Selection Sort Algorithm: Step 1 − Set MIN to location 0 Step 2 − Search the minimum element in the list Step 3 − Swap with value at location MIN Step 4 − Increment MIN to point to next element Step 5 − Repeat until list is sorted

Quick Sort: Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays. A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value. Quick sort partitions an array and then calls itself recursively twice to sort the two resulting subarrays.

Quick Sort Algorithm: Step 1 − Choose the highest index value has pivot Step 2 − Take two variables to point left and right of the list excluding pivot Step 3 − left points to the low index Step 4 − right points to the high Step 5 − while value at left is less than pivot move right Step 6 − while value at right is greater than pivot move left Step 7 − if both step 5 and step 6 does not match swap left and right Step 8 − if left ≥ right, the point where they met is new pivot