A computational problem refer to a specification that asks for certain outputs from a family of instances or inputs. For example, the graph colouring problem is a computational problem where both the inputs and outputs are (networked) graphs.
A computational problem specifies a set of inputs , and some output for each input .
An algorithm is an implementation of such a problem, that defines the steps required to get from the certain input to the output. More specifically, it is a series of computational steps. An algorithm solves a computational problem, if, for every inputs specified by the problem, it produces the required output. Mathematically:
Solving
A basic guide to attempting to solve an algorithmic problem.
• Understand the problem • Decide on the computational means (sequential/parallel, exact/approximate) • Decide on method to use (design paradigm, use of randomization) • Design the necessary data structure and algorithm • Check for correctness, trace example input • Evaluate analytically (time complexity, space complexity, worst and average case) • Code it • Evaluate empirically
Problem Classifications
Decision
Optimisation
Correctness
Optimality
Optimisation
Examples
- 0-1 Knapsack Problem
- Acceptance Problem
- Boolean Satisfiability Problem
- Closest Pair Problem
- Coin Collecting Problem
- Coin Row Problem
- Coin Change Problem
- Computational Model Problems
- Emptiness Problem
- Equivalence Problem
- Graph Colouring Problem
- Halting Problem
- Map Colouring Problem
- N-Queens Problem
- Packing Problem
- Proof By Reduction
- Shortest Path Problem
- String Matching Problem
- String Pattern-Matching
- problem.template
- Topological Sorting
- Travelling Salesman Problem (TSP)