Chapter 1: Introduction

Computational thinking

Decomposition: breaking down complex problem/system into smaller, more manageable parts
Pattern Recognition: looking for similarities among and within problems
Abstraction: focusing on important information only, ignoring relevant details
Algorithms: developing a step-by-step solution to the problem, or rules to follow to solve the problem

Problem-solving steps:

Define the problem

Write statement of objectives to be accomplished (problem to solve)
Specify users of your program if necessary
E.g.

Mark Range	Grade
0-44	Fail
45-100	Pass

Analyze the problem

Identify

Input data: values that must be supplied from outside the program* (e.g. Mark)
Constant data: values given on the problem* (e.g. 0,44,45,100)
Output: values that must be produced as a result of solving the problem (e.g. ‘Fail’ or ‘Pass’)

*focuses on what the program must achieve

Design the solution

How to solve the problem systematically
Take given input data and constants, produce desired output values
Specify action taken (verb) and data that action has taken on
Algorithm: a step-by-step process or sequence of instructions that can be used to solve a problem in a finite amount of time
Concise and precise, state all necessary info including assumptions
Described using flowchart or pseudocode
Flowchart: formalised visual / graphical representation of an algorithm / logic sequence, work process, organisation chart or similar structure
Provides people with a common knowledge or reference point when dealing with a project or process
OR step by step diagrammatic representation of the logic paths to solve a given problem
¹

Symbol	Symbol Name (alias)	Symbol Description
Process / Operation Symbols
	Process (Rectangle)	Process / action step
Branching and Control of Flow Symbols
	Flow Line (Arrow, Connector)	Shows direction the process flows
	Terminator (Oval)	Start and stop points in a process
	Decision (Diamond)	Question / branch in the process flow (e.g. 2 options Yes/No)
Input and Output Symbols
	Data (I/O shape) (Parallelogram)	Inputs to and outputs from a process

Pseudocode: English with some defined rules of structure and some keywords similar to program code
Pseudo-Code Guide
Can focus on logical details of our program solution, without being bogged down with the syntax rules of the programming languages
Indent to show structure in the algorithm
Disadvantage: has no single form; format varies depending on author

Start:	Begin	Input:	Read
Finish:	End	Output:	Print
Selection: (If & end-if is a pair)	If, then, else, end-if	Multi-way selection:	Case-where, otherwise, end-case
Pre-test repetition:	While, end-while	Post-test repetition:	Repeat Until

E.g.
BEGIN
READ Mark
Cutoff = 45
IF Mark < Cutoff
PRINT ‘Fail’
ELSE
PRINT ‘Pass’
ENDIF
END

3 basic flow of execution constructs
Sequential
Selection
Repetition
Sub-divide problem solution into modular (self-contained & logical), easy-to-manage chunks, through step-wise refinements
Only 1 start and end termination point

Implement the solution (code program)
Test the solution

Run test plans with known solutions: set of possible inputs along with their associated expected output
Checks for correctness during and after its development
Complete fully-developed test plan as you design the solution (not after)
Must contain enough sets of possible inputs to thoroughly test the program and its algorithm
Normal data: typical, valid values
Extreme data: boundary values
Abnormal data: invalid values
E.g.

Possible inputs		Expected output	Reason for test item
Item #	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

Debug program if fail to meet our expectations
Use data validation and data verification techniques to prevent the wrong input data
Data validation: process to ensure that the data entered is sensible and reasonable

Type	Check if:	Example
Range check	Data value is within certain range	Marks from 0-100
Format check	Data is in right format	dd/mm/yy
Length check	Length of data is entered into a field	Length of password
Presence check	Data is entered into a field	Username cannot be left blank
Check digit	Other digits are correct, checked using last 1 or 2 digits in data	ISBN of a book

Data verification: process to ensure the input data matches the original resource / checks if input data is what user intends to enter
Even when data entered in correct format/range/length, user may still make mistake when inputting data
E.g. asked to enter password twice in order to change it ⇒ double entry of data to verify if 2nd input matches 1st input (proofread input data)
E.g. proofread before submitting forms
(X): Entering account + password is NOT data verification
Debug: detect, locate, and remove all errors in a computer program
Syntax error: syntax rules in the programming language are not adhered to (e.g. error in syntax of a sequence of characters of tokens). Program will not compile until all syntax errors corrected
Logical error: wrong program design, e.g. wrong algorithm to solve the program. Program may be compiled and executed but does not give expected output
Run-time error: detected at run-time, e.g. stack overflow, division by 0, open a file that does not exist
Techniques for debugging:
Specify a point in the source code and have the program execute up to a point (break point) to evaluate different portions of the code
Display the procedure stack to list the sequence of the procedures called during the executing of the program (trace facility)
Mark out as comments and procedures or program statements to be excluded in the testing of the intended portion of the code

