Binary Search
This is a very important algorithm you can apply at many different problem environments you never expect.
Understand the runtime complexity for the Binary Search and understand how to derive the complexity from algorithm. Note that it can be applied for only sorted lists. Learn how to apply Binary Search in a Rotated Sorted List by using recursion and how the algorithm complexity varies. Implement Binary Search using C for a list of strings. You should familiarize the terms in place sorting, stable sorting and also should understand which sorts come into these categories.
Insertion Sort
Understand the algorithm and derivation of algorithm analysis. Compare it with Card game in which we move the cards to the suitable position. Keep the example in mind and apply to similar problems. In Insertion sort, we sort the element set by consequently moving the current element to the appropriate position in an already sorted set.
QuickSort
QuickSort is a very important sorting technique. It uses divide and conquer technique. Divide the given set of elements into smaller sets recursively and apply comparison and swap. When comparison and swap is performed to formulated smaller sets, it results in the larger sorted set. Learn algorithm analysis. Learn how to find kth smallest element by modifying the Quicksort algorithm in O(nk) complexity. Find out mean of a set of elements in O(n) by modifying the above problem.
MergeSort
Mergesort is also a divide and conquer sorting technique. The concept is to merge two sorted list to obtain larger sorted set. By dividing the given array into smaller subset by recursion, smaller subsets are formed. Merging the subsets from lower level to higher level, we obtain sorted array. Learn algorithm analysis. Note that merge sort takes an extra array. Hence this is not an in place sorting. It has O(n) space complexity. You should practice problems related to merge sort. Eg. You are given two sorted arrays with size n and 2n. The second array contain n elements in the positions 0 to n-1. Now without using extra space, formulate the elements in 1st and 2nd array into 2nd array and return a sorted array of size 2n.
HeapSort
Heapsort is an interesting sorting technique. Heap is a tree in which parent node is always >= child nodes (called as max-heap) or parent node is always <= child nodes (called as min-heap). This is the basic property for a heap. Let us have an overview of how to create a heap and manage it. When we need to add an element into an existing heap, we add the element as root or to the rightmost bottom element in the heap. Then apply heapify operation. Heapify operation can be of two types: shiftup and shift down. When we add a new element to an existing heap as root element, we perform shift down operation. Shift down operation performs a traversal from root level to bottom level, at each level of traversal, it compares whether heap property is violated, if so it will perform swap between parent node and child node to obey the heap property. Hence the element we added as root will move to the accurate position when the traversal reaches the bottom level. If we add a new element to the bottom right element, we need to perform a shift up to position the element to the right position. We traverse from parent in the bottom level to the root, by checking the heap property at each level and swapping elements to meet the heap property, we get a balanced heap when traversal reaches the top element.
Heapsort makes use of these operations to obtain a sorted set. Let us assume we have a heap (1,n). the root element will be the highest value (max-heap). Hence it will be the last element in the sorted list. We swap the root and the last element. Now the heap property is lost. But the nth position of array has the correct element in the sorted list. So we exclude nth element and heapify the heap(1,n-1) by using shift down operation. Because the root element is the one breaking the heap balance. After doing heapify 2nd time, we get 2nd highest element as root element. Now swap root element with n-1 element. Hence n-1, nth elements are 2nd largest and largest elements. Now exclude the n-1 and nth element, heapify heap(1,n-2). Follow the procedure until the newly formed heap size become one. You will get a sorted list. Read the chapter Heaps from Programming Pearls (It will give you a wonderful insight). Practice the problems: Find kth largest element from a given unsorted array. Implement priority queues.
