Chapter One & Two DSA PDF

Chapter One: Introduction to Data Structures 1.1. Introduction to Data Structures and Algorithms Analysis A program is written in order to solve a problem. A solution to a problem actually consists of two things:-  A way to organize the data.  Sequence of steps to solve the problem. Th...

Chapter One: Introduction to Data Structures 1.1. Introduction to Data Structures and Algorithms Analysis A program is written in order to solve a problem. A solution to a problem actually consists of two things:-  A way to organize the data.  Sequence of steps to solve the problem. 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, a program is nothing but data structures plus algorithms. 1.1.1. Introduction to Data Structures Data Structure is simply a way to organize data. Data Structure can also refers to a collection of variables, possibly of different data types connected in various ways. 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). 1.1.2. Abstract Data Types Compiled by: Musa A. (MSc.) 1|Page An ADT consists of an abstract data structure and operations. Put in other terms, an ADT is an abstraction of a data structure. The ADT specifies: 1. What can be stored in the Abstract Data Type 2. What operations can be done on/by the Abstract Data Type. For example, if we are going to model employees of an organization:  This ADT stores employees with their relevant attributes and discarding irrelevant attributes.  This ADT supports hiring, firing, retiring … operations. A data structure is a language construct that the programmer has defined in order to implement an abstract data type. 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. Types of Data Structure: There are lots of formalized and standard Abstract data types such as: ▪ Array ▪ Linked list ▪ Queue ▪ Stacks ▪ Trees ▪ Hast Tables 1.1.2.1. 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 Compiled by: Musa A. (MSc.) 2|Page Chapter 2: Algorithm and Algorithm Analysis 2.1. Introduction 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. Data structures model the static part of the world. They are unchanging while the world is changing. In order to model the dynamic part of the world we need to work with algorithms. Algorithms are the dynamic part of a program’s world model. Algorithm is a recipe/formula/ direction for solving a problem. It is a finite set of instructions, which, if followed, accomplish a particular task. 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. The quality of a data structure is related to its ability to successfully model the characteristics of the world. Similarly, the quality of an algorithm is related to its ability to successfully simulate the changes in the world. However, independent of any particular world model, the quality of data structure and algorithms is determined by their ability to work together well. Generally speaking, correct data structures lead to simple and efficient algorithms and correct algorithms lead to accurate and efficient data structures. 2.2. 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 for all possible legal inputs. 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. Compiled by: Musa A. (MSc.) 3|Page  Input/Output: There must be a specified number of input values, and one or more result values. 2.3. Algorithm Analysis Concepts Algorithm analysis refers to the process of determining the amount of computing time and storage space required by different algorithms. In other words, it’s a process of predicting the resource requirement of algorithms in a given environment. In order to solve a problem, there are many possible algorithms. One has to be able to choose the best algorithm for the problem at hand using some scientific method. To classify some data structures and algorithms as good, we need precise ways of analyzing them in terms of resource requirement. The main resources are:  Running Time  Memory Usage  Communication Bandwidth Running time is usually treated as the most important since computational time is the most precious resource in most problem domains. There are two approaches to measure the efficiency of algorithms: Empirical: Programming computing algorithms and trying them on different instances. Theoretical: Determining the quantity of resources required mathematically (Execution time, memory space, etc.) needed by each algorithm. However, it is difficult to use actual clock-time as a consistent measure of an algorithm’s efficiency, because clock-time can vary based on many things. For example,  Specific processor speed  Current processor load  Specific data for a particular run of the program o Input Size o Input Properties  Operating Environment Accordingly, we can analyze an algorithm according to the number of operations required, rather than according to an absolute amount of time involved. This can show how an algorithm’s efficiency changes according to the size of the input. 2.3.1. Complexity Analysis Complexity Analysis is the systematic study of the cost of computation, measured either in time units or in operations performed, or in the amount of storage space required. Compiled by: Musa A. (MSc.) 4|Page The goal is to have a meaningful measure that permits comparison of algorithms independent of operating platform. There are two things to consider:  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. Complexity analysis involves two distinct phases:  Algorithm Analysis: Analysis of the algorithm or data structure to produce a function T(n) that describes the algorithm in terms of the operations performed in order to measure the complexity of the algorithm.  Order of Magnitude Analysis: Analysis of the function T(n) to determine the general complexity category to which it belongs. There is no generally accepted set of rules for algorithm analysis. However, an exact count of operations is commonly used. 2.3.1.1. Alaysis Rules: 1. We assume an arbitrary time unit. 2. Execution of one of the following operations takes time 1:  Assignment Operation  Single Input/Output Operation  Single Boolean Operations  Single Arithmetic Operations  Function Return 3. Running time of a selection statement (if, switch) is the time for the condition evaluation + the maximum of the running times for the individual clauses in the selection. 4. Loops: Running time for a loop is equal to the running time for the statements inside the loop * number of iterations. The total running time of a statement inside a group of nested loops is the running time of the statements multiplied by the product of the sizes of all the loops. For nested loops, analyze inside out.  Always assume that the loop executes the maximum number of iterations possible. 5. Running time of a function call is 1 for setup + the time for any parameter calculations + the time required for the execution of the function body. Examples: 1. int count(){ int k=0; cout>n; for (i=0;i