texts: How to make sure matrix completion can generate a matrix with values in expected range?

texts:
I am doing a matrix completion project. Assume that I have an incomplete matrix like

        func1    func2    func3
prot1     0        0        1
prot2     1        0        1
prot3     0        0        0

I want to use Standard Matrix Completion to recover the matrix, like

        func1    func2    func3
prot1    0.1      0.9       1
prot2     1       0.2       1
prot3    0.3      0.8      0.7

Standard Matrix Completion refers to

$$\min_{W, H} \frac{1}{2} \Vert W \Vert_F^2 + \frac{1}{2} \Vert H \Vert_F^2 + \frac{\lambda}{2} \Vert \Omega \circ (W H^T - Y) \Vert_F^2$$

and $X = WH^T$.

However, I find that the recovered matrix X is not range between 0 and 1, say (just an example, not the truth)

        func1    func2    func3
prot1    -0.1     1.1       1
prot2     1       0.2       1
prot3    0.3      2.1      0.7

How can I restrict the range (here 0-1) of unobserved entries in X (in particular how can I implement it in Tensorflow)?


texts: Rigorous proof against pseudo random function

texts:
I have the following problem:

Deﬁne the keyed function F as follows: On input k ∈ {0, 1}$^n$
and x ∈ {0, 1}$^n$ , Fk(x) = k ⊕ x.Rigorously prove that F is not a pseudorandom function.

How do I approach a proof against pseudorandomness for a keyed function? I don't know where to start with this one.


texts:
"Independent Component Analysis" is this : someone is sampling a random vector $s \in \mathbb{R}^d$ such that all its components $s_i$ are mutually independent and $\mathbb{E}[s_i^4] < 3$ and the observer has access to only a transform of it as $y = Ws + b$ where $W$ is a full rank $d \times d$ matrix and $b \in \mathbb{R}^d$. Now the question is to be able to recover $W$ and $b$ from $i.i.d$ samples of $y$.

Is there a natural scenario where one looks at a non-linear version of this question? Like one has to recover the non-linear transformation applied to the sampled $s$?


texts: Maximum sum subset of an array with an extra condition

texts:
We are given numbers $n \leq 200$, $k \leq 10$ and an array of $3n$ positive integers not greater than $10^6$. Find the maximum possible sum of a subset of elements of this array, such that in every contiguous $n$ elements there are at most $k$ chosen.

As this is an old high-school level contest problem, I ask for some hints. Also, this means I know there exists a solution far quicker than the proposed by D.W. and most likely not very complicated, so the question is still open.

My ideas mostly involved dynamic programming. I was trying to calculate, for each prefix of the array, best score we can acquire. However, in order to do this, I think I would need to calculate it for every prefix, and every possible choosing of $k$ numbers in the last $n$ numbers of this prefix, resulting in complexity $O(n^{k+1})$, which is far from acceptable. Also, I thought of looking at pairs of positions in the array which are distant by $n$ and their relation to each other, but this approach fails, as in an optimal solution not in every contiguous $n$ element we would choose exactly $k$, sometimes it could be less.


texts: On satisfiability for 2-variable FOL being NEXPTIME-complete

texts:
Let $\mathbf{FO^2}$ be the fragment of first-order logic consisting of sentences with at most two variables and no function symbols. It is well known that satisfiability for $\mathbf{FO}^2$ is decidable (see [1], for instance). Furthermore, in that same paper, it is argued that $\mathbf{FO^2}$ satisfiability is $\mathbf{NEXPTIME}$-complete, and that this result follows from these two lemmas:

Satisfiability for $\mathbf{FO^2}$ is in $\mathbf{NTIME}(2^{O(n)})$.
Satisfiability for $\mathbf{FO^2}$ has a lower complexity bound of the form $\mathbf{NTIME}(2^{cn/\log{n}})$ for some positive constant $c$.

I don't have a lot of background in complexity theory, so this has left me with two questions:

Is it easy to see that these two lemmas imply $\mathbf{NEXPTIME}$-completeness?
Is this result not contradictory? By definition, $\mathbf{NEXPTIME} = \bigcup_{k \in \mathbb{N}}\mathbf{NTIME}(2^{n^k})$, and by the non-deterministic time hierarchy theorem we have for any $i, j \in \mathbb{N}$ that $\mathbf{NTIME}(2^{n^i}) \subsetneq \mathbf{NTIME}(2^{n^j})$ if $i < j$. So I'm wondering how a problem complete for the class can lie at the "lowest rung" of the ladder - is this because Karp-reductions can blow-up the size of an input polynomially?

REFERENCES

[1] On the Decision Problem for Two-Variable First-Order Logic - Grädel, Kolaitis and Vardi


texts: Minimizing cost of shortest paths to a group of vertices by adding minimal edges to an unconnected vertex

texts:
Let $G=(V,E)$ be directed graph, where the weights of the edges are non-negative. The graph might have cycles, but without parallel edges.

Consider a  $T \subset V$, and $u \notin V$.

I'm trying to develop algorithm for following optimization problem:

Adding  minimal new edges (that have fixed costs that is greater than any already existed edge), which decrease the cost of

$ \min (||E^{+}||+\sum_{ \forall w \in T}  d(u,w))$, where we define $d$ to be the cost of the shortest path between $u$ and $w$, and $||E^{+}||$ is the cost of adding $|E^{+}|$-new edges.

The simple algorithm (see explanation in [1]) would have the following complexity (just using a Bruteforce).

$ (\sum_{i= 1}^{|T|}  {n \choose |i|}) \cdot |T| \cdot SPT$
where, we denote SPT as the complexity of the best shortest path algorithm to to a single path $(u,w)$.

But, I'm sure there exist better heuristics approaches.

I appreciate any existing reference if this problem is already solved, or similar problems if it is open question.

[1]- Explanation:

Add 1 edge to any of the graph and compute the formula , then add 2 arbitrary edges and compute where is the minimum. Keep on going till adding |T| edges, i.e connect directly u to any node in T. Then, choose the construction that has minimal cost


texts: Fitting a polynomial to a set of points or to a skeleton

texts:
Available data

Available to me is a set of points which can be represented as shown in image 1:

Also available to me is a non-continuous path derived from this data. It is not important how this non-continuous path is obtained. It is however important, that it roughly represents a curve I intent to approximate. This non-continuous path is shown in image 2:

Goal

I want to approximate this data using a polynomial of either second or third degree. Examples of these approximations are shown in images 3, 4:

Problem / question

Now I am looking for a way to obtain the red curve. Some details confuse me, where my knowledge is likely to be simply lacking. For example, how to fit a polynomial, when technically what I require is not a function, at least not in this coordinate system, because there will be situations where an x value is being assigned two y values.

I thought of possibly using the ends of my path to define a new x-axis, but I consider this approach faulty. Another consideration are Splines.

How should I go about obtaining this red curve from the non-continuous path (preferred) or from original data? What sources should I look into?

Apologies if this is an already answered question which I suspect it might be. However I have been issuing search queries for this without success, hence my question.


texts: Why can't I find anything on the non-deterministic Nick's Class (NNC)?

texts: It seems that non-deterministic Nick's Class (NNC) would be the same as non-deterministic polynomial time, but I haven't been able to find anything on NNC.


texts: What is the difference of temporal dynamics in RNNs and the NEF

texts: Both spiking neural networks created with the Neural Engineering Framework (NEF) and Recurrent Neural Networks (RNNs) can be connected recurrently to exhibit neural dynamics. What is the difference between the set of dynamics that they can approximate and/or exhibit?


texts: How to show that for $\epsilon>0$, there exists a function $G:\{0,1\}^n->\{0,1\}^{2^{\epsilon n}}$ that is a $2^{\epsilon n}$-prg, without the condition that is is computable in $2^{O(n)}$ time. What I am trying to show is with high probability, if we take $\epsilon=1/10$, a random $G$ satisfies this condition. But in order to show that, we need to show, no circuits of size $<2^{3/10n}$ are able to distinguish between uniform distribution of length $2^{n/10}$ and output of $G$. This I am not able to get. Can anyone give me an approach?


texts: Are there search algorithms that perform better on a Rope than a String?

texts:
I want to implement fast text-search over a Rope data structure. That is, a B-Tree of characters, where the characters are not sorted. (Meaning the standard way to search in a B-Tree by key does not apply.) This data structure is good for making incoherent edits to, but retrieving the character at a given index takes $O(\log n)$ time. All the text search algorithms I've examined so far seem to assume that accessing characters in $O(1)$ and therefore tend to use a lot of accesses. In particular, the search algorithm I've implemented is performing poorly on large files, (hundreds of thousands of characters.) Profiling reveals most of the time to be spent in retrieving the characters to be compared.

The particular algorithm I currently have implemented is the Two-way string-matching algorithm. I chose it for my first attempt mainly because it needs only $O(1)$ additional memory, and not having an additional data structure to implement seemed like it would speed up implementation.

So, I'm wondering are there any well-described search algorithms exist which are designed for use on a B-Tree, or which otherwise perform well in such an environment? I assume the algorithms I have been looking at are trying to minimize comparisons, which I suppose would tend to minimize character retrieval as well. Does it seems sensible to suppose that one would design an algorithm differently if it was to be used on a data structure with a larger than $O(1)$ indexing time?


texts: Algorithm analysis in the presence of undefined functions

texts: I wonder how we can perform algorithm analysis when in an algorithm we have calls of functions whose definition we do not know, e.g. functions delivered by external libraries.


texts: "Equality" problem in distributed computation

texts:
I recently started learning about distributed computation on graphs (not to be confused with parallel computation with threads).
I have seen as a side note in a few lower bound proofs, a reference that says the proof could be shorter using the "linear lower bound theorem for the Equality problem", but I couldn't find the statement or proof of this theorem.
I would like to know a few things:

What exactly is this "Equality" problem? (how is it formulated?)
Where can I find a proof for its lower bound? (or if the proof is short enough, I would be glad if you could add it here)

Thanks!


texts:
I calculated the worst case scenario of a time complexity of an algorithm problem using recurrence tree. (The problem cannot be solved by master theorem.)

Now I want to find a lower bound on the expression I got. Specifically, I want to prove that

$$ 1^k + 2^k + \dots + n^k = \Omega(n^{k+1}). $$


texts:
I'm looking for an explanation or reference on the implementation of computer clock. To keep the question at the level of logical abstractions: say, we put together some combinational and sequential logic from basic gates. The role of the clock (an oscillator of some sort, but that's going into more detail than needed for my abstraction) is to synchronise the unorderly chorus of inputs and outputs passing through the gates. Exactly how does the clock synchronize the signals?

To render things more concrete... Take a two-way NAND gate. Say, I set the two inputs (U1) to high signal, and obtain (after some inherent delay) a stable low signal at the other end (U2). Now, to add basic sequential logic to this inverter, let's add a Data Flip-Flop (DFF). The effect is that we can be certain that the Q end of the DFF will broadcast the low signal "definitively" at the start of the next clock cycle. What happens within the cycle is not to be trusted. The clock period is set such that the other circuitry (NAND gate in my case) has the time to stabilize during the cycle. This is the contract. But how is it achieved?

