Data Stuctures.pdf

Data Stuctures Algorithm A data structure is a special format for An algorithm is a step-by-step set of storing and organizing data. instruction to be executed in sequence for Two types of data structures are:...

Data Stuctures Algorithm A data structure is a special format for An algorithm is a step-by-step set of storing and organizing data. instruction to be executed in sequence for Two types of data structures are: solving problem. Linear: Elements are stored and Characteristics of an algorithm: accessed in a non sequential order. Finiteness: An algorithm must terminate Non-Linear: Elements are stored after a specified number of steps. and accessed in a non sequential order. Definiteness: Each instruction has to be clear and unambiguous. An abstract data type (ADT) is a logical Input: An algorithm should have zero or description of how data is viewed as well as more well-defined data given before the operation the operations that are the algorithm begins. allowed without regard to how they will be Output: An algorithm must have one (1) or implemented. more results, with specified relation Two parts of ADT: to the input. Public or external - the data and Uniqueness: The result of each step the operations depends on the input and/or the result of Private or internal - the the previous step. representation and implementation. Abstract data types: Elements of an algorithm: Linked list is used for storing Sequential operations elements where each is a separate object. Actions based on the state of a data Stack is an ordered list in which structure insertion and deletion are done at one (1) Iteration – repeating an action multiple end. times Queue is an ordered list in which Recursion – when a function calls itself insertion and deletion are done at separate. once or multiple times to solve a Tree represent a hierarchical nature problem of a structure in a graphical form. Priority queue is used for retrieving Algorithm design paradigms: and removing either the minimum or Divide and Conquer – breaking a problem maximum element. into smaller subproblems Heap is partially sorted binary tree. Greedy Algorithms – always chooses the Set represents collection of optimal approach in solving a problem elements that do not have to be in order. Dynamic Programming – similar to divide Map is a set of ordered pairs with and conquer except that the results of elements known askey and value. the subproblems are used for overlapping Graph consist of a set of subproblem points/nodes (vertices) and set of links (edges) which connects pairs of vertices. The four (4) main operations that could be defined for each ADT are initializing, adding, accessing, and removing data.