Question 1 Modify Mergesort and Quicksort to automatically a

Question 1: Modify Mergesort and Quicksort to automatically assign starting and ending number for each recursion call.

Question 2: Use the explorer procedure to explore the following graph starting from node 2. Please show the problem solving procedure (recursive) in details and show the stack status at each step.

23 4 5

Solution

Question 1: Modify Mergesort and Quicksort to automatically assign starting and ending number for each recursion call.

ANSWER:

Merge sort Explanation:

Merge Sort follows the principle called as Divide and conquer method.The full problem is to sort a subarray.In particular we will think of a subproblem as a sorting the subarray starting at index p and going throughindex r.

How merge sort uses Divide and conquer method :

1.Divide by finding the number q of the position mid way between p and r.Do this step the same way to found the mid point in binary search :p and r,divided by 2 and round down

2.Conquer by recursively sorting the subarrays in each of the two sub problems

3.Combine by merging the two sorted subarrays back ito the single sorted sub arrray[p..r]

Merge Sort(a1)

1 if length[A] ==1

2 return a1

3 else

4 q <- [length[a1]/2]

5 create arrays L[1..q] and R[q+1..length[a1]]

6 copy a1[1..q] to L

7 copy A[]q+1.length[a1] to R

8 LS <- MergeSort(L)

9 RS <- MergeSort(R)

10 return Merge(LS,RS)

Quick sort Explanation:

Principle of the quick sort algorithm as follows:

1) pick a pivot element

2)Partition the array into 3 parts.

3) First part:All elements in this part is less than the pivot.

4) second part : The pivot itself (only one element)

5) Third part :All elements in this part is greater than or equal to the pivot.

Quicksort(A)

{

empty array:less,equal,greater;

if length(A) <=1 return A;

for each x in A

{

if x pivot then append x to less;

else if x> pivot then append x to greater;

else append x to equal;

}

return concatenate(Quicksort(less),equal,Quicksort(greater))

}

Question 2: Use the explorer procedure to explore the following graph starting from node 2. Please show the problem solving procedure (recursive) in details and show the stack status at each step.

Answer :

Here i explain with the principle of Depth-first search(DFS) is an algorithm that traverses a graph in search of one or more goal nodes. The defining characteristic of this search is that,When ever DFS visits a maze sell c,it recursively searches the sub-maze whose origin is c. This recursive behaviour can be simulated by an iterative algorithm using a stack.

DFS algorithm:

Depth first search (Maze m)

Depth first search ( m.StartCell)

end procedure

Depth first search ( (MazeCell c)

if c is the goal

Exit

Mark c \"visit in progress\"

foreach neighbour no of c

if n \"unvisited\"

Depth first search (n)

Mark c \"visited\"

End procedure.

Stack status of each step for the following graph:

These are the step by step stack procedures for the following graph:

Action Stack Visited

1)push 2 [2] {}

2)pop and visit 2 [] {2}

3)push 3,5,1 [3,5,1] {2}

3)pop and visit 1 [3,5] {2,1}

3)push 2 [3,5,2] {2,1}

4)pop 2 (visited ) [3,5] {2,1}

5)pop and visit 5 [3] {2,1,5}

6)push 2,4 [3,2,4] {2,1,5}

7)pop and visit 4 [3,2] {2,1,5,4}

6)push 3,5 [3,2,3,5] {2,1,5,4}

7)pop 5(visited) [3,2,3 ] {2,1,5,4}

8)pop and visit 3 [3,2] {2,1,5,4,3}

9)push 2,4 [3,2,2,4] {2,1,5,4,3}

10)pop 4(visited) [3,2,2] {2,1,5,4,3}

11)pop 2(visited) [3,2] {2,1,5,4,3}

12)pop 2(visited) [3] {2,1,5,4,3}

13)pop 3(visited) [] {2,1,5,4,3}