# Question
Title: How can a distributed system cooperate to determine rules of its environment?
I'm sorry if this question is silly or elementary. I'm not a computer scientist so I don't know the vocabulary to use to ask this question. Thus I've produced an analogy to explain the challenges I'm facing in my program. Please do point me in the right direction, I don't know what I need to learn to solve this problem:

An Analogous Puzzle:

Assume you are given a new house with 4 rooms. But this house is very strange; each room has 1-3 lights in it and 1-3 light switches. Some diabolical electrician has wired the house very strangely so that the switches can control lights in other rooms of the house. Furthermore, the behavior of the lights and switches may depend which lights are on at the time.

For instance a switch in room 1 may turn on on a light in room 2 if a light in room 4 is off, but it won't if room 4 is lit up. Almost all the light switches have a very strange relationship to some of or all of the other lights in this way. But they're not random, in their behavior: given the same state of the house a light switch will have the same effect as it did.

Now imagine you and 3 friends each occupy a room and are able to do one action in the house at a time. You can talk to each other by calling or texting each other on your cell phones, but every minute costs money, or every text costs money so you want to communicate as little as possible (thus you want to be efficient).

What I need to figure out is the answer to the following question:

How do you and your 3 friends need to communicate (what information do you need to share with each other) in order for the 4 of you to work together to deduce the wiring rules that govern the lights?

Does each person need to know the state of each room? Or do they only need to know the state of each room when something unexpected happens? How do they deduce the rules that govern the lights?

I need to find a universal way for the agents to infer the rules underlying the system efficiently. That's basically it.

In a more complicated scenario (thousands or millions of rooms), does anything change? What do I need to learn to solve this puzzle in a way that scales?

One other consideration: if necessary for a scalable algorithm you can recruit other friends from outside the house and give them information. I'm not sure why you would need to, but that's also a possibility.

That is the puzzle I have: many agents, mainly identical and independent are interacting with the same system.

**I need to find an algorithm of cooperation/communication that results in the system as a whole, or each individual agent to infer/deduce (or even just behave in accordance with) the underly rules of the environment.**

# Answer
> 2 votes
This is a non-mathematical riddle, so part of the solution is determining the rules of the game. The computer science way of solving this, however, would be to use a Gray code and a synchronized system. The idea is as follows. Suppose that there were only 3 switches. You will go over their states in the following order: $$ 000\\001\\011\\010\\110\\111\\101\\100 $$ (Here 0 is the original state of the switch, and 1 is the other state of the switch.) Decide on a reasonable time interval $t$. There will be 8 rounds (or, in general, $2^k$ rounds if there are $k$ switches), each taking $t$ units of time. Each round other than the first begins with the appropriate person changing one of the switches (the appropriate person can be determined in advance once we know how many switches are in each room). Then they all record the "output" that they see in their room. When this process ends, they can compare notes and reconstruct the entire function.

This strategy is optimal with respect to the number of switch flips. While it takes $2^k$ rounds for $k$ switches, you can't really do any better since the function converting the input (switches) to the output (lights) is completely arbitrary. This does mean that it doesn't scale at all. If you want a strategy that does scale, you'll have to adjust the problem by restricting the set of possible functions (switch–light correspondences).

---
Tags: finite-automata, machine-learning, distributed-systems, bayesian-statistics
---


# Question
Title: Solution to a Np-hard problem and its relevance to a dual LP
From The design of APX algorithms book by *David P. Williamson* and *David B. Shmoys*, at the bottom of page 21 I saw the following statement (it is about the set cover LP and its dual):

