Preview

03 - Use of Divide and Conquer

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

  iteration

  factorialisation

  randomisation

  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

  appropriately combining the answers of the sub problems

  recursively solving sub problems

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

 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:

  quick sort and merge sort

  A* algorithm and heuristic division

  iteration and selection

  linear search and iterative search

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

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

  simple array or non-binary tree

  variable or constant

  non-recursive graph

  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

  random

  non-recursive

  recursive

  iterative

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

  quicksort

  an array search

  linear search

  the creation of a main menu


Report an error