UNIT-III(DS)

Views:
 
     
 

Presentation Description

No description available.

Comments

Presentation Transcript

slide 1:

Unit-III Topics to be covered  Stacks and Queues: Introduction to stacks  applications of stacks  implementation and comparison of stack implementations.  Introduction to queues  applications of queues and implementations  Priority Queues and applications S. Durga Devi CSECBIT

slide 2:

Stacks Definition - A stack is an ordered collection of homogeneous data elements where the insertion and deletion takes place at one end known as TOP.  The stack is also called LAST IN FIRST OUTLIFO  It means: the element which is inserted last must be deleted first  Example 1. pile of plates in cafeteria 2. stack of coins S. Durga Devi CSECBIT

slide 3:

 Stack maintains a pointer called top which keeps track of the top most element in the stack.  Any insertions or deletions should be based upon the value of top.  It works on the basis of LIFO Last in First out.  According to the definition new elements are inserted from top and the elements are deleted from same end i.e again top.  This suggests that the element inserted most recently can only be deleted.  In the stack the elements are removed in the reverse order of that in which they were added to the stack i.e last element inserted is to be deleted first.  So it is called last in first out.  Stack has structured with two operations 1. push- insertion\ adding elements on to a stack 2. Pop- deletion \ removing element from the stack S. Durga Devi CSE CBIT

slide 4:

Basic operations:  The basic operations are insertion deletion display.  In stacks special terms are given for insert and delete. i.e push for insert and pop is for delete.  Push: inserting or adding element into the stack is called push.  Pop: deleting or removing element from the stack is called pop. S. Durga Devi CSECBIT

slide 5:

Elements are inserted in the order as ABCDE It represents the stack of 5 elements. The top most element in the stack is E If we want to delete element E has to be deleted first S. Durga Devi CSECBIT

slide 6:

Pop operation- delete element from the stack S. Durga Devi CSECBIT

slide 7:

Example :- S. Durga Devi CSECBIT

slide 8:

ADT For Stack ADT for stack int stack5top void push void pop void display int size void isEmpty void isFull S. Durga Devi CSECBIT

slide 9:

Applications of stacks  Balancing symbols  Parenthesis matching.  Evaluation of postfix expressions.  Infix to prefix conversions.  Infix to postfix conversions.  Implementing function callsRecursion  Web browser history  Undo operations in text editors  Matching tags in HTML and XML  Quick sort. S. Durga Devi CSECBIT

slide 10:

Implementing stack using arrays Algorithm for inserting element into the stack: Algorithm push 1. if topSIZE-1 then write ‘stack overflow’ else 2. read item or data 3. top←top+1 4. stacktop← item 5. stop S. Durga Devi CSECBIT

slide 11:

Explanation:  The stack is of size max. This procedure inserts an element item on to the top of a stack which is represented by an array stack.  The first step of this algorithm checks for an overflow condition.  Overflow means inserting element into a stack which is full.  If the top value reaches to maximum size of the stack then elements cannot be inserted into the stack i.e. stack is full.  Otherwise top is incremented by one and element is inserted into the stack. S. Durga Devi CSECBIT

slide 12:

Algorithm to delete elements from the stack: Algorithm pop 1. if top-1 then write ‘stack underflow’ else 2. item ← stacktop 3. top ← top-1 S. Durga Devi CSECBIT

slide 13:

Explanation: This procedure deletes an element from the stack. The first step of this algorithm checks for underflow condition. If the top value is -1 then stack is empty. Empty stack is known as underflow. Takeout the element from the location where the top is pointing and then decrement top by one. S. Durga Devi CSECBIT

slide 14:

Display of stack: Printing the contents of stack after push and pop operations. Algorithm print 1. if top-1 then write ‘stack empty’ 2. Repeat for i ← top to 0 printstacki 3. stop S. Durga Devi CSECBIT

slide 15:

 Space complexity  Time complexity of push popsize isEmpty isFull will take O1.  Limitation in stack using array is that maximum size of the stack must be pre defined and it cannot be changedfixed.  When trying to add elements in the stack when the stack is full will rise the exception. S. Durga Devi CSECBIT

slide 16:

 Consider size of the stack is 4  Insert following elements ABCD Representing Stack with Dynamic array S. Durga Devi CSECBIT A A B A B C A B C D A B C D E Stack is full when E is inserted create a new stack with double size and copy all the old stack elements to new stack and named it as old stack

slide 17:

 Disadvantage of using an array to implement a stack or queue is the wastage of space.  Implementing stacks as linked lists provides a feasibility on the number of nodes by dynamically growing stacks as a linked list is a dynamic data structure.  The stack can grow or shrink as the program demands it to.  A variable top always points to top element of the stack.  top NULL specifies stack is empty. Representing Stack with Linked List S. Durga Devi CSECBIT

slide 18:

 In this representation first node in the list is last inserted element hence top must points to the first element on the stack  Last node in the list is the first inserted element in the stack.  Thus push operation always adds the new element at front of the list  And pop operation removes the element at front of the list.  Size of the stack not required.  Test for overflow is not applicable in this case. S. Durga Devi CSECBIT

slide 19:

10 NULL 1500 1800 1200 1400 20 1400 30 1200 40 1800 50 1500 1100 top Example: The following list consists of five cells each of which holds a data object and a link to another cell. A variable top holds the address of the first cell in the list. S. Durga Devi CSECBIT

