Today we take a break to review the mechanics of Active Directory replication:
We are referring to intrasite replication for the most often use cases of Active directory domain name-context item changes. Such AD replication takes place between DCs in pull operations, not pushes.
Each domain controller (DC)  stores three naming contexts (NC)  in its local copy of AD at the minimum. These are schema NC, Configuration NC, and AD Domain NC which corresponds to AD Data.  The last one is usually the one that frequently changes. There are two type of writes - an originating write and a replication write.  Since directory changes can be made from any active directory DC, any one DC can be the originating DC.  AD controls and manages the transmission of AD Data with replication metadata.
The first item of replication metadata is the USN which is the update sequence number and pertinent only locally at a DC to indicate a sequence number associated with the changes at that DC.
The other DCs keep track of these USN for each other. The other DCs are referred to by their GUIDs so that the information does not change when the DC is renamed or offline.
Since an originating change can be come a replicated change for the other DCs and perpetually propagated, the cycle is broken with the help of an indicator called the high watermark vector. This tells apart an originating change from a replicated change and also prevents repeated changes for the same entry.
#codingexercise
Given an array integer k, find the maximum of each and every contiguous subarray of size k
Yesterday we saw a simple but O(n^2) complexity for solving this exercise.
We could also make it linear by keeping track of a list of  candidates in sorted descending manner. As the window moves the numbers smaller than the current number are removed from the tail and the max element from the head is printed. The list keeps track of index only.
void PrintMax(List<int>nums, int k)
{
var sorted = new List<int>();
if ( k < nums.count() || k == 0 || nums.empty()) return;
int I;
for (int I =0; I < k; i++)
{
while (!sorted.empty() && nums[I] >= nums[sorted.Last()]))
      sorted.RemoveLast();
Sorted.InsertLast(I);
}
for (int I = k; I < n; i++)
{
Console.WriteLine(nums[sorted.first()]);
while (!sorted.empty() && sorted.frst() <= I - k)
      sorted.RemoveFirst();
while (!sorted.empty() && nums[I] >= nums[sorted.Last()])
      sorted.RemoveLast();
sorted.InsertLast(I);
}
Console.WriteLine(nums[sorted.first()]);
}

Today we continue our discussion on natural language processing with a particular word ontology called FrameNet. We see how it is different from other ontologies , such as WordNet, PropBank , AMR etc. While AMR introduced graphical model, it did not have the rich semantic grouping that FrameNet had. Now let us look at a specific example of a model that make use of terms in a graphical data structure to see what FrameNet may bring to it. To do that we first look at one such model that does PoS tagging. A similarity graph is constructed and the labels are propagated.  A classifier is trained on prelabeled data. Then it is used to predict the decode the labels from the target domain. We saw how a standard label propagation technique works.
Let us now look at one instance of this classifier as a tagger.
We start with a set of labeled source domain examples that gives pairs of parts of speech labels to inputs and a disparate test data that has yet to be labeled. The input is a sequence of words in the sentence and the output is a sequence of labels. Previous label affects the current label and the current label is independent of the previous ancestors except for the parent. Also the current label is iid. Therefore this is a good candidate for markov chain or a linear CRF. Therefore the goal here is to learn a CRF of the form exponentials of weighted feature functions where the functions range from 1 to K and the inputs range over some window of input sequence. Given only the labeled data, the optimal feature weights are given by the sum of conditional probabilities with respect to a specific set of feature weights and some adjustment based on a trade-off parameter and a regularizer. This we can decide based on training data. The regularizer helps with guiding the learning process.  The CRF is based on conditional distributions and not on the actual probabilities of the inputs. So we cannot rely on the untrained data. That is why we use a regularizer and the graph comes in useful as a smoothness regularizer. Subramanya et al use this technique to train the CRF. They take a set of CRF parameters, first compute the marginals over the untrained data which is simply the conditional distribution in this iteration over all the data.  The marginals over tokens are then aggregated to the marginals over types, which are used to initialize the graph label distributions. The labels are then propagated. The posteriors from the graph are then used to smooth the state posteriors. 
A posterior is a conditional distribution. While the prior represents the uncertainty over our choice parameter before we have sampled the data, the posterior represents the uncertainty over our choice parameter after we have sampled the data and attempted to estimate it. Prior is regular probability while the posterior is conditional probability distribution because it conditions over the observed data.
The unlabeled data then produces a new set of automatic annotations that can be combined with the labeled data to retrain the CRF.
#codingexercise
Given an array integer k, find the maximum of each and every contiguous subarray of size k
List<int> GetMaxForWindows(List<int> nums, int windowSize)
{
var ret = new List<int>();
for (int i =0; i <= nums.Count - windowSize; i++)
{
max = nums[i];
for (int j = 1; j < windowSize; j++)
{
   if (nums[i+j] > max)
       max = nums[i+j];
}
ret.Add(max);
}
return ret;
}

