Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 31 views

    TCP2101 Algorithm Design and Analysis Lab02 - HashTables

    Uploaded by

    husnazk.work
    The document describes a lab assignment on implementing and using hash tables. It includes: - Learning outcomes about understanding the hash table abstract data type (ADT) and using chaining and linear probing to resolve collisions. - A problem to insert keys into a hash table using chaining or linear probing and describe the resulting table. - An incomplete C++ implementation of a hash table class using chaining that needs functions for insertion and retrieval completed. - A main program to demonstrate use of the hash table class by inserting an array of keys and retrieving a target key.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    TCP2101 Algorithm Design and Analysis Lab02 - HashTables

    Uploaded by

    husnazk.work
    31 views4 pages
    The document describes a lab assignment on implementing and using hash tables. It includes: - Learning outcomes about understanding the hash table abstract data type (ADT) and using chaining and linear probing to resolve collisions. - A problem to insert keys into a hash table using chaining or linear probing and describe the resulting table. - An incomplete C++ implementation of a hash table class using chaining that needs functions for insertion and retrieval completed. - A main program to demonstrate use of the hash table class by inserting an array of keys and retrieving a target key.

    Original Description:

    Original Title

    TCP2101 Algorithm Design and Analysis Lab02_HashTables

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes a lab assignment on implementing and using hash tables. It includes: - Learning outcomes about understanding the hash table abstract data type (ADT) and using chaining and linear probing to resolve collisions. - A problem to insert keys into a hash table using chaining or linear probing and describe the resulting table. - An incomplete C++ implementation of a hash table class using chaining that needs functions for insertion and retrieval completed. - A main program to demonstrate use of the hash table class by inserting an array of keys and retrieving a target key.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    31 views4 pages

    TCP2101 Algorithm Design and Analysis Lab02 - HashTables

    Uploaded by

    husnazk.work
    The document describes a lab assignment on implementing and using hash tables. It includes: - Learning outcomes about understanding the hash table abstract data type (ADT) and using chaining and linear probing to resolve collisions. - A problem to insert keys into a hash table using chaining or linear probing and describe the resulting table. - An incomplete C++ implementation of a hash table class using chaining that needs functions for insertion and retrieval completed. - A main program to demonstrate use of the hash table class by inserting an array of keys and retrieving a target key.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 4

    TCP2101 Algorithm Design and Analysis

    Lab 2 HashTables

    Learning Outcomes
    ● Understand HashTable ADT
    ● Use chaining and linear probing to resolve collision.

    1. Hashtable ADT: The following sequence of 10 numbers are inserted into a hash table using
    hash function h(k) = k % 11.

    (a) (30 min) If chaining is used to resolve collision, how does the hashtable look like? Fill up
    the h(k) value in the table below.

    k 36 99 80 21 58 11 25 46 91 10
    h(k) 36% 99% 80% 21 % 58 % 11 % 25 % 46 % 91 % 10 %
    11 = 11 = 11 = 11 = 11 = 11 = 11 = 11 = 11 = 11 =
    3 0 3 10 3 0 3 2 3 10
    Collision N N Y N Y Y Y N Y Y
    (Y/N)

    0 -> 11 -> 99
    1 ->
    2 -> 46
    3 -> 91 -> 25 -> 58 -> 80 -> 36
    4 ->
    5 ->
    6 ->
    7 ->
    8 ->
    9 ->
    10 -> 10 -> 21

    (b) (30 min) If linear probing is used to resolve collisions. What does the hashtable look like?
    Fill up the h(k) value in the table below.

    k 36 99 80 21 58 11 25 46 91 10
    h(k) 3 0 3 10 3 0 3 2 3 10
    No of 0 0 1 0 2 1 3 0 4 9
    Collision

    k 99 11 46 36 80 58 25 91 10 21
    probe 0 1 0 0 1 2 3 4 9 0
    index 0 1 2 3 4 5 6 7 8 9 10

    1
    2. An incomplete C++ implementation of Hashtable ADT with chaining is provided below.

    (a) (20 min) Complete the insert function and retrieve function in the HashTable class. Use
    the LinkedList.cpp from tutor.

    // HashTable.cpp
    #include <vector>
    #include "LinkedList.cpp" // get from tutor

    template <typename T>


    class HashTable {
    vector< LinkedList<T> > table;
    int hashfunction (int hashitem) { // hash function
    return hashitem % table.size();
    }
    public:
    HashTable (int size) {
    table.resize (size); // resize vector to support size elements.
    }
    ~HashTable() {
    for (int i = 0; i < table.size(); i++)
    table[i].makeEmpty();
    }
    int size() {
    return table.size();
    }
    void insert (T newItem) {
    //int location =?
    int location = hashfunction(newItem);
    table[location].insertFront(newItem); //chaining

    }
    bool retrieve (T & target) {
    int location = hashfunction(target);
    if (!table[location].find(target)//type ife ctrl+j
    {
    return false;
    }
    else
    {
    return true;
    }
    // bool found = table[index].find(target);
    //return found;

    }
    friend ostream& operator<< (ostream& os, HashTable<T>& ht) {
    for (int i = 0; i < ht.size(); i++)
    os << i << " = " << ht.table[i] << endl;
    return os;
    }
    };

    2
    (b) (20 min) Complete the following program that uses the above HashTable class. Verify that
    the program output is correct.

    // lab02q2b.cpp -- demonstrates the use of hashtable with chaining.


    #include <iostream>
    // 1. Include HashTable.cpp.
    #include "HashTable.cpp"

    using namespace std;

    int main() {
    const int n = 10;
    int A[n] = {36, 99, 80, 21, 58, 11, 25, 46, 91, 10};
    // 2. Declare a hashtable of int named "ht", size is 11.
    HashTable<int> ht(11); //<int> is to support integer datatype

    cout << "Array : ";


    for (int i = 0; i < n; i++) {
    cout << A[i] << " ";
    // 3. Insert A[i] into ht.
    ht.insert(A[i]);
    }
    cout << endl;

    // Display ht.
    cout << ht << endl;

    int target;
    cout << "Target to retrieve: ";
    cin >> target;
    // 4. Retrieve the target from ht.
    if (ht.retrieve(target))
    cout << "Target found\n";
    else
    cout << "Target not found\n";
    }

    (c) (10 min) Count the number of primitive operations of each step in LinkedList’s insertFront
    function. What is its time complexity?

    Algorithm Number of primitive operations


    Node<T> *newNode = new Node<T>; 1
    newNode->info = element; 1
    newNode->next = start; 1
    start = newNode; 1
    T(n) O(1) -> independent of the number of
    items

    3
    (d) (10 min) Count the number of primitive operations of each step in LinkedList’s find function.
    What is its time complexity?

    Algorithm Number of primitive operations


    bool found = false; 1
    Node<T> *ptr = start; 1
    while (ptr != NULL && !found) n
    if (ptr->info == target) n
    found = true; n
    else n
    ptr = ptr->next; n
    return found; 1
    T(n) O(n) -> proportion to the number of
    items

    You might also like