Lesson 1 - Introduction to Algorithms.pdf

Lesson 1 Introduction to Algorithms Contents 1.1. What an Algorithm is, p1 1.2. Features of an Algorithm, p2 1.3. Designing Algorithms, p3 1.4. Importance of Analyzing Algorithms, p4 Summary, p5 Learning Outcomes, p5 1.1. What an Algorithm is? An algorithm is a method, or a process followed to so...

Lesson 1 Introduction to Algorithms Contents 1.1. What an Algorithm is, p1 1.2. Features of an Algorithm, p2 1.3. Designing Algorithms, p3 1.4. Importance of Analyzing Algorithms, p4 Summary, p5 Learning Outcomes, p5 1.1. What an Algorithm is? An algorithm is a method, or a process followed to solve a problem. If the problem is viewed as a function, then an algorithm is an implementation for the function that transforms an input to the corresponding output. We need algorithms because of the following reasons: Scalability: It helps us to understand scalability. When we have a big real-world problem, we need to scale it down into small-small steps to easily analyze the problem. Performance: The real world is not easily broken down into smaller steps. If the problem, can be easily broken into smaller steps means that the problem is feasible. In our day-to-day life we come across many algorithms. Friends give directions for finding the way to their homes. Recipes in cookbooks are often cited as examples of algorithms. Most of the household products are labelled with simple set of instructions for their use that resemble algorithms. Algorithms are everywhere in computing, and they help us do lots of important things Practically. Here are some examples: The Internet lets us find lots of information really fast. Websites use special algorithms to handle all the data they have and help us find what we're looking for. When we buy things online, like with electronic commerce, algorithms help keep our personal information safe. They use numerical algorithms and number theory to encrypt things like credit card numbers, passwords, and bank statements. So, nobody else can see them. 1  Scientists use algorithms to study human DNA and figure out what genes we have and what makes up our DNA. They need smart algorithms to do things like store all this information and analyze it. Usually, there are lots of ways to solve a problem using different algorithms. Each algorithm is like a recipe that solves just one specific problem. A good programmer plans out the steps of the algorithm first, then writes it down. He looks at it carefully, making changes to make it better until it's really good. He makes sure it works quickly and doesn't use up too much space in the computer's memory. 1.2. Features of an Algorithm The previous section discusses that an algorithm is a sequence of well understood steps that one takes to do a task. To make good algorithms, it's important to understand the features and strengths of an algorithm. By definition, an algorithm must possess some unique qualities. Something can be called an algorithm to solve a particular problem if it has all of these properties. 1. It must be correct. In other words, it must compute the desired function, converting each input to the correct output. 2. An algorithm is constructed with a series of concrete steps. That is actions described in each step must be completely understood and should be able to do by the person or the machine that perform the algorithm. Further, these steps must be performable in a finite amount of time. 3. There can be no ambiguity as to which step will be taken next. Often it is the next step of the algorithm description. Thus, in a selection statement it is like if else although there is a choice in selecting the next step to follow but the selection process is unambiguous. 4. It should consist of a finite number of steps. That is at any point the algorithm should not enter an infinite loop. The notions such as while do, or and repeat until loops allows repetitions their number of steps actually performed are controlled by the input. 5. Algorithm must terminate, that is it should not go into an infinite loop. Next, we'll see how these qualities show up in algorithms with some examples. Example 1.1 x: = y + z This instruction has a clear meaning, values of variables y and z are added and assigned to x and it can be executed in a finite amount of effort and time. Therefore, this statement can be considered as a concrete step of an algorithm. 2 Example 1.2 N=1 Print N N=N+1 GO TO STEP 2 Although the above segment of instructions has a finite sequence and a clear meaning but do not finish in a finite amount of time due to absence of a terminating condition. Therefore, this is not an algorithm. Therefore, we can informally say that an 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 to the output. The process of transforming the input to the output can be designed in several ways. 1.3. Designing Algorithms Designing algorithms is a challenging task that requires a lot of time and effort. Therefore, it is important to design them to work efficiently. Thus, algorithms must undergo analysis before implementation. Various techniques, like divide and conquer method, dynamic programming, greedy method, linear programming and reduction, are used to design algorithms. Each method encompasses various algorithm types, with distinct approaches for design. In the following sections, we will briefly examine each of these methods. Divide and conquer: Break a big problem into smaller ones, solve them, then put the answers together. Dynamic programming: Find solutions to smaller parts of a problem and build up the whole solution. Greedy method: Make the best choice at each step without thinking too far ahead. Linear programming: Solve problems using a specific set of rules and finding the best outcome. Reduction: Transform a hard problem into an easier one, solve that, and then go back to the original problem. Each of these methods has its own way of doing things, and we'll look at each of them in more detail. Algorithms can be written in different ways, like in natural languages, diagrams, or programming languages. We often use diagrams or special code-like languages to write them down clearly. 3 1.4. Importance of Analyzing Algorithms Basically, there can be many approaches to solve a single problem. This is quite natural because, if given a problem to two different persons under same conditions though they will come to the same conclusion most probably the sequence of steps followed may not be the same. This is mainly due to the person’s perception of the problem as well as the already existing knowledge about the problem domain. Therefore, each of these variations yields different algorithms to solve the same problem. Hence selecting the desired algorithm from many possible algorithms will be a quite a challenge. In addition, there will be algorithms to solve practical problems such as finding shortest path in a road network. In such situations the desired algorithm has to be found by careful analysis of the problem by comparing the efficiency of algorithms. Usually there are two types of algorithms with contradicting goals. 1. Algorithms those are easy to understand code and debug. 2. Algorithms that make efficient use of computer’s resources especially one that runs as fast as possible. Therefore, when developing algorithms we have to be sure what approach we consider. For this, it is necessary to consider the aspects that are related to selecting/designing an algorithm. Some of the aspects are: 1. Time needed to design the algorithm. 2. The amount of time needed to execute the algorithm successfully, i.e., running time of the algorithm. 3. The amount of space required. At the development stage one of the key factors in the economic aspect is the programmer’s time. To utilize this time with efficiency it is necessary to identify the type of the algorithm to be developed with respect to its goal as described earlier. If an algorithm is to be used only once, then the cost of the programmer’s time is more important than the cost of the running time of the program. In such a situation it is desirable to choose a program, which consumes lesser amount of time for writing it. In a situation where an algorithm is to be used repeatedly, then it is appropriate to select an algorithm which runs faster and requires less computer space because it is more economical. We often come across situations where we must select one algorithm out of two or more with respect to efficiency for implementation. How do we handle such a situation? One method is to implement all the algorithms under the same conditions and measure how much of resources are used by each algorithm. This approach is often an unsatisfactory method, mainly because it is a waste of time resources. Because when the requirement is to keep one, you test many. The other method is to use the technique called algorithm analysis or performance analysis of algorithms. Algorithm analysis measures the efficiency of an algorithm or its implementation as a program, as the input size becomes larger. It is actually an estimating 4 technique, and it has proved useful in the process of determining whether a particular algorithm is worth considering for implementation. The next lesson is devoted to analyzing algorithms. Summary This lesson carried an extensive discussion about algorithms by explaining what an algorithm is along with features, designing methods and importance of comparing algorithms based on efficiency of an algorithm. An algorithm is described as the set of instructions that has to be followed in order to convert the inputs into outputs. There are many ways to design an algorithm as well as there can be more than one algorithm for a given problem. Therefore, it is of great importance to identify the most efficient algorithm. The efficiency can be measured in terms of space complexity or time complexity of the algorithm. Yet, the time complexity in terms of running time of an algorithm is used more often than the space complexity. Learning outcomes Having studied this lesson, you would be able to: Explain what an algorithm is. Describe different ways to design algorithms. 5