slide 20:

/ write a c program to implement stack using linked list / includestdio.h includemalloc.h includestdlib.h int push int pop int display int choiceiitem struct node int data struct node link topnewptr main topNULL printf"\nSelect Menu\n" while1 printf"\n1.Push \n2.Pop \n3.Display \n4.Exit\n5.Count" printf"\n\nEnter ur choice: " scanf"d"choice switchchoice case 1: push break case 2: pop break case 3: display break case 4: exit0 case 5: count break default: printf"\nWrong choice" / end of switch / / end of while / / end of main / S. Durga Devi CSECBIT

slide 21:

int push newmallocsizeofstruct node printf"\nEnter the item: " scanf"d"item new-dataitem iftopNULL new-linkNULL else new-linktop topnew return / end of insertion / int pop iftop NULL printf"\n\nStack is empty" return //if else printf"\n\nThe deleted element is: d"top-data toptop-link return / end of pop / S. Durga Devi CSECBIT

slide 22:

int display ptrtop iftop NULL printf"\nThe list is empty" return printf"\nThe elements in the stact are: " whileptrNULL printf"\n d"ptr-data ptrptr-link / end of while / return / end of display / int count int count1 ptrtop iftop NULL printf"\nThe list is empty" return whileptr-linkNULL ++count ptrptr-link printf"\n\nThe number of elements in the stack are: d"count return / end of count / S. Durga Devi CSECBIT

slide 23:

Applications of stacks Balancing symbols ”” Evaluation of postfix expressions. Infix to postfix conversions. Infix to prefix conversions. Implementing function callsRecursion Web browser history Undo operations in text editors Matching tags in HTML and XML Quick sort. S. Durga Devi CSECBIT

slide 24:

1.Parenthesis matching The objective of this function is to check the matching of parenthesis in an expression i.e  In an expression the no of left parenthesis must be equal to no: of right parenthesis. Ex: A+BC This is a valid expression because in this no of left parenthesis 2 no: of right parenthesis 2. S. Durga Devi CSECBIT

slide 25:

Conversion of expressions Arithmetic expressions can be represented in three ways:  Infix notation  Prefix notation  Postfix notation 1. Infix notation- In which operator should be placed in between the two operands. Example- A+B C-D EF G/H. 2. Prefix notation polish notation- • Operator preceded by the operand is called prefix notation Examples +AB -CD EF \GH. 3. Postfix notationreverse polish notation or suffix notation- • Operator should be placed after operands. AB+ CD- EF GH\ S. Durga Devi CSECBIT

slide 26:

Notations – Conversions Consider the infix expression: 2 + 3 5 – 7 / 9 Let us insert implicit parentheses 2 + 3 5 – 7 / 9 Transfer the operators to the beginning of parentheses + 2 / 3 – 5 7 9 Remove the parentheses: + 2 / 3 – 5 7 9 This is the equivalent prefix expression. Transfer the operators to the end of parentheses 2 3 5 7 – 9 / + Remove the parentheses: 2 3 5 7 – 9 / + This is the equivalent postfix expression. S. Durga Devi CSECBIT

slide 27:

Examples Infix Expression Prefix Expression Postfix Expression 2 + 3 + 2 3 2 3 + 2 + 3 5 + 2 3 5 2 3 5 + 2 + 3 5 + 2 3 5 2 3 + 5 2 3 – 5 + 9 – 2 3 + 5 9 2 3 5 9 + – S. Durga Devi CSECBIT

slide 28:

Infix to post fixRPN Conversion Algorithm to convert infix expression to postfix expressionRPN: 1. Declare a stack and postfix arrayoutput : postfix expression 2. Repeat the following steps until the end of the infix expression is reached. 1. Get input token constant variable arithmetic operator left parenthesis right parenthesis in the infix expression. 2. If the token is 2.1 A left parenthesis: Push it onto the stack. 2.2 A right parenthesis: 2.2.1 Pop the stack elements and add to postfix array until a left parenthesis is on the top of the stack. 2.2.2 Pop the left parenthesis also but do not add to postfix array 2.3 An operator: 2.3.1 While the stack is nonempty and token has lower or equal priority than stack top element pop and add to postfix array. 2.3.2 Push token onto the stack. 2.4 An operand: add to postfix array 3. When the end of the infix expression is reached pop the stack elements and add to postfix array until the stack is empty. Note: Left parenthesis in the stack has lowest priority S. Durga Devi CSECBIT

slide 29:

Note • the lower precedence operator never placed on top of the higher precedence. • A-BD/E S. Durga Devi CSECBIT

slide 30:

Operator Precedence S. Durga Devi CSECBIT

slide 31:

Infix expression- A+BC-DE/F Infix Stack Post fix Empty A A + + A B + AB Empty AB+ AB+ C AB+C - - AB+C - AB+C D - AB+CD - AB+CD E - AB+CDE - AB+CDE / -/ AB+CDE F -/ AB+CDEF Empty AB+CDEF/- S. Durga Devi CSE

slide 32:

Postfix reverse polish notation expression evaluation • Algorithm 1.Scan expression from left to right and repeat steps 2 and 3 for each element of expression. 2. If an operand is encountered push it on to stack. 3.If an operator op1 is encountered then 3.1 remove the top two elements of stack where A is the top and B is the next top element. 3.2 evaluate B op1 A 3.3 push the result back on to the stack. 4. set the top value on stack. 5. stop S. Durga Devi CSECBIT

