Algorithmic thinking, problem partitioning and problem solving

algorithmic thinking

Algorithmic Thinking refers to the ability or process of thinking about logical procedures and approaches in problem solving and task execution. Having algorithmic thinking is an important skill that can help in dealing with a wide range of complex challenges. The main elements of algorithmic thinking are discussed below.

1. Problem decomposition: the ability to break up a large problem into smaller sub-problems, effectively dividing complex problems into manageable units and devising solutions to each.
2. Pattern recognition: the ability to find hidden patterns and regularities in problems and data, which facilitates the discovery of common approaches to similar problems.
   Abstraction: the ability to focus on the essential parts of a problem and ignore unnecessary details, which captures the elements of the problem at an abstract level and is what designs the solution.
3. Sequencing: the ability to arrange the steps for solving a problem in a logical sequence, where it is important to consider which steps should be carried out in what order.
4. Efficiency considerations: the ability to consider efficiency, such as execution time and resource usage, when designing a solution, and to select the best method or algorithm to find an efficient solution.
5. Situation modelling: the ability to translate a problem into a mathematical equation or model and apply mathematical methods and algorithms, which improves the ease of finding a solution by taking a mathematical view of a real-world problem.

Algorithmic thinking is a useful skill in many fields, not just programming and computer science, and provides a basis for taking a logical and effective approach to everyday problem solving and decision-making. To develop algorithmic thinking, it is important to hone the above elements through problem-solving practice and the study of algorithms.

This algorithmic thinking is also summarised in e.g. “Algorithms to Live By: The Computer Science of Human Decisions“.

In this section, I would like to discuss the division of the problem among the key elements of the above algorithm.

Division of problems in algorithmic thinking.

Problem partitioning in algorithmic thinking is the process of dividing a large problem into a number of smaller sub-problems, an approach that breaks down a complex problem into manageable units, making the larger problem easier to understand and allowing each sub-problem to be solved individually and efficiently. Problem splitting can be seen as the first step in the general problem-solving process.

Some key points on problem splitting are

1. Understanding the problem: First understand the problem in detail, its structure and requirements. Clarifying the nature of the problem and its goals forms the basis for splitting it up.
2. Identification of sub-problems: the division of a large problem into smaller sub-problems. View sub-problems as steps or procedures necessary to solve the original problem.
3. Relevance considerations: consider the relevance and dependencies between subproblems. Understand which subproblems depend on the results of other subproblems.
4. Balancing the partitioning: it is important to balance the partitioning of the subproblems appropriately. Too small subproblems make it difficult to integrate solutions, while too large subproblems increase the complexity of the problem.
5. Recursive partitioning: a recursive approach may be adopted when the problem is to be further partitioned into smaller subproblems. Recursive partitioning is effective when the subproblems have the same form.

Thus, the division of the problem is an approach to the analysis of the problem itself and is the most important method of problem solving. The following section describes specific techniques for the partitioning of that problem.

Specific techniques for problem splitting.

Several specific methods and frameworks exist for problem partitioning, which enable problem solving to proceed effectively by selecting the appropriate method depending on the situation. The following sections describe specific problem-splitting methods.

1. top-down approach: the top-down approach is a method where the overall problem is first identified and then the larger problems are divided into smaller sub-problems. This approach starts with the top-level abstract goal and gradually breaks down the problem into concrete issues.

The concrete steps are as follows.
1. define the overall goal: set objectives and goals for the whole issue
2. divide into sub-problems: identify the subtasks and problems required to achieve that objective.
3. further division: each subproblem is further divided and subdivided into smaller units.

This top-down approach can also be described as the KPI etc. approach described in ‘Overview and practice of KPIs, KGIs and OKRs for problem analysis’. While the top-down approach is simple and can be implemented with speed, it does not work well for ventures that aim to develop new ideas and creative services and products, as mistakes in the top-level objectives and their interpretation can lead to wrong results.

