Course topic 12¶

Self-study¶

The topic for this week is Hash tables.

The following links will take you to the video-lectures and the accompanying slides:

Hash tables¶

Hashtables¶

Question 1

How is a key used in a hash table?

The default status of a hash table is that it is locked, in other words no records in the hash table can be accessed. With a key, we can unlock the hash table.

A hash table is essentially just an array, where each location (or index) stores a record. A key is just a pompous synonym for a vector index.

Typically a hash table contains several keys, each of which is repeated. Hence there are two locations in the hash table containing the same key. To use the hash table we must search for the two locations containing the same key.

A unique key is associated with each record that is stored somewhere in the hash table. Using the key we can find the location of the record and hence access the contents of the record.

Question 2

Suppose in a hash table we want to store two keys \(k1\) and \(k2\) and their accompanying records. Assume \(k1\) is stored before \(k2\). If \(k1\) and \(k2\) point to the same bucket, how is this situation handled in open hashing?

Each bucket has associated with it a data structure, typically a linked list. The keys \(k1\) and \(k2\) and their accompanying records will be both stored somewhere in this data structure.

When key \(k2\) and its accompanying record are to be stored, an entirely new empty hash table is created in which only key \(k2\) is stored. Key \(k1\) remains stored in the old hash table.

The hash-function used in open-hashing will repeatedly change key \(k2\) to a new value until it finds an empty bucket. It then stores the new \(k2\) and its record and returns the new \(k2\) to the user.

Since the bucket to which \(k2\) points will not be empty, a search is conducted in the hash table for an empty bucket in which \(k2\) can be stored.

Question 3

Each bucket has associated with it a data structure, typically a linked list. The keys \(k1\) and \(k2\) and their accompanying records will be both stored somewhere in this data structure.

When key \(k2\) and its accompanying record are to be stored, an entirely new empty hash table is created in which key \(k2\) is stored.

The hash-function used in closed hashing will repeatedly change key \(k2\) to a new value until it finds an empty bucket. It then stores the new \(k2\) and its record and returns the new \(k2\) to the user.

Since the bucket to which \(k2\) points will not be empty, a search is conducted in the hash table for an empty bucket in which \(k2\) and its accompanying record can be stored.

Question 4

Which of the following are properties of a good hash function? (More than 1 property may be correct.)

It maps the keys uniformly amongst all the buckets.

It provides exactly two different bucket candidates for each key

It uses all data provided in a key.

It always maps all keys having the same length to the same bucket.

It always results in at least one bucket being empty.

It can be computed quickly, hence it should have a constant (\(O(1)\)) runtime efficiency.

Question 5

Suppose we are using the std:unordered_map container from STL. For which of the following situations will it be necessary for us to provide our own hash function?

When the keys we want to use are all of the std:string type.

When the number of buckets we wish to use is odd.

When the keys we want to use are all of some struct type, which we we have defined ourselves.

When we are sure that rehashing will have to be done at some point.

Question 6

Rehashing is necessary when …

at least half of the buckets are empty.

the load factor becomes larger than some acceptable limit.

the key sizes become too large.

at least one bucket starts leaking

Question 7

Suppose we are using a hash table with open-hashing. What is the load factor of such a hash table?

the number of records being stored divided by the total number of buckets available

the total number of buckets available divided by the number of records being stored

the largest number of records stored in any one bucket

the number of empty buckets divided by the total number of buckets available

Question 8

Suppose we are using a hash table with open-hashing. Suppose we want to search for key \(k\) in the hash table. From an runtime efficiency viewpoint, what is the worst possible situation for this search operation?

The bucket to which the hash function maps key \(k\) is empty.

All the keys currently stored in the hash table have been mapped to the same bucket and the hash function also maps \(k\) to this same bucket.

We have to search all the buckets in the hash table to find where the hash function has been stored.

There are no keys currently stored in the hash table and hence we have to go through all the buckets to confirm they are all empty.

