IB Computer Science Designed by:

Professor. A. Lawson
Sources: Online Materials, thanks for all

Topic.4:
Problem-solving and programming
1
 IB Computer Science
Topic 4 - Overview
Thinking procedurally
4.1.1 Identify the procedure appropriate to solving a problem
4.1.2 Evaluate whether the order in which activities are undertaken will result in the
required outcome
4.1.3 Explain the role of sub-procedures in solving a problem
Thinking logically
4.1.4 Identify when decision-making is required in a specified situation
4.1.5 Identify the decisions required for the solution to a specified problem
4.1.6 Identify the condition associated with a given decision in a specified problem
4.1.7 Explain the relationship between the decisions and conditions of a system
4.1.8 Deduce logical rules for real-world situations
Thinking ahead
4.1.9 Identify the inputs and outputs required in a solution
4.1.10 Identify pre-planning in a suggested problem and solution
4.1.11 Explain the need for pre-conditions when executing an algorithm
4.1.12 Outline the pre- and post-conditions to a specified problem
4.1.13 Identify exceptions that need to be considered in a specified problem solution
Thinking concurrently
4.1.14 Identify the parts of a solution that could be implemented concurrently
4.1.15 Describe how concurrent processing can be used to solve a problem
4.1.16 Evaluate the decision to use concurrent processing in solving a problem
Thinking abstractly
4.1.17 Identify examples of abstraction
4.1.18 Explain why abstraction is required in the derivation of computational solutions
for a specified situation
4.1.19 Construct an abstraction from a specified situation
4.1.20 Distinguish between a real-world entity and its abstraction

2
 IB Computer Science
Topic 4.1.1
Identify the procedure appropriate to solving a problem
• Evaluate whether the order in which activities are
undertaken will result in the required outcome.
• Explain the role of sub-procedures in solving a problem.

Examples: recipes, block-arrow-block-arrow, etc.

What is your daily schedule routine

Thinking procedurally involves having the

decomposed parts of a problem available.
Following that you are going to look at how
these can be ordered procedurally in order to
create a program or algorithm. The outcome of
thinking procedurally is to:
•Identify the components of a problem.
•Identify the components of a solution to
a problem.
•Determine the order of steps needed to
solve a problem.
•Identify sub-procedures necessary to
solve a problem.

IB Computer Science
Topic 4.1.2
Evaluate whether the order in
which activities are undertaken
will result in the required outcome

3
Lets Practice by doing some
Java problems

Username:
lawsonsclass
Password:
codechef021

https://www.codechef.com/problems/school http://codingbat.com/java

IB Computer Science
Topic 4.1.3 – 4.1.8

SUB-Procedures

Explain the role of sub-procedures

in solving a problem

Identify when decision-making is

required in a specified situation

Identify the decisions required for

the solution to a specified
problem

4
Explain the role of sub-procedures
in solving a problem

Conditions (Pseudo code)

Explain the relationship

between the decisions and
conditions of a system

Deduce logical rules for

real-world situations

5
 Logic algorithm mathematical games to practice

https://www.mathplayground.com/logicgames.html

Explain why abstraction is required in the derivation of

computational solutions for a specified solution

Why use abstraction?

• Abstraction can be viewed both as a process and as an entity.
• Abstraction enables a person to concentrate on the essential aspects of
the problem on hand, while ignoring details that tend to be distracting.
• The real world is sufficiently complex and presents to many items
simultaneously to be dealt with.
• To solve problems well, we need to conquer this complexity.
• Abstraction is a convenient way to deal with complexity. 6
 IB Computer Science
Topic 4.1.9
Thinking ahead = Thinking concurrently = Thinking abstractly

Construct an abstraction from a

specified situation

Levels of abstraction through

successive decomposition
Realistic Abstract

How school departments are

broken down by hiatus of each
employer and subject

7
 IB Computer Science
Topic 4.1.20
Distinguish between a
real-world entity and its
abstraction

Real vs abstract: it’s all about the details

