#codingexercise
Yesterday we were discussing finding largest sum sub-matrix. It required largest sum subarray to be efficient. This we have seen earlier as Kadane's algorithm. Today we require to compute k such maximum sum subarray that are non-overlapping. The approach in this case is
repeat for k times :
   First find a subarray with maximum sum using techniques discussed earlier.
   If such an array exists:
         print the bounds of the subarray along with its sum
         replace this subarray with values lower than all elements so that it does not participate in the next find.
Note that the existence of the array might fail because there might not be k such subarray. Each iteration is greedy and inclusive of as many contiguous elements as possible. If the number of such arrays fall short of k, we can always slice the arrays to meet or exceed k based on the descending order of subarrays ordered by their sum.
   We discuss the ways to find the max subarray sum:
Largest subarray sum - Kadane’s algorithm

Initialize 

max_so_far = 0

max_ending_here = 0

For each element of the array

                max_ending_here = max(0, max_ending_here+ A[i])

                max_so_far  = max(max_so_far, max_ending_here)

Alternatively

Initialize and maintain the following variables

x = sum of elements

y = minimum of sum encountered

z = maximum of sum encountered

For each element of the array

           y = min(x, y)

           z = max(z, x-y)
 return s

For example:

-1, 0, 2, 1 array
has following x, y, and z values in each iteration:
      x     y   z
      -1   -1   0
      -1   -1   0
       1   -1   2
       2   -1   3
max sub array sum = 3