Today we continue our discussion on natural language processing with a particular word ontology called FrameNet. We see how it is different from other ontologies , such as WordNet, PropBank , AMR etc. While AMR introduced graphical model, it did not have the rich semantic grouping that FrameNet had. Now let us look at a specific example of a model that make use of terms in a graphical data structure to see what FrameNet may bring to it.  To do that, we consider building a classifier could be build that creates lexical units for FrameNet frames and maps terms or senses to their corresponding FrameNet Frames.
Let us first look at one such model that does POS tagging with the help of graphs. It relies on the assumption that similar words will have similar Part of Speech tags.  A similarity graph is constructed and the labels are propagated.  Data both labeled and unlabeled is represented by vertices  in a graph. Graph edges link vertices that are likely to have the same label. Edge weights determine how strongly the labels agree. Usually the number of labels are small. And even smaller are the labels that are composites. The number of atomic labels may be small but there may be much large number of ways to combine them.  One way to combine them would be to structure them as a tree.
A classifier is trained on prelabeled data. Then it is used to predict the decode the labels from the target domain. The classifier which here can also be called a tagger can be based on any suitable model. For example, it can be based on word matrices. However computations for large matrices do not scale well especially if there are inversions involved. On the other hand conditional random fields are better suited for these purposes. They scale well because they use only conditional probability distributions. Standard inference and learning techniques as well as standard graph propagation technhiques are also scalable.  The building blocks for the CRF inference could contribute to the efficiency.
The label propagation works like this:
Initialize the labels at all nodes in the network. For a given node, the label at start is the initialization label.
Set the iteration to 1
Take the nodes in a random order and assign it to a list
For each node in that list, use a function to assign the labels from all those adjacent to that node from the assignments in the previous iteration. For example, this could be the most frequently occurring label among the adjacencies.
If every node satisfies the chosen function, stop the algorithm or repeat with the next iteration.

#trivia question
What is a keep-alive header ?
The keep-alive header provides connection use policies. It's a hop by hop header that provides information about a persistent connection. It includes a timeout that determines how long a connection can be idle before it is closed. 

Today we continue our discussion on natural language processing with a particular word ontology called FrameNet. We see how it is different from other ontologies , such as WordNet, PropBank etc. One such was AMR which had extensive documentation. It had PropBank predicate-argument semantics. It had name and value entities with entity linking. Entities and events formed coreference.
It included modality, negations and questions. It had relations between nominals. The content words were canonicalized. It would convert adverbs to adjectives to noun to verbs wherever possible. Moreover it represented all of this in a single graph. AMR Assets is a snazzy annotation tool that comprised of 15,000 AMRs which is roughly 270K words released with another 5000 AMRs or 150K words annotated and in the pipeline. AMR differed from FrameNet in that it's purpose was cost effective annotation together with NLP as opposed to FrameNet's lexicography. FrameNet frames was about rich semantic groupings while AMR retained PropBank's lexicalized rolesets. FrameNet annotated by using labeled spans in sentences. AMR was represented by graph where sentences and words  did not directly translate to nodes. A sentence does not have any explicit relationships across frame annotations in FrameNet where as AMR comprised of predicates with shared arguments.
We note here the functionality of the FrameNet and the advantages of the form of AMR. In general, there are many ways to come up with an ontology or pseudo ontology for different purposes, however a graph based data structure where the nodes are not necessarily terms only comes helpful in many cases.  Further a lookup of each term to such graph nodes also helps with directly representing models over the graph nodes instead of terms with more static pre-discovered relationships available for incorporation in the models.

#puzzle
Prove that for every prime p greater than 3, the value p ^ 2 - 1 is a  multiple of 24.
p ^2 -1 can be written as (p-1)(p+1)
Since p is prime both the components above are even. So they must each be divisible by 2.
Further they are consecutive even numbers, therefore they should be divisible by 4 as well. So we have factors 2 x 2 x 2
Next p-1, p and p+1 are three consecutive numbers, hence they must be divisible by 3. We know p is not divisible, therefore this must be p-1 or p+1. This gives us 3 as a factor.
Consequently the factors are 2 x 2 x 2 x 3 = 24 for all p > 3.

