Study notes
No notes have been generated for this topic yet. Open the topic page online and click Generate notes first.
Past exam questions (12)
2021 · Part A · Q14(b)(v) · p.22
Explain why (n, n, n) is a winning position in a game where 3 piles are used?
2021 · Part A · Q14(b)(iv) · p.22
Hence, or otherwise, describe a winning strategy from state (n, m), where n ≠ m.
2020 · Part A · Q12 · p.10
The travelling salesperson problem is commonly used in the study of algorithms and appears in formats similar to the problem below. "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city once and returns to the original city?" [Diagram: A graph representing cities (numbered 1 to 5) and distances between them. City 1 is labelled 'Start / Finish'. Distances are shown on the edges: 1-2 (10), 1-4 (5), 2-3 (8), 2-5 (14), 3-4 (7), 3-5 (6), 4-5 (20).] Why would heuristics be considered a good approach to solving a problem such as this?
2020 · Part A · Q13(c) · p.15
Why is the study of algorithmic efficiency considered to be important in computer science?
2020 · Part A · Q13(b)(iii) · p.14
What is the maximum number of comparisons the binary search algorithm would need to make if the value to be searched for did not exist in a list of 8 items? Answer: Space for rough work:
2020 · Part A · Q13(b)(ii) · p.13
Step through how the binary search algorithm finds the integer 28 in the list L shown below. [Diagram: A list L of 8 integers with indices 0 to 7. L = [3, 7, 13, 18, 28, 35, 41, 50]. Arrows indicate 'left' pointing to index 0, 'mid' pointing to index 3, and 'right' pointing to index 7.]
2020 · Part A · Q13(b)(i) · p.13
State one disadvantage of the binary search algorithm.
2020 · Part A · Q13(a)(v) · p.12
What is the worst-case time complexity of this search algorithm? Explain your answer. [Visual aid: Python code for a linear search algorithm]
2020 · Part A · Q13(a)(iv) · p.12
What would be the value of index after running the algorithm if the user entered a name that was not present in the list called names? [Visual aid: Python code for a linear search algorithm]
2020 · Part A · Q13(a)(iii) · p.12
Step through how the algorithm finds the name Zoe in the list called names. [Visual aid: Python code for a linear search algorithm]
2020 · Part A · Q13(a)(i) · p.11
State the name of the above search algorithm. [Visual aid: Python code for a linear search algorithm]
2020 · Part A · Q8 · p.7
The diagram below sets out the operation of the bubble sort algorithm to sort the list of integers [8, 5, 9, 7, 6]. The algorithm works by scanning over the data in four passes. The diagram is complete for pass 1 and started for pass 2. Complete the diagram for passes 2, 3 and 4. You only need to fill in the numbers. [Diagram: Bubble sort algorithm steps for list [8, 5, 9, 7, 6]. Pass 1 shows initial list and intermediate steps. Pass 2 starts with [5, 8, 7, 6, 9] and shows one intermediate step. Pass 3 starts with [5, 7, 6, 8, 9]. Pass 4 starts with [5, 6, 7, 8, 9] and is labelled (finished).]