Introduction to Problem-Solving

INTRODUCTION

problem-solving There is a famous quotation by Steve Jobs, that says, "Everyone in this country should know to program a computer because it guides you to think".

This section itself is explanation enough to say that in order to program an explanation for a problem, you should think in a specific way. And this is what we are going to talk about in this chapter. In this chapter, you will learn about problem-solving, i.e., analyzing a problem, designing algorithms using tools like flowcharts and pseudocode, and problem-solving using decomposition. So, let us begin...

What is an algorithm?

An Algorithm refers to a sequence of instructions, a finite set of commands, or a method of working. It can be represented as a sequence of instructions to be carried out until an endpoint is reached as per the rules, conditions, or sequence by which the computer or people tackle a problem or situation.

What do you understand by analyzing an algorithm?

Problem analysis is an important phase as its success leads to the final solution. In problem analysis, the following things are carried out :
1. identifying processing components.
2. Identify the relationships among processing components.

PROBLEM-SOLVING CYCLE

Programs are not quick creations. In order to make efficient and effective programs, you should assume a proper problem-solving methodology and use proper techniques. In fact, problem-solving methods follow a cycle - the problem-solving cycle. In the coming lines, we are going to discuss the same

What are conditionals? When they are required in
a program?

Conditionals are the statements that test a condition.
Conditionals are required in a program where the control has to take a different flow of action depending upon a condition's result.

Broadly problem-solving requires four main steps:

1. Identify and analyze the problem.
2. Find its solution and Develop an algorithm for the solution.
3. Code the solution in a programming language.
4. Test and Debug the coded solution.

And finally, implement and maintain it.

Steps in the Problem-solving cycle.

The above-mentioned steps are four major steps in a problem-solving cycle. Each step contains many sub-steps. Let us talk about these sub-steps in order to understand the problem-solving cycle. The aim of a problem-solving cycle is to create a working program for the solution.

1. Understand the problem well	It is very important to understand the problem minutely because sometimes the problem is not what appears but something else that is causing it.
2. Analyze the problem	problem analysis is very important as the outcome of this will convert to the success of the final solution. While analyzing,  i. identify processing components and  ii. identify the relationships among processing components.

Analyze the problem

Think of possible solutions	As per the problem analysis, think of possible solutions by trying this: i. think of different ideas for solutions ii. check your ideas for aptness iii. finally, zero on the most appropriate solution.
Follow a Modular approach while designing a most appropriate solution	Many small logically related modules or functions must be preferred over a big problem. It is called the Modular approach wherein we divide a big program into many smaller and more manageable and understandable modules. Design the final program by i. deciding step-by-step solution ii. breaking down the solution into simple steps.
Identify operations for the solution	Program coding involves the identification of constituent operations required to get the desired output. One must decide about the minimum but simple operations required. Identify i. minimum number of inputs required ii. arithmetic and logical operations required for solutions iii. simple and efficient data structures suiting the need.

Developing the algorithm

Code program using appropriate control structures

The next step is to code the program as per the findings of the previous step. Coding is the technological word for writing the program. This step is to solve the algorithm into a programming language. You should use the most proper control structures out of the available options. Thus, it is important to know the working of different control structures and their suitability in different conditions. i. Use appropriate control structures such as conditional or looping control structures. ii. Think program's efficiency in terms of speed, performance, and effectiveness.

Coding

Test and Debug your program	Testing is the process of finding errors in a program and debugging is the process of correcting errors found during the testing process. Thus, this phase involves : i. finding errors in it. ii. rectifying the errors.
Complete your documentation	Documentation is intended to allow another person or the programmer at later date, to understand the program. Documentation might also consist of a detailed report of what the program does and how to utilize the program.

Testing and debugging

Implement your code	After testing and documentation, implement your program for actual use on-site. Now, real users can use your programs.
Maintain your program	Maintaining programs involves modifying the programs to remove previously undetected errors, enhance the program with different features or functionality, or keep the program up-to-date as government regulations or company policies change.