#codingexercise
Find power x, n with logarithmic time complexity and limited storage
int power( int x, uint n)
{
int result = 1;
while (n > 0)
{
   if (n & 1)
      result = result * x;
   n = n >> 1; // reduce n by half
   x = x * x;
}
return result;
}



This can be made recursive as well but it wont be storage efficient.

Today we continue our discussion on natural language processing with a particular word ontology called FrameNet. We see how it is different from other ontologies. For example, FrameNet differs from WordNet in the lexical information and is in fact, complimentary in many ways. FrameNet has far fewer nouns, verbs, adjectives and adverbs as compared to WordNet. FrameNet Frame hierarchies provide better generalizations than WordNet synset hierarchies.
FrameNet also differs from PropBank (Proposition Bank discussed by Palmer et al 2005). PropBank began with labeling verbs and their arguments.
FrameNet assigns names such as communicator, evaluee and reason for corresponding PropBank role labels.
There have been other works to represent semantic information such as Abstract Meaning Representation ( Banarescu et al, Law 2013). AMR is a graph based representation of lexical concepts and typed relations between those concepts that are denoted by an English sentence.
However the lexical semantics in FrameNet are much deeper than AMR
What AMR means for Framenet and for our use is that we can represent the Frames in a graph where the relationships are persisted. These edges can then be traversed.  Previously we used graphs with edges established based on similarity measures. Here we establish edges based on the relationships between frames.

#codingexercise
Find the number of islands of 1 in a binary matrix comprising of 0 and 1. In other words, count the number of connected components in an undirected graph.
int GetCountOfIslands(int[,] m, int row, int col)
{
bool visited = new bool[row,col]; // initialized to False
int count = 0;
for (int I = 0; I < row; I ++)
   for (int j = 0; j < col; j++)
       if (m[i.j] == 1 && visited[i,j] == False)
      {
             DFS(m, I, j, visited);
             count++;
      }
 return count;
}
int DFS(int[,] m, int row, int col, bool[,] visited)
{
var radj = new int[] {-1, -1, -1,  0, 0,  1, 1, 1};
var cadj = new int[] {-1,  0,  1, -1, 1, -1, 0, 1};
visited [row,col] = true;
for (int k  = 0; k < 8; k++)
   if (withinMatrixAndNotVisited(m, row + radj[k], col + cadj[k], visited))
      DFS (m, row + radj[k], col + cadj[k], visited);
}
We can also measure the size of each island with a minor modification to above.

Today we continue our discussion on natural language processing with a particular word ontology called FrameNet. We see how it is different from other ontologies. For example, FrameNet differs from WordNet in the lexical information and is in fact, complimentary in many ways. FrameNet has far fewer nouns, verbs, adjectives and adverbs as compared to WordNet. FrameNet Frame hierarchies provide better generalizations than WordNet synset hierarchies.
FrameNet also differs from PropBank (Proposition Bank discussed by Palmer et al 2005). PropBank began with labeling verbs and their arguments.
FrameNet assigns names such as communicator, evaluee and reason for corresponding PropBank role labels.
There have been other works to represent semantic information such as Abstract Meaning Representation ( Banarescu et al, Law 2013). AMR is a graph based representation of lexical concepts and typed relations between those concepts that are denoted by an English sentence.
However the lexical semantics in FrameNet are much deeper than AMR
What AMR means for Framenet and for our use is that we can represent the Frames in a graph where the relationships are persisted. These edges can then be traversed.  Previously we used graphs with edges established based on similarity measures. Here we establish edges based on the relationships between frames.

#codingexercise
Find the number of islands of 1 in a binary matrix comprising of 0 and 1. In other words, count the number of connected components in an undirected graph.
int GetCountOfIslands(int[,] m, int row, int col)
{
bool visited = new bool[row,col]; // initialized to False
int count = 0;
for (int I = 0; I < row; I ++)
   for (int j = 0; j < col; j++)
       if (m[i.j] == 1 && visited[i,j] == False)
      {
             DFS(m, I, j, visited);
             count++;
      }
 return count;
}
int DFS(int[,] m, int row, int col, bool[,] visited)
{
var radj = new int[] {-1, -1, -1,  0, 0,  1, 1, 1};
var cadj = new int[] {-1,  0,  1, -1, 1, -1, 0, 1};
visited [row,col] = true;
for (int k  = 0; k < 8; k++)
   if (withinMatrixAndNotVisited(m, row + radj[k], col + cadj[k], visited))
      DFS (m, row + radj[k], col + cadj[k], visited);
}

