CMPT435 Assignment 3- Searching and hashing Solved

Goals • to    implement    searching    and    hashing,    and    to    understand    their    performance.
Requirements    
and    Notes • Download    the    the    text    Aile    magicitems.txt    from    our    web    site    if    you    
don’t    have    it    already.    
• Read    it    line    by    line    into    an    array.    
• Sort    the    array    using    one    of    your    sort    implementations    from    Assignment    
Two.    (Include    a    copy    of    your    sorting    code    in    this    assignment’s    directory    
so    that    it’s    easy    to    compile.)    
• Develop    your    own    implementation    of    linear    and    binary    search.    
• Randomly    select    42    items.    
• Perform    a    linear    search    on    the    (sorted)    array    for    each    of    those    randomly    
selected    items.    Print    the    number    of    comparisons    for    each    search    and    
compute    the    overall    average.    
• Perform    a    binary    search    on    the    (sorted)    array    for    the    same    “randomly”    
selected    items    as    before.    Print    the    number    of    comparisons    for    each    
search    and    compute    the    overall    average.    
• Record    your    results    in    a    table    in    your    LaTeX    document.    Also    note    the    
asymptotic    running    time    of    each    sort    and    explain    why    it    is    that    way.    
• Develop    your    own    implementation    of    a    hash    table    (with    chaining)    of    
size    250.    Use    the    hash    function    we    spoke    about    in    class    (and    in    the    
example    code    on    our    web    site    at    https://www.labouseur.com/courses/
algorithms/Hashing.java.html).    
• Load    your    hash    table    with    the    magic    items.    
• Retrieve    the    same    42    (no    longer-)    randomly    selected    items    from    your    
hash    table.    Print    the    number    of    (get    +    comparisons)    for    each    item    and    
compute    the    overall    average.    (Every    get    is    one,    then    count    the    
comparisons    needed    to    handle    chaining.)    
• Add    your    results    to    the    LaTeX    document,    including    the    asymptotic    
running    time    of    hashing    with    chaining    and    explain    why    it    is    that    way.
[60    points]    
[30    points]    
[10    points]
As    usual,    your    code    must    separate    structure    from    presentation,    be    
professionally    formatted    yet    uniquely    yours    (show    some    personality),    use    
and    demonstrate    best    practices,    and    make    me    proud    to    be    your    teacher. [−∞    if    not]
Resources • Linear    and    binary    search    are    described    in    our    text    in    sections    10.2    and    27.3.    
• Hash    tables    with    chaining    are    described    in    our    text    in    section    11.2.