Notes on recursion

THINKING IN RECURSION

1.       When you think of recursion, think of the “base case” first and put it as the first line inside recursive function.

2.       All the values used in the recursive function should be passed as input parameters in the function (rather than declaring inside the function).

3.       Any “calculated value” inside the recursive function should be in the “return value” of the recursive function. Example  - output = quickselect(A, p, q – 1, k, output)

4.       “Returning part” i.e. the return statement should be in the end of the recursive function (unless it’s a base case).

5.       Think of recursion as box inside a box inside a box inside a box…..till the base case.

Refer http://lazynreclined.blogspot.in/2016/10/algorithms-quicksort.html for Quickselect recursive function

Algorithms - Dynamic connectivity problem

DYNAMIC CONNECTIVITY PROBLEM –

Is ‘0’ connected to ‘2’.  YES

Is ‘2’ connected to ‘3’. NO

The algorithm will give you answer in YES or NO. It will not give you the path from src to dest.

Connected components are –    {10},                       {0, 1, 2, 4, 5, 6},                  {3, 7, 8, 9}

Two basic operation-

·         Union command – Joins two nodes ONLY if they are not connected (DIRECTLY or INDIRECTLY).

·         Find query – Answers in YES or NO, if two nodes are connected directly or indirectly.

Couple of approaches in implementing

1)      Quick Find – (BAD) as ‘union’ operation goes in O(n²).

2)      Quick union – (GOOD) as it works in logarithmic times.

a.       Improvement  1. Keep it balanced by using an auxiliary array. In Weighed quick union, we make the root of the smaller tree (IN TERMS OF NUMBER OF NODES, NOT HEIGHT), the root of the larger tree.

b.      Improvement 2 – path compression.

One of the practical usage of solving this problem is MONTE CARLO SIMULATIONS.

Monte Carlo simulations can be used to find the percolation threshold.

The system will percolate if there is a connectivity between top and bottom. Each site is open with a probability p.

This can only be found using COMPUTATIONAL MODELS rather than MATHMATICAL MODELS.

With random tries of various values for n in the grid above and multiple experiments, it is found that at p=0.592746, the system percolates.

Data structure - Graphs

GRAPHS

class graph

{

       int v;      //number of vertices

       LinkedList<Integer> adj[]; // “array of” linked lists.

       void AddEdge(int v, int w)

       {

            Adj[v].add(w); //adj[0], adj[1],….adj[v-1] are initialized in the ctor of the graph class.

       }

}

Couple of points –

a)      Graph contains a set of vertices called nodes.

b)      Graph contains ordered pair of the form (u, v) called EDGE.

c)       (u, v) is not same as (v, u) in a directed graph (di-graph).

Real life uses – Social network, paths in a city, network, web crawler, garbage collection.

Representation –

Adjacency list. Pros – less space. Cons – To find if edge exits, it will take O(v) time.

Adjacency matrix. Pros – Quick to find edge exists or not O(1). Con – more space.

Fibonacci using matrix multiplication

FIND nth FIBONACCI NUMBER USING MATRIX MULTIPLICATION

1              1              2              3              5              8              13           ….
F1            F2             F3             F4            F5            F6              F7          .....    Fn  

Basis used – 

Lets call this matrix M. All we have to do is M^n-1 and  return its [0][0]th element.

An efficient implementation using recursion is given below –

def power (F, n):

            if n == 1 or n == 0:

                                return   /// base case

            M = [[1, 1], [1, 0]]

power(F, n/2)

multiple(F, F)

if (n % 2 != 0):

                multiple(F, M)

def multiply (F,M):

                does the matrix multiplication and puts the result back into F.

Data structure - Stacks and Queues

STACKS & QUEUES

Inner class –

private class Node

{

                Employee item;

                Node next;

}

Stack Implementation : LinkedList vs Resizing array

LinkedList –

Pros – Every operation takes constant time in the worst case.

Cons – Uses extra time + space to deal with links (pointers).

Resizing Array –

Pros – Less wasted space.

Cons – Every operation takes constant AMORTIZED time.

One of the practical application of stack – To evaluate expression.

