The NSE is made up of three neural networks-

• the read layer,
• the write layer
• and the compose layer.

They operate on the encoding memory to perform the namesake operations. The encoding memory is different form the neural network parameters. It is of dimension M ∈ R^k × l where k is the hidden dimension of the representations stored and l is the sequence length. Note: this is a single matrix maintained for all the data points in the set. The memory is initialized by the embedding vectors of the input sequence and is evolved over time. In some cases it is found as expected that the read module produces a key or points to a memory slot same as the input word, in this case they chose the second most probable memory slot as the associatively coherent word.

Important list of vectors -

• x_t ∈ R^k this is the input to the LSTM (word embedding)
• o_t ∈ R^k this is the hidden state (output) produced by the LSTM
• z_t ∈ R^l this is the key vector shared between the read and write module

the read module neural network o_t = f_r^LSTM(x_t)

the key vector z_t is produced by attending over the memory at the previous time step, indicated by the equation z_t = softmax(o_t^TM_t-1) Note: this is essentially a dot product happening between the hidden state and the memory slots to find the most coherently associated memory slot

Sine the key vector is fuzzy the final answer is got by taking a weighted sum of the key vector with all the memory slots, this is indicated by the equation m_r,t = z_t^TM_t-1 This can also be viewed as a soft attention mechanism

The next equations compose and write to the memory slot previously read

In this post I want to guide you to develop intuition and understanding for the longest palindromic substring P_i and ∑_iP_i

Brute force

Using two points i, j we can run down all possible substrings of a string. There would be $N^2$ of them. For each substring we iterate the substring to check if it is a palindrome. This would result in a total worst case complexity of $N^3$

Slightly better approach

Here, we use the insight that a palindrome is symmetric around its centre (for odd length palindromes) and for even this centre is the empty space between the characters. Consider the examples,

“madam” symmetric about ‘d’ “oo” symmetric about

for k in xrange(0, len(str_s)):
  #for odd length palindromes centred around str_s[k]
  i, j, opl = k - 1, k + 1, 1
  while i > 0 and j < len(str_s):
    if str_s[i] == str_s[j]:
      opl++
    i -= 1
    j += 1

  #for even length palindromes
  i, j, epl = k, k+1, 1
  while i > 0 and j < len(str_s):
    if str_s[i] == str_s[j]:
      epl++
    i -= 1
    j += 1

  max_pl = math.max(epl, opl)

FIFO multicast

Basically says that messsages from the same sender are delivered at each receiver in the order in which it was sent from that particular sender, we do not care in what relative order messages from different senders are delivered. Hence, the algorithm

Notation: the vector pi[,,,] denotes the number of events seen so far for each respective index (length of vector equals number of processes in the multicast group)

• When process pj sent a message
  • pj[j] += 1
  • include pj[j] in the multicast message as its sequence number
• When process pi receives a mulicast from pj with sequence number S in message

    if msg.ts == pi[j] + 1:
        deliver msg to application
        pi[j] += 1
    else:
        buffer msg till condition is true
  

Totally ordered multicast

Ensures that all receivers get the messages in the same order i.e. its focus is on the consistency of messages received across all processes in the multicast group. It doesn’t guarentee messages of one sender are received in the same order it was sent.

We use a central sequencer, so first we run a leader election algorithm to choose a sequencer or leader. Then the algorithm,

• When a process Pi wants to send a message
  • Sends the multicast to the group as well as the sequencer/leader
  • Sequencer maintains a global sequence number S initially 0
  • When it receives a message M, it sets S = S + 1 and multicasts <M,S>
• Receive multicast at Pi
  • It maintains a local received global sequence number Si (initially 0)
  • If Pi receives a multicast M from Pj, it buffers it untill
  • Pi receives the multicast <M, S(M)> from the sequencer
  • Si + 1 == S(M)
  • After delivering the message to the application set Si += 1

Causal ordering

Multicasts whose send events are causally related by a causal path, must be received in the same causality-obeying order at all receivers. Formally,

• If send_event_multicast(g,m) -> send_event_mutlicast(g, m’) then any correct process that delivers m’ would already have been delivered m.
• Each process Pi maintains a vector Pi[1..N] whose length equals the number of processes in the multicast group
• Each value of the vector indicates the number of events that Pi has seen occured

When a process Pi wants to send a message

• Sets Pi[i] += 1
• Include the whole vector Pi in the multicast message

When a process Pj receives a message from Pi. It buffers the message untill both

1. Pj is expecting msg.ts[i] as the next sequence from Process Pi

      Pj[i] + 1 == msg.ts[i]
   

2. Receiver Pj satisfies causality which was true at the time of send for Pi

       for k != i
       Pj[k] >= msg.ts[k]
   

    After the above condition is satisfied logical clock needs to be updated before message delivery.
   

   • set Pj[i] = max(msg.ts[i], Pj[i])
   • Before delivery to app layer update self clock Pj[j] += 1
     Note: Causal ordering implies FIFO ordering