The metaphor in my mind is that the clock acts as a sluice. But the comparison is misleading, in that the signal entering and exiting the DFF is not truncated at any point. We could physically measure the signal within the tick-tock cycle of the clock at the Q end of the DFF. Another high-flown metaphor would be the warm-up motions of an orchestra before the rehearsal gradually transforming into an attuned performance, with the conductor setting the beat.

How is the proper signal (attuned to the clock's oscillations) distinguished from the noise propagating through gate circuitry at all times? I realize, there may be missing parts in my picture, so that question should be framed in constructive terms:
How can one implement this basic circuit to allow the logic to distinguish between signal and noise?

Edit: Judging by responses to this question, my original question must be poorly phrased. I understand the reasons behind the choice of frequency for the system clock to ensure the circuit is stable on the tick of the clock. The responses from @Ran G. and @slebetman emphasize the "contractual" side of things. My question is really about why the contract holds. In retrospect, what I was getting at is the trivial fact that measuring instruments (system clock) must be selected based on the degree of precision required -- in a typical case discussed here, for our human sluggish attention span.

To illustrate, here's a graph of the clock pulse against data-in and Qa output for a DFF.

Say, in the 2nd clock cycle, Captain Marvel sends a pulse on the data-in line and -- oblivious to the clock period -- expects to read it off immediately (mid-phase). With his lightning speed, there's no way he can make sense of the output of this circuit because the clock cycle is geological time to him. Billy Watson, on the other hand, can read it just fine. Neither Captain M. nor Billy W. is synchronized with the system clock. Not in the sense that the gate circuitry is. But for Billy's experience of time, the clock's time scale is sufficiently precise.


texts: Algorithm for locking based on a shared resource (dictionary)

texts:
I am working with a shared resource with the following specifications

acts as a dictionary (values can be obtained with key name: dictionary['key'])
does not have builtin system for locking
Multiple threads can read and write to same keys (simple writes and reads are atomic)
I am trying to implement locking based on keys in that resource using one or more keys in the dictionary as locks with which the threads can obtain a lock for the shared resource. For example:

dictionary['lock'] == null would mean that the lock has not been obtained.
dictionary['lock'] = myThreadId would obtain the lock
dictionary['lock'] == myThreadId would mean the lock is reserved

As far as I know using only one key would not work (see below). I came up with the following 2-part lock solution and the question is: is there an official name for this kind of solution and could the algorithm be simplified? Or are there any (fatal) flaws in this solution? Some issues might occur when freeing the locks if another thread has previously been able to enter through the 1st lock.
Lock using one key
Thread reads lock (value in dictionary['lock'])
Thread writes lock
Thread 1 reads lock (to ensure successful write)

but that could fail with:
Thread 1 reads lock
Thread 2 reads lock
Thread 1 writes lock
Thread 1 reads lock (value "thread1")
Thread 2 writes lock
Thread 2 reads lock (value "thread2")

2-part lock
I figured having locking with two parts should fix the issue:
Step1: READ LOCKS1+2 (reading LOCK2 might not be necessary)
Step2: WRITE LOCK1
Step3: READ LOCK2
Step4: WRITE LOCK2
Step5: READ LOCKS1+2 (reading LOCK2 might not be necessary)
Step5: READ LOCKS1+2 (reading LOCK2 might not be necessary)

if two concurrent threads try to obtain the lock, the lock can be recognized as being in a "dirty" state
A Step1: READ1+2 => empty+empty
B Step1: READ1+2 => empty+empty
A Step2: WRITE1 => A
A Step3: READ2 => empty
B Step2: WRITE1 => B
B Step3: READ2 => empty
A Step4: WRITE2 => A
A Step5: READ1+2 => B+A !! DIRTY STATE - WAIT
B Step4: WRITE2 => B
A Step5(again): READ1+2 => B+B !! LOCK LOST
B Step5: READ1+2 => B+B

likewise:
A Step1: READ1+2 => empty+empty
B Step1: READ1+2 => empty+empty
A Step2: WRITE1 => A
A Step3: READ2 => empty
A Step4: WRITE2 => A
A Step5: READ1+2 => A+A
B Step2: WRITE1 => B
B Step3: READ2 => A !! LOCK RESERVED, RESTORE LOCK1 AND CANCEL

3rd case:
A Step1: READ1+2 => empty+empty
B Step1: READ1+2 => empty+empty
A Step2: WRITE1 => A
A Step3: READ2 => empty
A Step4: WRITE2 => A
B Step2: WRITE1 => B
A Step5: READ1+2 => B+A !! DIRTY STATE - WAIT
B Step3: READ2 => A !! LOCK RESERVED, RESTORY LOCK1 AND CANCEL
A Step5: READ1+2 => A+A !! LOCK1 RESTORED BY B, CONTINUE

The code would look something like this:
if( lock1.IsFree() && lock2.IsFree() )
{
    lock1.LockForCurrentThread();
    if( lock2.IsFree() )
    {
        lock2.LockForCurrentThread();
        if( lock1.IsLockedByCurrentThread() && lock2.IsLockedByCurrentThread() )
        {
            // OBTAINED
        }
        else
        {
            // Locks not obtained, wait until 1st lock freed or another thread takes the second lock.
            while( lock1.IsLocked() && lock1.IsLockedByCurrentThread() == false && lock2.IsLockedByCurrentThread() )
            {
            }

            // 1st lock is restored to this thread.
            if( lock1.IsLockedByCurrentThread() )
            {
                // OBTAINED
            }
            else // another thread has "stolen" the 2nd lock
            {
                // NOT OBTAINED
            }
        }
    }
    else
    {
        // Another thread already has 2nd lock, let's restore it to 1st lock and cancel.
        lock1.Lock( lock2.GetCurrentLockingId() );

        // NOT OBTAINED
    }
}
else
{
    // NOT OBTAINED
}


texts: Why does an inverted page table keep a chain of pages per frame when it can only store one of such pages?

texts:
I'm currently dealing with inverted page tables and how they work. If I understood correctly, an IPT is a table that maps a frame number to a PID and page number. The way this works is by having a hash function map a tuple (PID, page_number) to (frame_number). If the entry of the table given by the frame number contains (PID, page), then we have a hit. Because a hash function can map multiple inputs to one output, we have to keep a chain of pages for each frame (according to my lecture notes).
Why does an inverted page table keep a linked list of pages per frame? Only one page can be loaded into a single frame at a time, how does this make sense? To me this seems more an issue similar to that of direct-mapped caching, where you have to throw out the previous block to make place for a new block.


texts: What is the chance that this code terminates?

texts:
I wrote this Python code, and wondered if it sometimes simply doesn't terminate (assuming we had infinite memory/time and no recursion depth limit).

Intuitively you'd think it terminates, since at some point you must get lucky, and if it doesn't terminate you have an infinite amount of time to get lucky. On the other hand, as the recursion depth increases you must become exponentially more lucky.

import random

def random_tree():
    if random.random() < 0.5:
        return 0
    return [random_tree() for _ in range(random.randint(1, 5))]

If random_tree doesn't always terminate, why, and what is the chance that it does terminate?

I've tried to calculate it using $P = 1 - (1 - 0.5)(1 - (P + P^2 + P^3 + P^4 + P^5)/5)$, which in it's terrific uselessness either gives the answer ~$0.684124$ or... $1$.

Probably more complicated, but also intriguing to me, what is the termination chance  $P(a, b)$ for:

def random_tree(a, b):
    if random.random() < a:
        return 0
    return [random_tree(a, b) for _ in range(random.randint(1, b))]

Or in pseudo-code:

random_tree(a, b) is a function that either:
    - returns 0 with probability a
    - returns a list containing the results of 1 to b
      (uniformly chosen from this inclusive range) recursive calls

random_tree(a, b):
    if rand() < a # rand() is a random real on [0, 1)
        return 0
    list = []
    len = randint(1, b) # uniform random integer from 1 to b inclusive
    do len times
        append random_tree(a, b) to list
    return list


texts: Is there any scenario whereby randomly shufflying a sequence improves it's compressibility?

texts:
I'm performing some correlation assessment à la NIST Recommendation for the Entropy Sources Used for Random Bit Generation, § 5.1.

You take a test sequence and compress it with a standard compression algorithm. You then shuffle that sequence randomly using a PRNG, and re-compress.  We expect that the randomly shuffled sequence to be harder to compress as any and all redundancy and correlations will have been destroyed. It's entropy will have increased.

So if there is any auto correlation, $ \frac{\text{size compressed shuffled}} {\text{size compressed original}} > 1$ .

This works using NIST's recommended bz2 algorithm, and on my data samples, the ratio is ~1.03.  This indicates a slight correlation within the data. When I switch to LZMA, the ratio is ~0.99 which is < 1. And this holds over hundreds of runs so it's not just a stochastic fluke.

What would cause the LZMA algorithm to repetitively compress a randomly shuffled sequence (slightly) better than a non shuffled one?


texts: How To Show That B is Semi-Decidable Given A

texts:
I am preparing for my Computational Theory final and ran into this exact problem :

B={ x | there exists a prefix of x that is in A}.

Show that B is semi-decidable.  In other words, you need to describe an algorithm M that on input a string x semi-decides if some prefix of x is in A (“semi-decides” means that it is OK if the algorithm loops for strings with no prefix in A). You will assume that you have an algorithm MA that semi-decides A.

Any help would be greatly appreciated!


texts: I am currently learning category theory and a saying that I see a lot is that X is the algebra of something (e.g. Monoid is an algebra of something). Can someone explain to me what that means? Thanks!


texts: Average time complexity of linear search

texts:
It is usually assumed that the average time complexity of the linear search, i.e., deciding whether an item $i$ is present in an unordered list $L$ of length $n$ is $O(n)$ (linear).
I have read several proofs, usually assuming either:

that $i$ and the elements of $L$ take values in an infinite domain, in which case the probability of $i$ being is $L$ tends towards 0 and the algorithm will iterate over all elements.
that $i$ is present exactly once in $L$, in which case the expectancy on the number of iterations is $(1 + 2 + … + n)/n \in O(n)$.

However, I would like to introduce the case where $i$ and the elements of $L$ take values in a finite domain of size $d$. Is this case studied somewhere? I have failed to find proof online, but I have found one that finds that the complexity is $O(d)$, and would like to know whether it is correct.
I assume that each element of $L$ is a random value from $[1..d]$. I want the expectancy $E$ on the number of iterations of the linear search algorithm. I also assume that $L$ has infinite size, without loss of generality, I do not want to question the fact that linear search is $O(n)$ on average, it clearly is. My point is that linear search is both $O(n)$ AND $O(d)$. I have interest in the case where $d \ll n$.
At the first iteration, there is a $1/d$ probability that the sought element is found and the algorithm stops. In other cases, i.e. with a probability of $(d-1)/d$, the algorithm iterates. Recursively, I have $E = 1 + E\cdot(d-1)/d$, which boils down to $E=d$.
Also, this seems related to the fact that $\sum_{n=0}^{\infty} \frac{n}{e^n} \in O(1)$, if the recursion is unrolled. My proof, however, seems almost too easy. Is there a fail somewhere?


texts: Consensus algorithm for imperfect annotators

texts:
I'll pose the question in the abstract first and then describe concretely what I'm trying to do.
Suppose I have a set of 1000 000 multiple-choice questions and 10 oracles that can answer the questions. But the oracles are imperfect and don't always answer correctly. Some oracles answer more accurately than others. We don't know which ones are better beforehand though. All answer correctly with probability greater than 60% and less than 100%.
Suppose each oracle answers 100 questions. One in every 10 questions, however, is not a new question but a (random) question that a different oracle has already answered. Which lets you check whether they each got the same answer or not.
Now my question is this, suppose I want to rank the oracles at the end in order of most reliable to least reliable, what's the best metric?
Naively, we could just ask, which oracle had the highest proportion of co-coinciding answers out of all the questions they answered that were also answered by another oracle. But this ignores that fact that if an oracle's answer disagrees with a different oracle, it could be the different oracle that was wrong.
So I think there needs to be a way to scale the penalty based on the rating of the oracle that disagreed.
Is there an algorithm for this sort of ranking?
The two that came to my mind are the Buchholz system, and page rank. Because they both consider secondary comparisons, not just direct comparisons. But I'm not sure how I could apply them.
Concrete context: I have lots of annotators annotating data. We get to send some of the data to multiple annotators, but not all of it. I'm looking for a way to identify annotators who perform poorly so that I can either remove their annotations or reduce the weight of their annotations.


texts: What is the state of the art of full text searching across languages?

texts:
I have looked at a few papers on this such as this, and it basically says that full text search is all about English with few resources for languages without spaces between words (like Chinese or Tibetan), and little for languages with complex morphologies like Arabic.
However, when I do a search on Google for different languages, they show matching results. How are they doing this?

Above I am searching for very popular keywords (key texts in those languages), but still, they are finding relevant results. Searching for word fragments, I find matches (in bold) too:

What is Google potentially doing (at a high, theoretical level) to accomplish this? Are they just doing character grams and statistical analysis? Or is something more fancy going on? Wondering what the general state of the art is.
Other sites like bible.com seem to have full-text search across 900+ languages. For example, ᐊᒡᓔᑦ ᐃᑦᔪᕐᖕᓁᑦᑐᑦ. What are they doing?


texts:
Consider the hitting set problem with $n$ elements and $m$ sets. I gather from the linked page as well as this that

1) it is NP-hard to approximate the cost of the optimal solution to a multiplicative factor of $c \log n$ for some $c>0$.

