Introduction

Algorithmic Thinking

Computational thinking is a high level problem-solving skill comprising of:

Decomposition: Breaking down a complex problem or system into smaller, more manageable parts
Pattern Recognition: Looking for similarities among and within problems
Abstraction: Focusing on the important information only, ignoring irrelevant details
Algorithms: Developing a step-by-step solution to the problem, or the rules to follow to solve the problem

Steps of Algorithmic Thinking

Define the problem

**Define **the **objectives **to be **accomplished **or the problem
Specify the following:
- The **problem **we are trying to solve
- The **users **of our program

Analyse the problem

Identify the following:
- The **values **that must be **supplied **from outside the program (input data)
- The **values **that are **given **on the **problem **(constant data)
- The **values **that must be **produced **as a **result **of solving the problem (output data)

Design the solution

**Design how **the **problem **can be solved in a systematic manner
**An algorithm **is a step-by-step **process **or sequence of instructions that can be used to solve a problem in a finite amount of time
Generally, we can use either flowchart or pseudocode to describe an algorithm

Implement the solution

**Write **the program with an appropriate programming language
Following the language syntax correctly

Test the solution

**Test **the **program **by running test plans with known solutions
**Debug **the **program **if it fails to meet expectations
Use data verification and data validation to prevent incorrect input data

Document the solution

Written description of purpose and process
Understandable by others
Makes changes easier

Flowchart

Definition: Formalised graphic representation of a logic sequence, work process, etc.
Provides people with common language/reference point when dealing with a project or process

Symbol

Symbol Name

Symbol Description

Process / Operation Symbols

**Process **

(Rectangle)

Shows an action step

Branching / Control Symbols

Flow Line

(Arrow, no Connector)

Shows the direction that the process flows

Terminator

(Oval)

Shows the start and stop points in a process

Decision

(Diamond)

Shows a question or branch in the process

Input / Output Symbols

Data

(Parallelogram)

Shows the input to and output from a process

Pseudocode

Structure & Style

Use UPPERCASE for pseudocode keywords: IF, ELSE, WHILE, FOR, etc
Indent blocks to show structure clearly
Use descriptive variable names
Keep code logic-focused, not syntax-specific

Variables and Constants

DECLARE age: INTEGER
DECLARE name: STRING
CONSTANT PI ← 3.14

Input and Output

OUTPUT "Enter your name:"
INPUT name

Arithmetic & Logic

sum ← a + b
average ← sum / count
IF x > 0 AND y < 10 THEN
    ...
ENDIF

Selection (IF / CASE)

IF score ≥ 50 THEN
    OUTPUT "Pass"
ELSE
    OUTPUT "Fail"
ENDIF

CASE grade OF
    "A": OUTPUT "Excellent"
    "B": OUTPUT "Good"
    "C": OUTPUT "Average"
    OTHERWISE: OUTPUT "Invalid"
ENDCASE

FOR Loop (Count-controlled)

FOR i ← 1 TO 10
    OUTPUT i
ENDFOR

WHILE Loop (Pre-condition)

WHILE x < 100 DO
    x ← x * 2
ENDWHILE

REPEAT UNTIL Loop (Post-condition)

REPEAT
    INPUT value
UNTIL value = 0

Procedure (No return value)

PROCEDURE greet(name: STRING)
    OUTPUT "Hello " + name
ENDPROCEDURE

Function (With return value)

FUNCTION square(x: INTEGER)
    RETURN x * x
ENDFUNCTION

Arrays and Strings

DECLARE scores[5]: ARRAY OF INTEGER
scores[1] ← 80

FOR i ← 1 TO LENGTH(name)
    OUTPUT name[i]
ENDFOR

Comments

// Calculate total marks
total ← a + b + c

// Print total marks 
OUTPUT total

Principles of a Good Algorithm

A good algorithm is one that satisfies the following:

It is easily understood by another person
It solves the problem **efficiently **and cleanly

