Algorithms

What is the purpose of a sub-program (subroutine)?

Explain what decomposition means in the context of problem solving.

What is meant by "abstraction" in computational thinking?

A programmer designing a navigation app ignores details like road colour and building height, and focuses only on road connections and distances. What is this an example of?

A large program to manage a school is broken down into smaller modules: attendance, timetabling, and grades, each developed separately. What computational thinking technique does this illustrate?

Give one benefit of using decomposition when solving a complex programming problem.

Which of the following best demonstrates abstraction?

Explain why using a function/subroutine such as calculateAverage() in a program, without needing to know how it is implemented internally, is an example of abstraction.

A team is developing a large online shopping system. Suggest one way decomposition could be applied to this project.

Which of the following is the best description of how decomposition and abstraction work together when solving a problem?

What does a rectangle represent in a flowchart?

What is the difference between iteration and selection?

What is pseudocode used for?

Trace through this pseudocode and state the output: count ← 0 FOR i ← 1 TO 5 IF i MOD 2 = 0 THEN count ← count + 1 ENDIF ENDFOR OUTPUT count

What shape is used in a flowchart to represent a decision (e.g. an IF statement)?

Convert the following pseudocode into a flowchart description (in words), stating each shape used: INPUT num IF num > 0 THEN OUTPUT "Positive" ELSE OUTPUT "Not positive" ENDIF

In OCR exam reference pseudocode, which keyword is used to mark the end of a FOR loop?

Write pseudocode for an algorithm that inputs a number and outputs whether it is even or odd.

What is the main advantage of representing an algorithm as a flowchart rather than as written pseudocode?

Trace this pseudocode and state the final value output: total ← 0 FOR i ← 1 TO 4 total ← total + i ENDFOR OUTPUT total

A linear search checks each element one at a time. What is its worst case?

Describe how a linear search algorithm finds a target value in a list.

Does a linear search require the list to be sorted before it can be used?

Trace a linear search for the value 7 in the list [3, 8, 7, 1, 9]. State how many comparisons are made and the index found (starting from index 0).

In what situation would a linear search be the most appropriate choice of search algorithm, even though binary search is generally faster?

What is the best-case scenario for a linear search, and how many comparisons does it require?

Write pseudocode for a linear search algorithm that searches for a value called "target" in an array called "myList" of length "n", outputting the index if found or -1 if not found.

What is the time complexity of linear search in the worst case, using Big O notation?

Explain why a linear search will always correctly find a target value (or correctly report it is not present), regardless of how the list is ordered.

A teacher wants to find a specific student's name in a class register of 30 names, which is not in any particular order. Which search algorithm should be used, and why?

How does a binary search work?

What is the pre-condition for binary search?

Trace a binary search for the value 23 in the sorted list [4, 9, 15, 23, 42, 56, 71]. State the values compared at each step, including the index ranges considered.

Trace a binary search for the value 5 in the sorted list [2, 5, 8, 12, 17, 20]. State the indices/values compared at each step (indices starting at 0).

Explain why binary search requires the list to be sorted before it can be used.

In a binary search on a sorted list, if the target value is greater than the value at the middle index, what happens next?

What happens in a binary search if the search range becomes empty (the lower bound exceeds the upper bound) without a match being found?

Write pseudocode for a binary search algorithm on a sorted array "myList" of length n, searching for "target", that outputs the index if found or -1 if not.

A sorted list contains 100 elements. What is the maximum number of comparisons binary search would need to make to find any element (or determine it is absent)?

Explain why binary search would give an incorrect or unreliable result if used on an unsorted list.

What is the best case time complexity of bubble sort and when does it occur?

Describe how the bubble sort algorithm sorts a list into ascending order.

Trace one full pass of bubble sort on the list [5, 2, 4, 1], showing the list after each comparison/swap.

A list of 5 elements is sorted using bubble sort without the early-stopping optimisation. How many comparisons are made in each pass, and how does this relate to the algorithm being O(n²)?

What is the bubble sort optimisation that allows the algorithm to stop early?

How many passes does an unoptimised bubble sort make over a list of n elements in the worst case?

Trace the bubble sort algorithm (with the early-stopping optimisation) on the list [1, 2, 3, 4]. Describe what happens during the first pass and explain whether further passes are needed.

Why is bubble sort generally considered inefficient for sorting large lists?

During a pass of bubble sort, the largest unsorted element is always moved to its correct final position by the end of that pass. Explain why this happens.

A list of 6 items requires 3 full passes before bubble sort (with the early-exit optimisation) terminates with no swaps in the final pass. How many total passes were performed, and why does the algorithm stop after the pass with no swaps?

What are the two main phases of the merge sort algorithm?

Describe what happens during the "split" phase of merge sort.

Describe what happens during the "merge" phase of merge sort.

Show the result of fully splitting the list [8, 3, 5, 1] using merge sort, down to individual elements.

Two sorted sub-lists, [3, 8] and [1, 5], are merged using merge sort's merge step. What is the resulting merged list?

What is the time complexity of merge sort, using Big O notation?

Explain why merge sort is generally more efficient than bubble sort for large lists.

Merge sort is described as a "divide and conquer" algorithm. Explain what this means in the context of merge sort.

Fully trace merge sort on the list [4, 2, 7, 1], showing the split phase down to single elements and the merge phase building the final sorted list.

During the merge phase, two sorted sub-lists are being combined. At each step, how does the algorithm decide which element to place next into the merged list?

What does it mean to say an algorithm is O(n²)?

Compare the worst-case time complexities of linear search and binary search using Big O notation.

Explain why binary search becomes increasingly faster than linear search as the size of the dataset (n) grows larger.

A list contains 1,000,000 sorted items. Approximately how many comparisons would binary search require in the worst case, compared to linear search?

Despite binary search being faster for large sorted datasets, give one reason why linear search might still be preferred in some situations.

Which of these statements correctly compares linear and binary search?

Explain the trade-off involved in choosing binary search over linear search when the data needs to be sorted first specifically for the search.

A phone's contacts app needs to find a contact by name very quickly, even with thousands of contacts. Which search algorithm is most suitable, assuming contacts are stored alphabetically, and why?

On a graph plotting the number of comparisons (y-axis) against the size of the dataset n (x-axis), describe how the lines for linear search and binary search would differ.

Which factor determines whether binary search can be used instead of linear search on a given dataset?