Unit 1 abstract data types

Data structure

1. ABSTRACT DATA TYPES

2. INTRODUCTION Data items are represented within a computer as a sequence of binary digits. To distinguish between the different types of data, the term type is often used to refer to a collection of values and the term data type to refer to a given type along with a collection of operations for manipulating values of the given type.

3. The data types known as primitives come in two categories : simple and complex . Simple data types :- values that are in the most basic forms and cannot be decomposed into smaller parts. Ex- Integer and real types. Complex data types:- constructed of multiple components consisting of simple types or other complex types. In python objects, strings, list and dictionaries which can contain multiple values are all examples of complex types.

4. ABSTRACTIONS An Abstractions is a mechanism for separating the properties of an object and restricting the focus to those relevant in the current context. The user of the abstractions does not have to understand all of the details in order to utilize the object, but only those relevant to the current task or problem.

5. TYPES OF ABSTRACTION 2 TYPES:- 1.Procedural abstraction – use of function or method knowing what it does but ignoring how it’s accomplished. 2. Data abstraction – separation of the properties of a data type from the implementation of that data type.

6. ABSTRACT DATA TYPES An abstract data type (or ADT) is a programmer defined data type that specifies a set of data values and a collection of well defined operations that can be performed on those values . Abstract data types are defined independent of their implementation, allowing us to focus on the use of the new data type instead of how it’s implemented. It is a type or class object which has its own behavior and properties.

7. Abstract data types can be viewed like black boxes as illustrated below

8. It is just a class defined in a standalone manner. The class has definitions of all the properties and functionalities defined in it. Whenever the a data structure is required, the ADT file can be imported and objects of that class can be created and used directly. Abstraction means just to show the users what they want and hide the unwanted technical details.

9. There are several advantages of working with abstract data types and focusing on the “what” instead of the “how .” We can focus on solving the problem at hand instead of getting bogged down in the implementation details . We can reduce logical errors that can occur from accidental misuse of storage structures and data types by preventing direct access to the implementation. The implementation of the abstract data type can be changed without having to modify the program code that uses the ADT . It’s easier to manage and divide larger programs into smaller modules, allowing different members of a team to work on the separate modules.

10. Algorithmic Complexity Algorithmic complexity is a very important topic in computer science. Knowing the complexity of algorithms allows you to answer questions such as How long will a program run on an input? How much space will it take? Is the problem solvable? These are important bases of comparison between different algorithms. An understanding of algorithmic complexity provides programmers with insight into the efficiency of their code . Complexity is also important to several theoretical areas in computer science , including algorithms, data structures, and complexity theory

11. COMPLEXITY Any algorithm should have a way to measure it. The standardized way of comparing algorithms is complexity . All algorithms will have two complexities:- a. Time complexity- is the measure of running time of an algorithm. b. Space complexity – is the measure of total memory used by an algorithm.

12. Average and Worst case Analysis Worst-case complexity: The worst case complexity is the complexity of an algorithm when the input is the worst possible with respect to complexity. Average complexity: The average complexity is the complexity of an algorithm that is averaged over all possible inputs ( assuming a uniform distribution over the inputs).

13. Why Worst Case Analysis? Worst case running time : It is the longest running time for any input of size n. We usually concentrate on finding only the worst-case running time, that is, the longest running time for any input of size n, because of the following reasons: The worst-case running time of an algorithm gives an upper bound on the running time for any input. Knowing it provides a guarantee that the algorithm will never take any longer. For some algorithms, the worst case occurs fairly often. For example, in searching a database for a particular piece of information, the searching algorithm’s worst case will often occur when the information is not present in the database. The “average case” is often roughly as bad as the worst case.

14. Asymptotic Analysis Goal : to simplify the analysis of running time by getting rid of “details” which may be affected by specific implementation and hardware like “rounding” : 1,000,001 = 1,000,000 Capturing the essence : how the running time of an algorithm increases with the size of the input in the limit . Asymptotically more efficient algorithms are best for all but small inputs.

15. Time complexity Running time may vary from one processor to another, based on their processing speed and memory. Based on the internal resources availability , the running time of an algorithm may differ. To overcome these difficulties, asymptotic notations were introduced. Time complexity gives the total runtime of an algorithm. Thus when a solution is designed, every module must be highly optimized for time complexity, in order to prevent wastage of computer resources.

16. The time complexity is the amount of time required by an algorithm to execute. It is measured in terms of number of operations rather than computer time; because computer time is dependent o n the hardware , processor, etc .. Every single step of execution in a program will consume one unit time. For universal standards, this unit is not assigned any metric and computation of all the steps is done at this basic time unit level. Some general order that we may consider O(c ) < O(log n ) < O(n) < O(n log n) < O(nc) <O(cn ) < O(n!) <O(nn) , Where c is some constant.

17. Space complexity The space complexity of an algorithm is the amount of memory it needs to run to completion. Space complexity can be defined as : Amount of computer memory required during the program execution, as the function of input size. The difference between space complexity and time complexity is that the spacecan be reused.