2) it is NP-hard to approximate the cost of the optimal solution to a multiplicative factor of $c \log m$ for some $c>0$.

3) it is NP-hard to approximate the cost of the optimal solution to a multiplicative factor of $c \log \max(n,m)$ for some $c>0$.

Is my understanding correct? This seems to be a straightforward consequence of what is on the internet, but some of the notation in these sources is mysterious to me and I want to make sure I'm not misunderstanding.


texts: If only using bit-shifts can produce a Turing-machine, or if you need more bitwise operations

texts:
So you can have One Instruction Set Computers. But typically these instructions have rather complicated underlying implementations.

addition (addleq, add and branch if less than or equal to zero)
decrement (DJN, decrement and branch (jump) if nonzero)
increment (P1eq, plus 1 and branch if equal to another value)
subtraction (subleq, subtract and branch if less than or equal)
subtraction when possible (Arithmetic machine)

Those first ones involve 3+ underlying operations. I'm wondering though what bitwise operations you would need in order to produce a Turing-complete computer. The minimal set of bitwise operations, independent of efficiency. Then if that's an easy answer perhaps one that takes efficiency into account, but not necessary for the main question, would just be interesting to know.

I am pretty sure I've seen that you can create every other bitwise operation from a NAND gate, so perhaps you can create them all with a NAND gate. But I am in particular wondering if only using bitshifts can produce a Turing machine. Or if not, what minimal set of bit operations can do it.


texts: Lower the frechet distance between two curves

texts: Fréchet distance tells how similar two curves are. Now let's say I have two curves A and B, both represented in several discrete coordinate x, y points. And the fréchet distance between A and B is d. What technique can I employ to find another curve that has d/2 fréchet distance from both curves and has a total euclidean distance which is in the range [min(|A|, |B|), max(|A|, |B|)], where |A| is the total euclidean distance of the curve A and |B| is the total euclidean distance of the curve B? I know that there is probably not a single curve, any one curve will be great help for me. Thanks in advance.


texts:
I'm doing practice problems for an upcoming exam and I'm unsure if the following problem is NP-complete. If it is can you please give me a hint as to what problem I should reduce to it. I believe it's NP-Complete and maybe the knapsack problem can be reduced to it but I'm not sure.

  WEIGHTED VERTEX COVER:
  Input: A weighted graph $G$ with integer weight $Wv>1$ on each vertex $v$ and an integer $T$.
  Question: Does $G$ have a vertex cover with total weight at most $T$?


texts: Understanding 2's complement multiplication using Booth's algorithm

texts:
I was referring Booth's algorithm for 2's complement multiplication from William Stallings book. It was explained as follows (please ignore two starting words "As before", it still makes complete sense):

The author then gives following example for $7\times 3$, which I am able to understand:

Next author gives examples for all combinations of +ve and -ve combination of multiplication:

Doubt

I am not able to get how example in figure 9.13 maps to same example but more compact approach illustrated in figure 9.14(a). I mean how those entries are made in fig 9.14 (a)

PS: Wanted to add tags "booths-algorithm" and "2s-complement-multiplication", but wasnt able to create those due to low reputations.


texts:
Considering functions f and g, is the following true?

$ (f \in O(g)) \implies (f \in \Theta(g)) \lor (f \in o(g))$

If not, can you please state an example? Despite thinking hard, i could not find one.

Thanks a lot!


texts: Changes in runtime as the input is incremented