slide 33:

Evaluate the expression • Postfix:- 562+124/- Symbol scanned stack content 5 5 6 5 6 2 5 6 2 + 5 8 40 12 40 12 4 40 12 4 / 40 3 - 40-3 37 S. Durga Devi CSECBIT

slide 34:

Convert infix to postfix expression 1. A-BD/E 2. A+BD/E-F+G 3. AB+D/E-FG+H/K 4. A+BDE-F 5. A-B/D+EF 6. A+B/DE-FG 7. 12/7-3+21+5 8. 5+32-8/43+6 9. 6+23+9/3-45 10. 6+232-45 Evaluate the postfix expression 1. 53+2697-/- 2. 35+64-41-2+ 3. 31+2741-2+5.- S. Durga Devi CSECBIT

slide 35:

includestdio.h includectype.h includestring.h int prioritychar c int pushchar c int pop static char str30 int top-1 void main char in30post30ch int ijl printf"enter the string" getsin lstrlenin Write a C program to convert infix to postfix evaluation S. Durga Devi CSECBIT

slide 36:

fori0j0ili++ ifisalphaini||isdigitini postj++ini else ifini pushini else ifini whilechpop postj++ch else whilepriorityiniprioritystrtop postj++pop pushini whiletop-1 postj++pop postj\0 printf"\n equivalent infix to postfix is:s"post int priority char c switchc case+: case-: return 1 case: case/: return 2 case:return 3 case :return 4 return 0 int pushchar c str++topc pop returnstrtop-- S. Durga Devi CSECBIT

slide 37:

 A queue is a linear data structure in which insertion take place from one end called rear end and deletions take place from other end called front end i.e insertion and deletion take place from different ends.  The principle used to in queue is FIFO.First In First Out  FIFO- the element which is inserted First must be deleted First.  In a queue there are two variables one is the rear and other one is front.  the element must be always added at rear end and removed from the front. Basic operations on queue: The operations that can be performed on queue are  Insertion\ Enqueue  Deletion\ Dequeue  Display Queues Front rear S. Durga Devi CSECBIT

slide 38:

Bus Stop Queue Bus Stop front rear rear rear rear rear S. Durga Devi CSECBIT

slide 39:

Bus Stop Queue Bus Stop front rear rear rear S. Durga Devi CSECBIT

slide 40:

Bus Stop Queue Bus Stop front rear rear S. Durga Devi CSECBIT

slide 41:

Bus Stop Queue Bus Stop front rear rear S. Durga Devi CSECBIT

slide 42:

Front Rear Front Rear Front Rear •A queue is like a line of people waiting for • a bank teller. The queue has a front and a rear. New people must enter the queue at the rear. When an item is taken from the queue it always comes from the front. S. Durga Devi CSECBIT

slide 43:

Queue ADT • basic queue operations: – add enqueue: Add an element to the back. – remove dequeue: Remove the front element. – peek: Examine the element at the front. – isEmpty: check whether queue is empty or not – isFull : whether queue is full or not S. Durga Devi CSECBIT

slide 44:

• Different types of queues 1. Linear queue or queue 2. Circular queue 3. Doubly ended queue dequeue 4. Priority queue S. Durga Devi CSECBIT

slide 45:

Working of a linear queue using an array i Initially frontrear -1. It indicates queue is empty. 0 1 2 3 4 frontrear-1 0 1 2 3 4 ii Add 10 10 front rear 0 2 3 4 iii Add 20 front rear 1 10 20 0 2 3 4 iv Add 30 front rear 1 10 20 30 0 2 3 4 v Add 40 front rear 1 10 20 30 40 S. Durga Devi CSECBIT

slide 46:

0 2 3 4 vi Add 50 front rear 1 10 20 30 40 50 0 2 3 4 vii Add 60 overflow front rear 1 10 20 30 40 50 0 2 3 4 viii delete 10 is removed front rear 1 20 30 40 50 0 front rear 1 30 40 50 ix delete 20 is removed 2 3 4 S. Durga Devi CSECBIT

slide 47:

0 front rear 1 40 50 x delete 30 is removed 2 3 4 0 front rear 1 50 xi delete 40 is removed 2 3 4 0 frontrear-1 1 ix delete underflow 2 3 4 0 frontrear-1 1 xii delete 50 is removed 2 3 4 S. Durga Devi CSECBIT

slide 48:

Implementation of queue using array Algorithm insert 1. If rear ≥ size-1 then write ‘overflow’ 2. Read item 3. rear← rear + 1 4. queuerear← item 5. Iffront-1 6. front++ 7. stop Explanation: This procedure adds an element item to the queue. First it checks for an overflow condition. If the rear value reaches or exceeds size of the queue then elements cannot be inserted into the queue. ie. Overflow. Whenever element is inserted into the queue rear is increment by one and place the element in the location where rear is pointing. S. Durga Devi CSECBIT

slide 49:

Algorithm to delete element from the queue Algorithm delete 1. If front -1or front rear then write ‘queue underflow’ item ← queue front 2. front ← front + 1 Explanation: This procedure deletes an element from the queue. The first step of this algorithm checks for underflow condition. If the front value is -1or greater than rear then queue is empty. Take out the element from the location where the front is pointing and store it in the variable then increment front by one. S. Durga Devi CSECBIT

