CS 201 - Data Structures & Algortithm.pdf

What is Data Structures? Dynamic – the size can change dynamically, like in lists. In computer science, a data structure is a particular way of storing and organizing Classification of Data Structure data in a computer so that i...

What is Data Structures? Dynamic – the size can change dynamically, like in lists. In computer science, a data structure is a particular way of storing and organizing Classification of Data Structure data in a computer so that it can be used According to Relationship efficiently. Linear – this data structure maintains a Data Structures are generally based on a linear relationship between its elements, computer's ability to fetch (retrieve) and e.g., array. store data at any place in its memory, specified by an address—a bit string that Non-linear – this data structure does not can be stored in memory and manipulated maintain any linear relationship between its by the program. elements, e.g., in a tree. Classification of Data Structure Memory According to Type Main memory (RAM) – where instructions Primitive – these are basic data structures (programs) and data are stored; volatile and are directly operated upon machine means may be lost once the computer is instructions, e.g., integer, character. powered down. Cache memory in the central processing Non-primitive – these are derived from unit (CPU) – is used to store frequently primitive data structures, e.g., arrays. used instructions and data that either is, will be, or has been used by the CPU. A Classification of Data Structure segment of the CPU’s cache memory is called a register ( a small amount of According to Elements memory that is used to temporarily store instructions and data. Homogeneous – in this data structure, all Persistent storage (external storage elements are of the same type, e.g. array. devices) – used to store instructions and data in external devices such as a hard Heterogeneous – in this data structure, disk; non-volatile; commonly used by the elements are of different types, e.g., operating system as virtual memory (a structure. technique an OS uses to increase the main memory capacity beyond the RAM). Classification of Data Structure Reserving Memory According to Size Data used by a program is stored in memory and manipulated by various data structure techniques, depending on Static – the size of this data structure the nature of the program. cannot be changed after the initial. allocation, like matrices. What is an Abstract Data Update − Algorithm to update an existing item in a data structure. Type(ADT)? Delete − Algorithm to delete an existing item from a data structure. It is a programming language keyword that specifies the amount of memory needed to store data and the kind of data stored in Characteristics of an Algorithm that memory location. Unambiguous − The algorithm should be unambiguous. Each of its steps (or phases), and their inputs/outputs should be clear and Abstract Data Type Groups must lead to only one meaning. Integer - stores whole numbers and signed Input − An algorithm should have 0 or more numbers well-defined inputs. Floating-point - stores real numbers Output − An algorithm should have 1 or (fractional values). more well-defined outputs and should match the desired output. Character - It is represented as an integer value that corresponds to a character set. Finiteness − Algorithms must terminate after a finite number of steps. Boolean - stores a true or false value. Feasibility − This should be feasible with Algorithm the available resources. An algorithm is a step-by-step procedure, Independent − An algorithm should have which defines a set of instructions to be step-by-step directions, which should be executed in a certain order to get the independent of any programming code. desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be Algorithm Analysis implemented in more than one programming language. A Priori Analysis − This is a theoretical analysis of the Efficiency of an algorithm Basic Categories of Algorithm that is measured by assuming that all other factors, for example, processor Search − Algorithm to search an item in a speed, are constant and have no effect on data structure. the implementation. Sort − Algorithm to sort items in a certain order. A Posterior Analysis − This is an Insert − Algorithm to insert an item in a data empirical analysis of an algorithm. The structure. selected algorithm is implemented using a programming language. This is then executed on the target computer In this Asymptotic Analysis analysis, actual statistics like running time an algorithm refers to defining the and space required, are collected. mathematical foundation/framing of its run-time performance Algorithm Complexity The time required by an algorithm falls under three types: Time Factor - Time is measured by counting the number of key operations Best Case − Minimum time required for the such as comparisons in the sorting program Average Case − Average time required for Space Factor - Space is measured by the program counting the maximum memory space Worst Case − Maximum time required for required the program Space Complexity.Asymptotic Notations an algorithm represents the amount of memory space required by the algorithm The Notation O expresses the in its life cycle. upper bound of an algorithm’s running time. It measures the Two Components: worst-case time complexity A fixed part is a space required to store certain data and variables, that are independent of the size of the Omega Notation expresses the problem. For example, simple lower bound of an algorithm’s variables and constants used, running time. It measures the program size, best-case time complexity or the best amount of time an algorithm A variable part is a space required can take to complete. by variables, whose size depends on the size of the, for example, Theta Notation expresses both the dynamic memory allocation, lower bound and the upper bound recursion stack space, etc. of an algorithm's running time. Time Complexity an algorithm represents the amount of time Array required by the algorithm to run to a collection of items stored in contiguous completion, which can be measured as memory locations. The idea is to store the number of steps, provided each step multiple items of the same type together. consumes constant time. This makes it easier to calculate the position of each element Accessing Array Element To access an array element or a part of the array, you use a number called an index or a subscript. ArrayList a part of collection framework and is present in java.util package. It provides a dynamic way of manipulating data. ArrayList Constructors ArrayList(): This constructor is used Creation of Stack to build an empty array list used by importing the java.util library. ArrayList(Collection c): This constructor is used to build an array Stack s = new list initialized with the elements from Stack(); collection c Stack Operations ArrayList(int capacity): This push( ) operation is used both to constructor is used to build an array initialize the stack and to store list with initial capacity being values to it. specified pop( ) operation is responsible for removing a value from the stack, What is a Stack? and decrementing the value of size. a way to group things together by placing size( )operation is an operation to one thing on top of another and then determine the size (number of items) removing things one at a time from the of the Stack. It is used mainly to top of the stack. control loops. peek( ) operation is a method that a Last-In, First-Out (L I F O) abstract data looks at the item at the top of a type and data structure stack. The peek ( ) method returns the item at the top without removing it. search ( ) member method is a Stack as Data Structure method that returns the position (in A stack is a restricted data structure number) of an item from the top of a because only a small number of operations stack are performed on it. empty ( ) member method is a method that tests if a stack object is empty or not.