Introduction to Problem Solving

Written and reviewed by Rohit Singh, Computer Science & Commerce faculty at UniDrill (MCA, Osmania University · 6 years teaching). Based on NCERT Computer Science Class XI, Chapter 4.

A computer cannot solve a problem. You can.

Booking a train ticket from your phone looks like magic. Behind it is a huge task: many trains, many types of berths, a schedule, and thousands of people booking at the same moment. A computer handles it only because someone first worked out, in exact steps, how to handle it.

That is the main message of this chapter: a computer cannot solve a problem by itself. We must give it precise, step by step instructions. Whether a computer succeeds depends on how correctly we define the problem, design the solution (an algorithm) and implement it (a program). The correctness of the output depends on the correctness of the input, a rule summed up as GIGO, garbage in, garbage out.

The cycle in one line: analyse the problem → develop an algorithm → code → test and debug → maintain.

The steps of problem solving

When a car starts making a strange noise, a mechanic first finds where the noise comes from, makes a plan, and then repairs it. Solving a problem on a computer follows the same logic.

During testing, a syntax error means no output at all, while a wrong output points to a logical error. Industry follows standard testing methods such as unit (component) testing, integration testing, system testing and acceptance testing. A program must meet the user's needs, respond within the expected time, and give correct output for all possible inputs.

Algorithm: the recipe

An algorithm is a finite sequence of exact steps that leads to the desired result in a finite amount of time, if followed correctly. Like a recipe, it has a definite beginning, a definite end and a finite number of steps. The word comes from the name of the Persian mathematician Al-Khwarizmi (about 850 AD), whose name became "Algorithmi" in Latin.

Worked example: GCD of 45 and 54. The greatest common divisor is the largest number that divides both.

Why do we need an algorithm? A programmer needs a roadmap before writing code, otherwise the program may not work as expected. Search engines, messaging, online banking and taxi booking all rest on algorithms. If the algorithm is correct, the computer runs the program correctly every time. This increases the reliability, accuracy and efficiency of getting solutions. While writing an algorithm you identify three things: the input to be taken, the processing to be done and the output wanted.

Pause and predict: what happens if an algorithm does not stop after a finite number of steps?

Check your answer: It never produces its final output, so it fails the finiteness test and isn't an algorithm at all. A loop whose condition can never become false is the usual cause.

Representing an algorithm: flowchart and pseudocode

An algorithm is written down in one of two ways, and in either case it should show the logic without implementation details and make the flow of control clear.

A flowchart is a diagram of shapes joined by arrows. Each shape is a step and each arrow shows the order.

Pseudocode ("not real code") is an informal, human readable description of the instructions in order. It cannot be run by a computer and there is no standard for writing it. Common keywords are INPUT, COMPUTE, PRINT, INCREMENT, DECREMENT, IF/ELSE, WHILE and TRUE/FALSE. Writing pseudocode first protects a programmer from leaving out an important step, and lets non-programmers read the plan and confirm that it gives the desired output.

Worked example: square of a number. Identify the input, process and output first: input a number, process by multiplying it by itself, output the square.

For the sum of two numbers the pseudocode is INPUT num1, INPUT num2, COMPUTE Result = num1 + num2, PRINT Result. For a rectangle:

Flow of control: sequence, selection, repetition

The flow of control is the order in which the steps of an algorithm happen.

Selection. A condition is either true or false, and the program does different things in each case. In actual programs the "otherwise" is the else keyword, giving an if-else block.

Worked example: odd or even.

MOD gives the remainder, so an even number has remainder 0 when divided by 2. In the flowchart a diamond asks whether the remainder equals 0, and the two branches lead to two print boxes.

Worked example: child, teenager or adult. Child is below 13, teenager is 13 or more but below 20, and adult is 20 or more.

The tests run top to bottom and stop at the first true one. That is why the second test does not need to say "at least 13": a person reaching it is already known to be 13 or more.

