# 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