> Let $y^\*$ be an optimal solution to the following dual LP $$max \sum\_{i=1}^n{y\_i}$$$$subject \sum\_{i:e\_i\in{S\_j}}{y\_i \leq w\_j}, y\_i \geq0; j=1,...,m;i=1,...,n$$ and consider the solution in which we choose all subsets for which the corresponding dual inequality is *tight*; that is, the inequality is met with equality for subset $S\_j$, and $\sum\_{i:e\_i \in{S\_j}}{y^\* = w\_j}$. Let $I^{'}$ denote the indices of the subsets in this solution. We will prove that this algorithm also is an $f$-approximation algorithm for the set cover problem

I would like to know what does the writer mean by *corresponding dual inequality*? Is there any correspondence between a solution of the *Set Cover* problem and a dual LP solution?

I can't understand what does the paragraph mean.

Thanks in advance.

# Answer
Any linear program has a dual linear program, whose constraints are in one-to-one correspondence with the variables of the primal program. Under mild conditions, the optimal value of the dual program coincides with the optimal value of the primal program, and certain conditions known as *complementary slackness* are satisfied by any pair of optimal solutions.

In this case, however, we are already looking at the dual linear program; the constraints here correspond to subsets. In detail, the constraint $\sum\_{i\colon e\_i \in S\_j} y\_i \leq w\_j$ corresponds to the subset $S\_j$.

What is the relation to Set Cover? There is a natural linear program which is a relaxation of a natural integer programming formulation of Set Cover. If you compute its dual, you get the linear program that you quote. (If you're not sure which primal linear program was used to generate this dual linear program, you can always compute the dual of the dual linear program to get back the primal linear program.)
> 3 votes

---
Tags: algorithms, approximation, linear-programming, set-cover
---


# Question
Title: What category of AI would a 2048 bot be considered?
I have just delved into the realm of AI and from what I can tell its a very vast field of study. I am a game programmer, so AI in games is particularly interesting to me. My question is, what type of AI would a bot that can beat 2048 fall under?

I learned the basics of machine learning, but I wasn't sure if this is how you could apply machine learning. I want to know what category this falls under so I know what to research and learn to make my own bot. Also, if you don't know what 2048 is, check it out here.

# Answer
I would initially say that you can classify 2048 as a MDP problem.

For this reason, I would consider looking at Reinforcement Learning (an area of Machine Learning).

Another option, however, more specific would be to look at the performance of Monte Carlo Tree Search.

There is a great discussion in StackOverflow about 2048 different approaches have been tried: https://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048
> 2 votes

---
Tags: machine-learning, artificial-intelligence
---


# Question
Title: Estimating the number of distinct elements
Need to understand "intuition" part. It does not make sense to me why $log(d)$ is a good approximation.

> We have a stream $\sigma = \\{a\_1, ..., a\_n\\}$, with each $n \in \[n\]$, and this implicitly defines a frequency vector $F = {f\_1, ..., f\_n}$. Let $d = |\\{j : f\_j \> 0$}| be the number of distinct elements that appear in $\sigma$.
>
> For an integer $p \> 0$, let $zeros(p)$ denote the number of zeros that the binary representation of $p$ ends with. Formally,
>
> $zeros(p) = max\\{i : 2^{i}$ divides $p\\}$
>
> Algorithm:
>
> Initialize:
>
> 1. Choose a random hash function $h$: $\[n\] \mapsto \[n\]$ from a 2-universal family;
> 2. z $\leftarrow $ 0;
>
> Process $j$: 3. if $zeros(h(j)) \> z$ then $z \leftarrow zeros(h(j))$
>
> Output: $2^{z+\frac{1}{2}}$
>
> The basic intuition here is that we expect $1$ out of $d$ distinct tokens to hit $zeros(h(j)) \geq log(d)$, and we don't expect any tokens to hit $zeros(h(j)) \>\> log(d)$. Thus the max value of $zeros(h(j))$ over the stream - which is what we maintain in $z$ \- should give us a good approximation to $log(d)$.

# Answer
The idea is that the hash function $h$ maps elements to random elements. Now think about the likelihood that the last $k$ digits of a random number are $0$. There's a 50/50 chance that the number ends with $0$, but it becomes more and more unlikely as you increase the number of zeroes at the end. For $000$, the probability is already down to $\frac{1}{8}$, and for ten zeroes it's around one in one thousand. So it's very unlikely that any one random number has a lot of zeroes at the end.

So what's the maximum number of zeroes can you expect when you take $d$ random numbers? It's unlikely that one of the $d$ numbers ends in loads of zeroes, but the probabilities are so that it's likely that at least one has $\log{d}$ zeroes.

If you do this with one hash function, that's a pretty rough estimator, but due to the so-called *median trick* you can do it a couple of times with different hash functions, use the median of the outputs, and the certainty of the result increases exponentially in the number of different hash functions (they have to be independent).
> 2 votes

---
Tags: algorithms, lower-bounds
---


# Question
Title: Non-regularity of the set of primes in unary encoding using Myhill-Nerode
I have found many proofs for this using pumping lemma, I'm curious of how to proof it via Myhill-Nerode theorem.

Suppose $L= \\{a^p \mid p \text{ is prime}\\}$ is regular. Then we have congruence such $u ∼ v ⇒ uw ∼ vw$ of finite index $k$, so it has $k$ equivalence classes. $L$ is union of some of its equivalence classes.

Let's choose $aa,aaa,...,a^{p\_k},a^{p\_{k+1}}$, where $p\_k$ is $k$-th prime. Then, there exists $i,j$ from $\\{1,...,k+1\\}$, that $a^i∼a^j$. Now we should concatenate some word to $a^i$ and $a^j$, that one of the words is in $L$, while the other is not, but in contradiction, they are in the same equivalence class.

Any ideas?

# Answer
We can prove that every string in $L$, $a^p$, $p$ is prime, is in its own different equivalence class. We simply cannot have two strings, $a^p$ and $a^{p'}$, both $p$ and $p'$ prime, in same equivalence class.

Assume $a^p$ and $a^q$, $q\>p$, $p$ and $q$ prime, are in same equivalence class. Then since $a^{p}a^{q-p}=a^q$ is in $L$ therefore $a^qa^{q-p}=a^{2q-p}$ will be in $L$. Since $a^{p}a^{2q-2p}=a^{2q-p}$ is in $L$ therefore $a^qa^{2q-2p}=a^{3q-2p}$ will be in $L$. We will be able to show that $a^{p+i(q-p)}$ will be in $L$ for every $i \geq 0 $. But for $i=p$ there is a contradiction.

Factually speaking even $a^c$ and $a^d$ for composites $c$ and $d$ will be in different equivalence classes. If we assume $a^c$ and $a^d$, $d \> c$, where $c$ and $d$ are not primes, are in same equivalence class, then we can similarly reach a contradiction. Even if we don't prove this, the number of equivalence classes is still infinite because each $a^p$ for prime $p$ is in different equivalence class.

Thus as number of equivalence classes for $L$ is infinite (because number of primes is infinite), therefore by Myhill-Nerode theorem $L$ is not a regular language.
> 6 votes

---
Tags: formal-languages, regular-languages
---


# Question
Title: What's the fastest known algorithm for generating $k$-subsets of an $n$-set?
We are given a set of $n$ elements and we'd like to generate all $k$-subsets of this set. For example, if $S=\\{1,2,3\\}$ and $k=2$, then the answer would be $\\{1,2\\}, \\{1,3\\}, \\{2,3\\}$ (order not important).

There are $\binom{n}{k}$ $k$-subsets of an $n$-set (by definition :-), which is $O(n^k)$ (although this is not tight). Obviously any algorithm for the problem will have to run in time $\Omega(\binom{n}{k})$.

What is the currently fastest known algorithm for this problem? Can the lower bound of $\binom{n}{k}$ actually be achieved (so that we have an essentially optimal algorithm)?

(Note: I reposted this from StackOverflow as the question seems better suited for CS StackExchange.)

# Answer
> 4 votes
Knuth's Algorithm R Revolving-Door combinations is generally accepted as the current best for algorithms and time complexity for generating combinations.

---
Tags: algorithms, combinatorics
---


# Question
Title: Is there anything that MUST be done on a multi-core CPU?
When considering how multi-thread-friendly our program must be, my team puzzled about whether there's anything that *absolutely cannot be done* on a single-core CPU. I posited that graphics processing requires massively parallel processing, but they argue that things like DOOM were done on single-core CPUs without GPUs.

**Is there anything that *must* be done on a multi-core processor?**

Assume there is infinite time for both development and running.

# Answer
> 48 votes
If you don't care about the running time, anything you can do on a multi-core machine, you can do on a single-core machine. A multi-core machine is just a way of speeding up some kinds of computations.

If you can solve a problem in time $T$ on a multi-core machine with $n$ cores, then you can solve it time $\sim Tn$ (or less look at Amdahl's law) on a single-core machine. The single-core machine can emulate a multi-core machine using time-slicing / time-sharing.

# Answer
> 58 votes
The question is: under what constraints?

There are certainly problems where, if we ask the question "can we solve this problem on hardware X in the given amount of time", the answer will be no.

But this is not a "future-proof" answer: things which in the past could not be done fast enough in a single core probably can be now, and we can't predict what future hardware will be capable of.

In terms of computability, we know that a single-tape Turing Machine is capable of computing all the same functions as a single or multi-core computer, so, runtime aside, there are no problems that a multi-core computer can solve that a single-core can't.

In terms of something like graphics, literally everything that is on the GPU *could* be done on the CPU... if you are willing to wait long enough.

# Answer
> 17 votes
As other answers have pointed out, a single CPU can always emulate multiple CPUs by slicing time and playing the role of each virtual CPU. This emulation will certainly calculate the correct answers.

In the real world, execution time may be important. It could mean the difference between a mediocre frame rate and a stellar visual experience. Or the difference between profit and loss in trading.

One pathological situation where a multiprocessor is *vastly* faster than a uniprocessor is where the processing is a data pipeline, context switching is expensive, and the machine code for each pipeline stage just barely fits in a CPU's cache.

Let me illustrate with some numbers. Suppose you have a data pipeline (3D rendering, etc.) that has 4 processing stages, each stage has 256 KiB of program code, and you conveniently have 4 CPUs with 256 KiB of L2 cache. If you try to run this processing on a single CPU, then switching between the 4 tasks will be expensive and involve heavy cache misses. On the other hand if you run it on a 4-core system, the calculation could potentially be very smooth, cache misses are minimal, and context switches are non-existent. (As a side note, this is related to the notion of pinning certain applications to certain cores - e.g. only doing OS kernel operations in one core, or TCP/IP handling, etc.)

# Answer
> 8 votes
It's much harder to develop really nefarious data races with a single CPU. I mean, sure, you can pull off tearing between words if you interrupt a single CPU, but can you build exotic scenarios where there is no single interleaving of threads which does what you want?

Okay, maybe making insidious bugs doesn't count as a valid use of multi-code advancements. As it turns out, there's not much that mutli-core can do that single core cannot given time. The reason is simple. If you try to avoid those evil data races, you have to have synchronization points in your code. If you model your code as a lattice of computations where ones inputs must be complete and synchronized before you can calculate and produce outputs, it's easy to see that a single CPU can simply work their way along the lattice, calculating the next available block of work.

In fact, if you can demonstrate that your algorithm can be solved by a Turing machine (which is virtually every algorithm we care about), it can be proven that the algorithm can be done by not only a single core CPU, but in fact a state machine with a very long piece of tape for memory!

The CHESS race detector actually leverages this to find race cases. It runs everything singlethreaded and systematically explores all possible interleaves between threads, trying to find cases where a test fails because of a race case. CHESS *depends* on the fact that you can run any multithreaded application on a single core.

The cases where you *need* multicore appear when you start stretching the limits of hardware. The obvious one is when you have time constraints. Some problems with realtime time constraints are impossible to do single core because they simply can't drive a single core's clock fast enough. There's a reason CPUs climbed up to 4Ghz and then settled down a bit, preferring more cores at lower speeds.

A more exotic version of this timing constraint is in hard-real time systems. In some hard real time systems, the service of interrupts is so demanding that you actually have to pick a multi-core CPU that lets you divvy the interrupts up across the cores, or you run into timing limitations.

Another limit arises with data busses. Consider the Blue Gene/P as an example. JUGENE, a particular Blue Gene/P supercomputer, has 144 **terabytes** of memory. They simply don't make single CPU computers that can access all of that memory.

# Answer
> 6 votes
If you need to observe a process running on a single processing element without disturbing its real-time behavior (or as little as possible), like for benchmarking or activity logging, you'll probably need a separate processing resource.

# Answer
> 4 votes
The other answers adhere to the limited view of parallelism as "distributed concurrency". This gives some answers: in a clean model of computation à la Turing, multiple cores do not offer an advantage; the only advantage you may get is efficiency.

There is *the* one thing multiple processing units (PUs) can do that a single one can not, though: execute operations *in parallel*, that is *at the same time*.

That is very useful if you run multiple programs at the same time. Granted, it is only rarely that you absolutely need more than concurrent execution, and most uses come down to increased efficiency. But there *is* this difference.

Say you need to **process data sensor data** from multiple sources in real time. Whatever that means precisely in your application, one PU can only handle so many input streams concurrently without violating its response time limit. So you *need* multiple PUs once you have too many sensors for your current PU generation.

In the more classical realm, one maybe convincing example are **portfolio algorithms**. Say you have a problem for which you have multiple (say $k$) algorithms with orthogonal costs; good cases of one are bad cases for others. You can not quickly tell which one is best for a given input, though.

You can run *all* algorithms in parallel and abort once one finishes. If you have at least $k$ PUs, you get the *minimum* running time among all $k$ algorithms in the portfolio. With only one PU, you'd get $k$ times that, assuming a fair scheduler, plus all the overhead.

# Answer
> 0 votes
from a CS pov, "multicore" is not that much different in theory than "distributed computing". the basic concept is "independent computing elements (that compute in parallel". so slightly rephrasing the question ("multicore" is not really exactly a theoretical concept in CS) leads to some other possibilities. as pointed out in other answers, sequential programming is equivalent to parallel programming from a CS pov. this goes back to the definition of the theoretical system for computing, namely a Turing machine. theoretical analysis of CS performance is ultimately in terms of TMs where the distinction of parallel vs sequential does not really apply (although there is some rough analogy with *multitape TMs*).

but considering this question less abstractly, distributed computing is indeed *superior* or possibly nearly even *required* for some problems involving *fault tolerance*. in this area there is a concept that it applies when/ where the independent computing elements are taken to have some degree of *unreliability* (this is not really a universally applicable assumption for all contexts). here are several cases where fault tolerance is *improved* with or even *requires* independent computing elements.

* consider that each processor has an independent "\[x\]%" chance of failing during computation. a system can be devised whereby through communication the overall fault tolerance of the system is superior to individual components. this was applied many decades ago eg in Space Shuttle systems. more recently there are basic protocols designed to utilize it eg Paxos which solve the so-called consensus problem. a more down-to-earth example is Google which has a lot of proprietary algorithms to essentially build their supercomputer(s) out of individually unreliable elements coupled with fault-tolerant algorithms.
* Bitcoin involves distributed transactions to compute the ledger and that is not merely due to sheer processing load issues. the algorithm is carefully designed to thwart corrupt nodes. in short it "solves"/ implements the Byzantine generals problem which is not merely about maximizing parallel performance, it involves independent entities "checking" each other and "algorithmically/ cryptographically/ securely" rejecting invalid computations aka a sort of "cheating" or "corruption".
* a classic analysis of parallelism concludes there are about 7 "fundamental" problem pattern types that decompose into particular parallel execution breakdowns. see The Landscape of Parallel Computing Research: A View from Berkeley
* there is some element of an open theoretical question here wrt performance considerations addressed in most other answers. the question of whether there are any problems that are "inherently faster" in parallel than sequential is also known roughly as the P=?NC problem where NC is considered the class of "efficiently parallelizable" algorithms and  is "efficient \[sequential\] algorithms"

---
Tags: computation-models, cpu, multi-tasking
---


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

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

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

---
Tags: algorithms, complexity-theory
---


# Question
Title: A certain submatrix of the correlation polytope
I am kind of confused by the argument at the top of page 5 here, http://homes.cs.washington.edu/~jrl/notes/bonn-lecture-notes.pdf

* Firstly given that the author wanted to look at quadratic multilinear functions on $\\{0,1\\}^n$ why is he finding it enough to look at functions of the form, $f(x) = a\_0 + \sum\_{i,j} A\_{ij}(xx^T)\_{ij}$ for some real symmetric matrix $A$ and a real number $a\_0$?

These $f$s won't have any linear term and doesn't that mean a loss of generality?
* The author defines the set $QML\_n^+$ as the set of functions of the above type which are non-negative on the Boolean hypercube. Isn't this set an uncountably infinite set?

Because I don't understand how the author now hopes to define a matrix $M\_n$ whose rows seem indexes by $f \in QML\_n^+$ and the columns seem indexed by $x \in \\{0,1\\}^n$ and the entries are $M\_n(f,x) = f(x)$.

How does this make sense as a matrix (of finite dimensions!)?
* Given everything above how is it obvious that this matrix $M\_n$ is a submatrix of some slack matrix of the correlation polytope $conv(\\{ xx^T \vert x \in\\{0,1\\}^n \\})$ ?

# Answer
Every quadratic multilinear polynomial can be written as $$ a\_0 + \sum\_i a\_{ii} x\_i + \sum\_{i \neq j} a\_{ij} x\_i x\_j = a\_0 + \sum\_i a\_{ii} x\_i^2 + \sum\_{i \neq j} a\_{ij} x\_i x\_j, $$ using the fact that $x\_i^2 = x\_i$ for every $x\_i \in \\{0,1\\}$. This clearly equals $a\_0 + \sum\_{ij} A\_{ij} x\_i x\_j$, which in turn is the same as what you wrote.

Regarding the matrix $M\_n$, it is indeed infinite. For the proof that it is a submatrix of some slack matrix of the correlation polytope, see Lemma 2.8 of these lecture notes by James Lee.

If you have any more questions on the Bonn lecture notes, I suggest looking in the cited lecture notes, which seem to be more thorough.
> 1 votes

---
Tags: complexity-theory, np-complete, optimization, np-hard, np
---


# Question
Title: primitive recursive functional equivalence
Given two primitive recursive functions is it decidable whether or not they are the same function? For example lets take sorting algorithms A, and B which are primitive recursive. While there are many algorithms for sorting they all describe the same relation. Given two primitive recursive implementations of A, and B, can they be proven to represent the same function? Please note that this question is not about unrestricted recursion, and as such not limited by the properties of Turing machines.

I know that if you have two functions that halt, and have a finite domain they can be proven to be the same function because you can simply try every possible input, and compare the output of each function. My confusion is when working with things working on say natural numbers because they are not finite.

If this is not decidable for the primitive recursive functions is it possible for weaker classes like say the elementary recursive functions. I also know that this IS possible for weaker things like finite state machines, and deterministic pushdown automata. Thanks.

# Answer
It is well known that equivalence is undecidable even for CFGs resp. PDAs (see even Wikipedia). This provides a proof that the same property is undecidable for every model of any superset of CFL (by a simple special case reduction).

Since solving the word problem for any given CFL is clearly primitive recursive (by virtue of your favorite parsing algorithm), this includes the set of primitive recursive functions/algorithms.
> 6 votes

# Answer
It is not decidable, by the relatively straightforward informal proof:

Given an arbitrary Turing machine $M$, you can define the following function $f\_M$:

$$ f\_M(n) = \cases{0 \mbox{ if $M$ does not halt in $\leq n$ steps on empty input}\\ 1\mbox{ otherwise}}$$

It's a fundamental fact of primitive recursion that $f\_M$ is, in fact, primitive recursive (it "simulates" $M$ for $n$ steps).

Now the statement $$ M \mbox{ does not halt on empty input}$$

is equivalent to

$$ \forall n,\ f\_M(n) = {\bf0}(n)$$ where $\bf 0$ is the function which always returns $0$. The language of functions which do not halt is undecidable, and so, the above equivalence of primitive recursive functions is undecidable for general $f\_M$.

It's not too hard to show that deciding equivalence of primitive recursive functions is in fact in $\Pi^0\_1$, that is to say exactly as hard as determining non-termination of Turing machines, or deciding arithmetic sentences with a single non-bounded universal quantifier (and possibly bounded $\forall$ and $\exists$).
> 5 votes

---
Tags: computability, decision-problem, primitive-recursion
---


title: Analysing a small recursive algorithm

text:
# Question
Title: Analysing a small recursive algorithm
I need to calculate the complexity of func5, depending on variables $n, m$.

func4 is a function whose complexity is $\Theta(n+m)$

```
void func5(int a[], int n, int m, int b[])
{
    if (n==0) { return; }
    *b = func4(a,n,m);
    func5(a+1,n-1,m,b+1);
}

```

I get an expression which looks like:

$$C\_1\*n + C\_2\*(nm+n^2) - C\_2(1+2+3+..n)$$

$C\_1$ is the operations done in each iteration of func5,
$C\_2$ is the operations done in each call to func4,
and the substraction comes since func4 is receiving each time a smaller $n$ by one.

The answer says that complexity is $\Theta(n\*m+n^2)$ but I don't understand how to find the constants leading to Big-Theta notation.

Thanks.

# Answer
> 1 votes
Since $1+2+\cdots+n = \frac{n(n+1)}{2}$, your expression is equal to $$ C\_1 n + C\_2 (nm+n^2) - C\_2 \frac{n^2+n}{2} = C\_2(nm+n^2/2) + (C\_1-C\_2/2)n. $$ This shows that for constant $m$ and large enough $n$, your expression is at least $(1/2-\epsilon)C\_2(nm+n^2)$ (for any $\epsilon \> 0$ and, if $C\_1 \geq C\_2/2$, even for $\epsilon = 0$), and at most $(1+\epsilon)C\_2(nm+n^2)$ (for any $\epsilon \> 0$ and, if $C\_1 \leq C\_2/2$, even for $\epsilon = 0$).

---
Tags: algorithm-analysis, asymptotics, runtime-analysis
---


# Question
Title: Switching between user-level and kernel-level threads
After reading difference between user-level threads and kernel-level threads ,now I am in doubt of context switching.Context switching is managed by OS when switching between processes/threads but google didn't clarify me when i asked it that in which case more number of switching will take place for these cases :

1). User-level thread switched to another user-level

2).kernel-level thread switched to another kernel-level

3). User-level thread switched to kernel-level

Anyone please make it clear

# Answer
> 1 votes
# Exceptional Control Flow

There is a process called *exceptional control flow* to deal with the problem of switching between kernel code and user code. Switching between user mode programs actually need the kernel code being executed between.

## Context Switching

When a user mode program times out, an external timer triggers an interrupt. Then the operating system kernel takes back the control, save all registers used by the program. Then schedule another program to run.

## Exceptions and Interrupts

There are some kinds of exceptional interrupts from outside, for instance user hit Ctrl-C or when you try to open a file (syscall), it will switch to kernel code. When the file is opened for you, the program will come back running. Another example is on modern virtual memory systems, if a memory requested is currently in a disk, not on memory, the system will interrupt the program by a page fault. Then the computer continue to run kernel code to fetch that portion of memory and come back to the program.

# Answer
> 1 votes
User level threads is usually meant to be threads managed in userspace. The context switching is done in userspace, by the threading library. There is just one (kernel level) thread running at a time in the application, even if there are several processors.

Kernel level threads, in contrast, means that the kernel is aware of the threads in the application, Context switching is in the kernel, more than ore thread can be active at the same time.

In the Linux case, some experiments where done a long while back, to measure performance of both models (and a hybrid model, combining both). Pure kernel threads won hands down.

---
Tags: operating-systems, process-scheduling, threads, os-kernel
---


title: Largest sum divisible by n

text:
# Question
Title: Largest sum divisible by n
I asked this question on StackOverflow, but I think here is a more appropriate place.

This is a problem from *Introduction to algorithms* course:

> You have an array $a$ with $n$ positive integers (the array doesn't need to be sorted or the elements unique). Suggest an $O(n)$ algorithm to find the largest sum of elements that is divisible by $n$.

*Example:* $a = \[6, 1, 13, 4, 9, 8, 25\], n = 7$. The answer is $56$ (with elements $6, 13, 4, 8, 25$)

It's relatively easy to find it in $O(n^2)$ using dynamic programming and storing largest sum with remainder $0, 1, 2,..., n - 1$.

Also, if we restrict attention to a contiguous sequence of elements, it's easy to find the optimal such sequence in $O(n)$ time, by storing partial sums modulo $n$: let $S\[i\]=a\[0\]+a\[1\]+\dots + a\[i\]$, for each remainder $r$ remember the largest index $j$ such that $S\[j\] \equiv r \pmod{n}$, and then for each $i$ you consider $S\[j\]-S\[i\]$ where $j$ is the index corresponding to $r=S\[i\] \bmod n$.

But is there a $O(n)$-time solution for the general case? Any suggestions will be appreciated! I consider this has something to deal with linear algebra but I'm not sure what exactly.

Alternatively, can this be done in $O(n \log n)$ time?

# Answer
> 4 votes
Here are a few random ideas:

* The dynamic-programming algorithm can be flipped to look for a smallest sum instead of a largest sum. You just end up looking for a sum congruent to the remainder of the sum of the entire array, instead of one congruent to zero. If we process the elements in increasing order, this sometimes allows the dynamic algorithm to terminate before processing the entire array.

The cost would be $O(n k)$ if we processed $k$ elements. There's *not* a lower bound of $\Omega(n \log n)$ on this algorithm because we don't have to sort all the elements. It only takes $O(n \log k)$ time to get the $k$ smallest elements.
* If we cared about the set with the larget size, instead of the set with the largest sum, we might be able to use fast-fourier-transform-based polynomial multiplication to solve the problem in $O(n (\log n)^2 (\log \log n))$ time. Similar to what's done in 3SUM when the domain range is limited. (Note: use repeated squaring to do a binary search, else you'll get $O(n k (\log n) (\log \log n))$ where $k$ is the number of omitted elements.)
* When $n$ is composite, and almost all remainders are a multiple of one of $n$'s factors, significant time might be saved by focusing on the remainders that aren't a multiple of that factor.
* When a remainder `r` is very common, or there are only a few remainders present, keeping track of 'next open slot if you start from here and keep advancing by `r`' information can save a lot of scanning-for-jumps-into-open-spots time.
* You can shave a log factor by only tracking reachability and using bit masks (in the flipped dynamic algorithm), then backtracking once you reach the target remainder.
* The dynamic programming algorithm is very amenable to being run in parallel. With a processor for each buffer slot you can get down to $O(n)$. Alternatively, by using $O(n^2)$ breadth, and divide and conquer aggregation instead of iterative aggregation, the circuit depth cost can get all the way down to $O(\log^2 n)$.
* (Meta) I strongly suspect that the problem you were given is about *contiguous* sums. If you linked to the actual problem, it would be easy to verify that. Otherwise I'm very surprised by how difficult this problem is, given that it was assigned in a course called "Introduction to Algorithms". But maybe you covered a trick in class that makes it trivial.

# Answer
> -1 votes
My proposed algorithm goes as follows:

A sum is divisible by n if you only add summands which are multiples of n.

Before you start you create a hashmap with an int as key and a list of indices as value. You also create a resultlist containing indices.

You then loop over the array and add every index which mod n is zero to your result list. For every other index you do the following:

You subtract the value mod n of this index from n. This result is the key for your hashmap which stores indices for elements with the required value. Now, you add this index to the list in the hashmap and move on.

After you finished looping over the array you compute the output. You do this by sorting each list in the hashmap according to the value the index points to. Now you consider every pair in the hashmap summing up to n. So if n = 7 you search the hashmap for 3 and 4. If you got an entry in both you take the two largest values remove them from their lists and add them to your resultlist.

Last recommendation: still didn't test the algorithm, write a testcase against it using a brute force algorithm.

---
Tags: algorithms, optimization, dynamic-programming, arrays
---


# Question
Title: Relation of deterministic push down automata and lower elementary recursion
Deterministic context free languages are the context free languages that can be accepted by a deterministic push down automata.

Deterministic context free languages can be recognized by a deterministic Turing machine in polynomial time.

The lower elementary functions are a subset of the elementary recursive functions.

Lower elementary recursive functions are limited to polynomial time growth.

From this is it correct to derive that deterministic push down automata are of equal power to the lower elementary recursive functions?

Edit: My reasoning is that because the deterministic context free languages can be recognized in polynomial time that a deterministic push down automata is implementing a boolean function of up to that complexity. The lower elementary functions are also up to polynomial time. As such are they not equal in power?

# Answer
No, that doesn't follow at all. There are problems that can be solved in polynomial time, but that don't correspond to any deterministic context-free language.
> 2 votes

---
Tags: complexity-theory, automata, pushdown-automata, computation-models, polynomial-time
---


title: Proving a CFG is ambiguous?

text:
# Question
Title: Proving a CFG is ambiguous?
I have a CFG:

```
S --> 0S1S | 1S0S | ε

```

I'm trying to prove that it is ambiguous, but the steps to proving so are confusing me.

So if I pick a string, let's say 010110, I just have to show that there are two different parse trees for the string?

# Answer
> 3 votes
Proving inherent ambiguity of a language is difficult, but proving ambiguity of a grammar is relatively quite easy.

The definition of ambiguity of a grammar does not say that every string has to have different parse trees. It says there need to exist only one string which has different parse tree to make a grammar ambiguous.

The trick to achieve two different parse tree for an ambiguous grammar is to look for a string where you can apply two different rules for the same string or the same rule in two different ways. Since one rule derives $0S1S$ and the other rule derive $1S0S$ you cannot have both rules deriving same strings, so you have to look for a rule that can be applied in two different ways. There you are in luck. Both rules can be applied in different ways.

Take first rule for example: $S \rightarrow 0S1S$. Can you have a string starting with 0 but matches 1 at two (or multiple) different places? It turns out you can $\underline 0$-$10$-$\underline 1$-$\epsilon$ and $\underline 0$-$\epsilon$-$\underline 1$-$01$ i.e. string $0101$. $0101$ and $1010$ are the smallest length strings of the grammar which will have different parse trees.

String $010110$ also has two parse trees $\underline 0$-$\epsilon$-$\underline 1$-$0110$ and $\underline 0$-$10$-$\underline 1$-$10$.

# Answer
> 1 votes
You have to find a string which has two different parse trees. That string might be 010110 or it might be something totally different. In this kind of situation my recommendation is to refer back to the definition in your textbook and work out what the definition is saying.

---
Tags: formal-languages, regular-languages, context-free
---


title: What is a local inference system?

text:
# Question
Title: What is a local inference system?
A inference system is a set of rules that can be used to prove something in some formal model. I understand that.

But what does it mean to a inference system to be local?

For instance, in the page 36 of these MPRI notes there is the following definition:

**Definition 4.2 (locality)** Let $I$ be an inference system. The system $I$ is local if whenever $T ⊢ u$ in $I$, there exists a proof $\Pi$ of $T ⊢ u$ such that $Steps(\Pi) \subset st(T \cup \\{u\\})$.

But I am not able to understand this definition because even if I know that $st(T\cup\\{u\\})$ is the set of subterms of $T \cup \\{u\\}$, I don't know what is $Steps(\Pi)$.

# Answer
> 2 votes
$\mathsf{Steps}(\Pi)$ is defined just above, in the paragraph below Definition 4.1. It's the set of node labels in the proof, i.e. the set of propositions that are proved as lemmas in that proof.

Thus a local inference system is a set of propositions such that every deduction $T \vdash u$ can be proved from lemmas that only involve terms that are subterms of the proposition $u$ or of the premises $T$.

---
Tags: terminology, logic, formal-methods, software-verification
---


# Question
Title: Which law is this expression X+ X’.Y=X+Y
Question. Name the law given and verify it using a truth table. X+ X’.Y=X+Y

```
My Answer.
X   Y   X’  X’.Y    X+X’.Y  X+Y
0   0   1   0       0       0
0   1   1   1       1       1
1   0   0   0       1       1
1   1   0   0       1       1

Prove algebraically that X + X’Y = X + Y.
L.H.S. = X + X’Y
           = X.1 + X’Y        (X . 1 = X property of 0 and 1)
           = X(1 + Y) + X’Y   (1 + Y = 1 property of 0 and 1)
           = X + XY +  X’Y
           = X + Y(X + X’)
           = X + Y.1          (X + X’ =1 complementarity law)
           = X + Y            (Y . 1 = Y property of 0 and 1)
           = R.H.S.      Hence proved.

```

My teacher marked my answer wrong. And told me to find the correct answer. Friends tell me is it a *complementary law or distributive law or Absorption law?* If it is absorption kindly tell me how to prove RHS and LHS algebraically.

# Answer
One way of looking at this is as a consequence of distributivity, where $P+QR\equiv (P+Q)(P+R)$. Then you'll have $$\begin{align} X+(X'Y) &\equiv (X+X')(X+Y)&\text{distributivity}\\ &\equiv T(X+Y)&\text{inverse}\\ &\equiv X+Y&\text{domination} \end{align}$$
> 10 votes

# Answer
This is known as the third distributive law (see, e.g., this page). I think your proof is correct
> 0 votes

# Answer
X+X'Y=X+Y

taking LHS X+X'Y=(X+X')(X+Y) OR distributes over AND 1.(X+Y) (X+X'=1) X+Y=RHS 1 is identity for AND

Hence Proved
> -4 votes

---
Tags: boolean-algebra
---


# Question
Title: Misconception in taking Pumping Length of language {a} to be $2$
I would like to know why the pumping length of language {a} is $2$ as said in this chat discussion.

Eventhough this discussion proves *trivially* that the pumping length of language {a} is $2$ I couldn't get by an example how the pumping length of language {a} becomes $2$.Could anyone help me with an example.

# Answer
**Informally**, the pumping lemma for regular languages state that any sufficient large string may be pumped.

Your language is finite, meaning if you pick a pumping length that is larger than any string in your language, the lemma is trivially true. In your example the pumping length is $2$ but there are no strings in your language of length at least two. So you can pump all strings of length $2$ or longer (there are none!).

If you try and pick a smaller pumping length (the only possibility is $1$) then you will find that you can not pump. $w = a$ is your only string and the only possible decompsition $w=xyz$ is $x=\epsilon$, $y=a$, $z=\epsilon$. You can't however pump that because e.g. $\epsilon$ and $aa$ is not in your language.

Therefore; $2$ is the minimal pumping length of the language $\\{a\\}$
> 5 votes

# Answer
If you look at the proof of the pumping lemma, then you will see that the *pumping length* is nothing else than the number of states in the minimal finite automaton accepting the language. Your language is accepted by an NFA having $2$ states, so the pumping length is $2$.
> 3 votes

# Answer
If any string of length 2 is pumped, you obtain an even longer string. The original one as well as the new one are outside the language, everythign is fine.

If you pump the string **a** from the language, you obtain a longer one and are now outside the language. Thus length one does not work.
> 2 votes

---
Tags: formal-languages, pumping-lemma
---


# Question
Title: Is there a known method for constructing a grammar given a finite set of finite strings?
From my reading it seems that most grammars are concerned with generating an infinite number of strings. What if you worked the other way around?

If given n strings of m length, it should be possible to make a grammar that will generate those strings, and just those strings.

Is there a known method for doing this? Ideally a technique name I can research. Alternatively, how would I go about doing a literature search to find such a method?

# Answer
> 12 votes
This falls within the general topic of "grammar induction"; searching on that phrase will turn up tons of literature. See, e.g., Inducing a context free grammar, https://en.wikipedia.org/wiki/Grammar\_induction, https://cstheory.stackexchange.com/q/27347/5038.

For regular languages (rather than context-free ones), see also Is regex golf NP-Complete?, Smallest DFA that accepts given strings and rejects other given strings, Are there improvements on Dana Angluin's algorithm for learning regular sets, and https://cstheory.stackexchange.com/q/1854/5038.

# Answer
> 9 votes
If the number of strings is finite say set $S=\\{s\_1,s\_2....s\_m\\}$ you can always come up with context free grammar that generates all those strings, let $A$ be a non terminal then the rule can be $A \to s\_1|s\_2|...s\_n$. For a finite set of strings you can even come up with a finite state automata that accepts only those strings. So the case of finite set of strings is really trivial.

# Answer
> 3 votes
There are lots of ways, so you need to impose additional criteria on the quality of the results. Examples:

1. *List*: For each string $w$ in the language, have a rule $S \rightarrow w$. Let $S$ be the starting nonterminal. Done.
2. *Prefix tree*: For each prefix $w$ of a string in the language, have the nonterminal $X\_w$. For each string $w\_1xw\_2$ in the language, where $x$ is a symbol, have the rule $X\_{w\_1} \rightarrow xX\_{w\_2}$. For each string $w$ in the language, have rule $X\_w \rightarrow \epsilon$. Let $X\_\epsilon$ be the starting nonterminal. Done.
3. *Suffix tree*: the same, reversed.
4. Applying an algorithm guaranteed to produce a grammar of minimal size, e.g. with the minimal number of rules. I don't know how hard this is.

# Answer
> 3 votes
What you are asking is akin to a search index. Indeed Finite State Transducers can be created and used to recognize text fed to them. For exameple, Lucene uses this algorithm: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.3698

For a practical use, check out this blog post by Andrew Gallant: Index 1,600,000,000 Keys with Automata and Rust

In the post he describes a method to construct a FSA given a corpus of text such that it recognizes all the words. The end result is to construct an approximately minimal FST from pre-sorted keys in linear time and in constant memory.

The implementation is available in his `fst` library: https://github.com/BurntSushi/fst

# Answer
> 1 votes
An answer to the question posed by reinierpost which also answers the original question:

We construct the dictionary automaton as follows:

1. construct an automaton that reads and accepts exactly the first string.
2. for the next string, start reading it with the automaton until for some letter there is no transition. start a new branch for the rest of the string. repeat until all strings are processed

The maximal size of the automaton is the total length of the input strings. Assuming that you can simulate transitions and create new ones in constant time, also the runtime is the total length of the input strings. No best or worst cases.

This automaton is minimal. since in the regular case automata and grammars correspond almost one to one, the same is true for the grammar, Of course, it is impossible to construct something of size n in less than n time.

---
Tags: formal-languages, regular-languages, formal-grammars, finite-sets
---


# Question
Title: Using Taylor series in 1D Grayscale Image
Could someone point me in the direction of how to solve this?

I = \[I1, . . . , In\] is a 1D grayscale image and D = \[D1, . . . , Dn\] represents the second derivative of I. I am given the four pixel intensities I1, I2, In−1, In\] and the second derivative values D3, . . . , Dn−2. How would I compute the rest of I’s intensities?

