Module 5

Question 1

This type of approach divides the problem into subproblems that are smaller instances of the same problem.

Answer 1

Divide and Conquer

Question 2

What are the steps in the Divide and Conquer approach?

Answer 2

• Divide the problems into subproblems
• Conquer by solving the problems recursively
• Combine the solutions to the sub problems into the solution for the original problem.

Question 3

This type of approach is used with 2 or more subproblems.

Answer 3

Divide and Conquer

Question 4

This type of approach is based on exploiting the relationship between a solution to a given instance of a problem and a solution to its smaller instance.

Answer 4

Decrease and Conquer

Question 5

This approach is also known as incremental or inductive approach.

Answer 5

Decrease and Conquer

Question 6

What are the steps in the Decrease and Conquer approach?

Answer 6

• Decrease or reduce problem instance a smaller instance.
• Conquer by solving smaller instance of the problem.
• Extend solution of smaller instance to obtain solution to original problem.

Question 7

What are the two types of implementation of Decrease and Conquer?

Answer 7

Top-down approach and Bottom-up approach

Question 8

The top-down approach to Decrease and Conquer always leads to the __________ implementation of the problem.

Answer 8

Recursive

Question 9

The bottom-up approach to Decrease and Conquer is usually implemented ___________, starting with a solution to the smallest instance of the problem.

Answer 9

Iteratively

Question 10

What are the different variations of Decrease and Conquer?

Answer 10

• Decrease by a constant
• Decrease by a constant factor
• Variable-size-decrease

Question 11

In this variation of Decrease and Conquer, the size of an instance is reduced by the same constant on each iteration of the algorithm.

Answer 11

Decrease by a constant

Question 12

True or False.
In the decrease by a constant variation of Decrease and Conquer, the constant is equal to two, although other constant size reductions do happen occasionally.

Answer 12

False.
(The constant is equal to ONE)

Question 13

In this variation of Decrease and Conquer, suggests reducing a problem instance by the same constant factor on each iteration of the algorithm.

Answer 13

Decrease by a factor

Question 14

True or False.
In most applications of the decrease by a factor technique, the constant factor is equal to two and A reduction by a factor other than two is especially rare.

Answer 14

True

Question 15

In this variation of the Decrease and Conquer approach, the size-reduction pattern varies from one iteration of an algorithm to another.

Answer 15

Variable-size-decrease

Question 16

True or False.
In the variable-size-decrease, the values are reduced by constant and a constant factor.

Answer 16

False
(reduced NEITHER by a constant NOR a constant factor)

Question 17

True or False.
There may be a case that a problem can be solved by decrease-by-constant as well as decrease-by-factor variations, but the implementations can be either recursive or iterative.

Answer 17

True

Question 18

In this type of sorting algorithm, the sorted array is built one item at a time.

Answer 18

Insertion Sort

Question 19

In this type of sorting algorithm, the array elements are compared with each other sequentially and then arranged simultaneously in some particular order.

Answer 19

Insertion Sort

Question 20

What is the worst case time complexity of insertion sort?

Answer 20

[Big-O] O(n^2)

Question 21

What is the best case time complexity of insertion sort?

Answer 21

[Big-omega] O(n)

Question 22

What is the average case time complexity of insertion sort?

Answer 22

[Big-theta] O(n^2)

Question 23

It traverses a graph depthward and uses a stack to get the next vertex when a dead end occurs.

Answer 23

Depth-First Search(DFS)

Question 24

What is the time complexity of DFS?

Answer 24

O(V+E)

Question 25

What is the space complexity of DFS?

Answer 25

O(V)

Question 26

It traverses a graph breadthward and uses a queue to get the next vertex to start a search when a dead end occurs.

Answer 26

Breadth-First Search (BFS)

Question 27

What is the time complexity of BFS?

Answer 27

O(V+E)