Cours LUA Project activities

Cours LUA Project activities, tutoriel & guide de travaux pratiques en pdf.

Project activities

There are three main activities for this project (after getting Lua to a workable state in your system). The activities will be graded on the basis of 100 points. The activities are:
1. Write two small utility functions on arrays. One will check that array is sorted. The other will check that two arrays have the same entries.
You can use the rst to check that a sorting routine has in fact delivered sorted result. You can use the second to check that two sorting routines have given the same result when applied to the same argument.
The sortedness checker should use a for loop to inspect each pair of ad-jacent entries. If any is in the wrong order, it should return false.
The array entry equality checker will rst check that its two arguments have the same length. If they do not, it returns false. Otherwise, it uses a for loop to inspect the array values of each array for each index. If the arrays di er for any index, it should return false. It does not have to report the index.
Add your commented code to the le proj1.lua, together with the example arrays that you used to test that your functions gave the right answer. (20 points.)
2. You will count the number of operations that the di erent sort algorithms require, when applied to various arguments. In particular, we will count comparisons between array elements, to determine whether they are out of order.
Insert code into proj1.lua to count how many times comparison operators are applied to array elements. Do not count other uses of <; , etc., just the ones that are applied to values in the arrays being sorted. You may  Write a test procedure that will generate 100 test arrays, of sizes increasing from 50 entries to 5,000 entries. This will take a few minutes to run of most computers. For each array, make a copy of it to sort using insertion sort; another copy to sort using bubble sort, and a copy to sort using merge sort. For each array and sorting algorithm, maintain two arrays. One array should have the elapsed times as entries. The ith entry in the insertion sort timing array should be the time it took to run insertion sort on the ith array. The ith entry in the merge sort count array should be the number of comparisons that merge sort required to sort the ith array. Etc.
You will use this information to answer four questions:
(a) For each algorithm, how stable is the relation between time used and number of comparisons? Do you have a fairly constant ratio of comparisons per unit time?
(b) For each of the three algorithms (bubble sort, insertion sort, and merge sort), how does the number of comparisons increase as the array size increases?
(c) For a particular (large) array size, what are the ratios of the numbers of comparisons that the di erent algorithms perform, as we look at the di erent pairs of the three algorithms?
(d) Are there speci c kinds of inputs for which an algorithm will perform particularly e ciently? For instance, inputs that are already in the right order, or nearly? Inputs that are almost completely wrong, namely the opposite of the right order? Randomly chosen input? For this question, you should also generate some specially designed arrays, and record the statistics for those.
Real world sorting applications often have special kinds of inputs.
Insert into the le your re-de nitions of the sort routines with extra code to do the comparison counting. Make sure that your test procedures call the procedures being tested repeatedly with di erent arrays as the test arguments. The test procedures should maintain arrays that record the numbers of comparisons for these di erent test arguments.
Include these output results, and also your conclusions, as comments in the code.
It’s convenient for this that Lua has \block comments » that look like this:
This is a block comment. You can include your output from the test in this form.
4 –]]
3. Now compare the timings for the three versions, namely the three di erent algorithms. You can get good, accurate timings in Lua using os.clock(). That gives a oating point number that says how many seconds of CPU time Lua has used since being started. You can nd how much work some activity requires using the code:
local start_time = os.clock()
… execute activity here …
local end_time = os.clock()
return end_time-start_time
Report the same kinds of information as for the comparison counting.