Preview

03 - Use of Divide and Conquer

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

  factorialisation

  randomisation

  iteration

  recursion

 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

  complex enough to be left to another algorithm to solve

  NULL and void

  an infinite stack or queue data structure

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

  linear search and iterative search

  A* algorithm and heuristic division

  iteration and selection

  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 x 2 numbers each

  n + 2 numbers each

  n/2 numbers each

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

  optimization

  slowing things down

  recursion

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

  non-recursive graph

  variable or constant

  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

  non-recursive

  random

  iterative

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

  the creation of a main menu

  quicksort

  an array search

  linear search


Report an error