Today we continue our discussion on natural language processing with a particular word ontology called FrameNet. We see how it is different from other ontologies. For example, FrameNet differs from WordNet in the lexical information and is in fact, complimentary in many ways. FrameNet has far fewer nouns, verbs, adjectives and adverbs as compared to WordNet. This is because FrameNet has very little to say about common nouns. WordNet has noun hierarchies and encompasses common nouns. WordNet has little syntagmatic information where as FrameNet has a lot.
WordNet separates hiearchy for Nouns, Verbs, Adjectives and Adverbs. Each Frame on the other hand can conver words of any part-of-speech. WordNet has hypernymn or hyponymn relations between synsets. Lexical units come close to synsets but there  are no relations per se between lexical units. However, there are several types of frame relations.  There are also content differences between the two. WordNet has annotated examples showing syntax and semantics of each LU.  FrameNet describes Frame Elements or roles for each frame. FrameNet Frame hierarchies provide better generalizations than WordNet synset hierarchies.
FrameNet also differs from PropBank (Proposition Bank discussed by Palmer et al 2005). PropBank began with labeling verbs and their arguments. PropBank uses Penn POS tags, Penn Tree Bank parse structures. It added nouns and roles from associated verbs. This includes an efficient semantic role labeling system but there is no equivalence to frames in FrameNet. There are two levels of role labels - those that are completely general and those that are specific to lexical unit. The lemmas from text are split into sequences that carry equivalence between PropBank verb specific and FN FE names. FrameNet assigns names such as communicator, evaluee and reason for corresponding PropBank role labels.
There have been other works to represent semantic information such as Abstract Meaning Representation ( Banarescu et al, Law 2013). AMR is a graph based representation of lexical concepts and typed relations between those concepts that are denoted by an English sentence. It integrates several aspects of lexical/relational meaning - abstracting away  from the grammatical details - in a single structure. This structure specifically helps with rapid corpus annotation and data driven NLP. However the lexical semantics in AMR are much shallower than FrameNet
Courtesy : Colin Baker FCSI
In general, it seems to be helpful to have a hash between a term and a corresponding ontology identifier
#codingexercise
Insert into a circular linked list that is sorted but where we are given a random node from the list not the head.
// start is a random node in the sorted circular list

Void insertCircular(ref node start, node target)

{
var head = start;
If (head == null) {head = target; target.next = target; return;}
Node prev = null;
Node curr = head;
Max = int_min;
Var pos = null;
Var prevpos = null;
while(curr.next != head){
If (curr.data > max && cur.data  < target.data ){
Prevpos = prev;
Pos = curr;
Max= curr.data;
}
    Prev = curr;
    Curr = curr.next;
    }

If (curr.data > max && cur.data  < target.data ){
Prevpos = prev;
Pos = curr;
Max= curr.data;

}
 If (pos == null){
    If (head.data < target.data){
         InsertAt(head, target);
    }else{
         InsertAtStart(head, target);
     }
 }else{
   if (pos.data < target.data) {
        InsertAt(pos, target);
   }else{
        InsertAt(prevpos, target);
   }
 }
}
Int rowWithMaximum1sInSortedMatrix(int[,] m)
{
Int max = int_min;
Int index = -1;
For (int i = 0; i < m.rows; i++)
{
int col = findfirst(m, i, 0, m.cols-1, 1);
If (col != -1 && m.cols - col > max)
{
   Max = m.cols -col;
    Index = i;
}
}
Return index;
}
The findfirst method is a binary search method.

