Difference Between a Problem and an Algorithm

Difference Between a Problem and an Algorithm

Unit 2: Computational Issues and Algorithms

Learning Outcomes:

After this unit, students should:

  • understand the basic terminologies: computational problem solving, algorithm, flowchart, debugging, testing, variables, value, assignment
  • be familiar with the algorithm to discover the maximum among a listing of numbers
  • be able to trace through flowcharts and updates of variables, and contend if a given algorithm is correct or incorrect

Computational Problems

And so, what is computational problem solving? Let’s start with the question, what is a
computational trouble?

A computational problem is a problem that tin be solved stride-by-step with a reckoner. These bug ordinarily accept a well-divers input, constraints, and atmospheric condition that the output must satisfied. Here are some types of computational bug:

  • A
    conclusion problem
    is one where the answer is yeah or no. For instance, “given a number
    northward, is
    n
    fifty-fifty?” is a conclusion problem. Some decision problems take more steps to solve than others. For instance, “given a number
    n, is
    n
    prime number?” takes more steps than just checking the parity of a number.

  • A
    search trouble
    is one where the solution consists of one or more values that satisfies a given condition. For case, nosotros may want to compute a path from i geographical location to another on a map.

  • A
    counting trouble
    is ane where the answer is the number of solutions to a search problem.

  • An
    optimization problem
    is one where the solution is the “best” possible solution, where the “best” tin be defined in a different manner. For example, we may want to compute the fastest route from one location to another.

Questions such equally “what is the significant of life?” “practice I look good in this outfit?”1
are not computational bug, because they do non have well-defined input, constraints, and conditions that the output must satisfy.

In CS1010 (followed past CS2040C and CS3230), you will acquire how to solve computational problems
computationally
— this means that you larn to come upwardly with stride-past-pace instructions meant for computers that y’all tin translate into figurer programs, to solve a given problem.

Case: Finding the maximum

Let’due south start with a uncomplicated trouble. Given a finite list

50

of

k

integers (
k

> 0), find the integer with the maximum value from the list.

Starting time, permit’due south consider if this is a computational problem. The input is very well defined. We know what an integer is. We are told we have at to the lowest degree i, and we have a finite number of them2.

Second, let’s consider the output. What conditions must the output satisfy? First, it has to exist equal or larger than every other integer on the list. Second, it must be an integer
in
the listing. This is well defined past the problem argument, and then we can say that it is a computational problem.

Hither is an example. Suppose the input consists of:

4 1 -4 0 9 nine 3 v 8

The output should be
9.

At present, you should interruption reading and retrieve about how you would solve this step-by-step.

Algorithm

One way to solve this problem is to cheque through the integers in the list, one-by-i, and keep track of the maximum value so far. When you reach the finish of the listing, your “maximum value so far” volition also be the maximum for the whole list.

Popular:   Standard Deviation Measures _____ Risk While Beta Measures _____ Risk

Permit’s expect at an case:

Integers Scanned Maximum And so Far
iv 4
4 ane 4
4 1 -4 4
4 1 -4 0 iv
iv ane -iv 0 9 9
4 1 -4 0 nine ix nine
4 1 -4 0 9 9 3 9
4 ane -4 0 nine ix iii 5 9
4 1 -4 0 nine 9 3 5 eight 9

The English description above, however, is not detailed plenty for computers to sympathise. What is the significant of “check i-by-one”? “go along track of maximum so far”? how to tell if nosotros have reached “the end of the listing”?

Permit’due south work out all the details.

First, we need a curtailed fashion of representing the integers in the list. Borrowing from mathematical notation, let’due south say that the list

L

contains the integers

l_0, l_1, …, l_{k-ane}
. To “check one-by-one,” nosotros introduce some other notation

l_i
, which is the integer currently being “checked”. Nosotros begin with

i = 0
, then

i = 1
, then

i = 2
, etc, until

i = k-1
. At every stride, we increment

i

by 1.

Second, we demand a concise way of keeping track of the maximum so far. We innovate another notation,

m
, to represent the maximum value so far. When

i = 0
,

grand = l_0
. Since nosotros just scan a single integer, it has to be the maximum. When we bank check some other integer

l_i (i > 0)
, only two things can happen:

  • if this

    l_i

    is larger than

    m
    , then

    l_i

    has to be the maximum so far, so we update

    m

    to be

    l_i
    .
  • if

    l_i

    is equal to or smaller than

    m
    , and so

    one thousand

    is withal the maximum value so far.

We proceed doing the above and increase

i
, until we reach the finish of the list when (later on increasing

i
) we detect that

i

is

grand
.

Now, we have enough details to describe footstep-by-step, how to find the maximum value from a listing of integers. Such steps, which the calculator can take to solve a problem, is called an
algorithm.

Flowchart

In that location are different ways ane tin depict an algorithm. The easiest way I discover is to use a diagram chosen a
flowchart. The flowchart for the algorithm above looks like this. A diamond box represents a “question” that can exist true or false (yes or no), and we trace through the “menstruum” step by footstep, following the corresponding path depending on the reply.

Please spend some time to trace through the walkthrough to a higher place. The snapshot of the values of the

i
,

l_i
,

k
, and

m
, at the point after “is

i

equals

k
” is shown in the table below
(except for the starting time row, which shows the value only before entering “is

i

equals

1000
“)
.

Integers Scanned
i

l_i

k
Maximum So Far (
m
)
4 ane
4

