## Description

## EL 9343 Homework 3

1. Given the array A[19, 5 , 9, 52, 26, 35, 61, 28]

a) Using Figure 2.2 on page 18 of CLRS as a model, illustrate the operation of insertion-sort on A.

b) Using Figure 2.4 on page 35 of CLRS as a model, illustrate the operation of merge-sort on A.

2. Consider sorting n numbers stored in array A by first finding the smallest element of A and exchanging

it with the element in A[1]. Then find the second smallest element of A, and exchange it with A[2].

Continue in this manner for the first n−1 elements of A.

a) Write pseudocode for this algorithm, which is known as selection sort.

b) What loop invariant does this algorithm maintain?

c) Why does it need to run for only the first n−1 elements, rather than for all n elements?

d) Give the best-case and worst-case running times of selection sort in Θ-notation.

3. For the maximum subarray problem, if we use divide-conquer, but instead of dividing the array into two

halves, we equally divide it into three segments, how should the algorithm be modified?

What is the

running time of the new algorithm?

Note: Pseudocode is not necessary. You can explain your algorithm and running time step by step.

The Tower of Hanoi is a mathematical game or puzzle consisting of three rods and a number of disks of

various diameters, which can slide onto any rod.

The puzzle begins with n disks stacked on a start rod

in order of decreasing size, the smallest at the top, thus approximating a conical shape.

The objective of

the puzzle is to move the entire stack to the end rod, obeying the following rules:

1. Only one disk may be moved at a time.

2. Each move consists of taking the top disk from one of the rods and placing it on top of another rod or on

an empty rod.

3. No disk may be placed on top of a disk that is smaller than it.

To print each move of this game with the minimum number of steps, please fill in the pseudo code in the

MOVE function.

For example, ideal output format should be like this：

>>> MOVE(3, 1, 3)

Move the top disk from rod 1 to rod 3

Move the top disk from rod 1 to rod 2

Move the top disk from rod 3 to rod 2

Move the top disk from rod 1 to rod 3

Move the top disk from rod 2 to rod 1

Move the top disk from rod 2 to rod 3

Move the top disk from rod 1 to rod 3

**Your Answer:**

PRINT(origin, destination):

print(“Move the top disk from rod”, origin, “to rod”, destination)

MOVE(n, start, end):

your code

your code

your code

…

Hint: You can try Divide and Conquer or Recursion. You can use the following code form as inspiration.

MOVE(n, start, end):

_________

if n == 1:

_________

else:

MOVE(___,___,___)

MOVE(___,___,___)

MOVE(___,___,___)

5. For an array with n elements, design a divide-and-conquer algorithm for finding both the minimum and

the maximum element of this array using no more than 3n/2 comparisons. (Pseudocode is required)