Document the solution

Write a description of its purpose and process
Allows other programmers to understand solution and make changes easily when necessary

Structured programming: methodology for developing programs

Manages complexity, develops programs that are easy to read, test and maintain
Emphasises the use of modules in program design and implementation
Top-Down Design / step-wise refinement: method of designing a solution to a problem by repeatedly breaking a problem down into simpler problems until the problem can be solved easily
These sub-problems are solved separately, then linked together using simple control structures
Divide and conquer & top-down approach are good for large problems
Modularity: feature of designing problem solution as a collection of well-defined separate modules, each of which serves a specific purpose and has specific connections with the main program
Module: a complete part-program that is used from within the main program
E.g. from math import * ⇒ import all from math module
E.g. math.sqrt(4) ⇒ 2
E.g. math.pi
OR from math import pi
print pi (?)
Advantages
Modules can be kept in a library and re-used in other solutions
Many programmers can work in the same problem as each can be given different modules to solve; Each module can be coded and tested separately
Easier to debug as modules are small
Easier to maintain and modify as modules can be removed/added easily
Easier to monitor and control large projects
Disadvantages
Time needed to partition problem into modules
Larger memory space needed
More files need to be managed (lost of files)
May not be able to see all code or refer to all the documentation
Possible to over modularize

Structure chart: pictorial description of a top-down design

1 box for each module of the solution at each level in the hierarchical breakdown
Top-box: main module / main program
Boxes in second level: called from the main module, each connected to their respective sub-tasks

Decision tables²

Provide alternative for specifying conditions or processing alternatives
All possible conditions and outcomes listed in 2D table that shows outcome results from each combination of conditions

E.g. The customer is approved if he has maintained monthly checking account balance of at least $1000 for each of the last three months and has averaged no more than two overdrafts per month. Customers meeting only one of these conditions but maintaining an average savings account balance of at least $500 for each of the last three months receive conditional approval with an automatic loan limit of $500.
3 conditions: Checking account balance: value >= 1000 Number of overdrafts <= 2 Average savings balance: values >= 500	3 possible outcomes: Approval (no limit) Conditional approval ($500 limit) Rejection
Table divided into 4 quadrants: Upper left quadrant: 1 row for each condition Lower left quadrant: 1 row for each outcome Upper right quadrant: values associated with each condition (e.g. Y/N or T/F) Can count total number of columns needed by multiplying the number of values each condition can assume E.g. 3 conditions each that can assume 2 values ⇒ total 2x2x2=8 possible combinations or outcome Lower right quadrant: X mark to designate each outcome AVG-CHK-BAL >= 1000 \| Y \| Y \| Y \| Y \| N \| N \| N \| N ³NUM-OVERDRAFTS <= 2 \| Y \| Y \| N \| N \| Y \| Y \| N \| N ⁴AVG-SAV-BAL >= 500 \| Y \| N \| Y \| N \| Y \| N \| Y \| N ⁵APPROVE \| X \| X ⁶COND-APPROVE \| X \| X ⁷REJECT \| X \| X \| X \| X ⁸ Then: Verify policy Completed decision table reviewed by end-users Resolve any rules for which actions are not specific Verify rules that you think are impossible or cannot in actuality occur Resolve apparent contradictions, e.g. 1 rule with 2 contradictory actions Verify that each rule’s actions are correct Simplify table Combine rules with indifferent conditions (i.e. values do not affect decision and always result in the same action) Look for rules with the same actions, then from these, find those whose condition values are the same except for only 1 condition (i.e. the indifferent condition) Collapse this set of rules into a single rule, replace indifferent condition value with a dash Note: all possible values of the indifferent condition must be present among the rules to be combined before they can be collapsed E.g. (column 1&2, 4&8 combined) AVG-CHK-BAL >= 1000 \| Y \| Y \| - \| N \| N \| N NUM-OVERDRAFTS <= 2 \| Y \| N \| N \| Y \| Y \| N AVG-SAV-BAL >= 500 \| - \| Y \| N \| Y \| N \| Y APPROVE \| X COND-APPROVE \| X \| X REJECT \| X \| X \| X

E.g. The customer is approved if he has maintained monthly checking account balance of at least $1000 for each of the last three months and has averaged no more than two overdrafts per month. Customers meeting only one of these conditions but maintaining an average savings account balance of at least $500 for each of the last three months receive conditional approval with an automatic loan limit of $500.

