COMPUTER

SCIENCE
(Problem solving)

Algorithms
o An algorithm is a step-by-step process of solving the
problem.
o A successful algorithm should satisfy 3 main factors:
 Accuracy - should generate expected outcome.
 Efficiency - should be passed with fewer
resources.
 Consistency - should give the same result each
time it runs.
o Algorithms can be designed in 3 ways:
 Written description
  Flowchart
 Pseudo code
Algorithms are used
o Advantages of algorithms:
for:
 Problem-solving
 Time saving o Solving problems
 Consistency o Making decisions
 Accuracy o Processing data
Variable o Running
o Variables are temporary memory locations that store
values while executing a program.
o At one time, you can store one value.
o Variables consist of a name that is unique and case
sensitive.

Constant
o A constant is fixed data that during the execution of
a program cannot change
o A constant can store a variety of different types of
data, like variables
 Pi π is an example of a mathematical fixed value
that would typically be stored as a constant

Assignment
o Assignment is the process of storing data in a
variable or constant under a descriptive name
o Assignment is performed using the '=' symbol

WRITTEN DESCRIPTION
 o Written description describes a process using natural
language.
o Benefits of written description:
 Provides step-by-step guidance
 Simplifies complex concepts
 Help identify errors

When developing a program there are 3

constructors to consider:
o Sequence:
 Instructions are executed one after the other.
 Ex: Ask the user to enter a number
Add 5 to the number
Display the result
o Selection:
 Selection is when the order of execution is
changed, depending on the set of conditions
 It uses the word if.
o Iteration/Loop
 It controls the order of execution based on a
condition.
 Indefinite loop:
 When order of execution is controlled by a
condition and repeats until the condition is
met.
 Keyword ‘while’ is used for this.
 Ex: Start
Star count = 0
While star count < 3 then
 Send * to display
Star count = Star count + 1

There are 2 types of indefinite

loops:
 When a condition is checked at the
beginning it is a pre-condition loop.
Ex: Start
Star count = 0
While star count < 5 then
Send * to display
Star count = star count+ 1
End
 When a condition is checked at the end
it is a post-condition loop.
Ex: Start
Star count = 0
Repeat
Send * to display
Star count = star count + 1
Until Star Count < 5
End
 Definite loop
  This is when code is repeated a fixed number
of times, continuing in order of execution for
the set number of repetitions.
 Keyword ‘for’ is used for this.
 Ex: Start
For num from 0 to 3
Send * to display
End

FLOWCHARTS
o Flowcharts are diagram representations of algorithms.
o Flowcharts use various notations to represent

instructions.
o Advantages of flowchart:
 Simplifies complex processes
 Saves time
 Easy to understand
 Reduces errors

PSUEDOCODES
o Pseudocode is a text-based tool that uses short
English words/statements to describe an algorithm
o Advantages of pseudocode:
 Makes debugging easier
 Helps in planning
 Simple to write

TRACE TABLES
o A trace table is used to manually test algorithms and
programs for logic errors that appear when an
algorithm or program executes
num factorial i output
5 1 1 1
5 1 2 2
5 2 3 6
5 6 4 24
5 24 5 120
5
❗ Factorial 👉 Multiply a number by all the numbers before it, down to 1

Example: 5 factorial (5!) = 5! = 5 × 4 × 3 × 2 × 1 = 120

o Advantages of trace tables

 Organizes Information
 Helps in debugging

Searching algorithms
o Searching algorithms are step-by-step instructions
that a computer can follow to efficiently locate
specific data in massive data sets (arrays)
o There are 2 searching algorithms:
1. Binary search
2. Linear search

Binary search
o Binary search finds an item by repeatedly dividing a
sorted list into halves.
o Process of Binary search 🔍
1. Look at the middle item median).
2. If the middle item is what you want → found ✅
3. If your item is smaller, search for the left half
4. If your item is bigger, search for the right half
5. Repeat until the item is found or the list ends.

Very important rule ⚠️

👉 The list must be sorted (in order).

o 🔴Because binary search requires a

sorted list so it can correctly decide
which half to search
 Time complexity
Case Time Explanation
complexity
Best Case ✅ O(1) The middle element is the
target.
Average Case O(log n) On average, we divide the list
⚖️ in half several times
Worst Case ❌ O(log n) Even if the target is at the end,
we keep halving the list.

Advantages/ Efficiency Disadvantages/ Not

effcient
Works very fast on large lists Not suitable for smaller lists
Saves time when data is Cannot work without order
already sorted
Time complexity is O(log n) Slow or useless on
unsorted lists
One-line summary 📝
 Binary search is efficient for large, sorted data
