2.1 Problems

This topic introduces the concept of a problem in computer science and explains how problems are categorized for computational solving.

Definition

Problem: A problem is a challenge or situation that needs to be overcome using some action. In computer science, a problem is a challenge or situation that needs to be solved using computation.

Core Concept

A problem is any situation where there is a gap between the current state and a desired state. In everyday life, problems range from simple (deciding what to eat) to complex (designing a bridge). In computer science, a problem is something that can be solved step-by-step using computation—whether through arithmetic, logic, or data processing. Understanding the type of problem helps determine the best approach to solve it.

Detailed Explanation

What is a Problem?

In computer science, a problem is a challenge or situation that needs to be overcome using some action. It can be anything that requires a solution, from a simple arithmetic calculation to a complex logistical challenge.

• A problem has a current state (what exists now) and a desired state (what we want).
• The gap between these states is what needs to be overcome.
• In computing, problems are solved using computation—a sequence of steps that transform input into output.

Types of Computing Problems

In computer science, computing problems are generally classified into three categories:

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.

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.

Counting Problems: These 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.

Examples of Computing Problems

Decision Problem Examples:

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".

Counting Problem Example: You visit a computer shop to buy a computer system for yourself. 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, the number of all possible computer systems you can buy is: 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

In computer science, a problem is a challenge that can be solved using computation. Problems are classified into three types: Decision (binary yes/no answer, e.g., "Is this number prime?"), Search (finding a specific element or path, e.g., "Find the maximum value in an array"), and Counting (determining the number of possible outcomes, e.g., "How many combinations are possible?"). The counting principle states that if one event has A choices and another has B choices, the total combinations are A × B. Understanding problem types helps in selecting appropriate algorithms and computational strategies.

Important Points

• - A problem is a challenge that needs to be overcome.
• - In computing, problems are solved step-by-step using computation.
• - Three types: Decision, Search, Counting.
• - Decision problems: Yes/No answer.
• - Search problems: Find a specific element or path.
• - Counting problems: Determine number of possible outcomes.
• - Counting principle: A × B combinations.
• - Brainstorming helps explore possible solutions.

Remember

• - Problem = Challenge to overcome.
• - **Decision** = Yes/No (e.g., Is it prime?).
• - Search = Find something (e.g., largest number).
• - **Counting** = How many? (e.g., A × B).
• - Counting Principle: Total = A × B.
• - Brainstorming = Discuss 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).
• - Thinking a problem is only mathematical: Problems can be logical, spatial, or data-driven.
• - Skipping problem classification: Identifying the type helps choose the right solution method.

Quick Revision

A problem is a challenge that needs to be solved. In computer science, 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). Understanding problem types helps in selecting appropriate computational strategies. Brainstorming is a useful technique for exploring possible solutions.

60-Second Revision

• Problem: Challenge to overcome.
• 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.