Implement and Maintain

Problem Solving using Decomposition

The previous section talked about the problem-solving cycle. The first five steps of the problem-solving cycle are very important as the rest of the steps are based on them. The first five steps involve understanding the problem, analyzing it, and thinking of possible solutions with sub-module and operations in it. All this is effectively carried out using decomposition. Let us know what decomposition means.

How do you implement Decomposition while problem-solving?

Decomposition is implemented by dividing the main algorithm into functions. The constructs each function independently of the main algorithm and other functions. Finally, then the algorithm is constructed using the functions. When we use the functions.
It is enough to know the specification of the function without knowing how the function is implemented.

Decomposition is the process of breaking down big or complex sub-processes to allow us to describe, understand, or execute the involved:

1. Splitting a task into a series of subtasks.
2. Identifying components or parts of a complicated system.

decomposition

The method of breaking down a big or complex issue into a set of smaller sub-processes in order to understand a problem or condition better is known as decomposition.

Identifying elements or parts of a complicated system

Consider some examples of decomposition :

• Everyday example. Making cookies is a complicated task that can be broken down into shorter, simpler tasks such as mixing up the dough, including into figures via cookie cutters and baking.
• Academic example. Writing an essay is a difficult task that can be broken down into smaller tasks such as developing a thesis, collecting evidence, and making a bibliography page.
• Engineering example. Designing a solution to construct a bridge by considering site conditions, the technology available, the technical capability of the contractor, foundation, etc.
• Computer Science example. Writing a computer program/software by determining a well-defined series of smaller steps (mostly in the form of modules and functions) to solve the problem or achieve the desired outcome.

 

(EXAMPLE-1) Decompose the task of creating a mobile app

SOLUTION:-

To decompose the task of creating a mobile app, we would need to know the answer to a series of smaller problems.

• what kind of app is to be created?
• who the mark audience for the app is.
• what the user interface of the app will be (what all screens, type of input, etc.)
• what the app's graphics will look like.
• what audio will be included?
• what software/ platform will be manipulated to create the app?
• how the user will navigate the app.
• what different services will be required for the app, e.g., database etc?
• how the app will be tested.

This list has broken down the complicated problem of making an app into much simpler issues that can now be worked out.

Need for Decomposition

Decomposition is the method of breaking a large issue into more manageable sub-problems. It is very important to decompose a problem into smaller sub-problems, the reason being that large problems are disproportionately harder to solve than smaller problems. It's much easier to write two 500-line programs than a single 1000-line program. The larger a problem is, the harder and more difficult it is to program as compared to a smaller problem (see figure).

Once you know how you can decompose a problem in smaller steps, you can create its solution by designing algorithms for it

NΟΤΕ

Decomposing a problem into smaller sub-problems is important because large problems are disproportionately harder to solve than smaller problems.

Decomposing

Problem-Solving Cycle

What are testing and debugging?

Testing is the process of finding errors in a program and debugging is the process of correcting errors found during the testing process. Thus, the testing and debugging involve:
1. finding errors in the program.
2. rectify the errors, which have been found.

DESIGNING ALGORITHMS

Computers are essentially problem-solving devices. Computers solve these problems by dividing the problems into simple and small steps that are expressed in the form of computer instructions.

The set of rules that specify how a particular problem can be solved in a limited number of steps is known as an algorithm. An algorithm is comprised of a finite set of steps, each of which may need one or more operations. But there are specific conditions to be placed on the type of operations as algorithms can contain.

These are:

Each operation must be definite	i.e., it must be clearly defined what should be done. For instance, 'x = 6/0, 'add 3 or 8 to a' are not permitted as these operations are not clearly defined.
Each operation must be effective	i.e., each step must be such that it can be done using pencil and paper in a finite amount of time. For example, arithmetic on integers is an effective operation, whereas arithmetic on real numbers is not since some values may be expressible only by an infinitely long decimal expansion.
Each operation must be finite	i.e., the algorithm should terminate after a finite number of operations.

