Lecture Note - 3 (Chapter 3)
Lecture Note - 3 (Chapter 3) COSC 600
Popular in Advanced Data Structures and Algorithm Analysis
verified elite notetaker
Popular in ComputerScienence
verified elite notetaker
This 9 page Study Guide was uploaded by NikkitheNotetaker on Tuesday March 8, 2016. The Study Guide belongs to COSC 600 at Towson University taught by Dr. Yanggon Kim in Spring 2016. Since its upload, it has received 112 views. For similar materials see Advanced Data Structures and Algorithm Analysis in ComputerScienence at Towson University.
Reviews for Lecture Note - 3 (Chapter 3)
If Nakshatra isn't already a tutor, they should be. Haven't had any of this stuff explained to me as clearly as this was. I appreciate the help!
-Mabel Bailey IV
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 03/08/16
COSC 600: Advanced Data Structures and Algorithm Analysis Lecture Notes 3 (Chapter 3) Lists, Stacks and Queues Abstract Data Types (ADT): An ADT is a set of objects together with a set of operations. These data types are mathematical abstractions and nowhere in ADT’s definition, there is no description of how the set of operations are implemented. Abstract data types can be two types based on their access to the data. 1. Linear ADT: linear ADTs can be two types again ● Direct access linear ADT which can be either a homogenous or a heterogonous one Ex: arrays, sets ● Sequential access linear ADT Ex: list (stacks filo, queuesFIFO) 2. Non linear ADT. Note: when the relationships between the elements is logical then is called a linear relationship. The following are the few other examples of the ADTs. 1. Graphs which have vertices and edges. 2. Tree (it is a specialty graph and it does not have cycle). 3. Binary tree is a specialty case of tree 4. Binary search tree is a specialty of binary tree 5. Balanced binary search tree is a specialty of binary search tree. Lists: List is a homogenous collection of elements with linear relationship between the elements. Lists can be of two types. ● Sorted lists ● Unsorted lists Operations that can be performed on lists are as follows: ● Printlist() ● Makeempty() ● Find()/search() ● Insert() ● Delete/remove() Implementation of the operations on list: Lists can be implemented in using the following data types 1. Arrays 2. Linked lists (single or double) Implementing the lists using arrays: All the operations on the list can be performed using arrays. All the capacity of the arrays is fixed; we can create the arrays with double the capacity when needed. The maximum size estimate for the array is not required in java or any other modern programming language. 1. Arrays become a good option to implement lists where the lists are build up by insertions at the high end. 2. If insertions and deletions occur throughout the list, then array is not a good option. Operation Sorted array Unsorted array Printlist() O(n) O(n) Find() O(log n) O(n) Insert() O(n) O(1) Delete() O(n) O(n) Implementing the lists using the linked lists: Linked lists consists of series of nodes which are not necessarily adjacent in memory. Each node contains the element and a link to the next node. The last cell next reference would be null. Linked lists help in reducing the time complexity for the insert and delete operations. Operation Sorted linked list Unsorted linked list Print() O(n) O(n) Find() O(n) O(n) Insert() O(1) O(1) Delete() O(n)/o(1) O(n)/o(1) Note : if the previous node information is present then the time complexity for the delete option becomes o(1). Stacks(LIFO): A stack is a list where the insertions and deletions can be performed at one position, that is at the end of the list, called the top. They are last in first out lists. Operations performed on a stack: 1. Push equivalent to insert 2. Pop equivalent to delete 3. Top which finds the element just inserted. In stack, only the top element is visible and that is the only element accessible to perform any operation on stack. All the stack operations are constant time operations. Since stacks are lists, they can either be implemented by arraylists or linked lists. Linked list implementation of stacks: It uses single linked lists. 1. Push inserts an element at the front of the list 2. Pop deletes an element at the front of the list 3. Top examines the element at the front of the list 4. Isempty()returns boolean 5. Isfull()returns boolean. Array implementation of the stacks: Here, the operations are performed at a very fast constant time. Each stack array has thearray() and the topofstack which is 1 for the empty stack. To insert some element into the stack, we incerement the topofstack and then set the thearray[topofstack]=x. To pop, we set the return value to the thearray[topofarray] and then decrement the topofstack. Applications of stacks: Compilers, game theory, all machines and backtracking[maze problem] Also converting the infix arithmetic expressions to the postfix arithmetic expressions uses stack adt. Priorities of the operators:(decreasing order of priority) 1. Unary operator(,++) 2. *,/,%,div 3. +, 4. ==,!=,<,>,<=,>= 5. Boolean 6. And/or 7. ( Algorithm to convert an infix expression to a post fix expression: 1. Initialize a stack 2. While (error/end of the stack) ● Read the token ● If the token is operand display it. ● If the token is (push it into the stack ● If the token is) pop and display the stack element until (is encountered. ● If the token is an operator If the stack is empty or the token as higher priority, then pop the top stack element out, and push the token into the stack Else(otherwise) pop and display the top item. (the above 2 steps should be done repeatedly) 3. At the end of the expression, pop and display stack items until stack is empty. Example: (((ab)c)d*e/f+(gh)) this is an infix expression Abcde*f/gf+ post fix expression. Below figure shows how the algorithm is implemented to convert the expression from infix to post fix. Step:1 first token is ( an operator so , its pushed into the stack ( ( ( ( ( ( * + _ ( ( ( ( ( ( ( ( ( Step 2: second token is again (, priority is compared with the elements in the stack. If its equal or less its pushed into the stack. Step 3: third token is again (, again priority is matched and its pushed into the stack Step 4: fourth token is an operand, so it is displayed. A Step 5: fifth token is , is an operator and its priority is higher than elements in stack and its pushed into the stack Step 6: token 6 is operand b, so its displayed Ab Step 7: token 7 is), now all the elements in the stack are popped out until an ( is encountered and its deleted from the stack Ab Step 8: 8th token is operator , so its priority is checked and pushed into stack Step 9: 9th token is c, it’s an operand and its displayed Abc Step 10: next token is), so the elements in the stack are check and all are displayed until (, is encountered. So the expression becomes Abc Step 11: next token is d, an operand so it is displayed Abcd Step 12: next token is *, an operand so priority is compared and since its higher, push into the stack Step 13: next token is e, it’s an operand so display it. Abcde Step 14: next token is /, it has same priority as *, pop the top element out and then display this operator also. Abcde* Step 15: next token is f, it’s an operand, so display it. Abcde*f Step 16: next token is +, compared to the existing elements and \ is popped out Abcde*f/ Step 17: next token is (, so it should be pushed into the stack and is popped out. Abcde*f/ Step 18: next token is g, and its displayed Abcde*f/g Step 19: next token is , its operator and pushed into the stack Queue Step 20: next token is h, its operand and displayed. Abcde*f/gh Step 21: next token is), so the elements in the stack are popped out until ( is encountered. Abcde*f/gh+ When the above procedure is followed for the entire infix expression, it gets converted to postfix expression. Stacks(lifo): With a queue, however, insertion is done at one end and deletion is done at the other end. Operations: Enqueue O(1) Dequeue O(1) Isempty O(1) Isfull o(1) dequeue enqueue < < Enqueue: which inserts an element at the end of the list called the rear. Dequeue: which deletes the element at the start of the list called as front. Array implementation of queues: array vs single linked list Like stacks, both the linked list and array implementation gives o(1) running times for every operation. Example: for each queue data structure we keep an array “thearray” positions “front” and “back” which represents the ends of the queue number of elements in the queue “currentsize” To enqueue an element “x”, increment currentsize and back then set thearray[back]= x To dequeue an element, set the return value to thearray[front], decrement currentsize and then increment front There appears a problem with this implementation, after several enqueues the queue will be full since back is now at the last array index, the next queue would be in a non existing position. The simple solution to this problem is that whenever front or back gets to the end of array, it is wrapped around to the beginning, known as circular array implementation. Initial state 2 4 ↑ ↑ front back After enqueue(1) 1 2 4 ↑ ↑ back front After enqueue(3) 1 3 2 4 ↑ ↑ back front After dequeue, which returns 2 1 3 2 4 ↑ ↑ back front After dequeue, which returns 4 1 3 2 4 ↑↑ front back After dequeue, which returns 1 1 3 2 4 ↑ back front After dequeue, which returns 3 and makes queue empty 1 3 2 4 ↑ ↑ back front How to distinguish queue is empty to queue is full? For array, use upto n1 items Use “counter” to keep track of # number of items in a queue If counter=0 array is full If counter=1 array is empty Applications of queues: There are many algorithms to give efficient running times. 1)virtually every real life line is a queue. For instance, lines at ticket counters are queues, because it is first come first served 2)calls to large companies are generally placed on a queue when all operators are busy 3)jobs sent to a line printer are placed on a queue
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'