What I have tried so far: Each Ix intensity can be approximated via Taylor series: Ix = I(0) + x(dI(o)/dx) + (1/2)x^2(d^2I(x)/dx^2).

I am sure the trick is in using the sliding window algorithm for fitting a 2nd degree polynomial, and that a matrix is involved in solving. However, I am unsure how big the sliding window should be (3, 5 pixels?), etc.

# Answer
> 1 votes
I am sure these are finite differences, so the first "derivatives" are just

$B\_i := I\_{i+1} - I\_i$

and the second "derivatives" are the differences of those:

$D\_i := B\_{i+1} - B\_i$

Write it out and solve for $I\_i$.

---
Tags: computer-vision, linear-algebra, pattern-recognition
---


# Question
Title: Maximal class for which function equivalence is decidable
I previously asked if it's decidable whether two primitive recursive functions are equivalent: "primitive recursive functional equivalence". The answer was no.

Here is my followup. What is the most powerful class of functions where it can generally be decided if two functions are equivalent? That is, a function can be written such as `areEqual :: fun1 -> fun2 -> Bool`. By equivalent I do not mean the same algorithm but the same relation between domain and codomain.

In another question I asked if lower elementary recursion was equivalent to deterministic push down automata: "Relation of deterministic push down automata and lower elementary recursion". The answer was no, and that my thought process was wrong. My hope was that this would show that polynomial time functions (lower elementary) could be proven equivalent.

