we were discussing a problem of finding the largest submatrix of 1 in a boolean matrix.
we presented several techniques to solve this including histogram method, iterative method and depth first approach. The depth first approach can find the number as well as sise of islands of 1s. This method explores all eight neighbors of a point. Therefore it visits all points in an island before going to the next island. This helps in knowing the size of the island before going to the others which also helps us deternine the largest island.

void DFS(int[,] A, int ROW, int COL, int row, int col, ref int[,] visited, ref int  size)
{

var rd = { -1,-1,-1,0,0,1,1, 1};
var cd = { -1,0,1,-1,0,1,-1,0,1 };

visited[row,col] = true;
for (int k = 0; k < 8; k++)
    if (isSafe(A, ROW, COL, row + rd[k], col +cd[k])){
           size++;
           DFS(A, ROW, COL, row+rd[k], col+cd[k], ref visited, ref size);
}
}

bool isSafe( int[,] A, int ROW, int COL, int row, int col, ref int[,] visited)
{
if ( row >= 0 && row < ROW &&
      col >= 0 && col < COL &&
      A[row, col] == 1 && !visited[row,col])
      return true;
return false;
}

int countIslands(int[,] A, int ROW, int COL)
{
var visited = new bool[ROW, COL] { False }
int count = 0;
int maxsize = 0;
for (int i = 0; i < ROW; i++)
   for (int j = 0; j < COL; j++)
      if ( A[i,j] == 1 && !visited[i, j])
   {
        int size = 0;
        count++;
        DFS(A, ROW, COL, i, j, ref visited, ref size);
        if (size > maxSize)
             maxSize = size;
   }

}

we were discussing a problem of finding the largest submatrix of 1 in a boolean matrix.

Another technique is to not divide the matrix into equal parts over and over again but to use a graph and traversal algorithms to find islands. Then for each of these islands find the largest size.

this is therefore a two step procedure.

first, we do a depth first traversal. here we only recurse if the cordinate is safe. by that we mean the points are within the matrix boundaries, are all ones and they have not been visited. we keep a visited matrix which we fill and we can explore all eight adjacencies of a point one at a time. if a cell with value 1 is not visited then we found a new island and make note of this cordinate.

• second for each island and a cordinate on this island, we can explore its size and the maximum submatrix rectangle contained by any of the techniques mentioned earlier such as the histogram method. This gives us the cordinates and the size of the final submatrix we are interested in.

today we look at a few more alternatives to the submatrix of 1 problem discussed earlier.
one such method is to facilitate merge along vertical and horizontal axis in a way such that contiguous regions of 1s are identified, sized and top left corner identified. then we split the original matrix into  2 power x sub matrices by repeatedly dividing  both x and y axis. This works well for cohesive matrices where the 1s are all together as islands. Since each point is counted only once during the merge before being assigned to a group and the results aggregated, this is more efficient than the nested evaluation of each point as a candidate for top left corner. Moreover we keep track of the top left and bottom right corners of each candidate submatrix from the adjoining contiguous overlaps during each merge. each overlap along a merge front determines the span of the submatrix


today we review a new topic called social balance theory from the chapter on network measures. this theory is about friends and enemies relationships abd i had never really paid attention to it so far. it states:
The friend of my friend is my friend, The friend of my enemy is my enemy, The enemy of my enemy is my friend, The enemy of my friend is my enemy.
All this theory states is that the friends or enemy relationships are consistent when the above is followed.

we can represent these relationships in a graph. The friendhip is denoted by positive edges, the enemity by negative edges and a triangle between participants denotes imbalance if the weights around the edges of the triangle taken together is less than zero. this kind of metric can also be explored for graphs that are not triangular in general.

#codingexercise
for the  problem duscussed yesterday, we see a few more alternatives

parallel processing
sum along all columns
sum along all rows
if any row or column is all zero
split the matrix on either side of the zeros
compute the submatrix as usual

another method may be to merge two sub matrices along a front
the histogram on both sides of the front are computed starting from the front and progressing outwards
for contiguous non-zero paired entries on the histograms on both sides, the max area is calculated for each contiguous zone out of which the largest is chosen

another method for a merge like above would be to find contiguous zones of ones along the front
for each of the contiguous zone, and for each of the ones in the zone find the max area on both sides noting the common width.
retirn the max of all such combined max.

