Module 5 Flashcards

1
Q

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

A

Divide and Conquer

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the steps in the Divide and Conquer approach?

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

Divide and Conquer

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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.

A

Decrease and Conquer

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

This approach is also known as incremental or inductive approach.

A

Decrease and Conquer

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What are the steps in the Decrease and Conquer approach?

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

Top-down approach and Bottom-up approach

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A

Recursive

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

Iteratively

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What are the different variations of Decrease and Conquer?

A
  • Decrease by a constant
  • Decrease by a constant factor
  • Variable-size-decrease
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

Decrease by a constant

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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.

A

False.
(The constant is equal to ONE)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

Decrease by a factor

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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.

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A

Variable-size-decrease

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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

A

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

17
Q

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.

A

True

18
Q

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

A

Insertion Sort

19
Q

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

A

Insertion Sort

20
Q

What is the worst case time complexity of insertion sort?

A

[Big-O] O(n^2)

21
Q

What is the best case time complexity of insertion sort?

A

[Big-omega] O(n)

22
Q

What is the average case time complexity of insertion sort?

A

[Big-theta] O(n^2)

23
Q

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

A

Depth-First Search(DFS)

24
Q

What is the time complexity of DFS?

A

O(V+E)

25
Q

What is the space complexity of DFS?

A

O(V)

26
Q

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

A

Breadth-First Search (BFS)

27
Q

What is the time complexity of BFS?

A

O(V+E)