IB Computer Science
Topic 4.2.1
Describe the characteristics of standard algorithms on linear arrays
The four key standard algorithms:
• Sequential search
• Binary search
• Bubble sort
• Selection sort
 IB Computer Science
Topic 4.2.1
Sequential search
• Linear search or sequential search is an algorithm to find an
item in a list.
• It starts at the first element and compares each element to
the one it’s looking for until it finds it.
• Commonly used with collections (which are unsorted lists
of items) and text/csv file reading.

Binary search

Sequential search (video)

Binary search (Pseudocode)

https://www.youtube.com/watch?v=D5SrAga1pno
 IB Computer Science
Topic 4.2.1
Binary search
• Binary search, also known as half-interval search, is a search algorithm that
finds the position of a target value within a sorted array.
• It works by comparing the target value to the middle element of the array;
• If they are unequal, the lower or upper half of the array is eliminated
depending on the result and the search is repeated in the remaining sub-array
until it is successful.
• It only applies to SORTED arrays (where there are usually no duplicate values,
or duplicates do not matter)

Bubble sort
• Bubble sort is a simple sorting algorithm that
repeatedly steps through the list to be sorted,
compares each pair of adjacent items and swaps
them if they are in the wrong order.
• The pass through the list is repeated until no
swaps are needed, which indicates that the list is
sorted.
• The algorithm, which is a comparison sort, is
named for the way smaller elements "bubble" to
the top of the list.
• Although the algorithm is simple, it is too slow
and impractical for most problem

Selection sort
• Selection sort is a sorting algorithm and it is inefficient on large lists
• Selection sort is noted for its simplicity, and it has performance advantages over
more complicated algorithms in certain situations, particularly where memory is
limited.
• The algorithm divides the input list into two parts: the sublist of items already
sorted, which is built up from left to right at the front (left) of the list, and the sublist
of items remaining to be sorted that occupy the rest of the list.
• Initially, the sorted sublist is empty and the unsorted sublist is the entire input list.
• The algorithm proceeds by finding the smallest (or largest, depending on sorting
order) element in the unsorted sublist, exchanging (swapping) it with the leftmost
unsorted element (putting it in sorted order), and moving the sublist boundaries
one element to the right.
 IB Computer Science
Topic 4.2.1
Selection sort
Selection sort (Pseudocode)
A - an array containing the
list of numbers numItems -
the number of numbers in
the list
for i = 0 to numItems - 1 for j
= i+1 to numItems if A[i] >
A[j] // Swap the entries
Temp = A[i] A[i] = A[j] A[j] =
Temp end if end loop
end loop

IB Computer Science
Topic 4.2.2
Outline the standard operations of collections
Collections?
• As far as the IB is concerned, collections are UNORDERED lists
usually of UNKNOWN length or size.
• In practice we usually program collections using LinkedLists in Java.
• This means that we must remember there are a few things that
LinkedLists CAN do that collections CANNOT.
Standard collection operations
.addItem( data ) = add data item to the collection .resetNext() =
start at the beginning .hasNext() → tells whether there is another
item in the list .getNext() → retrieves a data item from the collection
.isEmpty() → check whether collection is empty
 IB Computer Science
Topic 4.2.2
Collections (Pseudocode)
NAMES = new Collection()
NAME = ""
loop while NAME <> "quit"
input NAME
if NAME <> "quit" then
if NAMES.contains(NAME) then
output NAME , " returned" Task: This program inputs NAMES of students
NAMES.remove(NAME) who are leaving school early - for example to visit
else the doctor. The names are collected in a
Collection list. When a student returns, tying the
output NAME , " is leaving" same name again removes that name from the
NAMES.addItem(NAME) list. At the end of the day, the secretary types
end if "quit" to end the program and see a list of all
end if students who left but did not return.
end loop
output "The following students left and did not return"
NAMES.resetNext()
loop while NAMES.hasNext()
output NAMES.getNext()
end loop