Some guidelines for writing a good algorithm include:

Ask yourself: “Can it be implemented by someone else?”
This means that in your algorithm, you should use unambiguous expressions and be **concise **and precise
State all necessary information, including assumptions
Use only the three basic flow of execution constructs
**Sequential **
**Selection **
**Repetition **
Sub-divide the problem solution into **modular **(self-contained and logical), easy-to-manage chunks, through stepwise refinements
Have only one start and one termination point
Use **indentation **to show structure and improve readability

Program Testing

Test Plan

A set of possible inputs with their associated expected output
Ensures that boundary conditions and tricky inputs are not overlooked
Includes these data
- Normal Data: Typical, valid values
- Extreme Data: Boundary Values
- Abnormal / Deformed Data: Invalid Values

Possible Inputs	Expected Output	Reason for Test Item
Item No.	Mark
1	30	Fail	Normal Data
2	70	Pass	Normal Data
3	0	Fail	Extreme Data
4	44	Fail	Extreme Data
5	45	Pass	Extreme Data
6	100	Pass	Extreme Data
7	-1	Error: Mark cannot be negative	Abnormal Data
8	7.5	Error: Mark must be integer	Abnormal Data

Data Validation

Process of which the data entered is **sensible **and reasonable

Type	Method	Example
Range Check	Check that data is within given range	Test score must be between 0 and 100
Format Check	Check that data is in the right format	Date must be in the format dd/mm/yyyy
Length Check	Check that data length is correct	Length of password must be more than 6 characters
Presence Check	Check that data exists	Username cannot be blank
Digit Check	Check for validity of data	NRIC must be valid

Data Verification

Process of which to **ensure **the input data **matches **the original resource
The user may still make a mistake when inputting data
For example, we are often asked to enter the password twice to change it

Debugging

Process of which to detect, **locate **and remove errors in a program
Types of **errors **:
- Syntax Error: Syntax of program is not adhered
- **Logical Error: **Program design is incorrect
- **Runtime Error: **Unexpected conditions/detected error during execution
Steps to debug:
- Add **breakpoints **to code to evaluate different portions of the code
- **Display **the **procedure stack **to **trace **the source of error
- Mark out program statements to independently test portions of the code

Structured Programming

Structured programming is a** methodology **for developing programs
It manages program complexity and to develop programs which are easy to read, **test **and maintain
It **emphasises **the use of modules in program design and implementation

Top-Down Design

Repeatedly breaking a problem down into simpler problems
These sub-problems are solved separately and are then linked together by means of simple control structures
It derives solutions to large problems using ‘divide and conquer’ techniques

Modularity

Modularity is creating a **collection **of well-defined separate modules
Each module serves a specific purpose and has connections with the program
A **module **is a complete part-program that is used from within the main program

Advantages	Disadvantages
Can be kept in a library and re-used in other solutions	More time needed to split problems into modules
Can be coded and tested separately	Larger memory space needed
Easier to debug as modules are small	May not be able to see all code
Easier to maintain and modify as modules can be removed/added easily	More files need to be managed (potential lost of files)
Easier to monitor and control	Possibly over-modularise

Structure Chart

A structure chart is a pictorial description of a top-down design
The chart consists of **boxes **– one for each module at each level in the hierarchy
The top-box is the main module or main program
**Boxes **in the second level are called from the main module, each connected to their respective sub-tasks

Decision Tables

Decision tables help for program creators to process variations in conditions
All possible conditions and **outcomes **are listed in a two-dimensional table that shows the outcome results from each combination of conditions

Setting up the table

Table is divided into four quadrants
- Upper left quadrant: One row for each condition
- Lower left quadrant: One row for each outcome
- Upper right quadrant: Values associated with each of the conditions (T/F)
We may count the total number of columns needed by getting 2^{no. of conditions}

Simplify the table by combining indifferent conditions, meaning **conditions **where either state causes in the same result

Quartz 5

Explorer

01 Introduction