slide 50:

Algorithm to display elements in a queue 1. iffront-1||frontrear 1.1 print statck is Underflow 2. Else 2.1 repeat for i-front to rear 2.2. print queuei Drawback in queue In a queue when the rear pointer reaches to the end of the queue insertion would be denied even if room is available at the front one way to remove this is using the circular queue S. Durga Devi CSECBIT

slide 51:

Program: implementation of queue using array include stdio.h define size 4 void insertion void deletion void display int front-1rear-1itemchoicequeuesize void main clrscr while1 printf"\n MENU \n 1. INSERTION\n 2. DELETION\n 3.TRAVERSE\n 4. EXIT\n" printf"enter your choice:" scanf"d"choice switchchoice case 1:insertion break case 2:deletion break case 3:display break case 4:exit default:printf" wrong choice \n" S. Durga Devi CSECBIT

slide 52:

void insertion ifrearsize-1 printf" queue is full \n" else printf"enter item into queue:" scanf"d"item rear++ queuerearitem iffront-1 front++ void deletion iffront-1||frontrear printf" queue is empty \n" else itemqueuefront front++ printf"the deleted item from queue is d\n"item void display int i iffront-1||frontrear printf" queue is empty \n" else printf"\n elements in queue:- " forifrontireari++ printf"d "queuei S. Durga Devi CSECBIT

slide 53:

EMPTY QUEUE Circular queues Q0 Q1 Q2 Q3 QN Delete element 5 S. Durga Devi CSECBIT

slide 54:

rear S. Durga Devi CSECBIT

slide 55:

• How to test whether circular queue is empty or full • The circular q is controlled by the MOD operation. • Circular queue is empty when front -1 rear-1 Circular queue is full front rear+1 SIZE S. Durga Devi CSECBIT

slide 56:

Implementation of circular queue using array • Algorithm for insertion 1.iffront 0 rear SIZE-1 || front rear+1size 2.printf"Queue Overflow \n" return 3.if front -1 /If queue is empty / 3.1 front 0 3.2 rear 0 4.else 5.ifrear SIZE-1/rear is at last position of queue / 6.rear 0 7. else 8.rear rear+1 9.Read item 10.cqrear item 11.end S. Durga Devi CSECBIT

slide 57:

• Algorithm for deletion • 1.if front -1 2.printf"Queue Underflow\n" return 3.iffront rear / queue has only one element / 3.1front -1 3.2rear-1 4.else 5.iffront SIZE-1 • front 0 6.else 7.front front+1 8.Stop S. Durga Devi CSECBIT

slide 58:

int insert int item iffront 0 rear SIZE-1 || front rear+1 printf"Queue Overflow \n" return if front -1 /If queue is empty / front 0 rear 0 else ifrear SIZE-1/rear is at last position of queue / rear 0 else rear rear+1 printf"Input the element for insertion in queue : " scanf"d" item cqrear item printf"the element d at d position and frontdreard\n"cqrearrearfrontrear return /End of insert/ S. Durga Devi CSECBIT

slide 59:

int del if front -1 printf"Queue Underflow\n" return printf"Element deleted from queue is : d\n"cqfront iffront rear / queue has only one element / front -1 rear-1 else iffront SIZE-1 front 0 else front front+1 printf"frontdreard\n"frontrear return /End of del / Deletion S. Durga Devi CSECBIT

slide 60:

display int display int front_pos frontrear_pos rear iffront -1 printf"Queue is empty\n" Return printf"Queue elements :\n" if front_pos rear_pos whilefront_pos rear_pos printf"d "cqfront_pos front_pos++ else whilefront_pos SIZE-1 printf"d "cqfront_pos front_pos++ front_pos 0 whilefront_pos rear_pos printf"d "cqfront_pos front_pos++/End of else / printf"\n" return /End of display / S. Durga Devi CSECBIT

slide 61:

Applications of queues There are several applications of queues in computer science. 1. Implement various aspects of operating systems. 2. CPU scheduling in Multiprogramming environment- single CPU has to serve more than one program simultaneously. 3. Round Robin CPU scheduling algorithm. 4. In operating System maintains a queue of processes that are ready to process or that are waiting for particular event to occur. 5. Computer system maintains a buffer and is implemented as a queue. 6. Printer 7. Call waiting when you are attending other call 8. a file server in a computer network handles file access request from many clients throughout the network. Servers have a limited capacity to service request from clients. when that capacity is exceeded client requests wait in queues 9. This type of data structure is used in time sharing systems where many user jobs will be waiting in the system queue for processing. These jobs may request the services of CPU main memory or external devices such as printer. 10. Radix sort implemented using queue. S. Durga Devi CSECBIT

slide 62:

Queues in computer science • Operating systems: – queue of print jobs to send to the printer – queue of programs / processes to be run – queue of network data packets to send • Programming: – modeling a line of customers or clients – storing a queue of computations to be performed in order • Real world examples: – people on an escalator or waiting in a line – cars at a gas station or on an assembly line S. Durga Devi CSECBIT

slide 63:

Radix sort • This algorithm sorts the elements from least significant digit to most significant digit • As you know the numbers are formed with digits 0 to 9 so we need 10 buckets labelled 0 to 9 to sort the unsorted numbers. • First find the largest number in the given unsorted elements and count its digits. • If largest number has n digits the algorithm could be completed in n number of passes to sort the numbers in specified order. • Number of passes bucket sort stages will depend on the number of digits in the maximum value

