CS401A's Finals: Design & Analysis of Algrthms. Module 05

Question 1

Definition of || What is the

• It is a general algorithm design technique that solves a problem by dividing it into several smaller subproblems of the same type, solving each of them recursively, and then combining their solutions to get a solution to the original problem.

Answer 1

Divide and Conquer Algorithm || Design Technique?

Question 2

Definition of || What is the

• The figure below illustrates an example of a \_\_\_\_\_\_ \_\_\_ \_\_\_\_\_\_\_ \_\_\_\_\_\_\_\_\_ in a typical case:

(A problem of size n)
v > (Subproblm 1 of size n/2)
    v > [solution subproblm 1]
v > (Subprblm 2 size n/2)   v
    v > [soln subprblm 2] > v
                            v
[solution to original problem]

Answer 2

Divide and Conquer Algorithm || Design Technique?

Divide and Conquer algorithm

Question 3

Definition of Divide and Conquer Algorithm

Importance of Divide and Conquer Algorithm Design Technique

Answer 3

• Solving difficult problems
• Algorithm efficiency
• Parallelism
• Memory Access

Question 4

Application of

is a type of sorting algorithm that repeatedly divides the data in half, sorts each half separately, and combines the sorted halves into one sorted array.

Answer 4

Divide and Conquer Algorithm Design Technique

Merge Sort

Question 5

Application of

Example:
Initial Hand:

 0 1 2 3 4  5 6 
[2|Q|J|7|A|10|5]

1st Split:

Answer 5

Divide and Conquer Algorithm Design Technique

Merge Sort

1st Split:

 0 1 2 3   4  5 6 
[2|Q|J|7] [A|10|5]

Question 6

Application of

Example:
Initial Hand:

 0 1 2 3 4  5 6 
[2|Q|J|7|A|10|5]

2nd Split:

Answer 6

Divide and Conquer Algorithm Design Technique

Merge Sort

2nd Split:

 0 1   2 3   4  5 6 
[2|Q] [J|7] [A|10|5]

Question 7

Application of

Example:
Initial Hand:

 0 1 2 3 4  5 6 
[2|Q|J|7|A|10|5]

3rd Split:

Answer 7

Divide and Conquer Algorithm Design Technique

Merge Sort

3rt Split:

 0 1   2 3   4  5   6 
[2|Q] [J|7] [A|10] [5]

 0   1   2   3   4    5   6 
[2] [Q] [J] [7] [A] [10] [5]

Question 8

Application of

Example:
Initial Hand:
3rd Split:

 0   1   2   3   4    5   6 
[2] [Q] [J] [7] [A] [10] [5]

1st to 3rd Merge:

Answer 8

Divide and Conquer Algorithm Design Technique

Merge Sort

1st to 3rd Merge:

[2] [Q] [J] [7] [10|A] [5]

[2|7|J|Q] [5|10|A]

[2|5|7|10|J|Q|A]

Question 9

Application of

is a type of sorting algorithm in which the main idea is to partition the array into two (2) regions: small items are moved to the left side of the array and large items are moved to the right side. After partitioning, the sort is repeated on the left and right sides.

Answer 9

Divide and Conquer Algorithm Design Technique

Quick Sort

Question 10

Application of

is a type of search algorithm that is used to locate an element in an ordered array. It is advisable to use it whenever the list starts to become larger.

Answer 10

Divide and Conquer Algorithm Design Technique

Binary search

Question 11

Application of

The steps of the Binary search starts by

testing the target.

If the target is equal to the middle item,

quit.

Otherwise:

Answer 11

Divide and Conquer Algorithm Design Technique

The steps of the \_\_\_\_\_\_ \_\_\_\_\_\_ starts by

If the target is equal to the middle item,

Otherwise:
1. Divide the array into two sub-arrays about half as large. If the target is smaller than the middle item, choose the left sub-array. If the target is larger than the middle item, choose the right sub-array.
2. Divide (Solve) the sub-array by determining whether the target is in that sub-array. Unless the sub-array is sufficiently small, use recursion to do this.
3. Obtain the solution to the array from the solution to the sub-array.

Question 12

Application of

The steps of the Binary search starts by testing the target. If the target is equal to the middle item, quit. Otherwise:
1. Divide the array into two sub-arrays about half as large. If the target is smaller than the middle item,

