After
postponing for 3-6 months finally I took Algorithms 1 course in June-july 2017.
Notes:-
Week 1:-
I have
spent nearly 10-15 hours on solving the percolation problem.Its totally worth
it.
Mistakes:-
- I tried to solve
the problem without understanding completely.
- I wasted lot of
time in checking for references and help online.
Note:- Please
use the below code for reference only,else it will spoil the fun:-)
Analysis of algos:-
Week 2:-
Stacks
And Queues:-
- Implement each using either
a singly-linked list or a resizing array.
- Importance of generics and
iterators.
- parsing arithmetic
expressions using Dijkstra Algorithm
Sorting:-
Basic
Sorting Algorithms with O(n2) time complexity.
Shuffle:-
Knuth
Algorithm:-
public static void shuffle(Object[] a) {
int n
= a.length;
for (int i = 0; i < n; i++)
{
// choose index uniformly in
[0, i]
int r = (int) (Math.random()
* (i + 1));
Object swap =
a[r];
a[r] = a[i];
a[i] = swap;
}
}
Week 3:-
MergeSort:
very
good stable algorithm for sorting.
Performance = O(nlogn)
Space = O(n) !!!Major drawback it
requires n spaces
It
uses recursion:-
mergesort(array){
mergesort(leftarray)
mergesort(rightarray)
merge left half n right half in sorted
order
}
public
class MergeSort {
public static void
mergesort(Comparable[] array) {
Comparable[] temp = new
Comparable[array.length];
mergesort(array, temp, 0, array.length
- 1);
show(temp);
}
public
static void mergesort(Comparable[] array, Comparable[] temp, int leftStart,
int rightEnd) {
if
(leftStart >= rightEnd) {
return;
}
int middle = (leftStart + rightEnd) /
2;
mergesort(array, temp, leftStart,
middle);
mergesort(array, temp, middle + 1,
rightEnd);
merge(array, temp, leftStart, rightEnd);
}
@SuppressWarnings("unchecked")
public static void merge(Comparable[]
array,Comparable[] temp,int leftStart,int rightEnd) {
int leftEnd = (leftStart + rightEnd) /
2;
int rightStart = leftEnd +
1;
int size = rightEnd - leftStart +
1;
int index = leftStart;//index to temp
array,need to start from beginning i.e leftStart
while (leftStart <= leftEnd
&& rightStart <= rightEnd) {
if
(array[leftStart].compareTo(array[rightStart]) < 0) {
temp[index] =
array[leftStart];
leftStart++;
} else {
temp[index] =
array[rightStart];
rightStart++;
}
index++;
}
for (int i = leftStart; i <=
leftEnd; i++) {
temp[index] = array[i];
index++;
}
for (int i = rightStart; i <=
rightEnd; i++) {
temp[index] = array[i];
index++;
}
for (int i = leftStart; i <=
rightEnd; i++) {
array[i] = temp[i];
}
// System.arraycopy(array, leftStart,
temp, index, leftEnd - leftStart + 1);
// System.arraycopy(array, rightStart,
temp, index, rightEnd - rightStart + 1);
// System.arraycopy(temp, leftStart,
array, leftStart, size);
}
private
static void show(Comparable[] temp) {
for (int i = 0; i < temp.length;
i++) {
System.out.print("\t" +
temp[i]);
}
}
QuickSort:-(Lomuto partition scheme)
// Java program for implementation of QuickSort
class QuickSort
{
/* This function takes last element as pivot,
places the pivot element at its correct
position in sorted array, and places all
smaller (smaller than pivot) to left of
pivot and all greater elements to right
of pivot */
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low-1); // index of smaller element
for (int j=low; j<high; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
/* The main function that implements QuickSort()
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void sort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
sort(arr, low, pi-1);
sort(arr, pi+1, high);
}
}
/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
// Driver program
public static void main(String args[])
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = arr.length;
QuickSort ob = new QuickSort();
ob.sort(arr, 0, n-1);
System.out.println("sorted array");
printArray(arr);
}
}
Hoare’s Partition Scheme
Hoare’s Partition Scheme works by initializing two indexes that start at two ends, the two indexes move toward each other until an inversion is (A smaller value on left side and greater value on right side) found. When an inversion is found, two values are swapped and process is repeated.
artition(arr[], lo, hi)
pivot = arr[lo]
i = lo - 1 // Initialize left index
j = hi + 1 // Initialize right index
// Find a value in left side greater
// than pivot
do
i = i + 1
while arr[i] < pivot
// Find a value in right side smaller
// than pivot
do
j = j - 1
while arr[i] > pivot
if i >= j then
return j
swap arr[i] with arr[j]
WEEK 4:-
PriorityQueues:-
–
binary tree: empty or node with links to left and right binary trees
– complete B tree: perfectly balanced, except for bottom level
– complete B tree height h: lg N (h increases when N is a power of 2)
Binary heap:-
The items are stored in an array such that each key is guaranteed to be larger
than (or equal to) the keys at two other specific positions.
parent's key >= children's keys
The
parent of the node in position k is in position k/2; and, conversely, the two
children of the node in position k are in positions 2k and 2k + 1
To move up the tree from a[k] we set k to k/2; to move down the tree we set k
to 2*k or 2*k+1
– Largest key is a[1], root of b.tree
if
child becomes larger than parent then:
– swap child, parent; repeat up until in order
private
void swim(int k) {
while (k > 1 && less(k/2,
k)) {
exch(k, k/2);
k = k/2;
}
}
Insert:
add to end, swim up: at most 1+lg N compares
pq[++N] = x, swim(N)
–
parent becomes smaller than child
private
void sink(int k)
while (2*k <= N) {
int j = 2*k;
if (j < N && less(j,
j+1)) j++;
if (!less(k, j))
break;
exch(k, j);
k = j;
}
delMax:
swap root, tail; sink root down
max = pq[1], swap(1, N--), sink(1);
Binary Search Trees:-
– A BST is a binary tree in symmetric order
symmetric order:- The node is larger than its left element and smaller than its right element.
– each node (key, value, left right): empty or BST (each node is a root of a subtree)
– symmetric order: every node key is: larger than in left, smaller than in right
BST search
private Value get(Node x, Key key)
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) return get(x.left, key);
else if (cmp > 0) return get(x.right, key);
else return x.val;
BST insert: search for key, 2 cases: key in tree: reset value or: add new node
private Node put(Node x, Key key, Value val)
if (x == null) return new Node(key, val, 1);
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = put(x.left, key, val);
else if (cmp > 0) x.right = put(x.right, key, val);
else x.val = val;
x.N = 1 + size(x.left) + size(x.right); // update tree size
return x;
Week 5:-
As you can see from above table,we need do balance the tree somehow to reach the goal of logN for all operations.
Week 6:-
The performance of the map can be increased if we use array instead of othr data structures.we need a function which can convert the key into index and also reduce the collision.This function is called Hash function.
But the collision occurs when the Hash function returns same hash value(index) for different keys.
Avoid Collision:
1. Seperate Chaining(build, for each of the M array indices, a linked list of the key-value pairs whose keys hash to that index)
2. Open Addressing.
a. linear probing
hi(X) = (Hash(X)+i) % size
if h0 = (Hash(X)+0) % size if full will try for h1
if h1 = (Hash(X)+1) % size if full will try for h2
b. quadratic probing
c. Double probing
Tries
Tries stands for re
TRIEval.
Used in string prefix finding etc
Takeaways:
The key takeaways
for me after completing the algorithms part 1 course is that:-
- I got to know, how to build
the algorithms and progressively improve it.
- I got to know about many
algorithms of sorting and trees.
- I gained lot of confidence
after working on percolation problem,At one stage I gave up learning the
algorithms course as I was unable to understand the code at all.But now I
am able to understand and solve the problems.
- I spent lot of time in
understanding the Asymptotic notions but only after taking this course I
am able to apply those concepts and analyze in real time.
- Some of the java concepts
like generics,Iterators,Comparators were very useful
- After solving some of the
geometric problems,I am awe struck by the wide spectrum that algorithms
cover.