slide 64:

Example : 100 5435510243102875 0 1 2 3 4 5 6 7 100 54 355 102 43 10 287 5 Take buckets numbered from 0 to 9 Take first number 100 has 0 in the 1 st place so put that number in 0 th bucket 54 has 4 in the 1 st place so put that number in 4 th bucket 0 1 2 3 4 5 6 7 8 9

slide 65:

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 100 54 355 102 43 10 287 5 100 PASS-1

slide 66:

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 100 54 355 102 43 10 287 5 100 54

slide 67:

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 100 54 355 102 43 10 287 5 100 54 355

slide 68:

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 100 54 355 102 43 10 287 5 100 54 355 102

slide 69:

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 100 54 355 102 43 10 287 5 100 54 355 102 43

slide 70:

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 100 54 355 102 43 10 287 5 100 54 355 102 43 10

slide 71:

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 100 54 355 102 43 10 287 5 100 54 355 102 43 10 287

slide 72:

0 1 2 3 4 5 6 7 100 54 355 102 43 10 287 5 0 1 2 3 4 5 6 7 8 9 100 54 355 102 43 10 287 5 Take out the elements from the buckets starts from 0 th bucket to 9 th bucket Place it in an array

slide 73:

0 1 2 3 4 5 6 7 100 54 355 102 43 10 287 5 0 1 2 3 4 5 6 7 8 9 100 54 355 102 43 10 287 5 Take out the elements from the buckets starts from 0 th bucket to 9 th bucket Place it in an array 0 1 2 3 4 5 6 7 100

slide 74:

0 1 2 3 4 5 6 7 100 54 355 102 43 10 287 5 0 1 2 3 4 5 6 7 8 9 54 355 102 43 10 287 5 Take out the elements from the buckets starts from 0 th bucket to 9 th bucket Place it in an array 0 1 2 3 4 5 6 7 100

slide 75:

0 1 2 3 4 5 6 7 100 54 355 102 43 10 287 5 0 1 2 3 4 5 6 7 8 9 54 355 102 43 287 5 Take out the elements from the buckets starts from 0 th bucket to 9 th bucket Place it in an array 0 1 2 3 4 5 6 7 100 10

slide 76:

0 1 2 3 4 5 6 7 100 54 355 102 43 10 287 5 0 1 2 3 4 5 6 7 8 9 54 355 102 43 287 5 Take out the elements from the buckets starts from 0 th bucket to 9 th bucket Place it in an array 0 1 2 3 4 5 6 7 100 10 102

slide 77:

0 1 2 3 4 5 6 7 100 54 355 102 43 10 287 5 0 1 2 3 4 5 6 7 8 9 54 355 43 287 5 Take out the elements from the buckets starts from 0 th bucket to 9 th bucket Place it in an array 0 1 2 3 4 5 6 7 100 10 102

slide 78:

0 1 2 3 4 5 6 7 100 54 355 102 43 10 287 5 0 1 2 3 4 5 6 7 8 9 54 355 43 287 5 Take out the elements from the buckets starts from 0 th bucket to 9 th bucket Place it in an array 0 1 2 3 4 5 6 7 100 10 102 43

slide 79:

0 1 2 3 4 5 6 7 100 54 355 102 43 10 287 5 0 1 2 3 4 5 6 7 8 9 54 355 287 5 Take out the elements from the buckets starts from 0 th bucket to 9 th bucket Place it in an array 0 1 2 3 4 5 6 7 100 10 102 43

slide 80:

0 1 2 3 4 5 6 7 100 54 355 102 43 10 287 5 0 1 2 3 4 5 6 7 8 9 54 355 287 5 Take out the elements from the buckets starts from 0 th bucket to 9 th bucket Place it in an array 0 1 2 3 4 5 6 7 100 10 102 43 54

slide 81:

0 1 2 3 4 5 6 7 100 54 355 102 43 10 287 5 0 1 2 3 4 5 6 7 8 9 355 287 5 Take out the elements from the buckets starts from 0 th bucket to 9 th bucket Place it in an array 0 1 2 3 4 5 6 7 100 10 102 43 54

slide 82:

0 1 2 3 4 5 6 7 100 54 355 102 43 10 287 5 0 1 2 3 4 5 6 7 8 9 355 287 5 Take out the elements from the buckets starts from 0 th bucket to 9 th bucket Place it in an array 0 1 2 3 4 5 6 7 100 10 102 43 54 355

slide 83:

0 1 2 3 4 5 6 7 100 54 355 102 43 10 287 5 0 1 2 3 4 5 6 7 8 9 287 5 Take out the elements from the buckets starts from 0 th bucket to 9 th bucket Place it in an array 0 1 2 3 4 5 6 7 100 10 102 43 54 355

slide 84:

0 1 2 3 4 5 6 7 100 54 355 102 43 10 287 5 0 1 2 3 4 5 6 7 8 9 287 5 Take out the elements from the buckets starts from 0 th bucket to 9 th bucket Place it in an array 0 1 2 3 4 5 6 7 100 10 102 43 54 355 5

slide 85:

0 1 2 3 4 5 6 7 100 54 355 102 43 10 287 5 0 1 2 3 4 5 6 7 8 9 287 Take out the elements from the buckets starts from 0 th bucket to 9 th bucket Place it in an array 0 1 2 3 4 5 6 7 100 10 102 43 54 355 5

