Fundamentals of Data Structures and Algorithms PDF

IT1815 Fundamentals of Data Structures and Algorithms as keys (identifiers) and values (content)....

IT1815 Fundamentals of Data Structures and Algorithms as keys (identifiers) and values (content). o Graph – consists of a set of vertices (or nodes) and a set Data Structures of edges (relations) between the pairs of vertices. A data structure is a special format for storing and organizing The four (4) main operations that could be defined for each ADT data. are initializing, adding, accessing, and removing of data. Two (2) types of data structure: o Linear: Elements are accessed in a sequential order but Algorithm may be stored unsystematically. An algorithm is a step-by-step set of instructions to be executed o Non-Linear: Elements are stored and accessed in a non- in sequence for solving a problem. sequential order. Characteristics of an algorithm: An abstract data type (ADT) is a logical description of how data o Finiteness: An algorithm must terminate after a specified is viewed as well as the operations that are allowed without number of steps. regard to how they will be implemented. o Definiteness: Each instruction has to be clear and Benefits of using ADT: unambiguous. o Code is easier to understand. o Input: An algorithm should have zero or more well-defined o Implementations of ADTs can be changed without data given before the algorithm begins. requiring changes to the program that uses the ADTs. o Output: An algorithm must have one (1) or more results, o ADTs can be used in future programs. with specified relation to the input. Two (2) parts of ADT: o Uniqueness: The result of each step depends on the input o Public or external – the data and the operations and/or the result of the previous step. o Private or internal – the representation and the Elements of an algorithm: implementation o Sequential operations Abstract data types: o Actions based on the state of a data structure o Linked list – used for storing elements where each is a o Iteration – repeating an action multiple times separate object. o Recursion – occurs when a function calls itself once or o Stack – an ordered list in which the last element added is multiple times to solve a problem the first element retrieved or removed (Last-In, First-Out). Algorithm design paradigms: o Queue – an ordered list in which the first element added o Divide and Conquer: A problem is broken into smaller is the first element retrieved or removed (First-In, First- subproblems. Out). o Greedy Algorithms: The optimal approach is always o Tree – represents a hierarchical nature of a structure in a chosen in solving a problem. graphical form. o Dynamic Programming: Similar to Divide and Conquer o Priority queue – a special type of queue where elements except that the results of the subproblems are reused for are processed based on their order (natural or custom). overlapping subproblems. o Heap – a complete binary tree where the value of each of References: Karumanchi, N. (2017). Data structures and algorithms made easy. Hyderabad: each parent node is either higher or lower than the value CareerMonk Publications. of its child nodes. Lee, K. and Hubbard, S. (2015). Data structures and algorithms with Python. Cham: o Set – a collection of elements where each element is Springer International Publishing Switzerland. unique. Runestone Academy (n.d.). Citing sources. Retrieved from https://interactivepython.org/runestone/static/pythonds/index.html o Map – a set of ordered pairs where elements are known 01 Handout 1 *Property of STI  [email protected] Page 1 of 1  IT1815 RECURSION Types of Recursion Linear recursion – The function calls itself once each time it Fundamentals is invoked. Ex. finding the factorial Recursion is a process where a function calls itself once or multiple times to solve a problem. Any function that calls itself is recursive. Recursion that involves a method directly calling itself is called direct recursion. Indirect recursion occurs when a method invokes another method, eventually resulting in the original method being invoked again. When a recursive function fails to stop recursion, infinite recursion occurs. Output: A recursive algorithm must: o Have a base case – A base case is the condition that allows the algorithm to stop recurring. o Change its state and move toward the base case – A change of state means that some data that the Tail recursion – The function makes a recursive call as its algorithm is using is modified. very last operation. Ex. finding the greatest common divisor o Call itself, recursively. of two (2) non-zero integers Recursion vs. Iteration Iteration is a process of repeating a set of instructions. This is also known as “looping.” Recursion Iteration It terminates when a base It terminates when a condition case is reached. is proven to be false. Each recursive call Each iteration does not requires extra memory require extra memory space. space. An infinite recursion may An infinite loop could loop Output: cause the program to run forever since there is no extra out of memory and may memory being created. result in stack overflow. Solutions to some Iterative solutions to a problems are easier to problem may not always be as formulate recursively. obvious as a recursive solution. 02 Handout 1 *Property of STI  [email protected] Page 1 of 2  IT1815 Binary recursion – The function calls itself twice in the run Output: of the function. Ex. Fibonacci series References: Karumanchi, N. (2017). Data structures and algorithms made easy. Hyderabad: CareerMonk Publications. Runestone Academy (n.d.). Citing sources. Retrieved from https://interactivepython.org/runestone/static/pythonds/index.html Output: Mutual recursion – The function works in a pair or a group. Ex. determining whether an integer is even or odd 02 Handout 1 *Property of STI  [email protected] Page 2 of 2  IT1815 Linked Lists It can grow and shrink The array size is specified during program execution. during declaration. Linked List Basics The position of the elements The position of the elements A linked list is used for storing a collection of data where each is allocated during runtime. is allocated during element is a separate object. compilation. Elements in a linked list are called nodes. Elements are sequentially Elements are randomly The parts of a node are the following: accessed. accessed. Data Pointer It utilizes memory efficiently. Memory utilization is o Data field – This contains the value of the element. ineffective. o Pointer field (link or reference) – This contains the address (random memory location) of the next node. Types of Linked List The next node in the list is referred to as the successor. Singly linked list – the basic linked list The first node in the list is called head. Doubly linked list – contains an extra pointer to connect to The last node points to null since there are no more the previous node in the sequence. The left pointer contains successive elements. the address of the preceding node called “predecessor.” Left Pointer Data Right Pointer A linked list is illustrated by: o Placing the address of the node above its data field o Placing the address of the next node in the node’s A doubly linked list is illustrated by: pointer field o Placing the address of the node above its data field o Indicating null in the pointer field of the last node o Placing the address of the preceding node in the o Connecting the previous node to the next node using node’s left pointer field an arrow to the right. o Placing the address of the next node in the node’s Operations of a linked list: right pointer field o Display – shows the elements in the list o Indicating null in the left pointer field of the first node o Insert – adds an element into the list and in the right pointer field of the last node. o Delete – removes a specific element or all the Circular linked list is a linked list in which the last node’s right elements from the list pointer contains the address of the first node. o Search – finds a specific element in the list o Count – returns the number of elements in the list Linked List versus Array Iteration is the process of repeating a set of instructions. This References: Karumanchi, N. (2017). Data structures and algorithms made easy. Hyderabad: is also known as “looping.” CareerMonk Publications. Linked List Array TechDifferences (n.d.). Differences between array and linked list. Retrieved from https://techdifferences.com/difference-between-array-and-linked-list.html The number of elements The number of elements is can expand. fixed upon creating the array. 03 Handout 1 *Property of STI  [email protected] Page 1 of 1