ICT Chp 21,22,23,24Problem-Solving Procedures and Algorithm

ICT Chp 21,22,23,24Problem-solving procedures and Algorithm

Problem-solving concepts

1.What is problem-solving?

Problem-solving is a process of analyzingthedescription of problem until we reach a solution. To solve complex problems, we can divide the problem into smaller parts (i.e. modules) and solve them one by one.

2.Problem-solving procedure

Before analyzing, we have to know exactly what the problem is. So, the first step is:

1.Problem Identification

After that, we should do

2.Problem Analysis

Then, make a draft framework

3.Algorithm Design

Then, try to solve the problem by

4.Developing a Solution

Now, we have a solution, but we are not sure it is workable or not, so, we should perform

5.Debugging and Testing

Finally, a solution is developed, but it is not the end, to make improvement become smooth, we should remarks any

6.Documentation

Algorithm Design –

In the state of Algorithm Design, Pseudocode and Flowchart are two commonly used techniques to do the algorithm.

`will have no standard format (syntax) and so a segment of Pseudocode will have no syntax error but logical error only.

What is syntax error?

JavaScript is a programming language with standard format, so it may result syntax error. E.g.

X = 10;
Y = 20;
Y = 2X;
2X = Y  3; / Syntax error /logical error
How to fix?
document.output(“Who are you?”); / Syntax error /logical error
How to fix?
window.ResizeTo(100,200); / Syntax error /logical error
How to fix?
for (i=0,i<10,i++) {
alert(“hello!”);
} / Syntax error /logical error
How to fix?
for (i=0;i>10;i++) {
alert(“hello!”);
} / Syntax error /logical error
How to fix?

Syntax error / logical error / run-time error

Apart from syntax error and logical error, there is another source of error. It is run-time error. A run-time error occurs when a program crashes. For example,

X = 2;

Y = 3;

Z = (X – Y) / (X + Y – 5);

Obviously, the 3rd line of code will create run-time error. (OR in this case, it is a divided-by-zero error.)

Apart from divided-by-zero error, can you think of any other type of run-time error?

Example:

X = 5;

Y = 10;

WHILE (X > 0) {

X = X + 1;

Y = X*Y;

}

What kinds of error will it create? Select the correct answer:

Infinite Looping/data overflow error/ Out of memory stack error

Compilation (translator / compiler)

So, writing a program should avoid errors include syntax error, logical error and run-time error. As a matter of fact, a program has to be translated into machine code before execution. This process is called compilation.

Below shows the process:

High Level Programming Language / -> Compiler -> / Low Level Programming Language
for (i=0;i>10;i++) {
alert(“hello!”);
} / / 0010001010111000001010100
1010100010000100111111011
1000011000010101010111110
1111111101010001011110...
i.e. / Source program / / Compiler / / Object program

High level programming language is the programming language that human being can understand, example include JavaScript, Java, C++, Pascal, etc.

But for computer, it can only recognize machine code like 10010101 represents delete file, or 11001010 represents create folder, etc. However, since each machine code may be different for different OS (operating system), so, Low level programming language is not portable / compatible.

A compiler is a software program that it will translate a high level programming language into a machine language. So, a compiler should usually be platform oriented (machine dependent).And so, an executable file should be built according to the OS of the computer. So, an executable file should not be portable but the high level programming language may be portable.

Conclusion:

1.Error

-a violation of the grammatical rule of a programming language

-can be checked by the

-eg: wrong spelling of some reserved word, using an unknown variable

2.Error

-it occurs when a program terminates abnormally

-eg: division by zero, out of memory

3. Error

-it is mainly caused by an incorrect

-it produces an result

-it be detected by the translator / compiler

-eg: the calculated average mark of a test is greater than 100

Pseudocode Sample 1:

SET total to zero
REPEAT
READ Temperature
IF Temperature > Freezing THEN
INCREMENT total
END IF
UNTIL Temperature < zero
Print total / Description of the program:

Pseudocode Sample 2:

Input a number N
X <- 1
WHILE (X < N) AND (N < 5)
X <- X + 2
END
Output X, N / State the output of the program with input as
(i)4
(ii)14

Remember, there is no specific syntax for Pseudocode and so it will have no syntax error.

Note that in writing program, logical comparison is very useful and important. Below show some operations:

X = TRUE; Y = FALSE;

NOT X / NOT(NOT Y) / X and Y / NOT X AND NOT Y / (X OR NOT(X AND Y))
TRUE
FALSE

Flowchart is a way to represent the logic and actions of an algorithm graphically.

Flowchart Sample:

Developing a Solution –

It is a top-down approach that divides a complex solution into some manageable subprograms (module).

To develop a solution, usually we would create a program based on algorithm in “algorithm design” stage. That is, theoutput of this stage is a computer program. Below shows two simple programs in JavaScript:

function timeout1() {

var x = 10;

for (i=1;i<x;i++) { alert(i);}

}

function timeout2() {

var Limit = 10;

for (counter=1;counter<Limit;counter++) { // a FOR LOOP to popup a dialogue box.

alert(i);

}

By investigating the above two computer programs, we can find that there are several techniques which are important in programming design.

1.Make good use of comment.

2.Define meaning variables.

3.Proper indent.

4.Modular approach

Other than the above techniques, it is also important to set variables with appropriate data type. There are several data type in programs. They include:

Data type / Example / Description
Real / 2.534, 0, -28 / Decimal numbers
String / ‘abc’, ‘2.354’, ‘28abc’ / Alphanumeric or simply numeric
Integer / 15, 27, 91, -11 / Integer
Boolean / Logical / TRUE, FALSE / Logical data

Note that Real and Integer in real life is unlimited. However, in the world of computer, it is limited by the number of memory allocated to these data. For example, if 8 bits is set for a data type of an integer, then, it ranges –128 to 127 only. As a result, calculation of those data type may cause system crash and it is what we called overflow error or run-time error.

However, as a matter of fact, it is not often to encounter data out of the range, so, there are a number of different data type, for example, INTEGER use 16 bits, LONG INTEGER use 32 bits, etc. The case of real is similar.

Below is an example of a program with two different data types:

x = "12";

y = "34";

z = x + y;

document.write (z + "<br>");

a = pareseInt(x);

b = parseInt(y);

c = a + b;

document.write (c);

</Script>

What would be the expected output?

Exercise:

1.The purpose of adding comments to a program is

A.to evaluate the program.B.to increase functionality.

C.to increase the speed of the program.D.to assist program maintenance. Ans:D

2.The purpose of using meaningful variable names in a program is

A.to make the program more readable.

B.to increase the program development time.

C.to help translating programs into machine codes.

D.to test the program more thoroughly.Ans:A

Debugging and Testing

It is a checking process. Here,“Debugging” refers to the process of locating and fixing defects in a program. “Testing” is to ensure a program works and is free of error.

To test a program, the program itself should have already compiled successfully. That is, it will not contain any syntax error. So, basically, testing focuses mainly on finding out logical errors and run-time error.

To discover logical error, we should test the program with relevant input data and check whether it will give correct output data.

To discover run-time error, then, should we just test the program with relevant input data? Yes / No

If No, then, what else should be used as the input data? Give an example to support your answer.

Irrelevant data should also be inputted to test the program. It is because a
program may not be able to restrict all kinds of input from the user. For example,
a user may input a string into the field “age” in a online survey. Then, it may
make the program crash.

Documentation

It aims to describe in detail what a certain program is for and how it is designed, developed and tested. Although documentation appears at the last stage of the problem-solving procedure, it should be carried out throughout the whole process.

There are two main categories of written documentation for computer programs: user manuals and program manuals.

Function of documentation:

It can help programmers maintain the program in the future.

Other programmers may have to maintain the program or make changes to it at a later time.

It helps programmers discover errors in the program.

Users can learn how to use the program through a user manual like

how to install

what functions are provided by the program

how to handle a particular task, etc.

Introduction to Algorithm Design

Flowchart symbols

Begin / End /
Process /
Input / Output /

Decision /
Pre-defined Process /

Decision box: It has two common features. One is Branching and the other one is Looping.

Branching / IF / Conditional Statement / Looping

Exercise 1:Arrange the following flowchart symbols to form a program that can determine whether an inputted data is an odd number or an even number.

Exercise 2: Arrange the following flowchart symbols to form a program that can find the maximum divisor of a number. (Examples: 27 = 3x9, so, 9 would be the maximum divisor.)

To achieve the goal, we should think how to find a maximum divisor by ourselves. That is, what is the algorithm in our own brain to find the maximum divisor?

Take 27 be the example, the step to find the maximum divisor would be:

Step 1:, Divide 27 by 2, check the remainder.

Step 2: If remainder=0, then 2 would be a divisor.

Step 3: Divide 27 by 3, check the remainder.

Step 4: If remainder=0, then 3 would be a divisor.

Step 5: Do the steps above again and again until it reaches 26 (27 – 1) to find all the divisors.

Step 6: Output the maximum divisor.

To investigate the above steps, you will see it is in fact not 6 steps. It is like infinite steps it does 3 main steps over and over again. These 3 main steps would be:

1: Runs a counter (like 2, 3 and so on) from 2 to 27 – 1.

2: Divide 27 by the counter and check the remainder.

3: Store the divisor when found one.

These 3 main core steps involve repeated operations, we called looping or

Iteration. The structure of a looping by flowchart is shown on the right:

Finish the following flowchart so that it

runs a counter from 2 to 27 –1. It is what

we called a FOR-LOOP.

In JavaScript, it is

For ( ) {

…….}

Finish the following flowchart so that it can let users input a number, then it will output the maximum divisor.

Exercise 3: Create a flowchart so that it can find the H.C.F. of two inputted numbers.

In JavaScript, we can find the H.C.F. in the following manner:

function findHCF() {

var data1 = parseInt(num1.value);//parseInt() is a JavaScript function

var data2 = parseInt(num2.value); //to find the value of a text string

if (data1 < data2) {min = data1;}

else {min = data2;}

HCF_found = false;

for (i=2;i<=min;i++) {

R1 = data1 % i;

R2 = data2 % i;

if (R1 == 0 & R2 == 0) {

HCF = i;

HCF_found = true;

}

if (HCF_found) {

alert (HCF) }

else { alert("No HCF found!");}

}

</script>

<body>

First Number:<input type=text name=num1<br>

Second Number:<input type=text name=num2<input type=button value=HCF onClick=findHCF()>

</body>

FOR– Loop

For (i=1;i<10;i++) {
Alert(i);
} /

WHILE –Loop

i = 0;
x = “Numbers include ”;
while (i<5) {
x=x + ", " + i;
i++;
}
x = x + “ and “ + i + “.”
document.write(x); /

For the following two flowcharts, dry run them with the input 3 and 5 respectively.

(i) / (ii)
X = 3 / Output =
No. of iteration = / Output =
No. of iteration =
X = 5 / Output =
No. of iteration = / Output =
No. of iteration =

Description of the flowchart:

REPEAT UNTIL Loop

With respect to the diagram on the right,
(i)how many iterations will it make?
(ii)what is the value of S at the end of the process?
(iii)what is the value of I at the end of the process?
(iv)how to modify the iterations so that it will find the summation of all the multiplications of 3 between 0 and 100? /

Common programming techniques:

1.Swapping data:

The following program codes is supposed to exchange the data between X and Y. What would be the output and how to fix it?

X = 3 ;

Y = 5;

X = Y;

Y = X;

After the end of this program, X = and Y = .

The correct program code would be:

X = 3 ;
Y = 5;
temp = X;
X = Y;
Y = temp;

2.Summation from 1 to 100:

We can find the summation of 1 to 100 easily by a FOR-LOOP.

sum = 0;

for (i=1;i<100;i++) {

sum = sum + i;

}

The question is should it be

(i)for (i=1;i<100;i++)OR(ii)for (i=1;i<=100;i++) ?

What is the value of i in (i) and (ii) respectively?

3.Multiplication from 1 to 10.

Investigate what is wrong in the codes below:
result = 0;
i = 1;
While (i<10) {
Result = result * i;
i = i + 1;
} / Modification:

4.To output the absolute value of an input X.

if (X > 0) {

Y = }

Else { Y = }

X = ;

5.Data type problem, suppose

var X = ‘a’;

var Y = 10;

var Z = ‘c’;

What would be the result of the following?

(i)Z = X + Z;

(ii)Y = Y – 5.78;

(iii)Z = X + Y;

Advance Techniques:

1.Array + Passing variables (

function ReOrder(number) { //pass a number to this function.

var myArray = new Array();//create a new array

limit = number;

for (i=0;i<limit;i++) {

counter = i + 1;

statement = "Enter name " + counter + ":" ;

response = window.prompt(statement,"");

myArray[i] = response;//store the response into the array

}

document.write ("Original array is shown below:<br>");

for (i=0;i<limit;i++) { document.write(myArray[i]+"<br>");}

document.write ("The sorted array is shown below:<br>");

myArray.sort();

for (i=0;i<limit;i++) { document.write(myArray[i]+"<br>");}

}

</script>

<body>

Input different names and it will sort them to give you an ascending list.<br>

</body>

2.Modular Approach

A program may contain thousands lines of codes or more. So, smaller modules have to be adopted to form a real life program. The process of splitting up a whole program into modules is called “Modular approach”. Below shows a sample program that contains modules. Try to discover what the advantages of using modular approach are. (

From the above program code, we can discover that modular approach should be used:

1.when some standard procedures are frequently used.

2.because of easier debugging / understanding of the program

3.because of effective division of labour (i.e. each programmer can focus on particular task.)

4.for large scale project so that it can be divided into manageable size modules.

Exercise:

1.Which of the following statements consist of syntax errors?

(1)x + 1  4

(2)x  5 + 8 * 2

(3)x  "5" + 5

A.(1) onlyB.(3) only

C.(1) and (3) onlyD.(2) and (3) only

2.Which of the following will give a true result?

A.(x > x + 5) AND (1 > 2)

B.(3 > -7) OR (-7 > 3)

C.(5 >= 5) AND (4 >= 5)

D.(7+3 < 8) OR (-7 > -6)

3.Consider the following program:

INPUT x

IF x > 5 THEN

X  5

END IF

The purpose of the program is to

A.allow 5 to be entered only.

B.allow numbers less than or equal to 5 to be entered only.

C.ensure that the value of X is greater than 5.

D.ensure that the value of X is less than or equal to 5.

4.How many times will the following WHILE-loop iterate?

i 6

WHILE i <10 DO

…

i  i + 1

END WHILE

A.0B.4

C.5D.6

5.How many times will the following REPEAT…UNTIL-loop iterate?

i 6

REPEAT

…

i  i + 1

UNTIL i > 10

A.0B.4

C.5D.6

6.Which line of the following pseudocode segment can be deleted without affecting the result?

Line number / Statement
10 / C = 60
20 / E = 70
30 / M = 80
40 / T = 95
50 / M = M – T
60 / INPUT C
70 / C = C + E
80 / OUTPUT (C + E)
90 / OUTPUT M

A.Line 10B.Line 20

C.Line 30D.Line 40

7.An algorithm (算法) is

A.a program

B.a set of steps used to solve a problem

C.a description of how the problem has been solved

D.a clear diagram showing the existing problem

8.In a report card, the average mark of a student is outputted as -20. What kind of error is it?

A.syntax errorB.run-time error

C.logical errorD.printing error

9.Which of the following is/are advantage(s) of compiler over interpreter?

(1)Compiled programs run faster

(2)Source codes need not be present during execution.

(3)Compiled programs are easier to develop.

A.(1) onlyB.(2) only

C.(1) and (2) onlyD.(2) and (3) only

10.Object programs are free of

(1)syntax errors(2)runtime errors

(3)logical errors

A.(1) onlyB.(2) only

C.(1) and (2) onlyD.(1), (2) and (3)

11.Which of the following would lead to a logical error?

(1)A “” sign is mistyped as “” in a conditional statement

(2)The assignment statement x  x + 1 is mistyped as x  x + 2

(3)The reserved (保留字) word “if” is mistyped as “fi”.

A.(1) onlyB.(2) only

C.(1) and (2) onlyD.(2) and (3) only

12.Which of the following is/are high level language(s)?

(1)JAVA(2)PASCAL

(3)machine language

A.(1) onlyB.(2) only

C.(1) and (2) onlyD.(2) and (3) only

13.Which of the following is machine independent?

A.assembler

B.assembly language

C.machine language

D.C source programs

14.Consider the following program:

10P  1

20FOR i =6 to 8 DO

30P  P * i

What is the value of P just before the execution finishes?

A.21B.42

C.48D.336

15.Debugging is to

A.find out any hidden errors

B.make corrections to the program so that it is error free

C.kill any bugs or bacteria

D.kill a virus using an anti-virus software

16.Documentation

A.describe what has been done and how the problem is solved

B.use a word processing software to produce a document

C.write a letter to the clients telling them the problem is solved

D.re-write the program t make it more versatile.

17.If we are going to add up all the even numbers from 1 to 100, which of the following constructs is most likely to be adopted?

A.LoopingB.Branching

C.SequencingD.Sorting

18.What does a compiler do?

A.A compiler translates a program written in a high-level language into machine-executable instruction.

B.A compiler debugs errors found in a program written in a high-level language.

C.A compiler translates high-level language into an intermediate form, which is then executes.

D.A compiler makes a program written in a high-level language run on a computer.

19.Which of the following is the initial step in problem solving?