# Chapter 2

### Problem Solving & Algorithms

# 2.1 Problem Solving in Everyday Life

In everyday life, we perform several tasks that range from simple and automatic (tying shoe laces, brushing teeth, making beds, eating, running) to complex and attention requiring (driving, writing reports, solving problems) depending on our circumstances. While a lot of these tasks are routine and repetitive, some of our daily actions are targeted towards solving particular problems. A problem, in the most general of definitions, can be defined as an obstacle between you and what you need or want to do or achieve. Imagine, for example, driving from your home to your friend’s apartment, who lives across town in a large city like Ankara. Imagine also that it is the rush hour and it is also raining. In the case, the objective is to reach your friend’s house in a reasonable amount of time and the obstacles are the long drive, the heavy traffic and the rain.

**Figure 1.** possible roadmap between the departure and destination points

Figure 1 displays a sketch of a possible roadmaps between the departure and destination points. Under normal weather and traffic conditions, all three paths are equivalent in that they take you between the same two points. Since it is the shortest, you first get on path 1, which is the itinerary you would normally follow. However, you quickly realize that, there is very heavy traffic in the direction you are traveling that will keep you stuck for hours. You turn around and try the next shortest path, namely path 2. Halfway through this path, you see a sign that says that there is a flooded portion of the street up ahead and it is closed to traffic. You turn around one more time and try your last chance, path 3. It turns out that although it is the longest, path 3, under these particular conditions turns out to be the best option because since it is unobstructed, it takes you to your friend’s home the fastest. This simple example illustrates several ideas:

- There are often several ways to reach the solutions of a problem.
- Which solution is the best may depend upon conditions or priorities of the person.
- It is sometimes impossible to know or be able to analyze all the conditions a prior. Therefore sometimes trial-and-error processes are often necessary to find the optimal solution.

# 2.2 Logic and Algorithms

In the context of programming, we refer to the different ways of reaching the same solution logic. The logic that one person follows in solving a problem may be different from that of another person. For example, suppose student A and student B are trying to add 10 numbers from 1 to 10. They are allowed to add only two numbers at a time. Consider the two logics that they follow:

**Student A:**

`sum=0`

`sum=sum+1=1`

`sum=sum+2=3`

`sum=sum+3=6`

`...`

`finalsum=sum+10=`**55**

**Student B:**

`sum1=1+2=3`

`sum2=3+4=7`

`sum3=5+6=11`

`sum4=7+8=15`

`sum5=9+10=19`

`sumA=sum1+sum2=10`

`sumB=sum3+sum4=26`

`sumC=sumA+sumB=36`

`finalsum=sumC+sum5=`**55**

While student A elects to accumulate the sum as the numbers are incremented by one, student B groups them in two and regroups the sums in two. Student A ends up performing 10 addition operations while student B does 9. In this example, the difference between the two logic are marginal due to the simplicity of the problem. As the complexity of the problem increases different paths of reaching the goal diverge. Also, as in the example in Figure 1, different solutions may be preferable under different conditions. In the addition example, the solution that student A has arrived is straightforward but slightly longer. The solution of student B is a little more complicated but faster. In most computational scenarios, this kind of compromise between desirable traits of the solutions (fast vs easy, fast vs low memory cost) is inevitable.

Before actually writing a program, most of the time, we construct a symbolic, step wise chart of the solution called an algorithm. The best way to understand and appreciate what an algorithm is to take an everyday task and describe clearly the steps involved in the procedure. For instance, imagine you encounter a person that has never eaten an apple. You need to give them very clear step wise instructions on how to eat an apple. Here are the elements of your procedure:

### Eating an Apple

**Input:**Apple**Output:**Apple core and seeds**Procedure:****Step 1:**Take the apple in your hand and bring it to you mouth.**Step 2:**Take a bite of the apple and move it about 20 cm away from your mouth.**Step 3:**Chew the bite of apple and swallow.**Step 4:**Rotate the apple by 15 degrees.**Step 5:**If there is apple flesh to bite at the new angle, go to**Step 2**and repeat. If not, go to**Step 6**.**Step 6:**You have finished eating the apple. Stop eating!

**Assumptions:**- The apple was clean and you didn’t have to wash it.
- You were given a full apple and not a partially eaten one. (Does your algorithm break if you are given a partial apple?)
- You have healthy teeth that can handle biting into an apple.

As you see in this example, each task or problem has an input (what needs to be supplied to the program) and an output (what needs to be obtained). The input is taken in by the person (or the computer) and processed through the steps of the algorithm until it turns into the desired output. Something that happens very often in algorithms or real life procedures in general is the repetition of certain actions, in other words loops. In our apple-eating algorithm, steps between 2 and 4 are repeated until the apple is completely eaten. This is an integral part of almost all of the algorithms. In order to determine for how long the algorithm will go on, there must be check mechanism. In this case, that check mechanism is done with an if clause. We check to see if there is still apple to be eaten and if not we quit eating. Finally, your algorithm assumes that certain conditions are met without checking for them. If those conditions are met, your algorithm may break. For instance, if you have dentures, when you bite into the apple, they may dislocate. In that case, you cannot eat the apple. A good algorithm checks to make sure that all assumptions are actually being met before the code is run.

Let us now go over more example of algorithms :

### Make a cheese sandwich

**Input:**Two pieces of bread, block of cheese, cutting board, knife.**Output:**A happy person who just ate a sandwich.**Assumptions:**The person is old enough to use a knife.**The algorithm:**

1. Place the pieces of bread on a flat surface.

2. Place the block of cheese on the cutting board.

