In this blog, we are going to learn about the Fundamentals of algorithmic problem solving in Data Structures.

Fundamentals of algorithmic problem solving

1. Understanding the problem.
2. Ascertaining the capabilities of a computational device.
3. Choosing between exact and approximate problem solving.
4. Deciding an appropriate Data Structure.
5. Algorithm design techniques.
6. Methods of specifying an algorithm.
7. Proving an algorithms correctness.
8. Analyzing an algorithm.
9. Coding an algorithm.

1. Understanding the problem

• Understand the given problem completely.
• Read the problem description carefully.
• Ask doubts about the problem.
• Do few examples.
• Think about special cases like boundary value.
• Know about the already known algorithms for solving that problem.
• Clear about the input to an algorithm.

2. Ascertaining the Capabilities of a computational device

• Sequential Algorithms: Instructions are executed one after another and one operation at a time.
• Algorithms designed to be executed on such machine are called sequential algorithms
• Parallel Algorithms: Modern computers that can execute instructions in parallel. Algorithms designed to be executed on such machine are called parallel algorithms.

3. Choosing between exact and approximate problem solving

• Exact Algorithm: Solving problem exactly.
• Approx. Algorithm: Solving problem approximately.

Why Approx. Algorithm.?

• Some problems cannot be solved exactly.
• Solving problem exactly can be unacceptably slow because of the problem complexity.

4. Deciding on appropriate Data Structures

• A Data structure is defined as a particular scheme of organizing related data items.
• Decide on the suitable data structure.

5. Algorithm Design techniques

• An algorithm design technique is a general approach to solve problems algorithmically.

• The various design techniques are:

  1. Brute force
  2. Divide and conquer
  3. Decrease and conquer
  4. Transform and conquer
  5. Greedy approach
  6. Dynamic programming
  7. Backtracking and Branch and bound
  8. Space and time tradeoffs

6. Method of specifying an algorithm

There are 3 methods:

1. Natural language: Easy but ambiguous
2. Pseudo code: Mixture of programming language and natural language.
3. Flow chart: It is pictorial representation of the algorithm. Here symbols are used.

7. Proving an algorithm’s correctness

• Correctness: Prove that the algorithm Yields the required result for every legitimate input in a finite amount of time.
• A common technique for proving correctness is to use mathematical induction.
• In order to show the algorithm Is incorrect, we have to take just one instance of its input for which the algorithm Fails.
• If a algorithm is found to be incorrect, then reconsider one or more those decisions.
• For approx. algorithm We should show that the error produced by the algorithm does not exceed the predefined limit.

8. Analyzing an algorithm

Analyze the following qualities of the algorithm.

• Efficiency: Time efficiency and Space efficiency
• Simplicity: Simple algorithms mean easy to understand and easy to program.
• Generality: Design an algorithm for a problem in more general terms. In some cases, designing more general algorithm Is unnecessary or difficult.

9. Coding an algorithm

• Algorithms are designed to be implemented as computer programs.
• Use code tuning technique. For eg., replacing costlier multiplication operation with cheaper addition operation.