What is fastest algorithm for factoring out square from number I have $n$-digit integer $N=a^2b$, $b$ is square-free. In other words, $a$ is maximal square which divides $N$.

What is fastest known algorithm to find $a$? I can write algorithm of $O(n^2\sqrt{N})$ simply trying all squares that are smaller than $N$ and checking for divisibility.

Is this problem as hard as factoring integer?

Using state of the art factoring algorithms, you can substantially improve on the algorithm you state. It appears that no algorithm better than factoring is known at the moment. See this question on mathoverflow.


Why high and lower bit of generator must be 1? Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 213:

  When the polynomial code method is employed, the sender and receiver must agree upon a generator polynomial, $G(x)$, in advance. Both the high- and low-order bits of the generator must be 1. To compute the CRC for some frame with $m$ bits corresponding to the polynomial $M(x)$, the frame must be longer than the generator polynomial. The idea is to append a CRC to the end of the frame in such a way that the polynomial represented by the checksummed frame is divisible by $G(x)$. When the receiver gets the checksummed frame, it tries dividing it by $G(x)$. If there is a remainder, there has been a transmission error.

My question is how do you determine high order bit? And why high order bit and lower order bit, both must be one? From my understanding, it is used to detect burst error but is my understanding true?

The low order bit, also known as the least significant bit (LSB), is the "ones" bit of the number. For example, in 001101, the LSB is the rightmost bit 001101.

The high order bit, also known as the most significant bit (MSB), is the "topmost" bit of the number. In our example 001101, it is the leftmost bit 001101.

The two terms are also used figuratively (in general discourse): a high order bit is something important, and a low order bit is something not important.

Now to your question. We represent a message $m_0,\ldots,m_n$ by a polynomial $M(x) = \sum_i m_i x^i$. Given a generator polynomial $G(x)$, the idea is to extend the message to a new message $M'(x)$ that satisfies $G(x) \mid M'(x)$.

If the low order bit of $G(x)$ is zero, then such an extension isn't always possible. Indeed, the low order bit of $G(x)$ is zero iff $x \mid G(x)$. If this is the case, then $G(x) \mid M'(x)$ implies $x \mid M'(x)$, i.e. $m_0 = 0$. So if the lower order bit of $G(x)$ is zero, we will only be able to extend $M$ to $M'$ if $m_0 = 0$ (and even this is not necessarily a sufficient condition).

If the high order bit of $G(x)$ is zero, then the problem is a different. The probability that $G(x) \mid M'(x)$ for a random $M'$ is $2^{-\deg G(x)}$ (assuming $G$ is irreducible, that is, cannot be factored nontrivially). Therefore CRC offers us $\deg G(x)$ bits of protection. We therefore want $G(x)$ to have the maximum degree possible. This corresponds to having a high order bit of one.

In practice, $G(x)$ is stored without its high order bit: an 8-bit CRC polynomial really corresponds to 9 bits 1xxxxxxxx, but there is no need to store the 1.


Updating an AVL Tree Based On Balance Factors I'm looking at the lecture review for one of my computer science classes and I'm having trouble coming up with an answer. Could someone help me work through it?

Background:

Let the balance factor of a node be defined by $\left| height(\text{right sub tree}) - height(\text{left sub tree}) \right|$.

Questions:

Give the balance factor for the nodes in slides 27-30 (given below)
Instead of storing the heights of the nodes, can we store the balance factors of the nodes and update an AVL tree (for insertion and deletion) based on this information?

Here are the relevant slides:

I will answer the second question.

  Instead of storing the heights of the nodes, can we store the balance factors of the nodes and update an AVL tree (for insertion and deletion) based on this information?

Yes, actually that's the whole idea behind the avl tree. All balance factors are always in range [-1, 1], so you need only two extra bits per node to store it.

After insertion you simply climb up the tree and update balance factors:

decrease if the left sub-tree became higher,
increase if the right sub-tree became higher,
retrace the tree if the balance factor becomes -2 or 2 (this can be achieved by local rotations on the tree),
if balance factor becomes 0, then the tree became balanced and no further work is required.

For more details check wikipedia page.

If you need more mathematical analysis on how the balance factors change after local rotations, check my question/answer here.


Counting sort on non-integers - why not possible? What is it about the structure of counting sort that only makes it work on integers?

Surely strings can be counted?

''' allocate an array Count[0..k] ; initialize each array cell to zero ; THEN '''
for each input item x:
    Count[key(x)] = Count[key(x)] + 1
total = 0
for i = 0, 1, ... k:
    c = Count[i]
    Count[i] = total
    total = total + c

''' allocate an output array Output[0..n-1] ; THEN '''
for each input item x:
    store x in Output[Count[key(x)]]
    Count[key(x)] = Count[key(x)] + 1
return Output

Where above does the linear time break down if you try to use counting sort on strings instead (assuming you have strings of fixed length)?

If you naively apply the algorithm you need an encoding $f$ of strings of length $m$ into integers such that $s_1≤s_2$ iff $f(s_1)≤f(s_2)$. The bound on these integers is necessarily at least $c^m$ where $c$ is the number of possible characters.

You then have a complexity in $O(nc^m)$ where $n$ is the number of elements to be sorted. This could be interesting when $c^m$ is not too big compared to the usual bound $\log n$, which is possible, in very peculiar cases.

In general, one would prefer the bound $O(n\log n)$ which does not depend on the length of your strings and in general much faster than $O(nc^m)$. To give a formal comparison between them, the former would be $O(s\log s)$ and the latter $O(sc^s)$ where $s$ is the size of the input.

However what is possible if you know that you will have a number of different strings no greater than some $k$, and that there will be a lot of occurrences of the same strings, is to build a correspondence between these strings and $\{1,\dots,k\}$ on which you will apply the counting sort, thus obtaining a complexity of $O(kn)$ i.e. linear (since $k$ is constant). But in this case the counting sort is not the only one reaching a linear complexity, for example all algorithms using balanced trees can be adapted to be linear, even insertion sort which is quadratic in the worst case, becomes linear.


Converse proof for random coding capacity of AVC I want to see the converse proof for the random coding (shared randomness) capacity of AVC. All I can find online is Csiszar Narayan's AVC paper which looks at deterministic coding. Further, the proof itself is quite dense (using Lemma 2 in the paper).
I am wondering if there is any work that proves the converse of AVC random coding capacity (shared randomness). If anyone can write the proof here then that works as well. I am ok with a proof for deterministic coding capacity of AVC as well if it is different from the above-mentioned paper.

A complete proof appears in Blackwell, Breiman and Thomasian, The Capacities of Certain Channel Classes Under Random Coding. This paper is linked from the Wikipedia article on AVCs.


Running Floyd-Warshall algorithm on graph with negative cost cycle I am trying to find the answer to the following question for the Floyd-Warshall algorithm. Suppose Floyd-Warshall algorithm is run on a directed graph G in which every edge's length is either -1, 0, or 1. Suppose that G is strongly connected, with at least one u-v path for every pair u,v of vertices, and that G may have a negative-cost cycle. How large can the final entries A[i,j,n] be, in absolute value (n denotes number of vertices). Choose the smallest number that is guaranteed to be a valid upper bound?
There is the following answers:

+∞
n^2
n - 1
2^n

I have ruled out 3. (n-1) and 1. (+∞) since if a graph has a negative cost cycle, the absolute final value of a path including a negative cycle can be increased further than n-1. The answer also cannot be +∞ since the algorithm stops after a finite number of steps. But I am having trouble between answers 2. and 4. I am more inclined to 4. since I have run some test cases, and final values seemed to comply to an exponential growth. But I cannot find a proof for it.

I think the answer is 4, and here is why.

Assume the graph is fully connected with all edges having weight of -1.

Now let's consider the three loops of Floyd-Warshall algorithm:

for k = 1 to n:
    for i = 1 to n:
        for j = 1 to n:

Since -2 is "shorter" than -1, after we finish k = 1, the weight for i -> k = 1 -> j is -2 for most i and j (exceptions would be i = k and j = k).

After we finish k = 2, the weight for i -> k = 2 -> j is -4 for most i and j. This is because i -> 1 -> 2 -> 1 -> j is the shortest, giving us -4.

And so on and so on for the exponential growth.

Floyd-Warshall algorithm does not guarantee that we will find a simple shortest path, that is, a path containing only one instance of each vertex.


If we allow a database, what complexity class it is? Let we have some problem $A$. Input length is $n$. Now we write a database that will store info about some positive instances of problem $A$. For every $n$ size of $n^{th}$ sector of DB is $O(f(n))$. $f(n)$ is some function.

Then we assume that some solver for problem in complexity class $C$ (for example, $GI$) can use this DB to solve the problem $A$. Can we say that $A\in C/f(n)$ ($C$ solver with advice of size $f(n)$)?

You can say anything you want, if you define your terms and your notation and make it clear what you are saying.

In this case I would not expect someone to know what you mean by $M/f(n)$ or by $A \in M/f(n)$.  Something like $P/\text{poly}$ is well-understood, but $P$ is a complexity class, and $M$ is a specific machine.  Rather than risking confusion, just say what you mean -- it only takes a sentence to say that the problem can be decided by $M$ using advice of size $f(n)$.


How to transform lambda function to multi-argument lambda function and how to rewrite or approximate terms? I am trying to do the formal semantics (Montague grammar, abstract categorial grammar) of natural language and encode the sentence John is boss. The type system has to primitive types - e for entity and t for Boolean type. John has type e, is has type (e->t)->(e->t) and boss has type (e->t). The the full sentence is translated as the lambda expression:

(is(boss))(John): t

I don't like the chaining of functional application and more intuitive presentation could be by introducing new function IS of type (e, (e->t)) and hence the expression could become:

IS(John, boss): t

And by moving boss from the argument the function index we can arrive to the standard predicate expression with new predicate-function:

IS_BOSS(John): t

I have two questions regarding this example:

Does standard lambda calculus have multi-argument functions? As I guess that these calculus have such function by currying and hence the real type if IS is e->(e->t)->t. So, this part seems to be already answered.
And now is the main question - does lambda caluclus allow do function transformation - e.g. is there some operation which transforms is:(e->t)->(e->t) into IS:e->(e->t)->t? Are there some apparatus/algorithms/methods how can I express function is via the function IS and how can I transform terms involving is into terms that does not contain is and that contains IS? Are there some rewriting apparatus available for this in lambda calculus?

This question is inspired by the book https://www.amazon.co.uk/Elements-Formal-Semantics-Introduction-Mathematical/dp/0748640436 and uses notions and notation from this book.

Important note. I do not expect that is and IS are identical functions (but I would be glad to consider the case when some kind of identity is assumed as well). I expect that is is more general function (that is used for the processing of the raw text) and that I try to express it using more specialised function IS (which can convey more specific meaning, e.g. borrowing from pragmatics (branch of lingustics): I can analyse context and determine that in this context such detalization is desirable). Maybe rewrite operation should be used but maybe some other tools should be used - simply - how to transform term using these functions? Maybe I am just trying to approximate function is with function IS (of different type!) and is-terms with IS-terms? Are there such notions, theories?

