Algos.txt

                  ALGORITHMS PART 1 (PRINCETON)
                  =============================

Dynamic Programming Problems:
1 Sequence Alignment
2 Tower of Hannoi Puzzle
3 Egg dropping puzzle
4 Matrix chain multiplication
5

References:
[1] http://en.wikipedia.org/wiki/Dynamic_programming
[2] http://www.quora.com/Programming-Interviews/What-are-the-top-10-most-popular-dynamic-programming-problems-among-interviewers




- Dynamic Connectivity Problem (How many connected components exist)
- Quick Find
          // algo
          id[component] = component
          union(p, q):
                id[p] = id[q]
                each element that has id[p] has to be changed to id[q]
                (this is O(N) step)
          connected(p, q):
                return (id[p] == id[q])

        Algo          Initialize         Union       Find
        -------------------------------------------------
     Quick-Find            N               N           1

- Problem: Union is expensive. N^2 time for N union's
- Too slow algo.

- Quick Union: Lazy approach to above problem.
   Data Structure
   - Integer array id[] of size N
   - Interpretation: id[i] is parent of i
   - Root of i is id[id[...id[i] ...]]] - keep going until there is no
     change. Algo ensures no cycles.

   Find():
        - Check if p and q have same root?
   Union():
        - Merge components containing p and q, set the id of p's root to
          id of q's root. Only one value changes.

   // Algo
   private int root(int i)
   {
        while(i != id[i])
                i = id[i];
        return i;
   }

   public bool connected(int p, int q)
   {
        return root(p) == root(q);
   }

   public void union(int p, int q)
   {
        int pr = root(p);
        int qr = root(q);

        id[pr] = qr;
   }

        Algo          Initialize         Union       Find
        -------------------------------------------------
     Quick-Find            N               N           1
     Quick-Union           N               N*          1

     * - includes cost of finding roots

