Comp science paper 2 algorithms

What is abstraction?

Removing unnecessary detail from a problem to focus only on the important parts — simplifying complexity to make a problem easier to solve

What is decomposition?

Breaking a complex problem down into smaller more manageable sub-problems — each sub-problem can then be solved individually

What is algorithmic thinking?

Creating a step by step set of instructions to solve a problem — thinking logically about the sequence of steps needed

What is a structure diagram?

A diagram that shows the structure of a problem broken into subsections — shows how subsections link to each other — used in the design stage before coding

What is pseudocode?

An informal way of describing an algorithm using plain English and programming-like structure — not tied to any specific language — used to plan programs before writing real code

What are the flowchart symbols you need to know?

Oval/rounded rectangle — terminal (start/stop). Rectangle — process. Parallelogram — input/output. Diamond — decision. Rectangle with lines on sides — sub program. Arrow — flow of control

What is a trace table?

A table used to track the values of variables at each step of an algorithm — used to manually follow and check the logic of an algorithm — helps identify errors

What is a syntax error?

An error that breaks the grammatical rules of the programming language — prevents the program from being run or translated at all — eg missing bracket or misspelled keyword

What is a logic error?

An error where the program runs without crashing but produces unexpected or incorrect output — the code is syntactically correct but the logic is wrong — eg using < instead of <=

What is nesting?

Placing one selection or iteration construct inside another — eg an IF statement inside a FOR loop — or a WHILE loop inside an IF statement

LINEAR SEARCH

What is a linear search?

Checks each element of a list one by one from the start until the target is found or the end of the list is reached — works on both sorted and unsorted lists

What are the steps of a linear search?

Step 1 — start at the first element. Step 2 — check if the current element equals the target. Step 3 — if yes — return its position. Step 4 — if no — move to the next element. Step 5 — if end of list reached without finding target — return not found

What are the advantages of linear search?

Works on unsorted lists — simple to understand and implement — no pre-conditions required

What are the disadvantages of linear search?

Slow for large lists — must check every element in the worst case — inefficient compared to binary search on sorted data

Apply a linear search to find 15 in the list 8 3 15 22 7

Check 8 — not 15. Check 3 — not 15. Check 15 — found at position 3 (index 2)

Apply a linear search to find 10 in the list 5 12 3 9 6

Check 5 — no. Check 12 — no. Check 3 — no. Check 9 — no. Check 6 — no. End of list — 10 not found

BINARY SEARCH

What is a binary search?

Divides a sorted list in half — compares the middle element to the target — searches the left half if target is smaller — searches the right half if target is larger — repeats until found or not found

What are the steps of a binary search?

Step 1 — find the middle element of the list. Step 2 — if middle equals target — found. Step 3 — if target is less than middle — repeat on left half. Step 4 — if target is greater than middle — repeat on right half. Step 5 — if list is empty — not found

What is the key pre-condition for binary search?

The list must already be sorted — binary search will not work correctly on an unsorted list

What are the advantages of binary search?

Much faster than linear search for large sorted lists — eliminates half the remaining elements each time — very efficient

What are the disadvantages of binary search?

List must be sorted first — more complex to implement than linear search — sorting has its own cost

Apply a binary search to find 23 in the list 5 10 15 20 23 27 30

Middle = 20. 23 > 20 so search right half: 23 27 30. Middle = 27. 23 < 27 so search left: 23. Middle = 23 — found

Apply a binary search to find 7 in the list 2 4 7 9 11 13 15

Middle = 9. 7 < 9 so search left: 2 4 7. Middle = 4. 7 > 4 so search right: 7. Middle = 7 — found

Apply a binary search to find 6 in the list 1 3 5 7 9

Middle = 5. 6 > 5 so search right: 7 9. Middle = 7. 6 < 7 so search left: empty — 6 not found

BUBBLE SORT

What is a bubble sort?

Repeatedly compares adjacent pairs of elements — swaps them if they are in the wrong order — larger values bubble to the end — repeats passes until no swaps occur in a full pass