#codingexercise
Find the largest rectangular sub-matrix having sum divisible by k.
The naive approach is to exhaust all the rectangular sub matrices to find the sums. check that the sums are divisible by k and then update the max of the rectangular size found so far.
This appears something like
int GetLargest(int[,] M, int R, int C, int k)
{
int max = 0;
// Every element forms the top left corner of a rectangular area of different sizes
for (int i = 0; i < R; i++)
  for (int j = 0; j < C; j++)
{
   int kx = i;
   int ky = j;

    for (int m = kx; m < R; m++)
         for (int n = ky; n < C; n++)
    {
           int sum = GetSum(M, i,j,m,n);
           if (sum % k == 0)
           {
                    int size = GetSize(i,j,m,n);
                    if (size > max)
                        max = size;
           }
    }
return max;
}
The above is O(N^3) complexity as the 2D iterations are performed for every coordinate in the rectangular area
As we can see that this has a lot of overlapping regions that are summed again and again.
Instead, we could enumerate all the possible rectangular areas to be bounded in the matrix between a pair of left and right columns and a pair of top and bottom rows with the temporary sums along each row and column The temporary sums are in a linear array and we can now use the algorithm to find the longest sub-array having sum divisible by k to find the rectangular sub area in this 2D scan.

Let us take a closer look at the event application framework we mentioned yesterday. Several designs compete for this space. We enumerate some below: 

First – we mention the design of MSMQ with its dead letter and poison letter queues.  This design includes support for retries by the queue processor, non-invasive approach which lets the clients send and forget, ability to create an audit log, support for transactional as well as non-transactional messages, support for distributed transactions, support for clusters instead of standalone single machine deployments and ability to improve concurrency control. 

This design is somewhat different from that of System.Messaging. The system.messaging library transparently exposes the underlying Message queuing windows APIs . For example, it provides GetPublicQueues method that enumerates the public message queues. It takes the message queue criteria as a parameter. This criterion can be specified with parameters such as category and label. It can also take machine name or cluster name, created and modified times as filter parameters. The GetPublicQueuesEnumerator is available to provide an enumerator to iterate over the results.  

Second – we mention the design of ZeroMQ, RabbitMQ and others of this family with their flexibility for several publishers and consumers topology.  These are superfast guaranteed delivery message bus but they are mostly for standalone deployments and not as cloud services.  

In this regard, Amazon Simple Queue Services offers almost unparalleled fully managed message queuing service that makes it easy to integrate with microservices and serverless applications. SQS also makes it simple and cost-effective to intermediate between these producers and consumers. 

Third – we mention the highly performant Erlang-based messaging framework. Whatsapp is a messaging architecture. It offers free texting in a SMS world. There are no ads, no gimmicks, no games and no feeds. They have hundreds of nodes, thousands of cores, hundreds of terabytes of RAM, serve billions of smartphones. Their server infrastructure is based on Erlang/FreeBSD.  The Erlang is a programming language that is used to build massively scalable soft real-time systems with requirements on high availability.  With this programming language they send out about 70 million messages per second.  

This architecture is famous for “it just works” because only a phone number is used as the address to send messages to and messages can be voice, video, images or text.   It also features voice message, group chats and read-receipts.  

The backend consists of Erlang, Jabber, FreeBSD, Yaws web server, PHP, BEAM, and custom XMPP. The Frontend consists of seven client platforms for the different mobile devices and SQLite. Every user is an actor. Messages flow between actors when they are online or they are stored offline. When the actor comes online, he pulls the messages sent to him.  User and actor differ in that the actor notion or proxy exists only in the WhatsApp backend framework. Message sent from user goes to actor inbox which then sends the message to the other actor who then repeatedly sends to the user behind the actor. When that user comes online, the messages appear.  The Mnesia backend DB stores the actors and their inboxes. The message is encrypted with a key as a tag. They use tools for system activity monitoring on all their server operating systems as well as BEAM Processor hardware perf counters and dtrace. BEAM is the erlang VM that is used to process the messages.  

The highlight of this architecture is its performance-oriented design. Even similar feature from Facebook also written in erlang could not match the widespread adoption of this messenger.  They have proven that Erlang and FreeBSD have unmatched SMP scalability.  

With these three different forms of design, we can now utilize cloud services or build a limited scale light-weight customized solution for the requirements we mentioned. 

#codingexercise
Yesterday we were discussing ways to climb up the staircase with jumps of 1, 2 or 3 steps.
We can generalize this for climbing up staircase with jumps of  1 to N-1 steps
The number of ways to climb up the staircase with N steps by taking a leap of 1 to N steps at a time is simply the sum of binomial coefficients. We see this by cumulating that there are n-1Choose1 ways to take one stop jump and n-1Choose2 ways to take two jumps and so on.
static int GetCount(int n)
 {
            if (n == 0)
                return 1;
            return (1 << (n - 1));
 }

• The binomial coefficient for increasing degrees form the Pascals triangle. 

Event Application Framework for debugging.
Most of us have relied on the debugger for examining the execution of code. Undeniably, debugging is the authoritative way to figure out what the code is doing when unexpected execution happens especially if there are no exceptions or logs. We discussed a few of the debugging rules of thumb here (http://ravinote.blogspot.com/2013/05/today-i-had-to-do-some-debugging-and-it.html)
However, today I add event application framework support to the troubleshooting toolbox in addition to the debugger. One such example is the circuits library (https://pypi.python.org/pypi/circuits)
So we can do things like everything on the wire:
#!/usr/bin/env python
from circuits import handler, Debugger
from circuits.net.sockets import TCPServer
class EchoServer(TCPServer):

    @handler("read")
    def on_read(self, sock, data):
        return data
app = EchoServer(9000)
Debugger().register(app)
app.run()
While this kind of packet capture may not be very helpful as compared to the http archive file for the web applications since most of the handlers are already responding to http requests, it goes to show how the event application framework can be used for internal events. Moreover we can expose these handlers as web methods as well such as when we want to list some internal statistics or in-memory object audit history.
#!/usr/bin/env python
from circuits.web import Server, Controller
class Root(Controller):
    def index(self):
        return "Hello World!"
app = Server(("0.0.0.0", 9000))
Root().register(app)
app.run()


#codingexercise
We were discussing counting the number of ways to climb up the staircase and we can modify the number of steps at any time to  1 or 2
int GetCountWays(uint n)
{
    int [] dp = new int[n+2];
    dp [0] = 0;
    dp [1] = 1;
    dp [2] = 2;

    for (int k = 3; k <= n; k++) {
     
                 dp [k] = dp [k-1] + dp [k-2];
     
    }
   return dp [n];
}

and recursively as :
int GetCount(uint n)
{
if ( n == 0) return 0;
if (n == 1) return 1;
if (n == 2) return 2;
return GetCount(n-1)+GetCount(n-2);
}

Some people like to start the dp[0] as 1 so that this follows the Fibonacci pattern for 1 and 2 steps

Note we can generalize this for climbing up staircase from 1 to N-1 steps

We were discussing Monte Carlo simulations. Historically simulations were used to test a previously understood deterministic problem. The sampling was used to generate uncertainties in the simulations. Monte Carlo simulations inverted this approach. It tries to solve deterministic problems using optimizations based on probabilistic interpretations. It draws samples from a probability distribution. We had seen another such method earlier. It was called Simulated Annealing. This is a special case of Monte Carlo. In Simulated annealing, we computed the current cost and the new cost based on the direction of change. If it improves, we decrease the temperature.

#codingexercise
We were discussing the bottom up manner of counting ways to climb the staircase
int GetCountWays(uint n)
{
    int [] dp = new int[n+2];
    dp [0] = 0;
    dp [1] = 1;
    dp [2] = 2;
    dp [3] = 4;

    for (int k = 4; k <= n; k++) {
       
            
                 dp [k] = dp [k-1] + dp [k-2] + dp [k-3];
        
    }
   return dp [n];
}
Some people like to start the dp[0] as 1 so that this follows the Fibonacci pattern for 1 and 2 steps

The above memoization can be reused for computing results for consecutive integers 

We resume our discussion on Monte Carlo Simulation of Synthetic Data Sets shortly. This is a powerful technique. It generates samples that are similar to the actual data set. A large number of samples generated enable us to get closer to the global minima. For example, for estimating the value of pi, when we have a large number of samples, the computed value could get very close to the actual value. Monte Carlo assumes that if the fitted parameters a0 is a reasonable estimate of the true parameters by minimizing the chi-square then the distribution of difference in subsequent parameters from a0 should be similar to that of the corresponding calculation with true parameters
The assumed a0 initial parameter set together with noise can be used to generate new data sets at the same values of the independent  axis coordinate as the actual data set has with that axis. The synthetic data aligns with the actual data at these points of reference on the line. Now the interesting part is that the new dataset has the same relationship to a0 as the actual data has with the true parameter set.
We can generate many such data sets and they are called synthetic data sets. For each such dataset, we can fit a model and obtain the corresponding parameter set. This yields one data point for the difference between the parameter set  corresponding to the synthetic data from the initial parameter set. The simulation can be run thousands of times to generate sufficient data points. This leads to a probability distribution which is M-dimensional.  We can even calculate the standard deviation of the original parameter set after fit using the cumulative data point differences.
Historically simulations were used to test a previously understood deterministic problem. The sampling was used to generate uncertainities in the simulations. Monte Carlo simulations inverted this approach. It tries to solve deterministic problems using optimizations based on probabilistic interpretations. It draws samples from a probability distribution. Simulated Annealing is a special case of Monte Carlo which we had seen earlier here
#codingexercise
Count the number of ways to reach the n'th stair using 1,2 or 3
int GetCount(int n)
{
   switch(n)
   {
     case 0:
                return 0;
     case 1:
                return 1;
     case 2:
                return 2;
     case 3:
                return 4;
     default:
                return GetCount(n - 3) +
                           GetCount(n - 2) +
                           GetCount(n - 1);  
    }
}
The above can be rewritten with if then else statement.
f (4) = f (1) +f (2) +f (3) = 1 + 2 + 4 = 7
enumerated as
1 1 1 1
121
112
211
22
13
31
We can also similarly show f (5) = f (2)+f (3)+f (4) = 2 + 4 + 7 = 13
Note we could also write this dp using memoization and a bottom up manner computation.

Happy New Year
#codingexercise
Generate the nth Newman Conway Sequence number. This sequence is shown as
1 1 2 2 3 4 4 4 5 6 7 7
It is defined as the recursion :
P(n) = P(P(n - 1)) + P(n - P(n - 1))
and with closure conditions as
P (1) = 1
P (2) = 1

double GetNCS ( double n )
{
if ( n == 1 || n == 2)
      return 1;
else
      return GetNCS (GetNCS (n-1)) + GetNCS (n-GetNCS (n-1));
}
n = 3:
P (P (2))+P (3-P (2))
    = P (1) +P (2) = 2
n = 4
P (P (3))+P (4-P (3))
= P (2) +P (2) = 2