Answer To The Question 1: Experimental Purpose: Experimental Process

Answer to the question 1
1. Experimental Purpose: By using the merge sort algorithm on the given algorithm to rank
it in ascending order.
2. Experimental Process: The coding platform was Code Blocks C++.At first, the first line
is an integer N where N is not greater than 10000.
The key to merge Sort is merge. Therefore, it is done in two steps. First, it must split the given
array, and then merge the split sub-arrays.
merge sort employ a common algorithmic paradigm based on recursion. This paradigm, divide-

and-conquer, breaks a problem into sub problems that are similar to the original problem,
recursively solves the sub problems, and finally combines the solutions to the sub problems to
solve the original problem. Because divide-and-conquer solves sub problems recursively, each
sub problem must be smaller than the original problem, and there must be a base case for sub
problems. You should think of a divide-and-conquer algorithm as having three parts:
1) Divide the problem into a number of sub problems that are smaller instances of the same
problem.
2) Conquer the sub problems by solving them recursively. If they are small enough, solve the sub
problems as base cases.
3) Combine the solutions to the sub problems into the solution for the original problem.
3.Experimental Result and Analysis :
1) Separate the array from the middle to obtain two new sub-arrays, and repeat the division
operation on the sub-arrays until the sub-arrays are sufficiently small (array size is 1). Then the
original merge operation.
2) When the two sub-arrays that need to be merged have only one element, compare the sizes
and merge them into a new array.
3) When the two sub-array elements to be merged are greater than 1,
*If the two sub-arrays are left[i] and right[j].
First use the first element of the two arrays to compare the size, for example, left[0] and right[0]
compare the size, if left[0]<=right[0], when *forming a new array, left[0] is The first element of
the new array; right[0] is compared with left[1]. Go on like this
NWPU/ALGORITHM PRACTICAL Page 1

Answer to the question 1
If the elements of left[] are all in the new array, and right[] is not all in *the new array, add the
remaining elements of right[] to the new array in their own order.
4. Repeat the merge operation until the regenerated array is the same size as the array, and
Merge Sort ends.
4. Conclusion : The experiment was concluded successfully .There was no bug found in the
final stage. We obtained our desired merge sort

Answer to the question 2(Dynamic Programming)
1) Experimental Purpose : A common subsequence of two strings is a subsequence that

appears in both strings. A longest common subsequence is a common subsequence of
maximal length. A subsequence of a string S, is a set of characters that appear in left to-right
order, but not necessarily consecutively.
2) Experimental Process: The coding platform was Code Blocks C++.We can see that ,first
and second line of each of the input case contain two strings, which is composed of letters
and numbers, we need to make sure lengths of strings do not exceed 200.
We got two sequences, now the length of longest subsequence present in both of them. A
subsequence is a sequence that appears in the same relative order, but not necessarily
Let the input sequences be X[0..m-1] and Y[0..n-1] of lengths m and n respectively. And let
L(X[0..m-1], Y[0..n-1]) be the length of LCS of the two sequences X and Y. Following is the
recursive definition of L(X[0..m-1], Y[0..n-1]).
If last characters of both sequences match (or X[m-1] == Y[n-1]) then

L(X[0..m-1], Y[0..n-1]) = 1 + L(X[0..m-2], Y[0..n-2])

3.Experimental Result and Analysis: :
#We have two nested loops
*The outer one iterates n times
*The inner one iterates m times
*A constant amount of work is done inside each iteration of the inner loop
*Thus, the total running time is O(nm)
#Answer is contained in L[n,m] (and the subsequence can be recovered from the L table).

Dynamic Programming Technique,
# Applies to a problem that at first seems to require a lot of time (possibly exponential),
provided we have:
*Simple sub problems: the sub problems can be defined in terms of a few variables, such as j,
k, l, m, and so on.
*Sub problem optimality: the global optimum value can be defined in terms of optimal sub
problems
*Sub problem overlap: the sub problems are not independent, but instead they overlap
(hence, should be constructed bottom-up).
4. Conclusion : So we want to solve the longest common subsequence problem by dynamic

programming. To do this, we first need a recursive solution. The dynamic programming idea
doesn't tell us how to find this, it just gives us a way of making the solution more efficient
once we have The experiment was concluded successfully. There was no bug found in the
final stage. We obtained our desired result.

Answer to the question 3(Defense Missile System)
1. Experimental Purpose:
We are going to make new defensive missile that can intercept multiple attacks from
missiles. The missile we are going to make has some short comings. We cannot fly backward
or upward. We need to intercept the maximum number of offensive missiles that can be
intercepted by a defensive missile in each test. We will try to now find an algorithm which
will suit our narrative.

Answer To The Question 1: Experimental Purpose: Experimental Process

Uploaded by

Copyright:

Available Formats

Answer To The Question 1: Experimental Purpose: Experimental Process

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Answer To The Question 1: Experimental Purpose: Experimental Process

Uploaded by

Copyright:

Available Formats

Answer to the question 1

merge sort employ a common algorithmic paradigm based on recursion. This paradigm, divide-

3.Experimental Result and Analysis :

3) When the two sub-array elements to be merged are greater than 1,

*If the two sub-arrays are left[i] and right[j].

NWPU/ALGORITHM PRACTICAL Page 1

NWPU/ALGORITHM PRACTICAL Page 2

1) Experimental Purpose : A common subsequence of two strings is a subsequence that

If last characters of both sequences match (or X[m-1] == Y[n-1]) then

NWPU/ALGORITHM PRACTICAL Page 3

3.Experimental Result and Analysis: :

#We have two nested loops

*The outer one iterates n times

*The inner one iterates m times

*Thus, the total running time is O(nm)

NWPU/ALGORITHM PRACTICAL Page 4

Dynamic Programming Technique,

4. Conclusion : So we want to solve the longest common subsequence problem by dynamic

NWPU/ALGORITHM PRACTICAL Page 5

NWPU/ALGORITHM PRACTICAL Page 6

You might also like