Created on: July 9, 2009

Website Address: https://www.curriki.org/oer/Introduction-to-Algorithms

IN COLLECTION

An algorithm (pronounced AL-go-rith-um) is a procedure or formula for solving a problem. The word derives from the name of the great mathematician, Mohammed ibn-Musa al-Khwarizmi, who was part of the royal court in Baghdad and who lived from about 780 to 850. Al-Khwarizmi's work is the likely source for the word algebra as well.

WHAT IS AN ALGORITHM?

In computers and related subjects (like mathematics, science, programming methodology etc), algorithm is defined as a sequence of instructions, an explicit, step-by-step procedure for solving a problem, often used for calculation and data processing. It is formally a type of effective method in which a list of well-defined instructions for completing a task, when given an initial state, proceed through a well-defined series of successive states, eventually terminating in an end-state completing the desired work.

WHAT IS THE USE OF ALGORITHMS IN COMPUTERS?

To make a computer do anything, we have to write a computer program. To write a computer program, we have to tell the computer, step by step, what we want it to do. The computer then "executes" the program, following each step mechanically, to accomplish the desired goal.

When we are telling the computer what to do, we also get to choose how it's going to do it. That's where computer Algorithms come in to picture. The algorithm is the basic technique used to get the job/work done. Let's follow an example to get an understanding of the Algorithm concept.

Suppose you have to reach your home from your school or college.

Then you have different options to come back like you can come back by bus or by a taxi.

The Procedure wise detail for each option is provided below:**The taxi algorithm:1. Go to the taxi stand.2. Get in a taxi.3. Guide the driver to your home.The bus algorithm:1. Walk to the bus stand.2. Board the bus.3. Get off at the closest bus stop to your home.4. Walk to your home.**

Now each algorithm also has a different cost and a different travel time. Taking a taxi, for example, is probably the fastest way, but also the most expensive. Taking the bus is definitely less expensive, but a whole lot slower. You choose the algorithm based on the circumstances.

In computer programming, there are often many different ways to accomplish any given task.

Each algorithm has its distinct advantages and disadvantages in different situations. Sorting is one place where a lot of research has been done already, because computers spend a lot of time in sorting different lists. Here are five different algorithms that are used in sorting:**• Insertion sort• Selection sort• Bucket sort• Merge sort• Quick sort**

In the coming lessons we will be discussing all these different types of sorting also.

Now if we have a million integer values between 1 and 10 and we need to sort them, the bin sort is the right algorithm to use. If we have a million book titles, the quick sort might be the best algorithm. By knowing the strengths and weaknesses of the different algorithms, we can pick the best one for the task at hand.

WHAT KIND OF PROBLEMS CAN BE SOLVED BY ALGORITHMS?

Sorting is by no means the only computational problem for which algorithms have been developed. Practical applications of algorithms are ubiquitous and include the following examples:

• The Human Genome Project has the goals of identifying all the 100,000 genes in human DNA, determining the sequences of the 3 billion chemical base pairs that make up human DNA, storing this information in databases, and developing tools for data analysis. Each of these steps requires sophisticated algorithms.

• The Internet enables people all around the world to quickly access and retrieve large amounts of information. In order to do so, clever algorithms are employed to manage and manipulate this large volume of data. Examples of problems which must be solved include finding good routes on which the data will travel , and using a search engine to quickly find pages on which particular information resides .

• In manufacturing and other commercial settings, it is often important to allocate scarce resources in the most beneficial way. An oil company may wish to know where to place its wells in order to maximize its expected profit. A candidate for the presidency of the United States may want to determine where to spend money buying campaign advertising in order to maximize the chances of winning an election. An Internet service provider may wish to determine where to place additional resources in order to serve its customers more effectively. All of these are examples of problems that can be solved using algorithms.

• We are given a road map on which the distance between each pair of adjacent intersections is marked, and our goal is to determine the shortest route from one intersection to another. The number of possible routes can be huge, even if we disallow routes that cross over themselves. How do we choose which of all possible routes is the shortest? Here, we model the road map (which is itself a model of the actual roads) as a graph and we wish to find the shortest path from one vertex to another in the graph.

• We are given an equation ax ? b (mod n), where a, b, and n are integers, and we wish to find all the integers x, modulo n, that satisfy the equation. There may be zero, one, or more than one such solution. We can simply try x = 0, 1, ..., n - 1 in order, but there are more efficient methods.

• We are given n points in the plane, and we wish to find the convex hull of these points. The convex hull is the smallest convex polygon containing the points.

SOME OF THE PROBLEMS FROM THE ABOVE LIST WILL BE SOLVED IN THE COMING LECTURES.

SO FROM NOW ONWARDS WE WILL FIRST LEARN THAT WHAT ARE THE DIFFERENT BASIC APPROACHES TO SOLVE A COMPUTER-RELATED PROBLEM, THEN WE WILL BE DISCUSSING THE DIFFERENT TYPES OF SORTING MECHANISMS WITH THEIR ADVANTAGES AND DISADVANTAGES AND COMPLEXITIES. AFTER THAT WE WILL BE DOING SOME BASIC PROBLEMS THAT CAN BE SOLVED THROUGH THE ABOVE MENTIONED APPROACHES, FINALLY, WE WILL PERFORM SOME ADVANCED PROBLEMS TO DEVELOP THE SKILLS OF PROBLEM SOLVING. ALL OF THIS WILL BE DONE IN THE COMING LESSONS. I HOPE YOU WILL FIND IT USEFUL AND INTERESTING TOO.

BIBLIOGRAPHIC CITATIONS

WEBSITES

1. Wikipedia.org link click here

2. Howstuffworks.com link click here

REFERENCE BOOKS

1. Ellis Horowitz and Sartaj Sahni, *Fundamentals of Computer Algorithms*, Computer Science Press, Maryland, 1978, 626 pages.