slide 86:

0 1 2 3 4 5 6 7 100 54 355 102 43 10 287 5 0 1 2 3 4 5 6 7 8 9 287 Take out the elements from the buckets starts from 0 th bucket to 9 th bucket Place it in an array 0 1 2 3 4 5 6 7 100 10 102 43 54 355 5 287

slide 87:

0 1 2 3 4 5 6 7 100 54 355 102 43 10 287 5 0 1 2 3 4 5 6 7 8 9 Take out the elements from the buckets starts from 0 th bucket to 9 th bucket Place it in an array 0 1 2 3 4 5 6 7 100 10 102 43 54 355 5 287 PASS-1 completed

slide 88:

0 1 2 3 4 5 6 7 100 10 102 43 54 355 5 287 PASS-2 consider ten’s place and place it into its corresponding bucket number 100 has 0 in its ten’s place so put 100 in 0 th bucket 0 1 2 3 4 5 6 7 8 9 100

slide 89:

0 1 2 3 4 5 6 7 100 10 102 43 54 355 5 287 0 1 2 3 4 5 6 7 8 9 100 10

slide 90:

0 1 2 3 4 5 6 7 100 10 102 43 54 355 5 287 0 1 2 3 4 5 6 7 8 9 100 10 102

slide 91:

0 1 2 3 4 5 6 7 100 10 102 43 54 355 5 287 0 1 2 3 4 5 6 7 8 9 100 10 102 43

slide 92:

0 1 2 3 4 5 6 7 100 10 102 43 54 355 5 287 0 1 2 3 4 5 6 7 8 9 100 10 102 43 54

slide 93:

0 1 2 3 4 5 6 7 100 10 102 43 54 355 5 287 0 1 2 3 4 5 6 7 8 9 100 10 102 43 54 355

slide 94:

0 1 2 3 4 5 6 7 100 10 102 43 54 355 5 287 0 1 2 3 4 5 6 7 8 9 100 10 102 43 54 355 05

slide 95:

0 1 2 3 4 5 6 7 100 10 102 43 54 355 5 287 0 1 2 3 4 5 6 7 8 9 100 10 102 43 54 355 05 287

slide 96:

0 1 2 3 4 5 6 7 100 10 102 43 54 355 5 287 0 1 2 3 4 5 6 7 8 9 100 10 102 43 54 355 05 287 0 1 2 3 4 5 6 7 100 102 05 10 43 54 355 287 PASS-2 completed

slide 97:

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 100 102 05 10 43 54 355 287 PASS-3 Now consider 100 th place digit and put it in corresponding bucket 100 number has 1 in its hundred’s place so put it in bucket 1 100

slide 98:

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 100 102 05 10 43 54 355 287 100 102

slide 99:

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 100 102 05 10 43 54 355 287 100 102 005

slide 100:

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 100 102 05 10 43 54 355 287 100 102 005 010

slide 101:

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 100 102 05 10 43 54 355 287 100 102 005 010 043

slide 102:

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 100 102 05 10 43 54 355 287 100 102 005 010 043 054

slide 103:

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 100 102 05 10 43 54 355 287 100 102 005 010 043 054 355

slide 104:

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 100 102 05 10 43 54 355 287 100 102 005 010 043 054 355 287

slide 105:

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 100 102 05 10 43 54 355 287 100 102 005 010 043 054 355 287 0 1 2 3 4 5 6 7 5 10 43 54 100 102 287 355

slide 106:

Exercise use Radix sort 12 58 37 64 52 36 99 63 18 9 20 88 47

slide 107:

Circular queue using array includestdio.h includestdlib.h define SIZE 4 int insert int del int display int cqSIZE int front -1 int rear -1 main while1 printf"1.Insert\n" printf"2.Delete\n" printf"3.Display\n" printf"4.Quit\n" printf"Enter your choice : " scanf"d"choice switchchoice case 1 : insert break case 2 : del break case 3: display break case 4: exit0 default: printf"Wrong choice\n" /End of switch/ /End of while / /End of main/

slide 108:

int insert int item iffront 0 rear SIZE-1 || front rear+1 printf"Queue Overflow \n" return if front -1 /If queue is empty / front 0 rear 0 else ifrear SIZE-1/rear is at last position of queue / rear 0 else rear rear+1 printf"Input the element for insertion in queue : " scanf"d" item cqrear item printf"the element d at d position and frontdreard\n"cqrearrearfrontrear return /End of insert/

slide 109:

example 1.encqA 2.encqB 3.encqc 4. Encq D 5.Decq 6.encqE 7. Decq 8.encq F 9.Decq 10. Decq 11.Decq 12. Decq

slide 110:

Dictionaries 6 9 2 4 1 8

slide 111:

Dictionary ADT • The dictionary ADT models a searchable collection of key- element entries • The main operations of a dictionary are searching inserting and deleting items • Multiple items with the same key are allowed • Applications: – word-definition pairs – credit card authorizations – DNS mapping of host names e.g. datastructures.net to internet IP addresses e.g. 128.148.34.101 • Dictionary ADT methods: – findk: if the dictionary has an entry with key k returns it else returns null – findAllk: returns an iterator of all entries with key k – insertk o: inserts and returns the entry k o – removee: remove the entry e from the dictionary – entries: returns an iterator of the entries in the dictionary – size isEmpty