Maybe I should look to higher-order rewriting of lambda terms? Is there example available how my terms could be rewritten inside such framework?

You are looking for currying and uncurrying which transform functions of type $A \times B \to C$ to functions of type $A \to (B \to C)$, and vice versa. Currying takes IS to is, while uncurrying takes is to IS. This is a standard and very basic technique in $\lambda$-calculus. There are many manifestations of currying and uncurrying, for instance in arithmetic it is the identity $c^{a \cdot b} = (c ^ b) ^ a$.

It is largely a matter of taste how you write multi-argument functions. The uncurried form $A \to (B \to C$ has the advantage that you can apply the function only to the first argument. In your case is boss is a useful concept which is expressible very neatly. With the other function you have to write λ x . IS (boss, x).

Note however that sometimes people do not include product types $A \times B$ in their versions of $\lambda$-calculus, in which case of course currying is unavailable (but nothing much is lost).


How to check if two sequences of setoid members are mutual rotations? Real world background: There are 2 independent sources of polygon definitions, with arbitrary parameters. Meaning each source has it's own floating point precision, starting point and orientation of vertices.

The problem is to find an algorithm, that would receive those 2 polygon definitions and by a certain margin declare them equal or not. If a cutting machine would receive those 2 inputs, would it cut out the same shapes? (Which is btw. the real motivation behind the problem.)

E.g.: If

  polygonA = ( (1.0001, 1.0002), (2.0000, 1.0001), (1.5001, 1.9998) )

  polygonB = ( (1.9998, 0.9999), (0.9999, 1.0002), (1.5002, 2.0001) )

and there is precision margin of 0.001 (i.e. 1 mm) then polygonA would be equal to polygonB.

This problem can formally formulated as follows:

Task and terminology

Assume we have a set $X$ and two sequences $S_1 = (a_1, a_2, \ldots,a_n)$ and $S_2 = (b_1, b_2, \ldots,b_n)$, where $a_i \in X, b_i \in X, \forall i \in [1..n]$.

We define, that two sequences are congruent and denote them $S_1 \cong S_2$ if $\exists k,l \in [1..n]$ such that $a_{k+i \pmod{n}}=b_{l+i \pmod{n}}, \forall i \in [1..n]$. (Plainly said, they would define the same cycle.) If $S_1 \cong S_2$ then we say that $S_1$ is a rotation of $S_2$ and vice-versa.

The task is to find an algorithm that determines if $S_1 \cong S_2$.

Problem

In the case that $X$ is a total order set the task can be solved quite easily with a linear algorithm. (Finding a lexicographical extremum of all rotations for both sequences and then comparing those extrema.)

The question is, is there linear algorithm if $X$ is a setoid? I.e. members of $X$ can be checked only for equivalence. If not, does at least exist an algorithm with a better complexity than brute force?

It might depend on $n$. If $n$ is prime then the following algorithm works in linear time. Compare $a_1$ to all elements in $a$ and to all elements in $b$. The resulting $a_1$ patterns must be congruent, and if they are, then they are congruent uniquely. Once you know the shift, it is easy to check whether the original sequences are congruent.

When $n$ is composite then you might run into trouble since there are several shifts possible. Still, it seems possible but messy to get a linear or quasilinear time algorithm.


Consensus protocols in multiplayer video games I'm not 100% sure this appropriate for CS. Sorry.

I'm looking for prior art on an idea I had, but either my Google fu is lacking, or it genuinely hasn't happened.

In distributed systems, there are a number of consensus protocols and implementations (Raft, Paxos, Zookeeper, etc.). There's also the Bitcoin blockchain. Both of these approaches allow the cluster/network system to recover in the face of split brains and sometimes in the face of an evil node.

In the games world, there are really only two architectures in use:

Client-server, where the server simulates the game and is the source of truth and the clients simply act as a dumb terminal. No cheating possible. (Sometimes the server runs on a client.)
Peer-to-peer, where all clients broadcast their status to all other clients. Cheating very possible.

I am thinking of a third architecture that enhances the peer-to-peer architecture with a voting-based cheat detection. Desynchronized game state would be rejected by a majority vote. A colluding majority would be required to cheat.

The practical purpose is two-fold:

To eliminate the necessity of the server-side implementation of game simulation (e.g., game state machine). In the client-server model, you need to either write the implementation of the sim twice or write it generically enough that it will run in both client and server environments. For practical reasons, a shared codebase is difficult to do.
To eliminate the computational burden of running simulations. For large online games, this burden is not insubstantial.

I'm wondering if there's any research on such a system (either similar systems having been invented and used or even a paper describing it) specifically with respect to multiplayer games.

Section IX of the following paper proposes a variant of your idea:

OpenConflict: preventing real time map hacks in online games.  Elie Bursztein, Mike Hamburg, Jocelyn Lagarenne, and Dan Boneh.  IEEE Security & Privacy 2011.

The difference is that they propose that detection can be done by the central server, after the fact, by analyzing all of a client's status messages for consistency.  Your scheme differs only by having other clients do the same analysis.  (Their proposal also has some extra hashing and signatures and cryptography, which can probably be ignored for your purposes.)

Their scheme is basically a more sophisticated version of what you propose: rather than requiring everything to be broadcast, it only has to be uploaded to the server at the end of the game.  This has two advantages: (a) it significantly reduces network traffic, because they upload to the server rather than broadcasting to everyone; (b) by using commitments and hashes, they don't have to broadcast the full status messages to all other players on-the-fly; instead, it's enough to batch up all of those messages and upload them at the end (all that they need to broadcast at each step is just a commitment/signed hash, which will be much smaller and thus much more efficient to broadcast).  I wouldn't be surprised if they were already familiar with your proposal, but considered it too trivial and too inefficient, and so wrote only about a more sophisticated version that is less obvious and more efficient.

I recommend you take a look at the following book:

Exploiting Online Games: Cheating Massively Distributed Systems.  Greg Hoglund and Gary McGraw.  Addison-Wesley.


checking whether turing machine passes at least k>2 states before accepting a word $L=\{\langle M,k\rangle \mid\exists w\in L(M) \text{ such that $M$ passes at least
 $k>2$ distinct states before accepting $w$}\}$
I try to think of reduction to prove that this language is neither RE nor coRE.
How to approach this problem? Is there a hint, or intuition?
I usually check whether Rice can be used, but the question here is not about the language itself

Clearly $L$ is acceptable (just simulate $M$ and keep track of the number of distinct states encountered during the simulation). We now show that it is not decidable.
If $L$ were decidable, you would be able to solve the Halting problem as follows:
given a TM $T$ and an input $x \in \Sigma^*$, construct a TM $M$ that ignores its input, simulates $T$ with input $x$ and, when the simulation is complete, accepts.
You can further ensure that, if $M$ accepts, then it also traverses at least $3$ distinct states by just transitioning from the initial state to another (distinct) state before starting the simulation of $T$.
Now check whether $\langle M, 3 \rangle \in L$. If the answer is affirmative, then there is some $w \in \Sigma^*$ for which $M(w)$ accepts, showing that $T(x)$ halts.
If the answer is negative then $M$ never halts, showing that $T(x)$ does not halt.


Show that the tree resulting from BFS is a spanning tree? Given that $G$ is some connected and undirected graph, and I want to run BFS on it from some starting vertex. How can I show that $T = \{ \{\text{predecessor}[u], u\} \mid u \text{ is a vertex}\}$ is a spanning tree of $G$?

Observe that any spanning tree of $G$ contains every vertex of $G$, and has no cycles. Use induction to show that on every iteration, the process creates no cycles (and also visits every vertex).


Are there any efficient algorithems to find packets similarities in a list? I would like to make a program which finds similar packets (there might be more then one class of similarity) in packet list (which is updated all the time). Are there any efficient algorithems to find these similarities?

By similarities I mean that they have the same size, type and payload.

I thought about using tree(with conditions on the branches just like  decision tree) or vector support machine with k classes (k>2), but it means that it should have a lot of classes/nodes. Say there are 10 different packets and 2 kinds of similar packets (3 packets in each group). Then there will be 10 classes with single packet, 2 classes with 3 packets - So its size depends on the amount of packets which can be really big.

thank you

There are many possible approaches for measuring document similarity:

edit distance
shingling
Jaccard similarity
TF-IDF and cosine similarity
https://stackoverflow.com/q/101569/781723
https://stackoverflow.com/q/8897593/781723
https://stackoverflow.com/q/29842137/781723

I suggest you think more about what metric makes sense for you, and review the literature on information retrieval and natural language processing to see what metrics have been used in other contexts.


How should $\lambda x. \lambda y. f z x y \stackrel{\eta}{=} \lambda x. f z x$ be read? I'm currently learning untyped $\lambda$-calculus and especially the $\eta$-reduction.

The professor hat the following in his slides:

$$\lambda x. \lambda y. f~z~x~y \stackrel{\eta}{=} \lambda x. f~z~x$$

I don't know how to read and understand this. Could you please explain it to me?

My try

On the left side and the right side is a function and they are $\eta$-equivalent.

The right side seems simpler, so I start with that.

It is a $\lambda$ function with one bound parameter $x$ and two unbound parameters $f$ and $z$. But here start my problems: What does $f~z~x$ mean? Is this a triple? Is it a function $f$ and a function $z$ and a function $x$?

I think in $\lambda$-calculus everything can be viewed as a $\lambda$-function, so $f$, $z$ and $x$ are functions. So the right side is the same as

$$\lambda(x) = f(z(x))$$

correct?

Applying the same logic on the left side, I get:

\begin{align}
\lambda x. \lambda y. f~z~x~y &= \lambda(x)\\
&= f(z(x(y)))
\end{align}

As $y$ is not in $\lambda(x)$ it is not bound. So we can simply remove it. Correct?

I think this could work. But I still don't know how to read it. I guess it will be something like:

"The lambda-function with the parameter $x$ that is a lambda function with a parameter y is f applied to z applied to x applied to y is eta-equivalent to the lambda function with the paramter x that is f applied to z applied to x".

Applications in Lambda calculus are assumed to be left associative, this means that $f~z~x~y$ is the same as $((f~(z))~(x))~(y)$.

With this is mind eta-conversion makes more sense. Wikipedia says:

  Eta-conversion expresses the idea of extensionality, which in this context is that two functions are the same if and only if they give the same result for all arguments. Eta-conversion converts between λx.(f x) and f whenever x does not appear free in f.

This means that $\lambda x. \lambda y. f~z~x~y \stackrel{\eta}{=} \lambda x. f~z~x$ is assumed to be true because $y$ does not change the result of the application $f~z~x$, its value is applied after $f~z~x$ is already evaluated.

You can find out more about eta-conversion by playing with it in the Haskell REPL:

Prelude> let z = 1
Prelude> let f x y = (+) ((+) z x) y
Prelude> :t f
f :: Integer -> Integer -> Integer
Prelude> f 1 1
3
Prelude> let f x = (+) ((+) z x)
Prelude> :t f
f :: Integer -> Integer -> Integer
Prelude> f 1 1
3

As you can se, it is easily possible to leave out a the parameter y without changing the meaning of your program.


Finding the Entropy of a random experiment with probability of $\frac{1}{3}$ Entropy is the randomness collected by an operating system or application for use in Cryptography or other uses that require random data. The formula for Entropy is $$H(p_1, ..., p_k)=-\sum_{i=1}^{k} p_i\log_2(p_i)[bit]$$

So if I were to calculate the Entropy of a coin toss. it would be
$$H(\frac{1}{2}, \frac{1}{2})=-(\log_2(\frac{1}{2})+\frac{1}{2}\log_2(\frac{1}{2}))=-(0-1)=1 Bit$$

But why is there a $\frac{1}{2}$ before the $\log$? Also if I were doing an experiment where the probability of an outcome is $\frac{1}{3}$ and there are $3$ outcomes, so would the entropy be

$$H(\frac{1}{3}, \frac{1}{3}, \frac{1}{3})=(\log_2(\frac{1}{3})+\frac{1}{3}\log_2(\frac{1}{3})+\frac{1}{3}\log_2(\frac{1}{3}))$$

Your formula is totally inapplicable in computer randomness harvesting.  I think that people use it because it's easy to write down.  Even then, it's not really usable - what's i exactly?  For any non trivial application, there are correlations.  Try using this formula for the English language. No you can't say there are just 26 letters as they are hugely correlated. There are two, three, four letter combinations, and then there are words and sentences that have lexological and grammatical structure. I don't know what you do with full stops.  The entropy rate will very much depend on who wrote the words and about what.  If you try the Shannon formula in it's most simplistic typical use case, "1111111111...0000000000..." has exactly 1 bit/bit of entropy. Clearly it doesn't.

Entropy harvesting by a computer kernel consists of sucking up hardware device interrupts including keyboard presses.  Non of this is uncorrelated.  The official cryptographic term is non IID (non independent and identically distributed). And for measurement of such non IID entropy,  there is no set standard. The best we have currently is either direct compression, or the NIST SP800-90B_Entropy Assessment tools (which also include compression as one of the tests). They may have been written by a chap using up his spare time.

Is von Neumann's randomness in sin quote no longer applicable? is a currently open question  featuring such entropy measurements.  So essentially coin toss randomness is completely different to operating system randomness.


Subgraph isomorphism on star multi-graphs with labelled edges My approach to the problem has been to reformulate it into something more recognizable, but I don't know the best way to solve the reformulated problems either. I list the original problem, an example, and two reformulations below. The second reformulation is equivalent to an unbalanced assignment problem with a binary cost matrix.

Original Formulation

I have two star multigraphs: A small pattern, and a large target. The graphs may have multiple edges between a single pair of nodes. The edges of each graph have labels from some small set of labels. I am looking for the most efficient algorithm to check if there exists a subgraph of the target which is isomorphic to the pattern.

Example

Consider the pattern

and the target

where edge colors represent labels. There is a subgraph of the target consisting of the nodes 1, 2, 3, and 5 (and some edges that I haven't given names) which is isomorphic to the pattern graph. Note that the subgraph need not be a node-induced subgraph, and is not in this case.

Reformulation 1

Enumerate the neighbors of the center of each graph: $1, 2, \dots n_{\mathrm{pattern}}$ and $1, 2, \dots n_{\mathrm{target}}$. Define $A_{i,j}=1$ if node $i$ in the target has at least as many edges of each type to the target's center as node $j$ in the pattern has to the pattern's center. If the constraint is not met, then $A_{i,j}=0$. The problem becomes: Given a binary matrix $\mathbf{A}$ with more rows than columns, does there exist a permutation of the rows such that the main diagonal is all ones?

Reformulation 2

You are given $n_{\mathrm{target}}$ workers to perform $n_{\mathrm{pattern}}$ tasks, where each worker is competent in only a subset of the tasks. Does there exist an assignment of workers to tasks such that each task has at least one competent worker assigned?

After you fix the star centers, your problem is simply bipartite matching.


Is necessarily the following language not decideable For A,B that are not decidable, does AB U BA not necessarily decidable?

I think that the answer is NO. Not necessarily.
I thought about the following example, but it does not refute exactly:

If we take A and A complement, and without losing generality the empty word is in A, than every word in A' is also in AA' U A'A, but I can't use it to show that every word in A is also in AA' U A'A.

If someone can help me how can I show that also A is in AA' U A'A the problem will be solved.

thank you very much.

Take some undecidable language $A$ and choose $B=A'\bigcup \{\epsilon\}$. $B$ is also undecidable, and the rest of the proof is just as what you have already done.


Conflict serializibility So, the task is to prove the following:

  If S is a schedule containing at most one write action, then S is conflict-serializable.

The answer is yes, but I disagree, because the following schedule contains at most one write action, and is not conflict-serializable:

  R1(A), R2(A), W2(A), R1(A).

Am I completely wrong? Or is the answer wrong?

The resulting precedence graph for your example will contain a cycle due to $R1(A) W2(A) R1(A)$. Hence its not conflict serializable. Since one example is sufficient to disprove the statement, therefore I agree with you. The answer might be wrong.


Maximal number of rotations after deleting a node in an AVL tree What is the maximal number $c$ of single rotations after deleting a node from an AVL tree? We treat double rotations as two single ones.

I know that it is $O(\log n)$ but I'm trying to find a more precise number – it is in $[\log n, 2\log n]$ of course.

Nevertheless, I am dying to see the exact value of $c$.

Note: This does not answer the question exactly. However, it would be helpful for further study.

Quoted from Section 6.2.3 (entitled "Balanced Trees") of TAOCP "Sorting and Searching", 2nd Edition:

  In order to figure out the running time of Algorithm A (for AVL search and insertion; [emphasis mine]), we would like to know the answers to the following questions:

  How many comparisons are made during the search?
  How much adjustment is needed in step A6?
  How often do we need to do a single or double rotation?

Before going into details, it summarizes:

  It is not difficult to derive upper bounds on the worst case running time, using Theorem A, but of course in practice we want to know the average behavior.
  No theoretical determination of the average behavior has been successfully completed as yet, since the algorithm appears to be quite complicated, but several interesting theoretical and empirical results have been obtained.

You would probably be interested in Theorem A mentioned above:

  Theorem A (Adelson-Velsky and Landis). The height of a balanced tree with
  $N$ internal nodes always lies between $\lg(N + 1)$ and $1.4404 \lg(N + 2) -
0.3277$.

You can also find many empirical results (and some theoretical results) in the following paragraphs.


Runtime analysis of a nested loop I have some difficulties performing the worst case analysis on this algorithm.
The outermost loop is executed $2N$ times.
The while loop, in the worst case, will increase by $2$ each time, so it performs $i/2$ basic operations ($*2$ because double call)

for (i=1; i<=2*N; i++) {
        j = 0;
        while (j <= i) {
            a[i] = function (function (a[i]));
            if (c[i][j] != 0)
                j = j + 6;
            else
                j = j + 2;
        }
    }

function is the basic operation.
Am I going the right way?

The worst case for the number of function calls is (as you already observed)

$$\sum_{i=1}^{2N}\sum_{j=1}^{i/2} 2 =\sum_{i=1}^{2N} i = \frac{2N(2N+1)}{2}=2N^2+N,$$

by Gauß' summation formula.


Machines for context-free languages which gain no extra power from nondeterminism When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines.

For the first and last levels1 (regular languages and recursively enumerable languages), it makes no difference to the power of the model whether we consider deterministic or nondeterministic machines, i.e. DFAs are equivalent to NFAs, and DTMs are equivalent to NTMs2.

However for PDAs and LBAs, the situation is different. Deterministic PDAs recognise a strictly smaller set of languages than nondeterministic PDAs. It is also a significant open question whether deterministic LBAs are as powerful as nondeterministic LBAs or not [1].

This prompts my question:

  Is there a machine model that characterises the context-free languages, but for which non-determinism adds no extra power? (If not, is there some property of CFLs which suggests a reason for this?)

It seems unlikely (to me) that it would be provable that context-free languages somehow need nondeterminism, but there doesn't seem to be a (known) machine model for which deterministic machines are sufficient.

The extension question is the same, but for context-sensitive languages.

References

S.-Y. Kuroda, "Classes of Languages and Linear Bound Automata", Information and Control, 7:207-223, 1964.

Footnotes

Side question for the comments, is there a reason for the levels (ordered by set inclusion) of the Chomsky hierarchy to be number 3 to 0, instead of 0 to 3?
To be clear, I'm talking about the languages that can be recognised only. Obviously questions of complexity are radically affected by such a change.

As far as I know, we do not know whether Non- deterministic context-sensitive languages are more powerful than deterministic context-sensitive languages. And the simplest reason behind this is: Till now no-one has been able to give a language that is accepted by the non-deterministic LBA and not accepted by the deterministic LBA. So if someone can come up with one such language that is accepted by ND LBA and not accepted by deterministic LBA then only this will be proven. As we know this method of proving is called proof by contradiction.
Because proving something is TRUE is a hard problem but proving something FALSE is easy, just get one instance where it fails and we're done.


Are NP-complete sets formed from two other sets only if at least one is NP-hard? This question is somewhat of a converse to a previous question on sets formed from set operations on NP-complete sets:

If the set resulting from the union, intersection, or Cartesian
product of two decidable sets $L_1$  and $L_2$ is NP-complete, is at
least one of $L_1, L_2$ necessarily NP-hard?  I know that they cannot
both be in P (assuming P != NP) since P is closed under these set operations.  I also
know that the conditions of "decidable" and "NP-hard" are necessary
since if we consider any NP-complete set $L$ and another set $B$ outside
of NP (whether just NP-hard or undecidable) then we can form two
new NP-hard sets not in NP whose intersection is NP-complete.  For
example: $L_1:= 01L \cup 11B$, and $L_2:= 01L \cup 00B$.  However,
I don't know how to proceed after that.

I'm thinking that the case of union might not be true since we can take a NP-complete set $A$ and perform the construction in Ladner's Theorem to get a set $B \in$ NPI which is a subset of $A$.  Then $B \cup (A \setminus B) =  A$ is the original NP-complete set.  However, I don't know if $A \setminus B$ is still in NPI or NP-hard.  I don't even know where to start for the case of intersection and Cartesian product.

The intersection of two non-NP-hard languages can be NP-hard.  Example: The solutions of any 3SAT instance are the set intersection of the solutions of a HORN-3SAT instance and an ANTIHORN-3SAT instance.  This is because a 3CNF clause must be either a Horn or anti-Horn clause and a 3SAT instance is the conjunction of such clauses.  3SAT is of course NP-complete; HORN-3SAT and ANTIHORN-3SAT are both in P.


Can Barrington's Theorem be used to speed up computation of some function ? How? How can Barrington's Theorem be used to obtain faster programs ? Assuming, I want to evaluate function greater than gt between two bits x and y, defined as $gt(x,y)=xy+x$, equal with $1$ when $x$ is greater than $y$. Now, let's say I have two numbers on $N$ bits and the problem expands.

Can Barrington theorem be applied to speed up computation ? Or not necessary speed the computation, but reduce the number of multiplications of the boolean circuit implementing the greater than function for two numbers on $N$ bits ?

Barrington's theorem probably isn't going to be useful to speed up computation.  Rather, it's a useful way to understand the power of different computing models.  For instance, it has been used to prove facts about what can be computed with log-depth circuits.  It has also been used as a tool in building fully homomorphic cryptosystems.


Enumerate all combinations of operations that fit memory and time criteria I have the following problem:

$x$ is the number of operations I have to perform.

$O=\{o_1,o_2,\ldots o_n\}$ is the set of possible operations.

I know beforehand the cost in terms of time and memory of every operation $o_i \in O$.

I have a limited amount of memory and computation time, $M$ and $T$ respectively.

What is the most efficient way to generate the list of computable combinations? i.e. I need to generate a set of computables $C=\{c_1,c_2,\ldots c_m\}$ such as:

$\forall c_i \in C, c_i$ is a combination (with possible repetition) of $O$ and $|c|=x$
$\forall c_i \in C$ the memory and time consumption should be less than $M$ and $T$ respectively.

I think this is an operations research problem, but I can be wrong. If so, what branch of operations research? If not, then what is the most suitable approach?

You can use uniform-cost search in the space of possible combinations of operations. Each node will be an ordered list of operations performed. Terminate the search when the maximum memory or time allotment is reached.


how to get rows with more than 1 appearance of a specific column in relational algebra I have a table like this:

PostId   |    Body    |    AuthorId
  2             b               F
  2             b               E
  2             b               C
  4             d               A
  4             d               E
  8             h               F

So what I want is to get all the rows that have more that 1 appearance of PostId. Here the result would be 2 and 4 because they appear more than 1 time. I want this in relational algebra.
I have already a relation that works just fine but in this relation I use aggregation methods and I don't really what to use count in my relation. I am wondering if there is a way to this with subtraction or division operators?
What I do for now is π PostId (σ c ≥ 2 ( γ Body; COUNT(PostId)->c R2)) to get the row with more than 1 appearance of PostId.
Thanks in advance for help

Here is a relational algebra expression given $R_2$ described in the question that uses set division operator
$$
\Pi_{\text{PostId}, \text{AuthorId}}(R_2) \div \sigma_{\text{AuthorId} = E}(\Pi_{\text{AuthorId}}(R_2))
$$
$\sigma_{\text{AuthorId} = E}(\Pi_{\text{AuthorId}}(R_2))$ will return a set $\{E\}$. Then by the definition of set division operator, we can see that only $(2,E)$ and $(4,E)$ belong to the $R_2$. Thus, the above relational algebra expression will return $\{2,4\}$. Also, we observe that both 2 and 4 are the only PostIDs that have more than one appearance. Thus, the above relational algebra expression gives the right answer.


Differences between Fuzzy C-Means and EM When clustering a set of data points, what exactly are the differences between Fuzzy C-Means (aka Soft K-Means) and Expectation Maximization?

In slide 30 and 32 of this lecture I found, it says that Soft K-Means is a special case of EM in Soft K-Means only the means are re-estimated and not the covariance matrix, why's that and what are the advantages / disadvantages? How does covariance matrix affect the outcomes of EM?

Another question about these two algorithms: When they converge, all the data points will be hard-assigned to a particular cluster if the probability of it being in the said cluster is highest, right?

The difference between the two schemes is the model of the clusters. Fuzzy C-means and K-means model their clusters as circles (spheres in n-dimensional space), EM-clustering models the clusters as probability density functions (PDFs). In Euclidean space, the latter can have elliptical shapes (using Gaussian PDFs), determined by their covariance matrices.

Thus the difference is that the assignment criterion for K-means is the distance to a centroid whereas the criterion for the EM-algorithm is the probability of a data point given the PDF of the cluster center.

The cluster centers in K-means are hard-assigned, in Fuzzy C-means they are not; but it is rather simple to get a hard decision by, as you stated, taking the cluster with the highest probability/smallest distance for a given data point.


Efficient way to calculate sum in sliding window? Assume you have a grid as below:

The square is the sliding window. I want to slide this window over all the possible position such that the window is contained in the grid (i.e the edges of the window should not cross the boundaries of the grid.)

For each such position I want to calculate the sum of the cells in the window.
I'd like to be able to do this with different sizes of windows as well.
More specifically, given some range for the possible widths and possible heights of windows, I want to calculate and store all the sums over the cells in the window, for all positions of the window, and for all possible width/height combinations.

As an example: if the possible widths are 2 and 3 and the possible heights are 4, 5 and 6, then there are 6 combinations: $2 \times 4$, $2 \times 5$, $2 \times 6$ $3 \times 4$, $3 \times 5$, $3 \times 6$ and for each such sliding window size, I want to store the sums over cells in the sliding window for all possible positions of the sliding window.

What would be an efficient way to do this?

Cheers

One possible way would be to store the sum of all the submatrices of the form $((0,0),(i,j))$. You can compute each of these sums in $O(1)$ time per entry (by using the previous entries).

If you then want to know the sum of the submatrix $((x,y),(i,j))$, you can compute this in $O(1)$ from the stored sums using inclusion-exclusion. If we let $S$ denote such a sum, then

$$S((x,y),(i,j))=S((0,0),(i,j))-S((0,0),(x,j))-S((0,0),(i,y))+S((0,0),(x,y))$$


How do I prove no algorithm exists for a given problem? Is there a general framework for showing that a problem has no algorithm? For example, to show that two problems are equally as hard to each other, we use reduction.

One example of where this was done, is Hilbert's 10th problem

The term or tag you are looking for is "undecidability" or "computability". The basic version of the theory of undecidability is a part of the theory of computation, which is an ingredient of the curriculum of all students majoring in Compute Science, as far as I know.

You can search for "undecidability" or "halting problem", the most famous and the most canonical problem that cannot be solved by an algorithm, in your textbook or course material. Or right here. There are also much stuff around.


Job scheduling with a bottleneck problem Given $n$ jobs $J_1,J_2,...,J_n$, each job requires $T_i > 0, T_i \in N$ time to complete.

Each job must be pre-processed and post-processed by a single machine M that can handle only 1 job at a time and both phases require 1 unit of time. After being pre-processed, job $J_i$ is sent to a machine with unlimited power (that can handle in parallel an unlimited number of jobs) and it will be ready in time $T_i$, then it must be sent (immediately) to machine M again for post-processing.

The associated decision problem is:

Input: the processing times $T_i >0, T_i \in \mathbb{N}$ of $N$ jobs, an integer $K\geq 2N$
Question: can we process all the jobs in time $\leq K$ using the above "bottleneck" model ?

Has this problem a name?
What is its complexity? (is it in $\sf{P}$ or is it $\sf{NP}$-complete?)

UPDATE 29 March:
As correctly noticed by M.Cafaro in his answer, the problem is similar to the
Unconstrained Minimum Finish Time Problem (UMFT) (see Chapter 17 of
Handbook of Scheduling Algorithms) which is $\sf{NP}$-hard (proved in
 W. Kern and W. Nawijn, "Scheduling multi-operation jobs with time lags on a single machine", University of Twente, 1993). As I can see, there are some differences because in my model:

the pre/post processing time is constant (1 unit of time)
as soon as the job is completed it must immediately be post-processed (the UMFT model allows delays)

I didn't found the Kern & Nawijn proof online, so I still don't know if the above restrictions change the difficulty of the problem.

Finally you can think the whole process like a single cook robot with a big oven; the robot can prepare different types of foods one at a time (all require the same time of preparation), put them in the oven, and as soon as they are cooked it must remove them from the oven and add some cold ingredients ... the "cook robot problem" :-)

This looks like the so called master-slave scheduling model introduced by Sahni. In particular, your problem falls under the Single-Master Master-Slave Systems. You can distinguish several cases:

1) If you do not add any additional constraint on the order of job execution (as in your case), the problem is called unconstrained minimum finish time problem (UMFT) and has been shown to be NP-hard;

