CSC 202: COMPUTER PROGRAMMING II

Course Content
• Introduction to Problem-Solving Methods and Algorithm Development,
• Principles of Good Programming,
• Structured Programming Concepts,
• Debugging, Testing, String processing,
• Searching and Sorting
• Recursion.
Java, a widely used programming language, will be used in teaching this course.

INTRODUCTION
We usually use the term computerisation to indicate the use of computers to develop software in order to
automate any routine human task efficiently. Computers are used for solving various day-to-day problems;
thus, problem-solving is an essential skill a computer science student should know.

It is pertinent to mention that computers themselves cannot solve a problem. We should give precise step-
by-step instructions to solve the problem. Thus, the success of a computer in solving a problem depends on
how correctly and precisely we define the problem, design a solution (algorithm) and implement the solution
(program) using a programming language.

Thus, problem-solving is the process of identifying a problem, developing an algorithm for the identified
problem and finally implementing the algorithm to develop a computer program.

When problems are straightforward and easy, we can easily find the solution. However, a complex
problem requires a methodical approach to find the right solution. In other words, we have to apply
problem-solving techniques. Problem-solving begins with identifying the problem and ends with a complete
working solution regarding a program or software.

CONCEPTS OF ALGORITHM
In our day-to-day lives, we perform activities by following a certain sequence of steps. Problem-solving
goes through a sequence of steps which involves the abstraction and decomposition of a large amount of
problem into smaller manageable subtasks that can be handled independently. An algorithm is important
in the planning and execution of a problem solution since it specifies the sequence of steps needed to carry
out the instructions that will lead to the overall result. An algorithm can be defined as a sequential set of
instructions that are followed in order to solve a problem using a finite amount of data in a finite amount of
time.

1
More than one algorithm can be written for a particular problem (see Figure 1.0). Selecting a particular
algorithm in place of the other depends on the following factors: reliability, accuracy, ease of
modification, and execution time when converted to a high-level language.

Figure 1.0: Relationship between Problem, Algorithms and Programs

Why do we need an Algorithm?

A programmer writes a program to instruct the computer to do certain tasks as desired. The computer
then follows the steps written in the program code. Therefore, the programmer first prepares a program
roadmap to be written before writing the code. Without a roadmap, the programmer may not be able
to visualise the instructions clearly and may end up developing a program that may not work as expected.

Such a roadmap is nothing but the algorithm, which is the building block of a computer program. For
example, searching using a search engine, sending a message, finding a word in a document, booking
a taxi through an app, performing online banking, and playing computer games are all based on
algorithms.

Writing an algorithm is mostly considered the first step in programming. Once we have an algorithm to
solve a problem, we can write a computer program to give instructions to the computer in a high-level
language. If the algorithm is correct, the computer will run the program correctly every time. So, the
purpose of using an algorithm is to increase the reliability, accuracy and efficiency of obtaining solutions.

Major Components of Algorithm

Most algorithms used in solving program-related problems consist of three major sections: the input,
processing and output. That is the summary of most if not all, the activities most algorithms undertake to
produce a result. To execute a task, the algorithm requires some data (i.e. input), performs some
computation on the data (i.e. processing), and then produces the result (i.e. output). The processing
comprises any or all of the following: computation, selection, iteration, etc. Figure 1.1. Shows the three
major sections of an algorithm.

2
Figure 1.1: The three major sections of an Algorithm
• Input: This represents the data sent for processing in the system. Most algorithms provide some
variables and a description of the data that the variable will handle.
• Processing: This is the action performed on data in order to produce the desired result—such
actions as computation, selection, iteration, etc.
• Output: This is the result produced after the data has been processed. When the algorithm has
been converted to programs, the data is usually displayed through the output device, for example,
the monitor.

Properties of Algorithm
a. Input/output: The algorithm should be able to produce output value(s) when given a set of
specified input value(s). There should be a relationship between the input and the output produced
by the algorithm.
b. Finiteness: An algorithm should be able to terminate after a finite number of instructions have
been processed. That means processing a set of instructions does not have to take forever.
c. Definiteness: The algorithm should be developed to make each step precise and easy to
understand.
d. Effectiveness: This means that the algorithm should be in a form that will be easy to convert to a
programming statement in a finite amount of time.
e. Generality: The algorithm should be able to produce the same output when given different types
of valid data (i.e. data taken from a specified domain).

Role of Algorithm in Problem Solving

a. An algorithm helps evaluate a problem to know if it can be solved using a computer. Once an
algorithm can be written for a problem, then the problem can be solved using computational means.
b. An algorithm helps identify the various steps, major decision points and variables needed to solve
a problem. These are the concepts that are needed for the development of a computer program.
c. An algorithm helps decompose a large task into small manageable subtasks. The decomposition
helps reduce the problem's complexity and makes it solvable.
d. The atomic nature of the tasks/subtasks of the algorithm makes the decision-making process more
rational in nature since facts support the subtasks.