Common wrong step. Writing the tests in the wrong order, for example testing Age < 20 first. Then a 5-year-old would be called a teenager, because the first test catches everyone below 20.

Worked example: the card game Dragons and Wizards. Rules: a diamond or a club gives Team DRAGONS a point; a heart that is a number gives Team WIZARDS a point; a heart that is not a number gives DRAGONS a point; any other card gives WIZARDS a point. The team with more points wins.

Trace five cards through the conditions.

Dpoint 3 beats Wpoint 2, so the dragons win. The pseudocode as given has a gap that a dry run exposes. If both teams finish with equal points, the last IF is false and it prints that the Wizard team wins, although neither team has won. The algorithm needs a third case for a tie.

Repetition. A loop repeats some statements until a condition is satisfied. A counter variable keeps track of the number of repetitions and is increased after each pass, until it reaches the set number. When the number of repetitions is not known in advance, the WHILE construct is used.

Worked example: average of 5 numbers (known count).

Trace table for the inputs 4, 8, 6, 2 and 10.

Now count is 5, the condition count < 5 is false and the loop ends. The average is $30 / 5 = 6$.

Worked example: average until the user enters 0 (unknown count).

Take the inputs 6, 7, 4, 8, 2, 5, 0, 3, 1.

The sum is 32 and the count is 6, so the average is $32 / 6 \approx 5.33$. The 3 and the 1 after the 0 are never read. The first INPUT before the loop gives the test something to look at, and the second INPUT at the end of each pass reads the next value. Dividing by count (not by a fixed number) is what makes it work for any number of inputs.

Common wrong step. Giving 0 as the very first input. The loop never runs, count stays 0 and the algorithm divides by zero. A dry run with this input shows the gap, so the algorithm needs a check for count == 0.

Checking an algorithm: the dry run

A faulty program can do damage: imagine a money transfer module that credits only half the amount, or debits instead of crediting. Software for hospitals and space missions must work in every situation. So before coding, you check the algorithm by taking sample inputs and going through every step by hand, which is called a dry run. A dry run helps you to identify incorrect steps and to find missing details. You choose inputs carefully, because a program that is not tested on all kinds of input will fail on the one you missed. It is also cheapest to fix a mistake at this stage.

It is just like checking the formula for the sum of the first $N$ natural numbers, $N(N+1)/2$. For $N = 6$ we get $1 + 2 + 3 + 4 + 5 + 6 = 21$ and $6 \times 7 / 2 = 21$.

Worked example: adding two journey times. Time from A to B is hh1 hours and mm1 minutes, and from B to C is hh2 and mm2. The first version adds hours to hours and minutes to minutes.

The second input shows that the algorithm works only when mm_total < 60. The fix is to add one test after the additions.

The same dry run now gives $6 + 1 = 7$ hours and $70 - 60 = 10$ minutes.

Worked example: boundary values. An algorithm classifies a number as "Single Digit" if Number < 9, "Double Digit" if Number < 99 and "Big" otherwise. Test it on 5, 9, 47, 99, 100 and 200.

The two failures happen exactly on the boundaries 9 and 99, because < leaves out the boundary itself. The fix is Number <= 9 and Number <= 99. Always test the boundary values of every condition, and values just on either side.

Worked example: a range check. An algorithm accepts a number if 0 <= Number AND Number <= 100, meant for positive integers up to 100. It wrongly accepts 0, since 0 is not positive, and it accepts fractions like 50.5, which are not integers. An improved version tests 1 <= Number, Number <= 100 and that the number is a whole number.

Pause and predict: a student tests an algorithm only with the input 25 and finds the output correct. Is the algorithm correct?

Check your answer: Not necessarily. One input proves nothing about the rest. Test ordinary values, boundary values and unusual values such as 0.

Comparing algorithms: time and space

There can be several algorithms for the same problem. Take testing whether a number is prime. Four approaches:

Worked example: how many divisions to test 97?

All four conclude that 97 is prime, but they differ greatly in the work done. Algorithms are compared on the processing time they need, called time complexity, and the memory they need, called space complexity. Method (iv) buys speed with memory.

Why the square root is enough. If $n = a \times b$ and $a \le b$, then $a \le \sqrt{n}$. So if $n$ has any factor besides 1 and itself, it has one no bigger than $\sqrt{n}$, and you can stop searching there.

Worked example: method (iii) as pseudocode.

The dry run on 1 exposes a bug: the loop never runs, so the answer stays TRUE, though 1 is not a prime. The algorithm needs a first test that n is greater than 1.

Beyond the textbook. For the exam: find the GCD by listing divisors, as in the example above. In reality: the Greek mathematician Euclid described a much faster method: replace the pair (a, b) by (b, a MOD b) until the second number is 0, and the first is the GCD. For 54 and 45: 54 MOD 45 = 9, then 45 MOD 9 = 0, so the GCD is 9 in two steps. Why it matters: it shows that different algorithms for the same problem can differ hugely in effort, which is the point of comparing algorithms.

Beyond the textbook. For the exam: algorithms are compared by time complexity and space complexity. In reality: the trade of memory for speed in method (iv) is everywhere in computing. The cache in the computer system chapter is another case: extra fast memory is spent to save waiting time. Why it matters: there is rarely a free lunch, so the best algorithm depends on which resource is scarcer.

Worked example: a water bill. Charges: the first 100 units at ₹5 per unit, the next 150 units at ₹10 per unit, more than 250 units at ₹20 per unit, plus a meter charge of ₹75 a month.

Common wrong step. Charging all 300 units at ₹20 (₹6000). The rate applies only to the units above 250, as in a tax slab.

Worked example: factorial and Armstrong number. The factorial of 5 is $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$. A three digit Armstrong number equals the sum of the cubes of its digits: 371 is one because $3^3 + 7^3 + 1^3 = 27 + 343 + 1 = 371$.

For the Armstrong test, the loop peels off the last digit with digit = temp MOD 10, adds its cube to a total, and removes it with temp = temp DIV 10 (DIV gives the whole number quotient). For 371 the digits come out as 1, 7, 3 and the total grows 1, 344, 371, which equals the input, so it is an Armstrong number.

Coding

Once the algorithm is final, it is written in a high level programming language by following its syntax, the set of rules, like grammar, that govern spelling, order and punctuation. Machine language of 0s and 1s runs directly on the hardware but is hard for humans. High level languages, such as FORTRAN, C, C++, Java and Python, are close to natural language and easy to read, write and maintain. They are portable: they run on different computers with little or no change, while low level programs run on only one kind of computer. A program in a high level language is source code, and a compiler or an interpreter translates it into machine language.

Choosing a language depends on the platform (operating system), on whether the application is for desktop, mobile or web, and on whether it is for an embedded system such as a digital watch, MP3 player, traffic signal or medical equipment, where specialised tools or assembly language may be needed.

Decomposition: divide and conquer

If a problem is too complex to solve directly, decompose it, that is, break it into smaller sub-problems that are easier to solve, and then combine the solutions in a logical way. The railway reservation system breaks into parts.

Each sub-problem can be studied in detail, solved independently, and handed to a team that is expert in it. Once solved, the parts must be tested for correctness and integrated into the complete solution. Decomposition is used for problems in mathematics and science, event management in a school, weather forecasting and delivery management.

Exam traps

60-second revision

Pseudocode patterns sheet

Where this chapter connects

• Previous: Emerging Trends shows the problems that today's algorithms are written to solve.
• Next: Getting Started with Python is where these algorithms are turned into real programs.
• Control flow in Python: Flow of Control turns sequence, selection and repetition into if statements and loops.
• Class XII link: Searching and Sorting compare several algorithms for one task, exactly like the prime test above.