Today we continue our discussion on natural language processing with a particular word ontology called FrameNet. The idea behind FrameNet is that the definition of a word is incomplete without the relations to conceptual structures and patterns of beliefs, practices, institutions, images etc. which are referred to as semantic frames. - courtesy Filmore 2003. Therefore meanings are relative to Frames. The scope of FrameNet includes Events: for example related to birth or death as noun, Relations: for example being relevant as in adjective or in a personal relationship as in a noun, States: for example on or off as in preposition, and Entities: for example a device. Therefore the words are related to notions that are represented by frames and the meaning is not complete without these relationships. A Semantic Frame is the description of an event, relation, entity or state and its participants thereby capturing the essential knowledge of a given word sense. Roles within the frame are called Frame Elements. Words that evoke the frame are called Lexical units. For example cooking appears in a frame called 'Apply_heat' where the frame elements are the cook, food, container and heating_instrument. and words that evoke it such as fry, bake, boil and broil are lexical units.
FrameNet comprises of over 1195 Semantic frames with approximately 12 frame elements per frame. It includes12,989 lexical units which represent connection between one lemma + POS and one frame. It includes 198,932 manual annotations of corpus examples and about 1774 frame to frame relations. Since the relations involve multiple inheritance, it forms a lattice. It is also constructed bottom-up. It comes with semantic type labels such as animate, human, positive_judgement and assumes construction grammar which describe the grammatical characteristics and semantic import of each construction ( Filmore, Goldman, Rhodes ). It also includes metaphor and metonymy.
FrameNet is not a formal ontology. It includes non-lexical frames that have been made up as needed to connect the nodes in certain cases. It attempts to include cross linguistic differences such as the difference between commercial_transaction versus a criminal_process although both describe methods.
Why is it an improvement over semantic ontologies ?
1) Frame is a useful level of abstraction
2) Roles are more meaningful than semantic labels
3) Frames represent conceptual gestalts - more than just the sum of their parts.

#codingexercise
Insert into a circular linked list that is sorted but where we are given a random node from the list not the head.

Void insertCircular(ref node start, node target)

{
var head = FindHead(ref node start, node target);
If (head == null) {head = target; target.next = target; return;}
Node prev = null;
Node curr = head;
while(curr.data < target.data && curr.next != head){
    Prev = curr;
    Curr = curr.next;
    }
 If (prev == null){
    If (curr.data < target.data){
         InsertAt(cur, target);
    }else{
         InsertAtStart(head, target);
     }
 }else{
   if (curr.data < target.data) {
        InsertAt(cur, target);
   }else{
        InsertAt(prev, target);
   }
 }
}

Node FindHead(ref node start, node target)
{
Node head = null;
if (start == null) return head;
If (start.next == start) return start;
Node curr = start;
min = curr.data;
head = start;
while(curr.next != start){
    if (curr.data < min)
    {
         head = curr;
         min = curr.data;
    }
    curr = curr.next;
}   
 if (curr.data < min)
    {
         head = curr;
         min = curr.data;
    }
return head;
}
Alternatively, we could also insert by iterating the circular list once to find the node that is closest to the given node in its value.

Today we continue our discussion on natural language processing with a particular word ontology called FrameNet.
Framenet is a lexical database maintained by Berkeley.
It has the following features:
It has annotations about how words are  used in actual text.
It can be used like a dictionary.
It has over 170000 annotated sentences describing word usage
It provides a unique training data set
It is both human readable and machine readable.
The data is freely available to download.
The annotations show how words have unique combinations.
FrameNet defines the idea that words have a meaning based on the presence of a semantic frame.  This is a type of event, relation or entity and the participants in it. The example cited is that of cooking. The concept of cooking typically involves a person doing the cooking (cook) and the food that is cooked (food) and something to hold (container) along with a source of heat (heating instrument) This is represented as a frame called 'Apply_heat' where the frame elements are the cook, food, container and heating_instrument. The frame units then naturally fit as superimposed on the words that evoke them.
The frame units help with both semantic and syntactic relationships. As such they are better representations than terms themselves while allowing the models based on those terms to work as before, if not improved with the frame elements.

#codingexercise

Insert a node into a sorted circular linked list

Void insertCircular(ref node head, node target)

{

If (head == null) {head = target; target.next = target; return;}

Node prev = null;

Node curr = head;

while(curr.data < target.data && curr.next != head){

    Prev = curr;

    Curr = curr.next;

    }

 If (prev == null){

    If (curr.data < target.data){

         InsertAt(cur, target);

    }else{

         InsertAtStart(head, target);

     }

 }else{

   if (curr.data < target.data) {

        InsertAt(cur, target);

   }else{

        InsertAt(prev, target);

   }

 }

}

void InsertAt(ref node head, ref target)

{

// Insert After head

var next = head.next;

target.next = next;

head.next = target;

}

#codingexercise
Print all nodes at a distance k from a given node
void printKDistanceDown(Node root, int k)
{
if (root == null || k < 0) return;
if (k == 0)
   Console.Write(root.data);
printKDistanceDown(root.left, k-1);
printKDistanceDown(root.right, k-1);
}

