COMPUTER SCIENCE
NOTES
JJJAAADZZZ
PRE-IG
CHAPTER 1: UNDERSTANDING ALGORITHMS
What is an Algorithm?
An algorithm is a step-by-step method used to solve a problem or complete a
task.
Example
A route between two cities calculated by a mapping algorithm.
The algorithm:
• Gives clear instructions to the driver (e.g. “turn left”)
• Follows a sequence of ordered steps
• Produces the same result when given the same conditions
Important Terms
Unambiguous
Instructions must be completely clear and impossible to misunderstand.
• Ambiguous: “turn”
• Unambiguous: “turn left”
Sequence
A sequence is an ordered set of instructions carried out one after another.
Characteristics of an Algorithm
A successful algorithm should be:
JJJAAADZZZ 1
1. Accuracy
Produces the expected outcome correctly.
2. Consistency
Produces the same result each time the same input is used.
3. Efficiency
Uses the shortest possible time and the fewest computer resources.
• Computers are faster and more efficient than manual methods.
Algorithms vs Programs
Algorithm Program
A detailed design for solving a The actual implementation of the
problem algorithm
Focuses on logic and steps Written in a programming language
High-Level Programming Language
A programming language that is similar to natural human language and easier for
humans to understand.
Everyday Use of Algorithms
People follow algorithms every day, often without realising it.
Examples
• Following a recipe
• Washing clothes
• Brushing teeth
• Making coffee
These tasks involve repeated step-by-step instructions.
Ways to Represent an Algorithm
An algorithm can be expressed in three main ways:
JJJAAADZZZ 2
1. Written Descriptions
2. Flowcharts
3. Pseudocode
1. Written Descriptions
The simplest way to express an algorithm using ordinary language.
Example: Making a Cup of Coffee
Fill kettle with water.
Turn on kettle.
Place coffee in cup.
Wait for water to boil.
Pour water into cup.
Add milk and sugar.
Stir.
2. Flowcharts
A flowchart is a visual representation of an algorithm.
Each step is shown using standard symbols.
Flowchart Symbols
Symbol Meaning
Ellipse Start / End
Rectangle Process / Action
Diamond Decision
Parallelogram Input / Output
Arrow Direction of flow
JJJAAADZZZ 3
Example 1: Making a Cup of Coffee
Note
“Wait for kettle to boil” is better than “wait for water to heat” because it is
more precise and less ambiguous.
Example 2: Logging into Account
Important Notes
• Written descriptions and flowcharts are mainly designed for humans to
follow.
• Algorithms form the basis of computer programs.
• Computers are mindless machines:
o They only follow instructions.
JJJAAADZZZ 4
o They cannot think independently.
o They carry out instructions much faster than humans.
3. Pseudocode
Definition
Pseudocode is a structured, code-like way of writing algorithms.
It:
• Focuses on logic rather than programming syntax
• Is easy for humans to read
• Can be translated into any high-level programming language
Example: Adding Two Numbers
SEND ‘Please enter the first number’ TO DISPLAY
RECEIVE firstNumber FROM KEYBOARD
SEND ‘Please enter the second number’ TO DISPLAY
RECEIVE secondNumber FROM KEYBOARD
SET total TO firstNumber + secondNumber
SEND total TO DISPLAY
Characteristics of the Pseudocode
• User input is stored in variables:
o firstNumber
o secondNumber
• The result is stored in:
o total
• Text displayed on screen must be inside quotation marks.
• Variables are displayed without quotation marks.
• Arithmetic operators are used for calculations.
JJJAAADZZZ 5
Variables and Constants
Variable
A container used to store data that can change while a program is running.
Example:
score = 10
The value may later become:
score = 15
Variables allow the same program to process different sets of data.
Constant
A container used to store data that does not change.
Example:
pi = 3.14
Identifier
A unique name given to a variable or constant.
Good identifiers:
• firstNumber
• studentName
• totalMarks
Descriptive identifiers make programs easier to read and understand.
Arithmetic Operators
Operation Operator Example Result
Addition + 5+2 7
Subtraction - 5-2 3
Multiplication * (asterisk) 5*2 10
Real Division / (forward slash) 13 / 4 3.25
JJJAAADZZZ 6
Quotient Division DIV 13 DIV 4 3
Modulus / Remainder MOD 13 MOD 4 1
Exponent / Power ^ (cap/caret) 2^3 8
Naming Conventions
Naming conventions are standard ways of writing identifiers.
1. Camel Case
• No spaces
• Second word begins with a capital letter
Example:
firstNumber
studentName
Alternative Form
All words begin with capitals:
FirstNumber
StudentName
2. Snake Case
• All lowercase
• Words separated using underscores
Example:
first_number
student_name
Important Rule
Be consistent with the naming convention used throughout the algorithm or
program.
JJJAAADZZZ 7
CHAPTER 2: CREATING ALGORITHMS
Avoiding Ambiguity
• Instructions in algorithms must be precise and clear
• Example:
o “Wait for water to boil” → ambiguous
o “Wait until water reaches 100°C” → unambiguous
Why ambiguity is a problem
• Humans can interpret situations (steam, sound, bubbles)
• Computers cannot think or assume
• If unclear, a computer may:
o Continue forever
o Produce incorrect results
JJJAAADZZZ 8
Key Constructs in Algorithms
Constructs are basic building blocks used to create algorithms.
1. Selection (Decision Making)
• Allows a choice between alternatives
• Usually has two outcomes:
o YES / NO
o TRUE / FALSE
2. Iteration (Repetition)
• Repeats a set of steps until a condition is met
Example:
• Keep heating water until it reaches 100°C
Selection and Iteration in Flowcharts
Iteration
• Represented using arrows looping back
• Repeats the same steps until the condition becomes TRUE/YES instead
of duplicating processes
Key Idea
• If answer is NO → repeat the step
• If answer is YES → move forward
Real-Life Example
• Eating food:
JJJAAADZZZ 9
o Repeat eating until plate is empty
Concatenation
Joining two or more strings (text values) together to form a single string
How it Works
• Strings are combined end-to-end in the order they are written.
• No space is added automatically unless you include it.
Example
• "Hello, " + "world" → "Hello, world"
Selection
• Represented by a decision (diamond)
• Has two branches:
o YES
o NO
If-Then-Else Command
• Runs different instructions depending on whether a condition is TRUE
or FALSE.
Basic structure
IF condition THEN
statements (if TRUE)
ELSE
statements (if FALSE)
END IF
How it works
• The condition is tested first.
• If the condition is TRUE → the THEN part runs.
• If the condition is FALSE → the ELSE part runs.
• Only one path is executed.
JJJAAADZZZ 10
Example: Calculating Grades
RECEIVE testScore FROM KEYBOARD
IF testScore >= 80 THEN
SEND ‘A’ TO DISPLAY
ELSE
IF testScore >= 70 THEN
SEND ‘B’ TO DISPLAY
ELSE
IF testScore >= 60 THEN
SEND ‘C’ TO DISPLAY
ELSE
IF testScore > 0 THEN
SEND ‘D’ TO DISPLAY
ELSE
SEND ‘FAIL’ TO DISPLAY
END IF
END IF
END IF
END IF
Summary: The key constructs of algorithms are sequence, selection, and
iteration.
JJJAAADZZZ 11
CHAPTER 3: SORTING AND SEARCHING
ALGORITHMS
Why Sorting and Searching are Important
• We often need to find information → this is called searching
• Without efficient searching algorithms → takes a long time
• Data is stored in lists (sometimes very large – millions of items)
• Searching is faster and easier if data is sorted
• Therefore:
o Sorting → arranges data in order
o Searching → finds specific data
Key Idea
• Two very common tasks in programs:
1. Sorting data
2. Searching for data
• Sorted lists are more useful and efficient to search
Sorting Algorithms
• There are many sorting algorithms
• Some are more efficient than others
1. Bubble Sort
Basic Idea
• Compares pairs of adjacent items
• If they are in the wrong order → swap them
• Repeats until the list is fully sorted
How Bubble Sort Works
1. Start at the beginning of the list
JJJAAADZZZ 12
2. Compare first and second items
o If wrong order → swap
3. Move to next pair (2nd and 3rd)
4. Continue to the end of the list
5. One full pass is completed
6. Repeat passes until no swaps occur
Key Terms
• Pass → one full traversal of the list
• Swap → exchanging two values
Important Features
• Largest values move to the end after each pass
• Like bubbles rising in water
• After:
o 1st pass → largest item is correct
o 2nd pass → second largest is correct
JJJAAADZZZ 13
Efficiency Improvement
• After each pass:
o The last elements are already sorted
o So fewer comparisons are needed
Human vs Computer
• Humans can see when sorted early
• Computer:
o Must complete a full pass with no swaps
o Cannot assume the list is sorted
Flowchart
JJJAAADZZZ 14
2. Merge Sort
Key Idea
• Uses divide and conquer
• Splits a list into smaller lists until each has one item
Process
1. Divide the list into two halves
2. Repeat until all sub-lists contain one element
3. Merge sub-lists back together in sorted order
Important Concepts
• Recursion: repeating the same process on smaller parts
• During merging:
o Compare leftmost elements
o The smaller value is placed first
JJJAAADZZZ 15
Efficiency of Sorting Algorithms
6
4
Time (seconds)
3
Bubble
2 Merge
0
100 1000 15000 250000 500000
Number of items
1. Bubble Sort (Slowest)
• Uses brute force
Brute Force
• Does not aim to improve performance
• Relies on trying all possibilities
Advantages
• Simple to understand and implement
• Suitable for small lists
Disadvantages
• Very slow for large lists (more than 1000 items)
2. Merge Sort (Efficient)
• Uses divide and conquer
Method
• Breaks a problem into smaller parts
• Solves each part
• Combines solutions to form the final result
JJJAAADZZZ 16
Advantages
• Efficient for large datasets
• Faster than bubble sort
Searching Algorithms
• To find a specific item in a list
1. Linear Search (Sequential)
Key Idea
• Checks each item in order
Steps
1. Start at the first item
2. Compare with the target item
3. If equal, stop
4. If not equal, move to the next item
5. Repeat until the item is found or the list ends
Features
• Simple
• Works on unsorted lists
• Slow for large lists
2. Binary Search (Divide and Conquer)
Key Idea
• Repeatedly checks the middle (median) item
Requirements
• List must be sorted
Definitions
• Median: the middle value
• If even number of items: mean of two middle values
JJJAAADZZZ 17
Steps
1. Select the middle item
2. If it equals the target, stop
3. If it is greater than target, search the left half
4. If it is less than target, search the right half
5. Repeat until found or no items remain
Features
• Much faster than linear search
• Reduces the search space each step
Example
Binary Search: 3 attempts
Linear Search: 6 attempts
Comparison
Algorithm Type Purpose Main Idea Best Used
When
Bubble Brute force Sorting Repeatedly compare Small lists
Sort and swap items
JJJAAADZZZ 18
Merge Divide and Sorting Split list into smaller Large lists
Sort conquer lists, then merge in
order
Linear Sequential Searching Check each item one Small or
Search by one unsorted
lists
Binary Divide and Searching Check middle item and Sorted lists
Search conquer halve search area
JJJAAADZZZ 19