Resolve left-rescursion Can anybody give me a hint on how to get rid of the left recursion in the following grammar?

$$A \rightarrow B \mid a$$
$$B \rightarrow b \mid C \mid D \mid E \mid F \mid G$$
$$C \rightarrow c \mid A d$$
$$D \rightarrow A e \mid f$$
$$E \rightarrow g \mid B h$$
$$F \rightarrow i \mid A j \mid k$$
$$G \rightarrow l \mid A m \mid n$$

So far I've tried this algorithm and this tool. But both are only applicable for smaller grammars and provide practically unusable results (1000's of rules).

This explanatory part can be skipped :

Non-terminal in a Context-Free Grammar can be interpreted as standing
for the set of strings they generate (this is actually one standard
interpretation of CF grammars as string set equations).

For example $A \rightarrow C \mid D \mid a$ may be read as a set
equation $A = C \cup D \cup \{a\}$ where $A$, $C$ and $D$ now stand
for sets of strings and {a} for a singleton set containing the
string "$a$".

Algebraic properties of concatenation and set union on strings and
string sets can be used to transform grammars. In particular, you can
use factorization in ways that are similar to what you do in
arithmetics to make formulae simpler to compute.

Typically, if $A$, $B$ and $C$ are string sets (possibly reduced to a
simgleton, i.e. a single string), then $(A \cup B)C = AC \cup BC$,
i.e. concatenation is distributive for set union, like product is for
sum.

How to do it

So, when you transform a CF grammar, you can first reduce the size
with factorization. For that, you may replace some non-terminals by the
right-hand-side of their defining rule, or introduce new non-terminals
when convenient.

$A \rightarrow C \mid D \mid a$
$C \rightarrow c \mid A d$
$D \rightarrow A e \mid f$

can be rewritten as

$A \rightarrow X \mid a$
$X \rightarrow AY \mid Z$
$Y \rightarrow d\mid e$
$Z \rightarrow c\mid f$

There are various ways of using this, but you should be able to use it
to do away with the complexity of your grammar.

I deliberately did not make it as simple as I could have. My purpose
is only to give you an idea of what can be done.

The correctness of transformations can also be proved directly on
derivations, without having to consider interpretations on string sets
as I did above.

Complete solution

Here is a suggested answer. Hoping to simplify presentation, I used
extended context-free notation that allows for regular expressions on
the right-hand side (RHS) of rule. It does not change the practical uses and
properties of CF grammars. You can do it as well by introducing new
non-terminals. This was not really necessary here, but I found it
convenient while doing the transformations. In retrospect, it would be simpler without it.

With this convention the rule $X\rightarrow Y\mid Z$ is equivalent to
$X\rightarrow Y+Z$.  Essentially the operators ¨$+$" and ¨$\mid$" have
the same role.

Starting with your grammar, I first eliminate some non-terminals by
replacing them by the corresponding RHS. I do that in the rule for $B$,
and it gives:

$A\rightarrow B \mid a$
$B\rightarrow (b+c+f+g+i+k+l+n) \mid A(d+e+j+m) \mid Bh$

Then, substituting $A$ by the RHS of its rule:
$A\rightarrow B \mid a$
$B\rightarrow (b+c+f+g+i+k+l+n) \mid (B+a)(d+e+j+m) \mid Bh$

and simplifying

$A\rightarrow B \mid a$
$B\rightarrow (b+c+f+g+i+k+l+n) \mid a(d+e+j+m) \mid B(h+d+e+j+m)$

And going back tu usual CF notation:

$A\rightarrow B \mid a$
$B\rightarrow BX \mid Y$
$X\rightarrow h \mid U$
$U\rightarrow d\mid e\mid j\mid m$
$Y\rightarrow aU \mid V$
$V\rightarrow b\mid c\mid f\mid g\mid i\mid k\mid l\mid n$

Now you only have to remove the left recursion from the $B$ rule in
the usual way, replacing it by:

$B\rightarrow Y \mid YH$
$H\rightarrow X \mid XH$

and you are set.


What is instruction throughput and instruction latency? I was reading an article on an alternative method of modulo reduction and i couldn't understand the following excerpt (Those in bold) :

"A single 32-bit division on a recent x64 processor has a throughput of one instruction every six cycles with a latency of 26 cycles. In contrast, a multiplication has a throughput of one instruction every cycle and a latency of 3 cycles."

Latency = time from the start of the instruction until the result is available. If your division has a latency of 26 cycles, and you calculate (((x / a) / b) / c), then the result of the division by a is available after 26 cycles. That's when the division by b can start, with the result available after 52 cycles, and the result of dividing by c is available after 78 cycles.

The throughput is one division every six cycles, which means you can start another division every six cycles. So if you want to calculate x/a, y/a, z/a, u/a, v/a, the five divisions can start at cycles 0, 6, 12, 18, 24, and the results are available at cycles 26, 32, 38, 44, and 50.

As an exercise, figure out how long it takes to evaluate (((x / a) / b) / c), (((y / a) / b) / c), (((z / a) / b) / c), (((u / a) / b) / c) and (((v / a) / b) / c) .


Knapsack problem with the restriction on the number of items Suppose $X$ is a set of integers. I am interested in the algorithm which computes the number of ways to represent an integer $W$ as a sum of exactly $k$ elements from $X$. Is it possible to modify the standard knapsack algorithm so that it does the job? Thank you for your suggestions!

Iterative solution (recursive is very similar too):

Have a 2d array $mat[W][k]$ and let the columns be $0..k$ and the rows be from $0..W$. Let $mat[x][y] = 0 \;\forall \;0\le x \le W, 0\le y \le k$. Let $mat[0][0] = 1$.

Now run $i$ across $[1,k]$. Within the $i$ loop run another loop iterating $j$ across $[1,W]$. In every iteration of the inner loop, run through the set of elements and calculate this:

$${mat[i][j] = \sum_{l=1}^{|X|} mat[i-1][j-X_l] }\:$$

$mat[W][k]$ will store the final answer. Time complexity = $\mathcal{O}(W.k.|X|)$, and space complexity = $\mathcal{O}(W.k)$.


Is this simplified consensus problem easier than the original? There is a famous Consensus Problem in Distributed Computing.

Let's consider and try to find the best possible algorithm for a simplified version of the consensus problem.

Assumptions: a process may undergo only crash failure (process abruptly stops and does not resume), process represent a complete graph.

Simplification: a crash failure may occur only between round, so there no a case when a process succeeds in sending some message and fails to send other message during the same round.

The algorithm for the general case FloodSet when a process may crash during the round is described in Distributed algorithms - Nancy Ann Lynch. By the analysis it was shown that $f+1$ rounds is enough to reach a consensus.

Intuitively, it looks like that the simplification completely changes the approach to the solution. It is may be enough just one round, every processes send an input message to every other processes and agree on the minimal value.

What is the simplest possible algorithms for simplified problem ?

What can we do in the case of general graph?

What you're describing as simplified problem is usually called consensus with clean crashes.
You can just compute the maximum of all received messages once. To see that this is sufficient, observe that everyone receives the exact same messages after the first round. Thus everyone agrees on the same maximum value and all nodes decide correctly.

To solve crash-fault consensus on a general graph you need to assume $(f+1)$-connectivity. Then you could simulate each round of the FloodSet algorithm by flooding through the entire graph (taking $D$ rounds), yielding $D(f+1)$ rounds in total. I would be surprised if there's a more efficient way to do this (without additional assumptions on the graph, .e.g., high expansion).


Analysing worst-case time complexity of quick-sort in different cases I am trying to understand worst case time complexity of quick-sort for various pivots. Here is what I came across:

When array is already sorted in either ascending order or descending order and we select either leftmost or rightmost element as pivot, then it results in worst case $O(n^2)$ time complexity.
When array is not already sorted and we select random element as pivot, then it gives worst case "expected" time complexity as $O(n \log n)$. But worst case time complexity is still $O(n^2)$. [1]
When we select median of [2] first, last and middle element as pivot, then it results in worst case time complexity of $O(n \log n)$ [1]

I have following doubts

D1. Link [2] says, if all elements in array are same then both random pivot and median pivot will lead to $O(n^2)$ time complexity. However link [1] says median pivot yields $O(n \log n)$ worst case time complexity. What is correct?

D2. How median of first, last and middle element can be median of all elements?

D3. What we do when random pivot is $i$th element? Do we always have to swap it with either leftmost or rightmost element before partitioning? Or is there any algorithm which does not require such swap?

The usual rule here is only one question per post.

Link [2] doesn't say that random pivot and median pivot lead to $O(n^2)$ time complexity.

The median of first, middle, and last element is not the median of the whole array.  Writing "median pivot" is probably a bad idea, unless you have carefully specified what that's a median of.

Link [1] says that taking the median of all elements leads to $O(n \log n)$ time complexity.  That's different than taking the median of first, middle, and last.  Also, it's rare for practical implementations to take the median of all elements, as that link already states.


Meaning of "number of keys in the range $a$ to $b$" Regarding this question:

You are given an unsorted array $A$ of $n$ integers in the range $2^n −10n \leq A[i] \leq 2^n$.
Suggest a data structure that allows to answer in $O(1)$ steps the number of keys in the range $a$ to $b$ (note that $a, b$ are not necessarily integers). The construction of data structure should cost at most $O(n)$ steps.

Describe in few sentences the data structure.
Write a pseudocode for constructing the data structure.
Write a pseudocode for the numberKeys(NewDataStructure,a,b).
Give a short explanation of the time and space complexity of (2) and (3).

Can someone please explain me what "the number of keys in the range $a$ to $b$" means?

It probably means "the number of array elements whose value is between $a$ and $b$".
For the solution, it is crucial that the number of possible values of array elements is $O(1)$.


Probability of having a log(n) length monotone subsequence in a random permutation of {1,...,n} How can I compute the probability of having a $\log(n)$ length monotone consecutive subsequence in a random permutation of $\{1,...,n\}$.

I wish to upperbound it with $1/n$.

You can upper bound this probability as follows. The relative order within a consecutive subsequence of a random permutation is just another random permutation, so the probability that a specific consecutive subsequence of length $\log n$ is monotone is exactly $2/(\log n )!$. Since there are at most $n$ of this (actually, exactly $n-\log n+1$), the probability is at most
$$
\frac{2n}{(\log n)!} \sim \frac{2n}{\sqrt{2\pi\log n}(\log n/e)^{\log n}} = o\left(\frac{1}{n}\right).
$$


How to parse data in a text file? I had a question about altering a text file. I have data in the following format.

1 a,b,c
2 d,e
3 a, l, m,n

Note that some of them have spaces after the coma

Now I have to resort the data in the following format

1 a
1 b
1 c
2 d
2 e
3 a
3 l
3 m
3 n