3
Ways of Expressing Algorithm
Algorithms can be expressed in three major ways: Natural Language, Pseudocode and Flowchart.
• Natural Language: This method of expressing algorithms using our day-to-day languages,
like English or other languages. This has been found to be disadvantageous as it is very wordy
and confusing.
Example 1.1: Write an algorithm to calculate the area of a triangle (area = 1/2 * base
* height)

Solution
Step 1: Start
Step 2: Ask the user to give you the base and height of the triangle
Step 3: Calculate the product of the values (i.e. base and height)
Step 4: Divide the product in step 3 by 2
Step 5: Display the area you got in Step 4
Step 6: Stop

• Pseudocode: This type of expression has a form closely related to a programming language,
though there is no restriction on the syntax. It is not ambiguous like the natural language.
Example 1.2: Write an algorithm to calculate the area of a triangle (area = 1/2 * base
* height)

Solution:
Step 1: Start
Step 2: Read base and height
Step 3: Product = base x height
Step 4: Area = product/2
Step 5: Print Area
Step 6: Stop

• Flow chart: Uses symbols to represent the sequence of instructions. It is not ambiguous like the
natural language, but the modification is done using a specialised tool. In addition, the
implementation uses a standard rule.
Example 1.1: Draw a flowchart to calculate the area of a triangle (area = 1/2 * base *
height)
Solution:

4
Table 1.0. Shapes or symbols to draw flow charts
Flowchart Symbol Function Description
Also called “Terminator” symbol. It indicates where the flow
Start/End
starts and ends.
Also called “Action Symbol,” it represents a process,
Process
action, or a single step.
A decision or branching point, usually a yes/no or
Decision true/false question is asked, and based on the answer, the
path gets split into two branches.

Also called data symbol, this parallelogram shape is used to

Input/Output
input or output data

Arrow Connector to show order of flow between shapes.

Algorithm Development Methodologies

Top-Down Design
The most common problem-solving approach humans use is divide and conquer, which means dividing a
large problem into smaller parts that can be solved independently. This is the concept used in Top-Down
Design.
Top-down design, also called functional decomposition, is a problem-solving methodology that involves
splitting a large problem into smaller manageable parts that can be solved independently and
integrated to form the overall solution. The problems in a top-down design are arranged in a hierarchical
tree structure (structured chart), consisting of problems or sub-problems called modules.
A module is a self-contained set of steps needed to solve a problem. The modules are arranged in a
hierarchy from top to bottom in a structure chart. The module at the top is the main problem, while the
ones at the bottom are a sub-division of the problem. The modules are numbered according to their
position in the hierarchy; those in the same level are given the same number. The numbering starts from
the top, usually zero, down to the bottom, which can be any finite number, depending on the problem.

5
The reason for the division of the problems into modules, parts, or segments is to reduce the problem's
complexity by subdividing them into smaller, manageable, independent parts. Some of the module(s)
could be responsible for data input. Some may perform the processing of data, which may involve
mathematical, logical or relational operations, while some may be responsible for the output.

As an example, let us refer to Figure 2.1. The figure is a hierarchical tree structure (structured chart)
comprising four levels (0, 1, 2, and 3). The top level, or level 0, describes the function of the overall
problem. It is the abstract step because the problems at this level can further be decomposed into smaller
sub-problems in the following levels. The concrete step is the last module at the bottom (i.e., the module
at level 3) that cannot be decomposed any further. Refer to case study II for a detailed example of
top-down design methodology.

Figure 2.1: An illustration of top-down design using a structured chart

Software Development Method

Problem-solving is an activity undertaken in every programming or software development environment,
so it is indispensable knowledge needed by every programmer or software developer. Problem-solving
is not just limited to computer scientists or programmers; it is also used by business students, engineers and
scientists in different ways. In business studies, students use the systems approach, while in engineering
and science, engineers and scientists use engineering and scientific methods, respectively. The
programmers, on the other hand, use the software development approach, which will be our topic of
discussion in this section. The software development methods are as follows:

6
a. Requirement Specification: Specify the problem requirements
This involves a critical examination of the problem to get a better understanding of the
requirements needed to solve the problem. The problem is restated, and every unimportant
aspect is eliminated at this point. This is to help in presenting the problem in a clear and
unambiguous form.

b. Analysis: Analyse the problem

