1
Data Structures & Algorithms [MOD002641]
Coursework Assignment for Semester 2, 2016-17
Due Date: Friday 12
th
May 2017
An examination of the number of comparisons needed for successful searches of
sorted arrays using ten different search algorithms
SID Number: XXXXXXX
Department of Computing & Technology
Faculty of Science & Technology
Anglia Ruskin University
East Road
Cambridge CB1 1PT
United Kingdom
2
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
Algorithm
Subsection
1
Subsection
2
Subsection
3
Subsection
4
Subsection
5
Marks
1. Linear N/A N/A N/A N/A N/A N/A
2. Random 0..2 0..2 0..2 0..2 0..2 0..10
3. Jump 0..2 0..2 0..2 0..2 0..2 0..10
4. K-level Jump 0..2 0..2 0..2 0..2 0..2 0..10
5. Exponential 0..2 0..2 0..2 0..2 0..2 0..10
6. Fibonaccian 0..2 0..2 0..2 0..2 0..2 0..10
7. Binary 0..2 0..2 0..2 0..2 0..2 0..10
8. Ternary 0..2 0..2 0..2 0..2 0..2 0..10
9. InterpolationSequential
0..2 0..2 0..2 0..2 0..2 0..10
10. Interpolation 0..2 0..2 0..2 0..2 0..2 0..10
Presentation 0..10
Total Marks 0..100
3
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
4
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
5
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
6
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.
Best Case Average Case Worst Case
Linear Search (Successful) O(1) O(n) O(n)
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
7
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.
8
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].
9
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)]);
print -f1 -r300 -dbmp linearSearchSuccessful.bmp
modify as
required
Our Service Charter
-
Excellent Quality / 100% Plagiarism-Free
We employ a number of measures to ensure top quality essays. The papers go through a system of quality control prior to delivery. We run plagiarism checks on each paper to ensure that they will be 100% plagiarism-free. So, only clean copies hit customers’ emails. We also never resell the papers completed by our writers. So, once it is checked using a plagiarism checker, the paper will be unique. Speaking of the academic writing standards, we will stick to the assignment brief given by the customer and assign the perfect writer. By saying “the perfect writer” we mean the one having an academic degree in the customer’s study field and positive feedback from other customers. -
Free Revisions
We keep the quality bar of all papers high. But in case you need some extra brilliance to the paper, here’s what to do. First of all, you can choose a top writer. It means that we will assign an expert with a degree in your subject. And secondly, you can rely on our editing services. Our editors will revise your papers, checking whether or not they comply with high standards of academic writing. In addition, editing entails adjusting content if it’s off the topic, adding more sources, refining the language style, and making sure the referencing style is followed. -
Confidentiality / 100% No Disclosure
We make sure that clients’ personal data remains confidential and is not exploited for any purposes beyond those related to our services. We only ask you to provide us with the information that is required to produce the paper according to your writing needs. Please note that the payment info is protected as well. Feel free to refer to the support team for more information about our payment methods. The fact that you used our service is kept secret due to the advanced security standards. So, you can be sure that no one will find out that you got a paper from our writing service. -
Money Back Guarantee
If the writer doesn’t address all the questions on your assignment brief or the delivered paper appears to be off the topic, you can ask for a refund. Or, if it is applicable, you can opt in for free revision within 14-30 days, depending on your paper’s length. The revision or refund request should be sent within 14 days after delivery. The customer gets 100% money-back in case they haven't downloaded the paper. All approved refunds will be returned to the customer’s credit card or Bonus Balance in a form of store credit. Take a note that we will send an extra compensation if the customers goes with a store credit. -
24/7 Customer Support
We have a support team working 24/7 ready to give your issue concerning the order their immediate attention. If you have any questions about the ordering process, communication with the writer, payment options, feel free to join live chat. Be sure to get a fast response. They can also give you the exact price quote, taking into account the timing, desired academic level of the paper, and the number of pages.