texts:
I have a bit of problem in the question below, mainly in the case of incrementing the input size (it doesn't seem solvable to me, like, do we just write $f(n)/f(n+1)$ or...), and also the logarithm ones because I'm not really comfortable with those.
I'd appreciate it a lot if you could take the time to explain them to me.Thank you.


texts: A comparison operation for lists, based on P(a > b)

texts:
Consider two lists $A$ and $B$, both containing $n$ numbers. A comparison operation can be defined based on the probability of uniformly selecting an element $a$ from list $A$ and an element $b$ from list $B$ such that $a>b$.

More precisely, define
$$ Q(A,B) = \sum_{i,j} \text{sign}(a_i-b_j)$$
If $Q(A,B) = 0$, then we can say the lists "tie". If $Q(A,B)>0$ then $A$ "beats" $B$, and likewise $Q(A,B)<0$ can be said as $A$ "loses" to $B$.

The naive way of calculating this comparison of lists involves checking each pair of elements and thus takes $n^2$ time.

  Is there a faster way to calculate this?

Note, that somewhat non-intuitively, $A$ can still beat $B$ even if the average value of $A$ is less than $B$. (Also, even more non-intuitive, this comparison operator is non-transitive. Known as "intransitive dice", you can have dice such that A beats B, B beats C, C beats A.)

I believe if we take the $O(n \log n)$ hit to sort $A$ and $B$ first, then there should be a better way to calculate the comparison. But I'm having trouble filling in the pieces.  Hopefully this is a useful hint instead of a red-herring.


texts:
I need a pool of photos (if possible with description) for my project. I mainly have to perform term extraction for semantic searching. Is there something available out there that is made available for such kinds of thing?

I'm going to mine the description of these photos, maybe build ontologies and then perform search on them. The result of the mining might give useful terms about the pictures.


texts: Let $L$ be a linear language. Then there is a constant $p$ such that for all $w$ in $L$ with $|w| \ge p$, $w$ can be written as $uvxyz$ where (i) $|uvyz| \le p$ (ii) $|vy| > 0$ (iii) $uv^ixy^iz$ is in $L$, for all $i \ge 0$. How do I prove the first condition? I am having difficulty proving the bound and relating the bound k to the grammar.


texts: Why are regular tree languages closed under intersection, but deterministic context free languages are not closed under intersection?

texts: I am looking for intuition here. Essentially, I understand that the set of parse trees from a context free grammar forms a regular tree language. I also understand that regular tree languages are closed under union, intersection and complement. Now, why are deterministic context free languages not closed under intersection? (the intersection of DCFL need not even be in CFL) but intersection of regular tree languages are closed under intersection? (I get why DCFL union is not in DCFL -- because there is ambiguity).


texts: Difficulty in updating the balance factor of nodes in AVL tree

texts:
In this figure x,y,z are the nodes on which rotation is performed and T1, T2, T3, T4 are the subtrees.
I have understood how the rotation is working and have no trouble with that. The problem I am having is determining the final balance factor of nodes in the tree.
In the first case before rotation, the balance of factor of x will be +2 or -2(that's why we are performing the rotation). But what about the balance factor of y? Why is it always taken as +1 or -1 before rotation? Why it can't be 0(the height of T3 can be equal to the height of z)? What will we the balance factor of z before rotation? It can be anything right? In short, what will be the balance factor of nodes with the question mark before and after the rotation?

This is the code I am trying to write:

Node insert(Node node, int key)
{
    if(node == NULL)
        node = new Node(key);

    else if (key <= node->key)
    {
        node->balance++;
        node->left = insert(node->left, key);
    }

    else if (key > node->key)
    {
        node->balance--;
        node->right = insert(node->right, key);
    }

    // Right Tree Heavy
    if (node->balance == -2)
    {
        /*Do the required rotation and update the balance factor*/
    }

    // Left Tree Heavy
    if (node->balance == 2)
    {
         /*Do the required rotation and update the balance factor*/
    }

    return node;
}

Edit: Initially the tree was satisfying all the properties of avl tree. Then a new node was added to either T1 or T2 which made the tree unbalanced at node x. Can anyone explain all the cases of balance factor of nodes before and after the rotation.


texts: Why is this pushdown automaton for some palindromes right?

texts:
$B = \{w \in \{0,1\}^* | w^R = w, w \text{ length is odd} \}$

Solution:

For example: $111$ should be accepted

steps are

$q_1 \to q_2$ stack: [$\$$]

$q_2 \to q_2$ stack: $[\$, 1, 1]$ (using up $11$ only having a single $1$ left)

$q_2 \to q_3$ stack: $[\$, 1, 1]$ (no change except we lost our final $1$)

$q_3 \to$ (no strings left to use)

I'm confused understanding this


texts: Negative Numbers in 32 bit Floating Point IEEE Numbers

texts:
So I understand the logic behind converting positive decimal numbers to IEEE 32 bit floating numbers but I'm not completely sure behind the negative one's. If for example we have a decimal number say -15.5, do we have to do two's complement first then convert it to the floating point representation or we directly do it for 15.5 and at the sign bit we do 1.
Thank you in advance.


texts: Generate numeric or string ID for a sequence of elements

texts:
How to generate a numeric or string id(not very large text) for a sequence of elements where ordering doesn't matter.

Example:
[41,1001,32] should generate the same ID as [32,1001,41]
[41,1001,32, 5] should be different.

Elements could be hundreds where each individual ID can be a 4/5-digit number.

I thought about sorting, concatenate and Hash/Compress the string, but are there gonna be a lot of collisions ?

Any ideas would be much appreciated.


texts: Expected time of unsuccessful search: chaining and linear probing

texts:
We use a simple uniform hash function to insert 300 keys into two tables of size 1000, we use chaining at one table and linear probing at the other. We are given that the keys were mapped into 290 different cells. What is the expected time of unsuccessful search in each case?

I think that the expected time will be 300/1000 at the chaining table, and $0.5(1+(1-3/10)^2)$ at the linear probing table. Is this correct? I'm not sure how the fact that the keys were mapped into 290 different cells may change the answer.


texts: NP-Completeness reduction, using a same input

texts:
We have problem X and Y that we know is NP-Complete. Problem X uses graph G as an input and Problem Y uses graph G and constant k as an input.

Problem we are trying to reduce to, which I will call Z, is reasoning whether given a graph G and constant k, does G have X or Y.

I have been trying to solve this problem and an idea I came up with is to use an input G and k which can serve as an input for both X and Y, and reduce it to G' and k' where G=G' and k=k' for problem Z

Is it a valid thing to reduce without changing an input?


texts: Check if a matrix over finite fields is superregular

texts:
Is there any practical, efficient algorithm to check if a matrix over $\mathbf{F}_{p^n}$ is superregular?

It need not be theoretically polynomial, just roughly be implementable for $n=32$ and for matrices of approximate size $20 \times 100$.

  Definition: A matrix is superregular if all its minors are non-singular.

In particular, I'm looking for a construction of block circulant matrices that are superregular.


texts: Maximum waiting time between events such that k events are not missed

texts:
I've been given some homework on dynamic programming and I'm having trouble to find the suboptimal recurrence. Let me copy the statement:

In a given motorcycle training circuit, the number of riders is becoming increasingly large. As such, a new set of stricter rules is being enforced.

Lap times last exactly a minute, and they are booked for the full minute.
If we use a free lap time slot, we must wait x seconds until we can use another.

We are given a list {s1,s2,s3,...,sn} of the free slots starting time and we want to practice at least m minutes, at minimum. Find the maximum x that allows this.
Example:
With the list {00:00:00,00:10:03,00:14:00} and an m = 2 we can impose a maximum wait time of 00:14:00 - 00:01:00 = 00:13:00 = 1560s because we only need to lap two times, and we can do so with the first and last slot.

So I tried hard and came up with this recurrence:
$$X[i,m] = \max_{1 \leq j \leq i}\ (\min\ (X[j,m-1],\sum_{k=j}^{n-1}abs(s_{k+1} - s_k)))$$
Where X[i,m] means "the maximum distance that I can pick in the subset $\{s_1,s_2,...,s_i\}$ so that I lap at least m times".
Then it's only a matter of applying dynamic programming. However, I'm not convinced that this solution is correct, because no matter how hard I try to make an algorithm out of it (using a matrix $X_{im}$) I can't come up with a good solution looking at the right bottom corner value (where i = n and m = laps requested).
Any ideas or hints?
Thank you.


texts: Proving NP-completeness in relation to putting items in bins

texts:
If I can assume that it is NP-complete to determine whether a set of objects can be packed into 2 bins, how can I prove that it is NP-complete to determine whether a set of objects can be packed into 3 bins?

I understand that this is like the Knapsack problem, but I am having trouble going backwards essentially, since 2 bins is the reduced version of 3 bins.


texts: Manage event programming under a stack-oriented language

texts:
I wonder how events, or more broadly reactive programming, could be managed in a simple stack-oriented language.

For example, let's imagine a context where there is a button that displays a small message when you press it. How could an entire program on the stack handle the case where the user presses the button without that becoming unmanageable (for example +30 buttons)? Does the button information remain on the stack throughout the execution? Since we only have access to the last element of the stack, how do we send the information?

More clearly, how could a stack of execution of a stack-oriented language handle the case of the events?


texts: Is the mate-in-n problem of infinite chess with each color using traditional pieces plus one huygens decidable?

texts:
I noticed in a paper that the mate-in-n problem of chess, even played on an infinite board is decidable. The mate-in-n problem of inﬁnite chess is decidable

I believe the paper assumes only traditional chess pieces are used.

What if one of the chess pieces is a huygens? (A huygens is a chess piece which jumps prime numbers of squares).

Is the mate-in-n problem of chess on an unbounded board with each color using traditional chess pieces plus at least one huygens also decidable?


texts: Is this graph problem NP-hard / NP-complete?

texts:
I have a certain kind of graphs. They are DAGs similar to dependency graphs but strictly hierarchical, that is, each node belong to a certain level in the hierarchy and cannot be moved up or down when the graph is laid out onto a plane. The nodes can be arbitrarily exchanged with others in the same level.

Here's an example:

The problem:

Find an ordering (permutation) of the nodes in each level of the hierarchy such that the total number of edge crossings is minimal.

The problem could be, I suppose, rephrased as a decision problem: Given an ordering of nodes in each level, decide whether that ordering is minimal in terms of number of edge crossings.

For example, in the above graph embedding there are 3 edge crossings, however, by reordering the nodes in a certain way we obtain an embedding that only has 1 edge crossing (I believe this is minimum for this particular graph):

(Nodes that have been moved are highlighted.)

The question:

Is this problem NP-hard? I'm having a hard time finding correspondence to one of the more well-known NP-hard/NP-complete problems but at the same time I'm having a hard time finding a polytime solution.


texts: I get how to reduce 3-SAT to 3-COLOR, but I'm not sure how to do it the other way around. Does anyone  have any hints or insight?


texts: conversion of basic $\text{CTL}^*$ formulas to $\text{CTL}$

texts:
Consider the $\text{CTL}^*$ formula $E[pU(qUr)]$.

It is not hard to show that it is equivalent to the $\text{CTL}$ formula $E[pU(EqUr)]$.

The informal reason is that a path where $p$ is true until $qUr$ is true is the same as a finite branch where $p$ is true along it, followed (concatenated with) by a path (starting at a son of the last state of the former branch) along which $qUr$ is true.

However, consider now the $\text{CTL}^*$ formula $A[pU(qUr)]$, here I have a problem in pushing the $A$ inside, because the $\text{CTL}$ formula $A[pU(AqUr)]$ is "stronger" than the former.

The reason is that in the former we demand that any branch contains a state starting from which $qUr$ is true. While, the latter formula demands that any branch contains a state such that any computation starting from it has $qUr$ true.

How can I still convert $A[pU(qUr)]$ to $\text{CTL}$?


texts: When concatenating two sequences, can evaluations of two input sequences be in parallel with each other?

texts:
In Practical Foundation of Programming Languages by Harper (www.cs.cmu.edu/~rwh/pfpl/2nded.pdf),

  37.3 Multiple Fork-Join

  So far we have conﬁned attention to binary fork/join parallelism induced by the parallel
  let construct. A generalizaton, called data parallelism, allows the simultaneous creation
  of any number of tasks that compute on the components of a data structure.

There are two expressions:

seq(e_0 , . . . ,e_{n−1} )     sequence
...
cat(e_1 ; e_2 )     concatenate

In the cost dynamics,

(37.9a) indicate that evaluation of a seq expression (forming a sequence from the n elements e_i's) can be parallelized betwen the n elements.
(37.9f) , evaluation of a cat expression (concatenate two sequences e_1 and e_2)  first evaluates e_1 and e_2 to two sequences, and then consolidate their elements into one result sequence. Why are evaluations of e_1 and e_2 to two sequences not in parallel with each other?

Thanks.


texts: Testing whether an analytic function vanishes identically

texts:
I have an application that basically reduces to testing whether a given function vanishes identically. The function is given symbolically, using unary and binary operators on complex numbers. For example, we might want to test the function $(z+1)^2-z^2-2z-1$. (It could be a function of more than one variable.)

The problem is known to be undecidable. However, there are reasonable heuristic approaches. The one I've been using involves numerical sampling. I just pick random complex values for $z$, and evaluate the function using machine-precision arithmetic. This works pretty well in most cases, and is efficient. If the function is known to be analytic, then the method would succeed with unit probability given infinite-precision arithmetic.

One could use a computer algebra system for this, but a CAS is computationally expensive and often will not reach any definite conclusion.

Although the numerical sampling heuristic generally works pretty well, it's not hard to come up with examples where it fails. For example, consider the function $z^{100}$. For almost any $|z|<1$, I get an underflow, and for almost any $|z|>1$, I get an overflow. Either way, the result is inconclusive. (An overflow doesn't automatically tell me the function is nonzero, because it could happen at some intermediate step in the computation.)

Can this heuristic be improved on? Using multiple-precision arithmetic rather than machine precision doesn't seem to be a big win. It's much more computationally expensive, and even if I take 100 digits of precision, it's still pretty easy to construct examples where it fails.

It seems like it might make sense to try some kind of adaptive algorithm in bad cases to search for regions of the complex plane that neither underflow nor overflow. Or more generally we could maintain error bounds, and search for regions where the error bounds do not make the result inconclusive.

Symbolic differentiation is cheap and doesn't fail, so I could also test whether the function's derivatives are zero. But this doesn't necessarily help for an example like $z^{100}$, unless I happen to get lucky and try the 100th derivative.


texts: Logarithmic space difference between deterministic and non-deterministic algorithms

texts:
I had an interview today, and the interviewer has told me about a theorem (of someone called Hill- or Hell-something) which states that for a non-deterministic algorithm there exists a deterministic algorithm of some time complexity and a space complexity of no more than the original space complexity times log(n).

I am looking for that theorem (couldn't find it on Google). Thanks!


texts: Big-O: Why is the time complexity of these loops O(N)?

texts:
I have the following function.

int fun(int n)
{
  int count = 0;
  for (int i = n; i > 0; i /= 2)
     for (int j = 0; j < i; j++)
        count += 1;
  return count;
}

It has O(N) time complexity. I thought it's O(N LogN)(i.e. If we remove the inner loop we get)

for (int i = n; i > 0; i /= 2){
...
}

This is O(Log N) isn't it? And the inner loop turns out to be O(N) as it just increase linearly. So I think it's supposed to be O(Log N * N). What might go wrong on my thought?


texts: Approximate Bayesian Computation VS Monte Carlo Simulation

texts:
I am a little confused about the differences between Approximation Bayesian Computation (ABC) and Monte Carlo Methods (MCM). Citing from wikipedia:

Approximate Bayesian computation (ABC) constitutes a class of computational methods rooted in Bayesian statistics. In all model-based statistical inference, the likelihood function is of central importance, since it expresses the probability of the observed data under a particular statistical model, and thus quantifies the support data lend to particular values of parameters and to choices among different models. For simple models, an analytical formula for the likelihood function can typically be derived. However, for more complex models, an analytical formula might be elusive or the likelihood function might be computationally very costly to evaluate.
Monte Carlo methods (or Monte Carlo experiments) are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. [..] Monte Carlo methods are mainly used in three distinct problem classes: optimization, numerical integration, and generating draws from a probability distribution.

In both cases, we run many simulation starting with constant or varying parameters and get the posterior probability (although I am not sure we call that a posterior probability in MCM). I would tend to think that ABC is MCM, where we use the posterior probability to define a confidence interval. Or maybe, by definition MCM are deterministic and therefore the resulting distribution is a function of the parameter values only and therefore it does not make any sense to make any statistical inference (such as calculating an confidence interval). I'd tend to think that ABC is a type of MCM, where we make statistical inference (or whenever the simulation takes a random seed in input). Is that right?

Is ABC a specific case of MCM?
Is ABC just like an MCM except that a random seed is taken in input?


texts: Why the restriction on the length of the proof in a $(r,q)$-verifier in PCP is inconsequential?

texts:
In the textbook by Arora-Barak, they define PCP verifier as

While in the definition they put a restriction of $q2^r$on the length of the proof, later, they say that it is inconsequential as the machine can look on at most this number of locations with nonzero probability over all $2^r$ choices for its random string.


texts: How many knights can be placed on an n-by-m chessboard?

texts: I have a task, and its essence is as follows: how many knights on an $n \times m$ board can be set so that they do not attack each other. I am wondering if there is any mathematical solution to this problem, except for the algorithmic one.


texts: What are the correlation between Actor model and Reactive Programming

texts:
Could anyone explain the difference/relation between the Actor model and Reactive programming?

It seems that they are located at different levels of abstraction - one can design the interaction between the components of any distributed system using Actor approach, they would send messages, and inside the actors, write code in reactive style?

this question related to How do Functional Reactive Programming and the Actor model relate to each other?

However, the answers wasn't clear enough, and my question relates reactive programming in general, not FRP in particular.


texts: Is it possible to achieve greater than perfect compression using machine learning and big data?

texts:
Imagine Google wanted to make their chrome browser faster. Let "database" be all the machines which serve content from Google's servers, including Search and Google cloud services. Google begins using machine learning to analyze thousands of petabytes of data on their database to extract a dictionary of the most redundant file sequences. Lets say the most redundant hexadecimal found was the sequence:

"64 65 63 69 6d 61 6c 20 66 6f 72 6d 61 74 2e 20 43 6f 6d 70 75 74 65 72 73 20 73 74 6f 72 65 20 74 65 78 74 20 61 73 20 6e 75 6d 62 65 72 73 2c 20 61 6e 64 20 77 69 74 68 20 68 65 78 20 79 6f 75 20 64 69 73 70 6c 61 79 20 74 68 65 20 6e 75 6d 62 65 72 73 20 6e 6f 74 20 61 73 20 61 20 64 65 63 69 6d 61 6c 20 6e 75 6d 62 65 72 2c 20 62 75 74 20 69 6e 20 62 61 73 65 20 31 36 2e 20 48 65 78 20 6f 72 20 62 61 73 65 20 31 36 20 6f 72 20 68 65 78 61 64 65 63 69 6d 61 6c 20 69 73 20 61 20 6e 75 6d 65 72 61 6c 20 73 79 73 74 65 6d"

They stored this sequence in their dictionary at index 1 and included this dictionary file in their Chrome update. For every user that had the latest Chrome update if they requested a file that had this sequence Google's server would return a flag and the index 1 (e.g. "D 1") such that the Chrome browser could lookup the bytes locally without the need of transferring them over the network. In essence the file being transferred would become something like "data data data D 1 data data"

Furthermore, they did this for gigabytes of sequences causing a larger Chrome update but faster file transfer times.

And to make things more interesting they used machine learning to analyze end-user behavior to predict which sequences were more likely to be requested.

After adding this functionality they achieved faster load times and decreased network congestion and possibly saved in electricity costs by removing redundancy across their entire network.

Questions:

What would this be called? Distributed Cached file transfer?  Would this be practical or desirable? I imagine it could save money in terms of electricity for a large company like google.


texts: Given two or more nodes in a network, is it possible to determine the one-way link latencies between two nodes that share a bi-directional connection?

texts:
We already know that detecting the one-way latency between only two nodes is impossible.

However, if I have a number of nodes in the same subnet that all know about each other, can measure round-trip latencies (e.g. via ping), and can communicate with each other - and assuming link latencies do not change over time (for the simplicity of the problem) - is it possible to measure the individual up and down link speeds between two particular nodes within the subnet, potentially via coordination of one or more unrelated nodes in the network?


texts: Which of $2^{\log_*n}$ and $\log\log n$ grows faster?

texts:
Function 1: $2^{\log_*n}$

Function 2: $\log(\log n)$

The first function is 2 to the log-star of $n$, the second function is log of log of $n$.
What I need to know is which one is Big-Omega of the other one, which means, which one grows faster. How can I figure that out? I know the definition of log-star (iterative logarithm) but I don't know how to apply it in order to compare the given functions. Could you guys give some help?

Thank you in advance.


texts: Is WPA2 with pre-shared key an example of a zero-knowledge proof?

texts:
When setting up an access point and selecting WPA2, one must manually enter a pre-shared key (a password), PSK, into both the AP and the STA.

Both parties, AP and STA, must authenticate each other. But they have to do so without revealing the PSK. Both have to proof to the other party that they know the PSK without actually sending it.

Is that an example of a zero-knowledge proof?

I thought it was, but nothing legit shows up when I google for zero-knowledge proof and WPA2 or EPA-PSK (the authentication method used).


texts:
If A and B are regular language, what is a context free grammar of the following language?
$$
A \circ B = \{ xy \mid x \in A \text{ and } y \in B \text{ and } |x|=|y| \}
$$


texts: Finding sequence of pairs with second element of previous pair matching first element of next pair

texts:
I am interested in efficient ways of doing certain problem.

I have list of $n$ pairs, where $n$ is usually a few houndred thousands and each pair's element is an integer (let's assume it is integer from $0$ to $10000$) and I am trying to find a sequence such that it start and ends at chosen integer (we can assume it is eg. $0$) and second element of previous pair matches first element of next pair. So as an example, if we have set of pairs $\{(0,1), (1,3), (3, 2) (3,0)\}$ the valid sequence would be eg. $(0,1), (1,3), (3, 0)$. If there is a few answers then I can find arbitrary one. Moreover it is no certain  that my list of pairs actually has a solution. If it does not have solution, then the method should return no valid solutions.

I think that maybe some kind of dynamic programming could be useful here, but I don't really have an idea for something better than just checking all the options, which I am almost certain is quite bad. Do you have any interesting insight about this problem?


texts:
Meek's version of the Single Transferable Vote system [.pdf] is used in multiple big elections including those of New Zealand and Stack Exchange.

Demonstration (with thanks to the Department of Internal Affairs of New Zealand).

I have a basic understanding of how the votes are counted, but there's one thing I haven't been able to figure out.

What happens if positions are left blank?

For example:
Assume 6 candidates and no limit on the amount of choices.

One could vote (where left is first vote and right is last): 3 4 5 6 1 2 or 4 5 6 and leave the rest blank.

In the STV system, the following is legal as well: 0 2 4 0 1 6
What would happen in that case?

Will the choices be shifted to clear it from any left-open positions or will the votes be counted at the moment indicated by the position? Those options will (likely) influence the election both in different ways.

I'm not a CS expert in any way, just trying to get the hang of an interesting system to implement my own vote counter.


texts: Why are Complexity Notations Called Asymptotic?

texts: Why do we use the term "asymptotic" in complexity. Although I know what an asymptote is, but what is an asymptote doing here?


texts:
Black box of $f(x)$ means I can evaluate the polynomial $f(x)$ at any point.

Input: A black box of monic polynomial $f(x) \in\mathbb{S}[x]$ of degree $d$.
Question : $\mathbb{S} \subseteq \mathbb{Z}$, unbounded from both sides

Here $\mathbb{S} \subseteq \mathbb{Z} $ is an interval unbounded from both sides. For example interval $(-b,\infty]$, where $b$ is any fixed value and this interval is bounded from left side. I am allowed to make only constant many queries to oracle. I want to find such an subset $\mathbb{S}$.

Unbounded interval: An interval is said to be left-bounded or right-bounded if there is some real number that is, respectively, smaller than or larger than all its elements. An interval is said to be bounded if it is both left- and right-bounded; and is said to be unbounded otherwise

Please give a reference to material also if possible. If anything is not clear please ask in the comments I will try clear it.

Motivation : Find a polynomial in two or three queries


texts: An equivalent of $\neg ((a \wedge b) \Leftrightarrow c)$ based on a specific requirement

texts:
I am solving a problem that is asking to provide an equivalent for $\neg ((a \wedge b) \Leftrightarrow c)$ and the equivalent shouldn't contain $\wedge$ (and), $\Rightarrow$ (implication) or $\Leftrightarrow$ (iff).
What I have worked out is:
$\neg(\neg((\neg a \vee \neg b) \vee \neg c) \vee \neg(\neg(\neg a \vee \neg b) \vee c))$
I wonder based on the requirement stated above, is there a shorter equivalent for my answer?
Update
$\oplus$ is not allowed in the requirement either.


texts: Making mathematical expressions as balanced trees as possible

texts:
I am having some trouble with turning the following mathematical expressions into as balanced binary trees as possible.

This is what I have done so far, but is there a way to make them even more balanced?

$( − 3)(^2 +  − 1)$

$4( − 1)( − 2)( − 3)$


texts: Sub-Graph Isomorphism for graphs with multiple edge types and multiple node types

texts: I found that there are algorithms like VFlib and LAD filtering for subgraph isomorphism with one edge type. For multiple node types,one idea could be color all node types with the same type and use colored sub-graph isomorphism which is available for VFlib. I was wondering is there any algo specifically for multiple edge types or should I modify existing algo to check for edge types also?


texts: Optimality in multi-agent multi-target path finding

texts:
Suppose I have a regular rectangular weighted grid with multiple agents and obstacles. Agents cannot be in grid sites that contain obstacles, and for simplicity assume multiple agents can be in the same grid site.

If I select a single location on the grid and want to find the nearest agent to that location, a good solution is easy: I can simply do a breadth-first (BF) search.

However, suppose I have n target locations and m>=n agents. I want to visit the target locations with n agents simultaneously. I do not care which agent goes to which location, but the total distance travelled must be minimal. Or, to rephrase, I'm attempting to find a distance-weighted maximum matching for two sets of nodes on a graph.

One solution would be to calculate the shortest path from all agents to all targets and then do a bipartite matching. Since the graph may be disconnected by obstacles, this could result in needless multiple sampling of the entire grid space of a connected region. This hardly seems optimal. (Solution 1)

I propose the following 'algorithm' (Solution 2):

from each target location start a BF search until there is one agent in every target's searched space
if the number of unique agents in the searched spaces is less than n, continue searching from all target locations
if a matching between targets and agents in their respective searched spaces is not possible with full target covering, continue searching from the target locations where covering was not possible and all other target sites that share agents with the uncovered target sites all target locations.
the first matching that fulfils step 3 is the solution

now I have two questions:

is solution 2 optimal, i.e. is it guaranteed that I will select precisely those agents with the least total distance to their assigned targets? I.e. am I not neglecting any agents by not continuing the search for long enough?
if solution 2 is optimal, are there any further ways of reducing the computational complexity?


texts: Is a set of acyclic |V| - 1 light edges always a Minimum Spanning Tree?

texts:
I am trying to prove the algorithm for Question 5 in this practice exam.
I am trying to prove this algorithm with the following three claims:

Suppose we have a graph G, a minimum spanning tree T, and a set of edges A that is a subset of T.  Suppose that we also have a cut C = (S, V - S) that respects A, and edge e = (u, v) is a light edge for that cut.  Then, A $\cup$ { e } is also a subset of some minimum spanning tree T'.

Suppose we have a graph G with |V| vertices that has a minimum spanning tree.  Suppose we also have a set of |V| - 1 edges = <$e_1$, $e_2$, ..., $e_n$>, such that each edge is a light edge for some cut C, and these edges do not form a cycle.  This set of edges must form a minimum spanning tree.

The algorithm given will generate a set of acyclic |V| - 1 edges each of which is light for at least one cut; thus, it will generate a minimum spanning tree.

The first and third claims are easy to prove, but I am unable to prove the second claim.  This is what I have so far:

Trivially, the set of edges must form a spanning tree - it is not possible to have |V| - 1 edges and no cycles without connecting all |V| vertices.
This spanning tree must also be a minimum spanning tree: suppose we have a new empty set of edges A.  A is trivially a subset of some minimum spanning tree for G.  A $\cup$ { $e_1$ } is also a subset of some MST by Claim 1 (because $e_1$ is a light edge for cut C which trivially respects the empty set A).
Now let us examine edge an edge $e_2 = (u, v)$ that is incident to one vertex touched by $e_1$.  We can assume without loss of generality that there is currently no edge incident to $v$.  [I can't prove that $e_2$ is safe to add].

I was wondering if this claim is even correct - and if so, how I can go about proving it.


texts: Viterbi training vs. Baum-Welch algorithm

texts:
I'm trying to find the most probable path (i.e., sequence of states) on an hidden Markov model (HMM) using the Viterbi algorithm. However, I don't know the transition and emission matrices, which I need to estimate from the observations (data).

To estimate these matrices, which algorithm should I use: the Baum-Welch algorithm or the Viterbi Training algorithm? Why?

In case I should use the Viterbi training algorithm, can anyone provide me a good pseudocode (it's not easy to find) ?


texts: How Janus (Reversible Programming Language) `if`, `while`, and Update Work

texts:
In Reversible Computing, all program statements are reversible. I understand for example that the following:

\begin{align}
x\ {+}&{=}\ 4\\
y\ {*}&{=}\ x\\
x\ {-}&{=}\ 10
\end{align}

Has the inverse:

\begin{align}
x\ {+}&{=}\ 10\\
y\ {/}&{=}\ x\\
x\ {-}&{=}\ 4
\end{align}

However, I am not following the following if statement, while loop, and reversible update:

$$\texttt{if}\;e_1\;\texttt{then}\;s_1\;\texttt{else}\;s_2\;\texttt{fi}\;e_2$$

$$\texttt{from}\;e_1\;\texttt{do}\;s_1\;\texttt{loop}\;s_2\;\texttt{until}\;e_2$$

$$x \odot f(y)$$

I understand that for a statement to be reversible, the function has to be injective. So you can't have $f(x, y) \mapsto x$ because information is lost.

I don't understand how those if/loop/update functions can be reversible without storing some sort of information/state in the program's evaluation. For example:

x += 4

While that does have the inverse x -= 4, that is not inherent in the statement x += 4. For it to be reversible, it is almost like it would have to store state about it's previous value:

statement1 x = 1
statement2 x.values.push(x)
statement3 x.value = x.value + 4

Then you can do undo x and it would do something like:

x.value = x.values.pop()
x // 1

which is equivalent to:

x -= 4

So basically I'm wondering, how these "reversible" statements work. If they are saving state in some hidden way, or if it is reversible in some sort of tricky way. Maybe an example of stepping forward and backward through the program as it evaluates any of these expressions.


texts: Simulate deterministic PDA with 1-tape Turing machine?

texts: Is it possible to write a 1-tape Turing machine in order to simulate a deterministic PDA? How would this be done?


texts: Proof of decidability of determining whether a DFA accepts a string

texts:
I want to ask the acceptance problem:
Whether a particular deterministic finite automaton accepts a given string can be expressed as a language, $A_{DFA}$.
Show $A_{DFA}$ is decidable.
The proof in the textbook (Siper page 195) uses two steps:

$M$ = “On input $\langle B,w\rangle$, where $B$ is a DFA and $w$ is a string:

Simulate $B$ on input $w$.
If the simulation ends in an accept state, accept. If it ends in a
nonaccepting state, reject .”

What exactly is the meaning of "simulating $B$" in the first step? In my understanding, if $M$ wants simulates multiple DFA $B$, the parameters of $M$ (transition function or acceptance state) need to be changed according to the different input DFA $B$ and input string $w$, since different DFAs may have different structure. In other words, can a TM simulate infinite DFAs? And how it can be done? I know this question may be trivial, but it really bugs me. Any clarification will be appreciated.


texts:
I read about the time complexity for modular arithmetic in many books. There is one thing that I don't understand. I read in some books the following:

For any $a \mod N$, $a$ has a multiplicative inverse modulo $N$ if and only if it is relatively prime to $N$. When this inverse exists, it can be found in time $O(n^3)$ (where  $n$ denotes the number of bits in the binary representation of $N$) by running the extended Euclid algorithm. My question revolves around extended Euclid algorithm having $O(n^3)$ complexity.

When I write in Java or C#, a line like this:

A = B.modInverse(N) // Java syntax

Can I usually say that this line has time complexity $O(n^3)$?
Or is it necessary to write the code for the extended Euclid algorithm?

Secondly, does extended Euclid algorithm depend on the compiler or the computer architecture?


texts: Is "duplicate" in RPN enough for replacing variable binding in term expressions?

texts:
I try to work out some consequences of storing (or "communicating"/"transmitting") a rational number by a term expression using the following operators: $0$, $\mathsf{inc}$, $\mathsf{add}$, $\mathsf{mul}$, $\mathsf{neg}$, and $\mathsf{inv}$. Here $\mathsf{add}$ and $\mathsf{mul}$ are binary operators, $\mathsf{inc}$, $\mathsf{neg}$, and $\mathsf{inv}$ are unary operators, and $0$ is a $0$-ary operator (i.e. a constant). Because I want to be able to also store numbers like $(3^3+3)^3$ efficiently, I need some form of variable binding. I will use the notation $(y:=t(x).f(y))$ to be interpreted as $f(t(x))$ in this question. Now I can store $(3^3+3)^3$ as
$$(c3:=(1+1+1).(x:=((c3*c3*c3)+c3).(x*x*x))).$$
If I stick to the operators $0$, $\mathsf{inc}$, $\mathsf{add}$, and $\mathsf{mul}$, this becomes
$$(c3:=\mathsf{inc}(\mathsf{inc}(\mathsf{inc}(0))).(x:=\mathsf{add}(\mathsf{mul}(\mathsf{mul}(c3,c3),c3),c3).\mathsf{mul}(\mathsf{mul}(x,x),x))).$$
Using RPN with a "duplicate" operation written $\mathsf{dup}$ instead of variable binding, this becomes
$$0\ \mathsf{inc}\ \mathsf{inc}\ \mathsf{inc}\ \mathsf{dup}\ \mathsf{dup}\ \mathsf{dup}\ \mathsf{mul}\ \mathsf{mul}\ \mathsf{add}\ \mathsf{dup}\ \mathsf{dup}\ \mathsf{mul}\ \mathsf{mul}.$$

My question is whether it is always possible to replace variable binding by the "duplicate" operation. The binary operations ($\mathsf{add}$ and $\mathsf{mul}$) are associative and commutative, but it seems to me that even this is not enough for ensuring that variable binding can be completely eliminated. Take for example
$$(c2:=(1+1).(x:=(((c2+1)*c2)+1).(y:=(x*x).((y+c2)*y)))).$$
If I stick to the operators $0$, $\mathsf{inc}$, $\mathsf{add}$, and $\mathsf{mul}$, this becomes
$$(c2:=\mathsf{inc}(\mathsf{inc}(0)).(x:=\mathsf{inc}(\mathsf{mul}(\mathsf{inc}(c2),c2)).(y:=\mathsf{mul}(x,x).\mathsf{mul}(\mathsf{add}(y,c2),y)))).$$
Using RPN with a "store" operation written $\mathsf{sto}(x)$ instead of variable binding, this becomes
$$0\ \mathsf{inc}\ \mathsf{inc}\ \mathsf{sto}(c2)\ c2\ \mathsf{inc}\ c2\ \mathsf{mul}\ \mathsf{inc}\ \mathsf{sto}(x)\ x\ x\ \mathsf{mul}\ \mathsf{sto}(y)\ y\ c2 \ \mathsf{add}\ y\ \mathsf{mul}.$$
After eliminating $\mathsf{sto}(x)$ and $\mathsf{sto}(y)$ by $\mathsf{dup}$, this becomes
$$0\ \mathsf{inc}\ \mathsf{inc}\ \mathsf{sto}(c2)\ c2\ \mathsf{inc}\ c2\ \mathsf{mul}\ \mathsf{inc}\ \mathsf{dup}\ \mathsf{mul}\ \mathsf{dup}\ c2 \ \mathsf{add}\ \mathsf{mul}.$$
Using explicit substitution to eliminate $\mathsf{sto}(c2)$, this becomes
$$0\ \mathsf{inc}\ \mathsf{inc}\ \mathsf{dup}\ \mathsf{inc}\ \mathsf{mul}\ \mathsf{inc}\ \mathsf{dup}\ \mathsf{mul}\ \mathsf{dup}\ 0\ \mathsf{inc}\ \mathsf{inc}\ \mathsf{add}\ \mathsf{mul}.$$
My issue with explicit substitution is that it might lead to an exponential increase in the size of the expression. It's easy to see that expressions like $(3^3+3)^3$ or $((3^3+3)^3+3)^3$ can't be stored efficiently without something like $\mathsf{sto}(x)$ or $\mathsf{dup}$. Is there another way to eliminate $\mathsf{sto}(x)$, like an additional first-in, first-out queue? Or can one prove that an exponential blowup of the expression won't happen, if only explicit substitution and $\mathsf{dup}$ are "suitably" used together?


texts: trouble solving the recurrence 4T(n/2) + n

texts:
I am having trouble figuring out how to solve this recurrence problem...
$$
\begin{aligned}
&4T(n/2) + n \\
= &4(4T(n/4) + n/4) + n \\
= &16T(n/4) + 2n \\
= &4^kT(n/2^k) + kn
\end{aligned}
$$
I lose the trail here and I cannot figure out how to finish it and actually find the complexity. Can anyone help? How can this be done?


texts:
SAT solvers are getting more and more efficient in solving large instances and are being used as back-ends in various contexts.
Every time one wants to use them to solve a problem in a specific domain, he/she has to come up with an ad-hoc encoding that not only has the right set of solutions but also puts the constraints (even redundant) in a form that helps the heuristics of solvers in finding a solution faster.

Many such encodings seem to me would be very common, for example: asserting that a finite set of nodes is linked as a tree, or as a DAG, or a list is sorted...

Is there a repository/recipe book of common encodings for common problems with optimised solutions?


texts: $L \in RE/R$ such that $L^R \cup L \in R$

texts:
Prove/disprove: $\exists L \in RE/R$ such that $L^R \cup L \in R$

Where in my context, $R$ is the turing decidable, and $RE$ is the recursively enurmable. I tried to find such an $L$ but couldn't. What I know for sure is that I need a language in $RE/R$ such that $L \cup L^R = \Sigma^*$, or am I also wrong?


texts: Terminology - What does alphanumeric order mean in relation to decimals?

texts:
It is also called Natural sort order.

  "It's hard to find information on natural sorting"-Jeff Atwood on Coding Horror.

And it seems true today as the Wikipedia entry seems pretty bare.

Definition 1: Non-numeric word-character substrings are sorted lexically, case-insensitively. Numeric substrings are sorted numerically. non words-characters, non-digits are ignored.

Definition 2: Natural sort order is an ordering of strings in alphabetical order, except that multi-digit numbers are ordered as a single character.

The main difference is that Definition 1 allows decimals while Definition 2 does not. For example I have the list ["t8.1", "t8.11", "t8.2", "t7.2", "t7.11"].

Definition 1 would yeild: ["t7.11", "t7.2", "t8.1", "t8.11", "t8.2"].

Definition 2 would yeild: ["t7.2", "t7.11", "t8.1", "t8.2", "t8.11"].

Python's natsorted function was definition 1 until v4.0.0 and now uses realsorted for this behavior. Python's natsorted function currently follows definition 2.

Perl follows definition 1 (which is where I found it.

Php follows definition 2

MATLAB uses definition 2 for non-version numbers.

Dave Koelle implements definition 1 for his examples but says it's a 'glitch' and thus supporting definition 2 as correct. In most the linked code, the code treats '.' as a string but what if it was a decimal in a numeric substring? Dave Koelle notes this as a glitch by saying "There is currently a glitch when it comes to periods/decimal points - specifically, periods are treated only as strings, not as decimal points.".

To me, the word numeric would imply decimals but in practice it seems that this is not the case unless specifically noted to include decimals.

What does Alphanumberic/Natural Order Sort mean exactly without additional qualifiers? For example: In "Natural Order Sort with decimals", "with decimals" would be an additional qualifiers. Which definition is correct for "Natural Order Sort"?

Alphanumberic (Non-Decimal) vs Alphanumberic (Decimal)


texts:
I'm reading "Algorithms Fourth Edition" by Sedgewick & Wayne and am wondering if I have spotted an error in the book or if I just can't wrap my head around something so simple.

When talking about the complexity of quicksort, the book says that the cost of partitioning, measured in the number of compares, is equal to N + 1, where N is equal to the number of elements in the collection to sort. We are assuming here that we just choose the first element in the collection to serve as the partition.

My question is would the cost of partitioning not really be equal to N - 1? That is, that you choose an element to serve as the partition and you compare it with every other element in the array.

--

As requested, the partitioning process is defined as follows:

The entry which will serve as partition is in its final place in the array.
No entries in positions before the partition are greater than the partition value.
No entries in positions after the partition are less than the partition value.

At this point I'm guessing it is in fact a typo...

--

The partitioning algorithm is outlined as follows

Take the leftmost array element as the "partitioning item"
Scan the array from the left until an element greater than or equal to the partitioning item is found
Scan from the right until an entry less than or equal to the partitioning item is found
When both a right and left item are found, exchange them
Repeat until the scan indexes cross
Once the scan indexes cross, exchange the partitioning item with the rightmost entry in the lower side of the array.

Note that the "cost" of the partitioning is being calculated in compares and not array accesses.


texts: Simple example for Higher Order Abstract Syntax (λ-tree syntax)

texts: I am reading https://www.cs.cmu.edu/~fp/papers/pldi88.pdf and https://en.wikipedia.org/wiki/Higher-order_abstract_syntax for trying to understand encoding of linear logic using HOAS into Coq. But I still cannot grasp whats going on? Is there simple concrete example available for using HOAS? E.g. exmaple in concrete syntax, example of abstract syntax and example of encoding in HOAS? Or maybe there is available good in-depth explanation of HOAS with multiple examples?


texts: CLRS: Asked to prove a result and then told to give a counter example

texts:
I am reading Introduction to Algorithms, and I am stuck at this execercise in the Appendix:

  Argue for any integers $n \ge 0$, $j \ge 0$, $k \ge 0$ and $j + k \le n$.

  $${n \choose j + k} \le {n \choose j} {n-j \choose k}$$

  Privde both an algebraic proof and an argument based on a method for
  choosing $j+ k$ items out of $n$. Give an example in which equality
  does not hold.

Here I am asked to prove it and then give a counter example. I can't seem to find any problem with the proof or the couter example, $n=4$, $j=k=1$. Puzzeled!

Here is a proof:

  First, let's establish that, $j!k!\le (j+k)!$. Both sides have the
  same number of terms, but the right side has $k$ terms more -
  $(j+1)(j+2)\ldots(j+k)$ - that are greeter than the corresponding
  terms on the left side $1\cdot2\cdot\ldots\cdot k$.

  Thus:

  $${n \choose j}{n-j \choose k}=\frac{n!}{j!(n-j)!}\frac{(n-j)!}{k!(n-j-k)!}=\frac{n!}{j!k!(n-j-k)!}\ge\frac{n!}{(j+k)!(n-j-k)!}={n \choose j+k}$$


texts: A question about the polynomial hierarchy

texts: Why does $\Pi_i^p \subseteq \Sigma_i^p$ imply $\Pi_i^p = \Sigma_i^p$?


texts:
I have a number $n$ and an integer $x$ which ends on $1, 3, 7 \ or\  9$, meaning that the last digit (rightmost digit) of $x$ is one of those 4 numbers.

Now if $z = x * y$, what number do I have to choose for $y$ such that the $n$ last (rightmost) digits of $z$ are equal to $1$ (I mean the numerical value of the rightmost $n$ digits of $z$ has to be $1$) while ignoring leading zeros.

Examples:

// computes y
long computeY(int n, long x) {
    // ...magic...
    return y;
}

computeY(1, 9) == 9 (because 9*9 = 81, take the n rightmost digits, result is 1)
computeY(1, 7) == 3 (because 7*3 = 21, take the n rightmost digits, result is 1)
computeY(2, 11) == 91 (because 11*91 = 1001, take the n rightmost digits, result is 1, ignore leading zeros)
computeY(3, 17) == 353 (because 353*17 = 6001, take the n rightmost digits, result is 1, ignore leading zeros)
computeY(5, 11327) == 23263 (because 11327*23263 = 263500001, take the n rightmost digits, result is 1, ignore leading zeros)

I encountered this problem during a programming contest at my school and am stuck, It looks like I have to use number theory but I just don't know where to start.


texts:
Given (n) , what is the Count of (x,y) pairs that satisfy the equation x^2+y^2 = n^2.
Is there any way I can re-write this code just without using nested loop?

int counter=0;
    int x=0;

    for (int i =(int) n-1; i>=0 ; i--){

        if(i == x)
            break;

        for (int j = 1; j< (int)n ; j++){

            if (Math.pow(i,2)+Math.pow(j,2) == Math.pow(n,2)){
                counter++;
                x = j;
            }
        }
    }
System.out.print(counter);


texts: What is the use of First() and Follow() in compiler design?

texts: I am completely aware of how to calculate first and follow, my professor has taught me that well , but he had not explained what is the need of First() and Follow(), so any explanation why we need them will help me very much.


texts: Conversion of left-recursive context-free grammars to strongly equivalent ones without left-recursion

texts:
It is a well-known problem that many top-down parsers have problems parsing a context-free grammar with left recursive rules. There exist algorithms to convert grammars with direct or indirect left-recursive rules to equivalent grammars that don't have such rules.

For example, a simple left-recursive grammar

$$\begin{alignat}{2}
  &E &&\to E \ \text{'-'}\ V \ \vert \ V\\
  &V &&\to \text{'a'} \ \vert\ \text{'b'}
\end{alignat}
$$
can be converted to an equivalent right-recursive one
$$\begin{alignat}{2}
  &E  &&\to V \ E'\\
  &E' &&\to \text{'-'}\ V \ E' \ \vert \ \varepsilon\\
  &V  &&\to \text{'a'} \ \vert\ \text{'b'}
\end{alignat}
$$
that accepts the same language.

The problem with that conversion in that the parse trees for the same input string look fundamentally different. In the first case the result is a left-leaning tree, reflecting the left-associativity of the subtraction operator. On the other hand, the parse tree for the second grammar would yield a right-leaning tree, which makes it harder to process or evaluate the built parse tree.

In terms of equivalence, this conversion yields a non-left-recursive grammar that is weakly equivalent to the original one, i.e. accepting the same language, but not strongly equivalent. The latter also requires structurally equivalent parse trees.

For every left-recursive context-free grammar, does there exist a non-left-recursive, strongly equivalent version that describes the same language? If so, how would an algortihm look like that performs such a conversion?


texts:
Let's say I have a list of "Items"

I also have a list of "Bags". Each bag is a set of "Items" which gives what item can be placed in that bag. But only one item can go in each bag.

I want to place all items in a bag. It's okay if there are empty bags left over.

Does this sort of problem have a name and a solution other than a naive depth first search (a link in the direction of such an approach will be fine)?


texts: Unbounded-time programs in lambda calculus?

texts:
The Turing machine model has been extended to “infinitary turing machines”, which are Turing machines that can perform a countably and uncountably infinite amount of computations in finite time.

Is there a similar model for the lambda calculus that is computationally equivalent to the infinite Turing machine? (I.e. that is “infinitarily turing complete”?).

I’ve seen some papers on infinitary lambda calculus, but I’m not sure if the concept is computationally equivalent to infinite turing machines.


texts: Is greedy minimax permutation rejecting sorting optimal?

texts:
I sketch an impractical, theoretical comparison sort.

Initialize a list of all $n!$ permutations of size $n$.
For each possible pair of indices $i, j$, count how many permutations would get rejected if we were to find out that $a_i < a_j$ or $a_i \nless a_j$ and choose the minimal of these two counts. Finally choose the pair of indices with the maximal minimum amount of rejections.
For this pair of indices, actually perform the comparison, and remove those permutations from the list that are in conflict with this comparison.
Stop if one permutation remains in the list, otherwise go to 2.

Assuming the input array is selected uniformly from all possible permutations, is this algorithm optimal in comparison count on average?

It's fairly easy to see that the algorithm acquires the most information possible in a single comparison at every comparison. But I have no clue whether this greedy strategy would result in optimal or suboptimal behavior for the entire task.


texts: Can a type system serve as a proof assistant for foreign functions?

texts:
Given that:

A language with very expressive type systems (e.g. Idris) can also have escape mechanisms like foreign function interfaces/unsafePerformIO.
There are proof assistants that can be used to prove some properties of a program written in a language that doesn't have a type system capable of expressing those properties.
The Curry–Howard correspondence shows that a successfully type-checked implementation of a function with a given type is proof of what is expressed by that type.

Can one express non-trivial proofs of some property of foreign language code in the type system of the native language?

For example, pretend I have a C function called stable_qsort that sorts numbers in a terribly clever and efficient way while maintaining the order of already equal elements, and an Idris program that calls stable_qsort via its FFI, but I don't trust this relatively obscure C function. Could I prove that the function doesn't reorder equal elements, for all inputs, in my Idris code instead of using a separate proof assistant?


texts: How do I optimize a set of sub-lists which can combine to recreate higher level lists?

texts:
I am writing a function which XORs 32 boolean variables to produce a 32 bit output. To this end I have 32 lists of boolean variables (the lists have between 12 and 17 elements). Every variable in list 0 can be XOR'd together to produce bit 0 of the output. Every variable in list 1 can be XOR'd to produce bit 1 of the output etc.

There are common variables between lists and I would like to find the optimum selection of sub-lists which combine the variables to reduce the total number of XORs. The hierarchy is limited to 2 deep so we can only have one layer of sub-lists.

Here is an example problem:

out_0: i_1, i_2, i_3, i_4, i_5, i_6
out_1: i_2, i_4, i_5, i_6, i_7, i_8
out_2: i_1, i_4, i_5, i_6, i_9

The simple solution just XORs every variable in each list. This solution requires 14 XORs:

out_0 = i_1 ⊕ i_2 ⊕ i_3 ⊕ i_4 ⊕ i_5 ⊕ i_6
out_1 = i_2 ⊕ i_4 ⊕ i_5 ⊕ i_6 ⊕ i_7 ⊕ i_8
out_2 = i_1 ⊕ i_4 ⊕ i_5 ⊕ i_6 ⊕ i_9

The associative property of the XOR function means we can improve on the simple solution by forming sub-lists which are included in the top level lists as required. This solution requires 11 XORs:

x_0 = i_1 ⊕ i_6
x_1 = i_4 ⊕ i_5

out_0 = x_0 ⊕ x_1 ⊕ i_2 ⊕ i_3
out_1 = x_1 ⊕ i_2 ⊕ i_6 ⊕ i_7 ⊕ i_8
out_2 = x_0 ⊕ x_1 ⊕ i_9

This is an improvement but there are other sub-lists which may result in fewer XORs. I would like a method of determining the optimum choice of sub-lists.

It is also worth noting that when an input is XOR'd with itself it cancels. Therefore we can add redundant terms to maximize the utility of a sub-list. The following solution which requires 10 XORs would work:

x_3 = i_1 ⊕ i_2 ⊕ i_4 ⊕ i_5 ⊕ i_6

out_0 = x_3 ⊕ i_3
out_1 = x_3 ⊕ i_1 ⊕ i_7 ⊕ i_8  [i_1 included to cancel the i_1 inside x_3]
out_2 = x_3 ⊕ i_2 ⊕ i_9        [i_2 included to cancel the i_2 inside x_3]

I have run a simple greedy optimization which always selects the group which provides the greatest reduction in the number of XORs. For my system (a parallel CRC32 implementation) this optimization reduces the number of XORs by 37%. My optimization does not add redundant terms. Is there a better optimization I can run to find the global optimum?


texts: Why don't RDBMS use a quorum based solution to do failover

texts:
For RDBMS viz. MySql, PostgreSql a common solution for scalability and high availability is to run a primary instance as master that is a read-write instance and one or more read replicas. If the master fails, a failover happens and one of the read replicas become the master. The problem happens, when a network partition separates the master from the replicas. The clients keep writing to the master and the failover also happens resulting in two masters. One recommended solution for avoiding such split brain situation is to kill the old master. I think this is still acheivable. If we run some local agents in each server node forming a quorum (maybe using Zookeeper), we can kill the leader that cannot reach the majority.

But I think the most difficult part is that when the server wakes up, it seems it still believes that it is the master.

If we look at all the other open source projects, almost everyone uses Zookeeper which seems pretty safe when it comes to preventing a split-brain situation.

Systems that don't use Zookeeper, uses some other quorum based solutions. For e.g. Redis. If it runs in stand alone mode, it uses Sentinel to form the quorum. If it runs in cluster mode, it uses all the masters to form the quorum.

My question is, why MySql and PostgreSql are not implementing a similar solution. Is there any technical constraint for RDBMS in general? Is there any future plan?


texts: How is the concurrent tracking of "state position" in NFA's typically modelled?

texts:
Conceptually, to track the multitude of "state positions" arising in an NFA while it is processing a given input string, a quantitative notion of memory/cache/storage is required per "fork" of execution over the automaton, for keeping track of the states where the computation is currently "at".

What is the typical theoretical treatment, regarding the complexity of this degree of concurrency?!


texts: How would you prove a family of functions is universal?

texts:
A set of functions from a universe U of keys to n buckets is universal if for every pair of keys in U, say x and y, such that x != y, the probability of h(x) = h(y) is less than or equal to 1/n, for a random function h in the set of functions.

Say you're given a prime number p, and a random integer n, such that p is greater than or equal to n. Say we want to look at the family of functions where we pick a random integer i, and define each function hi = ((i * x) mod p) mod n. The input can be any integer from 0 to p-1, and the the output can be any integer from 0 to n - 1.

How would you prove that this family of functions is universal. Or similarly, if you pick an arbitrary p and n, how would you come up with a counter example?


texts:
Apologies for this simple question. I found it in the book Algorithms by Sedgewick and Wayne.

Give a formula to predict the running time of a program for a problem of size N when doubling experiments have shown that the doubling factor is $2^b$ and the running time for problems of size N0 is T.

$$ \frac{T(2N)}{T(N)}=2^b.$$

$$ T(N_0)=T. $$

I am not sure how to proceed after that.


texts: Prove that a DFA will transition to the same state after $\gcd(i,j)$ steps where $i$ and $j$ steps can be taken to reach that state

texts:
Suppose $M=(Q,\Sigma,\delta,q_0,F)$ is a deterministic finite automaton, and suppose there exists a state $q \in Q$, a string $z \in \Sigma$, and integers $i,j>0$ such that $\delta(q,z^i)=\delta(q,z^j)=q$. Prove that $\delta(q,z^{gcd(i,j)})=q$

I can intuitively say that starting from a state $q$ if you take $x$ steps on a DFA to reach the same state and at the same time $y$ steps also takes the DFA to the same state, then there exists a cycle that is repeated $\gcd(x,y)$ times to reach the same state again and again. Is this correct for a DFA? How can I prove this formally?


texts: Distinct variables for different clauses

texts:
In resolution theorem proving, it is normally assumed variables in different clauses are distinct. This is not something that happens automatically; it requires significant extra code and computation to implement. Given that, I'm looking for a test case for it.

The problem is, in all the test cases I've tried so far, it makes no difference. Presumably it matters only in unusual edge cases. As Wikipedia puts it, "variables in different clauses are distinct... Now, unifying Q(X) in the first clause with Q(Y) in the second clause means that X and Y become the same variable anyway."

Are there any known test cases that will actually give the wrong answer if different clauses use the same variables?


texts:
I have a friend working in wireless communications research. He told me that we can transmit more than one symbol in a given slot using one frequency (of course we can decode them at the receiver).

The technique as he said uses a new modulation scheme. Therefore if one transmitting node transmits to one receiving node over a wireless channel and using one antenna at each node, the technique can transmit two symbols at one slot over one frequency.

I am not asking about this technique and I do not know whether it is correct or not but I want to know if one can do this or not? Is this even possible? Can the Shannon limit be broken? Can we prove the impossibility of such technique mathematically?

Other thing I want to know, if this technique is correct what are the consequences? For example what would such technique imply for the famous open problem of the interference channel?

Any suggestions please? Any reference is appreciated.


texts: Finite state automata, multiple completion states?

texts:
I'm currently studying for an exam for a course where some of the material covered included finite state automata, I've completed a question and I'm not sure about my answer.

Exercise

Explain what is meant by a Finite State Automaton (FSA) by drawing an FSA to recognise strings of the form $a^rb^s$, where $r\gt0$ and $s\ge0$ and with an alphabet of $\{a,b\}$, i.e., there must be at least one $a$, zero or more $b$'s and all occurrences of $a$ must precede any occurrence of $b$. Illustrate, how your FSA works given the following sample strings:
$\quad$(i) $abbb$
$\quad$(ii) $aaaa$
$\quad$(iii) $aba$

My Answer

Are multiple completion states allowed?


texts: Build all valid parenthesis in polynomial time

texts:
Given some binary operator $\otimes : X\times X\to X,$ and list $x_1,\dots,x_n$ where $x_i\in X,$ can all possible expressions in $\otimes$ be computed within a number of operator applications polynomial in $n$?

We say an expression in an operator $\otimes$ and list $x_i$ is formed by placing $\otimes$ between all $x_i$ in order with some choice of parentheses. For example given the list $x,y,z,$ valid expressions are $(x\otimes y)\otimes z$ and $x\otimes (y\otimes z)$. Alternatively, an expression in $x$ is precisely $x$ and an expression in $x_1,\dots,x_n$ is an expression in $x_1,\dots,x_{k-1},x_k\otimes x_{k+1},x_{k+2},\dots,x_n$ for some $1\le k < n.$

We assume that there are no more than polynomially bounded amount of setting the parenthesis (because its given in the assignment) and thus it has to run in polynomial time.

I'm doubting my solution so far, here it goes:

We define two working sets

$ result = \{ \}$

$ vars = \{\}$

Every single input variable is a valid expressions if it is paired with another valid expression ( since our operand is two-valued), and we add them to the vars set.

Now iterate through lengths $ 2, \_,n$ and build all valid expressions like so:

For length $2$ we build all valid strings like so: $w_1 = (x_0 \circ x_1) , w_2 =(x_1 \circ x_2) \ldots $ and add them to the $vars$ set.

For length $>3$ we greedily iterate through the biggest available chunks in the $vars$ set and try to fill up the voids with items from our vars set until we reach length 3.

Once we reach length $n$ we add all generated expressions to the $res$ set and return.

One thing I'm stuck on right now is the complexity analysis, one iteration of the subexpression generation takes $n^2$ steps at most, when we reach length $n$ we get $n^3$ complexity (much like CYK, which is very similar to this algorithm).

But something feels fishy, I feel like I've made a mistake somewhere, can someone point me in the right direction ?

This is an assignment so full answers are discouraged, please give hints, once I get the grading of the answer I'll post it here for the afterworld to admire.


texts: Converting Boolean circuit to Boolean formula in parallel

texts:
Let t be a fixed constant. I would like to convert a Boolean circuit C of depth t on n inputs over AND, OR and NOT gates (of fan-in 2, say) to an equivalent Boolean formula F on the same n inputs, in the sense that for each input vector x of length n, we have C(x) = 1 if and only if F(x) = 1. Some restrictions on the problem: the circuit has size m and depth t, and I would like the function mapping C to F to be computable by a PRAM (say) using a number of processors polynomial in m and time polylogarithmic in m. I don't mind that the size of the resulting formula is O(mt), I consider t to be a constant.

The approach I envision is to enumerate each path of length t from the output gate to each input gate and transform that set of paths into a trie. This trie will then be a tree of branching factor m and depth t representing a Boolean formula of size O(mt), observing that this is a polynomial in m if I consider t to be a fixed constant. My problem then reduces to the problem of constructing a trie from a set of at most mt strings, each one a string of length at most t over an alphabet of cardinality m.

Can I construct a trie of strings of length t over an alphabet of size m in parallel time polylogarithmic in m? More generally, can I convert a Boolean circuit of size m and depth t to a Boolean formula in parallel time polylogarithmic in m?


texts: Can Yacc be used to generate three address code for Java 1?

texts: I have read that yacc generates bottom up parser for LALR(1) grammars. I have a grammar for Java 1 that  can be used for generating three address code and is strictly LALR(1), but the translation scheme I am employing makes it L-attributed. Now I have read that L-attributed LR grammars cannot be parsed by using bottom up parsing. So, can yacc be used here or not?