This question is in relation to what class of recursion, not machine. As such deterministic pushdown automata is not what I am looking for. If I understand the answers to my second question correctly the automata do not necessarily translate to a class of recursive functions.

I have been poking at this question for a while in a round about way probing for an answer.

The problem is intuitively solvable for simple problems. For example the `even?` function could be implemented in a mutual recursive manner with `odd?` or from `mod 2`. These two ways do the same thing. The question is in relation to the highest class of functions where this is possible.

# Answer
> 6 votes
There is no such maximal class.

Proof: suppose that there is a class $C$ of representations of total functions for which function equivalence is decidable. If $C$ is finite, then $C$ augmented with the constant function that returns $\max\\{\overline{f\_i}(0)\\} + 1$ (which by construction is not in $C$) has decidable function equivalence (test the function at $0$ then apply the postulated decision algorithm). If $C$ is infinite, it is denumerable (because representations of functions are denumerable¹), so let $(f\_i)\_{i\in\mathbb{N}}$ be an enumeration of all function representations in $C$. Let $G(i) = \overline{f\_i}(i) + 1$ (a classic diagonal construction). By construction, $G$ does not have a representation in $C$ (because $\forall i, g\_i(i) \ne h(i)$). Let $g$ be a representation of a function that calculates $G$ (this is doable in any Turing-equivalent framework). The algorithm that reports that $g$ is distinct from any member of $C$, and otherwise applies the existing decision algorithm for $C$, is an equivalence decision procedure for $C \cup \\{g\\}$.