The identification of the input variables (i.e. the data) needed for implementing the problem is
done at this point. The expected output (i.e. the result) to be obtained after the execution of the
input data and the formats (for example, a table with headings, rows and columns) of presenting
the result are also identified. The use of formulas or other methods to express the relationship
that exists with the variables in the problem is strongly encouraged. It is important to note that
if the first step and this second step are not carried out properly, it will lead to error or failure
in the solution. See example 2.1 for an explanation of this phase.

Example 2.1:
Given the three sides and height of a triangle, calculate in centimetres the area and
perimeter of the triangle.

• Problem Input
Three sides (side1, side2, and side3) of the triangle (in centimetres) Height (h) of the triangle
(in centimetres)

• Problem Output
Area of the triangle
Perimeter of the triangle

• Formula to identify the relationship between the input and output

Once we have determined the problem's input and output, we can establish a relationship
between the input and output variables using formula(s).
Let the base = side3;

Perimeter = side1 + side2 + side3;

Area = 1/2 * base * h;

When solving a problem, we extract those variables and relationships that are of interest
to us. The process of modelling a problem by extracting relevant information is known as
abstraction.

7
c. Design: Design the algorithm to solve the problem
This phase involves developing the sequence of steps called an algorithm that will be followed
to solve a given problem. After all, verification will be made to know if the steps taken solved
the problem. It is usually advisable to adopt a top-down design (or divide and conquer)
approach in carrying out this algorithm design and development task.
Using a top-down design implies that the overall solution to the problem will be realised by
unifying all the steps followed and solutions obtained from the sub-modules. Some steps taken
in each module need to be expanded so that the required details will be provided to solve the
problem adequately. This approach of expanding the steps by providing additional detailed
steps to a particular step is called stepwise refinement.
Let us examine how a lecturer develops his lecture notes; he takes up a topic, breaks it down
into sub-topics (or course outline), and then, for each of the sub-topics, he fills in some additional
details that will enhance the understanding of the course. Providing additional details into a
sub-topic or course outline is an example of stepwise refinement in a top-down design process.

d. Implementation: Implement the algorithm

After the algorithm has been developed, the next step, which is the implementation of the
algorithm, is to convert every step in the algorithm to an equivalent statement in a programming
language. One algorithm can be implemented using one or more programming language(s).

e. Testing: Test and verify the completed program

Testing and verification involve executing the program in the computer to know if it is producing
the desired result. The testing phase is tedious, as the program must be tested given different
circumstances and data.

f. Maintenance: Maintain and update the program

After the program has been tested, certified and put into productive use, it will be used in
different hardware, operating systems, geographic locations, security conditions, etc. It will be
expected to deliver its task effectively and uninterruptedly. The program needs regular or
periodic maintenance and updates in case of any malfunction or deviation from the originally
intended task. For effective maintenance and update of a program, there is a need for proper
documentation at every point of software development and maintenance. Maintenance and
update are a means through which software is released at intervals to be installed in existing
software to improve its functionality, fix bugs, improve performance or address some security
challenges.

8
Applications of Software Development Methods in Problem Solving
• This section will demonstrate how we can apply software development methods to problem-
solving.

CASE STUDY I: Temperature conversion

THE PROBLEM

You have been entrusted with weather forecasting, and you have a device that can only read the
temperature in Celsius, and you are expected to report in Fahrenheit. Write a program to convert every
Celsius temperature reading recorded by your device to Fahrenheit.

ANALYSIS

The first thing to do is to understand what is expected of you in the problem. The problem says that you
will get the Celsius temperature from your device, which will be converted to Fahrenheit. Therefore, the
input is Celsius, and the output is Fahrenheit. In this phase, we must ascertain the relationship between
the input and the output. This can be established using the formula.

DATA REQUIREMENT

• Required Input
Celsius /* the temperature in degree Celsius */
Product /* the result obtained after multiplying Celsius by 9/5 */

o Constants
SCALERATE = 9.0/5.0;

TEMPSCALE = 32;

• Required Output
Fahrenheit /* the temperature in degrees Fahrenheit */

• Required Formulas
Fahrenheit = (Celsius * 9/5) + 32

By substituting the constants SCALERATE for 9/5 and TEMPSCALE for 32 we have
Fahrenheit = (Celsius * SCALERATE) + TEMPSCALE

9
DESIGN

The next step will be formulating the algorithm by listing the steps needed to execute the problem. Such
steps are listed below:

Algorithm
Step 1: Start
Step 2: Read Celsius Temperature
Step 3: Convert Celsius to Fahrenheit
Step 4: Print Fahrenheit
Step 5: Stop
To convey meaning and enhance clarity, we have to refine some steps as follows:

