Problem Solving and Algorithms

Introduction

A problem space is all of the various components that go into creating a resolution for a problem. Think of it like a frame, which acts as something of a border to help define an area. A problem space helps you or, on a larger scale, a business, figure out what the problem is, work through ways to correct them and then drives implementation of the appropriate solution. The ultimate purpose is to take corrective action for some identified problem.

Problem solving refers to cognitive processing directed at achieving a goal when the problem solver does not initially know a solution method.In computer science there are two different types of problems, ill-defined and well-defined: different approaches are used for each. Well-defined problems have specific end goals and clear expected solutions, while ill-defined problems do not.

In computer science, an algorithm is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation.Algorithms are unambiguous specifications for performing calculation, data processing, automated reasoning, and other tasks.

What is an algorithm?

An algorithm is an effective, efficient and best method which can be used to express solution of any problem within a finite amount of space and timeand in a well-defined formal language. Starting from an initial state the instructions describe a process or computational process that, when executed, proceeds through a finitenumber of well-defined successive states, eventually producing "output"and terminating at a final ending state.

In other words, we can say that,

Step by step procedure for solving any problem is known as algorithm.
An algorithm is a finite set of instructions that, if followed, accomplishes a particular task.
An algorithm is a sequence of computational steps that transform the input into a valuable or required output.
Any special method of solving a certain kind of problem is known as algorithm.

All Algorithms must satisfy the following criteria -

1) Input

There are more quantities that are extremely supplied.

2) Output

At least one quantity is produced.

3) Definiteness

Each instruction of the algorithm should be clear and unambiguous.

4) Finiteness

The process should be terminated after a finite number of steps.

5) Effectiveness

Every instruction must be basic enough to be carried out theoretically or by using paper and pencil.

Properties of Algorithm

Simply writing the sequence of instructions as an algorithm is not sufficient to accomplish certain task. It is necessary to have following properties associated with an algorithm.

Non Ambiguity

Each step in an algorithm should be non-ambiguous. That means each instruction should be clear and precise. The instruction in any algorithm should not denote any conflicting meaning. This property also indicates the effectiveness of algorithm.

Range of Input

The range of input should be specified. This is because normally the algorithm is input driven and if the range of input is not being specified then algorithm can go in an infinite state.

Multiplicity

The same algorithm can be represented into several different ways. That means we can write in simple English the sequence of instruction or we can write it in form of pseudo code. Similarly, for solving the same problem we can write several different algorithms.

Speed

The algorithmis written using some specified ideas. Bus such algorithm should be efficient and should produce the output with fast speed.

Finiteness

The algorithm should be finite. That means after performing required operations it should be terminate.

Types of algorithms

While solving a problem in computer science we came up with different kind of strategies i.e different ways of solving the problem.

Divide and Conquer Algorithm

This is another effective way of solving many problems. In Divide and Conquer algorithms, divide the algorithm into two parts, the first parts divides the problem on hand into smaller sub-problems of the same type. Then on the second part, these smaller problems are solved and then added together (combined) to produce the final solution of the problem.

Dynamic Programming Algorithm

These algorithms work by remembering the results of the past run and using them to find new results. In other words, dynamic programming algorithm solves complex problems by breaking it into multiple simple sub-problems and then it solves each of them once and then stores them for future use.

Greedy Algorithm

These algorithms are used for solving optimization problems. In this algorithm, we find a locally optimum solution (without any regard for any consequence in future) and hope to find the optimal solution at the global level.

The method does not guarantee that we will be able to find an optimal solution.

Brute Force Algorithm

This is one of the simplest algorithms in the concept. A brute force algorithm blindly iterates all possible solutions to search one or more than one solution that may solve a function. Think of brute force as using all possible combinations of numbers to open a safe.

Backtracking Algorithm

Backtracking is a technique to find a solution to a problem in an incremental approach. It solves problems recursively and tries to get to a solution to a problem by solving one piece of the problem at a time. If one of the solutions fail, we remove it and backtrack to find another solution.

In other words, a backtracking algorithm solves a sub-problem and if it fails to solve the problem, it undoes the last step and starts again to find the solution to the problem.

Understand By Examples

Divide and Conquer

Merge sorting and quick sorting can be done with divide and conquer algorithms. Here is the algorithm of the merge sort algorithm to give you an example:

MergeSorting

Step 1 - Find the mid-point to divide the given array into two halves:

Step 2 - Call mergeSorting for the first half:

Step 3 - Call mergeSorting for the second half:

Step 4 Merge the halves sorted in step 2 and 3

Dynamic Programming Algorithm

Fibonacci sequence is a good example for Dynamic Programming algorithms, you can see it working in this algorithm.

Fibonacci(N)

Step 1 - Fibonacci(N) = 0(for n=0)

Step 2 - Fibonacci(N) = 0(for n=1)

Step 3 - Fibonacci(N) = Fibonacci(N-1)+Fibonacci(N-2)(for n>1)

Greedy Algorithm

Dijkstra’s algorithm is a prime examples where Greedy algorithm is used.

Step 1 - Mark all nodes unvisited. Create a set of all the unvisited nodes called the unvisited set.
Step 2 - Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes. Set the initial node as current.
Step 3 - For the current node, consider all of its unvisited neighbours and calculate their tentative distances through the current node. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one.
For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbour B has length 2, then the distance to B through A will be 6 + 2 = 8. If B was previously marked with a distance greater than 8 then change it to 8. Otherwise, the current value will be kept.
Step 4 - When we are done considering all of the unvisited neighbours of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again.
Step 5 - If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal; occurs when there is no connection between the initial node and remaining unvisited nodes), then stop. The algorithm has finished.
Step 6 - Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new "current node", and go back to step 3.

Brute Force Algorithm

Sequential or linear Search done by using brute force

linear search(array,key)

Step 1 - Start from the leftmost element of array and one by one compare key with each element of array.
Step 2 - If matches with an element, return the index.
Step 3 - If key doesn’t match with any of elements, stop.

Backtracking Algorithm

N Queens problem is one good example to see Backtracking algorithm in action. The N Queen Problem states that there are N pieces of Queens in a chess board and we have to arrange them so that no queen can attack any other queen in the board once organized.

Now let’s take a look at SolveNQ algorithm and Check Valid functions to solve the problem:

CheckValid(Chessboard, row, column)

Start

If there is a Queen at on the left of the current column then return false

If the queen is at upper-left diagonal, then return false

If the queen is at lower-left diagonal, then return false

Return true

End

SolveNQ(Board, Column)

Start

If all columns are full then return true

For each row present in the chess board

If, CheckValid( board, x, column), then

Set the queen at cell (x, column) on the board

If SolveNQ(board, column+1) = True, then return true.

Else, remove the queen from the cell ( x, column) from board

Done

Return false

End

Steps to solve a problem

Analyze the Problem
Redefine the Problem
Understand the Input and Output of the Problem
Break the Problem in Sub problems
Outline a Solution
Optimize the solution

Conclusion

This article starts by defining problem space, problem solution and algorithms then dive into algorithms deeply and concluded by listing the steps to solve a problem. In the next article we will take a problem and solve it from scratch by defining all the steps discussed earlier. I hope this gives you the basic idea about problem solving and algorithms.

References

CODEBUDY

Search This Blog