PRINT (SHORT PAPER).pdf

DATA STRUCTURES HANDOUT 1 & 2 REVIEWER Fundamentals of Data Priority queue - a special type of queue Structures and Algorithms where elements are processed based on their order (natural or custom). Data St...

DATA STRUCTURES HANDOUT 1 & 2 REVIEWER Fundamentals of Data Priority queue - a special type of queue Structures and Algorithms where elements are processed based on their order (natural or custom). Data Structures Heap - a complete binary tree where the - A data structure is a special format value of each of each parent node is either for storing and organizing data. higher or lower than the value of its child nodes. Set - a collection of elements where each TWO (2) TYPES OF DATA element is unique. STRUCTURE: Map - a set of ordered pairs where elements - Linear: Elements are accessed in a are known as keys (identifiers) and values sequential order but may be stored (content). unsystematically. Graph - consists of a set of vertices (or - Non-Linear: Elements are stored nodes) and a set of edges (relations) between and accessed in a non- sequential the pairs of vertices. order. The four (4) main operations that could be an ABSTRACT DATA TYPE (ADT) is a defined for each ADT are initializing, logical description of how data is viewed as (adding, accessing, and removing of data.) well as the operations that are allowed without regard to how they will be Algorithm implemented. - An algorithm is a step-by-step set of instructions to be executed in TWO (2) PARTS OF ADT: sequence for solving a problem. Public or external - the data and the operations Characteristics of an algorithm: Private or internal - implementation the - Finiteness: An algorithm must representation and the implementation terminate after a specified number of steps. Abstract data types: - Definiteness: Each instruction has to Linked list - used for storing elements be clear and. unambiguous. where each is a separate object. - Input: An algorithm should have Stack - an ordered list in which the last zero or more well-defined data given element added is the first element retrieved before the algorithm begins. or removed (Last-In, First-Out). - Output: An algorithm must have Queue an ordered list in which the first one (1) or more results, with element added is the first element retrieved specified relation to the input. or removed (First-In, First- Out). - Uniqueness: The result of each step Tree - represents a hierarchical nature of a depends on the input and/or the structure in a graphical form. result of the previous step. Page | 1 Elements of an algorithm: A RECURSIVE ALGORITHM - Sequential operations MUST: - Actions based on the state of a data BASE CASE is the condition that allows structure the algorithm to stop recurring. - Iteration - repeating an action A CHANGE OF STATE means that some multiple time data that the algorithm is using is modified. - Recursion - occurs when a function Call itself, recursively. calls itself once or multiple times to solve a problem Types of Recursion: Linear recursion - the function calls itself Algorithm design paradigms: once each time it is invoked. Divide and Conquer: A problem is broken (Ex. finding the factorial) into smaller subproblems. Tail recursion - the function makes a Greedy Algorithms: The optimal approach recursive call as its very last operation. is always chosen in solving a problem. (Ex. finding the greatest common divisor of Dynamic Programming: Similar to Divide two (2) non-zero integers) and Conquer except that the results of the Binary recursion - The function calls itself subproblems are reused for overlapping twice in the run of the function. subproblems. Ex. Fibonacci series Mutual recursion - the function works in a RECURSION pair or a group. Fundamentals (Ex. determining whether an integer is even Recursion - is a process where a function or odd.) calls itself once or multiple times to solve a problem. RECURSION VS. ITERATION Iteration is a process of repeating a set of Any function that calls itself is instructions. This is also known as "looping." RECURSIVE. Recursion that involves a method directly RECURSION ITERATION calling itself is called It terminates when a It terminates when a base case is reached. condition is proven to be DIRECT RECURSION. false. Each recursive call Each iteration does not INDIRECT RECURSION occurs when a requires extra memory require extra memory method invokes another method, eventually space. space. resulting in the original method being An infinite recursion An infinite loop could invoked again. may cause the program loop forever since there to run out of memory is no extra memory When a recursive function fails to stop and may result in stack being created. recursion, INFINITE RECURSION overflow. occurs. Solutions to some Iterative solutions to a problems are easier to problem may not always formulate recursively. be as obvious as a recursive solution. Page | 2