If the target is larger than the middle item,

Answer 12

Divide and Conquer Algorithm Design Technique

1. Divide the array into two sub-arrays about half as large. If the target is \_\_\_\_\_\_\_ \_\_\_\_ \_\_\_ \_\_\_\_\_\_ \_\_\_\_,

choose the left sub-array.

If the target is \_\_\_\_\_\_ \_\_\_\_ \_\_\_ \_\_\_\_\_\_ \_\_\_\_,

choose the right sub-array.

Question 13

Application of

The steps of the Binary search starts by testing the target. If the target is equal to the middle item, quit. Otherwise:
2. Divide (Solve) the sub-array by determining whether the target is in that sub-array. Unless the sub-array is sufficiently small,

Answer 13

Divide and Conquer Algorithm Design Technique

use recursion to do this.

Question 14

Application of

The steps of the Binary search starts by testing the target. If the target is equal to the middle item, quit. Otherwise:
3. Obtain the solution to the array from the

Answer 14

Divide and Conquer Algorithm Design Technique

solution to the sub-array.

Question 15

Application of

is a type of tree data structure in which no node can have more than two (2) subtrees. In other words, a node can have zero, one, or two subtrees. These subtrees are designated as the left subtree and right subtree.

Answer 15

Divide and Conquer Algorithm Design Technique

Binary Tree

Question 16

Application of

requires that each node of the tree be processes once and only once in a predetermined sequence.

Answer 16

Divide and Conquer Algorithm Design Technique

Binary tree traversal

Question 17

Application of

The \_\_\_ (_) general approaches to the traversal sequence are as follows:

Answer 17

Divide and Conquer Algorithm Design Technique

two (2)
* Depth-first traversal
* Breadth-first traversal

Question 18

Application of

The
general approaches to the traversal sequence are as follows:

is where the processing proceeds along a path from the root through one child to the most distant descendent of the first child before processing a second child.

Answer 18

Divide and Conquer Algorithm Design Technique

• Depth-first traversal

Question 19

Application of

The
general approaches to the traversal sequence are as follows:

In other words, in the \_\_\_\_\_\_\_\_\_\_\_ search \_\_\_\_\_\_\_\_\_, all of the descendants of a child are processed before going on to the next child.

Answer 19

Divide and Conquer Algorithm Design Technique

depth-first search traversal

Question 20

Application of

\_\_\_\_\_ (_) types of depth-first search binary tree traversal

Answer 20

Divide and Conquer Algorithm Design Technique

Three (3)
preorder traversal
inorder traversal
postorder traversal

Question 21

Application of

types of depth-first search binary tree traversal

the root is visited first and successively moving to the left subtree until a leaf is reached, visiting each node on the way there.

Answer 21

Divide and Conquer Algorithm Design Technique

In the preorder traversal,

Question 22

Application of

types of depth-first search binary tree traversal

Once there are no more children on the left of a node, the children on the right subtree are visited.

Answer 22

Divide and Conquer Algorithm Design Technique

In the preorder traversal,

Question 23

Application of

types of depth-first search binary tree traversal

the left node is visited first, and subsequently visits the parent of that node.

Answer 23

Divide and Conquer Algorithm Design Technique

In the inorder traversal,

Question 24

Application of

types of depth-first search binary tree traversal

It then goes to the child on the right and finds the leftmost node in the tree to visit.

Answer 24

Divide and Conquer Algorithm Design Technique

In the inorder traversal,

Question 25

# **Application of** types of depth-first search binary tree traversal the leftmost leaf in the tree is visisted first, then going up to the parent and down the second leftmost leaf in the same branch, and so on until the parent is the last node to be visited within a branch.

Answer 25

**Divide and Conquer Algorithm Design Technique** In the ***postorder traversal***,

Question 26

# **Application of** The general approaches to the traversal sequence are as follows: is where the processing proceeds horizontally from the root to all of its children, then to its children's children, and so forth until all nodes have been processed.

Answer 26

**Divide and Conquer Algorithm Design Technique** * *Breadth-first traversal*

Question 27

# **Application of** The general approaches to the traversal sequence are as follows: In other words, in the `_____________ _________`, each level is completely processed before the next level is started.

Answer 27

**Divide and Conquer Algorithm Design Technique** breadth-first traversal