2) Same Pre- and Postprocessing Orders: it is possible to design an $O(n \log n)$ algorithm to construct an order preserving minimum finish time (OPMFT) schedule;

Therefore, in case 1 your problem is $NP$-hard, while it is in $P$ in case 2.

Additional related problems are:

3) Reverse Order Postprocessing: For any given preprocessing permutation, $σ$ , it is possible to construct a reverse-order schedule, referred to as canonical reverse order schedule (CROS). Given a preprocessing permutation $σ$ , the corresponding CROS is unique. It is easy to establish that every minimum finish-time reverse order (ROMFT) schedule is a CROS.

4) no-wait-in-process constraint:

a) [MFTNW] Minimize finish time subject to the no-wait-in-process constraint;
b) [OP-MFTNW] This is the order-preserving version of MFTNW. That is, minimize finish time
subject to the no-wait-in-process and order-preserving constraints;
c) [RO-MFTNW] Minimize finish time subject to the no-wait-in-process and reverse-order
constraints.

Problems $a$ and $b$ are NP-hard, while $c$ admits a polynomial time solution.

Additional details in Handbook of Scheduling, chapter 17.


Sequential execution in $\pi$-calculus I am relatively new to $\pi$-Caculus and have a doubt wrt sequential execution in In $\pi$-Calculus .