Thus, we can say that a good algorithm must have characteristics listed in the following sub-section.

Characteristics of a Good Algorithm

In order to be an effective algorithm, an algorithm must have the following characteristics :

1. Precision. An algorithm should be precise, i.e., its steps should be precisely defined.
2. Uniqueness. Every step should uniquely contribute to the algorithm. It means that the result of a step is unique and it is only dependent on the input and the result of the preceding steps.
3. Finiteness. An algorithm must be finite. It must not repeat the steps endlessly. The algorithm must stop after a finite number of instructions have been executed.
4. Input. An algorithm requires a specific type of input to work upon.
5. Output. An algorithm produces output as per the stated objectives and the input it has received.

Components of an Algorithm

An algorithm clearly identifies the following components:

1. Input - the inputs and the type of inputs required by the algorithm. A user can provide the inputs or can be self-obtained too, such as reading from a file.
2. Processing - what and how the processing would use inputs to produce the desired output.
3. Output - the output expected from the algorithm. The objective of the algorithm.

NOTE

One must be able to identify where inputs, processing, and outputs are taking place within an algorithm.

A program is the manifestation of an algorithm in a programming language. Therefore, the success of a program relies upon the algorithm. Therefore, the logic of the problem must be clearly expressed in the algorithm. The logic of the problem can be expressed in various manners. One of the most preferred methods is the graphical method of representing the problem's solution, which is known as a flowchart.

Another useful tool for designing algorithms is pseudo-code. In the coming subsections, we are talking about both these tools.

Flowcharts

A flowchart not only pictorially displays the sequence in which teachings are carried out in an algorithm but also is used as an aid in developing algorithms. One must be friendly with such an important tool used in programming. This section shortly discusses the technique of flowcharting.

Flowcharts

A flowchart is a pictorial representation of step by step solution to a problem.

Different flowchart symbols carry extra messages and are used for extra purposes. These symbols are shown below:

various flowchart symbols that carry different messages

The following section illustrates the working and use of flow charts along with algorithm development.

Writing Algorithms

To write algorithms, such a language should be used that is close enough to the programming language(s) (in which the programs are to be written) so that a hand translation is relatively easy to accomplish. Thus, we have chosen a language for algorithms that resembles our programming language Python.

Let us discuss certain rules for writing algorithms:

Identifiers

Identifiers are the names given to various components of a program by the programmer e.g., to variables that hold values, functions, modules, etc.

While choosing names for identifiers, make sure that these are meaningful and not unnecessarily long or short names.

Assignment

The assignment of values to variables is done through assignment statement as :

            variable <--   eg..        A<--10

In an algorithm, the left arrow (←) denotes the act of assigning the value of its right-hand side to the variable on its left. Some people take liberty and use the assignment operators to assign values to variables in algorithms.

Sequence

The steps of an algorithm are executed in the sequence of top to bottom. One after another so steps must be listed in the correct order.

Selection/Conditional Statements

A conditional statement in an algorithm takes the following form :

There may be one or more if-then-else statements embedded in another if-then-else statement. depicts conditional statements pictorially.

The conditional If statements

Repetition - Looping Statement

A looping statement (also called an iteration statement) lets you repeat a set of statements depending upon a condition. To accomplish iteration, the for loop and while loop is used.

for looping statement

for item in sequence :       :   St          #block of statements :

St represents the set of statements to be repeated for each item in the sequence. When the statements block gets executed for each item in the sequence, the for-loop stops.

while looping statement

while condition :       :   St            # block of statements :

St represents the set of statements to be repeated. The while iteration statement tests the condition before entering into the loop. Thus, if the condition is false even before entering into the loop, the while-loop will never get executed.

Let us now consider some examples of algorithms and flowcharting.

(a) for the loop process.

(b) while loop processing