Algorithm description in data structures

Slides describing algorithm and pseudo code in data structures

1. What is an Algorithm? A n algorithm is any well-defined computational procedure that takes some value, or set of values , as input and produces some value, or set of values , as output . An algorithm is thus a sequence of computational steps that transform the input into the output.

2. algorithm An algorithm: is an outline of the steps that a program or any computational procedure has to take. A program: on the other hand is an implementation of an algorithm and it could be in any programming language. Data structure: is the way we need to organize the data, so that it can be used effectively by the program.

3. What is an Algorithm? We can also view an algorithm as a tool for solving a well-specified computational problem . The statement of the problem specifies in general terms the desired input/output relationship. The algorithm describes a specific computational procedure for achieving that input/output relationship.

4. algorithm What is an algorithmic problem? specifications of an input ? specification of output as function of input Input: 67, 34, 12, 5, 7, 67, 1 Output: 1, 5, 7, 12, 34, 67, 67

5. algorithm What is an algorithmic problem? specifications of an input Algorithm specification of output as function of input An algorithm is essentially, describing the actions that one should take on the input instance to get the specified output.

6. What is an Algorithm? For example, we might need to sort a sequence of numbers into non-decreasing order. Here is how we formally define the sorting problem . Input: A sequence of n numbers <a 1 , a 2, . . ., a n >. Output: A permutation (reordering) <a’ 1 , a’ 2, . . ., a’ n > o f the input sequence such that a’ 1 ≤ a’ 2 ≤ . . . ≤ a’ n .

7. What is an Algorithm? For example, we might need to sort a sequence of numbers into non-decreasing order. Here is how we formally define the sorting problem . Input: A sequence of n numbers <a 1 , a 2, . . ., a n >. Output: A permutation (reordering) <a’ 1 , a’ 2, . . ., a’ n > o f the input sequence such that a’ 1 ≤ a’ 2 ≤ . . . ≤ a’ n .

8. What is an Algorithm? For example, given the input sequence <31; 41; 59; 26; 41; 58>, a sorting algorithm returns as output the sequence <26; 31; 41; 41; 58; 59>. Such an input sequence is called an instance of the sorting problem. In general, an instance of a problem consists of the input (satisfying whatever constraints are imposed in the problem statement) needed to compute a solution to the problem.

9. algorithm Characteristics of an Algorithm An algorithm should have the following characteristics − Unambiguous − Algorithm should be clear and unambiguous. Each of its steps (or phases), and their inputs/outputs should be clear and must lead to only one meaning. Input − An algorithm should have 0 or more well-defined inputs. Output − An algorithm should have 1 or more well-defined outputs, and should match the desired output. Finiteness − Algorithms must terminate after a finite number of steps. Feasibility − Should be feasible with the available resources. Independent − An algorithm should have step-by-step directions, which should be independent of any programming code

10. What is an Algorithm? An algorithm is said to be correct if, for every input instance, it halts with the correct output. We say that a correct algorithm solves the given computational problem. An incorrect algorithm might not halt at all on some input instances, or it might halt with an incorrect answer. Contrary to what you might expect, incorrect algorithms can sometimes be useful, if we can control their error rate.

11. What is an Algorithm? There are two main criteria for judging the merits of algorithms: correctness (does the algorithm give solution to the problem in a finite number of steps?) and efficiency (how much resources (in terms of memory and time) does it take to execute the).

12. Why the Analysis of Algorithms? In computer science, multiple algorithms are available for solving the same problem (for example, a sorting problem has many algorithms, like insertion sort, selection sort, quick sort and many more). Algorithm analysis helps us to determine which algorithm is most efficient in terms of time and space consumed .

13. Goal of the Analysis of Algorithms The goal of the analysis of algorithms is to compare algorithms (or solutions) mainly in terms of running time but also in terms of other factors (e.g., memory, developer effort, etc.)

14. How to Compare Algorithms 1. Execution times? Not a good measure as execution times are specific to a particular computer. This analysis also known as empirical or posteriori . 2. 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. 3. Ideal solution? Let us assume that we express the running time of a 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. This anlysis also known as theoretical or apriori .

15. How to Compare Algorithms 1. Empirical or posteriori. 2. Theoretical or apriori analysis.

16. How does one measure the running time of an algorithm? Let us look at the empirical ( experimental) study. Write a program that implements the algorithm. Run the program with varying data sets in which some are smaller, some are of larger data sets, some would be of some kinds and some would be of different kinds of varying composition. Use a method (like System.currentTimeMillis ()) to get an accurate measure of the actual running time.

17. How does one measure the running time of an algorithm? This has certain limitations. First you have to implement the algorithm in which we will be able to determine how good your algorithm is. Implementing it is a huge overhead , where you have to spend considerable amount of time. Experiments can be done only on a limited set of inputs . You can run your experiment on a small set of instances and that might not really indicate the time that your algorithm is taking for other inputs, which you have not considered in your experiment. It is machine dependent.

18. How does one measure the running time of an algorithm? Theoretical or apriori analysis. Let us assume that we express the running time of a given algorithm as a function of the input size n (i.e., f ( n )) and compare these different functions corresponding to running times. That is, this methodology aims at associating with each algorithm a function f(n) that characterizes the running time of the algorithm in terms of the input size n. This kind of comparison is independent of machine time, programming style, etc.

19. 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.

20. What is Running Time Analysis? Typical functions that will be encountered include n and n 2 . For example, we will write statements of the type: "Algorithm A runs in time proportional to n," meaning that if we were to perform experiments, we would find that the actual running time of algorithm A on any input of size n never exceeds cn , where c is a constant that depends on the hardware and software environment used in the experiment.

21. What is Running Time Analysis? Given two algorithms A and B, where A runs in time proportional to n and B runs intime proportional to n 2 , Then, we will prefer A to B , since the function n grows at a smaller rate than the function n 2 .

22. What is Rate of Growth? The rate at which the running time increases as a function of input is called rate of growth.

23. Types of Analysis To analyze the given algorithm, we need to know with which inputs the algorithm takes less time (performing wel1) and with which inputs the algorithm takes a long time. We have already seen that an algorithm can be represented in the form of an expression. That means we represent the algorithm with multiple expressions: one for the case where it takes less time and another for the case where it takes more time .

24. Types of Analysis In general, the first case is called the best case and the second case is called the worst case for the algorithm. • Worst case ○ Defines the input for which the algorithm takes a long time (slowest time to complete). ○ Input is the one for which the algorithm runs the slowest.

25. Types of Analysis In general, the first case is called the best case and the second case is called the worst case for the algorithm. • Best case Defines the input for which the algorithm takes the least time (fastest time to complete). Input is the one for which the algorithm runs the fastest.