Question 9

Suppose we are using a hash table with open-hashing and that our hash function does a good job at uniformly distributing the keys amongst the buckets. To determine when rehashing is done, an upper limit on the load factor must be set. The value of this upper limit is a compromise between what two things?

how frequently rehashing must be done and the runtime efficiency of the hash function

the average time for performing one search operation and the average time for performing one delete operation

the total amount of memory needed for the buckets and the average time for performing one search or delete operation

how much new memory is needed when rehashing and how frequently rehashing must be done

Question 10

Which of the following statements is the most accurate regarding the runtime efficiency of one search operation in a hash table?

When the hash function effectively distributes the keys uniformly amongst the buckets, the search operation has a big-O efficiency that is constant.

Regardless of how well the hash function distributes the keys amongst the buckets, the search operation has a has a big-O efficiency that is constant.

When the hash function effectively distributes the keys uniformly amongst the buckets, the search operation has an amortized big-O efficiency that is constant.

Regardless of how well the hash function distributes the keys amongst the buckets, the search operation has a big-O efficiency efficiency that is linear in the number of buckets.

Question 1

What is a central question, related to this course, whose answer can be found in this week’s videos?

Question 2

Of the following topics, which do you think deserves further discussion/explanation during the weekly consultation session?

How does a hash table work

Hash functions

Open and closed hashing

Rehashing

Question 3

Were there any parts of the video lectures that were particularly difficult? Particularly interesting? Something about which you wish to learn more?

Extra links on the topic:

Week12 - Glossary

Submit weekly exercises¶

Questions to be submitted this week

Course topic 13¶

Self-study¶

The topics for this week are the following: (i) Binary search trees, (ii) Balanced binary search trees

The following links will take you to the video-lectures and the accompanying slides:

Binary search trees¶

Video_en (part 1)

Video_en (part 2)

slides

Balanced binary search trees¶

Video_bst_01 (part 1)

Video_bst_02 (part 2)

Video_bst_03 (part 3)

Video_bst_04 (part 4)

slides

Binary search trees¶

Question 1

Suppose all the keys in a binary search tree (BST) are unique. Let \(x\) and \(y\) be two nodes in the BST whose keys are \(x.key\) and \(y.key\). Which of the following statements are always true? (More than 1 statement may be true.)

If \(y.key < x.key\), then \(y\) is the left child of \(x\).

If \(y.key < x.key\), then \(y\) is in the left subtree of \(x\).

If \(y\) is in the left subtree of \(x\), then \(y.key < x.key\).

If \(y\) is in the left subtree of \(x\), then \(y.key > x.key\).

If \(y\) is further away from the root than \(x\), then node \(y\) is in one of the subtrees of node \(x\).

If \(y.key < x.key\) and \(x\) is the root, then \(y\) is in the left subtree of \(x\).

Question 2

Suppose all the keys in a binary search tree (BST) are unique. When searching for a particular \(k\) key using a standard BST search algorithm, the algorithm reaches a leaf \(x\). Which of the following is true?

The key of \(x\) is equal to \(k\).

There is no node in the BST whose key is \(k\).

If there is a node in the BST whose key is \(k\), then it is node \(x\).

If the key of \(x\) is not equal to \(k\), then the search must continue by starting from the root of the BST and searching in the subtree that does not contain \(x\).

Question 3

To obtain all the keys of a binary search tree in ascending order …

… we can use a breadth first search.

… we can use Dijkstra’s algorithm.

… we can use an inorder traversal.

… we can use a postorder traversal.

Question 4

Suppose all the keys in a binary search tree (BST) are unique and we want to insert a new node having key \(k\) into the BST using the standard insert algorithm. What can be said about the position of the new node?

If \(k\) is less than the key of the root, then the new node will always be a left child.

If \(k\) is less than the key of the key of some leaf, then the new node will always be a left child.

