Preview

03 - Use of Divide and Conquer

 1. In computer science, divide and conquer is an algorithm design paradigm based on multi-branched __________

  randomisation

  iteration

  recursion

  factorialisation

 2. Divide and conquer algorithms are said to solve problems by doing which of the following?

  All of the mentioned answers are valid in combination with each other

  breaking the problem into sub problems,that are smaller instances of the big problem

  recursively solving sub problems

  appropriately combining the answers of the sub problems

 3. A divide-and-conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become _____________________

  simple enough to be solved directly

  NULL and void

  an infinite stack or queue data structure

  complex enough to be left to another algorithm to solve

 4. This divide-and-conquer technique is the basis of efficient algorithms for all kinds of problems, including:

  iteration and selection

  A* algorithm and heuristic division

  linear search and iterative search

  quick sort and merge sort

 5. Fill in the blanks for the following excerpt. 
An example of divide and conquer is to sort a given list of n natural numbers, 
split it into two lists of about _________________, sort each of them in turn, 
and interleave both results appropriately to obtain the sorted version of 
the given list

  n x 2 numbers each

  n/2 numbers each

  n + 2 numbers each

  n * 3 numbers each

 6. An important application of divide and conquer is in ____________________.

  recursion

  optimization

  slowing things down

  creating self-creating-algorithms

 7. Divide-and-conquer algorithms naturally tend to make efficient use of memory caches 
The reason is that once a sub-problem is small enough, it and all its 
sub-problems can, in principle, be solved within the cache, without 
accessing the slower main memory.

  TRUE

  FALSE

 8. Divide-and-conquer algorithms can also be implemented by a non-recursive program that stores the partial sub-problems in some explicit data structure, such as a ______________.

  variable or constant

  non-recursive graph

  simple array or non-binary tree

  stack, queue, or priority queue

 9. In _____________ implementations of D&C algorithms, one must make sure that there is sufficient memory allocated for the stack. 
Note: If sufficient memory is not allocated, the execution may fail because of stack overflow

  recursive

  random

  non-recursive

  iterative

 10. Recursion gives us the ability to branch while iterating , known as the ‘divide and conquer’ technique used in algorithms like ____________.

  linear search

  an array search

  quicksort

  the creation of a main menu


Report an error