## ENGG1811 Lab 10: While and Algorithms

### Objectives

After completing this lab, students should be able to

• Use while in Matlab
• Write a linear scan and a binary search algorithm
• Understand the efficiency aspect of algorithms

### Assessment

This lab has four parts: Parts A to D. Parts A, B and C are independent. Part D requires the functions written in Part B and Part C. You need to show your tutors at least Parts A, B and C. Complete Part D if you can, otherwise do it in your own time; it shows you how to use a for-loop within a for-loop (or a nested for-loop) to fill in the elements of a matrix. All scripts and functions should be reasonably documented.

The on-line assessment is about Matlab built-in function min, and can be done at any time.

You should make a directory called lab10 to store your files for this lab.

### Part A: Terminating a simulation correctly

We went through an example of simulating the height and velocity of a parachutist in the lecture in Week 8. We did the simulation in a function but given that you are going to modify the simulation, it is easier for you to debug the program if we put all the code on a script. To start with, download the script file parachutistSimulation_prelim.m (which contains the simulation code) and the function file getDragCoeff.m (which returns the drag coefficient at a given time instance). Run the script parachutistSimulation_prelim and it will return a plot of the speed and height of the parachutist. There are three Matlab vectors that we are particularly interested in: vecTime (which contains the time instances in the simulation), and vecHeight and vecSpeed (which contains the height and speed of the parachutist at the corresponding time instances in the vector vecTime).

