Data structures and algorithms (comp science)

Coursework Assignment for Semester 2, 2016-17

Due Date: Friday 12th May 2017

An examination of the number of comparisons needed for successful searches of sorted arrays using ten different search algorithms

SID Number: XXXXXXX

Instructions

1. In this assignment, you will analyse some array search algorithms using MATLAB. The first search algorithm (linear search) is analysed for you as an example. There are 10 marks available for each of the remaining search algorithms to be analysed. Test your algorithms before analysing them to ensure that they operate correctly (e.g., using small arrays passed to your functions from the Command Window).

2. Complete the report in exactly the format given here (i.e., fill in the sections and do not change the structure of the document). 10 marks will be awarded for keeping the document in the correct format as you complete the report. In particular, note that code should be pasted directly from MATLAB, in order that a fixed-width font is used, and to ensure that indentation is maintained.

3. Your printed report must be submitted with a CD or USB drive containing your source code (functions for each search algorithm and test harnesses). Work must be submitted to the iCentre by the published deadline. This assignment is worth 50% of your grade for the module.

4. Some initial references are provided, but further research will be needed to learn about the search algorithms that have not been discussed in class. Additional references should be added to the Harvard style reference list to acknowledge the sources consulted. Use reliable sources wherever possible.

5. In the mark scheme (shown below) insert 0s for any algorithms or subsections not completed to determine the maximum possible mark that you can score and to indicate which parts were attempted.

Mark Scheme

Table of Contents

1. Linear Search (Sequential Search)

1.1 Basic logic used by the algorithm

1.2 Published and/or theoretically deduced time complexity

1.3 Presentation of algorithm as a function in MATLAB

1.4 Presentation of successful search test results graphs for increasing array sizes

1.5 Discussion of results

2. Random Search

2.1 Basic logic used by the algorithm

2.2 Published and/or theoretically deduced time complexity

2.3 Presentation of algorithm as a function in MATLAB

2.4 Presentation of successful search test results graphs for increasing array sizes

2.5 Discussion of results

3. Jump Search (Block Search)

3.1 Basic logic used by the algorithm

3.2 Published and/or theoretically deduced time complexity

3.3 Presentation of algorithm as a function in MATLAB

3.4 Presentation of successful search test results graphs for increasing array sizes

3.5 Discussion of results

4. K-level Jump Search

4.1 Basic logic used by the algorithm

4.2 Published and/or theoretically deduced time complexity

4.3 Presentation of algorithm as a function in MATLAB

4.4 Presentation of successful search test results graphs for increasing array sizes

4.5 Discussion of results

5. Exponential Search (Doubling Search, Galloping Search)

5.1 Basic logic used by the algorithm

5.2 Published and/or theoretically deduced time complexity

5.3 Presentation of algorithm as a function in MATLAB

5.4 Presentation of successful search test results graphs for increasing array sizes

5.5 Discussion of results

6. Fibonaccian Search

6.1 Basic logic used by the algorithm

6.2 Published and/or theoretically deduced time complexity

6.3 Presentation of algorithm as a function in MATLAB

6.4 Presentation of successful search test results graphs for increasing array sizes

6.5 Discussion of results

7. Binary Search (Half-interval Search, Logarithmic Search)

7.1 Basic logic used by the algorithm

7.2 Published and/or theoretically deduced time complexity

7.3 Presentation of algorithm as a function in MATLAB

7.4 Presentation of successful search test results graphs for increasing array sizes

7.5 Discussion of results

8. Ternary Search

8.1 Basic logic used by the algorithm

8.2 Published and/or theoretically deduced time complexity

8.3 Presentation of algorithm as a function in MATLAB

8.4 Presentation of successful search test results graphs for increasing array sizes

8.5 Discussion of results

9. Interpolation-Sequential Search

9.1 Basic logic used by the algorithm

9.2 Published and/or theoretically deduced time complexity

9.3 Presentation of algorithm as a function in MATLAB

9.4 Presentation of successful search test results graphs for increasing array sizes

9.5 Discussion of results

10. Interpolation Search (Predictive Search)

10.1 Basic logic used by the algorithm

10.2 Published and/or theoretically deduced time complexity

10.3 Presentation of algorithm as a function in MATLAB

10.4 Presentation of successful search test results graphs for increasing array sizes

10.5 Discussion of results

Appendix A: Test Harness for Deterministic Search Algorithms

Appendix B: Test Harness for Non-deterministic Search Algorithms

List of Figures

Figure 1: Min, average, and max comparisons for linear search for array sizes [0..1024].

Figure 2: Min, average, and max comparisons for random search for array sizes [0..1024].

Figure 3: Min, average, and max comparisons for jump search for array sizes [0..1024].

Figure 4: Min, average, and max comparisons for k-level jump search for array sizes [0..1024].

Figure 5: Min, average, and max comparisons for exponential search for array sizes [0..1024].

Figure 6: Min, average, and max comparisons for Fibonaccian search for array sizes [0..1024].

Figure 7: Min, average, and max comparisons for binary search for array sizes [0..1024].

Figure 8: Min, average, and max comparisons for ternary search for array sizes [0..1024].

Figure 9: Min, average, and max comparisons for interpolation-sequential search for array sizes [0..1024].

Figure 10: Min, average, and max comparisons for interpolation search for array sizes [0..1024].

List of Tables

Table 1: Time complexity summary for linear search.

Table 2: Time complexity summary for random search.

Table 3: Time complexity summary for jump search.

Table 4: Time complexity summary for k-level jump search.

Table 5: Time complexity summary for exponential search.