slide 112:

Example Operation Output Dictionary insert5A 5A 5A insert7B 7B 5A7B insert2C 2C 5A7B2C insert8D 8D 5A7B2C8D insert2E 2E 5A7B2C8D2E find7 7B 5A7B2C8D2E find4 null 5A7B2C8D2E find2 2C 5A7B2C8D2E findAll2 2C2E 5A7B2C8D2E size 5 5A7B2C8D2E removefind5 5A 7B2C8D2E find5 null 7B2C8D2E

slide 113:

The findAllk Algorithm Algorithm findAllk: Input: A key k Output: An iterator of entries with key equal to k Create an initially-empty list L B D.entries while B.hasNext do e B.next if e.key k then L.insertLaste return L.elements

slide 114:

The insert and remove Methods Algorithm insertkv: Input: A key k and value v Output: The entry kv added to D Create a new entry e kv S.insertLaste S is unordered return e Algorithm removee: Input: An entry e Output: The removed entry e or null if e was not in D We don’t assume here that e stores its location in S B S.positions while B.hasNext do p B.next if p.element e then S.removep return e return null there is no entry e in D

slide 115:

A List-Based Dictionary • A log file or audit trail is a dictionary implemented by means of an unsorted sequence – We store the items of the dictionary in a sequence based on a doubly- linked list or array in arbitrary order • Performance: – insert takes O1 time since we can insert the new item at the beginning or at the end of the sequence – find and remove take On time since in the worst case the item is not found we traverse the entire sequence to look for an item with the given key • The log file is effective only for dictionaries of small size or for dictionaries on which insertions are the most common operations while searches and removals are rarely performed e.g. historical record of logins to a workstation

slide 116:

Hash Table Implementation • We can also create a hash-table dictionary implementation. • If we use separate chaining to handle collisions then each operation can be delegated to a list-based dictionary stored at each hash table cell.

slide 117:

Linear\sequential Search • linear\sequential search of a list/array begins at the beginning of the list/array and continues until the item is found or the entire list/array has been searched

slide 118:

Example: Successful Linear Search

slide 119:

Example: Failed Linear Search

slide 120:

Linear Search Implementation using non recursive method include stdio.h define SIZE 8 int linear_searchint a int target int size void read_arrayint a int size int mainvoid int xSIZE target int index read_arrayx SIZE printf"Enter Element to search for: " scanf"d" target index linear_searchx target SIZE if index 0 printf"Target was found at index d\n" index else printf"Sorry target item was not found" return 0 void read_array int a int size int i printf"Enter d integer numbers separated by blanks\n " size for i 0 i size ++i scanf"d" ai / Searches for an target in an array using Linear search Returns index of target or -1 if not found / int linear_searchint a int target int size int iloc0 fori0iSIZEi++ iftargetai return ++loc else loc++ return 0

slide 121:

/ C program that use recursive function to perform the Linear Search for a Key value in a given list of integers/ includestdio.h define SIZE 5 int linearSearchint array int index int length int value void main int listSIZEelementitargetindex0 printf"\n\nEnter d integer elements: "SIZE fori 0 i SIZE i++ scanf"d"listi printf"\nEnter target element to be searched: " scanf"d"target element linearSearch listindexSIZEtarget if element -1 printf"\nElement is found at d location "element+1 else printf"Element is not found..."

slide 122:

int linearSearchint array int indexint length int value ifindexlength-1 return -1 else if arrayindexvalue return index else return linearSearch arrayindex+1length value

slide 123:

Search Algorithms -All the array elements must be visited if search fails.

slide 124:

Efficiency of Linear Search • The efficiency of an algorithm is measured using the big O notation O stands for order of • Big O Notation – Indicates the worst-case run time maximum time taken for execution for an algorithm – In other words how hard an algorithm has to work to solve a problem For Linear Search algorithm :On

slide 125:

Binary Search: The search starts at middle of a sorted array if middle is equal to target element search is successful otherwise it determines which half to be continue to search on that basis.  The algorithm starts searching with the mid element. midfirst + last/2  If the item is equal to mid then search is successful.  If the item is less than the mid element it starts over searching the first half of the list.  If the item is greater than the mid element the search starts over the second half of the list.  It then continues halving the list until the item is found.  Each iteration eliminates half of the remaining elements.  It is faster than the linear search.  It works only on SORTED array.  Thus there is a performance penalty for sorting the array.  The Time complexity of Binary Search is Olog N.

slide 127:

/ C program that use recursive function to perform the Binary Search for a Key value in a given list of integers/ include stdio.h define SIZE 8 int binary_search int list int low int high int target void main int listSIZE target indexi printf"Enter d elements in ascending or descending order: "SIZE fori0iSIZEi++ scanf"d"listi printf"Enter an element that is to be searched: " scanf"d" target index binary_searchlist 0 SIZE-1 target if index -1 printf"\nTarget was found at index: d " index+1 else printf"Sorry target item was not found"

slide 128:

int binary_search int list int low int high int target int middle if low high return -1 middle low + high/2 if listmiddle target return middle else if listmiddle target return binary_searchlistmiddle+1hightarget else return binary_searchlistlowmiddle-1target

slide 129:

