4.4.1.8 Problem reduction and decomposition Quiz: AQA Computer Science, Unit 4

The 20 questions

1. What is problem abstraction or reduction?

   • Converting a problem into a picture
   • Adding extra detail until the problem becomes unique and cannot be matched
   • Removing details until the problem reduces to one that is already solved
   • Splitting a problem into many unrelated tasks

2. A question asks for the median of a list of numbers. Which known problem can it be reduced to?

   • Sorting the list and then picking the middle value
   • Searching the list for a fixed string
   • Drawing a graph of the list
   • Encrypting the list so that the middle value is hidden from the user

3. Checking whether two words are anagrams can be reduced to which simpler problem?

   • Counting the words in a sentence
   • Finding the longest word in a dictionary by comparing each word to every other
   • Sorting the letters of each word and comparing the results
   • Compressing each word into binary

4. A route between two towns on a road map is required. Which problem does this reduce to?

   • Sorting a list of town names alphabetically, then printing each one in order
   • Shortest path in a weighted graph
   • Hashing a password
   • Rendering a map image

5. Procedural decomposition means which of the following?

   • Breaking a problem into sub-problems, each accomplishing an identifiable task
   • Merging several separate programs into one large program with one shared variable
   • Converting every loop into recursion
   • Removing all variables from a program

6. A program that prints a report is decomposed into 'read data', 'calculate totals' and 'print report'. What is this an example of?

   • Information hiding
   • Automatic garbage collection
   • Procedural decomposition
   • Data encryption

7. Why is problem reduction useful?

   • It lets a new problem reuse algorithms already known to solve a related problem
   • It guarantees that every problem has a unique solution, which can always be found easily
   • It removes the need to test the solution
   • It makes all algorithms run in constant time

8. A shortest route problem with traffic times is reduced to a graph with weights. Which step is this?

   • Replacing the graph with a list of cities
   • Adding random noise to the data so that the algorithm cannot be predicted
   • Removing details until the problem fits a known solution
   • Duplicating the data for safety

9. Which is the best example of decomposing a problem into sub-problems?

   • Finding the maximum value by first sorting, then reading the last item
   • Storing all data in a single variable
   • Finding the maximum value by sorting the list, then reading the last item of the list
   • Repeating the same calculation many times without structure

10. A problem reduces to finding a path in a graph with no weights. Which algorithm is most suitable?

    • Bubble sort
    • Merge sort
    • Linear search of a list
    • Breadth-first search

11. Which statement about problem reduction is correct?

    • It is only valid when the reduced problem has a known solution
    • It is only used in hardware design
    • It requires the original problem to be discarded
    • It always produces a faster algorithm than the best method for the original problem

12. A chess-like puzzle is reduced to a graph of positions and moves, and then searched. Which abstraction step does this reflect?

    • Storing each position as a single number without meaning
    • Representing the problem so that an existing search can solve it
    • Removing all rules from the game
    • Encrypting the moves so that a second player cannot read them during play

13. A problem is decomposed into sub-problems A, B and C, where B is decomposed again into B1 and B2. What is this structure?

    • A hierarchy of sub-problems that can be subdivided further
    • A single flat list of unrelated tasks that all depend on one another
    • A list of random numbers
    • A cycle that never ends

14. To find whether a number is prime, a program checks divisors up to its square root. What principle does this use?

    • Sorting the divisors randomly
    • Encrypting the number
    • Reducing the problem to a smaller test that is sufficient
    • Storing the number as text

15. Which is an example of decomposition in a quiz application?

    • Copying the same screen code into every file
    • Separate parts for scoring, timing and displaying questions
    • A single unstructured block with no named parts
    • One variable holding every value in the program

16. A problem is reduced to a known problem, and the known problem is solved. What must still be checked?

    • Only the speed of the computer
    • That the reduction is valid, so the solution answers the original problem
    • Nothing at all, because reduction guarantees correctness and so no further checks are needed
    • Only the colour of the output

17. Which list of steps reflects decomposition in a sorting program?

    • Read the list, sort it, output the result
    • Output a random list of numbers
    • Sort the list before it exists
    • Output the result before reading the list

18. Reducing a problem to one already solved mainly helps because:

    • It shortens the source code to one line
    • It removes the need for any input
    • The solution to the known problem can be reused with confidence
    • It makes the output always identical

19. Problem reduction and decomposition are both used to:

    • Eliminate the need for algorithms
    • Make a complex problem tractable by breaking it into or matching it to simpler problems
    • Make a simple problem more complex
    • Guarantee the fastest hardware

20. A program to rank players is reduced to sorting their scores. Which sorting property matters most for ties?

    • The number of letters in each name only
    • The colour of each player's avatar
    • The location of the server
    • Whether the chosen sort is stable, if tied players must keep their original order

Related quizzes

• Problem-solving and algorithms Quiz · 4.4.1.1 · 20 questions
• Abstraction Quiz · 4.4.1.3 · 20 questions
• Composition Quiz · 4.4.1.10 · 20 questions
• Automation Quiz · 4.4.1.11 · 20 questions
• Finite state machines Quiz · 4.4.2.1 · 20 questions
• Regular expressions Quiz · 4.4.2.3 · 20 questions
• Backus-Naur Form and syntax diagrams Quiz · 4.4.3.1 · 20 questions
• Comparing algorithms Quiz · 4.4.4.1 · 20 questions
• Order of complexity Quiz · 4.4.4.3 · 20 questions
• Limits of computation and computable problems Quiz · 4.4.4.4 · 20 questions