IB Computer Science
Topic 4.2.3
Discuss an algorithm to solve a specific problem
Basic comparisons
• A binary search is faster - O( log N ), but can only be performed in a SORTED list
• A sequential search is slower - O(N) but can be performed whether the list is sorted or not
• A bubble sort can "quit early" if no swaps are made in a pass. But it makes lots of swaps.
• A selection sort must always perform N passes it cannot "quit early". But it makes fewer
swaps maximum of N swaps
• Both bubble and selection sort are O(n^2) = equally complex

Useful resources for algorithms

https://www.toptal.com/developers/sorting-algorithms/
 IB Computer Science
Topic 4.2.4

Analyse an algorithm
presented as a flow chart

Make sure you know

the symbols

Examples of symbol use explained: similar to questions

asked in your IB paper
 IB Computer Science
Topic 4.2.5

Analyse an algorithm
presented in pseudocode

Questions in exam pertaining to topic may include the following: variables, calculations,
simple and nested loops, simple conditionals and multiple or nested conditionals.

IB Computer Science
Topic 4.2.6

Construct pseudocode to
represent an algorithm

IB Computer Science
Topic 4.2.7
Suggest suitable algorithms to A Tale of Four Algorithms
solve a specific problem Article by: Virginia Eubanks

Questions in exam pertaining to topic may

include the following: both standard algorithms
and novel algorithms, efficiency, correctness,
reliability and flexibility. Click on picture for article link
 IB Computer Science
Topic 4.2.7
Past Paper Example 1:

Refer to past paper to check how

questions may be asked during
exam with topic context.

Tips for getting practice

• Try to come up with your own
problems and see if you can solve Past Paper Example 2:
them.
• Try to share your created problems
with a friend and see if you can solve
his/hers. Past Paper Example 3:

• For example:
If PRICES and NAMES and
INVENTORY are parallel arrays, write
an algorithm that finds all the items
where INVENTORY is below 10 items,
and adds 20% to the PRICES of those
items.

Past Paper Example 4:

 IB Computer Science
Topic 4.2.8
Deduce the efficiency of an algorithm in the context of its use
Notes:
• You should understand the difference in
efficiency between a single loop, nested loops, a
loop that ends when a condition is met or
questions of similar complexity.
• You should also be able to suggest changes in
an algorithm that would improve efficiency, for
example, using a flag to stop a search
immediately when an item is found, rather than
continuing the search through the entire list.

What effects run time of an algorithm?

(a) computer used, the hardware platform

