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