What are the Fundamentals of algorithmic problem solving in Data Structures
In this blog, we are going to learn about the Fundamentals of algorithmic problem solving in Data Structures.
- Understanding the problem.
- Ascertaining the capabilities of a computational device.
- Choosing between exact and approximate problem solving.
- Deciding an appropriate Data Structure.
- Algorithm design techniques.
- Methods of specifying an algorithm.
- Proving an algorithms correctness.
- Analyzing an algorithm.
- Coding an algorithm.
- 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.
- 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.
- 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.
- A Data structure is defined as a particular scheme of organizing related data items.
- Decide on the suitable data structure.
- An algorithm design technique is a general approach to solve problems algorithmically.
The various design techniques are:
- Brute force
- Divide and conquer
- Decrease and conquer
- Transform and conquer
- Greedy approach
- Dynamic programming
- Backtracking and Branch and bound
- Space and time tradeoffs
There are 3 methods:
- Natural language: Easy but ambiguous
- Pseudo code: Mixture of programming language and natural language.
- Flow chart: It is pictorial representation of the algorithm. Here symbols are used.
- 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.
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.
- Algorithms are designed to be implemented as computer programs.
- Use code tuning technique. For eg., replacing costlier multiplication operation with cheaper addition operation.