Basics of Data Structures and Algorithms
Data Structure:
Data Structure is a particular way of storing and organizing data in a computer. So, that it can be used efficiently. We can also say in the way of data structure is a special format for organizing and storing data. General data structure types include arrays, files, linked list, stacks, queues, trees, graphs and so on.
Data Structure is a particular way of storing and organizing data in a computer. So, that it can be used efficiently. We can also say in the way of data structure is a special format for organizing and storing data. General data structure types include arrays, files, linked list, stacks, queues, trees, graphs and so on.
Depending on the organization of the elements, data structures are classified into two types.
- Linear Data Structures: Elements are accessed in a sequential order. But, it not compulsory to store all elements in sequentially. Ex: Linked List, stacks and Queues.
- Non-Linear Data Structures: Elements of this data structures are sorted/accessed in a non-linear order. Ex: Trees and Graphs.
Algorithms:
The formal definition of an algorithm is the step-by-step instructions to solve a given problem. Let us consider the problem of preparing an omelet. For preparing omelet, general steps we follow are:
The formal definition of an algorithm is the step-by-step instructions to solve a given problem. Let us consider the problem of preparing an omelet. For preparing omelet, general steps we follow are:
- Get the frying pan
- Get the oil
a. Do we have oil?
i. If yes, put it in the pan
ii. If no, do we want to buy oil?
1. If yes, then go out and buy.
2. If no, we can terminate.
i. If yes, put it in the pan
ii. If no, do we want to buy oil?
1. If yes, then go out and buy.
2. If no, we can terminate.
- Turn on the stove, etc…
What we are doing is, for a given problem (preparing an omelet), giving step-by-step procedure for solving it.
Why analysis of Algorithm?
To go from city ‘A’ to city ‘B’, there can be many ways of accomplishing this: by flight, by bus, by train and also by bicycle. Depending on the availability and convenience we choose the one that suits us. Similarly in computer science multiple algorithms are available solving the same problem.
To go from city ‘A’ to city ‘B’, there can be many ways of accomplishing this: by flight, by bus, by train and also by bicycle. Depending on the availability and convenience we choose the one that suits us. Similarly in computer science multiple algorithms are available solving the same problem.
Ex: sorting problem has many algorithms like insertion sort, quick sort, selection sort and many more. Algorithm analysis helps us determining which of them is efficient in terms of time and space consumed.
Goal of analysis of Algorithms:
The goal of analysis of algorithms is to compare algorithms mainly in terms of running time but also in terms of other factors. Ex: memory, developers effort, etc..
The goal of analysis of algorithms is to compare algorithms mainly in terms of running time but also in terms of other factors. Ex: memory, developers effort, etc..
What is Running Time Analysis?
It is the process of determining how processing time increases as the size of the problem (input size) increases. Input size is the number of elements in the input and depending on the problem type the input may be of different types. The following are the common types of inputs.
It is the process of determining how processing time increases as the size of the problem (input size) increases. Input size is the number of elements in the input and depending on the problem type the input may be of different types. The following are the common types of inputs.
- Size of an Array
- Polynomial degree
- Number of elements in a matrix
- Number of bits in binary representation of the input
- Vertices and edges in a graph
How to compare Algorithms?
To compare algorithms, let us define few objective measures.
Execution Times? Not a good measure as execution times are specific to a particular computer.
Number of statements executed? Not a good measure, since the number of statements varies with the programming language as well as the style of the individual programmer.
Ideal Solution? Let us assume that we expressed running time of given algorithm as a function of the input size n(i.e. f(n)) and compare these different functions corresponding to running times. This kind of comparison is independent of machine time, programming style, etc.
To compare algorithms, let us define few objective measures.
Execution Times? Not a good measure as execution times are specific to a particular computer.
Number of statements executed? Not a good measure, since the number of statements varies with the programming language as well as the style of the individual programmer.
Ideal Solution? Let us assume that we expressed running time of given algorithm as a function of the input size n(i.e. f(n)) and compare these different functions corresponding to running times. This kind of comparison is independent of machine time, programming style, etc.