Any class of function representations with decidable equivalence can be augmented to a larger such class. Therefore there is no maximal class.

Intuitively speaking, if you have two classes of functions with decidable equivalence, you can apply the two decision algorithms inside each class, but it's not necessarily possible to compare two functions from different classes. And if you have an infinite set of classes, with a decision procedure for each, then even calculating which decision procedure to use is not necessarily doable.

¹ <sub> The set of all functions is not denumerable, but whatever representation of functions you choose (e.g. source code in some language), the set of inputs for your decision algorithm is denumerable. </sub>

---
Tags: computability, complexity-classes, decision-problem, computation-models
---


# Question
Title: Is it correct to use the pinhole camera model to get the mapping of a 3D line to a line in an image?
I've been working on a computer vision project in which I'm using the pinhole camera model to map one line of the world to one line in an image.

From previous research on the topic, I know that it is possible to map a point in the 3D world to a point in one image using the projection matrix obtained by calibrating the camera you're using to get the images of the 3D world. This mapping can be done as follows:

$ \lambda \begin{bmatrix}u \\ v \\ 1\end{bmatrix} = P \begin{bmatrix}X \\ Y \\ Z \\ 1\end{bmatrix}$,

in which $(u,v,1)$ are the coordinates of the point in the image, $(X,Y,Z,1)$ are the coordinates of the same point in the world and $P$ is the projection matrix.

