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.

Next we discussed privacy and clustering.  Today we review web-graph. The web graph is considered as a directed graph with the documents as nodes and the hyperlinks as edges. However it violates the principles of classical graph models. For example its indegrees and outdegrees of the nodes are distributed by a polynomial tailed distribution. The xth largest indegree or outdegree is about c.x^(-alpha) where c and alpha are positive instead of the Gaussian predicted by the law of large numbers. Its giant strongly connected components cover only 40% of the nodes instead of all or none. Also, there are scores of K3,3 subgraphs instead of none. A K3,3 graph is a complete bipartite graph of six vertices usually illustrated with two subsets of three nodes and  edges joining every vertex in one subset with another. The deviations from classical graph have prompted many other efforts to model the web graph. However no model comes close to satisfactorily explaination One model called the heavy tailed distributions is interesting because it seems to have parallels in other domains.  The population of xth largest city of any country is cx^(-1) with c depending on country. The market share of xth largest manufacturer in any sector is c.x^(-alpha) A document's indegree is determined by how interesting the document is and intuitively analogous to market share while outdegree depends on the entity's attention which is not very different from income. The heavy tailed distributions are also observed beyond the world wide web such as the degrees of routers and autonomous systems.

#codingexercise
Yesterday we showed that the optimum way of clustering into k segments of a demand curve is O(n^2)
Today we show that this can be done with dynamic programming. If the price is x, the ith customer will buy a quantity y = (bi-ai)x. The k segments are determined by increasing values of ai/bi.
int GetOptimumRevenueDP(int a, int b, int u, int i, int k, List<Customer>customers)
{
if (n == 1){assert(a <= u && u <= b);
            return minimum (Revenue (u,b) + Revenue(a,u));
}
return minimum(Revenue(u,b) + GetOptimumRevenue(a,b,u,n-1,k,customers);
}


Courtesy: https://www.rand.org/content/dam/rand/pubs/research_memoranda/2008/RM2978.pdf

Palindrome partitioning
find the minimum number of partitions for partitioning a string into palindromes.
int GetMinPartitions(String str, int i, int j)
{
if (i ==j ) return 0;
if (IsPalindrome(str.GetRangeBetween(i,j))/ return 0;
int min = int_max;
for (int k = i; k <=j-1; k++)
{
int val = GetMinPartitions(str, i, k) + 1 + GetMinPartitions(str, k+1, j);
if (val < min)
   min = val;
}
return min;
}
all non palindromes have an upper limit for the partitions as the number of characters in the string