2.1 Computing Problems

Introduction

A computing problem in computer science is one that is solved step-by-step through computation. Any kind of calculation, including arithmetical and logical ones, can be included. These problems often involve an input that is well-defined and an output that needs to satisfy a few desired properties.

Definition

A computing problem is a problem that can be solved by a computer through a series of well-defined computational steps. It takes some input, processes it according to specific rules, and produces an output that satisfies certain desired properties.

Main Idea

Computing problems are the foundation of computer science. They can be simple (like checking if a number is even) or complex (like simulating a scientific phenomenon). Understanding the different domains of computing problems helps in choosing the right approach to solve them.

Core Concept

Some examples of computing problems include:

• Finding the largest number in a list.
• Checking if a number is even or odd.
• Simulating a scientific phenomenon.

Some of the computing problem domains are as follows:

• Decision Problems
• Search Problems
• Counting Problems

Detailed Explanation

Decision Problems

In decision problems, normally a 'yes-or-no' response is found in a choice. For example, given a number n, "is n even?"

However, some decision problems may require more steps to solve. For example:

• Given a number n, "is n prime?" requires more work than just checking the number's parity.
• Given a string, is its length greater than 5 characters?
• Given an integer n, is n an even number?

• The answer is always yes or no.
• The problem is about making a decision.
• Sometimes the decision is easy (is n even?); sometimes it is hard (is n prime?).

Search Problems

In search problems, the solution is made up by having a set of values that satisfy a certain criteria.

For example:

- We might wish to calculate a route on a map from one site to another (e.g., from Islamabad to Lahore).

• The answer is a set of values or a path.
• The problem is about finding something that satisfies certain conditions.
• Search problems can have one solution, many solutions, or no solution.

Counting Problems

In counting problems, the number of possible solutions to a search problem is the answer to that counting problem.

For the above-mentioned search problem "we might wish to calculate a route on a map from one site to another." The answer to the counting problem would be two, supposing we have two roads from Islamabad to Lahore, e.g., G.T. Road and Motorway.

• The answer is a number (how many?).
• The problem is about counting the number of solutions.
• Counting problems are often built on top of search problems.

Intermediate Level

At the intermediate level, you should understand the relationship between these domains.

• Decision problems are the simplest. They ask for a yes/no answer.
• Search problems are more complex. They ask for a value or set of values.
• Counting problems are built on search problems. They ask how many solutions exist.

• Decision: "Is there a path from A to B?" → Yes/No.
• Search: "Find a path from A to B." → A → C → B.
• Counting: "How many paths are there from A to B?" → 3.

Important Points

• - A computing problem is solved step-by-step through computation.
• - Three main domains: Decision, Search, Counting.
• - Decision problems ask for a yes/no answer.
• - Search problems ask for a value or set of values.
• - Counting problems ask for the number of solutions.
• - Counting problems are built on search problems.

Remember

• - Decision = Yes/No.
• - Search = Find a value.
• - Counting = How many?
• - Decision is simplest.
• - Search is more complex.
• - Counting is built on search.

Common Mistakes

• - Confusing decision problems with search problems (decision = yes/no, search = find a value).
• - Thinking that all computing problems are the same type.
• - Forgetting that counting problems are built on search problems.
• - Assuming that decision problems are always easy (some are very hard, like "is n prime?").
• - Confusing the input with the output of a computing problem.
• - Thinking that a computing problem must involve numbers (it can involve strings, paths, etc.).

Quick Revision

• Computing problem: solved step-by-step through computation.
• Decision problems: yes/no answer (is n even?).
• Search problems: find a value or set of values (route from A to B).
• Counting problems: how many solutions? (number of routes).
• Counting is built on search.

60-Second Revision

• Computing problem = solved by computation.
• Three domains: Decision, Search, Counting.
• Decision = Yes/No (is n even?).
• Search = Find a value (route from A to B).
• Counting = How many? (number of routes).
• Warning: Don't confuse decision with search; decision asks yes/no, search asks for a value.