Now my plan is to first parse the data, and hold a count of how many data elements there are for each number. (Ex. for the number 1, there are 3 elements).
Then I would move down the data by 3 spaces, starting from the bottom. Kinda like moving an array. (The main concern here is space more than time complexity)

Then I would enter each data element at the top.

My first question is, how exactly would I parse the data in a txt file and indicate delimiters such as the coma and the possible spaces.

Second, having done this, how would I just move down a whole line inside a text file down one?

I am very sorry if my question is convoluted. I will gladly clarify anything. Thank you so much for your time! Please let me know if there is anything i need to add. Also, I'm comfortable in both java and c. So advice on either language is useful.

I propose this, more direct to code (in java, c, etc.)

read each line (until CR/LF)
at begining, read a number, until spaces => number n
after that, take next characters of line
split them by ,
for each, trim (delete space before or after) => strings s1, s2, s3
then output n s1  CRLF n s2 CRLF n s3, etc.


Reccurrence equation and finding suitable algorithm I'm given the following recurrence equation:

$$\begin{align*}
    T(1) &= 0\\
    T(n) &= T(n/2) + 1  && \text{when $n > 1$ is even}\\
    T(n) &= T((n+1)/2) + 1 && \text{when $n > 1$ is odd.}
\end{align*}$$

The problems I have are the following:

1) What does $T(1) = 0$ mean when it comes to writing computer program? It cannot be

return some_constant;

because this gives the complexity of $T(1) = 1$. Am I right?

2) I'm supposed to find an algorithm whose time complexity can be described using the given equation. I was thinking of Fast Power algorithm, because it has the same $O(n) = \log(n)$, but it's described differently:

$$\begin{align*}
    T(1) &= 1\\
    T(n) &= T(n/2) + 1 &&\text{when $n > 1$ is even}\\
    T(n) &= T((n-1)/2) + 1 &&\text{when $n > 1$ is odd.}
\end{align*}$$

1) It doesn't mean anything, for two reasons:

First of all, it's important to distinguish between an algorithm vs the running time of an algorithm.  $T(\cdot)$ is not an algorithm; it's a function.  For instance, $T(n)$ might be the running time of a computer program, as a function of the size of its input, but it's not the program itself.  Anyway, $T(n)$ is just a mathematical function: if it is intended to represent the running time of some algorithm, that should be stated explicitly.
Second, every algorithm needs to take at least at least one step, so the running time always has to be at least one: it can never be zero.  Therefore, it doesn't make sense to have a running time of zero.  This might be a bit of a quibble/nitpick.

2) I suggest you do a bit more practice with the reverse: given a simple algorithm, work out a recurrence relation for its running time.  Once you feel like you're able to do that confidently, you'll probably find this exercise easy.

See also our reference question, How to come up with the runtime of algorithms?.  There's also a more advanced, sophisticated treatment at Is there a system behind the magic of algorithm analysis?.


Show that the set of all TMs that move only to the right and loop for some input is decidable I am trying to prove that

$\qquad L=\{\langle M\rangle \mid M \text{ is a TM }, \exists w. \text{ in }  M(w) \text{ the head moves only right and } M(w)\!\uparrow \}$

is decidable.

I thought about the following solution:
Lets build $\hat{M}$, a TM that will decide L:
M on input $\langle N \rangle$:
 1. $\Sigma^{Q+1} $ is decidable so it has an enumerator f.
 2. for every word $ w\in\Sigma^{Q+1} $ simulate parallel N on w for |Q|+1 steps:
  $\space \space \space$ - if N got to a blank then N moved only right and is stuck in a loop.
3. if all of those words stopped the simulation at a blank accept. else reject.

I am quite sure I am missing something here. Can you help please?

Your approach is on the right track. It should follow the next ideas:

If there exists such $w$, then, when $M$ reaches the first "blank" after reading $w$ it will be in a state $\tilde q$ that goes right (and then keep going right, no matter the state changes). Finding this $\tilde q$ that satisfied this property (if such exists) can easily be verified for by checking all the states in $Q$ (of the given $M$).
If such $\tilde q$ exists, we need to see if it is reachable after reading some input $w \in \Sigma^*$. The idea you already noticed is that if this happen, then $\tilde q$ will be reachable after processing the end of some word in $\Sigma^{Q+1}$ (or the like). This is simply a pigeonhole argument..

Therefore it is enough to only examine all the words in $\Sigma^{Q+1}$ and check if $M$ on any of them goes only right, and reaches $\tilde q$ when hitting the first blank. Since the number of words in $\Sigma^{Q+1}$ is finite, this is doable in a finite time.

You just need to properly formalize the above ideas as a decider $\hat M$.


Why this division algorithm works? I found this problem on an algorithmic book. I have solve the requestments about time (O(n^2)) but I can't figure out how it works.

Input: Two n-bit integers x and y, where y ≥ 1

Output: The quotient and remainder of x divided by y

function divide(x, y)

    if x = 0:
        return (q, r) = (0, 0)

    (q, r) = divide(floor(x/2), y)

    q = 2 · q
    r = 2 · r

    if x is odd:
        r = r + 1

    if r ≥ y:
        r = r − y
        q = q + 1

    return (q, r)

For even $a$ and $b \ne 0$ and integral division
$$ \frac{a}{b} = \frac{2a}{2b} = 2 \cdot \frac{( a / 2 )}{b} $$
Similarly for the remainder
$$a = 2 \cdot \frac{a}{2} \space (mod \space b)$$
Effectively transforming your problem of division of number with n bits into division of a number with n-1 bits (half as big number).

The algorithm uses integral division in the floor(x\2) part and there you might lose 1 if x was odd. You're giving it back with the if x is odd: block to the remainder and since this might make your reminder the same size as y you need to check if that happened and change the values accordingly. (Notice that r > y can never happen and there could be just as fine if r == y:.)

You just do this n times where n is the number of bits of x.

Finally the algorithm is not $O(n^2)$ but rather $O(n)$ in the number of bits of x. That's assuming the floor(x/2) part does not call the divide function, because that would end in infinite loop (you would need e.g. compute a/2 to compute a/b which would in turn need again computation of a/2. This can be avoided by using a>>1 instead of a/2 which also authomatically floors the result).


Proving with co-induction principles I'm going through Adam Chlipala's "Certified Programming with Dependent Types" (available here for convenience), and I'm a bit stuck at internalizing the introduction of co-induction principle for the stream_eq predicate in Chapter 5.

Firstly, I'm used to induction schemes defined for data structures (stream in this case, if it were data and not codata). Yet, the co-induction principle being introduced seems to be defined for the predicate we're trying to prove itself, and how does it connect with the following (cursive ours)?

  Dually, a co-induction principle ought to be parameterized over a predicate characterizing what we mean to prove, as a function of the arguments to the co-inductive predicate that we are trying to prove.

Or should I parse this as implying parametrization over the predicate R : stream A -> stream A -> Prop, which, to me, seems like a reformulation of stream_eq, taking the following hypothesis into account?

Hypothesis Cons_case_hd : forall s1 s2, R s1 s2 -> hd s1 = hd s2.
Hypothesis Cons_case_tl : forall s1 s2, R s1 s2 -> R (tl s1) (tl s2).

Secondly, considering the quoted text again, we're trying to prove stream_eq. What would be the arguments to that predicate here? Looks like it should be the streams, but the hypothesis seem to be much more complex than that.

Lastly, all of this stream_eq_coind looks to me a like a somewhat generic way to do the match acrobatics on the streams to allow the simplifier to proceed (as Chlipala does in the version of the proof preceding this part). Is this correct or am I missing some deeper sense?

Oh, and what would be some good sources for me to read on co-induction? A few papers or tutorials I've found refer to some algebra or logic (i.e. Kripke models) quite beyond my current knowledge.

What likely makes it confusing is that you are doing very different things in inductive versus coinductive cases. This is somewhat alluded to by Chlipala's reference to "infinite proofs"1. (Another aspect that makes seeing what is really going on hard is the presentation that makes coinductive type declarations look similar to inductive type declarations.)

I'm going to set up some context starting with inductive types. This is motivated by the categorical understanding of inductive types via initial algebras, but I'm not going to elaborate on that too much

Since inductive types are modeled by initial algebras, this means if we define the behavior of a function on cases, which corresponds to providing an algebra, we get a unique algebra morphism from the initial algebra to our just defined algebra, and this unique algebra morphism is the recursor. The main thing to note here for our purposes is that we get an morphism into the type of our choosing. This is evident from the type of a recursor, e.g. the one for naturals is $\forall T.T\to(T\to T)\to\mathbb N\to T$ so we get to choose $T$. To get the inductive eliminator, we can essentially do the same story but instead of using a category of types and functions, we use a category of families of types and families of functions. This is a massively oversimplified summary of Fibrational Induction Rules for Initial Algebras. Again, the upshot for us is that we get to choose the family (represented by a $\mathsf{Prop}$-valued function) and the result is a function into this family. Since from a Curry-Howard perspective, to prove the predicate that the family represents, we want to produce values in the family, and this situation is ideal. Note that the predicates we're proving are not themselves inductive types (though they could be).

The categorical story for coinductive types is categorically dual. We talk about final coalgebras instead of initial algebras. The main point for us is that a final coalgebra provides a unique coalgebra morphism from a type of our choosing into our coinductive type. This leads to the duality that it's simple to create a value of an inductive type while consuming one is involved, meanwhile it is simple to consume a value of a coinductive type but producing one is involved. This is somewhat obscured by the presentation of coinductive types in Coq.2

The problem is that if we want to prove some predicate, we need to produce a value of the appropriate type, but coinduction is about how to produce values of the coinductive type.

The "solution" is to consider coinductively defined predicates, and then we can use coinduction to produce values of these predicates to prove them. And this is what's happening in the examples. We are not using coinduction on streams to show that stream_eq holds. Instead, stream_eq is itself a coinductive type. The fact that stream is also a coinductive type is irrelevant here. For example, would could define stream_eq to talk about functions $\mathbb N\to A$ instead of streams. Indeed, the evalCmd example is defining a coinductively defined predicate over inductive types.

As for why the coinduction rule takes the form it does for stream_eq, this follows from its definition fairly mechanically except the notation obscures things a bit. First, we can make the equality of the heads more apparent by, instead of using the same variable for both, using two variables and an explicit equality. Something like:

  CoInductive stream_eq : stream A -> stream A -> Prop :=
  | Stream_eq : forall h1 h2 t1 t2,
    h1 = h2
    -> stream_eq t1 t2
    -> stream_eq (Cons h1 t1) (Cons h2 t2).

A record-oriented rewriting would make things clearer still, e.g.:

coinductive StreamEq (A : Type) (xs ys : Stream A) : Prop where
     headEq : hd xs = hd ys
     tailEq : StreamEq A (tl xs) (tl ys)

The coalgebra (in a category of families) that we need to apply coinduction corresponds to producing a family of functions from $R$ to a record of the same form as StreamEq only with $R$ in the place of StreamEq. A function into a pair can be split into a pair of functions and this exactly what Cons_case_hd and Cons_case_tl correspond to.

