Algorithms For Dummies

 

»

Help you understand the limits of the solution

A common scenario that illustrates a solution and counterexample is the state-

ment  that  all  prime  numbers  are  odd.  (Prime numbers  are  integers  that  can  be 

divided  only  by  themselves  and  1  to  produce  an  integer  result.)  Of  course, 

the   number  2  is  prime,  but  it’s  also  even,  which  makes  the  original  statement 

false. Someone making the statement could then qualify it by saying that all prime 

numbers are odd except 2. The partial solution to the problem of finding all the 

prime  numbers  is  that  you  need  to  find  odd  numbers,  except  in  the  case  of  2, 

which is even. In this second case, disproving the solution is no longer possible, 

but adding to the original statement provides a boundary.

By  casting  doubt  on  the  original  assertion,  you  can  also  consider  situations  in 

which the hypothesis, all prime numbers except 2 are odd, may not hold true. For 

example,  1  is  an  odd  number  but  isn’t  considered  prime  (see  the  discussion  at 

https://primes.utm.edu/notes/faq/one.html

 for details). So now the original 

statement has two boundaries, and you must restate it as follows: Prime numbers 

are greater than 1 and usually odd, except for 2, which is even. The boundaries for 

prime numbers are better defined by locating and considering counterexamples. 

Just in case you’re wondering, 0 is also not considered a prime number, for the 

reasons  discussed  at 

http://math.stackexchange.com/questions/539174/

is-zero-a-prime-number

.

As the complexity of a problem grows, the potential for finding counterexamples 

grows as well. An essential rule to consider is that, as with reliability, having more 

failure points means greater potential for a failure to occur. Thinking of algorithms 

in  this  way  is  important.  Ensembles  of  simple  algorithms  can  produce  better 

results with fewer potential counterexamples than a single complex algorithm.