Technique – Dijkstra’s 2-stack algorithm.

Steps –

1)      Put values in one stack, operands in the other.

2)      Ignore ( i.e left parenthesis.

3)      For ) i.e. right parenthesis, pop 2 values from the value stack, pop operand from the operand stack, do the operation and put the output back (push) to the value stack.

Example – Evaluate :   (1 + 2) * ((3 – 1) + (4 * 5))

How a make a Queue using 2 stacks ?

1)      Create two stacks s-main and s-temp.

2)      For every enqueue operation, do push on s-main.

3)      For every dequeue operation, do the following –

a.       (n – 1) pop on s-main and (n – 1) push to s-temp.

b.      pop on s-main to the get the OUTPUT.

c.       (n – 1) pop on s-temp and (n – 1) push back to s-main.

Practical applications of Priority queues (implemented using binary heaps)

Requirement 1 – Find the largest M items out of the total of stream of N items. (example – Fraud detection: Isolate $$$ transactions, File maintenance: find top k largest files/ directories.

Requirement 2 – Not enough space to store all N items (otherwise we could have stored them all and sorted in NlogN time).

To solve problems while satisfying Requirement 1 and 2 above, PRIORITY QUEUES are the best.

For more details on heaps, look - http://lazynreclined.blogspot.in/2016/09/algorithms-heaps.html

Algorithms - Use Binary Search to find first/last occurrence, element count

BINARY SEARCH ON SORTED ARRAYS (FIRST/LAST OCCURRENCE).

GET ELEMENT COUNT IN A SORTED ARRAY.

Taken from  - https://www.youtube.com/watch?v=OE7wUUpJw6I

and https://www.youtube.com/watch?v=pLT_9jwaPLs&feature=player_embedded

BinarySearch(A,size,x):

                low = 0

                high = size – 1

                while low <= high:

mid = (low + high)/2

if A[mid] == x:

                return mid

elif A[mid] > x:

                high = mid -1

else:

                low = mid + 1

return -1

The above is a plain implementation of binary search that immediately returns ‘mid’ once A[mid] == x. So it does not find the first or last occurrence of an element. We easily modify the the above implementation by adding two lines (in yellow) to return the first/last occurrence.

BinarySearchFirstOccurence(A,size,x):

                low = 0

                high = size – 1

                result = -1

                while low <= high:

mid = (low + high)/2

if A[mid] == x:

                result = mid

                high = mid -1

elif A[mid] > x:

                high = mid -1

else:

                low = mid + 1

return result

Note in the above implementation, even if the element is found, we don’t immediately return. We store it in a ‘result’ variable and continue looking ‘leftwards’.  

In case you want to find the last occurrence of an element, you do the same except you continue looking ‘rightwards’.

To find the count of an element, you do lastIndex – firstIndex + 1.

Create WebAPI application with an empty template

Creating a WebAPI application in Visual Studio using the templates available makes it bloated with tons of nuget package references and other stuff. Following are the steps to make a WebAPI application in Visual Studio with an empty website template.


1) Create an empty Web Application with nothing in it. (no Global asax, no entry in web.config, no JS)


2) Add Microsoft.AspNet.WebApi.WebHost nuget package to the project. This will add the other dependent packages like WebApi.Core etc.

3) Add a Global.asax file and insert these lines
        protected void Application_Start(object sender, EventArgs e)
        {            
            WebApiConfig.Register(GlobalConfiguration.Configuration);
        }

4) Add a App_Start folder with WebApiConfig.cs
 public static class WebApiConfig
    {
        public static void Register(HttpConfiguration config)
        {
            config.Routes.MapHttpRoute(
                name: "DefaultApi",
                routeTemplate: "api/{controller}/{id}",
                defaults: new { id = RouteParameter.Optional }
            );
        }
    }

5) Add folder - "Controllers"

6) Add HomeController with the following code - 

 public class HomeController : ApiController
    {
        // GET api/values
        public IEnumerable<string> Get()
        {
            return new string[] { "value1", "value2" };
        }

        // GET api/values/5
        public string Get(int id)
        {
            return "value";
        }

    }