We continue discussing the paper by Papadimitriou  - Algorithms, Games and Internet. We started with Nash equilibrium and then we discussed Internet Equilibria. We viewed the latter in terms of multi commodity flow network where the maximum total flow in a subgraph is in the core of a coalition game. we saw the definition of core to hint at optimal set. Next we looked at markets.  Markets are known for price equilibrium. and then we discussed mechanism design problems.
A mechanism design problem is one which has N agents. These agents must make a collective choice from some set X of possible alternatives. However each agent before making a choice privately observes his preferences over the alternatives in X also referred to as his type which means he or she is guided by his or her own interest. Hence this is considered a game of incomplete information.A mechanism is a collection of a finite number of strategy sets and an outcome function based on the strategy sets taken together.A mechanism combined with a profile of possible types, the probability density of the possible realization of types, and the utility functions define a game of incomplete information.

#codingexercise
Print boundary nodes of a binary tree
   - print the left boundary from top to bottom
   - print the leaf nodes of the tree on both left and right
   - print the right boundary from bottom to top
void GetBoundary (Node root)
{
    if (root == null) return;
    Console.WriteLine(root.data);
    GetBoundaryLeft(root.left);
    GetLeaves((root.left);
    GetLeaves(root.right);
    GetBoundaryRight(root.right);

}

void GetLeaves(Node root)
{  
    if (root == null) return;
    GetLeaves(root.left);
    if ( root.left == null && root.right == null)
        Console.WriteLine(root.data);
    GetLeaves(root.right);
}

void GetBoundaryLeft(Node root)
{
  if (root == null) return;
  if (root.left)
  {
  Console.WriteLine(root.data);
   GetBoundaryLeft(root.left);
  }
  else if( root.right )
  {
  Console.WriteLine(root.data);
   GetBoundaryLeft(root.right);
  }
}
void GetBoundaryRight(Node root)
{
    if (root == null) return;
    if ( root->right )
   {
     GetBoundaryRight(root.right);
     Console.WriteLine(root.data);
   }
   else if ( root.left )
   {
     GetBoundaryRight(root.left);
     Console.WriteLine(root.data);
   }

}

We continue discussing the paper by Papadimitriou  - Algorithms, Games and Internet. We started with Nash equilibrium and then we discussed Internet Equilibria. We viewed the latter in terms of multi commodity flow network where the maximum total flow in a subgraph is in the core of a coalition game. we saw the definition of core to hint at optimal set. Next we looked at markets.  Markets are known for price equilibrium. and then we discussed mechanism design problems.
A mechanism design problem is one which has N agents. These agents must make a collective choice from some set X of possible alternatives. However each agent before making a choice privately observes his preferences over the alternatives in X also referred to as his type which means he or she is guided by his or her own interest. Hence this is considered a game of incomplete information.
Each agent is expected to be a utility maximizer based on the preferences exclusive to the agent. The probability density as well as the sets and the utility functions are assumed to be common knowledge The agents preference depends on the realizations of the set or profile of types so the agents may want the collective decision to depend on the profile of types. So a notion of social choice function  is introduced. This is a function which assigns a collective choice for each possible profile of the agents types.
Moreover this function can be Paretian or Pareto optimal, which is the name given to the most optimal one, if there does not exist a profile where there is a choice from the set of possible alternatives such that the utility  for that choice is greater than or equal to the utility for the collective choice for every type and strictly greater than the utility for the collective choice for some type. Simply put it is the most optimal.
This implies that a social welfare function is Pareto optimal if it selects for every profile of types, an alternative that is Pareto optimal given the agent's utility function. This welfare function only works if each agent is relied upon to disclose his type, however for a given social choice function, an agent may not find it to be in her best interest to reveal this information truthfully.
A mechanism is a collection of a finite number of strategy sets and an outcome function based on the strategy sets taken together. It can be viewed as an institution with rules that determine the procedure for making the collective choice.  The allowed actions of each agent are summarized by the strategy set corresponding to that agent and the rule for how the agents actions get turned into a social choice is given by an outcome function. A mechanism combined with a profile of possible types, the probability density of the possible realization of types, and the utility functions define a game of incomplete information.  This set of rules can be a complex dynamic procedure in which case the elements of the strategy set would consist of contingent plans of actions. A mechanism is said to implement social choice function if there is an equilibrium strategy profile of the game induced by the mechanism such that the outcomes is equal to the utilities for all types belonging to the combinations of possible types when taken together.

Courtesy: Microeconomic theory by Colell, Whinston and Green : Chapter on Incentives and mechanism design

#codingexercise

Find the minimum difference between any two integers in an array.

int GetMinDiff(List<int> A)
{
A.sort();
int diff = int_max;
for( int i =0: i < A.count -1; i++)
    if ( Math.Abs(A[i+1] - A[i] ) < diff )
           diff = Math.Abs(A[i+1] - A[i]);
return diff;
}

In the implementations of testing whether a given integer array is a pre order form or a post order form of a BST, we check for the subarray contained between a root and one of its siblings is strictly a valid subtree of the BST at that level. we dont do the check on both sub trees at that level. This means we can check the values in both sub arrays are strictly less than and strictly greater than the root as the case may be given which sub array is chosen.

Find the maximum difference between any two integers in an array.

int GetMaxDiff(List<int> A)
{
A.sort();
int diff = int_min;
for( int i =0: i < A.count -1; i++)
    if ( Math.Abs(A[i+1] - A[i] ) > diff )
           diff = Math.Abs(A[i+1] - A[i]);
return diff;

}

We continue discussing the paper by Papadimitriou  - Algorithms, Games and Internet. We started with Nash equilibrium and then we discussed Internet Equilibria. We viewed the latter in terms of multi commodity flow network where the maximum total flow in a subgraph is in the core of a coalition game.  Next we looked at markets.  Markets are known for price equilibrium. Arrow-Debreu 1953 theorem suggests that there is always a price vector p called the price equilibrium by which the endowments are indeed the best vector of goods.If game theory strives to understand rational behavior in competitive situations, then there is such a thing as inverse game theory. Given desired goals, we can design a game such that players motivated solely by self-interest end up achieving desired goals. That is why all design problems become mechanism design problems.
A mechanism design problem is one which has N agents. These agents must make a collective choice from some set X of possible alternatives. However each agent before making a choice privately observes his preferences over the alternatives in X also referred to as his type.
Each agent is expected to be a utility maximizer
#codingexercise
Given a tree and a sum, return true if there is a path from the root down to a leaf, such that adding up all the values along the path is lesser than the given sum.
bool hasPathSum(Node root, int sum)
{
  if (root == NULL)
  {
     return (sum == 0);
  }else
  {
    int newsum = sum - root.data; 
    if (newsum > sum) throw Exception("underflow")
    if ( newsum > 0 && root.left == null && root.right == null)
      return true;
    if(root.left && hasPathSum(root.left, newsum))
       return true;
    if(root.right && hasPathSum(root.right, newsum))
       return true;
    return false;
  }
}
the check for underflow need not throw an exception but just return value

codingexercise
Check if a given array can represent Postorder Traversal of Binary Search Tree
bool IsPostOrder(List<int> post, int i, int j)
{
if (i >= j) return true;
var lesser =  post.GetRange(0, j-1, j-i).ReversedFirst(x => x < post[i]);
if (lesser == null)
    return IsPostOrder(post, i+1, j);
var k = post.IndexOfReverse(j, lesser);
for (int l = k+1; l <j; l++)
     if (post[l] < post[j])
        return false;
return IsPostOrder(post, i, k) && IsPostOrder(post, k+1, j-1);
}

The only thing to change in the code above is the occurrence of root as the last element instead of the first element The same code above can be simplified with the use of a stack similar to the method IsPreOrder

We continue discussing the paper by Papadimitriou  - Algorithms, Games and Internet. We started with Nash equilibrium and then we discussed Internet Equilibria. We viewed the latter in terms of multi commodity flow network where the maximum total flow in a subgraph is in the core of a coalition game. The coalitions are not formed by a central governor.  It is decided locally. But if there were a central authority that allocates bandwidths to individual flows in order to maximize global optimum, then it may be better than the coalition game. This is referred to as the price of anarchy. Next we looked at markets.  Markets are known for price equilibrium. Once an optimum is reached and there is no further reallocation possible to improve, we have a Pareto set of the market. we can improve the efficiency and standardize the transactions with price and currency. All we need is a price per unit of each good. Arrow-Debreu 1953 theorem suggests that there is always a price vector p called the price equilibrium by which the endowments are indeed the best vector of goods.If game theory strives to understand rational behavior in competitive situations, then there is such a thing as inverse game theory. Given desired goals, we can design a game such that players motivated solely by self-interest end up achieving desired goals. In the context of the internet, if an artifact such as a new congestion control protocol, a new caching scheme, a new routing algorithm etc. has a better performance, it does not necessarily mean it will be successful unless there is a path from its introduction to prevalence where it is adopted, implemented and tolerated. That is why all design problems become mechanism design problems.
#codingexercise
Given a tree and a sum, return true if there is a path from the root down to a leaf, such that adding up all the values along the path is greater than the given sum.
bool hasPathSum(Node root, int sum)
{
  if (root == NULL)
  {
     return (sum == 0);
  }else
  {
    int newsum = sum - root.data; 
    if (newsum > sum) throw Exception("underflow")
    if ( newsum < 0 && root.left == null && root.right == null)
      return true;
    if(root.left && hasPathSum(root.left, newsum))
       return true;
    if(root.right && hasPathSum(root.right, newsum))
       return true;
    return false;
  }
}
the check for underflow need not throw an exception but just return value

IPSEC  for Cloud 

“The term spaghetti code is universally understood as an insult. All good computer scientists worship the god of modularity, since modularity brings many benefits, including the all-powerful benefit of not having to understand all parts of a problem at the same time in order to solve it.”  - David Clark, MIT 

Modularity manifests in hardware and software. From small applications to datacenters, there is increasing reorganization for improving modularity. Unfortunately cloud computing is a domain where different vendors, technologies, fabrics, infrastructures and even platforms compete and collaborate with one another. Many private datacenters have evolved by tossing in everything with regard for security almost as an afterthought.  

Fortunately, computer networking evolved in similar competitive environment where standards emerged in virtually every aspect. IPSEC became a framework as opposed to a single protocol or system for providing all the security services. It provided three degrees of freedom. First, it is highly modular, allowing users to select from a variety of encryption algorithms and specialized security protocols. Second, IPSEC allows users to select from a large menu of security services, including access control, integrity, authentication, protection against replay and confidentiality. Third IPSEC allows users to control the granularity with which the security services are applied 
IPSEC =  (     AH      +       ESP     )     +        ISAKMP
               (header)   +      (payload)         (key management)

I argue that the principles of IPSEC can be used to add an additional layer over cloud networking to improve its security by design.  

Moreover I discuss that IPSEC is used directly in Cloud Networking today to secure virtual private networks (VPNs) but we can use its principles for securing native cloud artifacts. 

Finally, I argue that public cloud providers tout security in the form of certifications such as 

ISO 27001 

ISO 27017 

ISO 27018 

SOC 2/3 

FedRAMP 

These certifications evaluate  

1. Infrastructure as a multi-tenant distributed environment 

2. Chunking of data and replicating over multiple systems 

3. Data storage, access and transfer controls 

4. Data centers and their redundancy for robustness and fault tolerance 

5. Authentication and Access  

I argue from the principles based on which the IPSEC was constituted that we could improve these certifications with the following 

1. Modularity 

2. Interoperability 

3. Rules  

Specifically, I want to stress on provable security model. We discuss it from the intruder’s perspective such as how security protocols were designed both from formal as well as cryptographic styles of analysis. A framework that encompasses both aspects, say the modeling capability with the probability and complexity of cryptography, would be more rigorous.
#codingexercise
Given a tree and a sum, return true if there is a path from the root down to a leaf, such that adding up all the values along the path equals the given sum.
bool hasPathSum(Node root, int sum)
{
  if (root == NULL)
  {
     return (sum == 0);
  }else
  {
    int newsum = sum - root.data; 
    if (newsum > sum) throw Exception("underflow")
    if ( newsum == 0 && root.left == null && root.right == null)
      return true;
    if(root.left && hasPathSum(root.left, newsum))
       return true;
    if(root.right && hasPathSum(root.right, newsum))
       return true;
    return false;
  }
}
 the buffer underflow check could return value as false instead of throwing exception

We continue discussing the paper by Papadimitriou  - Algorithms, Games and Internet. We started with Nash equilibrium and then we discussed Internet Equilibria. We viewed the latter in terms of multi commodity flow network where the maximum total flow in a subgraph is in the core of a coalition game. The coalitions are not formed by a central governor.  It is decided locally. But if there were a central authority that allocates bandwidths to individual flows in order to maximize global optimum, then it may be better than the coalition game. This is referred to as the price of anarchy.
Next we look at markets.  Markets are known for price equilibrium.
In a market there are again n agents each of which posseses a non-negative vector of k goods and a concave utility function The agents may all be dissatisfied with their current endowments and there may be a reallocation of the same goods that is higher in everybody's utility. Once an optimum is reached and there is no further reallocation possible to improve, we have a pareto set of the market.
 The market inches towards the pareto set by way of bilateral and multilateral exchanges and bartering but this may come at considerable delay and communication cost. If instead of barter, we use price and currency, we can improve the efficiency and standardize the transactions. All we need is a price per unit of each good. In such a case, the only rational behavior for each agent would then be to sell her endowment ei at these prices and to buy a new vector of goods with the proceeds. However, the goods may not be enough to fill optimum affordable shopping cart for everyone and they may not be only so much that the shelves are left empty with no goods.
Arrow-Debreu 1953 theorem suggests that there is always a price vector p called the price equilibrium such that the market clears which means that the endowments are indeed the best vector of goods.
It was also noted that the price equilibrium may not exist if the goods are integer valued but in such cases, we can get 'approximate in expectation' if the number of goods is fixed.

#writeup on cloud computing : https://1drv.ms/w/s!Ashlm-Nw-wnWqXUqaKP1HX09wuwo

#codingexercise
Given a boolean 2D array, where each row is sorted. Find the row with the maximum number of 1s.
int GetRowWithMax1s(int[,] A, int r, int c)
{
int ret = -1;
int max = int_min;
for (int i = 0; i < r; i++)
{
int index = A[i].indexOf(1); // use binary chop since row is sorted
if (index != -1 && c-index > max)
{
    max = c - index;
    ret = i;
}
}
return ret;
}
static int indexOf(List<int> a, int start, int end)
{
if (a[start] == 1) return start;
if (start == end) {
    if (a[start] == 1)
         return start;
    else
         return -1;
}
int mid = (start + end) / 2;
if (a[mid] == 0)
    return indexOf(a, mid+1, end);
else
   return indexOf(a, start, mid);
}

We continue discussing the paper by Papadimitriou  - Algorithms, Games and Internet. We started with Nash equilibrium and then we discussed Internet Equilibria. We viewed the latter in terms of flow network.We consider a graph of n nodes, an n x n symmetric traffic matrix with the cell values for (i,j) being the total requirements between customers of i and customers of j and a capacity ci. A subgraph of this multi commodity flow network with nodes S, corresponding capacities and v(S) as the maximum total flow in this network are in the core of a coalition game v if their corresponding payoffs for the nodes found by summing over all the subtraffic for all the customers of that node from the new traffic matrix is less than that of the original matrix. The payoff increases with the flow to and from the customers of that node. The core is a form of fairness in the splitting of the initial payoffs among n nodes because no coalition has an incentive to secede because it cannot make more by itself. If we determine such a core and a newer flow matrix, then we have defined an Internet equilibria.
The coalitions are not formed by a central governor.  It is decided locally. But if there were a central authority that allocates bandwidths to individual flows in order to maximize global optimum, how much better would it be ? This is also referred to as the price of anarchy. This can also be considered as the ratio between the worst case Nash equilibrium and the optimum sum of payoffs  The price of anarchy is the price of uncoordinated individual utility maximizing decisions. In the context of multi-commodity flow network in which the message delays increase with edge congestion while flow choose paths so as to minimize delay, the price of anarchy is two which means it is no worse than the optimum solution with double the bandwidth.
#codingexercise
Check if a given array can represent Preorder Traversal of Binary Search Tree
bool IsPreOrder(List<int> pre)
{
var stk = new Stack<int>();
int root = INT_MIN;
for (int i = 0; i < pre.Count; i++)
{
   if (pre[i] < root)
       return false;
   while (!stk.empty() && s.top() < pre[i])
   {
      root = stk.top();
      stk.pop();
    }
   stk.push(pre[i]);
}
return true;
}
or possibly more legible as
bool IsPreOrder(List<int> pre, int i, int j)
{
if (i >= j) return true;
var greater =  pre.GetRange(i+1, j-i).first(x => x > pre[i]);
if (greater == null)
    return IsPreOrder(pre, i+1, j);
var k = pre.IndexOf(i, greater);
for (int l = k+1; l <= j; l++)
     if (pre[l] < pre[i])
        return false;
return IsPreOrder(pre, i+1, k-1) && IsPreOrder(pre, k+1, j)
}