- Quick Union with Weighting (Improvement #1)
  - Modify QU to avoid tall trees
  - Keep track of size of each tree (# of objects)
  - Balance by linking root of smaller tree to root of larger tree.

  // Algo
  - Maintain sz[i] = size of tree rooted at i
  Find()/Connected(p, q):
        return root(p) == root(q);

  QUwithWeight(p, q)
  {
        int pr = root(p);
        int qr = root(q);

        if(pr == qr) return; // same tree

        if(sz[pr] < sz[qr])
                id[pr] = qr;
                sz[qr] += sz[pr];
        else
                id[qr] = pr;
                sz[pr] += sz[qr];
  }

  - Depth of each node is atmost lg N (base 2 log)

        Algo          Initialize         Union       Find/Connected
        -------------------------------------------------
     Quick-Find            N               N           1
     Quick-Union           N               N*          1
     Weighted QU           N              lg N        lg N



- Weighted QU (Improvement #2): Path compression. Flatten the tree.
  - After computing root of p, set id of each examined node to point to
    that root.
  - Starting from empty data structure, any sequence of M union-find ops
    on N objects makes <= c (N + M lg* N) array accesses.
    lg* N = 5 for 2^65536, which is pretty much constant.
  - Therefore, almost linear time algo.

              Algo              worst-cast time
        -------------------------------------------------
          Quick-Find            MN
          Quick-Union           MN
          Weighted QU           N + Mlog N
     QU + Path Compression      N + Mlog N
     Weighted QU + Path Comp    N + Mlg *N

        M union-find ops on set of N objects

Example: 10^9 union-finds with 10^9 objects
  - WQUPC reduces time from 30 years to 6 seconds.


Applications:
  - Percolation
  - Games (Go, Hex)

Percolation Problem Modeling
- How to check whether an NxN system percolates?
  1 Create an object for each site and name them 0 to N^2-1
  2 Sites are in same component if connected by open sites.
  3 Percolates iff any site on bottom row is connected to site on top row.
  This can be brute force and N^2 calls to connected() routine.
  4. Instead, create a virtual site at top & bottom that is connected to
  all nodes at top row and bottom row respectively.


Stacks & Queues
--------

Stacks: LIFO principle
-------
- push(), pop(), is_empty(), size() are main APIs
- Can be implemented using Linked Lists, Arrays.
- Arrays are very fast implementation
    * resizing problem is fundamental to Arrays

- How to grow an array?
    * "Repeated Doubling" - new array of double size. Copy elements.
- How to shrink the array?
    * Half the array when 1/4 full. Otherwise can run in to "Thrashing"


Queue: FIFO principle
-------
- enqueue(), dequeue(), is_empty(), size() etc
- Linked Lists, Arrays (though tricky to implement)




SUM in an Array Algos:
-------
2SUM/3SUM - Given N distinct integers, how many triples (or doubles) sum
to zero (or a particular number).

// Algos
- Brute Force - N^3

BinarySearch of an Array
--------
// Code - from lecture (non-recursive)

   public static int binarySearch(int[] a, int key)
   {
        int lo = 0, hi = a.length-1;

        while(lo <= hi)
        {
                int mid = lo + (hi-lo)/2;
                if      (key < a[mid]) hi = mid-1;
                else if (key > a[mid]) lo = mid+1;
                else return mid;
        }

        return -1;
   }

- An (N^2)log N algo for 3-SUM
  - Sort N distinct number (Nlog N)
  - For each pair of numbers in a[i] and a[j], binary search for
    negative (a[i]+a[j]) - this is (N^2)log N step.
  - Total: (N^2)log N + (Nlog N)


Memory Usage for Primitive Data Types in Java
---------

          Type           Bytes
          --------------------
        boolean            1
          byte             1
          char             2
          int              4
          float            4
          long             8
         double            8
         char[]           2N + 24
         int[]            4N + 24
       double[]           8N + 24

- Object overhead in Java = 16 bytes
- Reference overhead = 8 bytes
- Memory alignment = Each object uses multiples of 8 (on 64 bit machine)




SORTING
========
Selection Sort:
-------
- In iteration i, find index of smallest remaining entry (call it `min`)
- Swap a[i] and a[min].

Invariants:
-------
- No entry to right of i is smaller than elements less than i.

  // Code
  public static void selectionSort(Comparable[] a)
  {
        int N = a.length;
        for (int i=0; i<N; i++)
        {
                int min = i;
                for (int j=i+1; j<N; j++)
                {
                        if(less(a[j], a[min])
                                min = j;
                }
                exch(a, i, min);
         }
   }

- ~(N^2)/2 compares and N exchanges.
- Quadratic time input, even if input is sorted.


Insertion Sort:
-------
- In iteration i, swap a[i] with each larger entry to its left.
- All entries to left of i is sorted.

  // Code
  public static void insertionSort(Comparable[] a)
  {
        int N = a.length;
        for (int i=0; i<N; i++)
                for (int j=i; j>0; j--)
                        if (less(a[j], a[j-1]))
                                exch(a, j, j-1)
                        else
                                break;
  }

- On average, ~1/4(N^2) compares and ~1/4(N^2) exchanges.
- Best case: If array is in sorted (say, ascending order), only N-1
  compares and 0 exchanges.
- Worst case: If array is in descending order, ~1/2(N^2) compares and
  ~1/2(N^2) exchanges.

Insertion Sort: Partially-Sorted Array
-------
Def: An inversion is a pair of keys that are out of order.
         A E E L M O T R X P S

         There are 6 inversions in above array.
         T-R T-P T-S R-P X-P X-S

Def: An array is partially sorted if the number of inversions is <= cN
(some constant times N).

- For partially sorted arrays, insertion sort runs in linear time because
  number of exchanges = number of inversions.
  number of compares = number of exchanges + (N-1)



Shell Sort:
--------
Idea: Move entries more than one position at a time by h-sorting array.

An h-sorted array is h interleaved sorted subsequence.

- How to h-sort an array? Insertion sort, with stride length of h
- Why insertion sort?
  - Big increments = small subarrays.
  - Small increments = nearly in order (or partially sorted).

- Worst case: number of compares is O(N^(3/2)) for 3x+1 increments.
- Why are we interested in shellsort?
  - Useful in practice.
  - Fast unless array size is huge.
  - Tiny, fixed footprint of code (used in embedded sys).
  - Hardware sort prototype.


Shuffling: How do you shuffle a deck of cards?
-------
- Generate a random number for each card and sort them. But there is a
  cost of sorting the deck.
- Can we do better? Yes! Knuth Shuffle.

Knuth Shuffle:
-------
- In iteration i, pick integer r between 0 and i uniformly at random.
- Swap a[i] and a[r].
- This is linear time shuffling algo, making use of random number.

  // Code
  public void knuthShuffle(Object[] a)
  {
        int N = a.length;
        for(int i=0; i<N; i++)
        {
                int r = StdRandom.uniform(i+1);
                exch(a, i, r);
        }
  }
- Bug: Choosing to swap a random number between 0 and N-1. It is not
  uniformly random. However, choosing between i and N-1 will work.


Convex Hull:
-------
Smallest perimeter fence enclosing all points in a plane.

Mechanical Algo: Hammer nails on points and stretch elastic rubber band around
points.

Convex Hull Applications:
-----------
Robot Motion Planning: Path from point s to t and an obstacle in between.
    - If there's no direct, straight path between s and t, then it's along the
      perimeter of Convex Hull including points s and t.

Farthest Pair Problem: Given N points in plane, find a pair of points with
largest Euclidean distance between them.
    - Those points are on Convex Hull.


Graham Scan: To determine Convex Hull
------
- Choose point p with smallest y-coordinate
- Sort points by polar angle with p
- Consider points in order; discard unless it create a ccw turn.
- There's lot of implementation challenges to Graham Scan
    - How to find point p with smallest y-coordinate?
    - How to sort points by polar angle w.r.t p?
    - How to determine p1->p2->p3 is CCW direction?
    - How to sort efficiently?

Implementing CCW
------
Given 3 points a, b and c, is a->b->c a CCW turn?
    - Determinant (or cross product) gives 2x signed area of planar triangle


                            | ax ay 1 |
        2 x Area(a,b,c) =   | bx by 1 | = (bx-ax)(cy-ay) - (by-ay)(cx-ax)
                            | cx cy 1 |

- If signed area > 0, then a->b->c is CCW
- If signed area < 0, then a->b->c is CW
- If signed area = 0, then a->b->c is collinear (straight line)



Mergesort:
Split an input array in to two halves recursively, sort each one and merge

Runtime: O(N lgN)
Memory: O(N) as it uses auxiliary array

- A sorting algo is considered in-place if it uses <= c(lgN) extra memory, for
  a constant c.
  Ex: Insertion, Shell, Selection sorts.

Practical Improvements to Mergesort:
------
- Too much overhead for small arrays (or subarrays within a large array).
- Cutoff to insertion sort is ~7 items
- Biggest item in first half <= smallest item in second half. Stop.


Bottom-Up Mergesort:
------
- Pass through array, merging subarrays of size 1.
- Repeat for subarrays of size 2, 4, 8, 16, ...
- Uses O(N) auxiliary space
- Runs O(N lgN) time
- Overhead is much smaller. Easier to code.

    void merge(int arr, int lo, int mid, int hi) {/* standard */}
    void sort(int arr)
        for (int sz=1; sz<N; sz = sz+sz)
            for (int lo=0; lo=N-sz; lo+=sz+sz)
                merge(arr, lo, lo+sz-1, min(lo+sz+sz-1, N-1))


Stability of Sorting Algos:
------
Stable sort is one that preserves relative position of items with equal keys.
- Insertion and Mergesort are stable. Shell and Selection are not.




Quicksort:
------
- Shuffle the array
- Partition so that, for some j
    * entry a[j] is in place
    * no larger entry to the left of j
    * no smaller entry to the right of j
- Sort each piece recursively

Phase 1: Repeat until i and j pointer cross.
    - Scan i from left to right so long as a[i] < a[lo]
    - Scan j from right to left so long as a[j] > a[lo]
    - Exchange a[i] with a[j]

Phase 2: When pointers cross
    - Exchane a[lo] with a[j]

********* array is partitioned at this point *******

Partition Code:
------
int partition(int a[], int lo, int hi)
{
    int i = lo, j = hi+1;   /* 1st elem is partitioning elem */
    while (true)
    {
        while (less(a[++i], a[lo]))     /* find item on left */
            if (i == hi) break;

        while (less(a[lo], a[--j]))     /* find item on right */
            if (j == lo) break;

        if (i >= j) break;          /* check if pointers cross */
        exch(a, i, j);              /* swap */
    }

    exch(a, lo, j);
    return j;   /* index of partition item which is in place */
}

void Quicksort(int a[], int lo ,int hi)
{
    /* shuffle the array for performance gaurantee */

    if (hi <= lo)   return;
    int j = partition(a, lo, hi); /* j elem is in place now */
    Quicksort(a, lo, j-1);
    Quicksort(a, j+1, hi);
}

Worst Case: O(N^2)
Average Case: ~1.39(N lgN) --> O(N lgN)


Selection Problem: Given an array of N items, find the Kth largest.
------
Partition array so that:
- Entry a[j] is in place
- No larger entry to left of j
- No smaller entry to the right of j
- Repeat in one subarray, depending on j
- Done when j == k

void select(int a[], int k)
{
    /* shuffle the array */

    int lo = 0, hi = a.length - 1;

    while (hi > lo)
    {
        int j = partition(a, lo, hi);
        if      (j < k) lo = j + 1;
        else if (j > k) hi = j - 1;
        else    return a[k];
    }

    return a[k];
}

Average: Linear time
Worst Case: Quadratic time, but with random shuffle, very rare


Dijkstra 3-Way Partitioning. (AKA 3-way Quicksort)
-----
Goal: Partition an array in to 3 parts so that:

    +----------------------------------------------+
    |  < V     |      = V                |   > V   |
    +----------------------------------------------+

where V is the partitioning element.


Priority Queues:
---------------
Queues with elements having priorities. Usually implemented using Heaps.

Challenge: Find largest M items in a stream of N items.
    - Many applications
Constraint: Not enough memory to store N items.

Solution:
- Maintain a Min PQ, maintains M lowest number on front of PQ.

while (input)
    PQ.insert(input);
    if (PQ.size() > M)  // PQ contains largest M items
        PQ.delMin();    // Min in the PQ is front of PQ

Basic PQ implementations:
------
    Algo            Time        Space
    ---------------------------------
    sort            N lgN       N
    elementary PQ   M N         M
    Binary Heap     N lgM       M
    Best            N           M

PQ implementations
---
- Unordered Array: Keep inserting as elems come in. Search when required.
- Ordered Array: Insert elems as they come in. Shift elems around to maintain
  order.
- Linked List:

Goal of PQ implementation: lg N insert, lg N max, lg N delete

Practical PQ Implementation: Complete binary tree
------
Array Representation:
- Keys are elems of array
- Parent's key no smaller than children's keys
- Indices start at 1
- Take nodes in level order
- No explicit links needed

    a[] = T S R P N O A E I H G

                                T
                        S                   R
                    P       N           O       A
                  E   I   H   G


- Largest key is a[1], which is root of binary tree
- Parent of node at k is at k/2
- Children of node at k are at 2k and 2k+1

Scenario1: Child's key becomes larger than it's parent's key
- Exchange key in child with parent
- Repeat until heap order is restored

void swim(int k)
{
    while (k>1 && less(k/2, k))
    {
        exch(k, k/2);
        k = k/2;
    }
}

Insertion: Add node at end and swim up
Cost: At most 1+lg N compares

void insert(Key x)
{
    pq[++N] = x;
    swim(N);
}

Scenario2: Parent's key becomes smaller than one or both of it's children.
- Exchange key in parent with key in larger child
- Repeat until heap order is restored

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;
    }
}

Delete Max: Exchange root with node at end, then sink it down
Cost: At most 2*lgN compares

Key delMax()
{
    Key max = pq[1];
    exch(1, N--);
    sink(1);
    pq[N+1] = null;
    return max;
}


Heapsort
--------
- Create max-heap with all N keys
- Repeatedly remove the max key
- In-place sorting algo with N lgN worst case

    Mergesort: takes linear extra space
    Quicksort: quadratic worst case
    Heapsort: gauranteed N lgN worst case

Disadvantages of Heapsort
-----
- Makes poor use of cache memory. In modern systems, caching is very
  important. Lot of references in array.
- Not stable.


        Summary of Sorting Algorithms
        =============================
            inplace?  stable?  worst  average  best     remarks

Selection   Yes                N^2/2  N^2/2    N^2/2    N exchanges

Insertion   Yes       Yes      N^2/2  N^2/4    N        use for small or
                                                        partially ordered array

Shell       Yes                ??     ??       N        tight code

Quick       Yes                N^2/2  2N lgN   N lgN    fastest in practice

3-way Quick Yes                N^2/2  2N lgN   N        improves Quicksort
                                                        when duplicate keys are
                                                        present

Merge                 Yes      N lgN  N lgN    N lgN    N lgN gaurantee, stable

Heap        Yes                2N lgN 2N lgN   N lgN    N lgN gaurantee, in-place

????        Yes       Yes       N lgN  N lgN   N lgN    N lgN gaurantee, in-place



N body simulation
------
- Application of PQ
- Uses Hard disc model
    + Moving particles interact via elastic collisions with each other and
      walls.
    + Each particle is a disc with known position, velocity, mass and radius.
    + No other forces.

Event-driven Simulation
-------
Problem: To find when two bodies collide using brute force is hard problem
(Quadratic time).
Solution: Event-Driven Simulation

- Change state only when something happens
- Between collisions, particles move in straight-line trajectories
- Focus only on (predicted) times when collisions occur
- Maintain PQ of collision events, prioritize by time
- Remove the min, get next collision


Collision Prediction: Given position, velocity and radius of particle, when
will it collide next with a wall or another particle?

Collision Resolution: If collision occurs, update colliding particle(s)
according to laws of elastic collisions.


Todo: Watch video: Event Driven simulation



Symbol Tables
-------------
Key-Value pair abstraction, with two main operations
- Insert a value with specified key
- Given a key, search for the corresponding value

Eg: DNS lookup, given URL, provide IP and vice versa

Data Struct: Unordered Linked List of Key-Value pairs.
Search: Scan through all keys until you find a match.
Insert: Search. If no match, add to front.

Data Struct: Maintain an ordered array of KV pairs. Use binary search to find
keys.
Problem: Insert - need to shift all greater keys over.

Binary Search Trees (BSTs)
---------------
- Binary tree in symmetric order.
    + Symmetric means: Every node's key is larger than all keys in it's left
      subtree and smaller than all keys in its right subtree.

- There's 1-1 correspondance between BSTs and Quicksort partitioning

How to find following in BSTs
------
Min:    Smallest key in table

Max:    Largest key in table

Floor:  Largest key <= to a given key

Ceiling: Smallest key >= to a given key
// floor and ceiling isn't straightforward

Count:  Store # of nodes in the subtree rooted at that node. To
        implement size(), return count at the root

Rank:   How many keys < k?
        //Easy recursive algo

Inorder Traversal: Keys traversed in ascending order
    + Traverse left subtree
    + Enqueue key
    + Traverse right subtree

Deletion in BST: Hibbard Deletion

Deleting a node in BSTs

Case 1: Deleting node N has no subtrees.
Case 2: Deleting node N has 1 subtree.
                parent(child(N)) = parent(N)
Case 3: Deleting node N has 2 subtrees
                + find successor node X to N (smallest node > N)
                + Replace N with X and free N
                + X is minimum node to right subtree of N

- Why is successor node X chosen and not predecessor? No real reason.

Disadvantages:
- Tree becomes unbalanced after repeated deletion/addition. Choosing
  predecessor and successor randomly doesn't solve the problem
- The height of the tree becomes sqrt(N) instead of lgN
- Long standing open problem



Red-Black BST: Gaurantees logarithmic performance
--------

2-3 Trees
---------
- Allow 1 or 2 keys per node
- 2-node: 1 key and 2 children
- 3-node: 2 keys and 3 children

Perfect Balance: Every path from root to null link has same length

Symmetric Order: Inorder traversal yields keys in ascending order

Insert:
Case 1: Insert in to a 2-node at bottom
Case 2: Insert in to a 3-node at bottom. More work.
        + Add new key to 3-node to create temporary 4 node
        + Move middle key in 4 node in to parent, along with any child
        // See video for clarity

Tree height:
------
Worst Case: lgN     //all 2-nodes
Best Case: lg_3N ~ 0.631 lgN    // all 3-nodes. Base 3 log
Between 12 and 20 for a million nodes
Between 18 and 30 for a billion nodes

- Gauranteed logarithmic performnace for search and insert


//TODO: Watch this video again. Very detailed implementation of RB BST

Red-Black Trees (left-leaning RB tree)
---------------
- RB Trees can be represent using 2-3 tree
- Take the largest elem in a 3-node and make it root, with smaller elem on
  left subtree (hence left-leaning RB BSTs)
- Call this link as Red link
- Black links are those pointing to a 2-node

- Vice Versa is true. Given a BST, there's a direct correspondance to RB tree.

A BST such that:
- No node has 2 red links connected to it
- Every path from root to null link has same number of black links
- Red links lean left


- Search in RB BST: Same as BST. Most other operations are same.
- Change w.r.t BST, have a 'color' field to indicate left link (RED) and right
  link (BLACK)

Applications:
----
- java.util.TreeMap, TreeSet use RB trees
- C++ STIL: map, multimap, multiset
- Linux kernel: CFS, libux/rbtree.h

// TODO: Watch video

B-Trees
-------
- Generalized version of 2-3 trees

- Variants: B+ tree, B* tree, B# tree ...

Applications:
----
- Windows NTFS
- Mac: HFS, HFS+
- Linux: ReiserFS, XFS, Ext3FS, JFS
- Databases: Oracle, DB2, INGRES, SQL, PostgreSQL



Geometric Applications of Binary Search Trees (BST)
---------

1d Range Search
---------------
Problems:
[1] How many points in a plane lie within a rectangle
[2] If we have set of rectangles, how many are intersecting or how many of
them are intersecting

- Geometric objects intersections.
- Finding points in a 2d range
- Intersections of orthogonal rectangles.
- Many applications.


Solution: Binary Search Trees (and extensions)

Operations:
- Insert KV pairs in to Symbol Table
- Search for key k
- Delete key k
- Range search: find all keys between k1 and k2
- Range count: number of keys between k1 and k2


Application: Database queries

Geometric Interpretation:
- Keys are points on a line
- Find/count points in a given interval in 1-dimension (1d).

    **  * * *****    * * *  **  * **   * *
         ^                  ^
         S                  E

- How many points/keys between S and E?


Implementation Costs
----


       DS           insert       range count         range search
Unordered Array        1              N                    N
Ordered Array          N            log N               R + log N
Goal                 log N          log N               R + log N

N = number of keys
R = number of keys that match


Implementation
----
- Keep a rank(node) function that counts # of keys less than that node in
  a BST.
- Range(low, high) = rank(high) - rank(low) [+1 depending on high/low are
  part of the query]

                                S 6
                               / \
                              /   X 7
                             E 2
                            / \
                         0 A   \
                            \   \
                           1 C   R 5
                                /
                               H 3
                                \
                                 M 4

    public int size(Key lo, Key hi) {
        if (contains(hi))   return rank(hi) - rank(lo) + 1;
        else                return rank(hi) - rank(lo);
    }

- Num of keys between E and S?


// Algo: Find all keys between lo and hi
- Recursively find all keys in left subtree.
- Check key in current node.
- Recursively find all keys in right subtree.

- Run time is R + logN

Line Segment Intersection Search
-------
// Algo
- Sweep vertical line from left to right
- x-coordinates define events. Put x-coordinates in a PQ (or sort) - N log N
- h-line (left endpoint): insert y-coord in to BST - N log N
- h-line (right endpoint): remove y-coord from BST - N log N
- v-line: do a 1d-range search in BST for y-range - R + N log N

Bottom Line: Sweep line reduces 2d orthogonal line segment intersection search
to 1D range search.

2D Orthogonal Range Search
----
- Insert 2D key
- Delete a 2D key
- Search for a 2D key

Problem:
---
- Range Search: Find all keys that lie in a 2D range
- Range Count: Number of keys that lie in a 2D range



Line Sweep Algos
-------
Applications:
- Closest Pair of points.
- Line segment intersections.
- Area of union of rectangles.
- Convex hull.

Kd-Trees
--------
Extension of 1d-range
- Operations: Insert a 2d key; Delete a 2d key; Search for a 2d key
- Range search: find all keys that lie in a 2d range.
- Range count: # of keys that lie in a 2d range.

Geometric Interpretation:
- Keys are point in a plane.
- Find/count points in a given h-v rectangle.

Applications:
- Networking, Circuit Design, Databases.

Grid Implementation
--------
- Divide space in to MxN squares/grids.
- Create a list of points contained in each square.
- Use 2d array to directly index relevant square.
- Insert: add(x,y) to list for corresponding square.
- Range Search: Examine only squares that intersect 2d range query.

Space-Time Tradeoff:
---------
- Space: M^2 + N
- Time: 1 + N/(M^2) per square examined, on average

Choose grid square size to tune performance
---------
- Too small: wastes space.
- Too large: too many points per square.
- Rule of thumb: sqrt(N) by sqrt(N) grid.

Running Time
---------
- Initialize DS: N
- Insert point: 1
- Range search: 1 per point in range.

Clustering
--------
- Grid implementation is poor.
- Other options:
  2d Tree
  Quadtree
  BSP Tree


2d Tree
-------
// Algo
- Recursively partition plane in to two half planes (alternating between
  horizontal & vertival partitions).
- All points to left of a vertical will be in left sub-tree and vice
  versa.
- Similarly for horizontal partition.
- Build a BST in above fashion.


Application
-------
- Given a set of points in a plane and a rectangle, find all the points
  within that rectangle.
- Nearest neighbor search.
- Find all nodes in a plane that are at K distance from a given node.



Interval Search Problem
--------
- Data structure to hold set of overlapping intervals. Operations allowed:
    * Insert an interval (lo, hi)
    * Search an interval (lo, hi)
    * Delete an interval (lo, hi)
    * Query: Given (lo, hi), find one or all intervals that intersects with
      (lo, hi)


Rectangle Intersection Problem: Orthogonal Rectangles
----
- Modification of Sweep Line algo
- Sweep vertical line from left to right
    + x-coord of left and right endpoints define events. Put them on a PQ (or
      sort them) - N log N
    + When Sweep Line meets rectangle, insert y-interval in to interval search
      tree - N log N
    + When Sweep Line leaves rectangle, remove y-interval from search tree
        - N log N
    + Interval searches for y-intervals - (N log N + R log N)


Geometric Applications of BSTs
==============================

        Problem             Example                 Solution
    ----------------------------------------------------------------
  1d range search       ** ** * **** *  *           BST
                            ^     ^


                           |    --------            Sweep Line reduces to
  2d orthogonal line    ---+---- |  ------              1d range search
segment intersection       |     |      |
search                     |  ---+---   |
                                 |      |



                        *  *    *
                          *  *   *  *
    Kd range search    *   * +-----+*               Kd tree
                         *   |*   *|  *
                       * **  |  ** |*  *
                         *   |     | **
                        *   *+-----+ *
                          *   **  *


                        |-----|  |-------------|
  1d interval search       |----|    |----|   |-----|   Interval search tree




                          +------+
                          |      |         +-+
                          |    +--------+  | |
  2d orthogonal rectangle +----|-+      |  | |      Sweep line reduces to 1d
intersection search            +--------+  | |      interval search problem
                                           | |
                              +-------------------+
                              |            | |    |
                              +-------------------+
                                           | |
                                           +-+




Hashing:
--------
- All Java classes inherit a method hashCode(), which returns a 32-bit int.
- Requirement: In Java, x.equals(y) then x.hashCode() == y.hashCode()
- Highly desirable: If !x.equals(y) then x.hashCode() != y.hashCode()
- Default implementation: Memory address of x

- Java library implementations

    public final class Integer
    {
        private final int value;
        ...
        ...
        public int hashCode()
        {   return value;   }
    }

    public final class Boolean
    {
        private final boolean value;
        ...
        ...
        public int hashCode()
        {
            if (value)  return 1231;
            else        return 1237;
        }
    }

    public final class Double
    {
        private final double value;
        ...
        ...
        public int hashCode()
        {
            long bits = doubleToLongBits(value);
            return (int) (bits ^ (bits >>> 32));
        }
    }                           ^
                                |
                                |
                                |
        Convert to IEEE 64-bit representation. XOR most significant 32-bits
        with least significant 32-bits

- For String, Horner's method to hash string is used.

- Idea is to involve all char's in the String (or all bits in Double) for
  hashing.


Uniform Hashing: Each key is equally likely to hash to an integer between 0
and M-1

Bins and Balls: Throw balls uniformly at random in to M bins.

Birthday Problem: Expect 2 balls in same bin after ~sqrt(pi * M/2) tosses
Coupon Collector Problem: Expect every bin has >=1 ball after ~M tosses


Collisions: (a) Separate Chaining (b) Linear Probing (Open Addressing)
-----------
Separate Chaining: Linked Lists
- Hash: map key to int i between 0 and M-1
- Insert: put at front of ith chain (if not already there)
- Search: need to search only ith chain

Linear Probing (Open Addressing)
- Hash: Map key to int i between 0 and M-1
- Insert: Put at idx i if free; if not try i+1, i+2 ...
- Search: Same way as Insert till you hit empty position or wrap around
- Array size M must be greater than number of K-V pairs

Knuth's Parking Problem:
    Model: Cars arrive at one-way street with M parking spaces. Each desires a
    random space i: if space i is taken, try i+1, i+2 ...

    Q: What's mean displacement of a car?
    Ans: With M/2 (half-full), mean displacement is ~3/2
         If full, with M cars, mean displacement is ~sqrt(pi * M/8)


Suggested array size M and N keys:
    M too large: too many empty array entries
    M too small: search time blows up
    Typical choice: alpha = N/M ==> approx 1/2
    * With above choice, avg probes for search hit ~3/2 and avg probes for
    * search miss is ~5/2

Many variants of Hashing:
- Two-probe hashing: Has to two positions. Insert key in shorter of 2 chains
- Double hashing: Linear probing but skip variable amount, not just 1
- Cuckoo hashing: Hash key to 2 positions. Insert key into either. If
  occupied, reinsert displaced key into its alternative position


Applications of Symbol Tables (Hashing)
---------
Sets: A collection of distinct keys
Dictionary Lookups







                  ALGORITHMS PART 2 (PRINCETON)
                  =============================

String Problems:
-------
Longest palindrome in a string.
  - Manacher's algorithm is fastest: O(N) running and O(N) space.


Undirected Graphs
--------
Graph: Set of "vertices" connected by pairwise "edges"

Terminology:
    Path: Sequence of vertices connected by edges.
    Cycle: Path whose first and last vertices are the same.
    Connected Components: Subset of graph

Graph Probs:
---------
PATH: Is there a path between `s` and `t`
SHORTEST PATH:

CYCLE: Is there a cycle in graph?
EULER TOUR: Is there a cycle that uses each edge exactly once?
HAMILTON TOUR: Is there a cycle that uses each vertex exactly once?

CONNECTIVITY: Is there a way to connect all of the vertices?
MST: Best way to connect all vertices?
BICONNECTIVITY: Vertex whose removal disconnects the graph?

PLANARITY: Draw a graph in a plane with no crossing edges?
GRAPH ISOMORPHISM: Do two adjacency lists represent the same graph?

Graph Representation:
-----------
- Adjacency-Matrix with 0 indicating no connection, 1 indicating its
  connected. Not scalable (V^2 size).
- Adjacency-List: Each vertex has a list of adjacency nodes/vertices. Most
  commonly used representation.


        +---+      +---+      +---+      +---+
        |   | ---> |   | ---> |   | ---> |   |
        +---+      +---+      +---+      +---+
        +---+      +---+
        |   | ---> |   |
        +---+      +---+
        +---+      +---+      +---+
        |   | ---> |   | ---> |   |
        +---+      +---+      +---+
        +---+      +---+      +---+      +---+
        |   | ---> |   | ---> |   | ---> |   |
        +---+      +---+      +---+      +---+
        |   |
        +---+


- In real world, graphs have lots of vertices but small degree (fewer
  edges) - Sparse graphs.


DEPTH FIRST SEARCH [DFS]
-------------
/* A very concise Python implementation
https://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/
*/
- Tremaux Maze exploration algo:
     - Unroll a ball of string behind you.
     - Mark each visited intersection and each visited passage.
     - Retrace steps when no visited options.

  DFS (vertex v)   // algo
     mark v as visited
     recursively visit all unmarked vertices adjacent to v

Algo:
- Use recursion
- Mark each visited vertex (and keep track of edge taken to visit it)
- Return when no visited options

Data Structs:
- boolean marked[] - to mark visited vertices
- int edgeTo[] to keep track of paths. (edgeTo[w] == v) means that edge v-w
  taken to visit w for first time


public class DepthFirstPaths
{
    private boolean[] marked;
    private int[] edgeTo;
    private int s;  // root??

    public DepthFirstPaths(Graph G, int s)
    {
        ...
        dfs(G,s);
    }

    private void dfs(Graph G, int v)
    {
        marked[v] = true;
        for (int w : G.adj(v))
            if (!marked[w])
            {
                dfs(G, w);
                edgeTo[w] = v;
            }
    }
}



BREADTH FIRST SEARCH [BFS]
--------------
   BFS (vertex v)  // rough algo
      - add v to FIFO Q & mark as visited
       repeat until Q is empty
          - remove least recently added vertex v
          - add each unvisited adjacent vertex of v to Q and mark them as
            visited.

- BFS computes Shortest Path (fewest # of edges) from s to all other vertices
  in graph in time proportional to E+V

DFS: Put unvisited vertices on Stack
BFS: Put univisited vertices on Queues

Intuition: BFS examines vertices in increasing distance from s.


Connected Components
--------------
Def: Vertices v & w are connected if there is a path between them
Goal: Preprocess graph to answer queries: is v connected to w? Provide this in
constant time
Def: A connected component is a maximal set of vertices in a graph

- Similar to Union-Find problem but not exactly same.
- DFS can be used.

Practical Use:
- STD like health issues.
- Flood Fill in paint softwares.

Algo:
- Use DFS
- Instead of edgeTo[], use a cc[] that's slightly different. It has the
  connected component number instead of it's parent node number



Graph Challenges
-------------
1) Is a graph bipartite? Can graph be divided in to 2 set of
vertices each vertex in one set connecting to another in other set?
  - DFS can solve this prob

2) Does a graph have cycle?
  - DFS can solve this prob

3) Euler Tour: Given a graph, is there a cycle that uses each edge exactly
once?
  - Yes, iff connected and all vertices have even degree

