ch 1&2.pptx

Outline  Introduction Chapter 1 & 2: Introduction to Data Structures and Algorithm  Abstract Data Type and Abstraction  Properties of Algorithm  Analysis of Algorithm 08/14/2024 1 ...

Outline  Introduction Chapter 1 & 2: Introduction to Data Structures and Algorithm  Abstract Data Type and Abstraction  Properties of Algorithm  Analysis of Algorithm 08/14/2024 1  Overview of data structure and algorithm  we will deal on data structure and the theory of the analysis of the complexity of algorithms.  A program is written in order to solve a problem and a solution to a problem actually consists of two things: A way to organize the data Sequence of steps to solve the problem i.e. algorithm  The way data are organized in a computer’s memory is said to be Data Structure and the sequence of computational steps to solve a problem is said to be an algorithm.  Therefore, program is a combination of data structures plus algorithms. 08/14/2024 2  Introduction to Data Structures  Given a problem, the first step to solve the problem is obtaining one’s own abstract view, or model, of the problem. This process of modeling is called abstraction.  The model defines an abstract view to the problem. This implies that the model focuses only on problem related stuff and that a programmer tries to define the properties of the problem. These properties include: The data which are affected and The operations that are involved in the problem. With abstraction you create a well-defined entity that can be properly handled. These entities define the data structure of the program. An entity with the properties just described is called an abstract data type (ADT). 08/14/2024 3 Abstract Data Types (ADT) An ADT consists of an abstract data structure and operations. i.e. is an abstraction of a data structure. The ADT specifies: What can be stored in the Abstract Data Type? What operations can be done on/by the Abstract Data Type? A data structure is a language construct that the programmer has defined in order to implement an abstract data type. There are lots of formalized and standard Abstract data types such as Stacks, Queues, Trees, etc. Do all characteristics need to be modeled? Not at all It depends on the scope of the model It depends on the reason for developing the model 08/14/2024 4 Abstraction  Abstraction is a process of classifying characteristics as relevant and irrelevant for the particular purpose at hand and ignoring the irrelevant ones.  Applying abstraction correctly is the essence of successful programming. 08/14/2024 5  Algorithms An algorithm is a well-defined computational procedure that takes some value or a set of values as input and produces some value or a set of values as output. An algorithm transforms data structures from one state to another state in two ways: An algorithm may change the value held by a data structure An algorithm may change the data structure itself 08/14/2024 6  Properties of an algorithm  Finiteness: Algorithm must complete after a finite number of steps.  Definiteness: Each step must be clearly defined, having one and only one interpretation. At each point in computation, one should be able to tell exactly what happens next.  Sequence: Each step must have a unique defined preceding and succeeding step. The first step (start step) and last step (halt step) must be clearly noted.  Feasibility: It must be possible to perform each instruction. Correctness: It must compute correct answer all7 08/14/2024  Properties of an algorithm …  Language Independence: It must not depend on any one programming language.  Completeness: It must solve the problem completely.  Effectiveness: It must be possible to perform each step exactly and in a finite amount of time.  Efficiency: It must solve with the least amount of computational resources such as time and space.  Generality: Algorithm should be valid on all possible inputs.  Input/output: There must be a specified number of input values, and one or more result values. 08/14/2024 8  Need for Data Structure  It gives different level of organization data.  It tells how data can be stored and accessed in its elementary level.  Provide operation on group of data, such as adding an item, looking up highest priority item.  Provide a means to manage huge amount of data efficiently.  Provide fast searching and sorting of data. 08/14/2024 9  Goals of Data Structure Data structure basically implements two complementary goals.  Correctness: Data structure is designed such that it operates correctly for all kinds of input, which is based on the domain of interest. In other words, correctness forms the primary goal of data structure, which always depends on the specific problems that the data structure is intended to solve.  Efficiency: Data structure also needs to be efficient. It should process the data at high speed without utilizing much of the computer resources such as memory space. In a real time state, the efficiency of a data structure is an important factor that determines the success and failure of 08/14/2024 the process. 10  Features of Data Structure Robustness: Generally, all computer programmers wish to produce software that generates correct output for every possible input provided to it, as well as execute efficiently on all hardware platforms. This kind of robust software must be able to manage both valid and invalid inputs. Adaptability: Developing software projects such as word processors, Web browsers and Internet search engine involves large software systems that work or execute correctly and efficiently for many years. Moreover, software evolves due to ever changing market conditions or due to emerging technologies. Reusability: Reusability and adaptability go hand-in-hand. It is a known fact that the programmer requires many resources for developing any software, which makes it an expensive enterprise. However, if the software is developed in a reusable and adaptable way, then it can be implemented in most of the future applications. Thus, by implementing quality data structures, it is possible to develop reusable software, which tends to be cost effective and time saving. 08/14/2024 11  Static Data Structure Vs Dynamic Data Structure  Data structures can be two types: 1. Static Data Structure 2. Dynamic Data Structure What is a Static Data structure?  In Static data structure the size of the structure is fixed. The content of the data structure can be modified but without changing the memory space allocated to it. Example of Static Data Structures: Array 08/14/2024 12  Static Data Structure Vs Dynamic Data Structure… What is Dynamic Data Structure?  In Dynamic data structure the size of the structure in not fixed and can be modified during the operations performed on it.  Dynamic data structures are designed to facilitate change of data structures in the run time. Example of Dynamic Data Structures: Linked List Static 13  Operations on Data Structures Traversing: to access each data item exactly once so that it can be processed. For example, to print the names of all the students in a class. Searching: It is used to find the location of one or more data items that satisfy the given constraint. Inserting: It is used to add new data items to the given list of data items. For example, to add the details of a new student who has recently joined the course. Deleting: It means to remove (delete) a particular data item from the given collection of data items. For example, to delete the name of a student who has left the course. Sorting: Data items can be arranged in some order like ascending order or descending order depending on the type of application. For example, arranging the names of students in a class in an alphabetical order, or calculating the top three winners by arranging the participants’ scores in descending order and then extracting the top three. Merging: Lists of two sorted data items can be combined to form a single list of sorted data items. 08/14/2024 14  Chapter two Computational and Asymptotic Complexity 08/14/2024 15  Computational and Asymptotic Complexity  To compare the efficiency of algorithms, a measure of the degree of difficulty of an algorithm called computational complexity  Computational complexity indicates how much effort is needed to execute an algorithm, or what its cost is.  This cost can be expressed in terms of execution time (time efficiency, the most common factor) or memory (space efficiency). Time Complexity: Determine the approximate number of operations required to solve a problem of size n. Space Complexity: Determine the approximate memory required to solve a problem of size n. 08/14/2024 16  Computational and Asymptotic Complexity …  Since time efficiency is the most important, we will focus on this for the moment.  When we run a program on a computer, what factors influence how fast the program runs? One factor is obviously the efficiency of the algorithm, The speed of the computer the program is run on. The amount of input data is another factor: it will normally take longer for a program to process 10 million pieces of data than 1. Another factor is the language in which the program is written. Compiled languages are generally much faster than interpreted languages 08/14/2024 17 Computational and Asymptotic Complexity …  We need to express the relationship between the size n of the input data and the number of operations t required to process the data.  For example, if there is a linear relationship between the size n and the number of operations t (that is, t = c.n where c is a constant), then an increase in the size of the data by a factor of 5 results in an increase in number of operations by factor of 5. Similarly, if t = log2 n then a doubling of n causes t to increase by 1. 08/14/2024 18  Computational and Asymptotic Complexity …  In most real-world examples the function expressing the relationship between n and t would be much more complex.  Luckily it is not normally necessary to determine the precise function, as many of the terms will not be significant when the amount of data becomes large. For example, consider the function t = f(n) = n2 + 5n. This function consists of two terms, n2and 5n. However, for any n larger than 5 the n2 term is the most significant, and for very large n we can effectively ignore the 5n term. Therefore we can approximate the complexity function as f(n) = n2.  This simplified measure of efficiency is called asymptotic complexity  The asymptotic complexity of an algorithm is an 08/14/2024 19  Big-O Notation  The most commonly used notation for specifying asymptotic complexity, that is, for estimating the rate of growth of complexity functions, is known as big-O notation.  Given two positive-valued functions f and g, consider the following definition:  The function f(n) is O(g(n)) if there exist positive numbers c and N such that f(n) ≤ c.g(n) for all n ≥ N.  This definition states that g(n) is an upper bound on the value of f(n).  In other words, in the long run (for large n) f grows at most as fast as g. 08/14/2024 20  Big-O Notation … Consider the previous example where f(n) = n2 + 5n.  We showed in the last section that for large values of n we could approximate this function by the n2 term only; that is, the asymptotic complexity of f(n) is n2. Therefore, we can say now that f(n) is O(n2).  In the definition, we substitute n2 for g(n), and we see that it is true that f(n) ≤ 2.g(n) for all n ≥ 5 (i.e. in this case c=2, N=5).  The problem with definition 3 is that it does not tell us how to calculate c and N. In actual fact, there are usually an infinite number of pairs of values for c and N. We can show this by solving the inequality from definition 3 and substituting the appropriate terms, 08/14/2024 21  Big-O Notation … i.e. f(n) ≤ c.g(n) n2 + 5n ≤ c. n2 1 + (5/n) ≤ c  Therefore if we choose N=5, then c= 2; if we choose N=6, then c=1.83, and so on.  In the above example, the n2 term becomes larger than the 5n term at n>5, so N=5, c=2 is a good choice. 08/14/2024 22  Properties of Big-O Notation  Fact 1: If f(n) is O(h(n)) and g(n) is O(h(n)) then f(n) + g(n) is O(h(n)).  In terms of algorithm efficiency, this fact states that if your program consists of, for example, one O(n2) operation followed by another independent O(n2), then the final program will also be O(n2). i.e., 2n2  Fact 2: The function a.nk is O(nk) for any a and k.  In other words, multiplying a complexity function by a constant value (a) does not change the asymptotic complexity.  Fact 3: The function loga n is O(logb n) for any positive numbers a and b≠1 08/14/2024 23  Ω, Θ and Little-o Notations  There exist three other, less common, ways of specifying the asymptotic complexity of algorithms.  We have seen that big-O notation refers to an upper bound on the rate of growth of a function, where this function can refer to the number of operations required to execute an algorithm given the size of the input data.  There is a similar definition for the lower bound, called big-omega (Ω) notation. 08/14/2024 24  Ω- Notations  The function f(n) is Ω(g(n)) if there exist positive numbers c and N such that f(n) ≥ c.g(n) for all n ≥ N.  This definition is the same as definition 3 apart from the direction of the inequality (i.e. it uses ≥ instead of ≤).  We can say that g(n) is a lower bound on the value of f(n), or, in the long run (for large n) f grows at least as fast as g.  For some algorithms (but not all), the lower and upper bounds on the rate of growth will be the same.  In this case, a third notation exists for specifying asymptotic complexity, called theta (Θ) notation. 08/14/2024 25  Θ-Notations  The function f(n) is Θ(g(n)) if there exist positive numbers c1, c2 and N such that c1.g(n) ≤ f(n) ≤ c2.g(n) for all n ≥ N.  This definition states that f(n) is Θ(g(n)) if f(n) is O(g(n)) and f(n) is Ω(g(n)).  In other words, the lower and upper bounds on the rate of growth are the same.  The final notation is little-o notation, You can think of little-o notation as the opposite of Θ notation.  The function f(n) is o(g(n)) if f(n) is O(g(n)) but f(n) is not Θ(g(n)). 08/14/2024 26  Complexity Classes  We have seen now that algorithms can be classified using the big-O, Ω and Θ notations according to their time or space complexities.  A number of complexity classes of algorithms exist, and some of the more common ones are illustrated below. 08/14/2024 No. Input data (n) The number of operations required by algorithms of various complexity classes Complexity Class Number of operations performed based on size of input data n Name Big-O n=10 n=100 n=100 n=10,00 n=100,00 n=1,000,0 0 0 0 00 Constant O(1) 1 1 1 1 1 1 Logarithmi O(log n) 3.32 6.64 9.97 13.3 16.6 19.93 c Linear O(n) 10 100 1000 10,000 100,000 1,000,000 n log n O(n log 33.2 664 9970 133,000 1.66 * 106 1.99 * 107 n) Quadratic O(n2) 100 10,000 106 108 1010 1012 Cubic O(n3) 1000 106 109 1012 1015 1018 Exponenti O(2n) 1024 1030 10301 103010 1030103 10301030 al 08/14/2024 28  The Best, Average and Worst Cases  This last example indicates the need for distinguishing a number of different cases when determining the efficiency of algorithms.  The worst case is the maximum number of operations that an algorithm can ever require,  The best case is the minimum number, and  The average case comes somewhere in between these two extremes. 08/14/2024 29  ? 08/14/2024 30