Linear Probing - Coursera Algorithms

Linear probing is used to resolve collisions in hashing. It takes less space and has better cache performance.

An array of size M > number of elements N is used such that:

1. Hash - map key to i between 0 and M-1.
2. Insert - at table index i, if not free - try i+1, i+2 etc

3. Search - search table index i, if occupied and no match - try i+1, i+2 etc

Following is the implementation :

Separate Chaining - Coursera Algorithms

To deal with collisions in hashing, separate chaining implementation can be used, where M linked lists(<number of elements N) are used such that :

1. Hash - map key to i between 0 and M-1.
2. Insert - at the front of ith chain.

3. Search - in ith chain.

Easier to implement and clustering less sensitive to poorly designed hash function.

Following is the implementation:

Hash Functions - Coursera Algorithms

We can do better than the sequential/binary search or search through BST/red-black BST, by storing the data in key-indexed table. Hash functions compute the array index from key. We need to handle the hash implementation, equality test and collision resolution when two keys hash to the same index.

There are several hashing implementations, some of them being :
1. 31*initial_hash_value+ current element value or current object hashcode.
2. Modular - Math.abs(key.hashCode() & 0x7fffffff)%M returning a hash between 0 and M-1

Following code experiments with what happens when we override equals/hashcode:

Heap Sort - Coursera Algorithms

Heap Sort is an in place sort that builds a max binary heap and then repeatedly deletes the maximum element. It's not stable and it's inner loop takes longer than Quick Sort. It has poor cache usage. To build a heap, it takes O(N) and for sort, it takes O(NlogN).

Following is the program:

Related Posts:

Binary Heap

Binary Heap - Coursera Algorithms

A binary tree is either empty or points to a root node with links to left and right binary trees. A tree is complete if it is balanced perfectly, excluding the bottom level. A binary heap is an array representation of a heap ordered complete binary tree.

Max node is root at a[1]. For a node k, it's parent is at k/2 and it's children are at 2k and 2k+1.
Swim: When a child node is greater than parent, keep exchanging them till they are ordered.
Sink: When a parent node is lesser than child, keep exchanging them till they are ordered.
In insert operation, add the child at end and swim it. --> O(logN)
In delete operation, exchange root with node at end and sink the top node. -->O(logN)

Following is the program:

Maximum Priority Queue - Coursera Algorithms

Max priority queues pick the maximum element for deletion instead of picking the first in element as done in Queues. It takes O(N) for extracting the max. Following is the program:

Three Way Quick Sort - Coursera Algorithms

Three Way Quick Sort uses multiple partition elements, such that the there are no larger entries to their left and no smaller entries to their right. It is in place, but not a stable sort. This is used to deal with duplicate elements.

Time complexity: O(NlgN)


Following is the program, partition elements are from lt to gt:

Related Posts: 

Quick Sort

Insertion Sort