What are the steps of a bubble sort?

Step 1 — start at the beginning of the list. Step 2 — compare the first and second elements — if first is greater swap them. Step 3 — move to the next pair and repeat. Step 4 — continue to the end of the list — this completes one pass. Step 5 — repeat passes until a complete pass makes no swaps — list is sorted

How do you know when bubble sort is finished?

When a complete pass through the list produces no swaps — the list must be sorted

What are the advantages of bubble sort?

Simple to understand and implement — can detect an already sorted list quickly — uses very little additional memory

What are the disadvantages of bubble sort?

Very slow for large lists — requires many comparisons and swaps — inefficient compared to merge sort

Sort the list 5 3 8 1 using bubble sort — show all passes

Pass 1 — compare 5 and 3 swap → 3 5 8 1. Compare 5 and 8 no swap. Compare 8 and 1 swap → 3 5 1 8. Pass 2 — compare 3 and 5 no swap. Compare 5 and 1 swap → 3 1 5 8. Compare 5 and 8 no swap. Pass 3 — compare 3 and 1 swap → 1 3 5 8. Compare 3 and 5 no swap. Pass 4 — no swaps — sorted: 1 3 5 8

Sort the list 4 2 6 1 3 using bubble sort — show pass 1 only

Compare 4 and 2 — swap → 2 4 6 1 3. Compare 4 and 6 — no swap. Compare 6 and 1 — swap → 2 4 1 6 3. Compare 6 and 3 — swap → 2 4 1 3 6. End of pass 1

Sort the list 9 5 2 7 using bubble sort — show all passes

Pass 1 — 5 9 2 7 → 5 2 9 7 → 5 2 7 9. Pass 2 — 2 5 7 9 → 2 5 7 9. Pass 3 — no swaps — sorted: 2 5 7 9

MERGE SORT

What is a merge sort?

A divide and conquer algorithm — repeatedly splits the list in half until each section contains only one element — then merges pairs back together in sorted order — very efficient for large lists

What are the steps of a merge sort?

Step 1 — split the list into two halves. Step 2 — recursively split each half again until you have single elements. Step 3 — compare the first elements of two lists — take the smaller one. Step 4 — repeat until both lists are merged into one sorted list. Step 5 — continue merging up until the full list is sorted

How does the merging step work in merge sort?

Take two sorted lists — compare the first element of each — take the smaller and add it to the new sorted list — repeat until one list is empty — add remaining elements — result is one sorted merged list

What are the advantages of merge sort?

Very efficient for large lists — consistent performance — good for sorting linked lists — stable sort

What are the disadvantages of merge sort?

More complex to understand and implement — requires additional memory to store split lists during merging

Sort the list 4 2 7 1 using merge sort — show all steps

Split → 4 2 and 7 1. Split → 4 and 2 and 7 and 1. Merge 4 and 2 → 2 4. Merge 7 and 1 → 1 7. Merge 2 4 and 1 7 → compare 2 and 1 take 1 → compare 2 and 7 take 2 → compare 4 and 7 take 4 → take 7. Result: 1 2 4 7

Sort the list 8 3 5 1 using merge sort — show all steps

Split → 8 3 and 5 1. Split → 8 and 3 and 5 and 1. Merge 8 and 3 → 3 8. Merge 5 and 1 → 1 5. Merge 3 8 and 1 5 → compare 3 and 1 take 1 → compare 3 and 5 take 3 → compare 8 and 5 take 5 → take 8. Result: 1 3 5 8

Sort the list 6 4 2 8 3 1 using merge sort — show splitting stage only

Split → 6 4 2 and 8 3 1. Split → 6 4 and 2 and 8 3 and 1. Split → 6 and 4 and 2 and 8 and 3 and 1. Now merge back in pairs

INSERTION SORT

What is an insertion sort and how does it work?