4) TSP/Hamilton Tour: Find a cycle that visits each vertex only once
  - NP-complete problem

5) Are two graphs identical (except vertex names)? Graph Isomorphism
Problem:
  - No one knows how to classify this problem.

6) Layout a graph in a plane without crossing edges.
  - There is a linear-time DFS-based planarity algo discovered by Tarjan
    in 1970s (too complicated for most practitioners).



Directed Graphs (Digraphs)
-----------
- Set of vertices connected pairwise by directed edges.
- in-degree: number of edges pointing to a vertex.
- out-degree: number of edges pointing away from a vertex.

Typical Problems
-----------
- Is there a directed path from s to t
- What is shortest directed path from s to t
- Can you draw a graph so that all edges point upwards?
- Combination circuits
- Implication graphs
... many more



Digraph Search - DFS can be used
----------
- Reachability Application
    - Program control flow analysis (static analysis tools).
    - All vertices reachable from a node s

- Garbage Collection - Mark & Sweep algos use Digraphs.
  - Mark all reachable objects.
  - Sweep objects (garbage collect) if it is unmarked. Mark-Sweep algo

BFS on Digraphs
    - can be used to get Shortest Path from s to t in a Digraph.

- A variation can be done to get multiple-source shortest path.

Applications: Web crawler is an example of BFS on Digraphs.

