Divide And Conquer

The binary search algorithm is perhaps the most advanced of the simple algorithms. It is easy enough to understand both the problem and its overall solution – the details might be a little trickier, but still understandable. Algorithms of a similar type are often aimed at highly technical problems which tend to need a lot of preparation to understand, let alone solve or comprehend the solution.

The general approach used by the binary search is referred to as divide and conquer. The idea is that if you can split a problem that involves N things into two problems involving N/2 things then there is a chance you can solve the problem more efficiently by repeating the process of splitting. Of course, there is no guarantee that this splitting will give you a better algorithm. However, if you can deal with a set of N/2 things faster than you can deal with N things and if putting the solutions back together to give you an overall solution doesn’t take too much extra work then the divide and conquer algorithm is preferable.

In the case of the binary search, it is obvious that searching through N/2 things is faster than searching N things and putting the solution back together doesn’t take any extra time as in this case the solution to N/2 things is the solution to N things – if you have found it you have found it!

Divide and conquer algorithms are usually described as “fast” or “quick” and the best known are the Fast Fourier Transform (FFT) and Quick Sort – both too involved to describe here, but the background to each is interesting.

The story of the FFT is worth recounting. It was invented in 1965 by James Cooley and John Tukey and it is perhaps the most important algorithm of the 20^th century. The Fourier Transform is the technique for breaking down signals – audio, video and more – into their constituent frequencies. Before the FFT such analysis was so slow that it was generally impossible to do the job in real time, i.e. as the audio or video was begin produced. The FFT works by dividing the stream of values into two halves and performing that transformation on both. It repeats the division until it gets down to just two values and then it puts the results back together. It is an archetypal divide and conquer algorithm. The FFT revolutionized signal processing and made possible image and video compression. Overnight things that were impossibly slow became possible without any change to the hardware. Without it we would have a much harder time working with photos and video. You could say that the FFT made You Tube possible.

The QuickSort was invented by Tony Hoare in 1959 and published in 1961. Its practical effects weren’t as revolutionary as the FFT but they were still important. It too is a divide and conquer algorithm, but you can’t just divide a list into two parts and sort each part. The act of putting the two back together to form a single sorted list takes too many operations to be useful. The solution is to divide the list into two parts depending on a selected value – the pivot. The division is such that the portion to the left is less than the pivot and the portion to the right is bigger than the pivot. When the division reaches a single element the list is then sorted. It can be hard to understand QuickSort, but it is essentially the same as binary search where the target item is the pivot, which is used to create two portions of the list, one smaller and one larger. What is amazing is that repeating this gives you a sorted list and that it is faster than other methods. The value of the QuickSort algorithm is as much its status as a clever algorithm as its undeniable practical value.

Not in this extract but in chapter:

• Recursion
• Making A Hash
• Algorithms and Thought

Summary

• Algorithms are what programs implement and to do this you have to make the specification of the algorithm precise enough to allow a non-intelligent agent to follow the instructions.

• Finding a book in a big library is a good problem to illustrate the idea of implementing an algorithm because it can be solved using simple and more advanced approaches.

• The simplest is linear search which works with a library of books in no particular order.

• You can also try picking books at random, but this isn’t a good algorithm.

• If the librarian has gone to the extra effort of putting the books into order, then you can use the binary search algorithm which is much more efficient.

• Specifying the binary search algorithm in detail is a very good example of how algorithms are converted into programs.

• The binary search algorithm is an example of a general class of divide and conquer algorithms, the most important of these being the Fast Fourier Transform and Quicksort.

• Recursion is an alternative to iteration and it is particularly applicable to the binary search problem.

• The final algorithm for the book search problem is hashing. This is very efficient and doesn’t require the books to be sorted into order. If correctly implemented it can find a book in no more than a few attempts no matter how many books are involved.

The Trick Of The Mind - Programming & ComputationalThought

Buy Now From Amazon

Chapter List

1. The Trick Of The Mind

2. Little Languages
      Extract: Little Languages Arithmetic

3. Big Languages Are Turing Complete

4. The Strange Incident of The Goto Considered Harmful
      Extract: The Goto Considered Harmful

5. On Being Variable  

6. Representation

7. The Loop Zoo
      Extract The Loop Zoo
      Extract Advanced Loops
   

8. Modules, Subroutines, Procedures and Functions
      Extract Modular Programming

9. Top-Down Programming 

10. Algorithms
       Extract: Binary Search 
       Extract: Recursion ***NEW!!

11. The Scientific Method As Debugging 

12. The Object Of It All
       Extract Why Objects 

 <ASIN:1871962722>

<ASIN:B09MDL5J1S>

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info