// returns distance of root from target
int PrintKDistanceNode(Node root, Node target, int k)
{
if (root == null) return -1;
if (root == target){printKDistanceDown(root, k); return 0;}
int dl = printKDistanceNode(root.left, target, k);
if (dl != -1)
{
   if (dl + 1 == k)
       Console.Write(root.data);
   else
       printKDistanceDown(root.right, k -dl-2);
   return 1 + dl;
}
int dr = printKDistanceDown(root.right, target, k);
if (dr != -1)
{
      if (dr +1 ==k)
         Console.Write(root.data);
      else
          printKDistanceDown(root.left, k-dr-2);
      return 1+dr;
}
return -1;
}

2. Given a string, recursively remove adjacent duplicate characters from string. The output string should not have any duplicates.
For eg: abcdaadhhhhhzppzl
becomes abchl
 static String RemoveDuplicate(StringBuilder str, int n)
        {
            for (int m = 0; m < int.MaxValue; m++)
            {
                bool modified = false;
                int k = 0;
                int len = str.ToString().Length;
                if (len == 0) return str.ToString();
                for (int i = 0; i < len; i++)
                {
                    if (k == 0) {
                        str[k] = str[i];
                        k++;
                        continue;
                    }
                    if (str[k] == '\0' || str[i] != str[k-1])
                    {
                        str[k] = str[i];
                        k++;
                    }
                    else
                    {
                        k--;
                        str[k] = '\0';
                        modified = true;
                    }
                }
                if (!modified)
                    break;
                str[k] = '\0';
                k++;
                for (int i = k; i < len; i++)
                    str[i] = '\0';
                Console.WriteLine("val =" + str.ToString());
            }
            return str.ToString();
        }

#codingexercise
Flatten out a linked list with child and next pointers
void Flatten(Node head)
{
if (head == null) return;
Node temp;
Node tail = head;
while (tail.next)
     tail = tail.next;
Node cur = head;
while ( cur != tail)
{
if (cur.child && cur.child.visited == false)
{
tail.next = cur.child; // this goes to the tail
tmp  = cur.child;  // tail is updated
tmp.visited = true;
while (tmp.next)
  tmp = tmp.next;
  tmp.visited = true;
tail = tmp;
}
cur = cur.next;
}
}
#probability question
A fair die is thrown k times. What is the probability of sum of k throws to be equal to a number n?
void FairThrow(int k, int n, ref int current, ref int sum, ref int count, ref int total)
{
 if (current == k) {
      total += 1;
      if (sum == n) { count +=1;}
      return;
}
 for (int i = 1; i <=6; i++)
 {
         sum+= i;
         current += 1;
         FairThrow( k, n, current, sum, count);
         sum -= i;
         current -= 1;
 }
}
Probability = count/total;

Today we continue to discuss the conditional random fields we mentioned earlier.We have seen some generalized discussion about what random fields are, their benefits, their representations, the objective functions and their optimizations including techniques such as CG method which ties in things we have previously studied for the purposes of text analysis. We wanted to introduce sense embedding features into the word-context analysis. We can represent the conditional probability of a sense given its context using their corresponding vectors. Then we choose the parameters numbering 1..d for each of the context, semantic pairs. We would like to set the parameters such that their conditional log likelihood is maximized. We could do this with conjugate gradient method.
We saw linear chain CRFs. Now we could generalized this and the relax the requirements for previous state dependency.  Instead we define CRFs with general graphical structure. Such structures are found to be very helpful for relational learning because they relax the iid assumption between entities.
So far we have seen that models CRF included have been applied with training and testing data to be independent. However CRFs can also be used for within-network classification - one where we can model probabilistic dependencies between training and testing data. The generalization from linear chain CRFs to general CRFs is about moving from a linear chain factor graph to a more general factor-graph.
The general definition of the conditional random field is presented this way:  Let G be a factor graph over Y. Then p(y|x) is a conditional random field if for any fixed x, the distribution p(y|x) factorizes according to G. Therefore each conditional distribution is a CRF even though  it may be trivial. If F is a set of factors in G where each factor takes the exponential form, then each conditional distribution can be written in the form of exponential of weighted feature functions normalized by a partition function similar to what we have seen before except that they apply to each factor in the set F.
Models usually depend on parameter tying. For example, in the linear chain case, the same weights are used for the factors at each time step. This maintains the parameters between the transition. The same applied to a general model and not just a chain model.  To do the same, the factors of G are partitioned into C = C1, C2, .... Cp where each Cp is a clique template whose parameters are tied. A clique template is a set of factors which has a corresponding set of sufficient statistics and parameters. Then the weighted feature functions in the general definition can be replaced by a combination of the sufficient statistics and their parameters.
#codingexercise
Find the position of an element in a sorted array of infinite numbers:
int GetPosition(List<int> nums, int val)
{
int low = 0;
int high = 1;
int cur = nums[0];
while (cur < val)
{
low = high;
high = 2 * high;
val = nums[high];
}
return binarysearch(nums, low, high, val);
}