A line in the image can be defined as:

$\begin{bmatrix}A & B & C\end{bmatrix}\begin{bmatrix}u \\ v \\ 1\end{bmatrix}$,

in which $(A,B,C)$ are the parameters used to describe the line. My research also taught me that perspective projections preserve lines, i.e., a straight line in the world will map to a straight line in the image.

Using the description of a line and the method used to get the mapping of points, I got this model:

$ \lambda \begin{bmatrix}A & B & C\end{bmatrix} \begin{bmatrix}u \\ v \\ 1\end{bmatrix} = \begin{bmatrix}A & B & C\end{bmatrix} P \begin{bmatrix}X \\ Y \\ Z \\ 1\end{bmatrix}$.

I've done some additional research, but so far I haven't found anything that can support this affirmation.

Is it correct to say that the mapping of a 3D line in the world to a line in an image of the world is done using the previous model?

Could anyone please point me in the right direction?

Thank you.

# Answer
> 3 votes
The assumption is correct, if(f) you project the 3d line into the rectified image. The idea of projecting a 3d-line to a pixel-line is most often used in a stereo setup with two cameras: if the left camera sees a features at a certain pixel, then you know that this object is on a 3d-ray that corresponds to this pixel. If you want to search this object in the right camera's image, you only have to search on the pixel line that corresponds to this 3d-line. Keywords are here epipolar geometry or epipolar line: https://www.robots.ox.ac.uk/~vgg/hzbook/hzbook1/HZepipolar.pdf

# Answer
> 3 votes
Please refer: Perspective Projection and Perspective Projection Matrix.

Essentially pinhole camera is perspective view behind the camera. Since we need to divide the $z$ coordinate at places, we have to use homogeneous coordinates. It is easy to prove that line in the 3D world maps to line in the pinhole image.

A line in 3D is $\lambda p\_1 + (1-\lambda)p\_2 = $$ \begin{bmatrix} x \\ y \\ z \\ 1\end{bmatrix}$,
where $-\infty \< \lambda \< \infty$, $p\_1$ and $p\_2$ are points (4x1 vector in homogeneous coordinates) in 3D, and the line passes through these points. If $P$ is perspective matrix transformation then we have the following:

$P(\lambda p\_1 + (1-\lambda)p\_2) = $$ P\begin{bmatrix} x \\ y \\ z \\ 1\end{bmatrix}$ in pinhole camera image

$\Rightarrow\lambda (Pp\_1) + (1-\lambda)(Pp\_2) = $$ P\begin{bmatrix} x \\ y \\ z \\ 1\end{bmatrix}$ in pinhole camera image.

This is equation of line. So yes if you have $p\_1$ and $p\_2$ points as parameters of line in 3D then $Pp\_1$ and $Pp\_2$ will be the parameters of line in pinhole camera image.

# Answer
> 2 votes
You are confusing some things.

First off, a line (or more precisely: the set of points $(x,y)$ on a line) in 2D can be written as the set of points satisfying an *equation* of the form

$$\begin{bmatrix}A&B&C\end{bmatrix}\begin{bmatrix}x\\y\\1\end{bmatrix}= 0$$ for some $A,B,C$. We could also write

$$\begin{bmatrix}A&B\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix}= -C.$$

Note that we write the 2D point vector $(x,y)$ extended by a 1 here, $\begin{bmatrix}x\\y\\1\end{bmatrix}$, has *nothing* to do with the "homogeneous 1" appended to the 2D point $(u,v)$ in your (correct) equation for the perspective projection.

Let me write that one out too:

The 2D point $(u,v)$ is the projection of the 3D point $(X,Y,Z)$ under the projection matrix $P \in \mathbb R^{3 \times 4}$ iff there is some $\lambda \neq 0$ such that

$ \lambda \begin{bmatrix}u \\ v \\ 1\end{bmatrix} = P \begin{bmatrix}X \\ Y \\ Z \\ 1\end{bmatrix}$

Then you ask

`Is it correct to say that the mapping of a 3D line in the world to a line in an image of the world is done using the previous model?`

A *mapping* and a *model* are quite different things. IMO it is not very clear what you are asking for.

Here is a few questions that you could ask given these considerations:

* Given a line in 2D described via parameters $(A,B,C)$ as above, what is the corresponding line in 3D?
* Given a line in 3D, what is the line's $(A,B,C)$ parametrization in 2D?

Note that a line in 3D *cannot* be characterized by an equation of the form (say)

$$\begin{bmatrix}U&V&W&T\end{bmatrix}\begin{bmatrix}x\\y\\z\\1\end{bmatrix}= 0$$ (this characterizes a plane)

But in every dimension a line can be defined by a point and a vector as the set of points of the curve $\phi(t) :=p + tv$.

---
Tags: computer-vision
---


# Question
Title: Role of computational power in recent AI developments
Today Google's AI won its first game of Go against Lee Sedol, one of the best Go players on the planet. Image interpretation and self-driving cars are other recent success stories in machine learning. I was under the impression that these advances are largely the result of better algorithms and novel ideas, but some of the guys in my university were claiming these advances are mainly due to increased computational power. Neural networks in particular are an old concept that was largely forgotten for decades and now we're doing all sorts of cool new things with it.

What is the role of computational power with regards to recent successes in artificial intelligence?

# Answer
> 2 votes
This is a broad question, but from the presentations I've seen, there have been three major factors that all have come together over the past decade or two:

* **More data.** Machine learning algorithms rely upon having many instances, so we can train them. The more data we have (the more labelled instances we have), the better the algorithms do. On some of the harder problems people are tackling today, machine learning algorithms only start to do well once you give them millions or billions of examples. For example, speech recognition is a prime example of this: researchers in the field have told me that progress in speech recognition was closely related to the size of the data sets available for training. Over the past decade or two, large data sets have become available: it's become possible to train algorithms using every image on Flickr, or every video on Youtube, or every call ever made to Google Voice. That wasn't possible two decades ago.
* **More computational power.** Processing that much data requires efficient algorithms. One significant advance was that researchers found out how to use GPU's (graphic cards) as specialized processors: implementing the machine learning algorithm on a GPU could speed up the training process by 10x - 100x.
* **Better algorithms.** Deep learning has been having some significant successes over the past five years or so. This is a result of decades of hard work. There's a small subcommunity of researchers who have been working on neural networks for decades, and who have slowly been making progress, finding what kinds of neural networks work well. They've invented many new algorithmic ideas: autoencoders, stochastic gradient descent with mini-batches, ReLU activation functions, drop-out for regularization, convolutational neural network structures.

It has taken the combination of all of these new algorithmic ideas, plus larger data sets, plus new ways of implementing the algorithms efficiently so we can make effective use of the large data sets, to achieve these gains. This is a real success story for the field.

Sometimes you hear the stereotype of a lone inventor sitting in their garage, who one day has a "Eureka!" moment and comes up with a brilliant invention fully-formed in a flash of insight. However, that's typically not how research progresses. Deep learning is a good example of that. It has taken decades of work and gradual improvement, exploring many ideas that ultimately didn't pan out, with researchers building on incremental advances and new ideas from other researchers, to reach where we are today. An inspiring example for the impact of long-term fundamental research.

---
Tags: machine-learning, artificial-intelligence, neural-networks
---


title: Showing that 3-colorable is NP-complete

text:
# Question
Title: Showing that 3-colorable is NP-complete
Just as a background, *3-colorable* problem is as follows: Given a graph $G = (V, E)$, is it possible to color the vertices using just 3 colors such that no neighboring vertices have the same color?

I'm aware we can show that *3-colorable* is an NP-complete problem by reducing *3-SAT* to it. But I'm wondering is it possible to reduce *clique* to it?

I know for example that if a graph with n vertices contains a subgraph which is a clique of size k, then you need at least k colors (that is, the chromatic number is at least k).

So could we say that if a graph contains a *clique* of size 4, then it is not *3-colorable*, and vice versa?

Edit: Hmm..upon further thought, maybe the reduction wouldn't work because in order to reduce clique, you can't fix ahead of time that you're looking for a clique of size 4? The size of the clique would be arbitrary..

# Answer
> 3 votes
A problem $P$ being NP-hard means that all problems in NP can be reduced to $P$. That's by definition. Working out the exact reduction needed can be tricky, which is why one usually looks for a somehow similar problem to prove hardness. You probably wouldn't try to directly reduce MINIMUM INTERVAL GRAPH COMPLETION to Tetris to prove its hardness.

In general you can chain reductions. In your case, since you know 3-colorability can be used to solve 3-SAT and you know 3-SAT can be used to solve CLIQUE, you can first transform your CLIQUE instance to 3-SAT and then the resulting formula to a 3-colourability problem.

# Answer
> 5 votes
No, you couldn't say that, because it's not true.

A helpful method is to *prove* all your claims. Don't just guess -- try to find a proof. If you're struggling to find a proof, the first thing to check is whether maybe the thing you're trying to prove is false, so look for a counterexample. In this case you should easily be able to find a counterexample to your claim. Alternatively, if you can't find a proof and can't find a counterexample, look for a different approach or a different way to solve the problem that uses only facts you do know how to prove correct.

---
Tags: graphs, np-complete, reductions, colorings, clique
---


# Question
Title: Is a balanced binary tree a complete binary tree?
Considering that the opposite is true it's not mentioned anything about this. I am assuming its not, but I need a very good distinction between these two types of binary trees.

All I know is this:

* A binary tree is balanced (or height balanced), if the height of any node’s right subtree and left subtree differ no more than $1$.
* A complete binary tree of height h is a binary tree that is full down to level $h-1$, with level $h$ filled in from left to right.

# Answer
A **complete binary tree** is a binary tree of length $h$ such that all the levels from $1$ to $h-1$ are completed and the last level gets completed from left to right. As in the image below.

A **balanced binary tree** is a binary tree of height $h$ such that the height of any node’s right subtree and left subtree differ no more than $1$. So it doesn't say anything about it having to be completed from left to right.

The figure **above** describes this trees very clearly in a **recursive** way.
> 5 votes

---
Tags: data-structures, trees, binary-trees
---


# Question
Title: Can a cellular automata structure simulates another cellular automata structure?
In Elementary Cellular Automata, rules can show one pattern, but i am wondering if there is something where a cellular automata structure can simulate another structure?

Is there a category for this in Cellular Automata?

# Answer
> 1 votes
Any cellular automata that could be classified as a universal Turing machine would be able to do this. The Game of Life is one such cellular automata. Here is it (rather pointlessly) simulating itself on a larger scale. Here is a Turing machine implemented in it. This 'category' that you want is probably "cellular automata that qualify as universal Turing machines". I suspect this question will be of interest to you.

---
Tags: complexity-theory, computability, space-complexity, cellular-automata
---


title: Reduction between two decision problems

text:
# Question
Title: Reduction between two decision problems
We are given two decision problems: $Q\_1\colon I\_1\to\\{0,1\\}$ and $Q\_2\colon I\_2\to\\{0,1\\}$.

By definition, if there exists a function $f\colon I\_1\to I\_2$ such that for each $x\in I\_1$ we have $Q\_1(x)=Q\_2(f(x))$ then $Q\_1$ can be reduced to $Q\_2$ by $f$.

Now suppose that $Q\_1$ can be reduced to $Q\_2$ by a given $f$. My question is: is that true, that there always exists a function $g\colon I\_2\to I\_1$ such that for each $y\in I\_2$ we have $Q\_2(y)=Q\_1(g(y))$?

I believe so. Since the reduction of $Q\_1$ to $Q\_2$ by $f$ can be executed in a finite number of well-described steps and since I know explicitly the mapping: $I\_1\to I\_2$ I think there has to be a way to "reverse" the operation of reduction. Am I right? Is there a formal proof?

# Answer
First, your definition of reducibility needs to include some sort of restriction on the power of $f$: typically, for example, we require the function to be computable.

Without this restriction, any two decision problems (except the trivial problems "always yes" and "always no") are reducible to each other. Since there are always $y$ and $n$ such that $Q\_2(y)=1$ and $Q\_2(n)=0$, there is always a function $f$ that reduces $Q\_1$ to $Q\_2$: just take \begin{equation\*} f(x) = \begin{cases} \ y &\text{if }Q\_1(x)=1\\ \ n &\text{if }Q\_1(x)=0\\,. \end{cases} \end{equation\*}

So, we typically restrict to computable functions $f$ as reductions. Your question is, essentially, is a computable reduction always reversible? The answer to this is no and the reduction $f$ above gives a big hint why: that function is not invertible and there's no reason, in general, to expect that even a computable reduction should be invertible.

For example, consider any decidable problem $Q\_1$, and let $Q\_2$ be the halting problem. In this case, we can take $y$ to be the description of any Turing machine that halts immediately, and let $n$ be any Turing machine that just moves the head right forever. Since $Q\_1$ is decidable, the reduction $f$ above is computable. It tells you how to translate questions about $Q\_1$ to questions about the halting problem. It also kind of tells you how to translate questions about whether or not $y$ and $n$ halt into questions about $Q\_1$. But it doesn't help you determine whether any other Turing machine halts – and it can't, because that problem is undecidable.
> 2 votes

# Answer
No, you cant always find a reverse reduction. If $A$ is reducible to $B$ you should read it as: $A$ is not harder than $B$ (if i can decide membership to $B$, then i can decide membership to $A$), nothing is said about the opposite. For example, every decidable problem is reducible to the halting problem, but obviously the halting problem is not reducible to any decidable problem.
> 0 votes

---
Tags: complexity-theory, reductions
---


# Question
Title: Question about idempotent and Dominance Laws in Boolean Algebra
If I have the following statements:

For Idempotent:

Since **X * X = X**, would that imply that **~X * ~X = ~X**

For Dominance:

Since **X + 1 = 1** would that imply that **~X + 1 = 1**

# Answer
The principle of substitution states that if $\varphi$ is a valid (fully parenthesized) formula in variables $x\_1,\ldots,x\_n$ and $e\_1,\ldots,e\_n$ are arbitrary expressions, then if we substitute $e\_i$ for $x\_i$ in $\varphi$ (you have to substitute *all* occurrences of $x\_i$ by $e\_i$) we still get a valid formula. You can apply this principle to your examples.