For a top-down approach to be successful, it is necessary to incorporate indicators to assess the process, such as KGIs (Key Goal Indicators) and KSFs (Key Success Factors), and to provide feedback on the analysis of goals. The following are some of the key indicators that can be used to assess the process.

2. bottom-up approach: the bottom-up approach is a method in which small elements or partial problems are solved first and then combined to construct an overall solution; in this approach, specific, feasible level tasks are solved first and then the whole problem is solved by integrating them.

The concrete steps are as follows.
1. analysing individual elements: identifying small, solvable tasks or problems
2. creating partial solutions: developing solutions for each part and improving them with feedback on successes and failures
3. integration: integrating partial solutions to help solve the overall problem.

The advantage of the bottom-up approach is its flexibility: it is the base algorithm for the behaviour of many living organisms and is often used in systems that need to adapt and operate in a self-organising way in complex environments, such as robotic vacuum cleaners and the control of large chemical plants.

The number one challenge of the bottom-up approach is its speed, as described in ‘Introduction to multi-agent systems!’ The multi-agent system described in ‘Introduction to multi-agent systems’ is a typical example of a bottom-up approach implemented, but it is necessary to consider improving efficiency by introducing algorithms such as reinforcement learning, as described in ‘Overview and implementation examples of multi-agent systems using deep reinforcement learning (DRL)’, for collaboration between agents. The need to improve efficiency.

3. modularisation: modularisation is a method of designing an entire system by dividing it into a number of independent modules, each of which functions independently, so that each part can be developed and optimised independently and its dependencies with other parts minimised. .

The concrete steps are as follows.
1. defining modules: dividing the problem into modules based on different functions or domains
2. module-specific problem solving: solve each module separately and then integrate it with the other modules.
3. interface design: define interfaces between modules so that they can work independently of each other.

Examples of module partitioning include object-oriented partitioning, described e.g. in ‘object-oriented languages’, where the problem is partitioned based on objects (data and associated operations), and functional partitioning, where the system is partitioned based on its functions.

As in the above examples, modularisation is widely used in software development, and its application to AI development includes Herbert Simon’s decision support system described in ‘System design and decision-making systems’.

Another example of application to general issues, such as social problems, is the systems dynamics approach based on the integration of simulation with systems thinking, as described in ‘Systems thinking approach and the SDGs’.

The challenge of modularisation is how to define modules, and the consideration of these motivates the use of various programming languages, as described in ‘Overview of programming techniques’.

4. Hierarchical Decomposition: Hierarchical decomposition is a method of breaking down a problem into a hierarchical structure, progressively dropping from higher level abstract problems to lower level concrete problems, and finding appropriate solutions at each level, leading to the solution of the whole problem.

The concrete steps are as follows:
1. defining the higher-level problem: defining the overall goal or top-level issue of the problem.
2. hierarchical division: divide the top problem into sub-problems, each of which is further subdivided.
3. implementing the solution: solving the lower-level problems first, then integrating the solution into the higher-level problems.

A concrete example of a hierarchical approach is PID control, one of the control algorithms widely used in industrial control and robotics, which is a method for minimising system errors (i.e. specific actions (speed and position adjustment) are performed in the low-level control layer to realise precise actions in accordance with instructions from higher levels), Hierarchical State Machine (HSM), an application algorithm for state machines described in ‘Overview and Implementation of Finite State Machines (FSM), Reference Book’, which divides the system behaviour into different levels of states (low, medium and high) and controls the behaviour in a hierarchical manner. Hierarchical State Machine, HSM), an algorithm that controls a system to minimise certain performance criteria (e.g. energy consumption or time), Optimal Control, an algorithm that controls a system to minimise certain performance criteria (e.g. energy consumption or time) and is used in aircraft autopilot or energy efficient robot motion planning. Optimal Control, an algorithm that predicts system behaviour in the future and calculates optimal control actions, as described in ‘Overview, algorithms and implementation examples of Model Predictive Control (MPC)’, MPC, which is also used in robot control, such as automatic cleaning robots. Sub-sumption Architecture’ and “Task Hierarchy Control”, which are well-known for their use in controlling robots such as automatic cleaning robots and are also described in “Basic Technologies of Digital Game AI (Temporal Recognition Technology)”. and others.