3 conditions:
Checking account balance: value >= 1000
Number of overdrafts <= 2
Average savings balance: values >= 500

3 possible outcomes:
Approval (no limit)
Conditional approval ($500 limit)
Rejection

Table divided into 4 quadrants:
Upper left quadrant: 1 row for each condition
Lower left quadrant: 1 row for each outcome
Upper right quadrant: values associated with each condition (e.g. Y/N or T/F)
Can count total number of columns needed by multiplying the number of values each condition can assume
E.g. 3 conditions each that can assume 2 values ⇒ total 2x2x2=8 possible combinations or outcome
Lower right quadrant: X mark to designate each outcome
AVG-CHK-BAL >= 1000 | Y | Y | Y | Y | N | N | N | N
³NUM-OVERDRAFTS <= 2 | Y | Y | N | N | Y | Y | N | N
⁴AVG-SAV-BAL >= 500 | Y | N | Y | N | Y | N | Y | N
⁵APPROVE | X | X
⁶COND-APPROVE | X | X
⁷REJECT | X | X | X | X
⁸
Then:
Verify policy
Completed decision table reviewed by end-users
Resolve any rules for which actions are not specific
Verify rules that you think are impossible or cannot in actuality occur
Resolve apparent contradictions, e.g. 1 rule with 2 contradictory actions
Verify that each rule’s actions are correct
Simplify table
Combine rules with indifferent conditions (i.e. values do not affect decision and always result in the same action)
Look for rules with the same actions, then from these, find those whose condition values are the same except for only 1 condition (i.e. the indifferent condition)
Collapse this set of rules into a single rule, replace indifferent condition value with a dash
Note: all possible values of the indifferent condition must be present among the rules to be combined before they can be collapsed
E.g. (column 1&2, 4&8 combined)
AVG-CHK-BAL >= 1000 | Y | Y | - | N | N | N
NUM-OVERDRAFTS <= 2 | Y | N | N | Y | Y | N
AVG-SAV-BAL >= 500 | - | Y | N | Y | N | Y
APPROVE | X
COND-APPROVE | X | X
REJECT | X | X | X

Comments from the Word document

3 basic flow of execution constructs
Sequential
Selection
Repetition
Sub-divide problem solution into modular (self-contained & logical), easy-to-manage chunks, through step-wise refinements
Only 1 start and end termination point

Implement the solution (code program)
Test the solution

Run test plans with known solutions: set of possible inputs along with their associated expected output
Checks for correctness during and after its development
Complete fully-developed test plan as you design the solution (not after)
Must contain enough sets of possible inputs to thoroughly test the program and its algorithm
Normal data: typical, valid values
Extreme data: boundary values
Abnormal data: invalid values
E.g.

Possible inputs		Expected output	Reason for test item
Item #	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

Debug program if fail to meet our expectations
Use data validation and data verification techniques to prevent the wrong input data
Data validation: process to ensure that the data entered is sensible and reasonable

Type	Check if:	Example
Range check	Data value is within certain range	Marks from 0-100
Format check	Data is in right format	dd/mm/yy
Length check	Length of data is entered into a field	Length of password
Presence check	Data is entered into a field	Username cannot be left blank
Check digit	Other digits are correct, checked using last 1 or 2 digits in data	ISBN of a book

Data verification: process to ensure the input data matches the original resource / checks if input data is what user intends to enter
Even when data entered in correct format/range/length, user may still make mistake when inputting data
E.g. asked to enter password twice in order to change it ⇒ double entry of data to verify if 2nd input matches 1st input (proofread input data)
E.g. proofread before submitting forms
(X): Entering account + password is NOT data verification
Debug: detect, locate, and remove all errors in a computer program
Syntax error: syntax rules in the programming language are not adhered to (e.g. error in syntax of a sequence of characters of tokens). Program will not compile until all syntax errors corrected
Logical error: wrong program design, e.g. wrong algorithm to solve the program. Program may be compiled and executed but does not give expected output
Run-time error: detected at run-time, e.g. stack overflow, division by 0, open a file that does not exist
Techniques for debugging:
Specify a point in the source code and have the program execute up to a point (break point) to evaluate different portions of the code
Display the procedure stack to list the sequence of the procedures called during the executing of the program (trace facility)
Mark out as comments and procedures or program statements to be excluded in the testing of the intended portion of the code

Document the solution

Write a description of its purpose and process
Allows other programmers to understand solution and make changes easily when necessary