16 Fundamental Stages of Problem Solving

S. Sridhar

Module2

Fundamental Stages of Problem Solving

 

This module focuses on the stages of problem solving. The learning objectives of this module are as follows:

  • To understand stages of Problem solving process
  • Characteristics of an Efficient Algorithm
  • To categorize algorithms

Fundamental stages of Problem Solving

 

Problem solving is both an art and science. As there are no guidelines available to solve the problem, the problem solving is called an art as high creativity is needed for solving problems effectively. Thus by art, we mean one has to be creative, novel and adventurous and by science, we mean the problem solving should be based on sound mathematical and logical guidelines.

 

The problem solving stages are given as follows:

 

1.  Problem Understanding

2.  Algorithm Planning

3.  Design of algorithms

4.  Algorithm Verification and Validation

5.  Algorithm analysis

6.  Algorithm Implementation

7.    Perform post-mortem analysis

 

1. Problem Understanding:

Is it possible to solve the given problem? This falls under the domain called computability theory. Computability theory deals with the solvability of the given problem.

 

To deal with the solvability, one require analytical thinking. Analytical thinking deals with the ways of solving the given problems. It is not possible to solve the problem if the problem is ill- defined. Often puzzles depict the limitations of computing power. Sometimes, there may be some solution but one doesn‟t have the knowledge or means to analyze the algorithms. Thus problems can be as follows:

1.  Computationally hard problems: It is not possible to solve this problem.

2.  Analytically hard problems: These problems, like Traveling salesperson problem, runs effectively for small instances. But for larger problems, it may be computationally feasible. Also for some problems analysis is difficult.

 

In computability theory, these sort of problems are often considered. The problem solving starts with understanding of the problem and aims at providing a detailed problem statement. There should not be any confusion in the problem statement. As the mistakes in understanding the problem may affect the development of algorithms.

 

2.  Planning of an algorithm

Once problem statement is produced, the planning of algorithm starts. This phase requires selection of computing model and data structures.

Computational model is the selection of a computing device. A computational model is a mathematical model. Why? It is meaningless to talk about fastness of the algorithm with respect to a particular machine or environment. An algorithm may run faster in machine A compared to machine B. Hence, analysis of algorithms based on a particular brand of machines is meaningless. Hence, the algorithm analysis should be should be independent of machines.

Normally, two theoretical machines are used – One is called Random Access Machine (RAM) and another is called Turing machine.

 

Data Structures

 

Second major decision in algorithm planning is selection of a data structure. Data structure is a domain that deals with data storage along with its relationships. Data structures can have impact on the efficiency of the algorithms. Therefore, algorithms and data structures together often constitute important aspect of problem solving.

 

 

Fig. 1 : Example of a Queue

Data organization is something we are familiar with in our daily life. The Fig 1 shows a data organization called „Queue”. A Gas station with one servicing point should have a queue like above to avoid chaos. A queue (or FCFS – First Come First Serve) is an organization where the processing (filling of gas) is done in one end and addition of a vehicle is done in another end. A popular statement in computer science is “Algorithm + Data structure = Program” as a wrong selection of a data structure often proves fatal in problem solving.

The planning of a data structure can be based on the solution also as some of the problems can be solved exactly. Sometimes, getting the exact solution is impossible for computationally hard problems. Therefore, for such problems approximate solutions are planned.

 

2.  Design of Algorithms

Algorithm design is the next stage of problem solving. Algorithm design is a way of developing the algorithmic solutions using the appropriate design strategy.

Different types of problem demands different strategies for finding the solution. Just imagine, searching a name in a telephone directory. If one has to search for a name “Qadir”, then the search can be done from starting page to the end page. This is a crude way of solving the problem. Instead, one can prefer to search using indexed entries. It can be done using interpolation search also. Thus design strategy selection plays an important role in solving problems effectively.

 

After the algorithm is designed, it should be communicated to a programmer so that the algorithms can be coded as a program. This stage is called algorithm specification. The choices of communication can be natural language, programming language and pseudocode. Natural language is preferable, but has some disadvantages such as lack of precision and ambiguity. Programming language may create a dependency on that particular language. Hence, often algorithm is written and communicated through pseudocode. Pseudocode is a mix of natural language and mathematics.

 

3.    Algorithm Verification and validation

Algorithm verification and validation is the process of checking algorithm correctness. An algorithm is expected to give correct output for all valid inputs. This process is called algorithm validation. Once validation is over, program proving or program verification starts.

Verification is done by giving mathematical proofs. Mathematical proofs are rigorous and better than scientific methods. Program correctness itself a major study by itself. Proofs are given as follows:

1.  Proof by assertion: Assertion assert some facts. It can be given throughout the program and assertions expressed are in predicate calculus. If it can be proved that, if for every legal input, if it leads to a logical output, then it can be said that the given algorithm is correct.

2. Mathematical Induction: Mathematical induction is a technique can be used to prove recursive algorithms.