3. Take knife in hand.

4. Cut a slice of cheese.

5. Place the slice of cheese on one of the pieces of bread.

6. **Repeat** actions **3**, **4** and **5** until the surface of the slice is covered.

7. Place the other slice on top.

8. EAT.

Once again, this example has three steps that are repetitive.

### Factorial

A more mathematical example is calculating the factorial of a number N. Let us first describe in words how to do that and then form a condensed list. The particular logic we will follow will be to start from 1, increment numbers until you reach N and perform pairwise multiplications.

`In order to find the factorial of a number N, one first checks whether that N is a nonnegative integer. If it is not, we stop. If not, we set the value of a return integer, say, fact, to be equal to 1. The next number is two. We multiply, fact with 2 and reassign the value of fact to 2. The next number is 3. We multiply fact with 3 to get 6, we reassign fact to be 6. We repeat the multiplication action until we reach N. After the multiplication with N, we return the value of fact.`

While accurate, the above description of the factorial is awfully long. A more concisely constructed description could be as follows:

`1. Input an integer (N)`

`2. Let fact=1`

`3. If N > 1 go to step 5, otherwise go to step 8`

`4. fact=fact x N`

`5. N=N-1`

`6. Go to step 4`

`7. Output fact`

This is much simpler, yet we can simplify it ever more by using an flowchart. Figure 2 depicts such a chart for the factorial problem. In Fig. 2, an abstract depiction of the algorithm can be seen.

The choice of the shapes are not arbitrary; they are actually somewhat standardized. The **arrows **depict the direction of the flow of the program, the **oblong shapes** with START and STOP written in them are terminals and delimit the program, the **parallelograms **represent input and output, and the **diamonds **represent decisions. In the flowchart, the loops are also easily seen. For calculating the factorial, other logics may be used. Here are some examples:

`1. Logic 1: N! = N × (N - 1) × (N - 2) × ··· × 2 × 1`

`2. Logic 2: N! = 1 × 2 × 3 × ··· × (N - 1) × N`

`3. Logic 3: N! = N ∗ (N - 1)!`

The final logic where the action includes the factorial itself is called **recursion**. Another way of describing the algorithm is the pseudocode or pseudoalgorithm. A **pseudocode** is a shortened English format for representing the algorithm without going into the details of the particular syntax of a computer language.

**Figure 2.** Flowchart depicting the factorial algorithm

For our factorial program, a **pseudocode** may look like the following:

`GET value of N`

`SET initial value of F to 1`

`SET initial value of X to 1`

`WHILE N>X`

` F=F*X`

` X=X+1`

`ENDWHILE`

`DISPLAY value of F`

Finally, we can cast the pseudocode into an actual code in a suitable computer language. The below example is an **Octave code**.

`function F=fact(N)`

` if ( (N<0) || (rem(N,1)!=0) )`

` printf("N has to be a nonnegative integer. Exiting program.")`

` return`

` endif`

`F=1;`

`X=1;`

`while (X<N)`

` X=X+1;`

` F=F*X;`

`endwhile`

`endfunction `

### Binary Search

This problem has to do with the well-known game of guessing a number that another person has in mind. The progression of the game goes something like this:

- Player 1: I have picked a number between 1 and 15 (She picks 9).
- Player 2: Is it 11?
- PL 1: Lower.
- PL 2: Is it 5?
- PL 1: Higher.
- PL 2: Is it 7?
- PL 1: Higher.
- PL 2: Is it 10?
- PL 1: Lower.
- PL 2: Is it 9?
- PL 1: Yes, you win!

The object of PL2 is to guess the number in as few guesses as possible. There are many ways he can try to do this: he can guess randomly, he can guess in order (first 1, then 2, then 3 etc...) or he can use a well-known algorithm called binary search. In binary search, we always guess the number in the middle of the range of numbers offered. Here is a simple flow of the logic of this algorithm:

- Range : 1-15
- Number picked : 9
**First guess:**Let n_low = 1 and n_high = 15

g1 = n_low + floor(n_high - n_low) / 2 = 8 ➤➤➤ HIGHER

**Second guess:**n_high = 15 still holds while n_low = 8

g2 = n_low + floor(n_high - n_low) / 2 = 11 ➤➤➤ LOWER

**Third guess:**nl = 8 still holds while nu = 11

g3 = n_low + floor(n_high - n_low) / 2 = 9 ➤➤➤ CORRECT

This algorithm truns out to be much faster than both random and sequential guessing, when averaged over many instances of this game. Now, let us write an algorithm in words, that will guess a number given the range:

**Input:**The lower and upper ranges, Nl and Nu**Output:**The correct guess**Assumption:**The numbers in the range are consecutive integers**Algorithm:**

1. Read N_low and N_high,

2. Calculate guess: Ng=N_low + floor(N_high - N_low)/2

3. If Ng is equal to the number picked, Np, go to **step 5**.

If Ng > Np, N_low=Ng

If Ng < Np, N_high=Ng

4. **Repeat** steps 2 and 3.

5. Print "CORRECT!" and exit.

Corresponding flowchart is in Fig. 3.

**Figure 3.** Flowchart depicting the binary search algorithm.

The examples given above are clearly detached from any computer language. Although the particular implementation will be very different between different computer languages, the ideas will be the same. You need not worry about the particulars of the syntax at the moment.

You will learn them as necessary. There are countless examples of different logics being used under different conditions to solve the same problem. An excellent example is given in www.sorting-algorithms.com where different renditions for the famous sorting algorithm are put to test visually for different initial conditions. We recommend that you take a look.