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

  factorialisation

  recursion

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

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

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

  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 _____________________

  NULL and void

  complex enough to be left to another algorithm to solve

  an infinite stack or queue data structure

  simple enough to be solved directly

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

  linear search and iterative search

  iteration and selection

  A* algorithm and heuristic division

  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 * 3 numbers each

  n + 2 numbers each

  n/2 numbers each

  n x 2 numbers each

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

  recursion

  slowing things down

  optimization

  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.

  FALSE

  TRUE

 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 ______________.

  stack, queue, or priority queue

  simple array or non-binary tree

  variable or constant

  non-recursive graph

 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

  iterative

  recursive

  non-recursive

  random

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

  an array search

  the creation of a main menu

  linear search

  quicksort