DATA-STRUCTURE-LESSONS.pdf

LESSON: INTRODUCTION CLASSIFICATION TERMINOLOGIES Linear: data structures in which data elements are Data Definition: defines a particular data with the...

LESSON: INTRODUCTION CLASSIFICATION TERMINOLOGIES Linear: data structures in which data elements are Data Definition: defines a particular data with the arranged sequentially or linearly, where each element is following characteristics attached to its previous and next adjacent elements. Data Object: refer to the data that a variable can hold in Ex: array, stack, queue, LinkedList a programming language. Static: static data structure has a fixed memory size CRITERIA: Ex: array ATOMIC- definition should be define a single concept Dynamic: the size is not fixed TRACEABLE- definition should be able to Ex: queue, stack mapped to some data element (piece of Non-Liner: where data elements are not placed information or record) sequentially or linearly are called non-liner ACCURATE – definition should be Ex: trees, graphs unambiguous and understandable. DATA STRUCTURES - Specialized format to store and organize data in a computer’s memory or disk - Collection of variables, possibly of several different data types connected in various ways. PRIMITIVE VS AGGREGATE: NEED OF DATA STRUCTURE: All data structures can be classified as primitive or aggregate Data structures provide an east way of organizing, retrieving, managing and storing data. - Data structure modification is easy PREMITIVE: simple kind of data structure stores single - It requires less time data items. - Save storage memory space Ex: a variable that stores a Boolean value or an - Data representation is easy integer. - Easy access to the large database. AGGREGATE: Many data structures are capable of storing multiple data items. Ex: an array can store multiple data items in its various slots, and an object can store multiple data items via its fields. LESSON : ABSTRACT DATA TYPE FEASIBILITY: should be feasible with the available resources. ABSTRACTION : The user does not need to know the implementation of the data structure. OUTPUT: Should have 1 or more well-defined outputs, and match the desired output. BETTER CONCEPTUALIZATION: ADT gives us a better conceptualization of the real world. UNAMBIGUOUS: each of its steps (or phases) , and their inputs/outputs should be clear and must lead ROBUST: The program is robust and has the ability to to only one meaning. catch errors. MODEL Efficiency: At the heart of computer program design are ABSTRACTION: The process of providing only the two goals. Software Engineering (to design an algo that essential and hiding the details. is easy to understand, code, and debug) and Data ENCAPSULATION: It is a technique of combining the structure and algorithm analysis (to design an algo that data and the member function in a single unit is known makes efficient use of computer’s resources) as encapsulation Measurement of Complexity: determine the amount of resources necessary to execute it such as time and storage. Usually in terms of CPU time and memory requirements. Best-case Analysis [VERY RARELY USED]: OMEGA NOTATION DEFINES WHETHER THE SET OF FUNCTIONS WILL GROW FUNCTIONS FASTER OR AT THE SAME RATE AS THE EXPRESSION. - Can be used to improve accuracy of an overall worst case analysis. - Calculate the lower bound on the running time of an algorithm. - Time complexity would be Ω (1) - Occurs when x is present at the first location. ALGORITHM Average-case Analysis [RARELY USED] is a step-by-step procedure, which defines a set of THETA NOTATION instructions to be executed in a certain order to get the DEFINES WHEN THE SET OF FUNCTIONS LIES IN BOTH O desired output. (EXPRESSION) AND OMEGA (EXPRESSION). Characteristics: - It is difficult to determine average input FINITENESS: must terminate after a finite means and it has properties that makes number of steps. it difficult to mathematically characterize. INPUT: an algorithm should have 0 or more - Take all possible inputs and calculate well-defines inputs. the computing time for all inputs. INDEPENDENT: should have step-by-step - Sum all the calculated values and divide directions, which should be independent of any the sum by the total number of inputs. programming code. Worst-case Analysis [MOSTLY USED]  BIG-O NOTATION DETERMINES THE SET OF FUNCTIONS GROWS SLOWER THAN OR AT THE SAME RATE AS THE EXPRESSION IT EXPLAINS THE MAXIMUM AMOUNT OF TIME AN ALGORITHM REQUIRES TO CONSIDER ALL INPUT VALUES. - It is often of particular concern in real- time computing since it is crucial to know how much time will be needed in the worst case. - Calculate the upper bound of the running time of the algorithm. - The worst-case time complexity of the linear search would be O (n). PSEUDOCODE: is textual representation of flowchart. May become part of the program documentation. Close to a natural language; the control structures impose the logic. Could be translated into a program.