Multiple-Source Shortest Path
-----------------------------



Topological Sort/Precedence Scheduling
--------
- Use DFS
- Sample applications:
    - Scheduling of courses in university.
    - Scheduling of manufacturing tasks.

    // Algo
    - Run DFS
    - Return vertices in reverse postorder

Directed Cycle Detection
---------
- If directed cyclec, topological order is impossible.
- DFS can be used.


Strongly-Connected Components
---------
Def: Vertices v and w are strongly connected if there is a directed graph
from v to w and w to v.

Applications
---------
Food Web Graph:
    Vertex = species
    Edge = From producer to consumer

Algo to solve Strongly Connected Components
----------
Kosaraju-Sharir Algo
- Strong comp in graph G is same as reverse G
- Kernel DAG - Contract each strong component in to a single vertex.

  // Algo
  Phase 1: run DFS on reverse G to compute reverse postorder.
  Phase 2: run DFS on G, considering order given in phase 1.




Minimum Spanning Trees [MST]
----------
Given: Undirected graph G with positive edge weights (connected)
Def: A spanning tree of G is a subgraph T that is connected and acyclic.
Goal: Find a min weight spanning tree.


Simple Greedy Algo
----------
Assumptions:
  - Edge weights are distinct.
  - Graph is connected.

Definition:
  - Cut: partition in graph in to two sets of vertices. Vertices in one set
    belongs to MST while other's are not yet in MST.
  - Crossing Edge: connects vertex in one set to vertex in other set.
  - Cut property: Given any cut, the crossing edge of min weight is in
    MST.