/ C program that use non recursive function to perform the Binary Search for a Key value in a given list of integers/ include stdio.h define SIZE 8 int binary_search int list int low int high int target void main int listSIZE target indexi printf“\nenter the array elements” fori0iSIZEi++ scanf"d"listi printf“\n enter the target element" scanf"d" target index binary_searchlist 0 SIZE-1 target if index -1 printf"\nelement atlocation d " index+1 else printf"Sorry target item was not found" getch

slide 130:

int binary_searchint aint low int high int target int middle whilelowhigh middlelow+high/2 iftargetamiddle highmiddle-1 else iftargetamiddle lowmiddle+1 else return middle //while return -1 //binary_search

slide 131:

Static Hashing

slide 132:

Why hashing • Internet has grown to millions of users and terabytes of data every data. • It is impossible to find anything in the internet unless we develop a new data structure to store and access the data very quickly. • The amount of time required to look up an element in an array or linked list is either Ologn or On based on the list is sorted or not. • New data structure called Hashing used to store and retrieve any entry with constant time O1. • This technique is irrelevant to size of the list and order . • To increase the search efficiency the items to be stored in such a way as to make it easy to find them later .

slide 133:

Hashing - Hashing is a technique used to generate key where an element is to be inserted or to be located from. • Hash Table - hash table is a data structure to store and retrieve data very fast. - hash table consist of key and its value. - Each location in the hash table is called cell or bucket. - hash table is implemented using array. - An element is accessed very fast if we know the key or its index. Example- to store the Student record in hash table Student rollno is used as a key

slide 134:

Hash Function - to map the key value into its corresponding index in hash table hash function is used. A hash function h transforms a key into an index in a hash table T0…m-1: Where m is size of hash table. -Use hash function to compute the index in the hash table for the given key value. -Hash function returns integer value which give the index value in the hash table.

slide 135:

Types of hash functions 1. Division method 2. Mid square 3. Digit folding

slide 136:

1. Division method hkey recordM where M is size of the hash table Example: store following records in hash table 34 20 67 8 23. M is 10 use hash function to map them in hash table 0 20 1 2 3 23 4 34 5 6 7 67 8 8 9 3410 4 20100 67107 8108 23103

slide 137:

Consider the following elements to be placed in the hash table of size 10 37904522174955 0 1 2 3 4 5 6 7 8 9 49 37 45 90 22 H 1 3737107 H 1 9090100 H 1 4545105 H 1 2222102 H 1 1717107 H 1 4949109 H 1 5555105 In above example 17 and 55 are hashed to same location this condition is called collision

slide 138:

2. Mid square - Square the key value and the middle or mid part of the result is used as index. - Example to place a record 3111 then - Square of 3111 9678321 - If the hash table size is 1000 then consider the middle 3 digits 783. K 3205 7148 k 2 10272025 51093904 Hk 72 93

slide 139:

3. Folding method - Key value is divided into parts and add them yields required hash address. Key 3205 7148 Hkey 32+0537 71+4819 Note- the leading digit 1 in H7148 is ignored.

slide 140:

Collision resolution techniques • Two or more keys are mapping to same location in the hash table is called collision. Collision resolution techniques • They are two broad ways of collision resolution techniques 1. Separate chaining: an array of linked list representation 2. Open addressing: array based implementation i Linear probing linear search ii Quadratic probing nonlinear search iii Double hashing uses two hash functions

slide 141:

Separate chaining • Hash table is implemented as array of linked list. • All the records which are mapped to same hash address are lined together to form a linked list. • Example: Load the keys 23 13 21 14 7 8 and 15 in this order in a hash table of size 7 using separate chaining with the hash function: hkey key 7 h23 23 7 2 h13 13 7 6 h21 21 7 0 h14 14 7 0 collision h7 7 7 0 collision h8 8 7 1 h15 15 7 1 collision

slide 142:

Linear probing linear search • Idea is that when the collision occurs find the next available slot in the hash table i.e probing • The process wraps around to the beginning of the table • Example 89 18 49 58 9 and hash table size is 10 0 1 2 3 4 5 6 7 8 9 89 18 49 58 9 89109 18108 49109 58108 9109

slide 143:

3. Quadratic probing - It operates by taking hash value and adding successive values of an arbitrary quadratic polynomial. - Uses following formula H i key Hashvalue+i 2 m Where m may be table size or any prime number

slide 144:

Ex- 3799552211 174087 0 1 2 3 4 5 6 7 8 9 37107 37 99109 99 55105 55 22102 22 11101 11 17107 but already occupied Consider i0 then 17+0 2 107 17+1 2 108 17 40100 40 87107 occupied 87+1 2 108 occupied 87+2 2 101 occupied 87+3 2 106 87

slide 145:

4. Double hashing - Second hash function is applied when a collision is occurred. - the resultant of second hash function is to get the number of positions from the point of collision to insert. H 1 key keyvaluetablesize H 2 key M-key M Where M is prime number smaller than table size.

slide 146:

Ex- 37904522174955 0 1 2 3 4 5 6 7 8 9 H 1 3737107 37 H 1 9090100 90 H 1 4545105 45 H 1 2222102 17 H 1 1717107 H 2 177-1774 Move 4 locations from collision H 1 5555105 H 2 557-5571 Move one location from collision H 1 4949109 49 55 22

slide 147:

• https://www.codingbot.net/2013/02/radix- sort-algorithm-and-c-code.html

authorStream Live Help