Modern computers can carry out very complex tasks. Each task consists of well-defined procedures known as algorithms. Learn how computers use algorithms to perform the tasks we expect them to do.
What Is an Algorithm?
Consider how you use a computer in a typical day. For example, you start working on a report, and once you have completed a paragraph, you perform a spell check. You open up a spreadsheet application to do some financial projections to see if you can afford a new car loan. You use a web browser to search online for a kind of car you want to buy.
You may not think about this very consciously, but all of these operations performed by your computer consist of algorithms. An algorithm is a well-defined procedure that allows a computer to solve a problem. Another way to describe an algorithm is a sequence of unambiguous instructions. The use of the term 'unambiguous' indicates that there is no room for subjective interpretation. Every time you ask your computer to carry out the same algorithm, it will do it in exactly the same manner with the exact same result.
Consider the earlier examples again. Spell checking uses algorithms. Financial calculations use algorithms. A search engine uses algorithms. In fact, it is difficult to think of a task performed by your computer that does not use algorithms.
How Do Algorithms Work?
Let's take a closer look at an example.
A very simple example of an algorithm would be to find the largest number in an unsorted list of numbers. If you were given a list of five different numbers, you would have this figured out in no time, no computer needed. Now, how about five million different numbers? Clearly, you are going to need a computer to do this, and a computer needs an algorithm.
Below is what the algorithm could look like. Let's say the input consists of a list of numbers, and this list is called L. The number L1 would be the first number in the list, L2 the second number, etc. And we know the list is not sorted - otherwise, the answer would be really easy. So, the input to the algorithm is a list of numbers, and the output should be the largest number in the list.
The algorithm would look something like this:
Step 1: Let Largest = L1
This means you start by assuming that the first number is the largest number.
Step 2: For each item in the list:
This means you will go through the list of numbers one by one.
Step 3: If the item > Largest:
If you find a new largest number, move to step four. If not, go back to step two, which means you move on to the next number in the list.
Step 4: Then Largest = the item
This replaces the old largest number with the new largest number you just found. Once this is completed, return to step two until there are no more numbers left in the list.
Step 5: Return Largest
This produces the desired result.
Notice that the algorithm is described as a series of logical steps in a language that is easily understood. For a computer to actually use these instructions, they need to be written in a language that a computer can understand, known as a programming language.
Alternative Approaches and Optimization
There are many different types of algorithms. Search algorithms are used to find an item with specific properties among a collection of items. For example, you may want to know if a particular word occurs in a list of words or not. Searching is closely related to the concept of dictionaries since it is like looking up a word in a dictionary. There are different approaches to searching, each representing a slightly different technical approach to the same problem.
In a sequential or linear search, you start by examining the first item in the list to see if it matches the properties you are looking for. If not, you continue examining each sequential item until a match is found.
Over 79,000 lessons in all major subjects
Get access risk-free for 30 days,
just create an account.
This approach will produce the correct result, but it is not very efficient. For a relatively small list that only needs to be searched once, it may not matter much if the search takes a little longer. However, many computer tasks require not just one, but hundreds, of algorithms to be run. The datasets can also be very large and may need to be processed repetitively. As a result, processing speed matters.
Alternative algorithms may require less time to find the correct answer. This is known as optimization: the process of finding the most computationally efficient algorithms to solve a particular problem.
In the case of searching, an alternative to sequential search is the binary search. A binary search improves the algorithm by removing as much of the input data as possible without having to examine each item. Let's say you are looking for a particular number in a list of numbers, and the list is already sorted. This presents an opportunity to search faster.
In a binary search, you would jump to the item more or less in the middle of the list. If the number you are looking for is higher, you can drop the left-hand side of the list and continue only with the right-hand side. That reduces the number of items to search through by half in just one step. You can repeat this until you have found the number you are looking for or until the remaining list is very short, and then you can run a sequential search very quickly.
There are many alternative search algorithms, each with their own strengths and weaknesses. A good algorithm is one that produces the correct answer and is computationally efficient. Computer enthusiasts spend much of their time developing better algorithms.
Determining which algorithm is best for a given task is not as easy as it may sound. For example, in the case of sequential and binary search, the binary search is much faster but only if the list of interest is already sorted. Sorting would require another algorithm, which will take quite a bit of time. This may be worth it if the list will be searched many times. However, if you only plan to search an unsorted list once, the sequential search will be faster than first performing a sort and then a binary search.
Tasks performed by computers consist of algorithms. An algorithm is a well-defined procedure that allows a computer to solve a problem. A particular problem can typically be solved by more than one algorithm. Optimization is the process of finding the most efficient algorithm for a given task. A good algorithm is one that produces the correct answer and is computationally efficient.
After this lesson, you should be able to:
Define algorithm and explain how an algorithm works
Describe the process of optimization
Identify some of the different types of algorithms
A number x, such that f(x) = 0, is a root or a zero of the function. Solving an equation, f(x) = g(x), is the same as finding the roots of the function h(x) = f(x) - g(x).
The algorithm for the approximate zero of f(x) is xn+1 = xn - f(xn ) / f'( xn ) .
Starting with n = 1, you can get x2. Use x2 to get x3, and so on, recursively. The iteration stops when a fixed point (up to the desired precision) is reached, that is when the newly computed value is sufficiently close to the preceding ones. In the limit, as n goes to infinity, an infinite number of iterations, xn, approaches the zero of the function. This is a recursive formula that needs to be started with a reasonable initial guess. The function also needs to have a non-zero derivative. This method is called Newton's method or the Newton - Raphson method of root finding. Replacing the derivative in Newton's method with a finite difference, we get the secant method. This method does not require the computation (nor the existence) of a derivative, but the price is slower convergence.
Find the root of the equation cos(x) = x . Suggested initial guess of x = 1.
Solve for the zero of f(x) = cos(x) - x
The recursive algorithm for the approximate zero of f(x) is xn+1 = xn - f(xn ) / f'( xn ) .
The derivative is f'(x) = - sin(x) - 1
The initial guess is x = 1
Plug into the formula to find x2 = 0.75036387
Plug that into the formula to find x3 = 0.73911289
Plug that into the formula to find x4 = 0.73908513
Plug that into the formula to find x5 = 0.75908513
Since the last two approximants agree to six decimal places, we conclude that the root of the equation (correct to six decimal places) is 0.75908513
Register to view this lesson
Are you a student or a teacher?
Unlock Your Education
See for yourself why 30 million people use Study.com
Did you know… We have over 200 college
courses that prepare you to earn
credit by exam that is accepted by over 1,500 colleges and universities. You can test out of the
first two years of college and save thousands off your degree. Anyone can earn
credit-by-exam regardless of age or education level.