Matlab scripting

Scienti c Computing School of Computer Science The University of Adelaide Practical 2 1 Finding the square root of a number Given a number awe wish to nd xsuch that x2 = aapproximately. Here f(x ) = x2 a is the function that we aim to nd its roots. Newton's method (a.k.a. Newton-Raphson method) involves iteratingthe following formula:

x 0 = a=2 (an initial guess for x) (1) x n = ( x n 1 + a=x n 1) = 2; forn= 1 ;2 ;3 ; : : : (2) As ngets larger (i.e. as we perform more iterations) the value of x n approaches the square root of a. (Note that if x n 1 = p a exactly then the application of the formula yields x n = p a as well).

As an example try a= 79. Using the above formulae the rst few values are x 0 = 39 :5000 x 1 = (39 :5 + 79 =39 :5) =2 = 20 :7500 x 2 = (20 :75 + 79 =20 :75) =2 = 12 :2786 x 3 = (12 :2786 + 79 =12 :2786) =2 = 9 :3563 x 4 = (9 :3563 + 79 =9:3563) =2 = 8 :9000 This seems to be approaching the true value of p 79 = 8 :8882. In general we expect the results to quickly approach the true value if the initial guess is close to the true value.

On the other hand if the number of iterations is su ciently large then we also expect the nal value to be very close to the true value.

1.1 Your task Write a MATLAB script squareroot.mthat asks for a positive real number aand desired number of iterations N. The program will then calculate the square root of a using the Newton-Raphson formula with Niterations. You may use the MATLAB function inputto prompt the user to type in a number, e.g.

1 a = input('Please input a positive real number: '); When the above statement is executed MATLAB will prompt the user with the message \ Please input a positive real number: " after which the user can type in a value which will then be stored in the variable aafter the enter key is pressed.

Beginning from the initial guess, your program must print all the intermediate values of the Newton-Raphson formula for all iterations. It should also print the square root value obtained using MATLAB's sqrtfunction and the di erence between this value and the value obtained using Newton-Raphson. A sample output is as follows:

Please input a positive real number: 79 Please input the desired number of iterations: 6 39.500000000000000 20.750000000000000 12.278614457831326 9.356282575413884 8.899903476014160 8.888202119761800 8.888194417318926 MATLAB's value: 8.888194417315589 The difference is: -3.337774501233071e-12 Note that the exponent e-12in the di erence value is appended automatically by disp.

*** Once you are convinced that your program works (try with many other values to verify), you should show your results to the prac supervisor to mark o Section 1. Extension: What happens if you enter a negative value? What should your program do with a negative value?

2 2 Sorting a list of numbers using Selection Sort Imagine that we have a list of numbers which we wish to sort into ascending order. A simple way of doing this (so long as the size Lof the list is not too large) is to use the selection sort method. Consider the following list of L= 4 numbers:

a(1) = 3, a(2) = 5, a(3) = 11, a(4) = 1 We may sort this as follows: First nd the smallest element in the list and then swap it with the rst element. This gives the new list:

a(1) = 1, a(2) = 5, a(3) = 11, a(4) = 3 Now nd the second smallest element and swap it with the second element in the list:

a(1) = 1, a(2) = 3, a(3) = 11, a(4) = 5 Find the third smallest element and swap it with the third element in the list:

a(1) = 1, a(2) = 3, a(3) = 5, a(4) = 11 This is a very simple method which has the advantage that it is easy to program.

2.1 Selection Sort algorithm The above sorting procedure is an instance of the \Selection Sort" algorithm. This algorithm is summarised in the following:

Input: A list ofLnumbers stored in the vector a, e.g. a(1) = 3, a(2) = 5, a(3) = 11 and a(4) = 1.

Steps: For each ifrom 1 to L 1 do the following:

1. Set min index =i.

2. For each jfrom i+ 1 to Ldo the following:

(a) If a(j ) < a (min index ) then set min index =j.

3. Swap the values of a(min index ) and a(i).

Note that to swap two values, you will need to store one temporarily in another variable so that you do not lose one of the values.

3 2.2 Your task:

Write a MATLAB script called selectsort.mthat implements Selection Sort. In par- ticular the program must perform the following:

1. Prompts the user to enter the list of numbers that he/she wishes to sort. This can be accomplished with inputby enclosing the list of numbers with square brackets, e.g. if invoked at the MATLAB prompt >> a = input('Please enter a list of numbers: ') Please enter a list of numbers: [ 3 5 11 1 ] a = [ 3 5 11 1 ] >> 2. Prints the values of the array elements.

3. Sorts the array using Selection Sort and prints the contents of the array after every iteration.

The following is a sample output:

Please enter a list of numbers: [ 3 5 11 1 ] 3 5 11 1 1 5 11 3 1 3 11 5 1 3 5 11 *** Try with di erent inputs to convince yourself that your program works. Show your results to the prac supervisor to mark o Section 2. Extension: We should not use Selection Sort if the size of the list Lis large. Why?

4