1
9 4
4 1 1 1 9 iv
iv 1 -4 2 -4 9 iv
four 1 -4 0 3 9 4
four one -4 0 ix 4 nine 9 four
4 1 -4 0 9 9 5 ix 9 9
iv 1 -4 0 9 9 3 6 3 9 nine
4 ane -4 0 9 9 three 5 7 5 9 ix
4 1 -four 0 ix 9 3 5 8 8 8 9 9
4 one -4 0 9 9 3 5 8 9 9 9

Variables

In that location are a few important things to take annotation here.

chiliad
,

i
,

chiliad
, and the list

L

are what we called
states
or
variables. While in the above, we tin think of them as mathematical variables which we can assign
values
to, in a computer program, a variable is a location in the memory which holds a value.

Popular:   People Who Buy Stock in a Company Are Known as

We can perform two very basic operations on the variables: reading and writing. In other words, nosotros can ready their values and nosotros can recollect their values.

Nosotros can
assign
the value of one variable to a constant (e.g., set

i

to one) or to the value of some other variable (e.g., set

m

to

l_i
). In the latter example, we first read the value of

l_i
, from

l_i
‘southward memory location and and so we write that value to the memory location of

one thousand
. Once written, the value of

chiliad

will not change until the adjacent time we update the value of

m
.

It is important to annotation that, when

i

changes,

thou

does not alter automatically
to the new

l_i

This behavior is dissimilar from that which yous may be familiar with in spreadsheet software — if you lot set the value of a cell, say
A1
to exist
=B1, when the value in cell
B1
changes, the value
A1
besides changes automatically.

We tin also compare the values of ii variables. We see two examples higher up: “
i

equals

k
?” “
l_i > chiliad
?” When nosotros compare, we read the values of the variables from their retention location and checks their relations.

Nosotros can perform arithmetics operations on the variables: addition, subtraction, etc. We see one example in a higher place: “increase

i
“. This operation is actually an assignment performance in disguise. Nosotros can write it as “ready

i

to

i

+ 1″. Hither, you see that

i

is referred to twice. This operation reads the value from the memory location of

i
, adds 1 to it, and then writes the resulting value dorsum to the location of

i
.

Bugs

If you follow the execution of the algorithm above, step-past-step, using the example input
4 1 -4 0 9 9 3 5
above, you volition obtain the right maximum value

chiliad

of
9. But does that hateful that the algorithm is correct? The answer is NO.

For an algorithm to correctly solve the given problem, it has to produce the right outcome for all valid inputs to the problem. If we can observe one counterexample, i input where the algorithm does not produce the correct output, then the algorithm is incorrect. Note that I say
does not produce the correct output, which means that either the algorithm
produces the wrong output
or
does not produce any output at all.

In this example, we say that the algorithm or the program has a
problems. A bug is a defect that causes the algorithm to behave incorrectly. As a software developer, you will spend some time finding bugs in your lawmaking, a process known as
debugging. A
debugger
is a tool that helps programmers detect bugs in their code.

Before nosotros fifty-fifty start the process of debugging, nosotros first have to know if our algorithm is right. Think that an algorithm is correct only if it produces the right output but all possible valid inputs. And so, one way to bank check if an algorithm is correct is to try it with all possible valid inputs. For the problem we are solving in a higher place, however, even though the listing is finite, there are infinitely many possible inputs, and then, it is impossible to try all possible valid inputs. In practice, nosotros
craft
a smaller set of test inputs to cheque if the algorithm behaves correctly for these test inputs, and
hope
that information technology is right for all possible inputs. With experience, yous will cull the right ready of exam inputs to maximize that chances that you will find a bug in your code. At that place are likewise systematic ways of deriving exam cases and so that the test cases
cover
unlike paths of execution of the algorithm, only we won’t be covering it in CS1010iii.

Popular:   Which is an Example of a Positive Incentive for Consumers

Another way of checking if an algorithm is right, is to reason about the behavior of the algorithm. We will do this rather informally in CS1010, starting in 1-two lectures from now. You get to rigorously prove that an algorithm is right in a college level module (CS3230 Design and Analysis of Algorithms).

Finally, even if an algorithm is correct, the corresponding plan might not exist. Think that an algorithm is a pace-past-step process to solve a trouble. It is what you desire your program to exercise. Yous even so have to write a programme (in C, or other languages) to actually accept the computer practice what you want it to practice (in other words, to
implement the algorithm). This process of translating the algorithm to a computer program, chosen
coding
may introduce bugs as well. Only we will worry about this afterwards when we larn to program.

In the problem set up at the finish of this lecture, you will meet slight variations of the algorithm above. Y’all should cheque through them to see whether they are correct or not.

Problem Set

Problem 1.ane

The following algorithms are slight variations of the ane in the notes above. The differences are highlighted in red. Do they correctly discover the maximum integer from a finite list of

k

integers (
g > 0
)?

If an algorithm is buggy, requite a counter-instance where the output is incorrect. In addition, give an example input where the algorithm nonetheless produces the correct output, where possible.

(a).
Flowchart

(b).
Flowchart

©.
Flowchart

(d).
Flowchart

(e).
Flowchart

Trouble 1.2

Change the algorithm to a higher place to find the minimum value instead of the maximum value from the given list

L = \{l_0, …, l_{thousand-1}\}
.
You can too assume that the list

L

is finite and

k > 0

for this question
.

Problem 1.iii

Draw the flowchart for an algorithm, that takes in a list of integers

50 = \{l_0, …, l_{m-1}\}, k \ge 0
, and compute the
sum
of all the integers. Think about what variable(s) do yous need.

Difference Between a Problem and an Algorithm

Source: https://nus-cs1010.github.io/1819-s1/02-algo.html