2.2 Identifying a Computing Problem

This topic explains what a computing problem is and how to identify different types of computing problems, including decision, search, and counting problems.

Definition

Computing Problem: In computer science, a computing problem is a problem that is solved step-by-step using computation. It can include any type of calculation such as arithmetical or logical. These problems usually have a well-defined input and some desired properties that output must satisfy.

Core Concept

Identifying a computing problem is like diagnosing an illness before prescribing medicine. Before you can solve a problem with a computer, you must first understand what kind of problem it is. Is it asking for a yes/no answer? Is it asking you to find something? Is it asking how many possibilities exist? Recognizing the problem type helps you choose the right computational approach—just as a doctor chooses the right treatment based on the diagnosis.

Detailed Explanation

What is a Computing Problem?

In computer science, a problem is a challenge or situation that needs to be overcome using some action. A computing problem is a problem that is solved step-by-step using computation. It can include any type of calculation such as arithmetical or logical. These problems usually have a well-defined input and some desired properties that output must satisfy.

• Has well-defined input and output.
• Solved using computation (step-by-step).
• Can be arithmetical or logical.
• Output must satisfy desired properties.

Types of Computing Problems

Following are some of the computing problems:

• Decision Problems
• Search Problems
• Counting Problems

Decision Problems

A decision problem occurs when a given input requires a binary response, either Yes or No. Responses may take various forms, such as true or false. In complex cases, answers extend beyond a straightforward Yes-or-No, involving multiple decision factors and criteria.

• Binary answer (Yes/No, True/False).
• Input is given; output is a decision.
• Can involve multiple criteria in complex cases.

Example 1: The problem of whether a given number is odd (or even). This is a decision problem where the task is to check if a given integer is divisible only by 1 and itself. If it is, the answer is "Yes," otherwise, it's "No."

Example 2: The problem of whether a given number is a prime number. This is a simple decision problem where we check if a number is divisible by 2. The decision is based on whether the number gives a remainder of 0 or 1 when divided by 2. If the remainder is 0, the number is even, and the answer is "Yes". If the remainder is 1, the number is odd, and the answer is "No".

Example 3: The problem of whether there is any occurrence of "aa" in a sequence X of English alphabets. The problem is asking for a yes/no answer: If "aa" is found anywhere in X, the answer is "Yes". If "aa" is not present in X, the answer is "No".

Search Problems

A search problem involves finding a specific element or path within a set of possibilities. The goal is to locate the desired item or determine that it does not exist.

• Involves finding something.
• Input includes a search space.
• Output is the location or existence of the target.

Example: Finding the location of an element with a given value in an array.

Counting Problems

Counting problems involve determining the number of possible outcomes or combinations. They work on the principle that if an event/decision has A number of choices and another decision/event has B number of choices, then the total number of possible unique combinations would be A × B.

• Involves counting possibilities.
• Uses the counting principle (A × B).
• Can become complex as possibilities grow.

Example: You visit a computer shop to buy a computer system. The vendor asks you to choose one of 4 monitors, one of 2 keyboards, one of 4 computers, and one of 3 printers. How many possible systems can you choose from?

Solution: You must choose 1 monitor, 1 keyboard, 1 computer, and 1 printer. Using the counting principle: Total possible computer systems = 4 × 2 × 4 × 3 = 96

Do You Know?

Brainstorming is where people sit together with open minds to effectively discuss all possible solutions. The idea is to critically analyze every solution and later choose the optimal one for further analysis and implementation.

Intermediate Level

A computing problem is a challenge solved step-by-step using computation, with well-defined input and output. Decision problems require a binary (Yes/No) answer—e.g., "Is this number prime?" Search problems involve finding a specific element or path—e.g., "Find the maximum value in an array." Counting problems determine the number of possible outcomes using the counting principle: if one choice has A options and another has B options, total combinations = A × B. Recognizing the problem type is the first step in designing an appropriate algorithm.

Important Points

• - Computing problem: solved step-by-step using computation.
• - Has well-defined input and output.
• - Three types: Decision, Search, Counting.
• - Decision: Yes/No answer (e.g., prime number).
• - Search: Find a specific element or path.
• - Counting: Determine number of possibilities (A × B).
• - Counting principle: Total = A × B.
• - Brainstorming: Discuss all possible solutions.

Remember

• - Computing Problem: Solved step-by-step.
• - Decision: Yes/No (e.g., Is it prime?).
• - Search: Find (e.g., largest element).
• - Counting: How many? (A × B).
• - Counting Principle: Total = A × B.
• - Brainstorming: Explore all solutions.

Common Mistakes

• - Confusing decision and search problems: Decision asks yes/no; search asks to find something.
• - Forgetting the counting principle: Total combinations = product of choices.
• - Assuming all problems are computational: Some problems are not solvable by computation (undecidable).
• - Mixing up search and counting: Search finds one item; counting counts all possibilities.
• - Skipping problem identification: Identifying the type helps choose the right solution method.

Quick Revision

A computing problem is a challenge solved step-by-step using computation, with well-defined input and output. Problems are classified as Decision (yes/no answer, e.g., "Is this number prime?"), Search (finding a specific element or path), or Counting (determining the number of possible outcomes using the counting principle A × B). Identifying the problem type helps in selecting the right computational approach. Brainstorming is a useful technique for exploring possible solutions.

60-Second Revision

• Computing Problem: Solved step-by-step, well-defined input/output.
• Types:
• - Decision: Yes/No (e.g., Is it prime?).
• - Search: Find (e.g., largest number).
• - Counting: How many? (A × B).
• Counting Principle: Total = A × B.
• Brainstorming: Discuss all possible solutions.
• Key Point: Identifying the problem type helps choose the right solution approach.