1 I don't really like this reference to "infinite data structures" and "infinite proofs" as that's not what's happening.

2 If we used a more record-like declaration syntax it would be more obvious. Having something like:

coinductive Stream (A : Type) where
    hd : A
    tl : Stream A

with corec would be something like

corec : (S : Type) -> (S -> { hd : A, tl : S }) -> S -> Stream A

would make this a bit clearer. This record-/projection-oriented view of coinductive types helps explain the guardedness conditions. What we're really specifying in a corec is the behavior of hd and tl. If we don't manifestly present a Cons to Coq, so it can take the hd of it as the definition of hd and the tl as the definition of tl, then Coq doesn't know what those definitions should be, and, of course, they might not exist at all which means we don't have a coalgebra and can't apply corecursion.


Context Free Grammar for language L Can someone help with this:

$L=\{a^ib^j \mid i,j \ge 1 \text{ and } i \ne j \text{ and } i<2j\}$

I'm trying to write a grammar for this language?
I tried this:

$S \to S_1 \mid S_2 \\
S_1 \to aXb \\
X \to aXb \mid aaXb \mid aab \\
S_2 \to aYb \\
Y \to aYb \mid Yb \mid b \\
$

What do you think?

The solution in the question is correct.

The constraint $i\ne j$ is the one that gives us trouble. To get around it  we have to split into two cases: (i) $i<j$, and (ii) $i>j$ (but still $i<2j$)

thus
$S\to S_{(i)} \mid S_{(ii)}$
as the first production splits into this two cases.

Now, divide and conquer:  case (i) is very simple, since we only need $i<j$,
$S_{(i)} \to aS_{(i)}b \mid B$
$ B \to Bb \mid b$

This is your $S_2$.

For case (ii), we need to $j< i < 2j$, so for every single $a$, the variable $C$ will generate exactly one $b$, and at a certain point we switch to the variable $D$ that will generate two $a$'s for each $b$.
$S_{(ii)} \to aCb $
$ C \to aCb \mid D$
$ D \to aaDb \mid aab$

This is your $S_1$.


Data-structure for dynamic disjoint-sets I have a collection of objects, with certain properties (let say 3 - zone, type, owner) only having a small predetermined possible set of values (like enum).

This is just a simple (javascript) array of gaming cards (think "magic the gathering"), that could be in different zones (deck, hand, grave, play), and they could be owned by different players at different stages of their lifecycle. Also, there is a type (spell, minion, weapon, enchantment) which is unchangeable, but still very important discriminator.

In order to process game, I need to often query my store to get "all spells in hand which cost less than current mana of current player", or "all enemy minions which had not attacked this turn".

Right now I simply use Array.filter and just filter the all universe with small predicate functions, but I have a feeling this could be made more efficient, if I can at least cut the size of whole collection in the beginning of query processing.

To speed up queries like where type = N, I considered using a pre-made number of Sets (e.g.: "cardsByType = MINIONS | SPELLS | WEAPONS" or cardsByZone = HAND | DECK | GRAVE).
Also, during program life cycle - some of those properties could be updated - so I was updating those Sets together with object update.

Unfortunately in practice, I need the collection to be ordered, as insertions and removals need to happen in certain positions.
This means that Sets only help me with queries like count where type=n. Also, during program life cycle - some of those properties could be updated - so I was updating those Sets together with each object's (card) update.

Also, maintaining the consistency between object itself, and two collection (old and new) is very error prone.

Am I missing some known obvious data-structure that could be helpful with such task ? OR no general-purpose data-structure like that exists ?

For Magic the Gathering, the number of cards is so small that the simplest data structure is probably the best.  Just have a list of all cards (each card records its name, location, properties, etc.).  Then to answer a query, scan through all cards and see which ones match the query.  Since you'll probably have very few cards in the data structure at a time (like, at most a few hundred), all operations should be very fast.

There are more sophisticated schemes, but they probably aren't worth the implementation effort.  You could think of this as a table in a relational database (one row per card, one column per attribute), and build an index for each column.  In other words, you have an ordered list of cards.  You also have a hashmap that maps from location to a list of all cards in that location.  These lists are stored as balanced search trees, with links between them (i.e., given a card in one tree, you can follow pointers to find where that card is stored in each of the other trees). This will let you do queries quickly.  Also to update the data structure, you can remove a card by finding it, then removing it from all of the linked trees; and you can insert a card similarly.  But in your case it won't be worth the effort.


Clarification of definition of class $DisNP$ I an trying to learn about $DisNP$ Complexity class. I couldn't find this class in any book. But, regarding it, I found this definition in a paper:

Definition: A disjoint NP-pair (NP-pair for short) is a pair of nonempty sets $A$ and $B$ such that $A, B \in NP$ and $A \cap B = Empty$. $DisNP$ denote the class of all disjoint NP-pairs.

Now I am aware that when a problem like $SAT$ etc. is said to be in $NP$, it means that assuming we have a NDTM we can get the solution in polynomial time. Or in other words, if we can guess the solution, then the verification takes polynomial time.

But, what does it mean when we say a set $A \in NP$ or a set $B \in P$.

Does the elements of the sets represent the solution for which the corresponding $SAT$ instance for each set is true i.e. set $A$ and $B$ contain the solutions of some $SAT$ instances $SAT_A$ and $SAT_B$ such that $SAT_A$ is satisfiable iff its solution is in the set $A$?

I am not clear how we use sets (which I assume have binary strings) for defining $P, NP, NPC$?

A disjoint NP pair consists of two NP languages $A,B$ which are disjoint. For example, $A$ could consist of all graphs which are $k(n)$-colorable (where $n$ is the number of vertices and $k$ is an arbitrary function), and $B$ could consist of all graphs having a clique of size $k(n)+1$.

Disjoint pairs of NP languages are used in proof complexity. For example, the disjoint pair discussed above (for $k(n) = n^c$) is used to prove exponential lower bounds on the size of proofs in the cutting planes proof system. See for example these notes. (For the state-of-the-art regarding cutting planes, see the recent paper Random CNFs are Hard for Cutting Planes.)


Context sensitive grammar for $\{a^{2^n}\mid n\geq 0\}$ I want to build a context sensitive grammar for the language $\{a^{2^n}\mid n\geq 0\}$.  I think it should be something like this
\begin{align*}
S &\to aA \mid a\\
aA&\to aaaA \mid aa
\end{align*}

This is from Hopcroft and Ullman's book,
Example 9.4, pg 220:

$$ S \rightarrow ACaB $$
$$ Ca \rightarrow aaC $$
$$ CB \rightarrow DB $$
$$ CB \rightarrow E $$
$$ aD \rightarrow Da $$
$$ AD \rightarrow AC $$
$$ aE \rightarrow Ea $$
$$ AE \rightarrow \epsilon $$

Update: in fact given grammar is unrestricted which can be modified as a context sensitive.

But if your ultimate goal is to prove that the given language is a CSL, then it is enough to create a linear bounded automaton - a TM whose computational ability is restricted to the portion of input. In other words, the head of the TM cannot move beyond the input area. LBA's and CSG's are equivalent.

You can just erase one input symbol at a time starting from the right, and each time you erase one symbol increase a counter by one (binary symbols 0 and 1) which are stored in place of erased symbols. When you erase all input symbols check if the counter is of the form 100...0. If yes then accept, otherwise reject). 100...0 means it is a power of 2.


Proof of equivalence of regular expressions (0 + 1)(0 + 1)* and (0 + 1)*(0 + 1) How would I prove that the regular expressions RS and SR where R = (0 + 1) and S = (0 + 1)* are equivalent? The '+' sign represents union of two regular expressions and two expressions RS are concatenated.

From what I know, either you must prove using existing rules about equivalence of regular expressions (example: commutativity or associativity of union) or you must prove that L(RS) is a subset of L(SR) AND L(SR) is a subset of L(RS) where L is the language denoted by the regular expression in the parentheses.

However, I am struggling to come up with a proof. Could someone give me a hint?

Let's go with your second approach.

First note that $R^n$, for any nonnegative integer $n$, is in $L(S)$.

If the string $w$ is in the first language, $L(RS)$, then we know that $w$ can be written as the concatenation of some string in $R$ and some string in $S$. This concatenation is denoted $(0 + 1)(0 + 1)^n$ (for some nonnegative integer $n$), which equals $RR^n$ which equals $R^{n+1}$, which equals $R^nR$, which we know is in the language $L(SR)$ (since $S=R^*$).

The reverse direction is more or less the same thing.

Edit:
Another interesting way of proving this is to prove $L(RS) = L(S)$ and $L(SR) = L(S)$.

To prove $L(RS) = L(S)$, take any string in $L(RS)$. It can be written as $RR^n$ for some nonnegative integer $n$. Now this equals $R^{n+1}$, which is of course in $L(S)$. So we have that $L(RS)\subseteq L(S)$.

Now take any string in $L(S)$. It can be written as $R^m$ for some nonnegative integer $m$. This is equivalent to $RR^{m-1}$, which is in $L(RS)$, so we know that $L(S)\subseteq L(RS)$.

Therefore we have $L(S)=L(RS)$.

We can prove $L(S)=L(SR)$ in a very similar way. Therefore $L(RS)=L(SR)$.

The actual difficulty and intuition behind the proof is fairly trivial, but putting the proof into words is harder. The proof amounts to proving some kind of exponent law for the Kleene star. We don't have an actual exponent law for the Kleene star, so the key part of the proof is simply isolating a single arbitrary string in the language, and then we have the finite integer exponents and we can just use the normal exponent laws.


finger search on a red black tree I'm having trouble finding materials on what 'finger search' is, in the context of a red black tree.

Even Wikipedia has a very short page about that, could you refer me or explain what kind of search is that.

One of the basic operations supported by trees is searching for elements. A balanced binary tree (for example, a red-black tree) supports search in $O(\log n)$ time, where $n$ is the number of elements. In some scenarios, the elements we are searching for are close to one another, and finger search allows taking advantage of that. After having just searched the $j$th largest element, searching the $i$th largest elements only takes time $O(\log |i-j|)$. So scanning through all the elements in order would only take $O(n)$ time rather than $O(n\log n)$.

Finger search can be implemented using several different data structures. In particular, it can be implemented using balanced binary trees such as red-black trees.

For more on finger search, check out a research proposal by Maverick Woo and a book chapter by Gerth Stølting Brodal.


What is an efficient data structure for prefix matching? I'm looking for an data structure that supports efficient random prefix matching queries (pattern) over a previously known set of words (dictionary). The dictionary is expected to contain about 10,000 words of varying length (I haven't calculated average word length, but I don't expect any word to be more than 80 characters long). Prefix matching in this case would be equivalent to words[i].toLowerCase().startsWith(pattern.toLowerCase()).

