What makes one algorithm better than another?

There are two main aspects which make an algorithm better than another. The first one I would like to discuss is the measure of how efficient an algorithm is in terms of the time the algorithm takes to complete its calculations and come to a result (an end).

Consider the examples as outlined by Brookshear (2009) of a binary search and a sequential search for a specific item in an ordered list. While the sequential search runs through a list one by one until it finds an entry, on average this search will search through at least half of the list – if the list is very large this may add up to quite a sufficient amount of time per search. A binary search divides a list into two, looks at the middle entry and calculates whether the result is in the first or last half of the resultant lists, then further breaks the respective half in half again, and repeats this process until it finds the item it is looking for. One can plainly see that the binary search method will access a record far less times on average than the sequential search.

Another aspect of measurement is the physical space the algorithm consumes when performing its calculations/operations. A very simple way of explaining this is the one of sorting a list alphabetically. The two methods are firstly the bubble sort versus secondly creating a new list in the correct order. In the bubble sort the method is to sort the list in the form of looking at it in small pieces and sorting them by shuffling around the entries until the entire list is sorted. This way we only occupy the memory/space of the original list. In the method of sorting into a new list, the memory occupied by the original list is used and another entire list is created from the same entries sorted into the correct order. The latter occupies double the amount of memory than the former.

References

Brookshear, J.G (2009) Computer Science: An Overview. 10th ed. China: Pearson Education Asia Ltd.

 

What are good problem solving techniques for developing algorithms

From my personal experience I often use past experiences to aid me in the problem solving process. I find that experience is one of the most valuable tools in the problem solving process. At the same time one should not be confined to past experiences as new methods of problem solving are always being discovered, discovering and developing new ways of doing things is, in fact, one of the main points of the IT industry.

Another method of problem solving I use is researching similar problems using the Internet. The Internet is a fantastic resource for finding users with similar problems or who have already solved similar algorithms to the ones I am trying to solve. If the problem I am trying to solve is proving difficult to find then, depending on the size of the algorithm I am trying to develop, it is still possible to research or have experience with sub-sets of the algorithm, which is a good way to get your ‘foot in the door’ as described by Brookshear (2009, p.218).

Perhaps too obvious to mention but I feel it is worth mentioning, all of the above constitutes to the method of trial and error. It is common that you will try a possible solution that does not work and then move to perhaps another few solutions before finding the most suitable, or correct algorithm.

Mentioned by Brookshear (2009, p.216), G. Polya, a mathematician, has developed an outline of the problem solving process which constist of :

  1. Understand the problem.
  2. Devise a plan for solving the problem.
  3. Carry out the plan.
  4. Evaluate the solution for accuracy and for its potential as a tool for solving other problems.

It is important to remember, as also described by Brookshear (2009, p.216) “we should emphasize that these phases are not steps to be followed when trying to solve a problem but rather phases that will be completed sometime during the process”.

Two other methods mentioned by Brookshear (2009, p. 220) are the ‘top-down methodology’ or ‘stepwise refinement’; this is the process of “first breaking the original problem at hands in terms of several subproblems”. The other, opposite method is the ‘bottom-up methodology’ in which we look at solving the problem starting with the specifics and going down to the general.

Another method I sometimes use, as stated by Anders and Simon (1980), is to verbalise the problem at hand, “Within the theoretical framework of human information processing, we discuss different types of processes underlying verbalization and present a model of how subjects, in response to an instruction to think aloud, verbalize information that they are attending to in short-term memory (STM). Verbalizing information is shown to affect cognitive processes only if the instructions require verbalization of information that would not otherwise be attended to”. While this study is referring to perhaps a different question answer scenario than the one we are discussing, I do believe it is relevant and affective to sometimes speak aloud when trying to solve a problem.

References

Brookshear, J.G (2009) Computer Science: An Overview. 10th ed. China: Pearson Education Asia Ltd.

Ericsson, A. K. & Simon, A. H. (1980) ‘Verbal Reports as Data’, Psychological Review, 87 (3), pp.215-251, PsycNET [Online]. Available from: http://psycnet.apa.org.ezproxy.liv.ac.uk/doi/10.1037/0033-295X.87.3.215 (Accessed: 3 October 2010).