Void binarysearch(list<int> nums, int low, int high, int val)
{
Int mid = (low + high)/2;
If (nums[mid] == val) return mid;
If (low == high) return -1;
If (nums[mid] < val)
    Return binarysearch(nums,mid+1,high,val);
Else
     Return binarysearch(nums,low,mid,val);
}

Today we discuss a specific automation issue. This pertains to authentication:

We explain a difference between a JWT digest token and an HMAC hash:

We construct a JWT token this way:

    def data_to_sign(endpoint, environment, owner):

        banner = '{"alg":"SHA256withRSA","kid":"' + environment + '"}'

        banner = base64.b64encode(banner)

        start = int(datetime.datetime.now().strftime("%s"))*1000

        end = datetime.datetime.now() + datetime.timedelta(seconds=300)

        end = int(end.strftime("%s"))*1000

        expiration = '{"iss":"' + environment + '","nbf":' + str(start)  + ',"sub":"' + owner  + '","exp":' + str(end) + ',"aud":"' + endpoint + '"}'

        expiration = base64.b64encode(expiration)

        data_to_sign = banner + "." + expiration

        return data_to_sign

    def signature(endpoint, environment):

        data = data_to_sign(endpoint, environment)

        unpacked = data.split('.')

        unpacked[0] = base64.b64decode(unpacked[0])

        unpacked[1] = base64.b64decode(unpacked[1])

        unpacked = unpacked[0]+"."+unpacked[1]

        with open('./pem/file.txt', 'w') as f:

             f.write(unpacked)

        cmd = 'openssl  dgst -sha256 -sign ./pem/privateKey.key  -out ./pem/signature.sign ./pem/file.txt'

        cmd_execute(cmd.split())

        digest = ''

        with open('./pem/signature.sign', 'rb') as f:

             digest = base64.b64encode(f.read())

        cmd = 'openssl  dgst -sha256 -verify ./pem/privateKey.pub  -signature ./pem/signature.sign ./pem/file.txt'

        output = self.cmd_execute(cmd.split())

        # output says 'Verified'

        auth = data_to_sign + "." + digest

        return auth

       PyJwt encapsulates something similar with the following syntax:
       import jwt

       jwt.encode({'some': 'payload'}, 'secret', algorithm='HS256')

       The auth goes in the Authentication header field of the https request

We construct an HMAC token this way:
        def auth(KeyId, timestamp, token, SomeSecret):

                HMAC_KEY =  SomeSecret.decode('hex')

                CanonicalizedResource = 'timestamp=' + timestamp + '&' + 'token=' + str(token)

                StringToSign = CanonicalizedResource

                Signature = base64.b64encode(

               hmac.new(

                    HMAC_KEY,

                    StringToSign,

                    hashlib.sha256

                    ).digest()

                )

                auth = KeyId + ":" + Signature

                return auth

#codingexercise
Find the longest consecutive subsequence in a sequence

Use a hash table and add all elements in the sequence.

For every element check if it is a start of subsequence, previous one does not occur.

Count the length from each subsequence.

Return the max of the counts.

int GetLMS(List<int> digits)
{
var h = new Hashtable<int>();
for (int i = 0; i < digits.count; i++)
   if h.Contains(digits[i])
      h[digits[i]]++;
   else
      h[digits[i]] = 1;
int max = 0;
for (int i = 0; i < digits.count; i++)
{
  if (h.Contains(digits[i]-1) == false)
  {
      int count = 0;
      for (int j = digits[i]; h.contains(j); j++)
            count++;
      if (count > max)
          max = count;      
   }
}
return max;
}

Trivia question:

The question is why does net ads join fail with  ads_sasl_spnego_gensec_bind ? Hint: is this a kerberos failure.

Local only Automation scripts

