3D.1.1 Algorithms and the order of an algorithm Quiz: Pearson Edexcel Further Maths, Unit 35

The 20 questions

1. What does the order of an algorithm describe?

   • Exact run time
   • Growth rate
   • Line count
   • Memory usage

2. For graph algorithms, what typically represents the problem size?

   • Vertex count
   • Weight sum
   • Face count
   • Colour number

3. In a list of N items with N odd, the middle item is in position

   • N/2
   • (N-1)/2
   • N+1
   • (N+1)/2

4. Bubble sort has order

   • n log n
   • 2^n
   • n
   • n^2

5. How is the computational efficiency of an algorithm usually measured?

   • Code length
   • Clock time
   • Operation count
   • Variable total

6. What does the degree or valency of a vertex represent?

   • Path length
   • Loop count
   • Adjacent vertices
   • Incident edges

7. Which condition defines a simple path in a graph?

   • all vertices visited
   • no edge repeated
   • no vertex repeated
   • starts and ends same

8. An algorithm takes time proportional to n^2. If the problem size doubles, by roughly what factor does the running time increase?

   • 8 times
   • 16 times
   • 2 times
   • 4 times

9. A graph has vertex degrees 4, 3, 3, 2 and 2. How many edges does it have?

   • 10
   • 6
   • 14
   • 7

10. Which degree sequence cannot belong to any graph?

    • 4, 3, 3
    • 2, 2, 2
    • 1, 1, 2
    • 3, 3, 3

11. How many edges does the complete graph K5 have?

    • 10
    • 5
    • 20
    • 25

12. An algorithm needs T(n) = 3n^2 + 5n operations for input size n. What is its order?

    • O(n^2)
    • O(n)
    • O(n^3)
    • O(log n)

13. A list has 6 items. In which position is the middle item, using the usual definition for an even-length list?

    • 6th
    • 4th
    • 3.5th
    • 3rd

14. Bubble sort is applied to a list of 4 items. How many comparisons are made in the first pass?

    • 4
    • 6
    • 3
    • 2

15. Algorithm A needs n^2 operations and algorithm B needs 100n operations. For n = 10, which takes fewer operations, and how many does it need?

    • B, with 1000 operations
    • B, with 100 operations
    • A, with 1000 operations
    • A, with 100 operations

16. For which values of n does algorithm B (100n operations) need fewer operations than algorithm A (n^2 operations)?

    • n > 100
    • n < 100
    • n > 1000
    • n > 10

17. A tree has 8 vertices. How many edges does it have?

    • 6
    • 8
    • 7
    • 16

18. Which graph feature immediately rules out isomorphism if mismatched?

    • Embedding plane
    • Vertex labels
    • Degree sequence
    • Edge weights

19. Why is algorithm order preferred over single-computer timing?

    • Easier calculation
    • Hardware independence
    • Exact timing
    • Lower memory

20. A bubble sort of 20 items needs n(n - 1)/2 comparisons in the worst case. How many comparisons is that?

    • 200
    • 190
    • 380
    • 400

Related quizzes

• Bin packing, sorting, Eulerian graphs and planarity Quiz · 3D.1.2-3D.1.4 · 20 questions
• Proof by mathematical induction Quiz · 1.1 · 20 questions
• Quadratic equations and complex arithmetic Quiz · 2.1-2.2 · 20 questions
• Matrix arithmetic and inverses Quiz · 3.1-3.2 · 20 questions
• Expectation of discrete random variables Quiz · 3B.1.1 · 20 questions
• The Poisson distribution Quiz · 3B.2.1 · 20 questions
• Geometric and negative binomial models Quiz · 3B.3.1 · 20 questions
• Hypothesis tests for the Poisson distribution Quiz · 3B.4.1 · 20 questions
• Applying the Central Limit Theorem Quiz · 3B.5.1 · 20 questions
• Goodness of fit tests for discrete distributions Quiz · 3B.6.1 · 20 questions