but not efficient for small or unsorted data.
Trace table for Binary search
Index [0] [1 [2 [3 [4] [5 [6 [7 [8] [9 [1
] ] ] ] ] ] ] 0]
 Values 25 27 45 48 52 62 74 75 85 92 10
1
Show the steps of binary search algorithm to look for the number
88, which is not in the array.
Start End Calculation of mid- Foun Discard lower,
index index point d higher or
Y OR none
N
0 10 (0+10)/2 = 5 = 62 N Discard lower
6 10 (6+10)/2 = 8 = 85 N Discard lower
9 10 (9+10)/2 = 9 = 92 N Higher discard
9 10 STOP N NOT FOUND
Linear search
o Linear search checks each item one by one until the
target is found.
o Process of Linear Search 🔍
1. Start at the first element of the list.
2. Compare the element with the item you are
searching for.
3. If it matches → Stop, item is found ✅
4. If it doesn’t match → Move to the next element
5. Repeat until the item is found or the list ends
Time Efficiency
Case Time Explanation
complexity
Best Case ✅ O(1) The item is the first
element in the list.
Average Case O(n/2) → On average, we check
⚖️ O(n) half of the list.
Worst Case ❌ O(n) The item is last or not
 in the list

Advantages/Efficiency Disadvantages/Not
efficient
Simple and easy to Slow for large lists
understand
Works on unsorted lists. Time complexity O(n)
Can be used for small or Not suitable for very
large lists (but slow for big data
large lists).

Trace table for linear search

Index [0] [1] [2] [3] [4] [5]
Values 12 25 33 48 57 62
Draw a trace table showing each step of the
search and indicate whether the number is found.
Step Index Value at Found Y/N
checked index
1 0 12 N
2 1 25 N
3 2 33 N
4 3 48 Y
Sorting algorithms
o Sorting algorithms are step-by-step instructions that
a computer can follow to efficiently sort data in
massive datasets
o There are 2 sorting algorithms:
 Bubble sort
 Merge sort

Bubble Sort
o Bubble sort is a simple sorting algorithm which uses
comparisons to sort the algorithms.
o Process of Bubble Sort 🔍
1. Start from the first element of the list
2. Compare the first element with the next one
3. Swap them if they are in the wrong order
4. Move to the next pair and repeat
 5. After one full pass, the largest element moves to
the end
6. Repeat the passes for the remaining elements
7. Stop when no swaps are needed
Time complexity
Case Time Explanation
complexity
Best Case ✔️ O(n) The list is already sorted, so only one
pass is needed.
Average Case O(n²) The list is partially sorted, so many
⚖️ comparisons and swaps are needed.
Worst Case ❌ O(n²) The list is in reverse order, so
maximum comparisons and swaps
occur.

Array = [50, 40, 20, 30]

1st pass 2nd pass

50 40 20 30 40 20 30 50

40 50 20 30 20 40 30 50

40 20 50 30 20 30 40 50
40 20 30 50

Number of passes = length – 1

Number of comparisons in each
pass = Length of array – number of
the relevant pass
Advantges/ Efficiency Disadvantages/ Not
efficient
Simple to understands Slow for larger lists
Works well for small lists Time complexity is high

Merge sort
o Merge sort algorithm uses divide and conquers
method to sort larger data sets.
o Process of merge sort 🔍
1. Divides the list into smaller sub-lists until each
list has one element.
2. Merges those sub-lists back together in sorted
order.
 Time complexity
Case Time Explanation
complexity
Best Case ✔️ O(n log n) The list is already sorted, but
merge sort still divides the
list and merges it.
Average Case O(n log n) The list is in random order.
⚖️ Merge sort always divides
and merges the same way.
Worst Case ❌ O(n log n) The list is in reverse order.
Merge sort still divides and
merges all elements.

⭐ Important Point:
Merge sort always takes O (n
log n) time in all cases because
it divides the list into halves
and merges them.

Advantages/ Efficiency Disadvantages/ Not

efficient
Stable sort Slow for small list
Fast for large data Not memory efficient
Same speed in all cases High memory usage

Decomposition
o Decomposition means breaking problems down into
smaller more manageable parts, which are easier to
solve.

Abstraction
o The process of removing or hiding unnecessary detail
so that only important points remain.
o Example:
 Real-world object: Car
 Details we don’t need: color of screws, material
of engine parts.
 Details we do need for a program: speed, fuel
level, start/stop.