(b) representation of abstract data types (ADT's)
(c) efficiency of compiler
(d) competence of programmer (programming skills)
(e) complexity of underlying algorithm
(f) size of the input

Generally (e) and (f) are the most important

Definition: Complexity
• Complexity of an algorithm is a measure of the
amount of time and/or space required by an
algorithm for an input of a given size (n).
• Time for an algorithm to run t(n) is characterised
by the size of the input.
• We usually try and estimate the WORST CASE, and
sometimes the BEST CASE, and very rarely the
AVERAGE CASE.

What do we measure?
• In analysing an algorithm, rather than a piece of
code, we will try and predict the number of times
the principle activity of that algorithm is performed.
• For example, if we are analysing a sorting
algorithm we might count the number of
comparisons performed.
 IB Computer Science
Topic 4.2.8
Best vs Worst vs Average case
• Worst Case
– is the maximum run time, over all inputs of size n,
ignoring effects (a) through (d) above. That is, we
only consider the "number of times the principle
activity of that algorithm is performed".
• Best Case
– In this case we look at specific instances of input of
size n. For example, we might get best behaviour
from a sorting algorithm if the input to it is already
sorted.
• Average Case
– Arguably, average case is the most useful measure.
It might be the case that worst case behaviour is
pathological and extremely rare, and that we are
more concerned about how the algorithm runs in
the general case. Unfortunately this is typically a
very difficult thing to measure.

The growth rate of t(n)

• Suppose the worst case time for algorithm A is:
t(n) = 60*n*n + 5*n + 1 for input of size n.
• We ignore the coefficient that is applied to the
most significant (dominating) term in t(n).
• Consequently this only affects the "units" in
which we measure. It does not affect how the
worst case time grows with n (input size) but only
the units in which we measure worst case time
• Under these assumptions we can say: t(n) grows
like n*n as n increases or t(n) = O(n*n)
• which reads "t(n) is of the order n squared" or as
"t(n) is bigoh n squared"

Example (the tyranny of growth)

• In order (from least to most complex)…
– A = (log2 n) {log to base 2 of n}
–B = n {linear in n}
– C = (n * (log2 n)) {n log n}
– D = (n²) {quadratic in n}
– E = (n³) {cubic in n}
– F = (2n) {exponential in n}
–G = (3n) {exponential in n}
– H = (n!) {factorial in n}
 IB Computer Science
Topic 4.2.8
Tabulated below,
are a number of
functions against
n (from 1 to 10)

Big O notation summary

On a more basic note:

• A single loop that repeats n times takes n
time to run
• A nested loop that repeats n times takes n
x n times to run (potentially MUCH longer)
• A loop that checks a condition/flag (usually
a WHILE loop) only loops while it has to – no
unnecessary looping!
• So, want a loop to run faster? Try using a
flag-based (WHILE) loop that will stop once
the item you’re searching for is found. The
alternative (FOR loop) would check
EVERYTHING every time it runs.
 IB Computer Science
Topic 4.2.9
Determine the number of times
a step in an algorithm will be
performed for given input data
“Number of steps” is officially
called ITERATIONS

IB Computer Science
Topic 4.3.1
State the fundamental
operations of a computer
All CPUs have sets of instructions, also
called the fundamental operations,
that enable commands to be
processed.

The four most fundamental operations are:

>ADD
Fundamental vs Complex
>COMPARE An example of fundamental instructions:
>RETRIEVE (sometimes called LOAD) LOAD register 34AB39
>STORE (sometimes called SAVE) ADD 29 STORE result
COMPARE result to register 4

Examples of complex instructions:

Find the biggest number in an array
Sort the names alphabetically
 IB Computer Science
Topic 4.3.2
Distinguish between fundamental and
compound operations of a computer

Key difference: complexity

• A fundamental operation could be something like add two numbers, store a
number, move a number to another location in RAM etc.
• These are operations that do not require the processor to go through a large
number of sub operations to reach a result.
• A compound operation is an operation that involves a number of stages/other
operations. Think of it as a group of operations that combine together to form
an operation.

Fundamental vs Compound
An example of fundamental instructions: Examples of compound/complex
instructions:
LOAD register 34AB39 Find the biggest number in an array
ADD 29 Sort the names alphabetically
STORE result
COMPARE result to register 4

IB Computer Science
Topic 4.3.3
Explain the essential features of a
computer language

Two types of languages

• Human languages like English, Arabic, French,
Flemish are called natural languages.
• Computer languages are either high level
languages (like Java, C#, VisualBasic, Python, etc.) or
low level (like Assembly or Machine Code).
Natural vs Computer languages

Natural (Human) Computer (Java)

Varying vocabulary ‘way’ Fixed vocabulary int, public, String

Ambiguous He saw that gas can Unambiguous meaning String answer

explode = “#yolo”;
Grammar & syntax inconsistent Grammar & syntax consistent

Essential features of a computer language:

➢ Fixed vocabulary
➢ Unambiguous meaning
➢ Consistent grammar & syntax

IB Computer Science
Topic 4.3.4
Explain the need for
higher level languages
Low level vs High level language

Why do we need high level languages?

– High level language = similar to human language (like English)
– Low level language = close to the binary code used to actually process the instruction.
• As human needs for computer systems have expanded, it is necessary to abstract from the
basic operations of a computer.
• It would take far too long to write the type of systems needed today in machine code.

Comparison: C vs Java vs Python

IB Computer Science
Topic 4.3.5
Outline the need for a translation process from a
higher level language to machine executable code
 IB Computer Science
Topic 4.3.5
Video: Interpreter vs Compiler

https://www.youtube.com/watch?v=_C5AHaS1mOA#t=44

Key terms
• Compiler - If the translator translates a high level language into a lower level language
(done in a batch)
• Interpreter - the translator translates a high level language into an intermediate code
which will be immediately executed by the CPU (done line by line)
• Assembler - the translator translates assembly language to machine code (mnemonics to
binary)

Levels of language

Java virtual machine

* Java applications run on a virtual machine (the Java Virtual Machine or JVM).
This virtual machine is installed on the computer (e.g. PC, Mac, Smart Phone, Ticket Machine)
and allows the same java code to be run on many different types of hardware.
* Even though the hardware architecture and instruction sets of each of these devices is
different the virtual machine is the same.
* The trick is that the virtual machine software needs to match the hardware it will be installed
on, so you need to get the correct version of the virtual machine, but once you have it then you
can run any java program.
* This is good for the java programmer as he does not have to write lots of different versions of
the program he is writing, for each of the devices he wants it to run on.
* After the java program is written it can be deployed to any device that has the Java Virtual
Machine installed on it.
 IB Computer Science
Topic 4.3.6
Define the terms: variable,
constant, operator, object

Variable
• Variables are storage location for data in a program.
• They are a way of naming a memory location for later usage (to put a
value into/retrieve a value).
• Each variable has a name and a data type that is determined at its
creation (and cannot be changed).

Constant
• A constant is an identifier with an associated value which cannot be
altered by the program during normal execute -the value is constant.
• This is contrasted with a variable, which is an identifier with a value
that can be changed during normal execution – the value is variable.

Operator
• A character/set of characters that represents an action
• Types: – Boolean operators (AND, OR, &&, ||) for working out
true/false situations – Arithmetic operators (+, -, ++, --, /, %, div, mod)
for doing simple mathematical calculations – Assignment operators ,
which assign a specified value to another value and ( = ) – Relational
operators , which compare two values (<, >, >=, <=, ==, !=, .equals() )

Operator
Symbols:
 IB Computer Science
Topic 4.3.6
Object
• In Object-oriented programming (OOP), an object is an instance of a
class.
• Objects are an abstraction: they hold both data (states), and ways to
manipulate the data (behaviours).

Another set of definitions:

• Variable: a name that represents a value
• Constant: a value that cannot change during runtime • Operator:
numerical operations, String operations, logical (boolean) operations,
e.g. operations on primitive data types
• Object: a collection of data and methods, created from a design
(class), allowing multiple INSTANCES. An object has a REFERENCE
VARIABLE that "points to" the contents of the object

IB Computer Science
Topic 4.3.7
Define the operators:
=, ≠, <, <=, >, >=, mod, div

Simple Assignment operator

• = means “gets the value”
• Example: int i = 25
• Reads: An integer i gets the value of 25

Arithmetic Operators
• +: used for adding two numbers (also used for String
concatenation)
• -: used for subtractions
• *: used for multiplication
• /: used for division
•% or mod: returns the remainder of a division calculation
• div: returns the numbers of times X divides into Y without a
remainder
 IB Computer Science
Topic 4.3.7
Unary operators
• ++: Increment operator; increments a value by 1
• i++ is the same as i = i + 1
• --: Decrement operator; decrements a value by 1
• i-- is the same as i = i - 1

Equality and Relational Operators

• == : Equal to (only for non-Strings!)
• != : Not equal to
• >: Greater than
• >=: Greater than or equal to
• <: Less than
• <=: Less than or equal to

IB Computer Science
Topic 4.3.8
Analyse the use of For example, identify and justify the use of a
constant as opposed to a variable in a given
variables, constants and situation. These will depend on the
operators in algorithms algorithm presented in the exam and are
impossible to predict.

Past Paper - Example type questions:

QUANTITY = input("How many hamburgers do you want?")

if QUANTITY >= 10 then

PRICE = 2.59
else if QUANTITY <= 9 AND QUANTITY >= 5 then
PRICE = 2.89
else if QUANTITY < 5 then
PRICE = 3.25
end if

Why should QUANTITY always be a variable?

Is PRICE a variable or a constant?
What is 3.25?
 IB Computer Science
Topic 4.3.9
Construct algorithms using loops and branching

Practice code that uses:

• IF / ELSE
• Boolean conditions, e.g. WHILE list.hasNext()

Practice code that uses:

• FOR loops
• WHILE loops
 IB Computer Science
Topic 4.3.10

Describe the characteristics and

applications of a collection

In ‘real life’ Java, there are many

types of collections.
In IB land Java, think of a
collection as a Linked List with an
unknown size/length.

Important: the order is not known

A collection is like a linked-list, but the order of elements is not guaranteed.

Collection methods in Pseudocode are:

• .addItem( new data item )
• .resetNext( ) start at beginning of list
• .hasNext( ) checks whether there are still
more items in the list
• .getNext( ) retrieve the next item in the list
• .isEmpty( ) check whether the list is empty

NAMES = new Collection() Example of

NAMES.addItem("Bob") NAMES.addItem("Dave") collection in
NAMES.addItem("Betty") NAMES.addItem("Kim") Pseudo code
NAMES.addItem("Debbie") NAMES.addItem("Lucy")
NAMES.resetNext()
output "These names start with D"
loop while NAMES.hasNext() NAME = NAMES.getNext() if
firstLetter(NAME) = "D" then output NAME end if end loop
method firstLetter(s) return s.substring(0,1) end method
 IB Computer Science
Topic 4.3.10
Some applications for lists

• Useful for group of items when you don’t know how many items you’ll be
needing/using (contrast to arrays where the size is set in stone at creation)
• Because the collection is only as big as you need it to be, it is an efficient use
of RAM (memory)
• Can be of any data type (primitive or even your own object)

IB Computer Science
Topic 4.3.11
Construct algorithms using the
access methods of a collection
Important: only use the methods below
A collection is like a linked-list, but the order of elements is not guaranteed so
you can’t use .get(x) or .size() etc.

Collection methods in Pseudocode are:

• .addItem( new data item )
• .resetNext( ) start at beginning of list
• .hasNext( ) checks whether there are still
more items in the list
• .getNext( ) retrieve the next item in the list
• .isEmpty( ) check whether the list is empty

IB Computer Science
Topic 4.3.12
Discuss the need for sub-
programmes and collections
within programmed
solutions
 IB Computer Science
Topic 4.3.12
Advantages to modular design
• Modular programming is an important and
beneficial approach to programming problems.
They make program development easier, and they
can also help with future development projects.

• Key benefits/advantages:
– Usefulness of reusable code
– Eases program organization, both for the
individual programmer, team members
– Makes future maintenance easier – you only
have fix/update a module, not the whole program

Manageable tasks
• Breaking down a programming project into
modules makes it more manageable.
• These individual modules are easier to design,
implement and test.
• Then you can use these modules to construct the
overall program.

Distributed development
• Modular programming allows distributed
development.
• By breaking down the problem into multiple
tasks, different developers can work in parallel.
• And this will shorten the development time.
 IB Computer Science
Topic 4.3.12
Code reusability
• A program module can be reused in programs.
• This is a convenient feature because it reduces
redundant code.
• Modules can also be reused in future projects.
• It is much easier to reuse a module than
recreate program logic from scratch.

Program readability
• Modular programming leads to more
readable programs.
• Modules can be implemented as user-defined
functions.
• A program that has plenty of functions is
straightforward.
• But a program with no functions can be very
long and hard to follow.

IB Computer Science
Topic 4.3.13
Construct algorithms:
using predefined sub-programmes, one-
dimensional arrays and/or collections

Important: only use the methods below

A collection is like a linked-list, but the order of
elements is not guaranteed so you can’t use .get(x)
or .size() etc.

Collection methods in Pseudocode are:

• .addItem( new data item )
• .resetNext( ) start at beginning of list
• .hasNext( ) checks whether there are still
more items in the list
• .getNext( ) retrieve the next item in the list
• .isEmpty( ) check whether the list is empty
 IB Computer Science
Topic 4.3.13

Averaging an array

Copying from a collection

into an array

Factors

Copying a
collection into an
array in reverse