Algorithm
1) Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty.
2) Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first.
3) While sptSet doesn’t include all vertices
a) Pick a vertex u which is not there in sptSetand has minimum distance value.
b) Include u to sptSet.
c) Update distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if sum of distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v.
void dijkstra(int graph[V][V], int src)
{
int dist[V];
bool sptSet[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;
dist[src] = 0;
for (int count = 0; count < V-1; count++)
{
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++){
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
&& dist[u]+graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
}
}
Monthly Archives: October 2014
Prim’s Minimum Spanning Tree
Algorithm
1) Create a set mstSet that keeps track of vertices already included in MST.
2) Assign a key value to all vertices in the input graph. Initialize all key values as INFINITE. Assign key value as 0 for the first vertex so that it is picked first.
3) While mstSet doesn’t include all vertices
a) Pick a vertex u which is not there in mstSet and has minimum key value.
b) Include u to mstSet.
c) Update key value of all adjacent vertices of u. To update the key values, iterate through all adjacent vertices. For every adjacent vertex v, if weight of edge u-v is less than the previous key value of v, update the key value as weight of u-v
void primMST(int graph[V][V])
{
int parent[V];
int key[V];
bool mstSet[V];
for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V-1; count++)
{
int u = minKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++){
// graph[u][v] is non zero only for adjacent vertices of m
// mstSet[v] is false for vertices not yet included in MST
// Update the key only if graph[u][v] is smaller than key[v]
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
}
}
Huffman Coding
Steps to build Huffman Tree
1. Create a leaf node for each unique character and build a min heap of all leaf nodes (Min Heap is used as a priority queue. The value of frequency field is used to compare two nodes in min heap. Initially, the least frequent character is at root)
2. Extract two nodes with the minimum frequency from the min heap.
3. Create a new internal node with frequency equal to the sum of the two nodes frequencies. Make the first extracted node as its left child and the other extracted node as its right child. Add this node to the min heap.
4. Repeat steps#2 and #3 until the heap contains only one node. The remaining node is the root node and the tree is complete.
CODE
struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size)
{
struct MinHeapNode *left, *right, *top;
struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size);
// Iterate while size of heap doesn't become 1
while (!isSizeOne(minHeap))
{
left = extractMin(minHeap);
right = extractMin(minHeap);
// Create a new internal node with frequency equal to the
// sum of the two nodes frequencies. Make the two extracted node as
// left and right children of this new node.
// Add this node to the min heap
top = newNode('$', left->freq + right->freq);
top->left = left;
top->right = right;
insertMinHeap(minHeap, top);
}
return extractMin(minHeap);
}
void printCodes(struct MinHeapNode* root, int arr[], int top)
{
if (root->left)
{
arr[top] = 0;
printCodes(root->left, arr, top + 1);
}
if (root->right)
{
arr[top] = 1;
printCodes(root->right, arr, top + 1);
}
if (isLeaf(root))
{
printf("%c: ", root->data);
printArr(arr, top);
}
}
Kruskal’s Minimum Spanning Tree Algorithm
Pseudocode
KRUSKAL(G):
A = ∅
foreach v ∈ G.V:
MAKE-SET(v)
foreach (u, v) ordered by weight(u, v), increasing:
if FIND-SET(u) ≠ FIND-SET(v):
A = A ∪ {(u, v)}
UNION(u, v)
return A
MAIN CODE
struct Edge
{
int src, dest, weight;
};
struct Graph
{
int V, E;
struct Edge* edge;
};
struct subset
{
int parent;
int rank;
};
int find(struct subset subsets[], int i)
{
// find root and make root as parent of i (path compression)
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
// (uses union by rank)
void Union(struct subset subsets[], int x, int y)
{
int xroot = find(subsets, x);
int yroot = find(subsets, y);
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
else
{
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
int myComp(const void* a, const void* b)
{
struct Edge* a1 = (struct Edge*)a;
struct Edge* b1 = (struct Edge*)b;
return a1->weight > b1->weight;
}
void KruskalMST(struct Graph* graph)
{
int V = graph->V;
struct Edge result[V];
int e = 0;
int i = 0;
qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);
struct subset *subsets =
(struct subset*) malloc( V * sizeof(struct subset) );
for (int v = 0; v < V; ++v)
{
subsets[v].parent = v;
subsets[v].rank = 0;
}
while (e < V - 1)
{
struct Edge next_edge = graph->edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
if (x != y)
{
result[e++] = next_edge;
Union(subsets, x, y);
}
}
return;
}
Union-Find Algorithm
Detect Cycle in a an Undirected Graph
Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.
Union: Join two subsets into a single subset.
0
| \
| \
1-----2
For each edge, make subsets using both the vertices of the edge. If both the vertices are in the same subset, a cycle is found.
Initially, all slots of parent array are initialized to -1 (means there is only one item in every subset).
0 1 2
-1 -1 -1
Edge 0-1: Find the subsets in which vertices 0 and 1 are. Since they are in different subsets, we take the union of them. For taking the union, either make node 0 as parent of node 1 or vice-versa.
0 1 2 <---- 1 is made parent of 0
(1 is now representative of subset {0, 1})
1 -1 -1
Edge 1-2: 1 is in subset 1 and 2 is in subset 2. So, take union.
0 1 2 <----- 2 is made parent of 1
(2 is now representative of subset {0, 1, 2})
1 2 -1
Edge 0-2: 0 is in subset 2 and 2 is also in subset 2. Hence, including this edge forms a cycle.
How subset of 0 is same as 2?
0->1->2 // 1 is parent of 0 and 2 is parent of 1
CODE
// (uses path compression technique)
int find(struct subset subsets[], int i)
{
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
// (uses union by rank)
void Union(struct subset subsets[], int x, int y)
{
int xroot = find(subsets, x);
int yroot = find(subsets, y);
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
else
{
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
int isCycle( struct Graph* graph )
{
int V = graph->V;
int E = graph->E;
struct subset *subsets =
(struct subset*) malloc( V * sizeof(struct subset) );
for (int v = 0; v < V; ++v)
{
subsets[v].parent = v;
subsets[v].rank = 0;
}
for(int e = 0; e < E; ++e)
{
int x = find(subsets, graph->edge[e].src);
int y = find(subsets, graph->edge[e].dest);
if (x == y)
return 1;
Union(subsets, x, y);
}
return 0;
}
Remove duplicate from unsorted linked list
METHOD 1 (Using two loops)
struct node
{
int data;
struct node *next;
};
void removeDuplicates(struct node *start)
{
struct node *ptr1, *ptr2, *dup;
ptr1 = start;
while(ptr1 != NULL && ptr1->next != NULL)
{
ptr2 = ptr1;
while(ptr2->next != NULL)
{
if(ptr1->data == ptr2->next->data)
{
dup = ptr2->next;
ptr2->next = ptr2->next->next;
free(dup);
}
else
{
ptr2 = ptr2->next;
}
}
ptr1 = ptr1->next;
}
}
Time Complexity: O(n^2)
METHOD 2 (Use Sorting)
In general, Merge Sort is the best suited sorting algorithm for sorting linked lists efficiently.
1) Sort the elements using Merge Sort. O(nLogn)
2) Remove duplicates in linear time using the algorithm for removing duplicates in sorted Linked List. O(n)
Please note that this method doesn’t preserve the original order of elements.
Time Complexity: O(nLogn)
METHOD 3 (Use Hashing)
void deleteDups(LinkedListNode n)
{
Hashtable table = new Hashtable();
LinkedListNode previous = null;
while (n != null) {
if (table.containsKey(n.data))
previous.next = n.next;
else {
table.put(n.data, true);
previous = n;
}
n = n.next;
}
}
Time Complexity: O(n) on average (assuming that hash table access time is O(1) on average).
Find k closest elements to a given value
Runtime: O(Logn + k)
int findCrossOver(int arr[], int low, int high, int x)
{
if (arr[high] <= x)
return high;
if (arr[low] > x)
return low;
int mid = (low + high)/2;
if (arr[mid] <= x && arr[mid+1] > x)
return mid;
if(arr[mid] < x)
return findCrossOver(arr, mid+1, high, x);
return findCrossOver(arr, low, mid - 1, x);
}
void printKclosest(int arr[], int x, int k, int n)
{
int l = findCrossOver(arr, 0, n-1, x);
int r = l+1; // Right index to search
int count = 0;
if (arr[l] == x) l--; // Assumption: all elements in arr[] are distinct
while (l >= 0 && r < n && count < k)
{
if (x - arr[l] < arr[r] - x)
printf("%d ", arr[l--]);
else
printf("%d ", arr[r++]);
count++;
}
while (count < k && l >= 0)
printf("%d ", arr[l--]), count++;
while (count < k && r < n)
printf("%d ", arr[r++]), count++;
}
Sort n numbers in range from 0 to n^2 – 1 in O (n)
Radix Sort takes O(d*(n+b)) time where b is the base for representing numbers.
Since n2-1 is the maximum possible value, the value of d would be O(logb(n)).
So overall time complexity is O((n + b) * logb(n)).
If we set b as n, the value of O(logb(n)) becomes O(1) and overall time complexity becomes O(n).
// the digit represented by exp.
int countSort(int arr[], int n, int exp)
{
int output[n];
int i, count[n] ;
for (int i=0; i < n; i++)
count[i] = 0;
for (i = 0; i < n; i++)
count[ (arr[i]/exp)%n ]++;
for (i = 1; i < n; i++)
count[i] += count[i - 1];
for (i = n - 1; i >= 0; i--)
output[--count[ (arr[i]/exp)%n]] = arr[i];
for (i = 0; i < n; i++)
arr[i] = output[i];
}
void sort(int arr[], int n)
{
// Do counting sort for first digit in base n.
exp (n^0 = 0) is passed.
countSort(arr, n, 1);
// Do counting sort for second digit in base n.
exp (n^1 = n) is passed.
countSort(arr, n, n);
}
How to sort if range is from 1 to n2 ?
1) Subtract all numbers by 1.
2) Since the range is now 0 to n2, do counting sort twice as done in the above implementation.
3) After the elements are sorted, add 1 to all numbers to obtain the original numbers.
How to sort if range is from 0 to n^3 -1?
Since there can be 3 digits in base n, we need to call counting sort 3 times.
Search in an almost sorted array
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;
// If the element is present at one of the middle 3 positions
if (arr[mid] == x) return mid;
if (mid > l && arr[mid-1] == x) return (mid - 1);
if (mid < r && arr[mid+1] == x) return (mid + 1);
if (arr[mid] > x) return binarySearch(arr, l, mid-2, x);
return binarySearch(arr, mid+2, r, x);
}
return -1;
}
When does the worst case of Quicksort occur?
The answer depends on strategy for choosing pivot. In early versions of Quick Sort where leftmost (or rightmost) element is chosen as pivot, the worst occurs in following cases. 1) Array is already sorted in same order. 2) Array is already sorted in reverse order. 3) All elements are same (special case of case 1 and 2) Since these cases are very common use cases, the problem was easily solved by choosing either a random index for the pivot, choosing the middle index of the partition or (especially for longer partitions) choosing the median of the first, middle and last element of the partition for the pivot. With these modifications, the worst case of Quick sort has less chances to occur, but worst case can still occur if the input array is such that the maximum (or minimum) element is always chosen as pivot.
Learn By Coding 