A Trie is an obvious choice, and provides linear time search corresponding to the length of the pattern. However, I'm confused whether a Suffix Tree, or a Suffix Array, might provide any improvements over a Trie. It seems a Suffix whatever is commonly used for one text, not multiple. I also have no requirement for supporting the various cool use cases (longest common prefix, or number of times a prefix occurs etc) that Suffix whatever can efficiently support.

I'm looking for a recommendation on which data structure to use, and why. Tries use a lot of space, and if I end up using one, I'd consider compress the branches with nodes with outdegree 1.

For the duplicate button happy readers, I've read this and this question, none seemed directly relevant.

Example:

Dictionary: [banana, apple, banter, orange]

Pattern: ban
Return: banana (any match)

Pattern: grapes
Return: null

A trie is asymptotically optimal for this.  No data structure can achieve better asymptotic running time.

If you care about constant factors, the only way to know what will be optimal is to try multiple approaches and benchmark them.  Standard theoretical running time analysis is not reliable at predicting constant factors.

Another data structure to consider is to store every prefix of each word in a hashtable.  This will increase the space usage by about 10x (if the average word length is 10) but might speed up lookups in practice.  The asymptotic running time will remain the same.  You'll have to decide whether you're willing to trade off space for time.

Suffix trees and suffix arrays don't seem relevant.  You're asking about prefix matching, not suffix matching or matching in the middle of the string.


Distance-preserving permutations In the scope of my scheduling research, the question has been raised on whether distance-preserving permutations can be constructed easily.

Suppose that our domain is the set of natural numbers up until $n$, that is: $D=\{1,2,...,n\}$ where $n\geq 1$.

A permutation $\pi$ is a distance-preserving permutation in my context is one that has the following property: $|\pi(i) - \pi(j)| = |i-j|$.

For example, the most trivial distance-preserving permutation I have come up with is the following: $\pi(i) = n-i+1$, which is the permutation that maps $1$ to $n$, $2$ to $n-1$, etc. It can be easily shown that $|\pi(i) - \pi(j)| = |i-j|$.

My intuition says that there are no more distance-preserving permutations, since if we draw this as a graph where the $x$-axis is the numbers in $D$ and the $y$-axis is the values $\pi(i)$ then we will have a $90$-degree cornered triangle with the corner facing north-east, its' equal edges being the distances $|i-j|$ and $|\pi(i) - \pi(j)|$.

Are there distance-preserving permutations other than the above trivial one?

The only permutations who satisfy this condition are the identity and its inverse (as string inverse), $\pi(i)=n-i+1$.

Note that $1$ has to be in one of the edges (if it has two neighbors, then at least one of them is bigger  than $2$ and the condition is not satisfied). Placing $1$ in the left edge forces the entire permutation to be the identity, and placing $1$ in the right edge forces the permutation to be its inverse.


Is it possible to convert a graph with one negative capacity to a graph with only positive capacities? I am interested in whether a graph (say, a complete graph) with one capacity negative (or many, but one should suffice) can be reconstructed as a graph with all non-negative capacities where the max flow between vertices of the original graph can be identified with max flows between vertices of the new graph. It is ok for the new graph to have more vertices than the original graph. Said another way, consider a complete graph K-n with additional external edges in addition attached to source/sinks. Allow one of the edges of the complete graph to have negative capacity. Can I replace the complete graph with another graph with only positive capacities such that the max flow between all possible subsets of the external sources/sinks remains the same?

CLARIFICATION: We connect each vertex of the complete graph to a distinct external vertex with an edge. If it helps, picture a complete K_6 drawn as a hexagon with an additional edge coming out of each vertex of the hexagon to 6 extra distinct vertices. Those distinct vertices are the s and t's that we are interested in considering. The edges that are not edges of the complete graph that we add are the external edges. I am interested only in cases where the original graph is the complete graph, though edges are allowed to have weight 0 or weight infinity. I hope this helps.

Thanks,
Ning

If you indeed have an edge $e$ with a negative capacity, and, I assume, it is a directed edge having no corresponding opposite edge, then you can reverse $e$, make its capacity positive, and, then, solve a regular max-flow problem with all capacities being non-negative. (Look at the concept of the residual network to understand what a negative capacity means.) Make sure you are not confusing edge capacities with costs.


Buying as many items for as much money I cant find a way to implement a certain solution. Let me flesh out the problem.

Somebody gives you X amount of money and sends you to the shop to buy Y amount of items. You must spend as much money as you can and buy as many items as you can. You cant have more money they X. You cant buy more than Y amount of items. Some money can left afterwards, but as little as it can. You can buy less than Y items, but only if there is no other option. You cant buy same item more than once - items are unique.

Examples:

You have 15£, and need to buy 2 items. There are 4 items for 10£, 5£, 4£ and 3£. You buy 10£ and 5£ items. Perfect scenario - 15£ spend, 2 items aquired.

You have 15£ and have to buy 3 items. There are 4 items for 4£, 3£, 2£, 1£. You buy 4£, 3£ and 2£ items. 9£ and 3 items aquired.

You have 15£ and have to buy 2 items. There are 4 items for 20£, 19£ and 14£. You buy only 14£ item.

I think you understand by now how it works.

Implementation(Javascript):

var arrayOfItems = [];
arrayOfItems[0] = {"name":"Sandwich","price":15};
arrayOfItems[1] = {"name":"Water","price":10};
arrayOfItems[2] = {"name":"Cookie","price":5};

function getItems(moneyAmount,itemsAmount){
    //your code here....
}

var items1 = getItems(21,2); //returns [0,2]
var items2 = getItems(25,2); //returns [0,1]
var items3 = getItems(14,2); //returns [1]

I need to invent the inside of getItems() function. Can you lead me how to do this?

Thank you for help.

This is a classic Knapsack problem  some examples: Knapsack.java, JS example

Here is a pseudo code from Introduction to Algorithms, MIT:


P, Q, ((P→Q)→R) ⊢ R using only modus ponens Can $R$ be inferred from $P$, $Q$, and $(P \to Q) \to R$ using only modus ponens?
My understanding is that it can, as shown below, but I was told this was incorrect.

Proof of ${P, Q, (P \to Q) \to R} \vdash R$ using modus ponens:

P, Q, (P->Q)->R  : Given
Q, (Q)->R        : By Modus Ponens
R                : By Modus Ponens

Given $P$, $Q$ and $(P \to Q) \to R$, there is no way to apply modus ponens. You would need to have $(P \to Q)$. If you had $P$, $Q$ and $P \to (Q \to R)$, then you could apply modus ponens twice the way you did, but $P \to (Q \to R)$ and $(P \to Q) \to R$ are different.

$P \to (Q \to R)$ says “if I have P, then if I have Q, then I can get R”.
$(P \to Q) \to R$ says “if I can get Q given P, then I can get R”. It requires a method of getting from P to Q.

It is true that given $P$, $Q$ and $(P \to Q) \to R$, you can deduce $R$. You can see that with truth tables, for example. However this requires logical rules that go beyond modus ponens. This has a mathematical consequence: this deduction is only valid in logics where those extra rules are available (such as classical logic).

There is a computational interpretation of these deductions. $P \to Q$ can be interpreted as a function that produces a $Q$ given a $P$. Modus ponens then comes down to applying a function. Given a function $f : P \to (Q \to R)$, you can apply $f$ to a $P$, which produces a new function $Q \to R$; when you apply this function to a $Q$, you get an $R$. Given a function $g : (P \to Q) \to R$, the situation is different: you need a function from $P$ to $Q$ to get started. Given a $Q$, it's easy: you can use a constant function that returns this $Q$. But that first step of constructing the constant function is not modus ponens.


Imaginary numbers and negative zero I've been studying the low-level hardware implementations of floating point numbers and doing an exercise to design a custom floating point implementation.

I know that being able to represent negative zero is important for some purposes, but ran across a curious question.

Complex numbers are generally represented by two fp numbers. Is there any use in being able to represent negative zero on the imaginary line? Does anybody use this for anything?

Yes, there is a usage for the negative imaginary zero. But first, I will say something about the negative zero in general.

Why have a negative zero?

First of all, the main reason to have a signed zero for floating points is that floating points have only limited precision and we often want to distinguish the following cases of a real number $x$, represented by a floating point:

$x\geq 0$, which we will denote by $+0$.
$x<0$, which we will denoted by  $-0$.

As we cannot distinguish between these cases ordinarily in our floating point representation when $|x|$ is smaller than the floating point precision, we need a special notation for this. We want to distinguish between these two almost $0$ numbers, as this difference can be 'enlarged' with the appropriate function: when we have defined $1/0=\infty$ (we work with the extended reals) we have $+0={-0}$, but $1/{-0}={-\infty}\neq +\infty = 1/{+0}$.

The negative imaginary zero

For the following, consider a complex number $z=x+i\cdot y$, with $x$ the real part and $y$ the imaginary part, represented by a floating point for $x$ and another floating point for $y$.

One important application where we want to distinguish between $-0$ and $+0$ is when computing the inverse elementary functions (i.e. $\ln(z), \sqrt{z}, \arcsin(z)$) for the complex numbers. All these functions are defined in terms of $\ln(z)$, the complex logarithm.

I won't go into the details why, but this function is discontinuous on the whole negative real number line: $\ln(x + i\cdot +0)\neq \ln(x+i\cdot{-0})$ for all $x\leq 0$, this is half-line known as the branch cut of the complex logarithm. (Note that we also want to know the sign of $x$ here to see whether are 'on' this line in the first place!)

For example, we have $-4+i0 = -4 - i0$, but $2i=\sqrt{-4+i0 }\neq \sqrt{-4-i0}=-2i$. So, we need to distinguishing between $+i0$ and $-i0$ to know on which 'side' of the branch cut we are to compute the complex logarithm $\ln(x)$ and all other inverses of elementary functions defined from it. For more on this topic, see these notes by Prof. W. Kahan.


Maximize function over a set with a transitive and antisymmetric relation Let $\mathcal{R}$ be a transitive and antisymmetric relation defined over a finite set $X$.

For any set $S\subseteq X$ define $\Gamma(S)=\left\{y\in S  \mid \not \exists x\in S  . (x,y)\in\mathcal{R}\right\}$. (Thus, $y \in \Gamma(S)$ if it belongs to $S$ and no other element in $S$ "dominates" it.)

Suppose that each element is assigned a weight. This is represented by the function $w:X\to \mathbb{R}^+$.

The problem is to find a subset $S \subseteq X$ to maximize $\sum_{z \in \Gamma(S)}w(z)$.

Is this problem polynomial-time solvable?

You can compute the maximum weight of an antichain, or more generally the maximum weight of a union of $k$ antichains, by reducing to the maximum flow problem. See for example a technical report by Cong.


