WE WRITE CUSTOM ACADEMIC PAPERS

100% Original, Plagiarism Free, Tailored to your instructions

Order Now!

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

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.

Excellent Quality
Zero Plagiarism
Expert Writers

Instant Quote

Subject:
Type:
Pages/Words:
Single spaced
approx 275 words per page
Urgency (Less urgent, less costly):
Level:
Currency:
Total Cost: NaN

Get 10% Off on your 1st order!