Notes on Algorithms, Part I by Princeton University

After postponing for 3-6 months finally I took Algorithms 1 course in June-july 2017.

Notes:-

Week 1:-

Problem Statement:- percolation.pdf

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.

This video helped me a lot in understanding the problem:- https://www.youtube.com/watch?v=BiSKunzrC1g

Github link:- week1

Note:- Please use the below code for reference only,else it will spoil the fun:-)

Percolation problem:-     github link

PercolationStats :-            github link

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 reTRIEval.

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.