Kruskal's Algo
-------
- Sort all edges by weight.
- Keep adding edges to MST in order unless they create a cycle.
- MST is computed in E*lnE (in worst case)

Implementation Challenge:
------
- Use union-find data struct
- Maintain a set for each connected component in T
- If v and w are in same set, then adding v-w edge would create a cycle



Prim's Algo
--------
- Start with vertex 0 and greedily grow tree T.
- Add to T the min weight edge with exactly one endpoint in T.
- Repeat until V-1 edges.
- E*lnE running time and extra storage space proportional to E.

Implementation Challenge (Lazy Implementation):
------
- Use PQ with one end point in tree T
- Key = edge; Priority = weight of the edge
- delete-min to determine next edge e=v-w to add to T
- Disregard if both endpoints v and w are in T. union-find DS can be used
- Otherwise, let w be vertex not in T:
    - add to PQ any edge incident to w (assuming other endpoint not in T)
    - add w to T

Eager Implementation:
------
//TBD - Not worth at this time

Brovuka's Algo
--------
- Combines Kruskal and Prim's algo

K-Clustering: Divide a set of objects in to K coherent groups
Distance Function: Numeric value specifying "closeness" of two objects
Goal: Divide in to clusters so that objects in different cluster are far apart

Single-Link Clustering Algo:
- Well known problem and algo exists.
- Kruskals algo. Stop when k connected components
- Alternately, run Prims algo and delete k-1 max weight edges