Linux Containers
Today we discuss the Linux Containers. These form isolated environments within the operating system. As we know Linux itself is a modular design with layered components where every component can be replaced with another and the whole operating system can be rebuilt.
The standard layers including the operating system are:

Users
Utility Programs
System Library
Linux OS
Hardware

The interfaces between users and user programs is User Interface.
The interface between utility programs and system library is library interface
The interface between system library and Linux is system call interface.

The LXC hosts more than one containers by being a layer over the OS.  Since the OS can be over real or virtual hardware, we can have the whole stack nested as we nest containers.

A network bridge is established on the host operating system and the containers are usually NAT'ed. This means the containers are not directly reachable from the outside network. With DHCP, they get assigned an ip address so addressing is not a problem but to facilitate inbound and outbound connections, the gateway must be specified in routing table of the containers.  Outbound connections are facilitated with the gateway. If the bridge was established over the original ethernet interface of the host, the inbound connectivity is also established. This way the containers can be accessed by ssh.

Often containers are required to be cut with some customization scripts. These include provisioning a sudo user or enabling ssh access for public keys. All of these can be run as shell commands targeting the specific container from the host with something like:
lxc exec <container_name> -- command


#codingexercise
Find the largest sub matrix rectangle of 1's in a two dimensional binary matrix.
Here's the alternative version to the solution yesterday.
int GetMax(int[,] A, int R, int C)
{
int max = int_min;
for (int i = 0; i < R; i++)
   for (int j = 0; j < C; j++){
        area = AreaWithTopLeft(A,i,j, R, C);
        if (area > max)
             max = area;
     }
return max;
}
int AreaWithTopLeft(int[,] A, int i, int j, int R, int C)
{
int max = 0;
int prev = int_max;
if (A[i,j] != 1) return 0;
for (int x = i; x < R; x++){
   int count = 0;
   for (int y = j; y < C; y++)
   {
      if (A[i,j]  == 1) count++;
   }
   if (count == 0) return max;
   int newmax = min(prev, count) * (x-i+1))
   if (newmax < max)
       return max;
    max = newmax;
   prev = count;
}
return max;
}
we can also optimize the above bailing early so that we dont have to iterate when there are no ones.

Serial console on VMWare

Introduction:  We reviewed the DELL Serial Console Option. This document is about the serial console for VMWare Virtual Machines.

Architecture:

The VMWare community suggests using the virtual serial port concentrator. The concentrator also called the proxy has internal connections to several virtual machines in a datacenter and an external connection to a remote system.

The virtual serial port concentrator can be deployed as a virtual appliance involving a single virtual machine. This appliance uses the virtual machine ip address that persists across vMotion events. The Proxy accepts telnet connections from virtual machine and supports the VMWare telnet extension commands and corresponding notifications in addition to forwarding traffic both ways. The proxy serves as a point of authentication on a remote system. Since the telnet connections are internal, they need not be secured. Even a Moxa device server uses telnet console.

A virtual serial port provides out of band access to the virtual machine so that even if we lose network connectivity, we can use the serial console to interact with the machine. When this serial console is available over IP, you can remotely manage a machine even when there is a fault in the OS or the hardware of a machine.

Steps to take on the Proxy:

1.       Start the vspc.py using  - - server option

2.       Configure the vspc.py to start automatically at boot

3.       Edit the local firewall rules on the virtual serial port concentrator to permit 13370/tcp, 13371/tcp and a range of ports for target virtual machines starting at any high value say 63000

Steps to take on each VM

1.       Power off VM

2.       Add a serial port to the VM with the following settings:

On the Hardware tab, click Add.

In the Add Hardware wizard, select Serial Port.

Select where the virtual serial port sends output. It should be one of the following:

Use a physical parallel port

Use output file

Connect to named pipe

Connect via network

Choose the last option

And specify use virtual serial port concentrator and type the vSPC URI as telnet://vspc.local.lan:13370

If we don’t want to use a vSPC and provide a dedicated serial port, We can also use xcat/socat/netcat etc. Refer VMWare how to for virtual serial port configuration

select this end is the server from the first drop-down menu and select

the other end is an application from the second drop-down menu.

To connect the port to the virtual machine when the virtual machine powers on, select Connect at power on.

Click Finish to add the virtual serial port to the virtual machine.

On the Hardware tab, select the new serial port, select Yield CPU on poll, and click OK.

3.       Start the virtual machine