Perhaps the principle will become easier to understand if we take an example from algebra. Consider the identity $(x+y)(x-y) = x^2-y^2$. If we substitute $2a$ for $x$ and $1+a$ for $y$ then we get $((2a)+(1+a))((2a)-(1+a)) = (2a)^2-(1+a)^2$, which is still valid. The same happens in your case.
> 2 votes

---
Tags: boolean-algebra
---


# Question
Title: Euler graph k-coloring (np-completeness proof)
I've been studying np-completeness proofs by reduction, and was wondering whether my approach to the following problem is viable.

Define an Euler graph as a graph that 1) is connected, and 2) has every vertex with even degree.

Input: An Euler graph and an integer $k$. Problem: is the given graph $k-colorable$?

Show that the above is NP-complete.

My attempt: The problem is in NP since, given some solution "certificate" consisting of $k$ sets of vertices (where all vertices in a set are assigned the same colors), the solution can be verified in polynomial time: Just go thru each vertex and ensure that none of its neighboring vertices are contained in the same set as that vertex. Since a vertex can have at most $n - 1$ neighbors (where $n = |V|$), this should take asymtotically $O(n^2)$ time.

Reduction: reduce the general $k-coloring$ (chromatic number) problem (which is known to be NP complete). Here is where I run into some questions...

My initial thinking was that, given an instance of the general $k-coloring$ problem, with a graph $G$ and an integer $k$, we can construct $G'$ and $k'$ by adding a single vertex to $G$, and connecting that vertex to every odd vertex in $G$, while letting $k' = k$. But then I saw this wouldn't work for a 2-vertex tree graph. Letting $k' = k + 1$ is no good either, because this wouldn't work for the graph consisting of the shape of a square with a diagonal segment added to it.

So now I'm thinking, why not just locate every pair of odd-degree vertices in $G$ and connect each pair with a single edge, while letting $k' = k$? Would this reduction work, or are there still cases where this wouldn't work?

# Answer
A major part of proving that a problem is NP-hard by reduction is proving that the reduction works. It's not enough to find some procedure which takes an instance of problem A and transforms it to an instance of problem B; you have to figure out the connection betweens solutions of the one instances and solutions of the other.

In your case, one idea that does work pairs up odd-degree vertices and connects every pair to a new vertex. Now all the degrees are even, and the new graph is $k$-colorable iff the old one is $k$-colorable, *assuming $k \> 2$*. I'll let you figure out why this works.

While this idea is similar to your own idea of connected pairs of odd-degree vertices, your idea is problematic since it is not clear that if the original graph is $k$-colorable then so is the new graph. Indeed, if two vertices that you connected were colored using the same color then you cannot use the same coloring for the new graph. The idea described in the previous paragraph is very similar but doesn't suffer from this shortcoming.
> 4 votes

---
Tags: graphs, np-complete, reductions, colorings
---


title: Solving using the master theorem

text:
# Question
Title: Solving using the master theorem
I am wondering why this

$T(n)=3T(n/4)+n⋅lg(n)$

recurrence can be solve by Master Theorem case 3 but this
$T(n)=2T(n/2)+n⋅lg(n)$
recurrence can not be solve by Master Theorem what is the difference between this two recurrences.
When I searched on google I found tow questions related with this two recurrence
First Question:
Solving $T(n)= 3T(\frac{n}{4}) + n\cdot \lg(n)$ using the master theorem
Second Question:
T(n)=2T(n/2)+nlognT(n)=2T(n/2)+nlogn and the Master theorem

But both of them say something in contrast with each other and I could't find out the main reason.

# Answer
In these cases it's always a good idea to look at the **statement** of the master theorem. The statement on Wikipedia states regarding case 3 that if $T(n) = aT(n/b) + f(n)$ where

1. $f(n) = \Omega(n^c)$ for some $c \> \log\_b a$ (i.e. $b^c \> a$), and
2. $af(n/b) \leq (1-\epsilon) f(n)$ for some $\epsilon \> 0$ and large enough $n$,

then $T(n) = \Theta(f(n))$.

Let's see whether the theorem applies in your two cases. In your first case $a = 3$, $b = 4$, and $f(n) = n\log n$. We have $f(n) = \Omega(n^1)$ and $1 \> \log\_4 3$, and furthermore $$3f(n/4) = 3(n/4)\log(n/4) \leq (3/4)n\log n = (3/4)f(n).$$ Both conditions are satisfied, and so we can conclude that $T(n) = \Theta(n\log n)$.

In your second case $a = b = 2$ and $f(n) = n\log n$ is the same. In this case $f(n) = \Omega(n^c)$ only for $c \leq 1$, whereas we need $c \> \log\_2 2 = 1$, so we cannot apply case 3. The second condition also doesn't hold, since $2f(n/2) = 2(n/2)\log(n/2) = n\log n - \Theta(n)$, and so it is not true that $2f(n/2) \leq (1-\epsilon) f(n)$ for any $\epsilon \> 0$.

However, in this example case 2 of the master theorem applies, showing that $T(n) = \Theta(n\log^2 n)$.
> 1 votes

---
Tags: algorithms, algorithm-analysis, master-theorem
---


# Question
Title: sorting a sorted array that has been inc/dec by random numbers
If given a sorted array of n distinct positive integers. And each element is incremented or decremented by a number between 0 and X. For positive integer X that is a function of n.

Formulate an algorithm that takes the inc/dec array and sort it. Make the run time O(n) when X is constant.

I am unsure with my solution. Firstly, I just choose an random number of buckets... 10. The proof seemed to work out. Is there a way to prove that using X(the variable from above) number of buckets will be better?

In addition, is there a way to utilize the fact the array has been sorted prior to being augmented?

My solution:

```
1.  Find the minimum and maximum of the array by iteratively going through the array

O(n)

2.  Create intervals for the k buckets (k = number of buckets)
int interval
int k = 10
interval = (Max – Min + 1)/k

3.  Assign each element to the bucket based on the interval
O(n)

4.  Sort each bucket
if there is ni elements in each ith bucket
the sorting using randomized quicksort S(ni) = O(nilogni)

5.  Combine all the elements
O(n)
Runtime Analysis:
•   The time to sort every bucket will be as follows:
•   We assume the elements are uniformly distributed. Thus n/k elements in each bucket.

```

Since k = n/10, T(n) = n log(10) = O(n)

# Answer
Your algorithm doesn't work since you're analyzing it under some (suspect) random model, whereas the problem setters wanted a *worst case* guarantee. The worst case for you is that everything falls into the same bucket, and then you just get the usual $O(n\log n)$ guarantee.

Instead of your approach, I suggest trying to use the following observation:

> After sorting, each value moves at most $2X$ positions.

As an example of why this is useful, note that you can find the minimum of the array in time $O(X)$ by looking only at the first $2X$ elements.
> 2 votes

---
Tags: algorithms, runtime-analysis, sorting
---


# Question
Title: If a language is context free, then its complement is decidable
I am having a bit of trouble figuring this out. If L is context-free then we know it is decidable. The class of decidable languages is closed under complement thus, $L$ $\cap$ $L^{c}$, therefore $L^{c}$ is decidable.

Does this make any sense?

# Answer
> 1 votes
If $L$ is context free, it is decidable. Thus so is it's complement (to see if $\sigma \in L^c$, check if it is in $L$ and answer the opposite).

$L \cap L^c = \varnothing$, which is certainly decidable (just say no).

Your question is *seriously* confused...

---
Tags: formal-languages, computability, context-free, closure-properties
---


# Question
Title: What is the fastest way to input all of 30 million human "go" move into the computer that haven't digitized?
What is the fastest way right now to input all of 30 million "go" move from the beginning into the computer that haven't digitized?

The idea is came from Google's AlphaGo

# Answer
Your bottleneck when doing this will be to gather up all the not yet digitized moves, validate them somehow, and digitize them. Once that is done, reading in the data will be a snap.
> 1 votes

---
Tags: algorithms
---


# Question
Title: How to choose waiting process in a preemptive priority-based scheduler
If my CPU schedule is preemptive priority, and I have no new processes coming, how I should choose from the waiting processes?

# Answer
“Preemptive priority” is a property of a scheduler, it is not a complete specification. Under preemptive priority scheduling, you choose the waiting process that has the highest priority. If there are multiple process with that priority, knowing that the scheduler is preemptive priority-based isn't enough to know what it will do. If you want to completely describe a scheduler, you need to specify that case as well.

Two common choices that are used together with preemptive priority-based scheduling are preemptive round-robin (interrupt processes after a certain time if another process with the same priority is ready) and non-preemptive round-robin (a ready process is only ever interrupted by a higher-priority process). But there can be more complex algorithms as well.
> 2 votes

---
Tags: operating-systems, scheduling
---