Shortest Path
-------
- Given an edge-weighted digraph, find the shortest path from s to t.
- Variants:
    - Source-sink: from one vertex to another.
    - Single source: from one vertex to every other.
    - All pairs: between all pairs of vertices.

Dijkstra's Algo (Shortest path)
-------
- Consider vertices in increasing order of distance from s (lowest
  distTo[] value).
- Add vertex to tree and update distTo[] of all vertices pointing from
  that vertex.

- Prim's and Dijkstra's algos are same. Prim's is for undirected graph. It
  looks for closest vertex to the spanning tree. Dijkstra's is for
  directed graph. It looks for closest vertex along a shortest path
  starting at source.

Longest Path Edge-Weighted DAGs
---------
(applications)
Parallel Job Scheduling:
    Create a graph G such that, vertices are start times of job and edges
    are job duration.

    Use longest path from the source to schedule each job ??


MINCUT PROBLEM
-------
Input: An edge-weight digraph, source vertex s and target vertex t. All
edges are positive.

Definition: A st-cut(cut) is a partition of vertices in to two disjoint
sets with s in set A and t in set B.
Definition: Capacity is sum of capacities of edges from A to B.

Goal: Find a cut of minimum capacity.


MAXFLOW PROBLEM
-------
Input: An edge-weighted digraph, source vertex s and target vertex t.
Capacity Constraints: 0<= edge's flow <= edge capacity
Local Equilibrium: inflow = outflow at every vertex (except s & t).