To query the virtual serial port connections opened on the proxy, run, from any machine including laptop with connectivity to the proxy, the following command:

./vSPC.py vspc. local.lan

machine1:500aedefafeae42434-b534dade2eawa5q3:63002

machine2:90834124ewdafwe-aw243123ewdeawdea:63003

etc.

To connect to the serial console, let’s use the corresponding port

telnet vspc.example.com 63002

Caveat : This information is provided as-is by collection from literature. 

Courtesy : VMWare vsphere web services SDK

To view consoles in public cloud refer http://docs.aws.amazon.com/AWSEC2/latest/UserGuide/instance-console.html

#codingexercise
Tell whether a matrix containing 0s and 1s can be divided into 2 sub matrices containing equal number of 1s.
Matrices can be split into two only by vertical or horizontal partitions. We can enumerate all partitions and check

bool HasEqual1and0(int[,] A, int r0, int rn, int c0, int cn)
{
int count = CountOnes(A, r0, rn, c0,cn);
for (int i = r0+1; i <= rn-1; i++)
{
int count1 =  CountOnes(A, r0, i, c0,cn);
int count2 =  CountOnes(A,i+1, rn, c0, cn);
assert(count1+count2 == count);
if (count1 == count2) return true;
}
for (int j = co+1; j<=cn-1;j++)
{
int count1 =  CountOnes(A, r0, rn, c0, j);
int count2 =  CountOnes(A, r0, rn, j+1, cn-1);
assert(count1 + count2 == count);
if (count1 == count2) return true;
}
return false;
}

int CountOnes(int[,] A, int r0, int rn, int c0, int cn)
{
int count = 0;
for (int i = r0; i <= rn; i++)
for (int j = co; j<=cn;j++)
      if (A[i,j] == 1) count++;
return count;
}

Find the largest sub matrix rectangle of 1's in the above matrix:
we  create a histogram and find the maximum area under the histogram
int maxRectange(int[,] A, int R, int C)
{
int result = GetMaxFromHistogram(A[0]); // this is the area of the first row
for (int i = 1; i < R; i++)
{
   for (int j = 0; j < C; j++)
         if (A[i, j] ) A[i, j] += A[i-1, j]
  result = max(result, GetMaxFromHistogram(A[i]));
}
 return result;
}
MaxAreaOfARectangle implemented GetMaxFromHistogram earlier

alternatively the max area of submatrix of 1s can also be found by treating each cell as the top left corner of the rectangle.

Serial Console Access over SSH

iDrac already provides console access via SSH as per the diagram below for certain DELL servers. An API service facilitating console access needs to only secure it by allowing the console access on a customer by customer basis and to only his or her servers: 

 

1. Initial setup follows this configuration: http://www.slac.stanford.edu/grp/cd/soft/unix/EnableSerialConsoleAccessViaSSH.htm 

Which specifies console redirection over SSH from iDRAC with the following setting: 

# racadm get iDRAC.SSH.Enable 

[Key=iDRAC.Embedded.1#SSH.1] 

Enable=Enabled 

2. For each console session initiation and termination, we start the console redirection with the following serial console commands: (All serial console commands are identical and at the same level as RACADM CLI subcommands. This means you can specify serial commands as well as racadm commands from the serial/telnet console.)  

1. racadm racreset – this releases the serial port used previously 

2. connect <servername> -F 

1. (Instead of <servername> we can specify switch-x where x represents a module slot number on the chassis). When the system BIOS console redirection setting is set to BMC, the –F option forces the serial console redirection session to switch from BMC to DRAC/MgmtConsole. When the system is rebooted, the BIOS console redirection setting returns to the default setting.  

2. Reboot the target 

3. <Enter><~><.>  or ^\ to exit out of the session 

4. getpbinfo (for power status and power information) 

5. serveraction ( for executing a server reset/powerdown/graceful powerdown/powerdown/powerup/powercycle)

#codingexercise
Cars 1 to 9 are parked randomly in the slots marked 1 to 9. Using the tenth slot, arrange the cars.

void arrange(ref List<int>cars)
{
for (int i = 0; i <cars.count; i ++)
{
if (cars[i] == i) continue;
for (int j =i+1; j < cars.count; j++){
   if (cars[j] == i){
          Swap(cars,i,j);
   }
}
}
}
the above method can be made linear if we maintain a lookup of where the cars can be found.