ENGG1811 Lab 10: While and Algorithms

Objectives

After completing this lab, students should be able to

Assessment

This lab has four parts: Parts A to D. 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 on for-loop and is best done after Part B where you will be writing a for loop.

Organising your work

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

Part A: 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:

load  lab10NumberLists

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. Similarly, if you know that numberListShort(37) is 489 and numberListShort(67) is 875, you can further confirm that you program is correct. You will need this program in Parts B and D.

Part B: Testing your simple scan program exhaustively 

In Part A, you have written a program to do a simple scan and you have tested it with a few cases. In this part, you will write a Matlab script to test your program findNumberBySimpleScan exhaustively.

Consider the following questions:

  1. If your function findNumberBySimpleScan works correctly, what number should the function return in the following line of Matlab code? Answer is here if you need to check.
  2. If your function findNumberBySimpleScan works correctly, what number should the function return in the following line of Matlab code? Answer is here if you need to check.
  3. If your function findNumberBySimpleScan works correctly, what number should the function return in the following line of Matlab code? Answer is here if you need to check.
Hopefully you have spotted the pattern and understand why findNumberBySimpleScan(numberListShort,  numberListShort(k) ) should return the expected answer. In this Part, you are asked to write a Matlab script that does the following:
Remark: Software testing is an important part of software development. This exercise gives you an opportunity to learn how to use to use a program to test another program.

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

We consider the same problem as Part A 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 = 0; index2 = length of the vector list
  3. Compute indexMid = Rounding up of (index1 + index2)/2  
  4. Check whether list(indexMid) and target are equal. If no, do the following update and the return to Step 3.
  5. Return the answer indexMid.

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. For checking your program, you can of course adapt the test program that you have written in Part B for this part.

Question: You may ask why we initialise index1 to 0 rather than 1, after all, you cannot use zero to index an element in a Matlab vector. First you need to know that the variable indexMid should be able to take on any value from 1 to the length of list inclusively. If  index1 is initialised to 1, the variable indexMid will never take on a value that it is allowed to take on. The hint is to think about Step 3 where we are rounding up a number. The answer is here is you want.

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 A
  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.