Question

8. Assume you have a singly linked list with no tail pointer. Implement removeTail(). Raise an exception of the method is called on an empty list.
template<typename Object> class LinkedList {
private:

class Node {

Object data;

Node* next;

};

Node *head;
public:

LinkedList() : head(nullptr) {}

Object removeTail(Object data);

};

9. What are iterators? What purpose do they serve?
10. What does it mean to invalidate an iterator?
11. Explain the difference between separate chaining and open addressing in hash tables.
12. Define load factor and explain its relevance to hash table performance.
13. What are collisions with respect to hash tables?
14. Which hash tables distinguish between slots that have never been used, and slots that once contained an item but has now been deleted.
15. List and explain the worst-case and average-case running times for each HashTable method below
(a) void insert(Key k, Value v)

(b) bool contains(Key k)

(c) Value get(Key k)

Answer 1

8)

template<typename Object>
class LinkedList {
private:
class Node{
public:
    Object data;
    Node* next;
};

Node *head;

public:
LinkedList() : head(nullptr) {}
Object removeTail(Object data){
    try{
      if(head == nullptr) throw nullptr;
      Node* temp = head;
      while(temp->next != NULL){
        if(temp->next->next == NULL){
          delete temp->next;
          temp->next = nullptr;
          break;
        }
        temp = temp->next;
      }
    }catch(Node* n){
      cout<<"Exception on null list"<<endl;
    }
}
};

------------------------------------------------------------------------

9)

Iterator has behavioral purpose and applies to objects.
Iterators provides a way to access the elements of an aggregate object sequentially without exposing its underlying representation.

Purpose:
To access an aggregate object's contents without exposing its internal representation
To support multiple traversals of aggregate objects
To provide a uniform interface for traversing different aggregate structures

----------------------------------------------------------------------------

10)

An Iterator becomes invalidate when the object it points to changes its shape internally i.e. delete the object or move elements from one location to another that the iterator still points to old invalid location.

-----------------------------------------------------------------------------

11)

i] Separate chaining in hash table indexes into an array of pointers to the heads of linked lists. Each linked list cell has the key for which it was allocated and the value which was inserted for that key.
In open-addressing, you use the key's hash value to work out which slot in the array to look at first. If more than one key in the hash table has the same hash, then you use some scheme to decide on another slot to look in instead(rehash).

ii] When you want to look up a particular element from its key, the key's hash is used to work out which linked list to follow, and then that particular list is traversed to find the element that you're after.
In open-addressing, you keep rehashing the key until you find the value in the hash table.

iii] Separate chaining requires more memory and time than open addressing for inserting and searching values in hash table at worst case.

iv] Separate chaining is easy to implement and maintainace than open addressing where each new rehashing requires new hash function that returns new slot in an array except existing slot.

-------------------------------------------------------------------------

12)

Load factor is a measure, which decides when exactly to increase the hash table capacity to maintain insert and search operation complexity of O(1).
When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed so that the hash table has approximately twice the number of buckets.
Load factor defines how many entries can the hash table store, if it exceeds, then another hash table is created to maintain hash table performance which is O(1) insert and search.

----------------------------------------------------------------------------

13)

When hash key is computed by a hash function that generates an index into a slot of array that already been occupied then collision has occured.

-----------------------------------------------------------------------------

14)

open addressing hash tables (See Que. 11 Answer)

-------------------------------------------------------------------------------

15)

(a) void insert(Key k, Value v)

    Worst-case: O(n), Average-case: O(1)
    Depends on collision handling mechanism and hash functions.
    if separate chaining is used then O(n) in both worst & average cases. O(1) if collision not occurs.
    if open addressing is used then it depends on time complexity of the hash function.

(b) bool contains(Key k)

    Worst-case: O(n), Average-case: O(1)
    Same as in (a)
    if value is found at key k, then O(1), otherwise O(n).

(c) Value get(Key k)

    Worst-case: O(n), Average-case: O(1)
    Same as in (b)