Def: Value of a flow is the inflow at t.
Goal: Find a flow of max value.


Ford-Fulkerson Algo
-------


Strings in Java
------
- Strings are immutable.
- StringBuilder is mutable.

String Sorting Algos
------
Key-Indexed Counting   // basic algo
Goal: Sort an array a[] of N integers between 0 and R-1.

// Algo
- Count frequency of each letter using key as index.
- Compute frequency cumulates which specify destination.
- Access cumulates using key as index to move items.
- Copy back in to original array.

  int N = a.length
  int[] count = new int[R+1];

  // compute frequency of each letter
  for(int i=0; i<N; i++)
      count[a[i]+1]++;

  // compute cumulates
  for(int r=0; r<R; r++)
      count[r+1] += count[r];

  // move items to aux array
  for(int i=0; i<N; i++)
      aux[count[a[i]]++] = a[i];

  // get them to original array
  for(int i=0; i<N; i++)
      a[i] = aux[i];



LSD String (Radix) Sort
--------
- Consider chars from right to left.
- Stably sort using dth char as key (using key-indexed counting)

MSD Radix Sort
--------

Suffix Sort
--------
- Create an array of suffixes of a given string.
- Sort the suffix strings.

Longest repeated substring
-------
(Used in Genomics, Cryptanalysis)
- Get suffix arrays and sort.
- Compare length of longest common prefix.


Substring Matching
-------
- Brute Force: MN char compares in worst case (M= pattern length, N = text
  size).
-


Knuth-Morris-Pratt Algo
-------
- Construct a DFA to match/mismatch input chars and state changes.
- A state indicates number of matching chars in pattern.
- Building the DFA is trickiest. Read/understand more.
-

Boyer-Moore
--------

Rabin-Karp
--------
- There are variation of vanilla Rabin-Karp version called: Monte Carlo,
  Las Vegas versions.


Floyd-Warshall Algo (All Pairs Shortest Path)