5. Algorithm Analysis

Once the algorithm is proved correct, then the analysis starts. Analysis is important for two reasons. They are as follows:

1.  To decide efficiency of algorithms

2.  To compare algorithms for deciding the effective solutions for a given problem.

Algorithm analysis as a domain is called Algorithmic Complexity theory. What is a complexity? Well, complexity is assumed to be with respect to size of the input. Sorting of an array with 10 numbers is easy: but the same problem with 1 million is difficult. So there is a connection with the complexity and the size of the input.

The complexity of two or more algorithms can be done based on measures that can be categorized into two types.

 

1.  Subjective measures.

2.  Objective measures.

Subjective measures include factors like ease of implementation or style of the algorithm or understandability of algorithms. But the problem with the subjective measures are that they vary from person to person. Hence Objective measures are preferable.

Objective measures include factors like time complexity, space complexity and measures like disk usage and network usage. By and large, algorithmic analysis is the estimation of computing resources. Out of all objective measures, two measures are popular. They are time and space.

 

1.   Time complexity: Time complexity refers to the time taken by the algorithm to run for scaled input. By time, it is often meant run time. Actually, there are two time factors. One is execution time and another is run time. Execution (or compile time) does not depend on problem instances and compilers often ignore instances. Hence, time always refers to run or execution time only.

2.  Space Complexity: Space complexity is meant the memory required to store the program.

 

6.  Implementation of algorithm as a program and performance analysis

After the algorithms are designed, it is implemented as a program. This stage requires the selection of a programming language. After the program is written, then the program must be tested. Sometimes, the program may not give expected results due to errors. The process of removing the errors is called debugging. Once program is available, they can be verified with a bench mark dataset. It is called experimental algorithmics. This is called performance analysis. Thus, Profiling is a process of running a program on a datasets and measuring the time/space requirement of the program.

 

7.  Postmortem analysis

A theoretical best solution for the given problem is called lower bound of the algorithm. The worst case estimate of behavior of the algorithm is called upper bound. The difference between upper and lower bound is called algorithmic gap. Technically, no algorithmic gaps should exist. But practically, there may be vast gap present between two bounds.Problem solving process ends with postmortem analysis. Any analysis should end with the valuable insight. Insights like Is the problem solvable? Are there any limits of this algorithm? and Is the algorithm efficient? are asked and collected.

Refining the algorithms is to bring these gaps short by reefing planning, design, implementation and analysis. Thus problem solving is not linear but rather this is a cycle.

 

 

Classification of Algorithms

For effective, often algorithms are categorized. The algorithm categorization can be done based on various criteria such as

 

1.  Implementation

2.  Design

3.  Problem Types

4.  Tractability

 

1.  Classification by Implementation

Based on implementation, one can classify the algorithms as recursive algorithm and iterative algorithms.

Recursive algorithm is an algorithm that uses functions that call itself conditionally. Recursion is a top-down approach of solving the given problem by reducing the problem to another problem with a unit decrease in input instance. The transformed problem is same as the original problem but with a difference that its input is one less than the original problem. This strategy uses the principles of work postponement or delaying the work. Iterative algorithms on the other hand are deductive.

 

Based on implementation, the algorithms can be classified as sequential or parallel algorithms. An algorithm that uses only one processor is called sequential algorithm. On the other hand, a parallel algorithm uses a set of processors to find a solution of the problem. Similarly, the algorithm can be classified as exact or approximation based on the solution it provides for the given problem. Again, based on implementation, the algorithms can be categorized as deterministic and randomized. Deterministic algorithms have predictable results for a given input. If this is not possible, then the algorithm is called non-deterministic.

 

2.  Classification by Design

Based on design technique, the algorithms can be classified. Some of the popular algorithm design categories brute force method, Divide and Conquer, Dynamic programming, greedy approach, and backtracking.

 

 

3.  Classification by Problem TypesBased on problem types or domain, the algorithm can be classified as follows:

  1. Sorting Algorithms
  2. Searching Algorithms
  3. String Algorithms
  4. Graph Algorithms
  5. Combinatorial Algorithms
  6. Geometric Algorithms

4. Classification based on Tractability

Based on tractability, the algorithms can be categorized as polynomial algorithms and Non- deterministic polynomial problems. Easy solvable problems are called polynomial algorithms and the problems for which solution is not possible or difficult to solve given the limited nature of resources are called NP algorithms.

 

Summary

This module can be concluded as follows:

  1. Problem solving stages are problem understanding, planning, design, analysis, implementation and post-analysis.
  2. Problem understanding and planning is important. Algorithm design and analysis is crucial.
  3. Classification of  Algorithms  is  based  on  implementation,  design,  problem  type  and tractability.

References

  1. S.Sridhar – Design and Analysis of Algorithms , Oxford University Press, 2014.
  2. Cormen, T.H., C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA 1992.