Algorithmic Thinking has recently become a buzzword among programmers. It is a method for solving problems based on a clear definition of the steps: logically and repeatedly. The best idea would be to develop this skill independently from learning programming, where proper practice and visualization can help us understand several efficient problem-solving strategies.
Steps of Algorithmic Thinking
Step 1 : Comprehending the problem statement
- Do we understand every word used within the problem?
- What data or information are provided as input?
- What data or results are requested as an output?
- Understanding computational and non-computational details relevant to the problem : data structures, particular instances of the problem, critical operations, the specific constraint on input, distribution of the input, mathematics, physics, etc.
- Understanding the problem qualitatively by drawing a clear visualization.
Step 2 : Selecting concepts that can be applied
- Making some predictions regarding the concepts based upon problem description and listing down all relevant concepts.
- Have we solved any similar problems? If yes, then take advantage of that experience. Identify already known algorithms of similar problems.
- Are we going to use all the information available in the problem statement? Is it possible to eliminate unnecessary data?
- Selecting a structure to simplify data handling: function, arrays, linked lists, loop, stack, queue, hash table, local variables, global variables, etc.
Step 3 : Formulation of an algorithm strategy
- Exploring the hand-written way to solve the problem by going through several examples, then attempting to create a generalization. To do this, carefully think about each step and observe what actions are common to every example.
- Identifying the solution strategy based on the nature of the problem like divide and conquer, dynamic programming, backtracking, greedy, using a data structure, using numbers theory, etc. Here two types of thinking are important:
- Iterative Thinking : solving the problem by building the partial solution.
- Recursive Thinking : solving the problem using the smaller sub-problems.
- Visualizing solution on the paper by describing operations to transform given input to the desired output.
- Designing and writing step-by-step solutions in simple English and Transforming them into pseudocode or flowchart.
- Transforming the pseudocode into a working code using your favorite programming language like C++, Java, Python, etc.
- Taking care of the correct coding style.
Step 4 : Verifying correctness and optimizing further
- Manually analyze the input-output pattern by performing a hand trace. If needed, draw a plot to describe the behavior of the variables or critical steps defined in the algorithm.
- Is there some input for which our algorithm is not providing correct output? Does it work for all boundary cases?
- If there is an error or bug , identify the steps which are responsible for that. How to correct that bug or error?
- After verifying correctness, now we should analyze the efficiency by counting the total number of operations with respect to the input size. Sometimes we need to define the abstract mathematical model to count operations like recurrence, summation, etc.
- Now the critical step is to optimize the solution and solve it using a fewer number of steps. But how do we do it? We can identify some essential details of the problem to try a different problem-solving approach. We should keep optimizing the solution further until there is no further possibility.
- Sometimes we can also optimize the solution code further by reducing some intermediate steps in the pseudocode.
Algorithmic Thinking via Solving Puzzles
Solving algorithmic puzzles is a most productive and enjoyable way to develop algorithmic thinking. Puzzles are an ideal vehicle for mastering this skill for three reasons :
- Solving puzzles are always fun where a learner is normally willing to put more effort into solving them than everyday professional work.
- Most of us have a natural tendency to think in terms of computer programming problems instead of applying problem-solving strategies. Here algorithmic puzzles help us think on a more abstract level to develop ideas related to problem-solving strategies.
- Sometimes interviewers offering problems during interviews claim that they are more interested in how an interviewee approaches a problem than it's the implementation of the solution. Showing expertise in applying problem-solving strategies and analysis can be a highly attractive way to impress the potential employer.
But before moving forward, we would like to make an essential comment on different types of algorithmic puzzles :
- Every puzzle has an input that defines an instance of the puzzle. The instance can be either specific (e.g., find a false coin among eight coins with a balance) or general (e.g., find a false coin among N coins with a balance).
- When dealing with a specific instance of a puzzle, the learner has to focus on the particular instance given. It might be the case that other instances of the puzzle do not have the same solution or even do not have solutions at all!
- On the other hand, solving the general instance of the puzzle could be more satisfying and even more comfortable most of the time.
- But whether a puzzle is presented by a specific instance or given in its most general form, it is almost always a good idea to solve a few small instances of it anyway because it can provide useful insights into the puzzle given.
Popular Problem-Solving Strategies in Algorithms
The purpose of this section is to highlight some general strategies for designing algorithms and solving problems in computer science. Learning to apply these strategies could be one of the best achievements for the learners.
1. Incremental Approach by Building the Partial Solution
One of the simple ideas of our daily problem-solving activities is where we build the solution partially step by step. There is a different variation to it:
- Input-centric strategy : at each step of the iteration, we process one input and build the partial solution.
- Output-centric strategy : at each step of the iteration, we add one output to the solution and build the partial solution.
- Iterative improvement strategy : Here, we start with some easily available approximations to a solution and continuously improve upon it to reach the final solution.
Examples: Insertion Sort, Finding max and min in an array, Valid mountain array, Find equilibrium index of an array, Dutch national flag problem, Sort an array in a waveform
2. Decrease and Conquer Approach
The decrease-and-conquer strategy is based on finding the solution to a given problem via its one sub-problem solution. Such an approach leads naturally to a recursive algorithm, which reduces the problem to a sequence of smaller input sizes. Until it becomes small enough to be solved, i.e., it reaches the recursion’s base case.
Examples: Euclid algorithm of finding GCD, Binary Search, Josephus problem
3. Divide and Conquer Approach
The divide-and-conquer strategy is to partition a problem into more than one subproblems, solve each of them, and then, if necessary, combine their solutions to get a solution to the original problem. We solve many fundamental problems efficiently in computer science by using this strategy.
Examples: Merge Sort, Quick Sort, Median of two sorted arrays
4. Transform and Conquer Approach
The transform-and-conquer is a problem-solving approach that is based on the idea of transformation. A problem is solved in two stages:
- Transformation stage : We transform the original problem into another problem that is easier to solve.
- Conquering stage : Now, we solve the transformed problem.
We can identify three varieties of this problem-solving strategy:
- Instance simplification strategy : transforming an instance of the given problem into another instance of the same problem with some special property that makes the problem easier to solve.
- Representation change strategy : based on the transformation of a problem’s input to a different representation that is more conducive to an efficient algorithmic solution.
- Problem reduction strategy : here instance of a given problem is transformed into an instance of a different problem altogether.
Examples: Many problems based on array or list are easy to solve if array or list are sorted i.e. Pre-sorting based algorithms (Finding closest pair of points, checking whether all the elements in a given array are distinct, etc)
5. Greedy approach
The greedy approach solves an optimization problem by expanding a partially constructed solution until a complete solution is reached. At each step, we take a greedy choice and add it to the partially constructed solution. This idea produces the optimal global solution without violating the problem’s constraints.
- The greedy choice is the best alternative available at each step is made in the hope that a sequence of locally optimal choices will yield a (globally) optimal solution to the entire problem.
- This approach works in some cases but fails in others. Usually, it is not difficult to design a greedy algorithm itself, but a more difficult task is to prove that it produces an optimal solution.
Examples: Fractional Knapsack, Dijkstra algorithm of the shortest path
6. Dynamic programming
Dynamic programming is one of the most popular techniques for solving problems with overlapping or repeated subproblems. This
- Rather than solving overlapping subproblems, again and again, we solve each smaller subproblems only once and store the results in memory.
- We solve a lot of optimization and counting problems using the idea of dynamic programming.
Examples: Finding nth Fibonacci, Longest Common Subsequence, Climbing Stairs Problem, Maximum Subarray Sum, Minimum number of Jumps to reach End, Minimum Coin Change
7. Exhaustive search
An exhaustive search can solve many problems : a strategy that explores all possibilities of solutions until a solution to the problem is found. Therefore, problems are rarely offered to a person to solve the problem using this strategy.
The most crucial limitation of exhaustive search is its inefficiency: as a rule, the number of solution candidates that need to be processed grows at least exponentially with the problem size, making the approach inappropriate not only for a human but often for a computer as well.
Examples: Find all permutations of a string, Print all subset
Backtracking is an improvement over the approach of exhaustive search. It is a method for generating a solution by avoiding unnecessary possibilities of the solutions! The main idea is to build a solution one piece at a time and evaluate each partial solution as follows:
- If a partial solution can be developed further without violating the problem’s constraints, then it is done by taking the first remaining valid option at the next stage. (Think!)
- Suppose there is no valid option at the next stage, i.e. If there is a violation of the problem constraint, the algorithm backtracks to replace the partial solution’s previous stage with the following option for that stage. (Think!)
In simple words, backtracking involves undoing several wrong choices — the smaller this number, the faster the algorithm finds a solution. In the worst-case scenario, a backtracking algorithm may end up generating all the solutions as an exhaustive search, but this rarely happens!
Example: Rat in a maze, N-queen problem
Some of the best puzzles to warm up algorithmic thinking
Source: Algorithmic Puzzles by Anany Levitin and Maria Levitin
Enjoy learning, Enjoy coding, Enjoy algorithms!