Insertion sort builds a sorted list one element at a time — it takes each element from the unsorted part and inserts it into the correct position in the sorted part — like sorting playing cards in your hand — you pick up each card and slot it into the right place among the cards already sorted

What are the steps of an insertion sort — explained clearly?

Step 1 — the first element is already considered sorted. Step 2 — take the next element (the key). Step 3 — compare the key to each element in the sorted portion moving right to left. Step 4 — shift each sorted element one position to the right if it is greater than the key. Step 5 — insert the key into the gap created. Step 6 — repeat steps 2 to 5 for every remaining element

How does insertion sort slot an element into the right place?

It compares the element being inserted (the key) with the sorted elements to its left — each sorted element that is bigger than the key gets moved one place to the right — this creates a gap — the key is then placed in that gap — the sorted section grows by one each time

What are the advantages of insertion sort?

Simple to implement — very efficient for small or nearly sorted lists — builds sorted list in place using very little extra memory — can sort as data arrives

What are the disadvantages of insertion sort?

Slow for large unsorted lists — many comparisons and shifts needed in the worst case

Sort the list 5 3 8 1 using insertion sort — show every step clearly

Start — sorted section: 5. Unsorted: 3 8 1. Take key = 3. Compare 3 with 5 — 5 > 3 so shift 5 right. Insert 3 in gap. List now: 3 5 8 1. Take key = 8. Compare 8 with 5 — 5 < 8 so no shift. Insert 8 here. List now: 3 5 8 1. Take key = 1. Compare 1 with 8 — shift 8 right. Compare 1 with 5 — shift 5 right. Compare 1 with 3 — shift 3 right. Insert 1 at start. Sorted: 1 3 5 8

Sort the list 7 2 9 4 using insertion sort — show every step clearly

Start — sorted: 7. Take key = 2. 7 > 2 — shift 7 right. Insert 2. List: 2 7 9 4. Take key = 9. 7 < 9 — no shift. Insert 9. List: 2 7 9 4. Take key = 4. 9 > 4 — shift 9. 7 > 4 — shift 7. 2 < 4 — stop. Insert 4. Sorted: 2 4 7 9

Sort the list 6 1 4 2 using insertion sort — show every step clearly

Start — sorted: 6. Take key = 1. 6 > 1 — shift 6. Insert 1. List: 1 6 4 2. Take key = 4. 6 > 4 — shift 6. 1 < 4 — stop. Insert 4. List: 1 4 6 2. Take key = 2. 6 > 2 — shift 6. 4 > 2 — shift 4. 1 < 2 — stop. Insert 2. Sorted: 1 2 4 6

Sort the list 3 7 1 5 2 using insertion sort — show every step

Sorted: 3. Key=7 — 3<7 no shift — insert. List: 3 7 1 5 2. Key=1 — shift 7 — shift 3 — insert at start. List: 1 3 7 5 2. Key=5 — shift 7 — 3<5 stop — insert. List: 1 3 5 7 2. Key=2 — shift 7 — shift 5 — shift 3 — 1<2 stop — insert. Sorted: 1 2 3 5 7

COMPARISON QUESTIONS

Which sorting algorithm works by comparing and swapping adjacent elements?

Bubble sort

Which sorting algorithm works by dividing the list in half repeatedly then merging?

Merge sort

Which sorting algorithm works by taking each element and inserting it into the correct position in the sorted portion?

Insertion sort

Which searching algorithm requires the list to be sorted first?

Binary search

Which searching algorithm works on any list regardless of order?

Linear search

Which is more efficient for large lists — bubble sort or merge sort?

Merge sort — it has O(n log n) complexity compared to bubble sort's O(n²) — much faster for large data sets

Which sort would be best for a nearly sorted list of 10 items?

Insertion sort — very efficient for small and nearly sorted lists

Which sort would be best for a list of 1 million items?

Merge sort — consistent and efficient performance for large data sets

When would you choose linear search over binary search?

When the list is unsorted and sorting it first would take too long — or when the list is very small making the efficiency difference negligible