We discussed my some automation ideas yesterday by enabling platform specific api servers .
This is not complete without mentioning that APIs don't take the emphasis away from host specific actions and should remain as instance specific as possible. As an example use case, if we want to make the settings of a virtual machine to depend on the attributes of the virtual machine, we need not fetch it from an external data source but instead rely locally on the filesystem of the virtual machine such as when we read version or release. In windows, even Powershell is required to be local only and remote execution is not turned on by default. While this is done mainly for security and automation is internal such that security is not a primary concern, it is still good practice to observe local only execution.
We cite this self reliance example as a way to minimize code which is the hallmark of any good automation. In addition, it improves self sufficiency, reduces maintenance and the complicated requirements for cross platform operations.

#codingexercise
Given an initial and final arrangement of digits of a number, count the nunber of shifts. Assume all different digits

Int getShifts(list<int> initial, list<int> final)
{
Var common = final.GetLCS(initial);
Var diff = final.except(common);
Int sum = 0;
Foreach(var digit in diff)
{
Int i = initial.indexOf(digit);
Int j = final.indexOf(digit);
sum += math.abs(i-j);
}
Return sum;
}

LCS-LENGTH(X, Y)
m = X.length
n = Y.length
initialize b[m,n] and c[m,n] as new tables
for i = 1 to m
     c[i, 0] = 0
for j = 0 to n
     c[0,j] = 0
for i = 1 to m
      for j = 1 to n
            if xi == yi
               c[i,j] = c[i -1, j-1] + 1
               b[i,j] = up-left
            elseif c[i-1,j]  >= c[i, j-1]
               c[i,j] = c[i-1, j]
               b[i,j] = up
            else c[i,j] = c[i,j-1]
               b[i,j] = left
return c and b

and we print the LCS as
PRINT-LCS(b, X, i, j)
      if i == 0 or j == 0
        return
      if b[i,j] == up-left
         PRINT-LCS(b, X, i-1, j-1)
         print xi
      elseif b[i,j] == up
        PRINT-LCS(b, X, i-1, j)
      else PRINT-LCS(b,X, i,j-1)

APIs on Windows:

Why does this matter to you ?

If you are aware of just how much automation you use, you will want to see more on the horizon and the impact that you can make. If not, you are welcome to skip this for now.

On the Linux world Automation relies on shell scripts often invoked with SSH. On the Windows side, the Powershell is in the works on adding SSH support. And there is very little cross platform support but organizations have inventory and core functionalities deployed on both platforms  Therefore, more and more automation now relies on microservice APIs for programmatic and shell based access (think curl commands) to features  that are not limited to the current host.   In this regard, there are several APIs available for external services but very few for the operating system. Most of the tasks on the operating systems are done via local or remote shell scripts.

Not any more, APIs serve as  a conduit to invoking scripts locally and remote and for programmatic access anywhere. A large part of any organizations  offerings are automations that are built on microservice APIs. Today we expand that to include Runtime APIs such as those available in .Net world for access and control of the entire Windows ecosystem.

Why Windows ?

Virtually every component of Windows is available for programmatic access via APIs that can be called natively in .Net languages or Powershell scripts. However, functionality to execute it has always been limited because there is usually limited support for cross platform access. For example, running an SSH server for executing client called scripts on a windows box has not been easily available on Windows.

Not any more, we now have availability to execute automation in any .Net language on the windows world with access to such things as Active Directory, DNS, Firewall, etc. We are now able to execute  scripts against centrally managed organizational infrastructure.

What does it involve ?

It involves writing .Net code automation that can run on windows server and can be called by APIs directly from clients. This is slightly different from installing an SSH server on a Windows box to be able to listen to commands over the wire. Although that is also possible to increase the impact and reach of automation, the native API servers running on Windows Boxes can make use of SDKs from all parts of Windows ecosystem as well as execute scripts and command-lets locally on the windows box.

Why do we need our own API server when there are test automation infrastructure ?

True, there's Chef, SaltStack and many other automation infrastructures that claim to give seamless experience over both platforms - Windows and Posix family however they rely on the scripts and automations being authored and executed. Its these we want to add and increase directly in more maintainable, unit-tested, and source control governed automation assets. And yes if there is some functionality out of the box, we will prefer it but often automation is about integration and steps targeted on specific platforms. This is about Windows as invoked from Posix platforms.

 As an example : https://github.com/ravibeta/csharpexamples/tree/master/WindowsExports

#codingexercise
Take n=43592169 and k=5
1st swap: 43952169
2nd swap: 49352169
3rd swap: 94352169
4th swap: 94532169
5th swap: 95432169 :- final number.
Given a number with the final and initial arrangement of its digits, we find the ones that are out of sequence from the original and sum the number of shifts each has made to get the total number of swaps done between initial and final states.