2.2 Identifying a Computing Problem

In computer science, a problem is a challenge or situation that needs to be overcome using some action. 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 be satisfied.

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. Figure 2.1 visually illustrates a simple decision problem. In complex cases, answers extend beyond a straightforward Yes-or-No, involving multiple decision factors and criteria.

The examples of simple decision problems are:

• The problem whether a given number is odd (or even).
• The problem whether a given number is a prime number.
• The problem that is there any occurrence of "aa"? in a sequence x of English alphabets.

Search Problems:

In science and engineering, many problems are solved using search. In such types of problems, we have a set of objects among which we search for the solution. For example, finding a path between two cities. Search problems are often represented using graphs, where we have nodes and each link connects two nodes. A node can be connected to multiple nodes.

To solve such problems, we have three things:

• Initial State: Represents the node from where we need to start the search.
• Operations: Represents the moves that transition from one node to another.
• Goal: Defines the target or end condition.

Examples:

• Route Finding Problem: The map shown in Fig. 2.2 corresponds to a graph, where the nodes are assumed as cities and the links between nodes represent the routes between cities. The problem is to find a route in the graph from city S to city T.
• Eight Puzzle Problem: A 3x3 board is given that contains 8 tiles (each tile containing a number ranging from 1 to 8) and one empty space. The goal is to place the numbers on tiles in a specific ordering that matches the final configuration using the empty space. However, only one tile can be moved at a time, and only four types of slides are allowed (left, right, above, and below).

Counting Problems:

These problems 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 AxB.

Let's solve counting problems.

Example:

One event is numbers of shirts, and another event is number of pants you own then how many pairs of shirts and pants you can make from it.

Solution:

Total possible casual dresses = (number of shirts) x (number of pants).

Total casual dresses = 5 x 3 = 15

The counting problems are normally seen as an easy task that can immediately be done. As we go deeper, the counting problems can get complicated very quickly if we want to list out all of the possibilities.

Example:

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

Solution

You must choose 1 monitor, 1 keyboard, 1 computer and 1 printer. The below given diagram shows each component of the computer system with the number of choices you have.

For the computer system elements, we have 4 monitors, 2 keyboard, 4 computers and 3 printers. Using the counting principle, the number of all possible computer systems that you can buy is given by:

N = 4 x 2 x 4 x 3 = 96

2.3 Problem Solving

Problem solving defines the process of analyzing some situation and accordingly behaving to generate some response. For simple problems the following 4 steps are used:

• Define and analyze a problem: What is the problem and why it is happening.
• Design a plan: What we are going to do (Algorithm)
• Implement the plan: Code it by using some programming language.
• Evaluate: did our plan work?

However, for complex problems, the 6 step problem solving process could be used:

• Define and analyze a problem
• Decompose the problem: make sub-problems that are manageable
• Identify potential plans for each sub-problem: such as plan A, plan B and plan C
• Select and design best plan
• Implement that plan
• Evaluate

Before jumping into an action for a problem, it must be thoroughly investigated capture all the relevant aspects of the problem. For this purpose, we properly define ar analyze a problem. In defining a problem, there must be clarity and the objectives of the problem must be specified.