Disk scheduling algorithm - SCAN and C-SCAN I'm studying several disk scheduling algorithms; however, I'm kinda confused with SCAN. I understand the concept, but I don't understand the example given in the book. I think that the author made a mistake, but I want to be sure.
The example is the following:

Description of SCAN: The disk arm starts at one end of the disk, and moves toward the other
end, servicing requests until it gets to the other end of the disk,
where the head movement is reversed and servicing continues.
Suppose that the cylinder range goes from 0 to 199 and you have the following queue:
98, 183, 37, 122, 14, 124, 65, 67
Head pointer: 53
As seen in the image, the total head movement is of 208 cylinders

I don't understand why 208 cylinders. If I understand correctly, the head will start at 53 and then move to 0 (that's 53 cylinders), then the head will move up and the last service requested is at 183 (that's another 183 cylinders). So the total head movement should be 53 + 183 = 236.
The book also has an image and description of C-SCAN:

C-SCAN moves the head from one end of the disk to the other, servicing requests
along the way. When the head reaches the other end, however, it immediately returns
to the beginning of the disk without servicing any requests on the return trip.
The C-SCAN scheduling algorithm essentially treats the cylinders as a circular
list that wraps around from the ﬁnal cylinder to the ﬁrst one.

Using the same example, with C-SCAN the cylinder would start at 53, then move up to 199 (146 cylinder movements), then go to 0 (199 movements), and then the last request would be at 37 (37 cylinder movements). The total cylinder movements would be 146+199+37=382. My question here is, do we also have to count the cylinders when the head goes back to 0 since it isn't servicing any requests?
Note: This information was extracted from Operating System Concepts with Java - 8th Edition by Silberschatz, Galvin, Gagne.
You can also find this part of the chapter here.

Here are the examples of various disk scheduling algorithms.

Yes you are correct in both the case. The author here has made mistake.
For SCAN: The answer should be 236.
For C-SCAN: The answer should be 146+37=183.(Note: The head movement when its not servicing any requests is not counted.)
Refer the link, it gives a clear concept of how the different kinds of disk scheduling algorithms are used in practice.


What are the uses of Markov Chains in CS? We all know that Markov Chains can be used for generating real-looking text (or real-sounding music). I've also heard that Markov Chains has some applications in the image processing, is that true? What are some other uses of MCs in CS?

Markov Chain Monte-Carlo is a technique for efficiently sampling from a complicated probability distribution. No matter what your (discrete) probability distribution, you can set up a markov chain so that the steady-state distribution of a random walk is the distribution you wish to sample from. You can then approximate this distribution by simulating the random walk on the markov chain. If the markov-chain happens to have small mixing time, then the empirical distribution of your simulation will quickly converge to the steady state distribution, giving you an efficient algorithm for sampling from it.


Bitwise XOR of regular languages Is the language consisting of the bitwise XOR of elements of two regular languages still a regular language?

For example, consider
$$L=\{ x \operatorname{xor} y \mid x \in A, y \in B, |x|=|y| \},$$
where $A$ and $B$ are both regular languages.

Can I say that $L$ is also a regular language?

You can show that $L$ is regular by using an NFA. Briefly, the NFA is going to simulate DFAs for $A$ and for $B$, guessing the decomposition of the input into $x \oplus y$ as it goes. The same works for any other operation such as AND and OR.

In more detail, suppose that we are given DFAs for $A,B$:

Sets of states $Q^A,Q^B$.
Initial states $q_0^A,q_0^B$.
Final states $F^A,F^B$.
Transition functions $\delta^A,\delta^B$.

We construct an NFA for your language $L$ as follows:

Set of states is $Q^A \times Q^B$.
Initial state is $\langle q_0^A,q_0^B \rangle$.
Final states are $F^A \times F^B$.
Transition function is
$$
\begin{align}
&\delta(\langle q^A,q^B \rangle, 0) = \{\langle \delta^A(q^A,0), \delta^B(q^B,0) \rangle, \langle \delta^A(q^A,1), \delta^B(q^B,1) \rangle \}, \\
&\delta(\langle q^A,q^B \rangle, 1) = \{\langle \delta^A(q^A,0), \delta^B(q^B,1) \rangle, \langle \delta^A(q^A,1), \delta^B(q^B,0) \rangle \}.
\end{align}
$$
You can prove inductively that
$$
\delta(\langle q^A,q^B \rangle, w) = \{ \langle \delta^A(q^A,x), \delta^B(q^B,y) \rangle \mid x \oplus y = w \},
$$
from which the correctness of the construction easily follows.


Can a 600 MB text file with digits of the square root of 2 be compressed to 600 KB? I have a simple script to calculate gaps in a sequence of digits of the square root of 2 (or any other multi-precision constant).
As input, I generated files with the bigfloat module in Python:
from bigfloat import sqrt, precision

MAX_PRECISION_BITS: int = 1 << 30
CONSTANT = 2

precision_bits: int = 8
while precision_bits < MAX_PRECISION_BITS:
    with open(f"input/square_root_of_{CONSTANT}_with_{precision_bits}_bits.txt", 'w') as fd:
        fd.write(str(sqrt(CONSTANT, precision(precision_bits))))
        fd.flush()
    precision_bits *= 2

Although I can run the script any time, I decided to compress the input files, and I was surprised that a 646.5 MB got compressed to 632 KB, ie less than 1 MB! This value was obtained with the standard Zip method that is available in Mac OS X. I performed a diff command in the original and expanded file to check for possible differences and none was found.
I understand that every decimal digit takes about 3.32 bits, and the square root of 2  is conjectured to be normal, so I was expecting a compression to 40% or so.
How is this compression attained?

Clearly that's a way too good compression rate. $\sqrt{2}$ is not a rational number, so the decimal expansion will not start repeating. So there has to be something really fishy going on.
I run your script, and looked at the resulting file.
On my machine, the file square_root_of_2_with_536870912_bits.txt contains 161.614.250 digits, and the last 161.597.755 digits are all zeros. Only the first 16.495 digits are different from zero.
So given that pretty much almost everything in the files are zeros, it's not unexpected that the compression rate is so high.

I'm not experienced with the bigfloat package, so I can't tell if the bug is in your program or in the package itself. If you can't figure the error out yourself, open an issue on their Github page.
Btw, from those 16.495 digits, only about 5.000 of those are correct.


Confused about pumping lemma Here I have the method for pumping lemma to prove that a language $L$ is not regular:

Suppose to the contrary that L is regula, then $\exists$ DFA $A$, s.t. $L(A) = L$.
Let $n$ be the number of states in $A$.
So, $\forall w ∈ L(A)$, if $|w| \ge n$, then $w = xyz$,
where $x$, $y$, and $z$ as in Pumping Lemma.
Choose a suitable $w \in L$, where $|w| \ge n$.
Find an $i$, such that $xy^iz \not\in L$.
Since $xy^iz \in L(A)$, $L(A) \neq L$.
4 contradicts 1, so 1 cannot be true and therefore
$L$ cannot be regular

First of all, what are we trying to prove here in other words? That the language $L$ cannot be represented by a FSM, therefore cannot be considered "regular" because a regular language is only regular if it can be represented by a FSM?

Second, how am I supposed to find "$n$" which is the number of states in $A$? Is this also known as the pumping length?

What is the proper way in which we are supposed to break up the string chosen string $w \ge n$ into 3 parts ($xyz$)?

For example this teacher broke it up in this way:

$$\begin{align*}
w &= a^{n}ba^{n+2}\\
i &= 2 \\
xy^2z &= a^{n+∣y∣}ba^{n+2}
\end{align*}$$

How is the above equation equivalent? Why is he choosing $|y|$ and adding to to $n$?

And why would any of this prove that $L$ is not regular? I'm really confused about the whole thing.

First of all, what are we trying to prove here in other words? That
  the language L cannot be represented by a FSM, therefore cannot be
  considered "regular" because a regular language is only regular if it
  can be represented by a FSM?

Indeed. Although there are varying definitions for regularity (e.g., you may define the regular languages based on regular expressions), they are all equivalent. Hence, you only need to prove your language fails to satisfy one of the equivalent requirements to be regular. In the case of the pumping lemma, you argue on the basis of DFAs.

  Second, how am I supposed to find "n" which is the number of states in
  A? Is this also known as the pumping length?

You are not supposed to find anything. In the classical variant of the pumping lemma, the number of states only appears explicitly in its proof. In the statement itself, there is only mention that such a number $n \in \mathbb{N}_0$ exists.

  What is the proper way in which we are supposed to break up the string
  chosen string w >= n into 3 parts (xyz)?

The pumping lemma specifies what conditions should hold for $x$, $y$, and $z$. There are three of them. And, as $n$, when proving a language contradicts the lemma (to show it is not regular), you don't get to choose $xyz$; rather, you have to show your claim no matter what $x,y,z$ are (as long as they suffice the conditions from the lemma).

In your example, the word has prefix $a^n$, while one of the pumping lemma's requirements is $|xy| \le n$. Hence, there is no other option for $xy$ except for it to be a prefix of $a^n$, which is why you can extend this prefix to $a^{n + m|y|}$ for any $m \in \mathbb{N}_0$. (Remember: $y$ is the part that can be "pumped".)


Find longest path by number of edges, excluding cycles I need to analyse a directed graph (not a DAG) but I don't know the name of the algorithm I would need to use. The graph has many cycles.

My desired behaviour is: given a graph source and graph sink, find the longest path by number of edges, excluding cycles.

By graph source, I mean a vertex with one or more edges to other vertices and no incoming edges, and the opposite for sink. If there's better terminology, then please let me know about this.

It's important that I'm able to determine what the path is, so I would need an algorithm that can produce a list of edges.

By excluding cycles, this might entail not traversing an edge the process traversed previously.

Do you recognise this algorithm and could you tell me the name, please?

Thanks in advance

The problem you are defining is called Longest Path (and occasionally Longest $s$-$t$-Path) and is NP-complete.

That is, there is an algorithm for solving it, but you shouldn't keep you hopes up when it comes to the running time of the algorithm: it's unlikely to run in polynomial time.

The trivial algorithm is to check for every permutation of the graph, in time $O(d! \cdot 2^{dn})$, but this becomes intractable extremely quickly.  It is possible to bring this down to $O(2^n \cdot \text{poly}(n))$.

You have three options as far as I can see it:

limit the length of the path you need to some reasonable integer $k$ and solve with FPT techniques
use an approximation algorithm
limit the type of input graph to certain smaller and easier graph classes.

Note 1: As Yuval Filmus points out, the problem Longest Path is usually referring to the undirected version.  However, the problem remains NP-complete also in its directed version by a reduction from Directed Hamiltonian Path (Between Two Vertices) (Garey & Johnson, 1979).

Note 2: Yuval Filmus also pointed out that it is solvable in single-exponential time.

Note 3: The problem is solvable in linear time on DAGs, and if you allow repeating edges, the answer is always infinite when your graph has a cycle.


Expressing division in relational algebra in terms of other operations So, I've been conferred upon the opinion that:

  Union, difference, cross product, selection, projection form the "complete set of relational operations".
  That is, any other relational operation can be expressed as a combination of these (excluding domain manipulation operations like aggregate functions I assume).

Question 1: Is that true ?

Question 2: If yes, can someone help me break down division in terms of those operations.

Let $R(A,B)$ and $S(B)$ be two relations. Division should find all values of A in R that are connected with all values of B (in S). Think $AB\div B=A$.

Question 1: Yes. $R\div S=\pi_A(R)-\pi_A(\pi_A(R)\times S-R)$

Question 2:

$\pi_A(R)\times S$ : this contains all possible AB pairs.

$R$ : this contains the actual AB pairs.

For the values of A that are connected to all values of B, after we do the difference, those will be gone. In the difference $\pi_A(R)\times S-R$ there are only values of A that are NOT connected to all B.

The rest is obvious.


DFA complexity of reverse of language recognized by "maximal" DFA Let's assume that DFA $A$ over the alphabet $\Sigma$ and with states $Q$ is maximal if for every function $f\colon Q\rightarrow Q$ there exists such word $w \in \Sigma^{*}$, that $q \cdot w = f(q)$ for every state $q \in Q$. Let $L \subseteq \{a, b, c\}^{*}$ be a non-empty language recognized by a maximal automaton with $n$ states.

Prove that all DFAs recognizing language $L^R$ have got at least $2^n$ states.

Maximality implies that every state is reachable. Let $w_q$ by a word such that $q_0 \cdot w_q = q$.

Since $L$ is non-empty and its complement is also non-empty, there must be some accepting state $q_1$ and some non-accepting state $q_2$. For every subset $A \subseteq Q$, let $w_A$ be a word such that $q \cdot w_A = q_1$ for $q \in A$ and $q \cdot w_A = q_2$ for $q \notin A$.

I claim that if $A \neq B$ then $w_A^R$ and $w_B^R$ are not equivalent modulo $L^R$. Indeed, suppose (without loss of generality) that $q \in A \setminus B$. Then $w_A^R w_q^R \in L^R$ since $q_0 \cdot w_q w_A = q \cdot w_A = q_1$, whereas $w_B^R w_q^R \notin L^R$ since $q_0 \cdot w_q w_B = q \cdot w_B = q_2$. The result immediately follows.


Lambda Calculus Notation I'm reading through the paper Transactors: A Programming Model for Maintaining
Globally Consistent Distributed State in Unreliable
Environments by John Field and Carlos Varela.

I have basic knowledge about the lambda calculus (typed lambda calculus to be more precise) thanks to a class I took at my university.

However, I'm stuck finding out what the rule shown below actually means. I have looked through the Types and Programming Languages book by Benjamin Pierce but I can't seem to find an explanation.

Could somebody help me understand what rule pur7 means?

It probably depends on what $\mathcal{F}$ is -- the text tells you.
Each $f\in\mathcal{F}$ is a build-in/primitive function (such as $+$) and [pur7] gives the result of applying it to some arguments. $[\![ f]\!]$ gives the semantic interpretation of the function, and applying that to the arguments $v_1,\ldots,v_n$ gives the result of the function.


how to maximise the no of edges selected in the graph in form of cycles of unbounded length? Recently i started looking the perfect cycle cover algorithm related to kidney exchange problem where it is considered as NP-Complete for cycles restricted to a length>2. However if cycles are not restricted by removing the length constraint it is considered as solvable in polynomial time ,But if perfect cycle cover doesn't exist and just we need to maximise the no of edges selected in form of cycles(So as to maximise the no of kidney exchanges), also no restriction on cycle's length, then how do we do it?

I am thinking of finding all cycles in the graph and then one by one remove the cycle's edges from the graph and then find the cycles in the residual graph and so on till no more cycles exist and then sum up all the cycle's lengths continuing this for all cycles and find the solution with maximum edges selected. But since this is not a good solution i want to know how to solve this maximising problem

A solution is to solve the assignment problem. Let's call $G(W, E)$ your initial graph and build a weighted bipartite graph $G'(U,V,E')$:

on the first side $U$, you have one vertex $u_i$ for $w_i \in W$. In the kidney exchange analogy they are the donors.
on the other side $V$, you also have one vertex $v_i$ for $w_i \in W$. In the kidney exchange analogy they are the recipients.

Now, for every $e \in E$ linking $w_1$ and $w_2$, put two edges in $E'$:

$u_1$ to $v_2$, weight $0$
$u_2$ to $v_1$, weight $0$

They represent the potential trade.

Also, for every $w_i \in W$, add an extra edge in $E'$:

$u_i$ to $v_i$, weight $1$

These edges represent the possibility to have no cycle for $w_i$ in the optimal solution.

Now solve the assignment problem using Hungarian algorithm ($O(n^3)$), trying to minimize the edges selected in the assignment. You get the optimal solution maximizing the number of vertex covered by cycles.


Can quick sort time complexity be $\Theta(n\sqrt n)$ for some inputs? I know that the time complexity of quick sort in the worst case is $\Theta(n^2)$ and in the average case is $\Theta(n \log n)$. Can it be $\Theta(n\sqrt n)$ for certain inputs?

Assume the array is sorted. If you always pick the element at n/2 as pivot then the time is O(n log n). If you always pick the first or last element it’s $O(n^2)$.

So which pivot gives you $O(n^{1.5})$?


How are interrupts discovered? In the textbook I'm reading, it states that

  If the interrupt is of a lower/equal priority to the
  current process then the current process continues
  If it is of a higher priority the CPU finishes its current
  Fetch-Decode-Execute cycle. The contents of
  the CPU’s registers are copied to a st...

In short, the CPU reacts instantly to the interrupt and either ignores/defers it or waits until the current cycle is completed before processing it.

I don't know if this is just a simplification, but this doesn't seem right...

I thought interrupts were pushed into a buffer, while the CPU is running, and after every cycle, the buffer was checked by the CPU. This makes more sense, and seems more plausible, but also contradicts the previous explanation.

Does the CPU physically get interrupted by the interrupt, or does it briefly check the buffer after every cycle?

I don't know much of the terminology, besides "an interrupt service routine."

Edit: Is it a mixture of both? The highlighted explanation references a process, which I realise could encompass many CPU cycles, which are ended in the check of the buffer. If the precedence is higher, the process is popped out, for the ISR.

It would only make sense to service interrupts after a full cycle completes, not immediately, because intermediate values are only saved to the register file at the end of each cycle. Being able to service an interrupt at any point in the cycle would add a lot of complexity to a processor for very little benefit. Interrupts are time-critical, but they're typically not microseconds and nanoseconds critical.

How this happens specifically is a matter of micro-architecture, so it can vary from processor to processor, and the processor manufacturers do not share that level of implementation detail.
The interrupt hardware does not queue interrupts. Different hardware interrupts are asserted by electrifying pins on the processor. When an interrupt pin is sensed, the processor transfers control to a special piece of software called the interrupt service routine in the operating system. Thus, handling an interrupt requires many cycles at a minimum. It is possible that an interrupt could be dropped if two interrupts were to occur near-simultaneously.
However, modern OSes use a variety of techniques to handle interrupts efficiently, some of which might involve queuing. These techniques improve the behavior of the computer as well as essentially eliminating the possibility of dropping interrupts under normal conditions.

A classic approach used in Linux is the top-half/bottom-half approach. When an interrupt occurs, the physical hardware is handled by the top half, but any significant processing is deferred to the bottom half that can run at a later time. For example, suppose we're writing a driver for a network card. The top-half of the network card driver might be responsible for copying an incoming packet from the network card into the computer's memory and clearing the interrupt, while the bottom half (also called a tasklet in Linux) is responsible for processing the packet and routing it. This allows the physical interrupt to be cleared as quickly as possible by retrieving and queuing multiple packets in software, even though the processor interrupt hardware does not have any notion of queuing.

However, modern Linux has superseded all of these concepts, and now it is common to use threaded interrupt handlers, which uses a similar deferred processing approach as the top-half/bottom-half mechanism, but simplifies the instantiation of the bottom half in the kernel. Here, there might not be an actual queue of interrupts, but each interrupt can be handled concurrently by a different thread in the kernel.


Prove { | TM M on input 3 at some point writes symbol "3" on the third cell of its tape} is recursively enumerable but not recursive Question: Let $$S =
\{\langle M\rangle\mid \text{TM }M\text{ on input 3 at some point writes symbol “3” on the third cell of its tape}
\}.$$ Show
that $S$ is r.e. (Turing acceptable) but not recursive (decidable).

I'm bit confused about this question, I'm not even sure how exactly should I start an approach to it. As I study from Sipser's book, in general when we prove a language is undeciable, we use contradiction to show that if $S$ is decidable, then by doing some trick, $A_{\text{TM}}$ is also decidable but it's not. Thus, $S$ is not decidable. However, this question also asked to show $S$ is acceptable. I'm thinking if we show that $S$ is undecidable, it's sufficient to see that $S$ is acceptable?(I'm totally not sure) Any suggestion?

First we assume for the $S_3$ is decidable and let TM $R$ be the decider for $S_3$. With $R$, we can test whether $M$ writes symbol $``3"$ on the third cell of its tape at some point. If $R$ indicates that $M$ doesn't write $``3"$ on the third cell, reject because $\big \langle M,3 \big \rangle \notin A_{TM}$. If $R$ indicates $M$ writes symbol $``3"$ on the third cell, we can do the simulation without looping. Thus, if TM $R$ exists, we can decide $A_{TM}$, but we know that $A_{TM}$ is undicidable, by contradiction, we can conclude that $R$ doesn't exist. Hence, $S_3$ is undecidable.

Let's assume $S_3$ is decidable so we can obtain contradiction by having TM $R$ decides $S_3$, and construct TM $M'$ to decide $A_{TM}$ as follows.

$M'$ = $``$On input $\big \langle M, 3 \big \rangle$:

Run TM $R$ on input $\big \langle M, 3 \big \rangle$.
If $R$ rejects, $reject$.
If $R$ accepts, simulate $M$ to write symbol $``3"$ on the third cell of its tape.
If $M$ has accepted, $accept$; if $M$ has rejected, $reject$."

Clearly, if $R$ decides $S_3$, then $M'$ decides $A_{TM}$. However, since $A_{TM}$ is undecidable, so we know $R$ doesn't exist and hence $S_3$ must be undecidable.


removing indirect left recursion I want to remove indirect left recursion from these rules:
    S-->TU,
    T-->US|b,
    U-->ST|a

I don't know if I can implement the algorithm correctly. My assumption is to make it like this:
S-->TU, T-->U'b, U'b-->U'a

Is this correct?

No. The first language is non empty (e.g., it contains the word "ba"), while the second language is empty.


What exactly is a clique cover problem? I am really confused about clique problem and clique cover problem. I tried googling it,but I don't see to be able to visualise the clique cover problem.

A clique is a simple undirected graph with all of the possible edges. It is also known as a complete graph, but clique is more often used to referring to subgraphs that are complete graphs.

The clique cover problem asks whether a graph's vertices can be partitioned into $k$ or fewer sets such that each set of vertices induces a clique. That is, $V = V_1 \cup V_2 \cdots \cup V_k$ such that if $u, v \in V_i$ then $uv \in E$. For example, $C_4$ (a cycle of 4 vertices) can be partitioned into 2 cliques by choosing two non-adjacent edges. If the vertices were 1, 2, 3, 4 and the edges 12, 23, 34, 14, then we could write $V = \{1,2\} \cup \{3,4\}$, and check that $12$ and $34$ were edges as required.

This is different from the clique problem, which asks whether there is a clique in the graph of size at least $k$ (and does not care about the structure of the rest of the graph. For example, in $C_4$, there is a clique of size 2.


Can we apply the Master Theorem to the following recurrence? Our recurrence is

$$
T(n)=
\begin{cases}
T(\lfloor{n/2}\rfloor)+(\log(n))^{2}, & \text{if $n>1$} \\
1 & \text{if $n=1.$}
\end{cases}
$$

I have identified $a = 1 > 0$, and $b = 2 > 1$. I am having trouble identifying the $c$ (for $n^{c}$ in $f(n) =(\log(n))^{2}$. The best I could break it down to was $(\log(n))^{2} = \log(n)^{1}*\log(n)^{1}$, which doesn't seem to be the form we are looking for, as $\log(n) \ne n$. Also, how do we take the floor operator into account?

If it follows that we can't apply the Master Theorem (which seems to be the case), what is the culprit?

So, we have that $f(n) = O(n^c \log^k(n)) = O(n^0 \log^2(n))$; and since $log_b(a) = log_2(1) = 0 = c$, we are in the 2nd case of the Master's theorem (work to divide the problems is comparable to the work on subproblems (wiki)); thus, applying the theorem, we get $T(n) = \Theta(log^3(n))$.

On the floor operation, I don't know what is the cleanest way of solving it; one way could be to prove it for $n = 2^m$, and then extend to all $\mathbf{N}$ by monotonicity.

We can also calculate $T(n)$ directly:

$$T(n) = T(n/2) + log^2(n) = \sum_{j=0}^{log(n)} log^2(2^j) = log^2(2) \sum_{j = 0}^{log(n)} j^2 = \theta(log^3(n))$$


Product of all nodes except for one in Binary Tree Assume we are given a binary tree with an integer sitting at each node. I am looking for an efficient way to find for every path from the root to a leaf every possible product with exactly one node omitted. I am looking for a solution without divisions (i.e. integers can be zero).

One way to go about this I thought of is
I can compute all possible partial products starting at the root. That is each node stores the product of the unique path from the root up this node ( but except the integer stored at that particular value ). Then for each leaf node I can walk up the path to the root node multiplying the integers on the way. At a given node before accumulating the node into the product I can multiply the product with the prefix product stored in the node.

It feels like I am doing a lot of redundant multiplications when visiting each path from a leaf to the root, since these paths potentially share a lot of nodes. Is there a way faster way to do this?

One simple approach: for an internal node $x$, let $P(x)$ denote the product of the integers on the path from the root to $x$, and let $Q(x)$ denote the set of integers obtainable as the product of all but one of the integers on the path from the root to $x$.  Now, descend the tree from the root down to the leaves, computing $P(x)$ and $Q(x)$ for each node $x$ as you go.  Note that you can compute $P(x),Q(x)$ from $P(w),Q(w)$, where $w$ is the parent of $x$.

The asymptotic worst-case running time will be $O(n^2)$.  No algorithm has better worst-case asymptotic running time, as there can be $\Theta(n^2)$ different products that you need to output, so any correct algorithm will need to have worst-case running time at least $\Theta(N^2)$.


Algorithms for logical synthesis of multiple output bits? Karnaugh maps and the Quine–McCluskey algorithm can be good choices for coming up with fairly minimal logical expressions that match the requirements of a truth table.

What if I have a situation where I have $M$ input bits and $N$ output bits though?

A naive way to deal with it would be to solve each output bit independently and come up with $N$ logical expressions.  The problem with that is that in circuitry or in CPU implementations, you can do multibit operations which can potentially handle a more optimal logical expression which takes into account several, if not all, of the bits at once.

Are there any algorithms to come up with a fairly minimal logical expression when you have $M$ input bits mapping to $N$ output bits?

as you realize, while universal, Quine-Mcclusky is only a "bitwise" construction method (single bit output) that does not recognize/ exploit common subpatterns for multibit outputs. multibit function construction optimization is a very broad area handled by EE type papers/ applications/ algorithms, there are very many published. the general topic is "logic synthesis". there is also a very broad array of software built for this purpose both commercial and public domain. here is an example of a relatively recent survey of algorithms and also a technique of using known/ previously computed circuits in a library-like context. this paper is useful here in that it refs many of the top systems in use and gives a consolodated view that you seem to be asking for in particular.

Lazy Man’s Logic Synthesis / Yang, Wang, Mishchenko


Why it is not $O(m)$ but $O(\log m)$? I am reading the lecture notes and have a question. I am trying to understand the beginning of Section 3 on page 2.

Problem: Given an input stream $\sigma$, compute (or approximate) its length $m$.

Naive solution: $O(\log m)$ bits, exact solution.

I don't understand why it is not $O(m)$ bits but $O(\log m)$ bits. Any help would be greatly appreciated.

As a definition, the input size of a problem is the minimum number of bits $(\{0,1\})$ needed to encode the input of the problem. Since it is given that input length $|\sigma|=m$ , you should have $Ceil ( {\log_2 m}) $ bits to encode $\sigma$.


$T(n) = 2T(n-1)$ Recurrences What would be the complexity of the following recurrence?

$$T(n) = 2T(n-1)$$

Note: The original version of the post included the initial values $T(0) = 0$ and $T(1) = 1$.

If $T(n) = 2T(n-1)$ for all $n > C$ then, as you can prove by induction,
$$ T(n) = 2^{n-C} T(C). $$
In particular, in your case $T(n) = 2^{n-1}$. Note that given your initial values, the recurrence $T(n) = 2T(n-1)$ cannot hold for $n=1$; presumably it holds for all larger $n$.

You are asking for the complexity of the recurrence. Recurrences have no such thing as complexity. A recurrence might describe the running time of an algorithm, and then its solution is the time complexity of the algorithm. But a recurrence can describe any number of things, or even be completely abstract.


How can one measure the time dependency of an RNN? Most of the discussion about RNN and LSTM alludes to the varying ability of different RNNs to capture "long term dependency". However, most demonstrations use generated text to show the absence of long term dependency for vanilla RNN.
Is there any way to explicitly measure the time dependency of a given trained RNN, much like ACF and PACF of a given ARMA time series?
I am currently trying to look at the (Frobenius norm of) gradients of memories $s_k$ against input $x_l$, where $l\le k$, summed over training examples $\{x^i\}_{i=1}^N$ - $$\text{Dep}(k,l):=\sum_{i=1}^N \big\|\frac{\partial s_k}{\partial x_l}(x^i)\big\|_F$$ I would like to know if there are more refined or widely-used alternatives to this prototype.
I am working with time series so I treat the inputs $\{x_t\}$ as realization of a random process $\{X_t\}$, thus by "current" I mean $x_i,s_i$ for some fixed $i$, "the past" I mean $\{x_j\}_{j=1}^{i-1},\{s_j\}_{j=1}^{i-1}$ and "time" I mean the index $t$.
I guess that the "long-term dependency" in literature refers to the sensitivity of the current memory $s_k$ w.r.t. past inputs $\{x_j\}_{j=1}^{k-1}$, hence the prototype I formulated.

I am not aware of any standard or widely-used metric for this. I think what metric would be appropriate would depend on what you want to use it for.
The issues with RNN is "forgetting".  If you feed a long sequence of inputs $x=(x_1,\dots,x_n)$ into a RNN, where $n$ is too large, the problem is that often the final decision is determined by the last few values ($\ldots,x_{n-1},x_n$) and the earliest values ($x_1,x_2,\ldots$) have been "forgotten" and do not affect the final decision.  This is undesirable in many settings.
Your metric would be one reasonable way to get a feeling for this.  Another reasonable way might be to to feed in an input $x=(x_1,x_2,\dots,x_n)$, then change just $x_1$ to get a new input $x'=(x'_1,x_2,\dots,x_n)$, feed in $x'$, and compare the outputs of the RNN on $x$ vs $x'$; and repeat for many training samples or test samples $x$.


Error correction for windowed reads from cyclic tapes I have an array of N symbols written on a cyclic tape. I read a sequence of M symbols starting from a random place on the tape. What error correcting scheme and even a coding scheme should I use for such "channel"?
Also will this problem  be simpler if tape is not cyclic?

I don't know if this problem has been studied, and I bet there will be better solutions, but I'll suggest a scheme that I suspect might work well enough, even if it's not optimal.
Naive approach: brute-force decoding
I would bet that any erasure code would work, if combined with brute-force decoding.  For decoding, I am imagining that a naive algorithm is to enumerate all possibilities for what the starting point was, decode under that assumption, and check whether it leads to a correct reconstruction that is consistent with that assumption (i.e., all symbols you read match).  Heuristically, I would expect that typically there will be only one decoding that is consistent with the observed data.  This might be a bit slow -- decoding might take $O(MN)$ time for many codes, because of need to try all $O(N)$ possibilities for the starting point -- but if that's acceptable, it should be something that's easy to implement.
For instance, you could use a Reed-Solomon code.  To encode a message, you treat it as a polynomial $p(x)$ of degree less than $M$ (say, of degree $M-1-\lg N$) over some finite field (i.e., the bits of the message determine the coefficients of $p(x)$).  Then, you write $p(\alpha^i)$ in the $i$th position on the tape, for $i=1,2,\dots,N$ (where $\alpha$ is a fixed element of the finite field).  For each guess at where the read symbols might have started from, you can decode using polynomial interpolation.  The entire procedure will take $O(MN \log M)$ time, to decode.
Faster approach: rolling hash
Here is an alternative that should be me faster: it runs in linear time.  I expect it will be close to optimal.
Encoding algorithm.  Let $C$ be a small constant, to be chosen later.  Let's suppose we have a message that is $M-C$ symbols long.  We'll compute a Rabin-Karp rolling hash of the message, a hash that is $C$ symbols long, and append it to the message.  Then, we'll repeat these $M$ symbols cyclically, to get a $N$-symbol word.  That will be the codeword that is the encoding of the message.  Encoding can be done in $O(N)$ time.
Decoding algorithm. Given an observed value $Y$ with $M$ symbols, we'll try all $M$ possibilities for cyclically shifting it to see which is correct.  We can recognize when we have the correct shift because the last $C$ symbols will be the valid hash of the first $M-C$ symbols.
Naively, this decoding procedure would take $O(M^2)$ time.  However, we can use the properties of the Rabin-Karp rolling hash to make decoding much more efficient.  Let $H(x)$ denote the Rabin-Karp hash of $x$.  Note that we can apply the Rabin-Karp rolling hash to $Y$ and learn $H(Y_{1..i})$ for each $i$; we can compute all $M$ of these hashes in $O(M)$ time.
From $H(Y_{1..i-1})$ and $H(Y_{1..j})$, we can compute $H(Y_{i..j})$ in $O(1)$ time. Also, given two hashes $H(x_1)$ and $H(x_2)$, we can compute the hash $H(x_1||x_2)$ of the concatenation of $x_1$ and $x_2$ in $O(1)$ time.  Thus, for any candidate cyclical shift of $Y$, we can compute the hash of the first $M-C$ symbols in $O(1)$ time, given the precomputed values $H(Y_{1..i})$, and thereby check whether this candidate shift is correct (by comparing that hash to the last $C$ symbols of the shifted value).  This decoding algorithm does an initial $O(M)$-time precomputation to compute all of the $H(Y_{1..i})$ values, and then checks $M$ candidates, each of which takes $O(1)$ time, for a total decoding time of $O(M)$.
Choosing parameters. Lastly, I need to describe how we choose the constant $C$.  I suggest choosing it so that it is very unlikely that any incorrect decoding will survive the hash-value check.  Suppose each symbol is $b$ bits long.  Then, a $C$-symbol hash is $bC$ bits long, and each incorrect candidate shift has a $1/2^{bC}$ chance of being wrongly accepted (by having the hash value match just by sheer chance).  We test $M$ candidate shifts, so there is about a $M/2^{bC}$ chance that one of these is wrongly accepted.  We might set as a goal that this chance should be at most $1/2^{50}$ (so that the chance of wrongly accepting an invalid message is less than the chance of being struck by lightning multiple times, and less than the chance of a cosmic ray hitting your computer and causing a bitflip error, i.e., negligibly small).  This means we need $M/2^{bC} \le 1/2^{50}$, so it suffices to take $C = \lceil(50 + \lg M)/b \rceil$.


Formal way to model or describe distributed systems architecture I've been tasked to create the systems architecture for a distributed system.

One approach to designing this system is to pick systems architecture patterns, and then evaluate different technologies that implement those architectural patterns.

For example, a particular architecture might call for a message bus, and given that, I could choose between various off-the-shelf open source or commercial projects that implement a message bus.

While this approach yields a nice white-board diagram, and a high-level understanding of how the system will work, some drawbacks are:

its difficult to gauge the performance of the system as a whole without fully implementing it
its difficult to determine how well each pattern / implementation will mesh with the other components
because of that, choosing between patterns tends to be gut feelings similar to "Kafka is cool, I used it on project X and it did really well"
there are no hard guarantees about the performance of the system as a whole (consistency, availability, etc)

Is there a formal approach to modeling distributed systems?  Ideally one that provides a way to abstract patterns, and provide analytic tools for making predictions about the behavior of the system?

I am not sure what you mean by "formal approach" but have you looked at Petri Nets? Many consider Petri Nets to be a "formal approach".

Personally, I use Petri's net elements (Place, Transition, Input, Output) to organize my computer program (logic annotations to net elements). I also use it to organize requirements (annotations meant for human interpretation). I find it useful to begin with a diagram (technically, graphical annotations to net elements but if each graphic represents one and only one net element then the diagram may be used to generate the net elements). Then to aid my memory I use forms to create the annotations. Based on the diagrams and the forms, I create my computer programs.  For more information about this check out "Net Elements and Annotations for Computer Programming: Computations and Interactions in PDF".

Sometimes, I create a "high-level" diagram based on a Petri Net diagram to create a view of the system. [A high-level (Petri Net) diagram is a Petri Net diagram where one or more than one graphic object represented more than one net element]. Sometimes, I begin with a high-level diagram and break it down to a Petri Net diagram. In the "high-level" case, the form views are also applicable.


Impossibility of Distributed Consensus with One Faulty Process I'm reading Fischer et al.'s Impossibility of Distributed Consensus with One Faulty Process, and I don't quite follow 2 points:

The first is in the proof of Lemma 3, pg. 378:

  Otherwise, $e$ was applied in reaching $E_i$, and so there exists $F_i ∈ \mathscr{D}$ from which $E_i$ is reachable.

Why does there exist $F_i ∈ \mathscr{D}$ from which $E_i$ is reachable?

The second is more general: what does having at most one faulty process have to do with the theorem that "no consensus protocol is totally correct in spite of one fault"? In the part where

  We now show that it is always possible to run the system in a way that avoids such steps, leading to an admissible nondeciding run.

I don't see anything depending on having at most one faulty process. In fact, what would change if no process was faulty?

Adding context:

  If $E_i\in\mathscr C$, let $F_i = e(E_i)\in\mathscr D$. Otherwise, $e$
  was applied in reaching $E_i$, and so there exists $F_i \in \mathscr
D$ from which $E_i$ is reachable.

Of course, without the definitions of $E_i$, $e$, $\mathscr C$, and $\mathscr D$, this isn't much use either. We're given a configuration $C$. $e$ is by assumption an event applicable to $C$. $\mathscr C$ is the set of all configurations reachable from a given configuration $C$ where event $e$ has not been applied. $\mathscr D$ is all the configurations you get when you apply $e$ to the configurations in $\mathscr C$. $E_i$ is a(n $i$-valent) configuration reachable from $C$.

The first paragraph of the lemma shows that $e$ is applicable to all configurations in $\mathscr C$. Given this, if $E_i\notin \mathscr C$, then, by definition of $\mathscr C$ and the fact that $E_i$ is reachable from $C$, $E_i$ must be reachable via some configuration that applies $e$. Any run from $C$ to $E_i$ must have a first time where $e$ is applied. Any configuration before that is in $\mathscr C$ by definition. The configuration at the point $e$ is applied is in $\mathscr D$ by definition and the fact that $e$ is applicable to all configurations in $\mathscr C$. That configuration is $F_i$.

Again, your second quote lacks context. The "such steps" mentioned in it are the steps from a bivalent configuration to a univalent configuration. Avoiding "such steps" is only relevant if we must start from a bivalent initial configuration, which is what Lemma 2 establishes. Lemma 2 critically depends on allowing up to one faulty process. If the protocol did not have to work correctly in the face of up to one faulty process, then Lemma 2 would not apply.

The idea of Lemma 2 is that if we have two configurations that differ only in how the input register is set for a single process, then if they can both reach a decision without ever executing that process (i.e. that process is faulty), then they must reach the same decision, since, once we remove that process, they have the same set of processes with the same initial state receiving the same messages. If we assume there are no bivalent initial configurations (for contradiction), then by partial correctness it is necessarily the case that there are two configurations that would make different decisions, but differ from each other only by a single process' input. Thus a contradiction.

It's trivial to make a consensus protocol when no processes are faulty. Simply pick one process (via setting its initial state appropriately) to be the Decider. It copies its input to its output. All other processes do nothing. Clearly this scheme won't work if the Decider is faulty.


Does the space complexity of a recursive algorithm depend on the total no of recursive calls? I am confused whether space complexity of a recursive algorithm depends on the total number of recursive calls or not.

Say I have an algorithm which has exponential function calls, but stack size is linear, so in that case we can say that space complexity is not proportional to number of recursive calls but if we say that does it depend on the total number of recursive calls or not, then does it make sense to make such a statement because after all stack is made because of the recursive calls only?

So is it better to say that "stack size depends on the recursive calls but not on the total number of recursive calls"? Is this statement valid?

Yes, that's right.

The statement "space complexity is $f(n)$" means that, if we had only $f(n)$ memory and no more, it would still be possible to run the algorithm.

As an example, say we are generating all permutations of length $n$ recursively.
Then we make $c_1 \cdot n!$ recursive calls but, at every moment, use at most $c_2 \cdot n$ memory.
A hypothetical machine with $c_2 \cdot n$ memory, and no more, would still run the algorithm correctly.

The space complexity depends on the structure of recursive calls, not simply on their number.


Automaton accepting $\{a^{2i}bc^{2k} \mid i, k \in\mathbb{N}\}$ How can I produce an automaton accepting $\{a^{2i}bc^{2k} \mid i, k \in\mathbb{N}\}$? I am essentially confused about exactly what the $2i$ and $2k$ mean. Does that mean that the automaton only accepts strings where the number of $a$'s and $b$'s are multiples of $2$ and there is one occurrence of $b$ between $a$ and $c$? Any help is greatly appreciated, thanks.

Yes, it means exactly that. $i$ and $k$ are arbitrary natural numbers, so $2i$ and $2k$ are arbitrary even natural numbers.


Looking for an algorithm to minimize cost of edge traversals in a bipartite graph subject to constraints I have a set of urns that can each hold different amounts of sand. Porters can deliver sand to each urn subject to a transport fee per unit of sand. Each porter has a finite amount of sand they are capable of delivering to each urn. The objective is to fill the urns with all the available sand while minimizing total cost. Here's a motivating example:

Black circles show porters. The value in the center of the porter circles show the total amount of sand they can transport. Gray squares show urns. The value in the center of the urns show the amount of sand an urn can hold. Porter_Urn edges show the cost of transporting 1 unit of sand to a given urn. Using this example, Porter 1, which has 100 units of sand could transport 1 unit of sand for a cost of 50 to Urn 3, which can hold a total of 65 units of sand. That would be very expensive!
Is there an algorithm to solve this optimization problem? It seems like maybe a maximum flow problem or maybe a multi-knapsack problem? Or some other algorithm from Operations Research?

This is straight up a minimum-cost flow problem. All it's missing is a an edge from the source to each porter with zero cost and capacity equal to the porter, and a zero cost edge from each urn to the sink with capacity equal to that urn.


Minimum edge cover with a constraint An edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set. I am interested in finding the minimum edge cover of a tree such that each vertex is incident to an odd number of edges. Is anything similar studied in Computer Science?

There is at most one edge cover which touches each vertex an odd number of times. To see this, let us consider a more general problem, in which each vertex is labeled either "odd" or "even". We want to cover each vertex by an odd or even number of edges, according to its label.

If the tree contains more than one vertex, then we can always find some leaf. It it is labeled "odd", every solution must contain the unique edge containing it. We add this edge to the edge cover, remove the leaf, and modify the label at the other end of the edge accordingly. If the leaf is labeled "even", every solution must not contain the unique edge containing it, and so we simply remove the vertex. Eventually only one vertex will remain. There is a solution if and only if this vertex is labeled "even".