Classification of Computational Problems
Computational problems can be classified based on difficulty, type of data used, nature of input, and type of output.
1. Classification Based on Computational Complexity
This classification depends on how the execution time of an algorithm increases with input size.
1.1 Easy Problems (Polynomial Time Problems)
Definition:
Problems that can be solved efficiently. When the input size increases, the time required increases slowly and remains manageable.
Universal Example:
Sorting student roll numbers in a class.
Sorting 30 students is quick, and sorting 300 students still takes reasonable time.
Key Point for Exam:
These problems are solvable in polynomial time (P).
1.2 Hard Problems (NP-Complete Problems)
Definition:
Problems for which the time required grows very fast (exponentially) as input size increases.
Universal Example:
Timetable scheduling for exams.
As the number of subjects and rooms increases, finding a perfect timetable becomes extremely difficult.
Key Point for Exam:
Such problems belong to the NP-Complete category (e.g., Travelling Salesman Problem).
2. Classification Based on Problem Domain
2.1 Numeric Problems
Definition:
Problems that involve numerical calculations.
Universal Example:
Calculating total marks and average percentage of students.
Standard Example:
Matrix multiplication.
2.2 String Processing Problems
Definition:
Problems that involve characters, words, or text.
Universal Example:
Searching a name in an attendance list.
Standard Example:
Pattern matching.
2.3 Graph Problems
Definition:
Problems that deal with nodes (objects) and edges (connections).
Universal Example:
Finding the shortest route from home to college.
Standard Example:
Shortest path problem.
3. Classification Based on Nature of Input
3.1 Static Problems
Definition:
Problems where input data does not change during execution.
Universal Example:
Sorting final exam marks after results are declared.
Standard Example:
Sorting a fixed list.
3.2 Dynamic Problems
Definition:
Problems where input keeps changing and the algorithm must update the solution.
Universal Example:
Traffic signal control system adjusting timings based on vehicle flow.
Standard Example:
Dynamic shortest path updates.
4. Classification Based on Type of Output
4.1 Decision Problem:
Output is Yes or No
Example: Is a student eligible for scholarship?
4.2 Search Problem:
Output is a specific result
Example: Find the roll number of a student.
4.3 Optimization Problem:
Output is the best possible solution
Example: Find the minimum travel cost.
4.4 Counting Problem:
Output is a number
Example: Count number of present students.
Solution Approaches to Solve Problems
Definition
Solution approaches are different strategies or techniques used to design algorithms for solving computational problems.
The selection of a suitable approach depends on the nature of the problem, constraints, and efficiency requirements.
Major Solution Approaches
1. Brute Force Approach 🔍
Explanation:
This approach tries all possible solutions and selects the correct or best one.
Key Points:
- Very easy to understand and implement
- Not efficient for large input sizes
- Execution time increases rapidly
Example:
Trying all possible routes to solve the Travelling Salesman Problem (TSP).
2. Divide and Conquer Approach ✂️
Explanation:
The problem is divided into smaller subproblems. Each subproblem is solved independently, and the results are combined to get the final solution.
Key Points:
- Reduces problem complexity
- Efficient for large datasets
- Uses recursion
- Merge Sort
- Quick Sort
3. Greedy Method 🤑
Explanation:
At each step, the algorithm makes the locally optimal choice with the hope that it leads to a globally optimal solution.
Key Points:
- Fast and simple
- Does not always produce the optimal solution
- Suitable when greedy choice property holds
Example:
Kruskal’s Algorithm for Minimum Spanning Tree (MST).
4. Dynamic Programming (DP) 🧠
Explanation:
This approach solves complex problems by breaking them into overlapping subproblems and storing the results to avoid repeated calculations.
Key Points:
- Improves efficiency
- Uses memoization or tabulation
- Suitable for optimization problems
Examples:
- Fibonacci sequence calculation
- Bellman-Ford Algorithm
5. Backtracking 🔙
Explanation:
A solution is built step by step. If a solution violates constraints, the algorithm backtracks and tries another option.
Key Points:
- Used for constraint satisfaction problems
- May take more time for large inputs
Examples:
- N-Queens Problem
- Sudoku solving
6. Heuristic / Approximation Methods 🎯
Explanation:
These methods provide near-optimal solutions when exact solutions are too complex or time-consuming to compute.
Key Points:
- Faster than exact algorithms
- Solutions may not be perfect
- Useful for NP-hard problems
Examples:
- Genetic Algorithms
- A* Search Algorithm