Table 6: Time complexity summary for Fibonaccian search.

Table 7: Time complexity summary for binary search.

Table 8: Time complexity summary for ternary search.

Table 9: Time complexity summary for interpolation-sequential search.

Table 10: Time complexity summary for interpolation search.

List of Files on Attached Media

linearSearch.m linearSearchTestHarness.m

randomSearch.m randomSearchTestHarness.m

jumpSearch.m jumpSearchTestHarness.m

kLevelJumpSearch.m kLevelJumpSearchTestHarness.m

exponentialSearch.m exponentialSearchTestHarness.m

fibonaccianSearch.m fibonaccianSearchTestHarness.m

binarySearch.m binarySearchTestHarness.m

ternarySearch.m ternarySearchTestHarness.m

interpolationSequentialSearch.m interpolationSequentialSearchTestHarness.m

interpolationSearch.m interpolationSearchTestHarness.m

1. Linear Search (Sequential Search)

1.1 Basic logic used by the algorithm

The linear search algorithm compares a search target to the value in each element [1..N] of an array sequentially, starting from the first element (here, element 1). The search terminates if one of two things happens: 1. the search target is found; 2. the end of the array is reached. In the event that the target is found, the array index in which it was found is returned. In the event that the end of the array is reached and the search target has not been found, a fail token is returned (here, -1).

1.2 Published and/or theoretically deduced time complexity

For successful searches, the best case occurs when the target is found in the first index examined (i.e., index 1, requiring one comparison). The worst case occurs when the search target is found in the final element (at index N, requiring N comparisons). The average case is that the search target is found in the centre of the array, at index 0.5N, taking 0.5N comparisons. These time complexities are summarised in Table 1.

Table 1: Time complexity summary for linear search.

1.3 Presentation of algorithm as a function in MATLAB

function [numComparisons, currentIndex] = linearSearch(V, target)

numComparisons = 0;

for currentIndex=1:length(V)

numComparisons = numComparisons + 1;

if(V(currentIndex) == target)

break;

end

end

if(V(currentIndex)~=target)

currentIndex = -1;

end

end

The MATLAB source code for this algorithm is provided on the attached disk, filename linearSearch.m

1.4 Presentation of successful search test results graphs for increasing array sizes

Results for a successful linear search of array sizes 1..1024 are shown in Fig. 1.

Figure 1: Min (green), average (yellow), and max (red) comparisons for linear search of an array of size [0..1024]. Dotted lines show expected (theoretically deduced) min, average and max.

1.5 Discussion of results

The observed test results (coloured lines) are in good agreement with the published (expected) time complexities for a linear search (dotted lines). The best case (minimum number of comparisons required) was always one (green line), irrespective of array length. The worst case (maximum number of comparisons required) was always equal to the array length (red line), occurring when the search target was found in the final element. The average case was 0.5N, representing the average of all possible outcomes (yellow line), which is that the search target is found in the centre of the array. The average and worst cases therefore grew linearly as the size of the array increased as functions y = x/2 and y = x, respectively (i.e., as arithmetic progressions). If the array size were doubled, the best case would remain constant (at 1), and the average and worst cases would also double.

References

Shneiderman, B. (1978). Jump Searching: A Fast Sequential Search Technique, Communications of the ACM, 21(10), 831-834. [Jump Search].

Bentley, J. L. and Yao, A. C. (1976). An almost optimal algorithm for unbounded searching. Information Processing Letters, 5(3), 82–87. [Exponential Search].

Ferguson, D. E. (1960). Fibonaccian searching. Communications of the ACM, 3(12), 648. [Fibonaccian Search].

Perl, Y., Itai, A., & Avni, H. (1978). Interpolation search — a log log N search. Communications of the ACM, 21(7), 550-553. [Interpolation Search].

Appendix A: Test Harness for Deterministic Search Algorithms

Array sizes from 1..maxArraySize are tested, where maxArraySize = 1024. The current array size being tested is held in variable N. The sequence [1..N] is placed in the current array. Values [1..N] are used as search targets, one at a time. Best (minimum), average (arithmetic mean) and worst (maximum) number of comparisons performed for each array size are collected. A graph of N against comparisons is displayed, with three lines (minimum, average and maximum). Expected performance is also plotted (dotted lines).

clear all;close all;clc;

maxArraySize = 1024;

for N = 1:maxArraySize

array = 1:N;

for searchTarget = 1:N

comparisons(searchTarget) = linearSearch(array, searchTarget);

end

min_comps(N) = min(comparisons);

avg_comps(N) = mean(comparisons);

max_comps(N) = max(comparisons);

clear comparisons;

end

figure;

% Plot Observed

plot([1:maxArraySize], min_comps,'g','LineWidth',3);hold on;

plot([1:maxArraySize], avg_comps,'y','LineWidth',3);

plot([1:maxArraySize], max_comps,'r','LineWidth',3);

legend('min','mean','max');

% Plot Expected

plot([1:maxArraySize], linspace(1,1,maxArraySize), 'k:');

plot([1:maxArraySize], linspace(1,N/2,maxArraySize), 'k:');

plot([1:maxArraySize], linspace(1,N,maxArraySize), 'k:');

% Annotate Chart

xlabel('Array Size (N)','FontSize',14);

ylabel('Comparisons', 'FontSize', 14);

title('Linear Search (Successful)','FontSize', 14);

xlim([0 maxArraySize]);

ylim([0 max(max_comps)]);

modify as required

print -f1 -r300 -dbmp linearSearchSuccessful.bmp

2