If the existing BST has at least 2 nodes and \(x\) is the parent of the new node, then after inserting the new node \(x\) will have exactly 2 children.

The new node will always be a leaf.

Question 5

Suppose all the keys in a binary search tree (BST) are unique and let the tree have at least 1000 nodes. Let \(x\) be a leaf in the BST whose key is \(x.key\). If a new node \(y\) having key \(y\) is being inserted, which of the following claims is true?

If \(y.key < x.key\), then inserting node \(y\) as the left child of \(x\) will always yield a valid BST.

If \(y.key < x.key\), then inserting node \(y\) as the right child of \(x\) will always yield a valid BST.

If \(y.key < x.key\), then inserting node \(y\) as the right child of \(x\) will never yield a valid BST.

If \(y.key < x.key\) and \(x.key\) is the smallest key in the BST, then inserting node \(y\) as the left child of \(x\) will never yield a valid BST.

Balanced binary search trees and the efficiency of binary search tree operations¶

Question 1

Suppose a binary search tree (BST) has been formed by adding \(n\) nodes to an empty BST and \(n > 1000\). In addition suppose that we are performing a search for a key that does not occur in the BST. The worst case runtime efficiency for such a search is linear in \(n\). Which of the following properties does not correspond to a BST having this worst case runtime efficiency?

A BST where the number of nodes which have have 2 children is as large as possible.

A BST whose height is as large as possible for the given \(n\).

A BST where each node has at most one child.

A BST which has only one leaf.

Question 2

Suppose a rotation is performed on BST \(B1\) with the result being BST \(B2\). Which of the following is not a possible consequence of the rotation?

A right subtree of some node in \(B1\) becomes the left subtree of some other node in \(B2\).

When node \(u\) was the parent of node \(v\) in \(B1\), node \(v\) becomes the parent of node \(u\) in \(B2\).

For all nodes \(u\), the distance of \(u\) from the root in \(B2\) is less than the distance of \(u\) from the root in \(B1\).

The height of \(B2\) is less than the height of \(B1\).

Question 3

Which of the following is not true for an AVL binary search tree?

One or more rotations might be used when inserting a new node into an AVL binary search tree.

Let \(x\) be a node in an AVL binary search tree. The difference in the heights of the left and right subtrees of \(x\) is at most 1.

Let \(x\) be a node in an AVL binary search tree and \(y\) be a leaf in some subtree of \(x\). The distance of any leaf \(y\) from node \(x\) is always the same value.

Let \(x\) be a node in an AVL binary search tree. Some data must be stored at \(x\) from which we can get the difference in the heights of the left and right subtrees.

Question 4

Suppose a binary search tree (BST) has been formed by adding \(n\) nodes to an empty BST and \(n > 1000\). Consider two alternatives: (I) in forming the BST nothing special is done to try to keep it balanced, (II) the BST is formed using either an AVL or a red-black BST. What advantage do we gain by in using alternative (II)?

We avoid the possibilty that the runtime efficiency of a search operation is linear in \(n\).

We ensure that the difference between the depth of any two leaves is at most 1.

We ensure that the height of the BST is as small as possible.

We ensure that in the BST there is at most one node that has precisely one child.

Question 1

What is a central question, related to this course, whose answer can be found in this week’s videos?

Question 2

Of the following topics, which do you think deserves further discussion/explanation during the weekly consultation session?

What is a binary search tree

Rotations done in a binary search tree

AVL binary search trees

Red-black binary search trees

Question 3

Were there any parts of the video lectures that were particularly difficult? Particularly interesting? Something about which you wish to learn more?

Extra links on the topic:

A site where you can visualize operations on binary search trees

Week13 - Glossary

Submit weekly exercises¶

Questions to be submitted this week

Course topic 14¶

The only video this week is a blooper collection .

Blooper collection (mostly in Finnish)¶

Video

Extra links on the topic:

The Introduction to Algorithms course of MIT

Submit weekly exercises¶

There are no more exercises to be submitted.