Understanding algorithms and problem-solving

René Descartes (1596-1650), the French philosopher and mathematician, is renowned for his theory of mind-body dualism. He proposed that the mind and body are two fundamentally distinct substances: the mind as a non-extended, thinking entity and the body as an extended, non-thinking entity. Descartes believed in the interaction between these substances while maintaining their separateness and independent existence. This dualistic view emphasizes the separation of the mental (mind) and physical (body) aspects, positing that they differ in nature. His theory has had a significant influence on philosophical discussions about consciousness and the relationship between mind and body.

But why are we starting our discussion about algorithms with Descartes’ theory of dualism, despite serious criticisms of it from philosophers? The answer lies in the model’s ability to aid our understanding of the essence of algorithms and their uniqueness among all human inventions.

The historical narrative of computers, primarily seen as devices for automating problem-solving through mathematical representations, starts with a distinct separation between hardware and software. Hardware is the tangible, physical component that executes software code, producing the desired results. Conversely, software is the systematic solution articulated through a formal language known as a computer program, ranging from high-level languages such as Python and C++ to low-level ones such as assembly language and machine code.

However, hardware and software are fundamentally different, a distinction particularly notable in computer systems. The primary difference lies in the disciplines that govern each. Computer hardware is governed by the laws of physics, dictating how the physical components operate and interact. In contrast, computer software operates within the domain of mathematics, which dictates the logic, algorithms, and functions that software can perform. This dichotomy sets computer systems apart from other human-made technologies. For example, a car is governed entirely by physical laws at both microscopic and macroscopic levels. A significant distinction between hardware and software is that hardware is mortal. It is prone to decay, defects, and expiration. In contrast, software is immortal, not subject to depreciation, aging, defects, or expiration. This concept mirrors Descartes’ theory of dualism.

Software, at its core, embodies an abstract concept known as an algorithm. An algorithm represents an abstract set of rules or procedures, which can be realized and expressed in many ways across various programming languages. Despite this diversity in representation, all these different implementations of the same algorithm are designed to produce a singular, consistent output. This characteristic of algorithms, being abstract yet versatile in their implementation, is what makes them a fundamental element in software development and design. In the real world, the concepts most akin to algorithms are food recipes and musical notes. Both represent step-by-step implementations of a plan to create food or music.

The indication of a good recipe, aside from yielding delicious food, is in its expression in a quantitative and abstract form, allowing any cook, regardless of experience level, to execute it. However, this is often not entirely feasible, as recipes are typically written in natural language, making them prone to various interpretations. Another desired trait of a good recipe is its independence from specific kitchen equipment, although this too is not always realistic. Recipes, much like algorithms, aim for a level of universality in their application, but the nuances of language and specific contexts can affect their reproducibility and outcomes.

The situation with musical notes is slightly more favorable. Since these notes resemble formal language, they offer a clearer, more standardized method of instruction. However, the actual music produced is still subject to the interpretation of the player, the characteristics of the instruments, and a myriad of acoustic factors. While musical notes provide a more precise guide compared to the natural language of recipes, the variability in performance and environmental conditions means that the outcome can still vary significantly. This underscores the challenge of translating abstract, formalized instructions into consistent real-world results, much like the execution of algorithms in different computing environments.

These two examples help us infer key properties of algorithms:

• Programmer independence: Ideally, the final product of an algorithm should be largely independent of who implements it. This means that regardless of the programmer, the algorithm should consistently produce the same correct result, and the computational cost or resource usage should be comparably similar across different implementations.
• Hardware independence: An effective algorithm should, as much as possible, be independent of the hardware on which it runs. It should be capable of producing consistent results across various hardware platforms without significant modifications or dependence on specific hardware features.
• Abstraction and clarity: Algorithms should be abstract and unambiguous, leaving no room for interpretation. This clarity ensures that the algorithm can be understood and implemented consistently, regardless of the programmer’s subjective understanding or approach.
• Quantifiable correctness and cost: The correctness of an algorithm – its ability to produce the intended result – and its cost, in terms of computational resources such as time and memory, must be quantifiable. This allows for the objective assessment and comparison of different algorithms based on their efficiency and effectiveness.

Algorithms are defined as step-by-step, procedural, and often iterative methods for solving problems. It is crucial to understand, however, that they are designed to address only computable problems. This means that for a problem to be solvable by an algorithm, it must be one that can be resolved through a sequence of logical and mathematical steps. In essence, a computable problem is one that can be systematically worked through using algorithms, which provide a clear and organized approach to finding a solution.

One classic example of a non-computable problem is the halting problem. Posed by Alan Turing, this problem asks whether it is possible to create an algorithm that can determine whether any given program and its input will halt (stop running) or continue to run indefinitely. Turing proved that no such algorithm can exist; it is impossible for a general algorithm to predict the behavior of all possible program-input combinations and determine whether they will halt. This is because the algorithm would have to account for an infinite number of possible program behaviors, which is not feasible.

A classic example of a computable problem is sorting a list of numbers. For instance, given a list of numbers, such as [3, 1, 4, 1, 5, 9, 2], a sorting algorithm can rearrange these numbers in a specific order, such as ascending: [1, 1, 2, 3, 4, 5, 9]. Sorting problems are computable because they have a well-defined procedure or set of steps that can be followed to achieve the sorted list, and this process will work for any finite list of numbers.

Having established a basic understanding of the types of problems that can be solved using algorithms, we are now ready to explore the major problem-solving approaches employed in algorithm design. However, it is important to address a common misconception first. Some textbooks present heuristics and algorithmic approaches as opposites, but the relationship between them is more complementary than contradictory.

Heuristic methods, as we will discuss in Chapter 10, provide practical, often quicker solutions grounded in experience, intuition, or common-sense rules. Their main advantage lies in their speed and practicality, but this comes with a trade-off: heuristics do not always guarantee an optimal or correct solution. On the other hand, an algorithmic approach follows a set of defined, structured steps leading to a definite solution, which is often the most optimal for the problem at hand. Based on mathematical and logical procedures, algorithmic methods offer predictability, repeatability, and guaranteed outcomes, making them reliable in situations where accuracy is paramount. As we will explore in detail in Chapter 10, heuristics and algorithms have a symbiotic relationship. While each has its own strengths and weaknesses, they can often complement each other to effectively tackle a wide range of problems. Understanding when and how to use each approach is a key skill in the art of algorithm design.