Let us assume that the ground level is zero. You can see from the figure that the simulation is running longer than it should be because at final simulation time of 100, the parachutist has a negative height. If you look at values of vecHeight(188) and vecHeight(189), you will find that vecHeight(188) is positive while vecHeight(189) is negative. For the given parameter setting, the correct simulation outputs, at the end of the simulation, should be:
1. The vectors vecHeight, vecSpeed and vecTime should each have 189 elements. The first 188 elements in these vectors should be the same as before.
2. The last element of vecHeight should be 0. The last element of vecSpeed should be 0.
3. The last element of vecTime should be the time at which the parachutist touches the ground. You should be able to compute this time from vecTime(188), vecHeight(188) and vecSpeed(188).
In order to realise this, you are asked to do the following:
1. Copy the file parachutistSimulation_prelim.m to parachutistSimulation.m
2. Go through the program and locate the text "BEGIN - All modifications should be below here" and  "END - All modifications should be above here". This is the part of the file that you need to modify. Do not change the other parts. Specifically, the vectors vecTime, vecSpeed and vecHeight should still be initialized to have 401 elements. You will use your program to determine when the simulation should end and reduce the length of these vectors to their appropriate length later on. (Note that it is a good practice to initialize matrices in Matlab before computation, e.g. by using zeros(n,m) where n and m are the number of rows and columns that you want. This allows Matlab to allocate memory space to store the matrices. It is a poor practice to extend the size of the matrices on the go. It can have a detrimental effect on computation performance, especially when you are dealing with large problems. If you don't know how many elements you need, you can do an over-estimation and reduce the size of the matrix later on. This is what we are doing here.)
3. Change the for-loop to a while-loop so that the simulation stops at the right place. If the program gets into infinite loop, typing control-C at the keyboard will terminate the execution.
4. Modify the elements in vecHeight, vecSpeed and vecTime that correspond to the time instance that the parachutist touches the ground.
5. Reduce the length of the vectors vecHeight, vecSpeed and vecTime so that they contain only valid simulation outputs. For example, if you want to retain the first 200 elements of the vector x and discard the rest, you can do: x(201:end) = [ ].

Note that you know the magic numbers 188 and 189, but they hold only for this problem. You code must not contain these magic numbers and should work for the general scenario.

### Part B: Using simple scan (or linear scan) to locate a number in a sorted list of numbers

You are given a vector which contains numbers sorted in ascending order and also a number that can be found in the given vector. You want to find out where the number is located in the given vector. Note that we assume the numbers in the vector are unique so there is only one answer to this problem. We discussed this problem in Week 9's lecture using names sorted in alphabetical order rather than numbers sorted in ascending order, but the two problems are identical.

To give you an example, the matlab mat file lab10NumberLists.mat contains two such vectors. You need to load the file into Matlab first by using:

The vector numberListShort contains 100 numbers. The number 331 is a number from the vector and you want to find out where this number is located in the vector. We call the number that you want to locate the target.

A method is to scan through the numbers in the vector one by one. You first check whether numberListShort(1) is the target. If not, you then check whether numberListShort(2) and so on until you find the target.

You are asked to write a Matlab function that implements this simple scan. The function should have the declaration:

function position = findNumberBySimpleScan(list,target)

The function accepts two inputs: list is the vector of numbers and target is the number in the list that you want to locate. The output position is the index where the number target is located in the vector list. If you call the function

index = findNumberBySimpleScan(numberListShort,331)

then it should return index = 20. You can check that numberListShort(20) is indeed 331.

You should be able to derive your own tests to check that your program is working. Otherwise, we tell you numberListShort(37) is 489 and numberListShort(67) is 875. You will need this program in Part D.

### Part C: Use binary search to locate a number in a sorted list of numbers

We consider the same problem as Part B but we want to use binary search to locate the target. The key idea is to narrow down the possibilities as quickly as possible by eliminating half of the possibilities for each check. We discuss this method in the lecture but we were using sorted names instead of numbers arranged in ascending order, however the principles are the same.

For example, we want to locate the number 473 in the vector numberListShort. This vector has 100 elements. We check the element in the middle of the vector which is numberListShort(50) = 670. Given the numbers are arranged in the ascending order and the target is 473, it means that the target must be located in numberListShort(1:50). We can therefore ignore the other numbers and focus the search in numberListShort(1:50). We repeat the process by looking at the element in the middle of the vector numberListShort(1:50), which is numberListShort(25). The value of numberListShort(25) is 365. This means that the target 473 is located in the vector numberListShort(25:50). We repeat this procedure until we find the target 473.

The pseudo-code is:

1. Given: a vector list which contains numbers sorted in ascending order; target is a number in the vector list. The algorithm returns the index of the number target in the vector list.
2. Initialization: index1 = 1; index2 = length of the vector list
3. Compute indexMid = Rounding up/down of (index1 + index2)/2   (Note: You can choose to round up or down)
4. Check whether list(indexMid) and target are equal. If no, do the following update and the return to Step 3.

In Step 4 of the pseudo-code, one of the ??? is index1 and the other is index2, we will let you figure that out. Although the pseudo-code does not explicitly mention any loops, you indeed require a loop in your program.

Write a Matlab function findNumberByBinarySearch with the declaration

position = findNumberByBinarySearch(list,target)

As a hint, we have completed part of the code for you in findNumberByBinarySearch_prelim.m. Check your program is working and you will use it in Part D.

### Part D: Comparing the run time of three methods

In this Part, you will compare the run time (i.e. how long it takes a program to complete the tasks) of three methods to locate a number in a sorted list of numbers. The three methods are:
1. Simple scan that you wrote in Part B
2. Binary search that you wrote in Part C
3. The Matlab built-in function find

Another goal of our investigation is to understand how the average computation time increases within the size of the problem, which in this case, is measured by the length of the vector that contains the numbers.

We have written a Matlab script to perform this comparison. The code is almost finished and can be found in testComputationTime.m. The script uses a vector called numberList which contains ten thousand (100,000) numbers. The script carries out 3 rounds of tests. Rounds 1, 2 and 3 use, respectively, a vector with one thousand, ten thousand and hundred thousand numbers. In each round, it carries out 20 tests by picking twenty numbers at random from the vector. For each test, it runs the 3 functions to locate the number. We use the Matlab built-in functions clock and etime to find out how long each function takes to locate the given number for each test at each round. The amount of time needed by 3 methods are stored in three matrices timeRequiredSimpleScan, timeRequiredBinarySearch and timeRequiredFind. Each matrix has 10 rows and 3 columns. The (i,j) element in the matrix is the computation time for the method in test i and round j.

You may want to note that the script uses a for-loop within a for-loop to fill in the elements of the matrices. This is known as a nested for-loop. One for-loop is used to iterate on the rounds (columns) and the other on the tests (rows).

Given the computation times in timeRequiredSimpleScan, timeRequiredBinarySearch and timeRequiredFind, we want to find the average time required for each round (which uses a vector of a different length in each round) for each method. Your task is to compute these average computation times. You should do this at the place indicated by the script and store the results in meanTimeRequiredSimpleScan, meanTimeRequiredBinarySearch and meanTimeRequiredFind. Each of these should be a vector with 3 elements containing the average computation time per vector length. You can do this by using the Matlab built-in function mean. You can look up the Matlab help pages to see how to use this function.

Run the script after you have completed the script. It plots a graph with the lengths of the vector in the x-axis and average computation time for each length in the y-axis. There is a chance that you may see a graph that is abnormal or somewhat unexpected. If this is the case, this page explains why.

What conclusions can you draw? You may want to read the discussion here after you have drawn your conclusions.