Various algorithms have been devised for hierarchical approaches, which are widely used to optimise the overall system by efficiently linking low-level detailed control to high-level abstract goal setting.

By using these techniques to partition the problem, it is possible to derive effective solutions to complex problems. The choice and design of appropriate algorithms is a major factor influencing the success of problem solving.

reference book

Reference diagrams that can be used to learn about ‘problem partitioning’ (divide and conquer or hierarchical problem solving) in algorithmic thinking include the following.

1. “Introduction to Algorithms” by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein

• Overview: Often referred to as the “CLRS” book, this is one of the most comprehensive texts on algorithms. It thoroughly covers divide-and-conquer algorithms (like merge sort and quicksort) and dynamic programming, both of which are fundamental to understanding problem decomposition. It’s highly regarded for its clarity and depth, making it essential reading for computer science students and professionals.

2. “The Algorithm Design Manual” by Steven S. Skiena

• Overview: This book is an excellent guide for designing and implementing algorithms. Skiena provides practical advice on how to break down complex problems into simpler subproblems, focusing on strategies like divide-and-conquer, dynamic programming, and greedy algorithms. The book is noted for its problem-solving approach, with real-world examples.

3. “Algorithms” by Robert Sedgewick and Kevin Wayne

• Overview: This book provides a thorough introduction to algorithms and data structures, with a focus on problem-solving techniques. The authors emphasize divide-and-conquer algorithms, sorting, searching, and graph algorithms. The visual and intuitive explanations help in understanding how to break problems into manageable pieces.

4. “Grokking Algorithms” by Aditya Y. Bhargava

• Overview: This beginner-friendly book explains algorithms in a simple, visually engaging way. It covers key problem-solving techniques like divide-and-conquer, dynamic programming, and recursion. The book is heavily illustrated, making complex concepts more digestible, particularly for those new to algorithmic thinking.

5. “Computer Algorithms: Introduction to Design and Analysis” by Sara Baase and Allen Van Gelder

• Overview: This book offers a clear explanation of the design and analysis of algorithms. It includes a strong focus on divide-and-conquer methods, dynamic programming, and recursion, providing students with practical insights into how problems can be split into smaller subproblems and tackled efficiently.

6. “Algorithmic Thinking: A Problem-Based Introduction” by Daniel Zingaro

• Overview: This book uses a problem-based approach to introduce algorithmic thinking and problem-solving. It focuses on breaking down problems into smaller parts, with practical examples that show how to approach complex problems using divide-and-conquer, greedy algorithms, and dynamic programming.

7. “Algorithms Unlocked” by Thomas H. Cormen

• Overview: A more accessible version of the “Introduction to Algorithms” book, it provides an approachable introduction to the world of algorithms. It explains key concepts like divide-and-conquer in a way that is easier to grasp for those without a strong background in computer science.

8. “Algorithm Design” by Jon Kleinberg and Éva Tardos

• Overview: This book delves deeply into algorithmic techniques such as divide-and-conquer, dynamic programming, and greedy algorithms. It emphasizes problem-solving and provides numerous examples of how to divide problems into smaller, manageable parts to find efficient solutions.

9. “Algorithms Illuminated” by Tim Roughgarden

• Overview: A multi-volume series that breaks down complex algorithmic concepts into more manageable pieces. The divide-and-conquer method and dynamic programming are explored in detail, with clear explanations and examples to help readers master problem decomposition.

10. “Cracking the Coding Interview” by Gayle Laakmann McDowell

• Overview: Though primarily a coding interview preparation book, it covers essential algorithms and problem-solving strategies, including divide-and-conquer and dynamic programming. The book offers practical insights into how to break down large, complex problems in the context of programming interviews.