Step 1 refinement
Step 1: Read Celsius Temperature
1.1: Write “Enter Celsius Temperature”
1.2: Read Celsius temperature
Step 2 refinement
Step 2: Convert Celsius to Fahrenheit
2.1: Fahrenheit = (Celsius * 9/2) + 32

Algorithm With Refinement

Step 1: Start
Step 2: Read Celsius Temperature
2.1 : Write “Enter Celsius temperature value”
2.2 : Read Celsius temperature
Step 3: Convert Celsius to Fahrenheit
3.1: Fahrenheit = (Celsius * 9/2) + 32
Step 4: Print Fahrenheit
Step 5: Stop

IMPLEMENTATION

The next step is to convert every step of the algorithm to a valid programming statement using Java
language. To write the program, we must state the kind of input (data) to collect. In this case, we will use
decimal numbers (i.e. float). We will also identify the data in the memory (declare variable) with the
names Celsius and Fahrenheit. Then, we will proceed with the statement that will execute the conversion

10
algorithm from Celsius to Fahrenheit.

Below is the Java program of the above algorithm. The program uses a comment to explain the
program statements. A detailed explanation of the program will be in the next class.

Sample output of the program

Enter the Celsius temperature value and press enter key when done >> 20
The Fahrenheit equivalent of
20.00 degree Celsius is 68.00

TESTING
Testing the program means verifying that the program will give the required output when given a set of
valid input data. You have to test the program by supplying it with valid input data and examining it
carefully to know if it corresponds with the intended output. To ensure the program is behaving well, you

11
have to test it with variable input sets. Sometimes, you might have to test how the program will behave if
given some unrelated input values. This has to be ascertained so that the program will not crash when
someone mistakenly puts some unrelated input value(s).

USE CASE II: Volume calculation

THE PROBLEM
Given the radius and height of a cylinder, calculate the volume.

ANALYSIS

From the problem, we can deduce that the solution will require two inputs – the radius and height of the
cylinder, and then one output will be required, which is the volume. The input values will be of float
(fractional) type since the constant pie is of decimal type, changing the integer variable to fractional
type. The relationship between the variables (i.e. the input and output) will be listed subsequently.

DATA REQUIREMENT
• Required Constant
PI = 3.142 /* the value of the constant PI */

• Required Input
Radius /* the radius of the cylinder */
Height /* the height of the cylinder */
• Required Output
Volume /* the volume of the cylinder */

• Required Formulas
Area = PI * Radius * Radius

Volume = Area * Height

DESIGN

ALGORITHM WITH REFINEMENT

Step 1: Start
Step 2: Get input
2.1: Request for input 2.2: Read input
Step 3: Calculate volume

12
3.1: Area = PI * Radius * Radius 3.2: Volume = Area * Height
Step 4: Print the volume
Step 5: Stop

IMPLEMENTATION

Sample output of the program

Enter the radius: 7

Enter the height: 8

The volume of the cylinder is 1231.66

TESTING
The same explanation in Case Study I still holds here so you can refer to testing in Case Study I for a
review.

13
Exercises
Algorithm questions
1. Write an algorithm to calculate simple interest
2. Write an algorithm to calculate the area of a triangle
3. Write an algorithm to find the largest of three numbers x, y, z
4. Write an algorithm to test if a given integer value is prime or not

Programming questions
1. Write a Java program to calculate simple interest
2. Write a Java program to calculate the area of the triangle
3. Write a Java program to find the largest of three numbers x, y, z
4. Write a Java program to test if a given integer value is prime or not

14
import java.util.Scanner;

class TemperatureConverter {
public static void main(String[] args) {
/* Declaration of scanner object to read input */
Scanner scan = new Scanner(System.in);

/* Declaration of input variables */

float celsius, fahrenheit;

/* Declaration of conversion constants */

final float SCALERATE = 9 / 5;
final float TEMPSCALE = 32;

/* Read input from keyboard */

System.out.println("Enter temperature in Celsius");
celsius = scan.nextFloat();

/* Calculate the Fahrenheit equivalent */

fahrenheit = (celsius * SCALERATE) + TEMPSCALE;

/* Print the result (output) of the conversion */

System.out.println("The tempature in Fahrenheit: " + fahrenheit);

}
}

import java.util.Scanner;

class VolumeCalculator {
public static void main(String[] args) {
/* Declaration of scanner object to read input */
Scanner scan = new Scanner(System.in);

/* Perform variable declaration */

15
float radius; float height; double area; double volume;

/* Read radius and height from keyboard */

System.out.println("Enter the radius");
radius = scan.nextFloat();

System.out.println("Enter the height");

height = scan.nextFloat();

/* Calculate volume */
area = 3.142 * radius * radius;
volume = area * height;

/* Print volume */
System.out.println("The volume of the cylinder is: " + volume);
}
}

16