Does passing of common names over common channels shared between two Agents, represent a sequential execution ? so is the below reduction semantics correct if I have to represent a sequential execution between Agent A,B and C where A and B share common channel x and share data c' and similarly B and C share channel y?

\begin{equation}
\begin{gathered}  \label{eq23}
 \frac{A \xrightarrow{\overline{x}(c)} A' \quad B \xrightarrow{{x}(c').\overline{y}(c'')} B'  \quad C \xrightarrow{y(c''')}C'
 \ }
 {A|B|C  \xrightarrow{\tau} A'| B'\left\{c/c' \right\}|C'\left\{c''/c''' \right\}}
\end{gathered}
\end{equation}

$\pi$-calculus can represent all sequential behaviour. The key rule responsible for sequential behaviour is that for input:

$$
  \overline{x}y \ |\ x(v).P \quad \rightarrow\quad P\{y/v\}
  $$

(and its replicated variant).
  The process $P$ becomes active only after the interaction at $x$
  has taken place. You can generalise this: if $X$ and $Y$ are two
  arbitrary processes such that $Y$ should execute only  after $X$
  has terminated, you can use something like:

$$
  (\nu a)(X' \ |\ a().Y)
  $$

Here $a$ is a  fresh name, i.e. does not occur in $X$ and $Y$.  The
  process $X'$ is exactly like $X$, except it outputs an empty message
  on $a$ upon termination of $X$.  Defining $X'$ depends on the precise nature of $X$ since
  $X$ may itself have multiple threads. If $X$ is sequential, then
  it's easy to define $X'$, just replace $0$ by
  $\overline{a}\langle\rangle$.
The whole purpose of the handshake on $a$ is to exchange one bit of information, namely that $X'$ has terminated.

The answer to your question "Does passing of common names over common channels shared between two Agents, represent a sequential execution?" is positive in a narrow sense that the continuation of the input side will only start after this interaction. However the sender might do other things in parallel. BTW, the rule you give isn't quite right. You need two $\tau$-actions because you are doing two interactions. Moreover, it looks like you are doing a bound output of $c$ abd $c''$, so the resulting processes should have an outermost $(\nu c'')(\nu c)$, or something like that.

You can also define subcalculi of $\pi$-calculus where all computation is sequential: for example by considering only processes that have at most one active output (heriditarily). An output is active, it it's not under an input.  This property being heriditary means simply that it's stable under reduction.

I close with a quote of R. Milner's from his "Elements of interaction":

  I make a disclaimer. I reject the idea that there can be a unique conceptual
  model, or one preferred formalism, for all aspects of something as large as concurrent computation, which is in a sense the whole of our subject -- containing sequential computation as a well-behaved special area.


How to find i largest numbers in unsorted array in O(n) where i <= n^(1/2) If we have length $n$ unsorted array such that each element is integer and different, how to find $i$ largest numbers in linear time O(n)? but $i \leq n^{\frac{1}{2}}$.
For example, if we have $A = [11, 6, 8, 1, 9, 100, 88]$ and input $i = 2$, then output is $[100, 88]$ (sorted).

Use a selection algorithm to find the $i$th largest number.  This can be done in linear time.  Then, do a second scan over the array to find all numbers larger than the $i$th largest number.  (With many selection algorithms, this last step is unnecessary, as they partition the array into elements smaller than the $i$th largest and larger than the $i$th largest.)


Can the zero-one principle be used to prove the stability of a sorting network When dealing with sorting networks, we can check the validity of a sorting network with only $2^n$ sequences of $0$ and $1$ (where $n$ is the size of the collection to sort) thanks to the zero-one principle:

  The zero-one principle states that, if a sorting network can correctly sort all $2^n$ sequences of zeros and ones, then it is also valid for arbitrary ordered inputs.

I have used this principle to prove that my sorting networks worked. However, I also wanted to check whether some of them were stable or not: in order to do so, I tried to feed pairs of $(0, index)$ and $(1, index)$ to the networks instead of simple $0$ and $1$ and checked whether the indices of elements with the same values were still in the correct order after the sort (of course, the sequences were sorted based only on the first value of the pair). It was sufficient to prove that my sorting networks weren't stable since the algorithm was able to find at least one sequence that wasn't stably sorted per network.

However, even if every sequence was stably sorted, I still wouldn't be sure whether the sorting networks are stable or not without answering this question: can the zero-one principle be used to prove the stability of a sorting network?

You can use a $0/1/2$ principle, in which the inputs are $\{0,1,2\}$, and $1$-inputs are also annotated by their indices. The network should sort the input successfully, maintaining the order of the $1$-entries. This is clearly a necessary condition, and it's not too hard to show that it is sufficient.

That doesn't quite answer your own question, though I conjecture that your criterion isn't sufficient. All one needs to do in order to prove my conjecture is to give a sorting network satisfying your condition but not mine. You can try looking for such a network using a computer. If you can find no such network, perhaps your criterion does work after all.


is it possible to create an avl tree given any set of numbers? I am studying balanced trees, especially AVL trees. My question is whether is it possible to create an avl tree given any set of numbers. is it possible to prove the following statement?

Let $A$ be the set of integers. Given any set $A$, it's possible to create an avl tree corresponding to the given set of numbers.

Is there any way to prove or work out the above statement? I appreciate your answers.

AVL trees are a kind of binary search trees. As such, they implement the following operations, among else:

Initialize an empty tree.
Add a value to the tree.
Remove a value from the tree.
Search a value in the tree.

Try to use some of these operations to answer your question.


Maximal difference of height between two leaves in an AVL tree What is the maximal difference between heights of leaves in an AVL tree? I am interested only in the asymptotic difference.

I am not sure about my answer - I think that it is $O(\log n)$,  given the fact that at every level we may have difference equal one.

Am I right?

We consider Fibonacci tree ([TAOCP3, Knuth98, Sect. 6.2.1]) and compute the maximal height difference in it.

A Fibonacci tree of order $k$ which is constructed recursively (see an Fibonacci tree of order 6 in the figure below; also from TAOCP):

  If $k = 0$ or $k = 1$, the tree is simply a single node.
  If $k \ge 2$, the tree has a left subtree of order $k-1$ and a right subtree of order $k-2$.

It is easy to verify that a Fibonacci tree is also an AVL tree.

From the figure above, we observe that the two leaves at the leftmost $l$ and at the rightmost $r$ differ most by heights ($H_l, H_r$ among all pairs of leaves. We can compute the height difference as follows.

A Fibonacci tree of order $k$ has $n = F(k+2)-1 \sim \Phi^{k+2}$ nodes in total, where $\Phi$ is the golden ratio.

$$H_l - H_r = k \text{ (leftmost path; decrease by 1}) - k/2 \text{ (rightmost path; decrease by 2}) = k/2 \text{ (maybe floor or ceiling functions here; I omit the details)}.$$

Because $n = \Phi^{k+2}$, we have $k/2 = \log_{\Phi} \sqrt{n} - 1$.


Do two strongly connected nodes constitute a cycle in directed graph? I'm seeing seemingly contradictory information about this around. On the one hand, it seems that for undirected graphs, you need at least 3 nodes to make a cycle.
On the other other, I've also seen people differentiate between trivial and non-trivial cycles.

Let's say in your directed graph you have two nodes A and B with an edge  from A to B and an edge from B to A. Do you have a cycle (A, B)? And does it always count as a cycle, or would some people consider it a cycle and others not?

Also, let's say you traverse that directed graph and hit A before you hit B. Is the edge (B, A) a back edge?

Like most things, you should only care about definition if it makes sense and useful in your context.

And in the context of strongly connected component, a nice property we would like to say is that:

  Node $a$ and $b$ belongs to the same cycle if and only if $a$ and $b$ are strongly connected.

This nice statement only holds if you count $f\rightarrow g\rightarrow f$ as a cycle.
So, we would like to count this as a cycle when talking about strongly connected components.


Matrix element value counting in O(1) space The question arise from my customer's real-time system (RAM model, off-course), which has very limited resources.

Given an NxM matrix of integer values, we need to verify that the number of non-zero elements in every row and every column is maximum 2.
The matrix cannot be stored! It comes as a stream (M and N are known in advance but are not constants), row after row, and each element is accessed only once.
The space requirement is O(1), i.e. no additional array of size N or M can be used, only a constant number of variables.

Can this be done?
If not, can it be proved?
Can this be done in O(log(N) + Log(M)) space?

We were taught in undergrad school that if you are unable to provide an adequate solution, prove that no one else can... So I tried to prove to my customer that this can't be done in o(M) space, but was unable to.

Thanks allot

Checking whether the number of nonzero elements on each row is at most $2$ can be done in $O(1)$ space on a row-by-row basis by simply counting those elements.

Therefore the only interesting part is checking the condition over the columns.
This can be done in $O(M)$ space by keeping a counter for each column. In details, the counter $c_i \in \{0,1,2\}$ associated with the $i$-th column will be the number of rows seen so far that contain a nonzero element in column $i$. As soon as a row with a nonzero element in column $i$ is seen and $c_i$ was already $2$, you can immediately return "false". If the whole matrix is processed without this happening you can return "true".

Unfortunately, your problem cannot be solved using $x= o(M)$ bits.
Suppose this were the case and consider some matrices with $M$ of columns and $N=2M+1$ rows, of the form described in the following.

The $i$-th of the first $M$ rows will have zeros in all columns $j \neq i$, while $i$-th column will either contain a $0$ or a $1$.

The number of distinct choices for the first $M$ rows is $2^M$, yet there are at most $2^x < 2^M$ (for sufficiently large $M$) different possible states of the $x$ bits of memory. This means that there are (at least) two distinct choices $R$ and $R'$ of the first $M$ rows that leave the algorithm in the same internal state.

In other words, for any choice of the $(M+1)$-th to $(2M+1)$-th rows, the algorithm must behave in the same way, regardless of whether the set of the first $M$ rows was $R$ or $R'$.

Since $R$ and $R'$ are distinct, there must be (at least) one index $i$ such that
the element $r_i$ in the $i$-th column of the $i$-th row of $R$ is different from the element $r'_i$ in the $i$-th column of the $i$-th row of $R'$. Without loss of generality assume that $r_i = 0$ and $r'_i=1$.

For $i=1,\dots,M$, let the $(M+i)$-th row be the row containing a single $1$ in the $i$-th column. Finally, choose the $(2M+1)$-th row to have exactly one $1$ in the $i$-th column.

This leads to a contradiction: On one hand, if the set of the first $M$ rows is $R$, the algorithm must return "true" since there is at most one nonzero element per row and at most two nonzero elements per column; on the other hand, if the set of the first $M$ rows is $R'$, the algorithm must return "false" since column $i$ has $3$ nonzero elements (in the $i$-th, $(M+i)$-th, and $(2M+1)$-th rows).


Improve minimum spanning tree with new edge, with better running time than O(|V|)? The problem gives a MST $T$ and a series of $Q$ queries, each one with a new edge $e = \{u,v\}$ such that no edge between $u$ and $v$ exists in $T$. For every query, we have to improve $T$ with $e$ and print the new weight of $T$.

The best I can do is run a DFS ($O(|V|)$) to find the current path $P$ between $u$ and $v$, and find the heaviest edge $e_\text{max}$ in $P$. If $w(e) > w(e_\text{max})$, we improve $T$ removing $e_\text{max}$ and inserting $e$. The overall running time for a test case is $O(Q|V|)$.

Does anybody know an asymptotically faster algorithm for this problem?

Using Heavy path decomposition.

The key idea is to partition all edges into heavy edges and light edges.
Consider tree edge from parent node X to child node Y:

heavy edge: size of sub tree Y is at least half of the size of sub tree X;
light edge: size of sub tree Y is smaller than half of the size of sub tree X;

There are at most $O(\log |V|)$ heavy paths (path with only heavy edges) from any leaf to root. Maintaining each heavy path using segment tree or balanced BST, and converting MST into tree of heavy paths, one can query the heaviest edge $e_{max}$ between any two vertices $u$,$v$ in $O(\log |V|)$.

Another method is using Link cut tree which handles each query in $O(\log |V|)$ amortized time complexity. This can also handle the case that each query is applied to the result of previous implement.


Why is binary search faster than ternary search? Searching an array of $N$ elements using binary search takes, in the worst case $\log_2 N$ iterations because, at each step we trim half of our search space.
If, instead, we used 'ternary search', we'd cut away two-thirds of our search space at each iteration, so the worst case should take $\log_3 N < \log_2 N$ iterations...

It seems that ternary search is faster, so why do we use binary search?

If you apply binary search, you have $$\log_2(n)+O(1)$$ many comparisons. If you apply ternary search, you have $$ 2 \cdot \log_3(n) + O(1)$$ many comparisons, as in each step, you need to perform 2 comparisons to cut the search space into three parts. Now if you do the math, you can observe that:
 $$ 2 \cdot \log_3(n) + O(1) = 2 \cdot \frac{\log(2)}{\log(3)} \log_2(n)+ O(1) $$ Since we know that $2 \cdot \frac{\log(2)}{\log(3)} > 1$, we actually get more comparisons with ternary search.

By the way: $n$-ary search may make a lot of sense in case if comparisons are quite costly and can be parallelized, as then, parallel computers can be applied.

Note that argument can be generalized to $n$-ary search quite easily. You just need to show that the function $f(k) = (k-1) \cdot \frac{\log(2)}{\log(k)}$ is strictly monotone increasing for integer values of $k$.


Finding a target vector through applications of a binary operator Let $\mathbb{X} = \mathbb{N} \cap [0, 255]$. I am given three vectors in $\mathbb{X}^3$ which I will denote by $v_i = [x_i, y_i, z_i]^T$ for $i \in \{1, 2, 3\}$. Now we have a binary operator $\bigoplus$ defined by $w = u \bigoplus v = \lfloor0.9 \cdot u\rfloor + \lfloor0.1 \cdot v\rfloor$, where $u$ and $v$ are in $\mathbb{X}^3$. Given a target vector $t \in \mathbb{X}^3$, the goal is to find a sequence of applications of $\bigoplus$ starting only with vectors $v_1, v_2, v_3$ that yield $t$. We are also given a promise that such a sequence of applications exists. How quickly can I find this sequence? It is worth noting that $\bigoplus$ is non-commutative and closed on $\mathbb{X}^3$. In my case, I am given specific values for $v_1, v_2, v_3,$ and $t$:
$$\begin{align*}v_1 &=[150, 0, 255] \\ v_2 &= [255, 150, 0] \\ v_3 &= [0, 255, 150] \\ t &= [62, 63, 184]\end{align*}$$

The obvious thing to try was a memoization / search approach where we keep a data-structure containing each vector seen so far (initially containing only $v_1, v_2, v_3$) and recursively apply the operator on each pair of vectors stored in my data-structure until the target is found. However this appears to be much to time consuming as the number of possibilities grow super quickly. Is there any better approach that one might try? It doesn't help that there appears to be little structure - For example, starting with our three vectors, there appears to be many combinations that we cannot even form.

I am also interested in knowing what happens if we are not given the promise that $t$ can be obtained from a series of applications of $\bigoplus$ on our three vectors. If we are not given such a promise, is there any easy way to at least determine if such a sequence exists (even though finding it might be difficult)?

Here is a simple solution that I suspect will be fast enough.  Use breadth-first search on a graph where the vertex set is $X^3$.  In other words, each possible vector $w \in X^3$ is a vertex.  The vertex $w$ has 6 edges out of it going to $w \oplus v_1$, $w \oplus v_2$, $w \oplus v_3$, $v_1 \oplus w$, $v_2 \oplus w$, $v_3 \oplus w$.  Now use BFS to find the shortest path from $v_1$ or $v_2$ or $v_3$ to $t$.  This can be done by initially marking $v_1,v_2,v_3$ as visited and having distance 0, initializing the queue to contain $v_1,v_2,v_3$, and then running BFS until you reach the goal vertex $t$.

Why does this work?  Define $d(v,w)$ to be the distance from $v$ to $w$, i.e., the length of the shortest path from $v$ to $w$ in this graph.  Define $d(w) = \min(d(v_1,w),d(v_2,w),d(v_3,w))$.  Note that any path of length $d$ corresponds to an expression that uses $d$ applications of the $\oplus$ operator, and vice versa.  Therefore, $d(t)$ -- the distance to the goal vertex $t$ -- represents the minimum number of applications needed to reach $t$, and the corresponding path yields an expression that evaluates to $t$ using the minimal number of applications of $\oplus$.

How efficient is this?  BFS run in time linear in the number of vertices plus the number of edges.  Here we have $2^{24}$ vertices and $6 \times 2^{24}$ vertices.  Therefore, in the worst case we perform something like $c \times 6 \times 2^{24}$ basic operations, where $c$ is a small constant.  The performance in practice might be better than that, as there might not be any need to visit all possible vertices.  The memory requirements are relatively limited.  You can store the set of visited vertices in a 2MB bitmap; thus, checking whether a vertex has been visited before can be done by a single random-access lookup in this bitmap.  You can store the queue in a single array of maximum size $3 \times 2^{24}$ bytes, i.e., 48MB; this is not very large large, and locality of access will be excellent.  So I expect this algorithm to complete within seconds.

If this is not fast enough, it is probably possible to optimize it further using various techniques.  For example, here is one candidate.  Define $x-v = \{w \in X^3 : v \oplus w = x\}$ and $P(x) = \{v \in X^3 : \exists w \in X^3 . v \oplus w = x\}$.  Define $S_j = \{w \in X^3 : d(w)=j\}$ and $T_k = \{w \in X^3 : d(w,t)=k\}$.  Now you could consider an optimized iterative deepening algorithm, as follows:

For $d=1,2,3,\dots$:

For $k=\lfloor d/2 \rfloor, \lfloor d/2 \rfloor + 1, \lfloor d/2 \rfloor -1,\lfloor d/2 \rfloor +2,\dots,d,1$:

Set $j=d-k$.  For each $v \in S_j$:

If $v \in P(t)$ and $t-v \cap T_k \ne \emptyset$, then choose any $w \in t-v \cap T_k$ and output $v \oplus w$ and halt.

We can compute the $S_j,T_k$'s using the technique above (BFS).  The trick here is to use a clever data structure to store $T_k$.  If we store $T_k$ in an octree or k-d tree, then testing whether $t-v$ has any intersection with $T_k$ is a stabbing query: we are given a $10 \times 10 \times 10$ cube and want to know if there's any point of $T_k$ that falls within the cube.  This lookup can be done efficiently when $T_k$ is stored in an octree or k-d tree or similar data structure (basically in $O(\log |T_k|)$ time or so).

This requires more complex data structures, so I'm not sure that it will be worth it to implement.  It's not clear whether the resulting solution will be faster or slower than simple BFS, but if simple BFS is too slow, this is another approach you could try.

This finds the sequence that evaluates to $t$ and uses the minimal possible number of applications of $\oplus$.  If you just want any sequence (not necessarily minimal), it might be possible to find it faster.  For example, you could use best-first search, where the "goodness" of a vertex is measured by its $L_{\infty}$ distance to $t$.

An aside: your operator $\oplus$ is not associative, but it is "almost so".  In particular, $(u \oplus v) \oplus w$ is in general not equal to $u \oplus (v \oplus w)$ (due to the rounding), but it will be "close".  Ignoring rounding,
$$\begin{align*}(u \oplus v) \oplus w &= 0.81 u + 0.09v + 0.10w\\
u \oplus (v \oplus w) &=0.90 u + 0.09 v + 0.01 w,\end{align*}$$
so (again ignoring rounding) their difference is $0.09 u - 0.09 w$, which is in $[-23,23]^3$.  Rounding might make it a bit larger, but not too much.

It might be possible to use this property to gain some additional speedup -- though I have not identified a specific way yet.


Integer programming to MAX-SAT translation Reading A Comparison of Methods for Solving MAX-SAT
Problems, I can see that a MAX-SAT problem can be translated to an integer programming (IP) problem.

Definition of MAX-SAT [Wikipedia]:

  The maximum satisfiability problem
  (MAX-SAT) is the problem of determining the maximum number of clauses,
  of a given Boolean formula in conjunctive normal form, that can be
  made true by an assignment of truth values to the variables of the
  formula.

Definition of integer programming [Wikipedia]:

  An integer programming problem is a mathematical optimization or
  feasibility program in which some or all of the variables are
  restricted to be integers

Is there a similar translation backwards? Given an IP problem that can be translated to a MAX-SAT.

The MAX-SAT problem is NP-hard [2] and Integer programming is NP-complete [3].
technically it might not be very suitable to solve a (in principle) simpler problem using a formulation which is (in principle) harder to solve. But it will be great to understand the encoding both ways. My motivation is to compare MAX-SAT solvers with IP solvers.

More precisely given an IP problem like:
$$x_1 + x_{2} + \neg x_3 \leq 1 \\
  \neg x_1 + x_4 + x_3 \leq 1 \\
   ... $$

with total n inequalities/equations and each $x_i \in \mathbb{B}$. Such that maximize as many as equations (from total n). Encode it as a MAX-SAT problem.

First Attempt:
Each inequality encodes AtMostOne of the complement of the variables (or AtleastN-1 of the original IP inequality). But representing AtMostOne in CNF will create multiple clauses and destroys the possible use of direct MAX-SAT.

The decision versions of both MaxSAT and integer programming are in fact NP-complete, so there is polynomial reduction from integer programming to MaxSAT.

In the context of solvers, modern MaxSAT solvers support "weighted partial MaxSAT"-encodings (weighted clauses with possibly infinite weights), so you can add any SAT encoded hard constraints by encoding them as clauses with infinite weight.

For comparing MaxSAT and IP solvers, I would strongly suggest looking at modern literature on "implicit hitting set" algorithms for MaxSAT. The solvers using this algorithm use both IP solvers and SAT solvers as subroutines for solving MaxSAT. It might even be that if you use some direct translation from IP to MaxSAT and give the resulting instance for these solvers, the solver will under the hood just directly solve the original IP instance with the IP solver. Also, there is a lot of recent research comparing IP and MaxSAT solvers for solving specific problems (just search "integer programming maxsat" in Google Scholar).


Is it possible to design a C++ like language without a Preprocessor? According to the dragon book, one of the first steps the source code of a program goes through during compilation is the Preprocessor.

Assuming a language like C++ where there is no underlying virtual machine to abstract away the underlying platform, is there a way to deal with cross platform compilation without requiring the use of the Preprocessor?

Another use case would be code to remove code that should only be executed in "Debug Builds".

P.S: I'm not mentioning other uses of the preprocessor like defining a value for PI as these can easily be replaced with the use const global variables.

Yes, it's entirely possible.

For example, you can define the language as requiring at least a minimal degree of dead-code elimination, so (for example) something like:

const bool debug = false;

if (debug)
    whatever();

...requires that not only is whatever() not called, but that it produce code that does not refer to whatever at all.

This gives roughly the same effect as something like:

#if debug
    whatever();
#endif

...would in C or C++. The only obvious difference is that by including the capability in the language, you typically require that the contents of the condition be syntactically correct for the target programming language (whereas C and C++ allow an #ifdef block to contain code that isn't syntactically correct C or C++, as long as the preprocessor can still detect the matching #endif).

Now, in some cases it's easy to require things that nobody knows how to do, thus producing a specification that nobody can implement. That would not be the case here though: compilers that can do the optimization above already exist.

Ada, for one example, includes a great deal of ability to tailor code to a specific platform without using a preprocessor like C and C++ do. In fact, it (Ada) arguably supports quite a bit more than C and C++ do in this regard.


identify abrupt frame changes in a video The frames of live streams or videos, in general, do not flow smoothly. A sports game would have multiple cameras recording the game and hence, there will be camera switches in the stream. I am detecting objects and tracking them as long as possible. When there are full changes in the video stream, I wish to reset object tracking and do a full detection.

I am looking for methods to efficiently identify when a camera switch (or anything of that kind) happens.

What algorithms are available to efficiently identify abrupt changes in a video?

Easiest is to capture video with an h.264 encoder, which uses key frames to identify switches. (It’s a bit more complicated, h264 will handle situations where frames come alternatively fro two different source, for example), but extracting that information from a video stream is easier than doing it yourself).

Source code for decoders is available, and a decoder will also give you useful information about movement, and things that become covered or uncovered.


determining timeouts / retry attempts in distributed systems Is there a methodical procedure for determining the optimal timeout / retry strategy for dealing with a remote server that handles processes responses for requests, given some probability distribution of response time?

For example, suppose I have a client program which requests a web page from some server, and I know roughly the probability distribution of its response time, e.g. 95% of the time I'll get a response with a gamma distribution, and 5% of the time my request will get lost and a response never sent. So maybe 80% of the time I'll get a response within 100 milliseconds, and 90% of the time I'll get a response within 500 milliseconds.

On one hand, I could set a timeout of 500 milliseconds and retry with another request after then. Or I could set a timeout of 100 milliseconds. A longer timeout means I have more chance of success, but I have to wait longer. A shorter timeout means I can reduce my wait time potentially, at the cost of increasing the chance of failure (I give up too early; the server will respond). Or I could just send two identical requests up front and take whichever response arrives first -- this seems like it might be the optimal strategy, but something seems wrong here. (why then wouldn't I send 100 identical requests? I guess I'm not modeling the fact that lots of additional requests would clog the server queue.)

Please help; I know this is a fairly general question, but I have no idea where to look for more information of this type. I never took any classes on distributed systems in college + am trying to improve responsiveness of a client program.

The simplest solution I have found to this problem is using rolling percentile latency. The optimal timeout will shift based on hardware, network configuration and the state of the operating system. Therefore it cannot be fixed/established beforehand, but approximated at runtime. The typical practice in industry is to maintain P95 and P99 response times. These are durations in which 95% and 99% of requests complete respectively over some time duration. So you could perhaps store the last hour of request times, and if the current request is longer than 95% of the others in the last rolling 60 minutes, then you deem that a timeout.
This will adapt and gradually become more strict if response times are fast, and more lenient if they become slow.
You can read more about percentile latency here.


importance of alternate storage in external sort I'm trying to understand how external sorting works from the book "Data Structures and Algorithm Analysis" by Mark Allen Weiss.

The author illustrates an example where he tries to sort 81,94,11,96,12,35,17,99,28,58,41 with a memory which can hold upto M=3 numbers. He uses two input tapes Ta1,Ta2 and two output tapes Tb1,Tb2.

Ta1    81,94,11,96,12,35,17,99,28,58,41
Ta2
Tb1
Tb2

In the first step M numbers are read into memory then, sorted and written to Tb1 and Tb2 alternatively.

Ta1
Ta2
Tb1    11,81,94   17,28,99   15
Tb2    12,35,96   41,58,75

I understand how the algorithm works but, don't understand why it is important to write results alternatively. Couldn't this be achieved without alternating?

I believe the alternation is done to ensure that the data is split as closely as possible into equal-sized subsets, which minimizes the time spent on each later pass.


Queue FIFO search speed up through the change of visited array? As I was preparing for the CCC this year, I am quite confused as to why a certain code modification was able to speed up my code for CCC Seniors Problem 2.
Here was the C++ source code for my first attempt, which scored 13/15 in the cccgrader website as well as the DMOJ online judging website.
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vint;
typedef pair<int,int> pii;
vector<pii> vpairs[1000001];
vector<vector<bool>> vis;
int main(void){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int A,B;
    cin>>A>>B;
    for(int i=0;i<A;i++)
    {
        vector<bool> newvecbool;
        for(int j=0;j<B;j++)
        {
            newvecbool.push_back(false);
            int k;
            cin>>k;
            vpairs[k].push_back(pii(i,j));
        }
        vis.push_back(newvecbool);
    }
    queue<pii> queue;
    queue.push(pii(A,B));
    while(!queue.empty())
    {
        pii curpair = queue.front();
        queue.pop();
        if(curpair.first==1 && curpair.second==1){
            cout<<"yes";
            return 0;
        }
        vis[curpair.first-1][curpair.second-1] = true;
        int value = curpair.first*curpair.second;
       // cout<<curpair.first<<' '<<curpair.second<<endl;
        for(int i=0; i<vpairs[value].size();i++)
        {
            pii pair = vpairs[value][i];
            if(!vis[pair.first][pair.second]){
                //vis[pair.first][pair.second] = true;
                queue.push(pii(pair.first+1,pair.second+1));
            }
        }
    }
    cout<<"no";
}

Here, on the other hand, was my second attempt, being much faster in time and scoring 15/15 on both the cccgrader and the DMOJ judging website.
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vint;
typedef pair<int,int> pii;
vector<pii> vpairs[1000001];
vector<vector<bool>> vis;
int main(void){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int A,B;
    cin>>A>>B;
    for(int i=0;i<A;i++)
    {
        vector<bool> newvecbool;
        for(int j=0;j<B;j++)
        {
            newvecbool.push_back(false);
            int k;
            cin>>k;
            vpairs[k].push_back(pii(i,j));
        }
        vis.push_back(newvecbool);
    }
    queue<pii> queue;
    queue.push(pii(A,B));
    while(!queue.empty())
    {
        pii curpair = queue.front();
        queue.pop();
        if(curpair.first==1 && curpair.second==1){
            cout<<"yes";
            return 0;
        }
        //vis[curpair.first-1][curpair.second-1] = true;
        int value = curpair.first*curpair.second;
       // cout<<curpair.first<<' '<<curpair.second<<endl;
        for(int i=0; i<vpairs[value].size();i++)
        {
            pii pair = vpairs[value][i];
            if(!vis[pair.first][pair.second]){
                vis[pair.first][pair.second] = true;
                queue.push(pii(pair.first+1,pair.second+1));
            }
        }
    }
    cout<<"no";
}

As you may have noticed, the only difference between the two source codes is the position in which the vis vector, a vector used to store the pairs of integers of visited coordinates,  is set to true. after visit of a coordinate point. One is right after the if statement, whilst one is in the while loop. I'm not quite sure what led to the speed increase.
Any help will be greatly appreciated.

Suppose 3 rooms each of which contains number 6 have been visited before any room the product of whose coordinates is 6 has been visited.
In the first version of your code, every room of the second kind will be put into the queue 3 times.
In the second version of your code, every room of the second kind will be put into the queue only 1 time (except possibly the room at (A,B), which will be put into the queue 2 times).
The difference between 3 times and 1 time is what slows down the first version. In general, there might be $m$ rooms of the first kind for the corresponding second kind. The appropriate average of $m$ in the test cases is substantially greater than 1. Hence you see the significant speedup from the first version to second version.

A good rule of thumb across all these kinds of searching problems is to try setting visited as soon as possible to avoid unnecessary and sometimes even incorrect computations.


How to show that pda accepts empty language? I have to show that a PDA accepts empty language, but for this I have to use some algorithm, with what kind of algorithms could I demonstrate it? I've heard about the algorithm from Moore, Brzozowski or Thompson, but they are for DFA, so I don't know if it would work.

I am not aware of any straightforward algorithms. One roundabout way I can think of is:

Convert the PDA to a CFG (there is a standard construction for this covered in introductory automata classes, the resulting CFG has $O(|Q|^2)$ variables where $Q$ is the size of the PDA)
Check if the CFG's language is empty.

We can check if the language of a CFG $G$ is empty using an iterative algorithm that marks a variable if it can derive a string:

Mark all terminals in $G$ (or delete them from the rules)
While no new variables are marked:

For each rule $A \to \alpha_1 \ldots \alpha_k$, if $\alpha_1, \ldots, \alpha_k$ are all marked then mark $A$.

If the start variable is marked then $L(G)$ is nonempty, otherwise $L(G)$ is empty.

The algorithm above can be optimized with a worklist that skips re-visiting a same variable's rules after it's marked, and doing some processing to allow checking rules affected by the previous pass


How to implement random sampling with continuous variables? How functions like rnorm in R (and similar functions) create a random sample ? If I want to implement one algorithm to simulate this procedure what can I do? When you have the pdf or pmf of a distribution how can you use this to create a random sample with a computer? Is there some book on this topic?Is this a numerical analysis topic? I searched alot but I couldn't find any information about this.

One standard approach is to use inverse transform sampling: if $F$ is the cdf of the desired random variable and $U$ is uniformly distributed, then $F^{-1}(U)$ has the desired distribution.  There are more sophisticated methods for specific distributions; you can find references and links where you can learn more in the linked Wikipedia article.


Does checking the middle bit of an input require a log(n) space pointer? Let n be an even integer.

Let i be an input of length n.

Positions start at 0: the first bit is bit 0. The second bit is bit 1. etc.

The decision problem is, "Is bit n/2 equal to 1"?

The input is on a tape.

We have a single pointer to the input. We cannot overwrite the input tape.

We have finite amount of working-memory tapes to compute with (in case more than 1 is useful).

Space-complexity is the maximum amount of non-empty tape cells to ever appear across all work tapes at any point during the execution.

(That way, in practice, this can correspond to virtualizing a Turing machine and adding or removing physical hard drives to back each logical working-memory tape.)

Each pointer can be moved left or right one cell.

One way to decide the problem is with a counter of length O(log(n)): Initialize to 0's, then increment until the counter equals n/2, then check the bit.

That takes O(log(n)) space.

Can we do better? Or is O(log(n)) the best space-complexity we can do?

If we can do better, in general, then there's a system of representing integers more space-efficient than polynomial bases (decimal, binary, etc.).

For example, if we had access to the corresponding busy-beaver machine for n/2, then we could use that (and instead of printing out a 0, we could move our input tape by 1). However, in general, we cannot compute the (optimal) busy-beaver for n/2.

So, is there a way to compute a "sub-optimal busy-beaver" and use that to get to n/2 instead of a O(log(n)) counter?

You can do this with constant amount of memory (according to your definition of space complexity). Assume $n \ge 2$ (the complementary case is trivial).
Mark the work tape on the starting position of the input, then move right until you reach the end of the input and mark the last position of the input on the work tape.

Repeat the following:

Go back to towards the beginning of the input until you find a marked position on the work tape.
If the position immediately to the right is already marked, report the current position as the middle of the input.
Otherwise, remove the mark from the current position (i.e., write the empty symbol), move right, and mark the current position.
Advance towards the end of the input until you find a marked position on the work tape.
If the position immediately to the left is already marked, report that position as the middle of the input.
Otherwise, remove the mark from the current position, move left, and mark the current position.


Generalizing Knuth's $O(\log_2 n)$ Fibonacci algorithm to linear homogenous recurrences Knuth has a neat algorithm that uses matrix exponentiation to compute the $n$th Fibonacci number in $O(\log_2 n)$-time 1. However, there doesn't seem to be a lot of resources on generalizing his idea to other linear recurrences. Is it a generalizable idea, or is it just a special technique only applicable to the Fibonacci recurrence?

(I'm not asking for a closed-form solution, but an efficient method similar to Knuth's technique for Fibonacci numbers).

As a related question, can we speed up other recurrences by rewriting them as linear transformations, and how far can we go in applying this technique?

Yes.  This generalizes to any linear recurrence.  Suppose we have the linear recurrence

$$x_{n+1} = a_0 x_n + a_1 x_{n-1} + \dots + a_k x_{n-k}.$$

Define the column vector $v_n = (x_n,x_{n-1},\dots,x_{n-k})^\top$.  Then we have the equation

$$v_{n+1} = M v_n$$

where the matrix $M$ is given by

$$M = \begin{pmatrix}
a_0 &a_1 &a_2 &\dots &a_k\\
1 &0 &0 &\dots &0\\
0 &1 &0 &\dots &0\\
&&&\vdots\\
\end{pmatrix}.$$

It follows that

$$v_n = M^n v_0.$$

Therefore you can compute $v_n$ using $O(\log n)$ matrix multiplications, using a fast exponentiation algorithm for computing $M^n$.  This gives an efficient way to compute $x_n$: first compute $v_n$ using matrix exponentiation, then extract the first coefficient of $v_n$ to get $x_n$.

In fact, we can take this farther.  Suppose $M$ diagonalizes, say $M=PDP^{-1}$ where $D$ is a diagonal matrix.   Then

$$v_n = M^n v_0 = (PDP^{-1})^n v_0 = P D^n P^{-1} v_0,$$

so we don't need to perform matrix exponentiation; it suffices to exponentiate each of the diagonal entries of $D$.  In fact, expanding terms, you can get an algebraic closed-form expression for $x_n$.  If you apply this to the Fibonacci sequence, you get the closed-form expression in https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression (in terms of powers of $(1\pm \sqrt{5})/2$, because those are the elements of $D$); for a general sequence, you get a closed-form expression of the form

$$x_n = c_1 \lambda_1^n + \dots + c_k \lambda_k^n,$$

where $\lambda_1,\dots,\lambda_k$ are the diagonal entries of $D$ (i.e., the eigenvalues of $M$).  This also gives a potentially more efficient algorithm for computing $x_n$: instead of $O(\log n)$ multiplications of $k\times k$ matrices, we get $O(k \log n)$ operations on numbers.

If $M$ does not diagonalize, you may still be able to use the Jordan normal form of $M$.

See also https://en.wikipedia.org/wiki/Recurrence_relation#Solving_homogeneous_linear_recurrence_relations_with_constant_coefficients, which does something similar using the characteristic polynomial of the linear recurrence (which I think coincides with the characteristic polynomial of $M$, or something like that).


Complexity of black box satisfiablty Say I have a black box $f : 2^n \to 2$ and I want to determine if it is satisfiable. That is, does there exist an input how which it returns true. I am for the purposes of this considering $n$ to be the size of the problem. Perhaps that is a bad assumption to make but it seems a reasonable assumption.

Clearly I can reduce SAT to this problem but can I efficiently reduce this problem to SAT? I couldn't think of an efficient way and it doesn't seem possible due to the black box nature. It clearly lies in EXPTIME because I could just try each input. Further still it lies in PSPACE because the I only need to enumerate the linear space assignments. It does not however appear to be in NP as far as I can tell. I can't seem to figure out if it lies in PH either.

Has the complexity of this problem been studied? If so what complexity class does it lie in?

If it's a black box, you can't reduce it to SAT.  That's exactly what it means to be a black box: a black box is one where you can feed in any input $x$ you like, and get back $f(x)$, but where you know nothing about the structure of $f$ (for instance, you are not given an algorithm for $f$, you do not know the CNF for $f$, and so forth).

In particular, given only black-box access to $f$, in the worst case, you need $2^n$ queries to the black box to determine whether $f$ is satisfiable: you need to evaluate $f$ on every possible input, in the worst case.  Consider any algorithm which makes at most $2^n-1$ queries to the black box.  Suppose it got back $0$ as the answer to every query.  Then there is some input, say $x'$, which has not been queried.  Now the correct answer as to whether $f$ is satisfiable depends upon whether $f(x')=0$ or $f(x')=1$, but the algorithm has no clue which is the case.  No matter what the algorithm outputs, an adversary could always pick a $f$ (after the fact) that is consistent with all of the queries made to the black box but that makes the algorithm's output wrong.  Therefore, no deterministic algorithm can do better than $2^n$ queries, in the worst case.

It's not in EXPTIME, and it's not in NP, because it is an oracle problem, whereas NP and EXPTIME are for non-oracle problems -- but it is in the analogue of EXPTIME for oracle problems.... and in the analogue of NP for oracle problems, too.


How does Rogozhin's (2, 18) universal turing machine work? I am trying to understand Rogozhin's (2, 18) universal turing machine by stepping
through a simple 2-tag encoding that I believe should loop forever:

a -> aa

For example, using an initial input of aaa:

aaa
  aaa
    aaa
      .... etc

Apologies for the extremely specific question, but it's what I've narrowed my
issue down to and I've been stuck for a while!

Following the instructions in part 10 / pp22 and page 6 I believe this system
should be encoded as:

c⃖₁ c⃖₁ b  b  1  b  1  b >b  1  c  1  c  1  c
|P2   |P1           |P0   |Ar   |As   |At

Running this, however, results in termination rather than an infinite loop.
Following the trace I have managed to identify something I can't explain and
that seems wrong, but have not been able to figure out a resolution.

Following the first stage of modelling:

  On the first stage, the UTM searches the code P, corresponding to the code A,
  and then the UTM deletes the codes A, and A, (i.e. it deletes the mark
  between them)

  ...

  if the head of the UTM moves to the right and meets the mark c, then the first
  stage of modelling is over. The UTM deletes this mark and the second stage of
  modelling begins

Gives the following trace:

c⃖₁ c⃖₁ b  b  1  b  1  b >b  1  c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1  b  b⃖ >1  c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1  b >b⃖  c₂ c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1 >b  b  c₂ c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1  b⃖ >b  c₂ c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1  b⃖  b⃖ >c₂ c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1  b⃖  b⃖  1⃖ >c  1  c  1  c
c⃖₁ c⃖₁ b  b  1  b  1  b⃖  b⃖ >1⃖  1⃗  1  c  1  c

At this stage, Rogozhin claims the tape should be:

P2P1P'0R'At

Notice in particular R'At

  R’ consists of 1⃖ and 1⃗ and the head of the UTM is located on the R’ in the
  state Q2

But to me, it appears that only Ar has been deleted!?

c⃖₁ c⃖₁ b  b  1  b  1  b⃖  b⃖ >1⃖  1⃗  1  c  1  c
|P2   |P1           |P'0  |R'   |As!! |At

I would expect something like:

c⃖₁ c⃖₁ b  b  1  b  1  b⃖  b⃖ >1⃖  1⃗  1⃖  1⃗  1  c
|P2   |P1           |P'0  |R'         |At

I have identified the following potential errors I have made, but have double
checked each and have not been able to identify any:

Understanding of 2-tag system.
Encoding of 2-tag system.
Execution of rules (programming bug).
Formatting of trace.
Interpretation of trace.

Can anyone spot what I'm missing? Am hoping it's something obvious!

Supplementary materials

Spreadsheet to generate tape
Ruby program I'm using to generate traces
Full trace showing that aaa terminates when I think it shouldn't
Original motivation and how I ended up here in the first place

I see (at least) two errors:

The head position should be at the beginning of $S$; and there is an extra 1 at each $P_i, i > 1$: $P_i = bb 1^{N_{i_{m_i}}}1b....b1^{N_{i_2}}1b1^{N_{i_1}}$

c⃖₁ c⃖₁ b  b  1  1  b  1  b b >1  c  1  c  1  c
                 ^            ^
                !!!          !!!

Don't forget that the rest of the tape should be fille with $1^{\leftarrow}$ (the balnk symbol).

A few years ago I also examined its behaviour; you can find the javascript version I made here: click "Small" to load it, then fill the tape (click on the second gray row to place the head), and click "Step". You can compare it with your implementation.


Why are binary numbers sometimes written with one or more leading zeros that don't change the number (quantity) represented? Binary numbers like '0110', or '00100101' are seen very often in all contexts. What are the leading (left hand side) zeroes for? Why did the writer not write '110' and '100101', respectively?

Leading zeroes in binary usually indicate the bit length of the data type.
For example, the number 110 represented in a 4 bit data type would be 0110.
Even if there is no data type specified, it's sometimes common to pad your binary numbers to the next power of 2. For example, 10111 of size 5 should be padded to 8 $(2^3)$ as 00010111


Is substitution done to all occurrences? In a CFG, we might have :$A \rightarrow AA$ and $A \rightarrow a$ where $a$ is a terminal and $A$ is a variable.

Then if we apply the first rule,  and then the second , do we get $aa$ or either $aA$ or $Aa$ ?

A single substitution is one application of one rule. So the rule $A\to AA$ means "Pick any single $A$ in the string and replace it with $AA$" and "$A\to a$" means "Pick any single $A$ and replace it with $a$."  Substitutions are done one at a time, and there's no way to write a rule that says "Replace every $X$ with $Y$, or replace them all with $Z$."

If you start with $A$ and apply the first rule, you certainly get $AA$, since there's no other choice. But there are two ways of applying $A\to a$ to $AA$: you could pick the first or second $A$ to replace with $a$.

Indeed, there are two ways to apply $A\to AA$ to the string $AA$. However, replacing either the first or second $A$ with $AA$ gives the string $AAA$.