Data Structures and Algorithms PDF

o A module – small sec,on of a program that is customized to perform a par,cular task - Can be customized by a programmer to do a par,cular task UNIT 5 o Recursion – when a method calls itself un,l some termina,ng condi,on is met - Accomplished without any spe...

o A module – small sec,on of a program that is customized to perform a par,cular task - Can be customized by a programmer to do a par,cular task UNIT 5 o Recursion – when a method calls itself un,l some termina,ng condi,on is met - Accomplished without any specific repe,,on construct, such as while or a for loop - Follows one of the basic problem-solving techniques, which is to break down the problem at hand into smaller subtasks o Any algorithm that may be presented in a recursive manner can also be presented in an itera,ve manner and vice versa - Recursive algorithms are considered as harder to code o The Koch snowflake – mathema,cal curve which is based on the Koch curve à developed by the Swedish mathema,cian Helge von Koch - Can be constructed by star,ng an equilateral triangle o Using recursion each line segment changes using the following steps: 1. Divide the ini,al line segment into 3 sub-segments of the same length 2. Draw an outward-poin,ng equilateral triangle that has the middle segment from step (1) as its base 3. Delete the line segment that is the base of the triangle from the previous step o In many cases, data comes in the form of a data table. Each element in a 2D array must be of the same type, either a primi,ve or object type o A stack – stores a set of elements in a par,cular order and allows access only to the last item inserted - Items are retrieved in the reverse order in which they are inserted - Last-In, First-Out data structure (LIFO) o Stacks u;lize 3 methods: 1. push (). Pushes an item onto a stack 2. pop (). Removes and returns the last item entered in the stack 3. isEmpty (). Tests if a stack is empty. It will return true if the stack contains no elements LOOK AT PAGE 11 o A queue – stores a set of elements in a par,cular order and allows access only to the first item inserted - Items are retrieved in the order in which they are inserted - First-In, First-Out data structure (FIFO) o Queue u;lize 3 methods: 1. Enqueue (). Puts an item into the end of the queue 2. Dequeue (). Removes and returns the first item entered in the queue 3. isEmpty (). Tests if a queue is empty. It will return true if the queue contains no elements  o Applica;ons of queues: 1. Queues are used to model physical queues, such as people wai,ng in line at a supermarket checkout 2. The print queue displays the documents that are wai,ng to be printed. These documents will follow the first-send first-print policy 3. When sending data over the internet, various data packets wait in a queue to be sent 4. A server usually serves various requests. In most cases, these requests are stored in a queue. The first-come-first-served request procedure is followed o Methods: - Push (). – used to add elements to the stack. Inser,ng an element increments high by 1 and adds the element to this array posi,on. The high is incremented before the inser,on of the new item takes place. - Pop (). – returns the value of the top element and then decrements high. It serves to remove the top element from the stack. The item removed actually remains in the array but is inaccessible. - isEmpty (). – based on the high variable. It returns true(1) if the stack is empty - isFull (). – based on the high variable. It returns true(1) if the stack is full - size (). – based on the high variable. It returns the number of elements stored in the stack. PAGE 27 > data - and pointer o Node – a basic unit that contains both data and a pointer - Requires memory for both its data and pointer o A pointer – a field of the node whose value points to another object, stored in some other memory loca,on - o Each node in a linked list stores a pointer to the next value of the linked list o The NULL pointer – a special pointer that points to nothing, meaning that it has no pointee - Drawn as a diagonal line between the leN lower corner and the right upper corner of the pointers variable box o Linked lists – constructed from a series of nodes - Every node of the list is a dis,nct object that contains both data, as well as a reference (pointer) to the next node - Different from the array - Both are used to create lists à opera,onal characteris,cs are completely different - In the linked list – a par,cular element can only be accessed by following the references of all the previous elements à you cannot access an element directly - To insert an element in, one must first search through the list un,l he/she finds the correct place - Reference refers to an object’s address in the RAM o Logical representa;on – how the data and the links are “seen” by the programmer  o Physical representa;on – underlying mechanisms that store the data in RAM à memory addresses, types of data, number of bytes used, the way the pointers are used o Characteris;cs of a linked list: 1. To traverse a linked list, you start at the first node and then go from node to node, following each node’s pointer to find the next node 2. A node with a specific key value can be found by traversing the list. Once found, a node’s data can be accessed 3. A linked list consists of a sequence of nodes 4. Each node contains data and a pointer 5. A linked list may be empty 6. The length of a linked list is the number of elements that it contains 7. The last node contains a null pointer 8. A node’s successor is the next node 9. A node’s predecessor is the previous node PAGE 32, 33, 34 o To search for a specific element, in a sorted or unsorted linked list, the linear search must be followed o Star,ng from the first node, all elements are examined un,l the desired element is found o If the element is not in the linked list, an appropriate message is returned o Sorted linked list –it is useful to examine a program that keeps all array elements sorted, in descending order, at all ,mes - Keeping a list sorted makes it possible to apply binary search when searching for a data item o Advantages of sorted linked lists: 1. All data are stored according to a key value 2. The programmer can use it in the same way as a sorted array is used 3. Elements do not need to be moved, but only pointers need to be altered à high- speed element inser,on 4. Can easily expand to any size that is supposed by the available RAM o Double-linked lists – each node contains data, a pointer and its successor, and a pointer to its predecessor - The header node points to the first node and to the last node of the list - If the linked list is empty, the pointers point to NULL - Web browsers o Advantages of the double-linked lists: 1. The first node and the last node of such a list are directly accessible without traversal and allow traversal of the list from the beginning or the end 2. The pointers of each node allow transversal of the list in either direc,on 3. Dele,on and inser,on before a node is easier o Disadvantages of the double-linked lists: 1. Addi,onal space used 2. Requires 2 pointers per node à needs twice as much overhead o Circular-linked lists – linked list in which the last link points back to the first link - Easy to loop and access all the nodes circularly, and one can traverse the en,re list star,ng from any node - Implementa,on is more complex and extra cau,on is needed so as not to end up in an infinite loop - Applica,on of the lists include OS ,me-sharing algorithms and mul,player games o Binary trees – combine the quick inser,on and dele,on of linked lists, as well as the quick searching of an ordered array - Are fascina,ng dynamic data structures that have been studied as abstract mathema,cal en,,es - Belong to the graph category and consist of nodes that are connected by edges - The top node is connected to two or more nodes on the next row à nodes represent values or objects and the edges represent the way the nodes are connected/related - May have 0,1 or 2 children o Traversing a tree- to visit each node in a specified order - 3 ways to implement tree traversal: inorder, preorder, and postorder à work with all binary trees o Inorder traversal of a binary search tree will visit all the nodes in ascending order, according to their key values  o Inorder traversal algorithm – ini,ally starts with the root node as an argument and performs the following recursive steps: E 1. The algorithm calls itself to tzraverse the node’s leN-hand subtree 2. The algorithm visits the current node 3. The algorithm calls itself to traverse the node’s right-hand subtree o Postorder traversal algorithm – ini,ally starts with the root node as an argument and performs the following recursive steps: 1. The algorithm calls itself to traverse the node’s leN-hand subtree E 2. The algorithm calls itself to traverse the node’s right-hand subtree 3. Visit the node // Recall that visit a node means to perform an ac,on o A binary tree can be a valuable tool to symbolize an algebraic expression that involves operands and operators (+, -, /, *) o 3 nota;ons may be used: infix, prefix, pos`ix - In the infix nota,on, an operator is placed between two operands - In the possix nota,on, the operator follows the operands - In the prefix nota,on, the operator comes before the operands o Adding a new data item means adding a new object - An object is added in the correct posi,on of the trees as a node according to its key value - Adding a new data item is similar to adding a new node o Searching for a par,cular data item in a binary search tree involves comparing the value to be found with the key value of a node, and the following: - The node’s leN-hand child if the search value is smaller than the current node’s key value - The node’s right-hand child if the search value is greater than the current node’s key value m Pram) o To insert a new node into a binary search tree, follow the steps: 1. If the binary search tree is empty, insert the new node at the root 2. If the binary search tree is not empty, follow the root to the parent of the node to be inserted 3. The parent will be a leaf node. Insert the new node, according to the following rules: a. If the key of the new node is smaller than the key of the parent node, then connect the new node as the parent’s leN-hand child b. If the key of the new node is greater that the key of the parent node, then connect the new node as the parent’s right-hand child Practicea E  o An unbalanced tree – a tree whose leN or right-hand subtree has a lot more nodes than the other subtree o Binary trees become unbalanced because of the order in which the data items are inserted o A dynamic data structure changes its size at execu;on ;me as required by its elements o Alloca,on and de-alloca,on of memory is controlled by the data structure DEFINITION ADVANTAGES DISADVANTAGES DYNAMIC Memory is allocated § Makes the most efficient use § Given that the memory alloca\on to the data structure of RAM as it only uses as is dynamic, it is likely that the dynamically à ex. much memory as it needs structure will ‘overflow’ should it Stack implemented § One does not need to know exceed its allowed limit or using linked lists or decide upon the size of the ‘underflow’ should it become data structure on advance empty § In most cases algorithms with dynamic data are slow, during execu\on, than algorithms with sta\c data structure § Random access is not allowed and elements should be visited sequen\ally § As such, there is no way to implement binary search § More complicated to program as the sotware needs to keep track of its size and data item loca\ons at all \mes STATIC Memory is allocated § The memory alloca\on is § Can be very inefficient as the at compile \me. The fixed and as such there will memory for the data structure is size is predefined occur no problems when predefined and can never adding or removing data § Even when the array has no data change during run- items elements in it, s\ll takes up the \me à ex. Stack § Easier to program as there is RAM space that was allocated at implemented using no need to check upon the compile \me arrays data structure size § Some\mes is difficult to predict § The space reserved in RAM the required array size will always be available, in § In a sorted array, inser\ng a new order to be used by the data element in the correct posi\on or structure dele\ng an exis\ng one, requires shiting of other elements o An Abstract Data Type (ADT) – an abstract conceptual tool - All data structures can be used to implement ADTs - A (sta,c) linked list can be implemented using an array and an array-type structure can be implemented using a linked list o Building a linked list using an array is the op,on for primi,ve-level languages and assembly languages that require fixed-size data structures and do not support dynamic memory alloca,on o ADTs are conceptual models that abstract their fundamental data structures and are used with some specific purpose in mind