What's an example of a planar graph with two embeddings whose geometric duals are nonisomorphic? How to prove that the dual of the dual of a connected planar graph $G$ is isomorphic to $G$?
In the post linked above, the user "plop" gives a great response where they claim, in particular, that a plane graph $G$ has a well-defined geometric dual. Paraphrasing, for any two drawings $G^*_1$ and $G^*_2$ obtained in the following way, there exists a unique planar graph $Y$, up to isomorphism, such that the plane graphs $G_1^*$ and $G_2^*$ are planar embeddings of $Y$. Consequently, we may write $G^*$ for either $G_1^*$ or $G_2^*$, and call it the geometric dual of $G$.
To obtain such a plane graph $G^*$ from $G$, draw a point in$^\dagger$ each face of $G$, and for each arc $e$ of $G$, draw a new arc passing once through $e$ connecting the points in the two faces $f_1$ and $f_2$ incident with $e$. Do this such that no two of these new arcs intersect.$^{\dagger\dagger}$ This new set of points together with this new set of arcs describes the plane graph $G^*$.
$^\dagger$To make complete sense of this construction, one needs at least the Jordan Curve Theorem, and according to "plop" also needs the Jordan-Shoenflies Theorem.
$^{\dagger\dagger}$By the way, shouldn't this also require us to use the fact that a topological subspace of $\mathbb R^2$ (or of $S^2$) is connected if and only if it is path-connected? (Otherwise I could imagine two curves technically not intersecting but with something pathological happening where the curves get arbitrarily close to each other and end up "crossing" while still being curves in the sense that they are topological embeddings of $[0,1]$. This is a little beside the point.)
I am ok with the above claim. My question is:
Does there exist a planar graph $X$ with two planar embeddings $G_1$ and $G_2$ such that $G_1^*$ and $G_2^*$ are the planar embeddings of nonisomorphic graphs $Y_1$ and $Y_2$? If so, what's an example construction. If not, why not?
Note: Wikipedia claims seems to claim that the answer is "yes", but doesn't provide an example. I put a [citation needed] tag, so maybe once this is resolved, we can link it back to here.

The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs (graphs that are already embedded in the plane) rather than planar graphs (graphs that may be embedded but for which the embedding is not yet known). For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

https://en.wikipedia.org/wiki/Dual_graph

There is an answer in Graph Theory by Bondy and Murty:

It is clear that both graphs are isomorphic. Their respective duals are not, because each face of the first dual has degree 3  (except the unbounded one, of degree 5), and there are two faces of degree 4 in the second dual.


How are Qubits useful? I'm aware that a qubit can exist in an infinite number of states and that when measured it collapses into one state, with the probability of each state being directly affected by it's latitude.

My question is: Why is this in any way useful? Surely you can't use a unit of information meaningfully when you don't know what it will be..?

Surely, not knowing what a quantum bit is going to be is detrimental to computing? I'm evidently missing something since we know that quantum computing works, but why?

So you can't find out everything about the value of a qubit. That doesn't mean you know nothing about it. And, sure, quantum computing probably would be more powerful if you could find out everything about the value. But, again, the fact that you can't do everything doesn't mean that you can't do anything.

In particular, you know that the measured value of a qubit drawn from a probability distribution constructed by some quantum algorithm. The algorithm will, presumably, construct a distribution that's quite tightly concentrated about the true answer. And you can always repeat the computation to get multiple samples.


Multiple Variables in Asymptotic Notation I am trying to understand the multiple variable definition of an asymptotic notation. Particularly the definition in Wikipedia. It's also discussed in Asymptotic Analysis for two variables? but I think the answer is wrong. At least it is just corrected in the comments and and referenced to a lengthy answer. What I look for is just the answer for my confusion of the example given here. Wikipedia says,

Big $O$ (and little $o$, $\Omega$, etc.) can also be used with multiple
variables. To define big $O$ formally for multiple variables, suppose
$f$ and $g$ are two functions defined on some subset of
$\mathbb{R}^{n}$.
We say $f(\vec{x})$ is $O(g(\vec{x}))$ as
$\vec{x} \rightarrow \infty$ if and only if $\exists M \exists C>0$ such that for all $\vec{x}$ with $x_{i} \geq M$ $\textbf{for some $i$}$ $|f(\vec{x})| \leq C|g(\vec{x})|$.
... For example, if $f(n, m)=1$ and $g(n, m)=n$,
then $f(n, m)=O(g(n, m))$ if we restrict $f$ and $g$ to $[1,
\infty)^{2}$, but not if they are defined on $[0, \infty)^{2}$, This
is not the only generalization of big o to multivariate functions, and
in practice, there is some inconsistency in the choice of definition.

What I don't understand is, if we only look for some $i$, why can't we use the domain $[0, \infty)^{2} $? For example, if I only take the $n$ variable to infinity ($i$ is 0 in this case), then shouldn't it be fine and $f(n,m) \in O(g(n,m))$? Shouldn't the definition be not for some $i$ bur rather for all $i$? Do I understand the notion of for some in the wrong way?

Suppose that we consider $f(n,m) = 1$ and $g(n,m) = n$ as functions on $[0,\infty)^2$. Assume, for the sake of contradiction, that $f(n,m) = O(g(n,m))$. According to the definition, there exist $M,C>0$ such that $|f(n,m)| \leq C|g(n,m)|$ whenever $\max(n,m) \geq M$. In particular, this should hold for $(n,m)=(0,M)$, yet in this case $|f(n,m)| > 1 > 0 = C|g(n,m)|$.
The problem disappears if the domain is $[1,\infty)^2$. Indeed, in this case we can take $M=C=1$, since $g(n,m) = n \geq 1 = f(n,m)$ for all $n,m \in [1,\infty)^2$.
Perhaps the problem is with unpacking the definition. According to the Wikipedia definition, $f(\vec{x}) = O(g(\vec{x}))$ if there exist $M,C>0$ such that the following holds:

If $x_i \geq M$ for some $i$, then $|f(\vec{x})| \leq C|g(\vec{x})|$.

Equivalently,

If $\max(\vec{x}) \geq M$, then $|f(\vec{x})| \leq C|g(\vec{x})|$.

It should be noted that this definition is not standard, and one could think of other definitions. Two particularly natural alternatives are (i) requiring all entries of $\vec{x}$ to be large, and (ii) requiring the inequality $|f(\vec{x})| \leq C|g(\vec{x})|$ to hold for all $\vec{x}$.
(The second option is related to the fact that for functions $f,g\colon \mathbb{N} \to \mathbb{N}_{>0}$, the usual definition of $f=O(g)$, which is a special of the definition above, is equivalent to a definition which holds for all $n \in \mathbb{N}$.)


An imperative program is analogous to how a Turing machine works? Since Turing machines has great influence on typical hardware architecture (Von Neumann) and both uses concept of state, is correct to say that an imperative program is analogous to how a Turing machine works?

  “Computability via Turing machines gave rise to imperative
  programming. Computability described via λ-calculus gave rise to
  functional programming.” — Cooper, S. B., Leeuwen, J. (2013) . Alan
  Turing: His Work and Impact.

And

  "Imperative programming languages such as Fortran, Pascal etcetera as
  well as all the assembler languages are based on the way a Turing
  machine is instructed: by a sequence of statements." - Barendregt, H.,
  Barendsen, E. (2000) . Introduction to Lambda Calculus

At a high enough level and when contrasted with functional programming, sure. Turing machine models and imperative programs have in common that they start from an input and take a series of steps that change a state stored in memory, ending with some output.

This contrasts with lambda calculus and functional programming which generally and loosely do not have the above features.

I think reading any more into the comparison than this, or trying to take it any farther, is probably a mistake. As Yuval says, Turing machines are quite different from modern machines and program execution environments.


Confusion in 2's complement of 00000000 I'm solving the end of the chapter problems of Morris Mano's Digital Design (4th Edition, if that's relevant). In one of the problems, it is asked to simply find the 1's and 2's complement of 00000000. It's 1's complement would be 11111111. Now, for 2's complement, adding 1 to will give 100000000. But in the answer key, the answer is 00000000.

I know that if i'm working with a hardware that is only capable of handling 8 bits, the 1 will not be stored. But, in theory, the 2's complement of 00000000 should  be 100000000, right? Or is there something i missed? In the question there was no mention of hardware limitations, or even something like "use only 8 bits".

You have 00000000 as the number, it implies how many bits are used. The 1 at the front comes from carry bit, but two complements does not extend number of bits used, so the answer is 00000000, as the carry is discarded because it doesn't fit given space.

You can check it (to convince yourself) by converting code back from 2's complement to decimal. 00000000 yields 0, while 100000000 gives -256.


On asymptotic complexity class notation? Is the class of problems with complexity $O(n^{n^\epsilon})$ at every $\epsilon>0$ same as class of problems with complexity $O(n^{f(n)})$ at every $f(n)\in\omega(1)$ and hence both classes are equivalent to $\mathsf P$ ($n$ is number of input bits)?

(This is my view. Denote $C(n^{n^\epsilon})$ to be class of problems solvable in $O(n^{n^\epsilon})$ at every $\epsilon>0$ and let $D(n^{f(n)})$ be class of problems solvable in $O(n^{f(n)})$ at every $f(n)$ in $\omega(1)$. Does $\cap_{f(n)\in\omega(1)}D(n^{f(n)})=\cap_{\epsilon>0}C(n^{n^\epsilon})$ hold?  $\forall n\in\Bbb N\wedge\forall\delta>0 \exists\epsilon>0:n^\epsilon<1+\delta$ and so $C(n^{n^\epsilon})$ is smaller than $D(n^{f(n)})$ at every $f(n)$ in $\omega(1)$. However for every $\epsilon>0$ there is an $f(n)\in\omega(1)$ such that $f(n)<n^\epsilon$ at large enough $n\in\Bbb N$ and so $D(n^{f(n)})$ at any $f(n)$ in $\omega(1)$ is smaller than $C(n^{n^\epsilon})$. We then conclude both $O(n^{n^\epsilon})$ and $O(n^{f(n)})$ at any $f(n)\in\omega(1)$ are morally equal. Since $O(n^{f(n)})$ at any $f(n)\in\omega(1)$ is same as $\mathsf P$ we have the notation.).

The time hierarchy theorem shows that there are problems which can be solved in time $O(n^{\log n})$ but not in time $O(n^{\log\log n})$. These problems can be solved in time $O(n^{n^\epsilon})$ for any $\epsilon > 0$, but not in polynomial time.


Unrecognizable languages relationship to NP-hard languages I would like to know if there exists an NP-hard language which is also a member of co-RE\R?
I think it depends if P=NP or not, but i'm not sure.

Can I simply assume NP-hard is in R?

Can you direct me how to think about it?

There are NP-hard languages arbitrarily high in the arithmetical hierarchy.

To answer your specific question, the complement of the halting problem is NP-hard and it's in $\mathrm{coRE}\setminus\mathrm{R}$. To see this, let $M$ be a Turing machine that tries all variable assignments for a $\mathrm{SAT}$ instance.  Let it loop forever if it finds a satisfying assignment and let it halt if it doesn't, or if the input isn't a valid encoding of a $\mathrm{SAT}$ instance.  Now, for any string $x$, $x\in\mathrm{SAT}$ iff $\langle M\rangle,x\in\overline{\mathrm{HALT}}$ so we have a reduction from $\mathrm{SAT}$ to the complement of the halting problem.


recursion code counting down and counting up My apologies in advance if this is going to cause further confusion.  So, I wrote a very simple recursive method shown below. As you see line # 3 keeps track of value of n before recursive call and line # 5 keeps track of n after recursive call. As you can see both lines # 3 and 5 are printed to see the change in n value. I am puzzled why line 5 is printed in increments of one six times where n value goes from 0 to 5 as the unexpected (to me) output shows: "after: n: 0" ... "after: n: 5".

1    def countdown(n)
2      return n if n == -1
3      p "before: n: #{n}"
4      countdown(n-1)
5      p "after: n: #{n}"
6    end
7
8    countdown(5)

Output:

"before: n: 5"
"before: n: 4"
"before: n: 3"
"before: n: 2"
"before: n: 1"
"before: n: 0"
"after: n: 0"
"after: n: 1"
"after: n: 2"
"after: n: 3"
"after: n: 4"
"after: n: 5"

Look at the definition of your countdown function.

If I call countdown (5), then it prints "before: n = 5", then it does lots of stuff including lots of printing, then it prints "after: n = 5" and finishes. So your output must start with "before: n = 5" and it must end with "after: n = 5" and all kinds of things might happen in between.

And that's exactly what happens.


Time complexity of $a^{n^b}; a,b>1$ What ist the time complexitiy of an algorithm with the running time of $a^{n^b}; a,b>1$? And how is it compared to factorial complexity O(n!)?

Let's consider $n!<e\left( \frac{n}{2} \right)^n=e^{n\ln n+1-n\ln2}$. On other hand $a^{n^b}=e^{n^b \ln a}$. Now we should compare $(n\ln n+1-n\ln2)$ to $n^b \ln a$, where right member wins, when $a,b>1$:
$$\frac{n\ln n+1-n\ln2}{n^b \ln a}\to 0$$


Nielsen & Chuang Exercise 3.15: Lower bound for compare-and-swap based sorts From Nielsen & Chuang (page 138):

Suppose an $n$ element list is sorted by applying some sequence of
compare-and-swap operations to the list. There are $n!$ possible initial
orderings of the list. Show that after $k$ of the compare-and-swap
operations have been applied, at most $2^k$ of the possible initial
orderings will have been sorted into the correct order. Conclude that
$\Omega(n \log n)$ compare-and-swap operations are required to sort all
possible initial orderings into the correct order.

The compare-and-swap(j,k) operation is defined as:

compares the list entries numbered $j$ and $k$, and swaps them if they are out of order

Using an inductive argument, I understand that $k$ applications of the compare-and-swap operation sorts at most $2^k$ of the possible initial orderings into the correct order. However, I have trouble drawing the final conclusion from this, specifically that $\Omega(n \log n)$ compare-and-swap operations are required to sort all possible initial orderings.
$n \log n$ steps will sort at most $2^{n \log n}=\left(2^{\log n} \right)^n=n^n \gt n!$ of the possible orderings. So $n \log n$ steps might be enough to sort all possible orderings but I don't see why we need at least this many steps (which is what I think $\Omega(\cdot)$ means)? To me there seems to be a gap between $n^n$ and $n!$ and it's not obvious why there can't be an algorithm which solves the task by covering more than (or exactly) $n!$  but less than $n^n$ orderings?

$\Omega(\cdot)$ means “at least that many steps” _up to a multiplicative constant. There's a gap between $n!$ and $n^n$, and that gap is more than a multiplicative constant. But we aren't looking for an asymptotic bound on the number of length of the list that can be sorted in $k$ steps, but on the minimum number of steps $S(n)$ that it takes to sort a list of length $n$ in the worst case.
You've seen that after $k$ steps, it's only possible to distinguish between $2^k$ different orderings of the list. You've also seen that the total number of orderings of the list is $n!$. The number of steps must be sufficient to distinguish between all orderings, therefore $2^{S(n)} \ge n!$. This condition can equivalently be stated $S(n) \ge \lg(n!)$ where $\lg$ is the logarithm in base $2$.
You want to prove $S(n) \in \Omega(n \lg n)$. (Or maybe $\Omega(n \log n)$ for some different logarithm base, but logarithm bases are equivalent up to a multiplicative constant.) You know that $S(n) \ge \lg(n!)$. Therefore it is sufficient to prove that there is a multiplicative constant $C$ such that for large enough $n$, $\lg(n!) \ge C n \lg n$. Note that this is equivalent to $n! \ge 2^{C n \lg n}$, i.e. $n! \ge n^{C n}$, and the family of functions $n \mapsto n^{C n}$ is not the same as the family of functions $n \mapsto C n^n$.
Stirling's formula, obtained via calculus, can give you a precise approximation of $n!$ from which you can prove the desired asymptotic equality. But here we only need a weak version of it that can be proved more easily. For $n \ge 4$:
$$ \begin{align}
\lg(n!) &= \lg(1) + \lg(2) + \ldots + \lg(n) \\
&\ge \lg \lceil n/2 \rceil + \ldots + \lg(n) && \text{(only sum the larger half of the terms)} \\
&\ge (n/2 - 1) \lg(n/2) && \text{(all terms are larger than the smaller term; count them and round down)} \\
&\ge \left(\frac{1}{2} - \frac{1}{n}\right) \dfrac{\lg(n) - 1}{\lg(n)} \; n \lg(n) && \text{(algebra)} \\
&\ge \frac{1}{8} n \lg(n) && \text{(approximate the complicated factor by a constant)} \\
\end{align} $$
For large enough $n$, $\lg(n!)$ is larger than $n \lg(n)$ multiplied by the constant $1/8$. This fits the definition of $\lg(n!) \in \Omega(n \lg(n))$.


Just another Divide-And-Conquer question - but somehow different Please consider the following Divide-And-Conquer Problem:

  You’re consulting for a small computation-intensive investment
  company, and they have the following type of problem that they want to
  solve over and over. A typical instance of the problem is the
  following. They’re doing a simulation in which they look at n
  consecutive days of a given stock, at some point in the past. Let’s
  number the days i=1,2,...,n; for each day i, they have a price p(i)
  per share for the stock on that day. (We’ll assume for simplicity that
  the price was fixed during each day.) Suppose during this time period,
  they wanted to buy 1,000 shares on some day and sell all these shares
  on some (later) day. They want to know: When should they have bought
  and when should they have sold in order to have made as much money as
  possible? (If there was no way to make money during the n days, you
  should report this instead.)

There already is a discussion about the same problem, but I don't understand why they try to make it that complicated. I think the following Algorithm will yield the result they ask for:

DivideAndConquer(1,..,n)
(i1,j1) := DivideAndConquer(1,..,n/2)
(i2,j2) := DivideAndConquer(n/2 + 1,..,n)
return (min(p(i1),pi2),max(p(j1),p(j2)))

Even if they ask for the range, we can get it from (i,j) := DivideAndConquer(1,..,n) by j-i. So, what am I missing?

PS: I don't see the point of using a DivideAndConquer approch at all. Why not sorting the input twice. Once in ascending and once in descending order induced by p(i).

EDIT: According to the explanation of Yuval Filmus, the algorithm should look like the following:

DivideAndConquer(1,..,n)
(i1,j1) := DivideAndConquer(1,..,n/2)
(i2,j2) := DivideAndConquer(n/2 + 1,..,n)
Let p(i) be minimal in 1,..,n/2
Let p(j) be maximal in n/2 + 1,..,n
return (i,j)

Your solution doesn't work since it could output $i_2,j_1$ which isn't legal since $i_2 > j_1$. Your code also has a few bugs — are you returning indices or stock prices?

The idea behind the divide and conquer solution is that the optimal solution is of one of three forms:

Buy and sell within the first half.
Buy and sell within the second half.
Buy within the first half and sell within the second half.

The first two are taken care of by the recursion, and for the third you just need to compute the minimum of the first half and the maximum of the second half.

There is also a simple (and faster) solution not involving any kind of recursion or sorting. The idea is to scan the array from left to right, keeping at any given point the smallest value seen so far. At any given point in time, you can consider the gain from buying at the smallest price seen so far and selling at the current price. The maximum over all these possibilities is the optimal strategy. This algorithm takes linear time, and can even be implemented online.


Is Co-NP closed under taking subset? I have a question on my homework causing some confusion.

  If L is a strict subset of L', and L' is a member of Co-NP, is L a member of Co-NP? True of False

Now I understand what belonging to Co-NP. Essentially means instead of deciding a yes instance we're deciding a no instance of the decidable problem.  I'm stuck on interpreting L' and what it is.

My guess at this point is that L is a member of Co-NP since it's a subset of L' which we're given is in Co-NP.

For a language $L' \in \mathsf{coNP}$, there are certificates for all NO instances, which is to say inputs $x \notin L'$, which could be efficiently verified and used as proof that $x \notin L$. Suppose that $L \subset L'$: the fact that there are certificates for all NO instances $x \notin L'$ isn't enough to allow us to determine decisively if $x \notin L$, because we could have an input $x \in L' \smallsetminus L$.

Thus, the certificates for $L'$ are not sufficient to provide certificates for $L$, and we cannot conclude that $L \in \mathsf{coNP}$. Indeed, as @G.Bach indicates in the comments, there are examples where $L' \in \mathsf{coNP}$ and $L$ is not even a decideable language. Modifying his example, consider $$ L' = \Bigl\{ x \in \{0,1\}^\ast \;\Big|\; |x| \text{ is prime} \Bigr\}$$
which has certificates for NO instances simply by giving a non-trivial factor for $|x|$ on any input $x \notin L'$. Then $L' \in \mathsf{coNP}$, and indeed $L' \in \mathsf P$: not only because the AKS algorithm puts primality testing in $\mathsf P$, but because (the input being expressed in unary) even trial division would represent an efficient algorithm. However, the language
$$ L = \left\{ x \in L' \;\left| \begin{array}{c} x \text{ encodes a Turing machine} \\ \text{and an input on which it halts,} \\ \text{padded with 0s} \end{array} \right\}\right.$$
using whichever encoding of Turing machines that you like will not even be a decideable language in general, and so it will definitely not be in $\mathsf{coNP}$.


Is $MIN_{TM}$ not in $\overline{RE\cup coRE}$ Given the language:

$MIN_{TM}$= $\{ \langle M,k\rangle: there\ exists\ a\ TM\ D\ s.t.\ L(M)=L(D)\ and\ D\ has\ less\ than\ k\ states \}$

I need to prove if this language is in $R$ or $RE-R$ or $coRE-R$ or $\overline{RE\cup coRE}$.

I suspect this language is in $\overline{RE\cup coRE}$
but I can't prove it. (I Tried using reduction but no help).

Hint 1: What happens when $k=2$?

Hint 2: Use a reduction from $\text{ALL}_{\text{TM}}$.


Exist algorithms without input data? I would like to know cases that an algorithm runs without any data entry.

Yes, of course they exist, and they're useful both practically and theoretically.

Any time you write a computer program to solve some specific task that's hard-coded into the program (for example, to compute some value or find solutions to a specific set of equations you're interested in), that's an algorithm with no input.

If you want to prove undecidability of, e.g., the problem of determining whether a Turing machine halts for every input, the first step is to translate a program that uses its input to a program that doesn't use its input and always computes as if it received some specific input. That's another example of an algorithm without an input.


Halting problem for fixed Turing machine and fixed input It is known that the halting problem is undecidable even when we fix either the Turing machine $M$ or the input $w$.

What if we fixed both the machine and the input? I.e., is it decidable for every fixed Turing machine $M_0$ and every fixed input $w_0$ that $M_0$ will halt on $w_0$ as input?

It is known that the halting problem is undecidable even when we fix either the Turing machine $M$ or the input $w$.

You have to be more careful about this statement. It's not true for any fixed Turing machine $M$ that the halting problem $\text{HALT}_M$ (deciding on input $w$ if $M$ halts on $w$) is undecidable. For example, if $M$ is a machine that always halts, we can easily decide $\text{HALT}_M$ just by outputting "yes".

What you probably meant to say is the following facts, which are true:

There exists a Turing machine $M$ such that the problem $\text{HALT}_M$ (deciding on input $w$ if $M$ halts on $w$) is undecidable.
For all words $w$, the problem $\text{HALT}_w$ (deciding on input $M$ if $M$ halts on $w$) is undecidable.

In particular for fact 1, we can take $M$ to be the universal Turing machine.

  What if we fixed both the machine and the input? I.e., is it decidable for every fixed Turing machine $M_0$ and every fixed input $w_0$ that $M_0$ will halt on $w_0$ as input?

Yes, the problem becomes trivially decidable. Define the language
$\text{HALT}_{M_0, w_0}$ to be the problem of deciding whether $M_0$ halts on $w_0$. But notice that this problem no longer has any input that the answer depends on, as both things that the answer might depend on ($M_0$ and $w_0$) are now fixed, i.e. part of the language definition, not part of the input. That means the answer is just "yes" or "no". So we can trivially decide this problem either by using a program which always says "yes", or a program which always says "no".

This is a common pitfall about decidability: it is only useful to ask whether a problem is decidable or not when the number of possible inputs is infinite. If there are only finitely many possible inputs, then all problems become decidable.
You have asked whether a problem with only 1 possible input (the empty input) is decidable, and the answer to that is always yes.


Linear sorting algorithm I'm trying to understand sorting algorithms. And I'm thinking about a totally different way to tackle sorting: Use array indexes to sort a given set of integers.

Suppose We want to sort a list of positive integers (for now). Let's call it toSortArray

Create a boolean array that has a length equal to maximum integer in toSortArray + 1. Lets call it boolArray. All items in the array are false initially.
Loop through toSortArray and for each integer item, set the boolean at index item true: boolArraty[toSortArray[i]] = true;
Loop through boolArray and if boolArray[i] is true,  set the first element of toSortArray to i

Here is the pseudo-code if the algorithm is not clear:

    var boolArray = new bool[toSortArray.Max() + 1];

    for (int i = 0; i < toSortArray.Length; i++)
    {
        boolArray[toSortArray[i]] = true;
    }

    var index = 0;
    for (int i = 0; i < boolArray.Length; i++)
    {
        if (boolArray[i])
        {
            toSortArray[index] = i;
            index++;
        }
    }

First, Does every body agree that time complexity is O(N)?

Second, Am I missing something about this algorithm (As I don't think I'm the first one thinking about it)?

This is algorithm called bucket sort, integer sort, counting sort, or Pigeonhole sort (naming is a bit inconsistent across sources and/or different names refer to slight variations of the same idea).

Its time complexity is $O(m)$ (assuming distinct values) where $m$ is the largest among the $n$ integers you are trying to sort. Your algorithm takes $O(n)$ time as long as $m=O(n)$, for example if you know you that you want to sort a large-enough subset of the integers from $1$ to $n$.

If the integers are not distinct, you can replace booleans with counters to obtain an algorithm with complexity $O(m + n)$. In general, you can sort arbitrary items with integer keys by keeping an array of lists, where the $i$-th list will contain all items with key $i$. The output is just concatenation of these lists (and hence this sorting algorithm is stable as long as you append new elements at the end of the lists).

If you apply the above (stable) algorithm multiple times on your input, where the $j$-th execution sorts the integers w.r.t. the $j$-th least significant digit you obtain Radix Sort.

For example, in base $10$, you'd need $\lceil \log_{10} m \rceil$ iterations, thus obtaining an algorithm with time complexity $O( n \log m )$, which is in $O(n \log n)$ even when $m$ is exponentially larger in $n$ (on a unit-cost RAM machine). For a general base $b$, the time needed would be $O((b+n) \log_b m) = O((b+n) \frac{\log m}{\log b})$, which is optimized (in an asymptotic sense) by choosing $b = \Theta(n)$, resulting in a time complexity of $O(n \frac{\log m}{\log n})$.


Optimization of Hierarchical Data Propagation I have a system in existence which works on parent-child model.

They share common attributes, as they belong to same class.
A parent can enforces certain data on any user selected attribute, and the data is required to be propagated down the hierarchy for the same attribute in all children and their children.
For a given attribute, if a child's parent dies (object gets destroyed) or child has not been enforced by parent, child can behave the same way, like in point #2, (on user request) for its children.

My system is pretty big (in database). For example:

Each object of the class has 150 atributes.
There are in total about 8 million attributes for objects created. Hence, the objects are close to 53,333.
There is a single parent for the objects. Its a big tree.

If I want to enforce data on the top most parent for a single attribute, it takes about 8 mins for it to complete.

Does anyone know a model which can perform faster than hierarchical model, but similar to behaviour?

I am guessing that you used a technique known as "Adjacency list" to store your tree in the database. However, other solutions are also available, including "Path enumeration", "Nested sets" and "Closure table". The latter one, closure table, is the best one and you may want to design again your database using this technique for storing your hierarchical data.

For more information, see these slides, in particular the section on naive trees which starts at the slide #48. Or, this book from the same author. Finally, a more formal treatment of this subject is also included in this book.


Why is the laplace transform not popular for image processing convolution? Why is the laplace transform not popular for image processing convolution? Most textbooks only conver the Fourier transforms.

The Laplacian is indeed used in image processing routinely but, possibly not as much as Fourier transforms. Reasons (other than just the difference in span of uses, narrow vs wider) may be: Fourier transforms have been highly optimized due to their wide application, and are possibly less complicated theoretically than the Laplacian. sometimes the Laplacian of the Gaussian is taken for "blob detection".[2][3]

From the book Digital signal processing fundamentals By Ashfaq A. Khan p105:

  Convolution is the primarily tool in image processing while Laplace Transform is used mainly in signal processing, such as speech and controls systems.

[1] Laplace filter in image processing (with edge detection and motion estimation applications)

[2] Laplacian in blob detection intuition (mathoverflow)

[3] blob detection


Why do we need a separate notation for П-types? Main
I am confused about the motivation behind the need for a separate notation for П-types, that you can find in type systems from λ2 on. The answer usually goes like so - think about how one can represent a signature of identity function - it can be λa:type.λx:a.x or λb:type.λx:b.x. The subtle part, they say, is that these two signatures not only not equal, they are not alpha-equivalent as type variables a and b are free variables inside their correspondent abstractions. So to overcome this pesky syntactic issue, we present П binder that plays nicely with alpha-conversion.
So the question: why is that? Why not just fix the notion of alpha-equivalence?
UPDATE z:
Oh, silly of me, λa:type.λx:a.x and λb:type.λx:b.x are alpha equivalent. But why a:type -> a -> a and b:type -> b -> b arent then.
UPDATE suc z:
Aha, interesting, I guess this is a perfect example of selective blindness =D
I am reading the book Type Theory and Formal Proof, and in the chapter about lambda2 author motivates the existence of П using exactly that kind of argumentation - one cant say that \t:*.\v:t.v : * -> t -> t because this makes two alpha-equivalent terms\t:*.\v:t.v and \g:*.\v:g.v have different types, as corresponding types are not alpha-equivalent, where types like t:* -> t -> t are in fact alpha-invariant. Mind the difference between t:* -> t -> t and * -> t -> t. But, doesn't it make this argument a bit trivial, and is it even something meaningful to talk about type a -> b where a and b are unbound by any quantifiers variables.
Andrej Bauer pointed out in the comments that П is indeed resembles a lambda abstraction with a few additional bells and whistles.
All in all, I am done with that one, thank you guys.

I think we just need to get some things straight here:

In the expression $\lambda a : \mathsf{type} . \lambda x : a . x$ the variable $a$ is bound (by the outer $\lambda$). The expressions $\lambda a : \mathsf{type} . \lambda x : a . x$ and $\lambda b : \mathsf{type} . \lambda x : b . x$ are $\alpha$-equal.
The expression $\lambda a : \mathsf{type} . \lambda x : a . x$ is the identity function, it is not the "signature of the identity function".
If by "signature of the identity function" you mean to say "the type of the identity function", then it would be something like $\Pi_{a : \mathsf{type}} . (a \to a)$, or if you want only product types, then it is $\Pi_{a : \mathsf{type}} \Pi_{x : a} a$.

Is there still a question?
Maybe this will help:

the type of the identity function $\lambda x : a . x$ is $a \to a$
the type of the identity function $\lambda y : b . y$ is $b \to b$
the functions $\lambda x : a . x$ and $\lambda y : b . y$ are different
the types $a \to a$ and $b \to b$ are different
the type of the polymorphic identity function $\lambda c : \mathsf{type} . \lambda z : c . z$ is $\Pi_{c : \mathsf{type}} . c \to c$.
the functions $\lambda a : \mathsf{type} . \lambda x : a . x$ and $\lambda c : \mathsf{type} . \lambda z : c . z$ are $\alpha$-equal
the types $\Pi_{a : \mathsf{type}} . a \to a$ and $\Pi_{c : \mathsf{type}} . c \to c$ are $\alpha$-equal.

Supplemental: After talking to Alex Simpson over a cup of tea, there is one more thing I can say. We don't need separate $\lambda$ and $\Pi$ constructors, as they both have precisely the same syntactic shape (take two arguments, bind one variable). In fact, if my memory serves me right, Automath used the same notation for $\lambda$-abstractions and $\Pi$-types. But the point is that we want to use two different constructors because they denote different concepts.


Proof of linear search? Consider the searching problem:

Input: A sequence of $n$ numbers $A=(a_1, a_2, \ldots , a_n)$ and a value $v$.
Output: An index $i$ such that $v = a_i$ or the special value NIL if $v$ does not appear in $A$

Write pseudocode for linear search, which scans through the sequence, looking for $v$. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.
The algorithm is clearly very simple to prove. However could someone prove the correctness of the algorithm using a loop invariant? Note the "three necessary properties" are:

Initialization: It is true prior to the first iteration of the loop.

Maintenance: If it is true before an iteration of the loop, it remains true before the

Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

What about using a "goal" variable initialized to NIL and taking as invariant "After iteration i, the goal variable contains an index $0 \leq j < i$ such that $A[j] = v$ if there exists one (in the range $\{0, \cdots, i - 1\}$), or NIL otherwise" ?


center star alignment induces optimal alignments on pairs with the center string? I'm trying to follow the center star algorithm error analysis - section 6.5.3. They claim that for the center string $S_1$ the distance induced by the algorithm $d(1, j)$ is always equal the optimal alignment $D(S_1, S_j)$ since $\delta(-,-) = 0$.

I don't understand this argument. For each j, the algorithm aligns a totally different string $S'_1$ with many surplus gaps from the previous iterations.

How come we arrive to the same exact cost? Can't it be that for the new string $S'_1$ there's a very cheap alignment that would have costed lots of extra gaps if it was $S_1$?

$S'_1$ indeed can have many extra gaps over $S_1$, but it doesn't matter and the distance $d(1,j)$ between the final strings in the MA: $S'_1$ and $S'_j$ would be exactly the same as $D(S_1, S_j)$.

Why? when we start the $j$ iteration, we do an optimal global alignment between $S'_1$ and $S_j$. At first, it looks as if $S'_1$ might contain disturbing gaps, which will cause the distance to get larger than the distance to $S_1$, and helpful gaps which will cause the distance to get smaller than the distance to $S_1$. Let's show that both aren't really helpful or disturbing! suppose S1 = abc:

Disturbing gap - e.g. S'1 = ab_c and Sj = abc. as $\delta(-,-)=0$, whenever we encounter a disturbing gap at $S'_1$ we can just add an extra space to $S_j$ at no cost and get the same distance.

Helpful gap - e.g. S'1 = ab_c and Sj = abxc. It isn't really helpful, as if the global alignment would have wanted to add a gap to $S_1$, it would just add it - it makes no difference that that gap was there before we started the alignment...

Gaps added after the $j$ iteration - if the center star algorithm will add gaps to $S'_1$ in iteration $k > j$, it will always adjust strings from previous iterations with gaps at the same place, including $S_j$ - and again because $\delta(-,-)=0$ it doesn't make any difference.

To summarize - as there's no help or disturbance, the alignment distance would be exactly as the global alignment $D(S_1, S_j)$ would have wanted it, plus some extra aligned gaps which can not disturb our distance.


How to prove intersection between languages L1 (belongs to NP) and L2 (belongs to P) actually belongs to NP? I have to prove that if L <=p L1 intersection L2, where L1 and L2 are described as above, L belongs to NP.

I thought about the definitions of P and NP and built a DTM D that decides L2 and a NTM N that decides L1. Then I tried to build a NTM NN that accepts when both D and N accept on some input w.

Now,did I really prove that intersection between L1 and L2 is in NP by constructing NTM NN? Thx in advance

You can prove something more, intersection of two NP languages is also in NP.

Suppose you have polynomial time non-deterministic turing machines $M_1$ for $L_1$ and $M_2$ for $L_2$. We can modify $M_1$ as follows: Whenever any non-deterministic thread of $M_1$ accepts input string, say $w$, we run $M_2$ on $w$, if $M_2$ then accepts $w$, accept the input, otherwise reject.

The resulting machine is polynomial time non-deterministic.


Is there a way to get O(1) without extra space in the union find algorithm? Is there a way to get O(1) without extra space in the union find algorithm?

Imagine I have 3 sets

set1 = {1, 3, 5, 7}
set2 = {4,20,25}
set3 = {9, 13}

Now imagine I have a new edge between 3 and 20. So I would need to merge set1 and set2, but before I do that I need find which set 3 belongs to and which set 20 belongs to. So how can I get an O(1) find operation to find the set the element belongs to without extra space?

With extra space I can easily store each node and its corresponding set in a hashmap.

Sure, you can make Find run in $O(1)$ time if you allow Union to run in $O(n)$ time.

Suppose the elements are numbered $0,1,\dots,n-1$.  We'll maintain an array $A[0..n-1]$, where $A[i]$ is the set that contains element $i$.  Then a Find operation takes $O(1)$ time, since it consists solely of looking up in the array.  A Union operation can be done in $O(n)$ time by scanning through $A$ to find all elements of both sets and updating the array so that they're both contained in the same set.  Notice that this doesn't use any additional space.

You can replace the array with a hashtable if you prefer, and that will allow items to be identified by arbitrary identifiers (instead of integers $0..n-1$).

This probably isn't useful in practice unless Union operations are extremely rare, because the Union operation becomes so expensive.  In most situations it will probably be preferable to use a standard Union-Find data structure or extra space.


Longest "bounded" subsequence Given a sequence of comparable objects $a_1, a_2, \ldots a_n,$ how quickly can we find the longest subsequence $s$ such that $s_i > s_1$ for $i > 1$?  Or equivalently, how quickly can we find

$$
\underset{i}{\arg\max} \; \# \{j \mid a_j > a_i, i < j \le n \}
$$

Can it be done in less than $\Omega(n\,\lg n)$ comparisons in the worst case?

A $\Theta(n\,\lg n)$ algorithm is to scan from right to left, inserting each element into a balanced tree, keeping track of how many elements in the tree are larger.

This was inspired by this thread on reddit.

No, $\Omega(n\log n)$ comparisons are required. Let $k = \Theta(n)$ be an integer parameter and consider the following family of inputs.

$$k+1,\:k+2,\:k,\:k+2,\:k-1,\:k+2,\:\ldots,\:2,\:k+2,\:1,\:k+2,\:x_1,\:x_2,\:\ldots,\:x_k$$

Note that, for $a\in\{1,\:2,\:\ldots,\:k+1\}$, the maximum bounded subsequence beginning with $a$ consists of $a$, then $a$ copies of $k+2$, then a subsequence of $x_1,x_2,\ldots,x_k$. It is not profitable to begin anywhere else, since the maximum bounded subsequence beginning with $k+1$ has length at least $k+2$.

Let the adversary in this lower bound choose a random permutation $\pi$ on $\{1,2,\ldots,k\}$ and answer as though $x_j=\pi(j)+1/2$. This setting ensures that every maximum bounded subsequence beginning with $a\in\{1,\:2,\:\ldots,\:k-1\}$ has length exactly $k+2$. By the following argument, however, the algorithm cannot be sure of this fact unless it sorts $x_1,x_2,\ldots,x_k$.

Suppose that the algorithm cannot infer the order of $x_i$ and $x_j$. Without loss of generality, assume that $i=\pi^{-1}(\pi(j)-1)$, so that $x_i$ immediately precedes $x_j$ in the imagined sorted order of $x_1,x_2,\ldots,x_k$. It is consistent with the algorithm's observations that

$$x_\ell=\begin{cases}\pi(j)+1/2&\text{if }\ell=i\\\pi(\ell)+1/2&\text{if }\ell\ne i,\end{cases}$$

which would give rise to a bounded subsequence of length $k+3>k+2$.


how to generate all spanning trees from one spanning tree If I have one spanning tree from a connected and undirected graph, how can I generate all other spanning trees of this graph by modifying this spanning tree one edge at a time? All intermediates must also be spanning trees of the graph.

The solution is greatly presented in Knuth's book at 7.2.1.6 (see page 23)


When should you use the existential and universal quantifiers for Relational Calculus? Could someone explain to me WHEN do you use existential and universal quantifiers for Relational Calculus?

Given this schema:

Hotel(hotelNo, hotelName, city)

The expression below gets all hotel names based in London (expressed in Domain Relational Calculus)

$$\mathrm{HotelName|(\exists hNo,cty)(Hotel(hNo,hotelName,cty)\wedge cty=\,\,"\!\!London\!")}$$

Why does the existential quantifier required for this example? Wouldn't this be the equivalent {hotelName | (Hotel(hNo, hotelName, cty) AND cty='London')}

And why is only hNoand cty selected for the existential quantifier? What about the hotelName?

Source: Herts University - Advanced Database Course

This question is related to the very basics of database theory, finite model theory and logics. I would strongly suggest Abiteboul's book on Foundations of Databases, or Libkin's book on Finite Model Theory.

Very roughly stated, a database is a collection of facts, and a query is a logical formula, which is used to specify certain patterns to be matched against the database. The most common database query language is unions of conjunctive queries, which is simply a disjunction of conjunctive queries. These are existentially quantified queries and there is NO universal quantification at all. The query in the question is indeed the simple conjunctive query

$\exists \ x \ {Hotel(x, y, london)} $

where $x$ and $y$ are logical variables and $london$ is a constant. Intuitively, the $x$ variables are to be matched to hotel numbers, and $y$ variables to hotel names. Now, in this formula, $y$ is a free variable, i.e. it is not bound to any quantifier. It is wrong to assume that it is bound to a universal quantifier. Such variables are also called the answer variables as these are the variables for which you want to retrieve answers. Note that $x$ is not an answer variable; so, you are not interested in the hotel numbers. All you want to say with this query is: Give me all the names of the hotels in London! Differently, consider this query

${Hotel(x, y, london)} $

where $x$ is also a free variable. It asks for all names + numbers of the hotels in London. A Boolean query is a special case of a conjunctive query that does not contain any free variables. For instance, the query

$\exists \ x,y \ {Hotel(x, y, london)} $

has no free variables and asks a yes/no question: Is there a hotel in London (with some hotel number and name)? Overall, please have a look at the reference books, and simply learn the query semantics.


Finding maximum rectangular frame in array of zeros and ones I've recently come across a following problem. In a rectangular array of ones and zeros one has to find maximum non-degenerate rectangle whose sides are filled with ones. By "maximum" i mean any rectangle with maximum possible perimeter. By "non-degenerate" i mean that all sides consist of at least two cells. We do not care about the points inside the rectangle. The only requirement is that its sides consist of cells filled with ones.

I know how to solve a similar problem where one needs to find maximum rectangle totally filled with ones (i.e. not only its border, but its interior too). But with this problem i got stuck so any ideas will be highly appreciated. I believe that there is some smart $O(max(m,n)^3)$ solution but can't see it yet.

Thanks in advance.

P.S.
This is not a problem from an ongoing competition, hometask problem or an interview question. The problem originates from KPI-OPEN 2017 competition. You can find original statement here (problem F): http://kpi-open.kpi.ua/problemset/kpi_open_2017_2/eng.pdf

According to bounds on rectangle's size and time limitations there has to be at most cubic (or perhaps cubic-logarithmic) solution. As far as i know there were cubic solutions during the contest.

P.P.S.
There is an algorithm which precomputes for each cell how many cells there are to the left and above it which are filled with ones. Using such precomputation we can easily solve the problem in $O(max(m,n)^4)$ considering all possible rectangles. We just iterate through all possible cells for upper left corner of rectangle and through all possible cells for lower right corner. With the precomputation we might check in $O(1)$ that our rectangle is appropriate and if it is we just update the answer. Unfortunately such approach is to slow.

Yes, it is solvable in $O(\max(m,n)^3)$ time.  In fact, it should be solvable in $O(\min(m,n)^2 \max(m,n))$ time -- e.g., if $m<n$, it should be solvable in $O(m^2 n)$ time.

Let $N_\text{down}(i,j)$ denote the number of cells that you can go down, starting from $(i,j)$, without encountering a zero.  Similarly, let $N_\text{right}(i,j)$ denote the number you can go right.  You can precompute all of these values in $O(mn)$ time.  Do you see how?

Now, I'm going to give you some hints, to help you solve this on your own.  Hint #1:

   Suppose I told you that the left side of the rectangle is at column $j_0$ and the right side is at column $j_1$.  Could you find the top and bottom sides of the rectangle with maximum perimeter?  How efficiently could you find it?

Hint #2:

   Continuing from Hint #1 -- can you identify some necessary and sufficient conditions to recognize the upper-left corner of the rectangle, $(i_0,j_0)$?  What would have to be true about the $N_\text{down}$ and $N_\text{right}$ values?  Similarly for the lower-left corner.

Hint #3:

   Try a linear scan downwards in those two columns.  In fact, all you need are the $N_\text{right}$ values.


Circle Hough Transform. Improvement by knowing edge direction I'm studying Hough Transform.
I have fully understood the HT for detecting lines and successfully implemented it. I have more problems with the circle detection HT.
Given a circle, if the radius is known i have to work in a 2d parameter space (each point in the image space becomes a circle in the parameter space; the intersection of all the circles gives me the center of the image circle).
If the radius is not known the parameter space becomes 3d.
What i don't understand is why if i know the direction of the edges, even if my radius is unknown the parameter space lowers to 2d.

Consider circles of the form

$$(x - a)^2 + (y - b)^2 = r^2$$

The Circular Hough Transform with unknown radius and unknown gradient information has a parameter space $(a, b, r) \in H$. Given a single edge point we'd end up drawing a right cone increasing along the positive $r$ axis with its tip centered at $(x, y, 0)$.

Now to your question. When you know the gradient $\nabla I(x,y)$ of an edge point, $(x,y)$ from your image $I$, you have a vector originating from the center of the circle pointing outward. Since you have your edge point $(x,y)$ the center $(a, b)$ must lie somewhere along the lines $(x,y) \pm r \nabla I(x,y)$. There is only one variable in that statement, $r$.

Now the Circular Hough Transform becomes: for each edge point $(x,y)$, and for each plausible radius $r$, calculate $(a, b) = (x, y) \pm r \nabla I(x,y)$ and increment the accumulator array index $(a, b, r)$ by $1$. Then you go a do your usual vote counting to find the most likely parameters $(a, b, r)$.

For further details refer to D.H. Ballard, "Generalizing the Hough Transform to Detect Arbitrary Shapes" Pattern Recognition. Vol.13. 1981. Extends this concept to ellipses, general analytic curves, and the general transform.


In the Hopcroft-Karp algorithm, what is the purpose of the breadth first search? In the Hopcroft-Karp algorithm for bipartite matching, I don't understand the purpose of the breadth first search.  I think it's used to find a set of vertex disjoint augmenting paths, but I'm not sure what the significance of that is or even what that means.  Why do the augmenting paths have to be the shortest?  And why do they have to be vertex disjoint?

Vertex-disjoint means that no vertex appears in two augmenting paths.  The paths have to be disjoint so that all can be used.  If we have two augmenting paths, P1 and P2, and we augment the matching using using P1, is P2 still an augmenting path for the augmented matching?  Yes, if P1 and P2 are vertex disjoint.

As for minimum length, it has the practical implication that we spend the shortest time looking for augmenting paths, but there is a technical matter, too.  Augmenting paths found this way are guaranteed to be vertex-disjoint.  Look at this text.


Word arrangement in caches Why are the words in a cache line adjacent to one another?
Does this arrangement improve reading/writing performance or are there other reasons to justify this choice?

Because it's common for programs to access data sequentially.

This arrangement of the cache will make sequential data access more efficient.  In particular, when the program accesses the first word, that word and subsequent words in the same cache line are all loaded into the cache, so when the program accesses the next word, it will already be cached and access will be very fast.

Any other arrangement would make sequential access slower.


Proof of NP-completeness of a special case of longest-path problem Problem: Longest Path

Input: An undirected graph $G=(V,E)$

Question: Is there a path of length at least $\frac{|V|}4$?

I know that in order to prove the simple version of $k$ longest path, we reduce the Hamiltonian path to longest path. How we can prove the $NP$-completeness in this special case? Should I use a reduction from Hamiltonian cycle?

Edit: A hint : Reduction from Hamiltonian path. Try to think how many vertices should be added to a special instance $G'$ of Longest path problem so that if there is a path least $\frac{|V|}{4}$ vertices in length then there is a Hamiltonian path in $G$.

We can prove that requiring the graph $G$ to be connected does not decrease the hardness of our problem here.

Reduce from Hamiltonian path between $2$ specified vertices, namely $s,t\in V(G)$

Like before, we want to add new vertices to the graph while keeping it connected.

Now, do some arithmetics:

A Hamiltonian path between $s$ and $t$ is of length $n-1$, where $n=|V|$

If we attach some paths of length (at most) $k$ to $s$ and $t$, then we can increase the length of a path up to $n-1+2k$.

We should have $4(n-1+2k)=|\mathcal{V}|$ in the new graph $\mathcal{G(V,E)}$.

So $|\mathcal{V}|-|V|=3n-4+8k$. Take $k=\sqrt{n}$. Alternatively, attach $s$ and then $t$ and again $s$, etc. to a new short path of length (at most) $k$ (i.e. $k$ new vertices).

The point of setting $k=\sqrt{n}$ is to prevent one from concatenating $2$ short paths attached to the same vertex (either $s$ or $t$). So, one must take one path attached to each vertex among $s$ and $t$. And the middle part of the path is a Hamiltonian path between $s$ and $t$.


How can we prove Schwartz Zippel PIT is applicable to natural polynomials? The naturals lack subtraction, but SZ polynomial identity testing needs subtraction... I think it's applicable, but how to prove it?

Perhaps: SZ shows natural polynomials are equal iff it shows those polynomials are equal over integers. Integer polynomials are equal iff some sequence of algebraic manipulations transforms one into the other. Since these manipulations do not involve subtraction for our case (because no negatives), if they transform integer polynomials, they will also transform two natural polynomials.

But is that a proof? Is it even the right idea?

This question is based on the answer to Is there an efficient algorithm for expression equivalence?

We have two polynomials over the natural numbers. Are they equivalent?

If we take the same polynomials over integers (or some other ring)

$$f=g \implies f-g=0$$

But the reverse is not true, because $f-g$ may have roots, i.e. be zero without $f$ and $g$ being equal. The Schwartz Zippel lemma say how likely we are to have hit a root by chance, with a ramdom guess. By making repeated guesses we can be as sure as we like that we didn't get a root every time, (And if we ever get a non-zero, we know $f\neq g$.)

I've tried to simplify the question here, to focus on just one aspect, but maybe I've got it wrong and/or omitted important details.

Suppose that $P$ is a multivariate polynomial with integer coefficients. Then $P$ vanishes on all natural inputs iff it vanishes on all integer inputs. You can prove this by showing that if $P$ is not the zero polynomial then there is a natural input on which it is non-zero. This, in turn, you can prove by induction on the number of variables.

The base case is when $P$ is a univariate polynomial. In this case it is not hard to check that $P$ is non-zero for sufficiently large integer input. Suppose next that $P$ is a $(d+1)$-variate polynomial. Choose one variable $x$ which appears in some monomial of $P$, and write $P$ as a univariate polynomial whose coefficients are $d$-variate polynomials. Suppose that the highest power of $x$ that appears in $P$ is $x^n$, and that the corresponding coefficient is the $d$-variate polynomial $Q$ in the other variables. The induction hypothesis shows that there is an input on which $Q \neq 0$. Applying the base case again, we find a non-zero input for $P$.


MAX3SAT proof help? Showing that NP = coNP iff MAX3SAT is in NP For a 3CNF $\phi$, denote by $c(\phi)$ the largest number of clauses satisfied under an assignment. Define:

$\mathrm{MAX3SAT} = \{\langle\phi, k\rangle\mid c(\phi) = k \text{ and }\phi\text{ is a 3CNF}\}$.

Prove that NP = coNP if and only if MAX3SAT is in NP.

I've been working on this forever and can't seem to figure out anything. Any help?

Let's start by describing a polytime reduction $f$ that takes a 3CNF $\varphi$ to another $f(\varphi)$ such that:

$\varphi$ is satisfiable iff $f(\varphi)$ is satisfiable.
We can always satisfy all clauses of $f(\varphi)$ but one.

The idea is very simple: add a new variable $x$, replace each clause $\alpha \lor \beta \lor \gamma$ with 3CNF clauses equivalent to $x \lor \alpha \lor \beta \lor \gamma$ (i.e. with the clauses $x \lor \alpha \lor \lnot T$, $T \lor \beta \lor \gamma$ for a new variable $T$ appearing only in these clauses), and add the clause $\lnot x$. We can always satisfy all clauses but the last by having setting $x$ and all $T$ variables to true. On the other hand, the entire 3CNF is satisfiable if and only if the original one is.

We deduce that $\varphi$ is unsatisfiable iff $c(f(\varphi)) = |f(\varphi)|-1$, where $|f(\varphi)|$ is the number of clauses in $f(\varphi)$. This shows that MAX3SAT is coNP-hard. So if MAX3SAT is in NP then NP=coNP.

Conversely, as observed by David Richerby, MAX3SAT is in the polynomial hierarchy (indeed, in $\Delta_2^P$) since $c(\varphi) = k$ iff some assignment satisfies exactly $k$ clauses, and all assignments satisfy at most $k$ clauses. If NP=coNP then the polynomial hierarchy collapses to the first level (i.e. NP), and so MAX3SAT is in NP.


Scheduling: Existence of specific total order A question arising from a scheduling problem:
I have a finite set $X$ with elements $x_i$ and some preorder $\leq$.
I have pairs $p_j$ of $x_i$ (i.e. $p_j$ = $(x_k, x_l)$) with the property that $x_k \leq x_l$.
I say that for two pairs $p, p'$ : $p \leq p'$ when for all $x \in p, x' \in p': x\leq x'$.
I call two pairs $p = (x_1, x_2), p' = (x'_1, x'_2)$ unrelated if for no $x \in p$, $x' \in p'$ holds: $x \leq x'$ or $x' \leq x$.

Question: Does there always exists a total order $\leq'$ of $X$ which is compatible with $\leq$, with the property that $p \leq' p'$ or $p' \leq' p$, for all unrelated pairs $p, p'$?

To give an example:

$X = \{1,2,3,4,5\}$ , $p_1 = (1,2), p_2 = (3,5)$ and a partial order (preorder) $1 \leq 2, 3 \leq 5$. E.g. by topological sorting I can obtain a total order ($ 1 \leq 2 \leq 3 \leq 4 \leq 5$) which satisfies $p_1 \leq p_2$. However, tsort can also give me the total order ($1 \leq 3 \leq 2 \leq 4 \leq 5$), which does not satisfy $p_1 \leq p_2$ or $p2 \leq p1$ (here, $\leq$ refers to the corresponding total orders).

The relation to a specific scheduling problem is that I have undetermined times $x_i$ at which I acquire or release a resource. To avoid deadlocks, the pairs of (acquisition, release) must not overlap.

(In the actual problem, some time $x_i$ can occur in multiple such pairs, but that's another problem not considered here).

UPDATE

I think I found at least some idea, yet not sure if it is correct:
The graph below shows the general structure of such a preorder (which we now treat as a directed acyclic graph): Given two such pairs $(x, x')$ and $(y, y')$, there is a path from $x$ to $x'$ (and from $y$ to $y'$). There may be nodes in-between, and edges connecting to that path. However, by our assumption that the pairs are unrelated, none of the incoming or outgoing edges in the section $x \to x'$ can reach $y$ or $y'$.
We can now start constructing a topological sort. Without loss of generality, we reach $x$ as the first node of all pairs which we consider (which is not necessarily unique, but that does not matter). Because there are no edges between $x$ and $x'$ which connect from/to another point $y$ from another pair, we can continue our topological sort until we reach $x'$. Then, the pair $(x, x')$ is "compact" in our final order, that is, will have a $\leq'$ relation to all other pairs (because no point of any other reservation is between $x$ and $x'$, by construction of the total order $\leq'$). We can repeat this procedure every time we reach the first point of such a pair.

Is there any flaw in this argument?

I think you mean partial order, as if you only have a preorder then there might not even exist any total order that is compatible with it.

Your argument seems to be missing something about how you construct your topological sort, as it implies that any topological sort works, which you disproved yourself. In your example $x,y,x',y'$ could be a topological sort.

Here is an other attempt at a proof:

Let $\leq$ denote a partial order on $X$. I claim there exists a total order $\leq'$ compatible with $\leq$ such that the following never occurs:
$a\leq'\alpha\leq'b$
where $a \leq b$, and $\alpha$ is incomparable to both $a$ and $b$.
(Note that when I say comparable/incomparable I always mean with respect to $\leq$)

To see this choose a compatible total order $\leq'$ with the least amount of such "bad" pairs $(a\leq b)$. Suppose that this amount is non-zero and let $(a\leq b)$ be such a pair with smallest $a$ (with respect to $\leq'$). Let $\alpha_1 \leq' \alpha_2 \leq'\ldots\leq'\alpha_k$ denote all elements between $a$ and $b$ which are incomparable to both $a$ and $b$.

Now create a new total order $\leq^*$ from $\leq'$ by moving all $\alpha_i$'s right in front of $a$ to get $\alpha_1 \leq^* \alpha_2 \leq^*\ldots\leq^*\alpha_k\leq^*a$, the rest remaining unchanged. Notice that this is still compatible with $\leq$, as the only thing that could have gone wrong is that there was some $a\leq c \leq \alpha_i$ but this is impossible as $a$ and $\alpha_i$ are incomparable.

Notice also that, because all elements between $a$ and $b$ (with respect to $\leq^*$) are now comparable to $b$, we have created no "bad" pair $(\alpha_i\leq x)$ with $a\leq^* x \leq^* b$, otherwise we would have $\alpha_i\leq x \leq b$ meaning that $\alpha_i$ and $b$ are comparable. And we have created no "bad" pair $(x\leq a)$, otherwise $(x\leq b)$ would have been a bad pair to start with, contradicting our choice of $a$. Any other type of "bad" pair we created must have already existed previously.

Because $(a,b)$ is no longer a bad pair, $\leq^*$ has strictly less bad pairs than $\leq'$, which is impossible by definition of $\leq'$. Thus, $\leq'$ had no bad pairs to start with.

It is easy to show from here that $\leq'$ meets your requirements.


Constraint violation and efficiency in search It seems that (in a broad sense) two approaches can be utilized to produce an algorithm for solving various optimization problems:

Start with a feasible solution and expand search until constraints are tight and solution is maximal (or minimal).
Begin with violated constraints and search for maximal (or minimal) feasible approach.

For the Max-Flow problem Ford-Fulkerson satisfies condition (1), while Push-Relabel satisfies condition (2). An interesting point is that Push-Relabel is a more efficient algorithm than Ford-Fulkerson. My question is this:

  What other examples are there where (2)-based approaches outperform their (1)-based counterparts?

A follow up is:

  Do there exist meta-theorems regarding approaches based on condition (2)?

Another example is interior-point algorithms for convex optimizations, which (if I remember correctly) start at an arbitrary point and try to simultaneously get into the feasible region and optimize the objective function. They are provable and (to some extent) practically faster than the simplex algorithm (and related algorithms like the criss-cross algorithm), which does a local search inside the feasible polytope.


How to iterate through all values of an array? I'm trying to implement a brute-force algorithm.

If I have one variable x, I can iterate through all its values using a for loop:

for x in {1,2,..,MAX}:
    do something with x

But what if I have an array A?  The array has length SIZE, and each element takes values in the range 1..MAX.  Thus, there are MAX^SIZE possible values of this array.  How do I iterate through all such possible values?

I'm asking for an algorithm, not an implementation on a particular language. Both MAX and SIZE are arguments.  SIZE is not fixed, so I can't just create a set of nested for-loops (the number of for-loops that would be needed isn't fixed in advance and depends on the value of SIZE).

There are several approaches.  I will use 0-based indexing (so array elements are in the range 0 .. MAX-1) rather than 1-based indexing (range 1 .. MAX), for ease of notation.

Treat as an integer

You can treat the contents of an array as an integer in the range 0 .. MAX^SIZE - 1, expressed in base MAX.  For example, the array with contents [0, 3, 1] corresponds to the integer 0 * MAX^2 + 3 * MAX + 1.  Conversely, each such integer corresponds to an array.

Of course you can iterate through these integers by starting at 0 and incrementing until you reach MAX^SIZE - 1.  Now by expressing that integer in base MAX, you can convert the integer to an array, and thereby iterate through all possible values of the array.

Depth-first search

You can view this as a complete tree of depth SIZE, where each internal node has branching factor MAX.  Each leaf of the tree corresponds to a value of the array.  Then, you can iterate through the leaves of the tree following any standard tree traversal algorithm.

Direct iteration

To iterate through these arrays, it suffices to create an order on the arrays and build an algorithm to advance from one array to the next-largest array.  For this, you can use lexicographic order.  The smallest (first) such array is the all-zeros array [0, 0, ..., 0].

Given an array A, you can advance to the next array in lexicographic order via a simple procedure.  Basically, you increment the last element of the array; if that becomes too large (equal to MAX), it wraps around to 0, and then you increment the next-to-last element of the array (continuing if it wraps around).  If you think about it a bit, this is basically equivalent to the "treat as an integer" solution.

Running time

All of these methods have basically the same running time.  Asymptotically they all require approximately MAX^SIZE operations.  Depending on representation and implementation details, direct iteration might be slightly faster, but the differences are likely to be minor.

(The fine print: depending upon implementation details, the running time of the "treat as an integer" method might be more like SIZE * MAX^SIZE.)

There's no algorithm that can iterate through all values of the array in less than MAX^SIZE operations (as the number of possible arrays is a lower bound on the time to iterate through them all), so there's no hope for an algorithm that is significantly better.


Starvation is possible or not? let S and Q to be initialized to 1

process p0:          process p1:

wait(S);             wait(Q);
wait(Q);             wait(S);

..                    ..
..                    ..
Signal(S);           Signal(Q);
Signal(Q);           Signal(S);

I know there is a deadlock , where both the process will be going into the sleep , so what about starvation and bounded waiting?

My approach:

as only p0 can be executed any number of times i think there will be starvation and no bounded waiting.But answer is given that there is No Starvation.

The answer is wrong.

Deadlock implies starvation, and the given code suffers from deadlock, here's how.

Say p0 executes wait(S); and then p1 executes wait(Q);. Now both the semaphores S and Q have value = 0.Now p0 will keep on waiting due to statement wait(Q); and p1 will keep on waiting due to statement wait(S);.

Freedom from starvation means that:

  if a thread tries to acquire a lock , it will eventually succeed.

This does not happen here, so the answer is wrong.


Problems that are Cook-reducible to a problem in NP $\cap$ co-NP Let $\mathcal{A}$ be a problem in $\text{NP} \cap \text{co}$-$\text{NP}$.

Now assume we can reduce another problem $\mathcal{B}$ to it using Cook reduction.

What conclusions can we draw about $\mathcal{B}$? Does this question even make sense?

I'm asking because from what I understand Cook reductions differ from Karp reductions (for example, $\text{NP}$ cannot be distinguished from $\text{co}$-$\text{NP}$).
I'm pretty confused and can't seem to really understand the properties of Cook reductions. Any good reference about the topic would also be appreciated!

I hope this question is not too basic, but I was not able to find anything about it.

Nice question/homework!

Stated in another way: $\mathsf{NP}$ is not closed under Cook reductions (assuming $\mathsf{P}\neq \mathsf{NP}$).

How about $\mathsf{NP}\cap\mathsf{coNP}$? Is $\mathsf{NP}\cap\mathsf{coNP}$ closed under Cook reductions? Is the only reason that $\mathsf{NP}$ is not closed under Cook reductions is because it is not closed under complement so if we take those $\mathsf{NP}$ problems whose complement is also $\mathsf{NP}$ do we get around the problem?

For example, if we have a Cook reduction from a problem to Factoring, would that mean that the problem is in $\mathsf{NP}\cap\mathsf{coNP}$?

An oracle doesn't just allow us to ask about membership and non-membership in the oracle, it allows us to ask very complicated list of questions where each question can depend on the answer for the previous one.

Let's look at a problem $Q \in \mathsf{P^{NP \cap coNP}}$. We know that there is a polynomial-time algorithm $M$ and a set $A\in \mathsf{NP \cap coNP}$ such that $M^A$ solves the problem $Q$. Is $Q$ in $\mathsf{NP}$?

Hint: when does $M^A$ accept an input $x$?

Don't read the answer below if this is an assignment, the answer is not difficult, you should be able to solve it if you spend a few hours on it, and spending those hours is what makes you learn.

   Let's look at the execution of $M^A$ on an input $x$.
 $M$ will make a number of queries to $A$ during its computation and will receive YES and NO answers, and finally will accept or reject.
 If we could compute that answers to the queries in polynomial time we would have shown that the problem is in $\mathsf{P}$,
 we would simulate the algorithm $M$ and whenever it asked a query from $A$
 we would compute the answer and give to $M$ and continue with its simulation.

 But $A\in\mathsf{NP \cap coNP}$ and we don't know how to compute the answers to queries in polynomial time. But we don't need to do this in polynomial-time! We can just guess the answers to the questions and verify our guesses in polynomial-time. To be able to verify the answers for both positive and negative answers we need $A\in\mathsf{NP\cap coNP}$, that is why this does not work for $A \in\mathsf{NP}$, that would allow only verifying positive answers.

 Let $V_{YES}$ and $V^{NO}$ be two polynomial-time verifiers for membership and non-membership in $A$. Consider the verfier $V(x,y)$ which works as follows:

  I. check that $y$ consists of 1. a string $c$ (computation of $M$ on $x$), 2. a list of strings $q_1,\ldots,q_m$ (queries to the oracle in $c$), 3. a list of strings $a_1,\ldots,q_m$ (answers to queries from oracle), 4. a list of strings $w_1,\ldots,w_m$ (certificates/proofs/witnesses for the correctness of the query answers).
  II. check that the list of queries $q_1,\ldots,q_m$ contains all oracle queries in $c$,
  III. check that the computation $c$ is an accepting computation of $M$ on $x$ if answers to the queries are $a_1,\ldots,a_m$.
  IV. for all $1\leq i \leq m$, check that if $a_i=YES$ then $V^{YES}$ accepts $(q_i,w_i)$ and if $a_i=NO$ then $V^{NO}$ accepts $(q_i,w_i)$.

  All of these steps can be checked in polynomial-time. So we have a verifier for YES answers of $M^A$. Furthermore note that if $M^A$ accepts $x$, then there is $y$ satisfying these conditions which has polynomial-size: the computation of a polynomial-time machine is of polynomial-size and the number of queries and the size of all queries are also polynomial in the input. Moreover the size of certificates for queries are also bounded by some polynomial in the size of the queries, so again are polynomial in the size of input. In short we have a polynomial-time verifier with polynomial-size certificates for $M^A$.

  This completes the proof that $Q \in \mathsf{NP}$. A similar argument shows that $Q\in\mathsf{coNP}$. So $Q\in\mathsf{NP\cap coNP}$. In other words, $\mathsf{P^{NP\cap coNP}} \subseteq \mathsf{NP\cap coNP}$.


Are there NP languages whose verification is P-complete? A decision problem is in NP if a candidate "yes" can be verified in polynomial time.

Are there decision problems whose "yes" is verified with an algorithm that is P-complete (reducible in logspace)? Are those problems in NP?

If so, can the "yes" be verified in logspace?

I'm told "for every NP language we can find a verifier that uses only logspace."

Every language in NP has a logspace verifier.

Indeed, let $L$ be any language in NP. Therefore, there is a polynomial time machine $T$ and a polynomial $p$ such that $x \in L$ iff some string $y$ of size at most $p(|x|)$ makes $T(x,y)$ accept.

While the witness $y$ may be hard to check, we can make help a logspace machine verify it by including the transcript of the accepting computation. We construct another machine $T'$ which accepts a new witness $z$. The witness $z$ consists of a sequence of configurations of the machine $T$, starting with an initial configuration encoding $x$ and $y$, and ending at an accepting configuration. Since each configuration has polynomial length, a logspace machine can verify that $z$ indeed consists of a valid sequence of configurations.


Represent a real number without loss of precision Current floating point (ANSI C float, double) allow to represent an approximation of a real number.
Is there any way to represent real numbers without errors?
Here's an idea I had, which is anything but perfect.
For example, 1/3 is 0.33333333...(base 10) or o.01010101...(base 2), but also 0.1(base 3)
Is it a good idea to implement this "structure":

base, mantissa, exponent

so 1/3 could be 3^-1

{[11] = base 3, [1.0] mantissa, [-1] exponent}

Any other ideas?

There is no way to represent all real numbers without errors if each number is to have a finite representation. There are uncountably many real numbers but only countably many finite strings of 1's and 0's that you could use to represent them with.


I don't get why the time complexity of insertion on a linked list is O(1) I was watching the algoritmhs course by mycodeschool and he said that when we add a new item on a given position the worst case would be $O(n)$. Everywhere I look says insertion is $O(1)$...
Now I understand that insertion itself might be $O(1)$, but if I have the following interface (this is something I made up, not a real thing I'm working):
insertAtIndex(any item, int index)

Would this be $O(n)$? Since I will search $O(n)$ and then insert $O(1)$?
Thanks!

That is correct. There is no random indexing in a linked list so you will have to traverse it from the start until you reach the right index, requiring a $O(n)$ search. After that you have $O(1)$ reference/pointer bookkeeping for the insertion operation.


How to write program to list all the function values without repeating? Suppose I have a (recursive) function $f:\Bbb N\rightarrow\Bbb N$ whose range is infinite, and I want to list all the function values without repeating.

That is, if $f(0)=1,f(1)=1,f(2)=5,f(3)=6,f(4)=6,f(5)=2$, I need a program with outputs $1,5,6,2$ I need it to firstly list $1$, then $5$, then $6$ and then $2$.

My idea is: Start from $0$, firstly output $f(0)$, and then increase $0$ by $1$ to get $1$, look at what is $f(1)$, if it is equal to $f(0)$, then we do not output it, otherwise we output $f(1)$. And then look at $f(2)$, if it is equal to at least one of $f(0),f(1)$, then we do not write it out, otherwise we output $f(2)$. But so far I found my knowledge too poor to write a program in psudocode...

My attempt:

x := 0;

while (n < x)

{ if (f(n)=f(x));

 n := n+1;

else

return f(x)}

I think maybe this code is problematic. Could someone please tell me some way to write it? This is such a minor part of my math course that we are not taught how to write psudocodes and now I feel a bit frustrated...

Other simple ways to do it would also be appreciate. Thanks in advance to you all who may help!

To sum up, I wish to see a psudocode to out put all the values of the function:

$f':\text{n↦the nth value in the enumeration that isn't a repeat of a previous value}$
 where $f$ is a recursive function. Apologize for my poor knowlege of computing. I have no backgroud of computing and even not know what is "memory", only psudocode is readable for me... And actually I just need the psudocode program to prove that this function is recursive.

Thank a lot to you all who leave answers and comments!

You can implement your task by keeping track of the values that have appeared so far. You maintain an array $S$ that starts empty. You compute the values $f(0),f(1),f(2),\ldots$, and for each value, you check whether it is already in $S$; if so, you don't do anything; otherwise, you print it, and add it to $S$.


Looking for cheat sheet to J.C. Reynolds symbols Most specifically, his use of small epsilon introduced at the end of section 1 of "Types, Abstraction and Parametric Polymorphism" is throwing me, but in general I would like references to symbols in the Type and Logical Relations literature.

You aren't going to find a list of all notations ever used. Apart from a few standard notations, each paper will define the notation that it uses.

This paper is from the dark ages of typewriter typesetting, so the typographic quality is subpar. The character ε stands for $\in$, which is the standard mathematical notation for set membership.


How do I find my wife in a supermarket? If two people are lost in a maze, is there an algorithm that they can both use to find each other without having previously agreed what algorithm they will be using?

I think there are some characteristics that this algorithm will have:

Each person must be able to derive it using logic that makes no assumptions about what the other person is deciding, but as each person knows the other is in the same position they may make deductions about what the other must be deciding.
An identical algorithm must be derived by both people as there is total symmetry in their situations (neither has any knowledge about the starting position of the other, and the maze is a fixed size, and fully mapped by both).  Note that the algorithm is not required to be deterministic: it is allowed to be randomized.

This is called rendezvous problem.

As the paper: Mobile Agent Rendezvous: A Survey mentioned, this problem is original proposed by Alpern: The Rendezvous Search Problem:

  Two astronauts land on a spherical body that is much larger than the
  detection radius (within which they can see each other). The body does
  not have fixed orientation in space, nor does it have an axis of rotation,
  so that no common notion of position or direction is available to
  the astronauts for coordination. Given unit walking speeds for both astronauts, how should they move about so as to minimize the expected
  meeting time T (before they come within the detection radius)?

In the survey paper above,

  Abstract: Recent results on the problem of mobile agent rendezvous on distributed networks are surveyed with an emphasis on outlining the various approaches taken by researchers in the theoretical computer science community.

It covers both "Asymmetric Rendezvous" (in Section 4) and "Symmetric Rendezvous" (in Section 5).

For symmetric rendezvous, the paper by Alpern shows:

  It is shown how symmetries in the search region may hinder the process by preventing coordination based on concepts such as north or clockwise.


HOG vs. neural networks for person detection I am very new to computer vision, (a high school student) and I am working on a project to count the number of people present in a room. I have tried to use the HOGDecriptor for person detection provided by OpenCV (HOGDescriptor_getDefaultPeopleDetector()) but it is very inaccurate, understandably. I was thinking that it may be advantageous to train my own system, since each camera setup would be specific to a certain room. This would greatly restrict the bounds of what the computer has to recognize. (What I mean by this is that if I am analyzing a conference room, little about the environment changes, other than the addition of people. This would limit the scope of the detection problem.)

My question is whether to use a HOGDescriptor or a Neural Network. I was planning on using a HOGDescriptor but was advised that a Neural Network may be more accurate. At the same time however, the way I understand a Neural Network works is that I provide the number of input neurons as well as the number of output neurons, and the training algorithm creates the hidden neurons in between. The problem with this approach is that I would like to be able to count an arbitrary number of people in the camera frame, and thus I could not provide the training algorithm with a definite number of end neurons. I addition, I am able to mark frames positive or negative (whether or not they include people in them) quite easily, but providing the description of the number of people in them would be significantly harder. For both these reasons, it would seem to me that HOGDescriptors would work better, because they do not need to be told how many people are in the frame, and they can create an arbitrary number of "end neurons."

Any help clarifying the benefits of both technologies, as well as advice on which to use, would be greatly appreciated. I realize that this question might be very elementary, but I am willing to learn and will take all responses very seriously. Thank you.

Unfortunately, this remains a very challenging problem, that even state-of-the-art techniques find difficult to do accurately.  It's probably too hard for a high school project.

The closest work is probably on "pedestrian detection".  Do a search on Google Scholar, and you should find a bunch of research papers on this from the computer vision community.  However, the state-of-the-art techniques are complex, and even the best techniques aren't super accurate.

You should also read about "object detection", "object recognition", and related topics.  That will give you the basics of how to use machine learning (like neural networks) to recognize the location of objects in an image.  One standard technique is to crop out a small rectangle from the image, use your classifier to check it contains the object you're looking for (e.g., a person), and then repeat this for many crops of many different regions of the image -- this tells you the location of all people.  There are other approaches as well, based on regression to infer the location of the object.

You might find Stanford's CS231N useful for learning more about these techniques.

For your specific problem, doing this in the general case is probably too hard.  I'd advise you to look for a way to make the problem easier.  One way is to make the problem more constrained and place your cameras carefully to make the machine learning problem easier.

For instance, if the room is a lecture hall where everyone will be seated and facing the same direction, you could experiment with placing a camera that will see everyone from the front, and using facial detection to identify and count the number of faces in the image.  Or, you could place a video camera at each entrance and exit and use facial detection or other methods to try to recognize people when they are entering/leaving the room, and count the number who have entered and the number who have left.  This will probably be easier if you have two video cameras over each door: one on the outside pointing in, and one on the inside pointing out.  Or, you could experiment with entirely different sensors, such as a FLIR camera which can see in the infrared.  People are warm and glow in the FLIR wavelengths, which might make it easier to distinguish people from other elements of the scene.


Why is the halting problem decidable for LBA? I have read in Wikipedia and some other texts that

  The halting problem is [...] decidable for linear bounded
  automata (LBAs) [and] deterministic machines with finite memory.

But earlier it is written that the halting problem is an undecidable problem and thus TM can't solve it! Since LBA are defined as a type of TM, should the same not hold for them?

The halting problem is solvable for any Turing machine which uses a known bounded amount of space, by a generalization of the argument given by Yonatan N. If the amount of space is $S$, the alphabet size is $A$, and the number of states is $Q$, then the number of possible configurations is $QSA^S$. If the machine halts then it must halt within $QSA^S$ steps, since otherwise, by the pigeonhole principle, it has a repeated configuration and so is stuck in an infinite loop. Therefore to determine whether the machine halts, we just run it for $QSA^S$ steps and see whether it halts within that time frame.


How to prove prove $L(G) = \{~w\in\{a,b\}^*~|~\#_aw= \#_bw\}$ for my CFG $G$? For language $L = \{ x \in \{a,b\}^* \mid \#_a x = \#_b x \}$, I came up with the following CFG:
$$S \rightarrow aSbS \mid bSaS \mid \varepsilon.$$
It can be easily shown that it is correct (quick example, for string $x = aabb$ we have these derivations: $S \rightarrow aSbS \rightarrow^* aaSbSb\varepsilon \rightarrow^* aa\varepsilon b \varepsilon b \rightarrow aabb$). Then I was asked to provide a mathematical proof, which is more like to be intended as a formalism, to prove, indeed, the correctness of such CFG.

Arguably, by induction, one could assume it holds that $\forall k\leq n$, $|x| = 2k$ and then test a string $x$ with number of characters $|x| = 2n + 2$. So string $x$ is in the form of $x = au'bu''$. But now how can I show that $u'$ and $u''$ still contain an equal number of $a$'s and $b$'s? Sorry if I'm missing something and might be easier than I think.

There are two implications involved in the correctness. Every string in $L$ can be derived by the CFG (completeness) and every string derived by the grammar belongs to $L$ (consistency). I think you want an argument to formalize the first implication by induction.

Assuming the string $x\in L$ starts with an $a$, there must be a position with letter $b$ such that the string is of the form $aubv$ such that the $\#_a(u)=\#_b(u)$. The argument I know is by counting. Read the letters in $x$ one by one, and add $1$ for each $a$, subtract $1$ for each $b$. As the number of $a$'s equals the number of $b$'s, the count starts and stops with $0$. The counts becomes $1$ after the first letter, and must drop back to $0$ at some position with a $b$. In between we have seen an equal number of $a$'s and $b$'s.

Now that $x=aubv$ with $x\in L$ and $u\in L$ it is easy to argue that also $v\in L$.


Undirected graph with exponential number of simple cycles Hey I am new to graph theory and this question has me stuck for hours.

What is an example of undirected graph with n nodes where the number of simple cycles is exponential in n.

I was looking at complete graphs, but here's the catch: the total number of edges should be in theta of n.

Please help! I need to prove the correctness of such a graph but I can't find an example of the graph in the first place.

The graph below contains $3m+1$ vertices and at least $2^m$ simple cycles (illustration has $m=3$):


Citation for finding node disjoint paths using maximum flow We can find  the maximum number of vertex disjoint paths in a directed graph using maximum flow algorithm keeping the node capacity and edge capacity to one. I could not find the reference paper for this technique. Please let me know the citation for this technique.

This reduction appears in §4 (Menger's theorem) of ON THE MAX-FLOW MIN-CUT THEOREM OF NETWORKS, G. B. Dantzig and D. R. Fulkerson without citation to another work. It's possible that this was a reinvention, but it's not clear to me where to look next.


How to prove the union of languages recognized by a set of turing-recognizable Turing machines is also turing-recognizable? Let $G = \{\langle M_1\rangle, \langle M_2\rangle, \langle M_3\rangle,\cdots\}$ be an infinite turing recognizable language, whose members are descriptions of turing machines.

How can one prove that the union of all the languages recognized by the turing machines in $G$, $L(M_1) \cup L(M_2) \cup L(M_3)\cup\cdots $ is turing recognizable?

I tried to prove it by building an enumerator for the language, using the fact that since $G$ is turing recognizable it can be produced by one.

E' =
1. Initialize steps counter i=0
2. Run E, the enumerator of G, number of steps equal to i.
3. For every turing machine description M produced by E:
   3.1 for every input word corresponding to 0 up to i according to lexicographic order do:
      3.1.1 Run M on the current input.
      3.1.2 print if M accepts.
4. increase i by 1, and go back to step 2.

Is this a correct approach? Running the enumerator for a limited amount of steps would produce the same words over and over again. Is this not a problem when creating an enumerator? Is $E'$ valid and producing the language as needed? If not, what should be changed?

Your enumerator is incorrect. Because there are infinitely many Turing machine descriptions in $G$, the loop corresponding to Line 3 will not halt, so i will never be increased. Also, Line 3.2 may not halt too.

The correct enumerator is:

E' =
for i = 1 to infinity:
    Run E, the enumerator of G, to get the ith description of Turing machine <Mi>
    Build an enumerator Ei for Mi
    for j = 1 to i - 1:
        Run Ej to get the ith string, print it
    Run Ei to get the first i strings, print them

Suppose $E_i$ prints $s_{i1},s_{i2},\ldots$ in order. Then after $i$ iterations, $E'$ would have printed $s_{11},\ldots,s_{1i},s_{21},\ldots,s_{2i},\ldots,s_{i1},\ldots,s_{ii}$ (note this is not the order they are printed), and would print $s_{1(i+1)},s_{2(i+1)},\ldots,s_{i(i+1)},s_{(i+1)1},\ldots,s_{(i+1)(i+1)}$ in order in the $(i+1)$th iteration. Of course, before printing a string, you can check if it has been printed to avoid duplicates.


How precise to be when describing a Turing machine? I'm kind of new to the theory of computation and I was working on this problem:

  We say that a Turing machine $M$ uses $k$ squares of tape for an input string $w$ if and only if there exists a configuration $(q, u\underline{a}v)$ of $M$, such that starting with input $w$, $M$ yields $(q, u\underline{a}v)$ and $|uav| \geq k$.

  Now show that the following problem is solveable: Given a Turing machine $M$, an input string $w$ and a number $k$ does $M$ use $k$ squares of tape with input $w$?

So the solution I came up with is this:

If it is solvable there has to be a Turing machine $M^*$ that decides $$U = \{\ll M\gg\ll w \gg \ll k\gg\ :M\ \text{uses}\ k\ \text{squares of tape with input}\ w\}$$

And I describe such a machine:

$M^*$ writes in it's tape $w$ and starts operating as $M$ would. After each step of $M$, $M^*$ counts the number consecutive squares of tape from the start of the tape until it finds an empty square, and if that number is $\geq k$ it goes into an accept state and halts. If not, it continues its operation as M would. If $M$ halts without having used at least $k$ steps, $M^*$ goes into a reject state. So $M^*$ decides $U$, and thus the problem is solveable.

So my questions are these:

Is my solution correct?, and

Is my description of $M^*$ precise, or say, good enough?

You are asking two different questions: whether your solution is correct, and whether the level of description of your Turing machine is appropriate. I will answer them separately.

Correctness Your Turing machine $M^*$ is not guaranteed to halt. In other words, your solution is incorrect. The missing observation is that if a Turing machine uses only space $k$, then there is an upper bound on the number of steps that it can run without getting into an infinite loop.

Level of description Here you should be asking two questions:

What does it mean to describe a Turing machine?
How do I prove that a certain language is decidable?

The level of description of Turing machines is a touchy subject. Usually they are described quite informally. The level of description should be such that in principle you could convert the informal description into a formal Turing machine. In practice, I suggest looking at some examples to get the general feel.

As to how to prove that a language is decidable, there is no need to describe a Turing machine. Decidability can be proved using any model of computation. In particular, you can use the "English" model of computation, in which you describe how to decide the problem in the English language (or in any other language). For example, you could say "Simulate $M$ on $w$, and if it ever uses more than $k$ space, immediately reject; otherwise, once $M$ halts, accept". (This is just your incorrect solution.)


Join of recursively enumerable set and its complement The union of a recursively enumerable set and its complement is $\Sigma^*$, which is definitely recursively enumerable. What if instead we consider the following operation, on an RE set $S$?
$$
\{ \# w : w \in S \} \cup \{ \\\$ w : w \in \overline{S} \}
$$
Is the result recursively enumerable?

The operation you described in actually the join operator in the semilattice of Turing degrees, defined as $A\sqcup B=\{0x | x\in A\}\cup \{1x | x\in B\}$. It is not hard to show that $A,B\le_T A\sqcup B$, thus if $A\in RE\setminus R$ then $\overline{A}\notin RE$ and thus $A\sqcup\overline{A}\notin RE$.


Time/Space cost of Taxicab algorithm? The following is an algorithm for generating "Taxicab numbers" using a priority queue (pq). Vector is an arbitrary data type that allows for storage of two number and their cubed sum. For those unaware (although you really don't need to know), a taxicab number is an integer that can be expressed as the sum of two cubes of integers in two different ways: $a^3+b^3 = c^3+d^3$. An example would be $1729 = 12^3 + 1^3 = 10^3 + 9^3$.

for i = 1..n
 pq.insert( Vector(i^3+i^3,i,i) )

prev = Vector(0, 0, 0)

while not pq.empty()
 curr = pq.deleteMin()
 if prev[0] == curr[0]
      print curr[0] is a Taxicab number that can be expressed as
      prev[1]^3 + prev[2]^3 and curr[1]^3 + curr[2]^3
 prev = curr
 if curr[2] < N
     j = curr[2] + 1
     pq.insert( Vector(curr[1]^3 + j^3, curr[1], j) )

I know inserting an item into the priority queue is $O(\log n)$ but I am not sure how this relates to space usage and runtime. Can someone help?

If you think about this program, you will realize pretty quickly that the vectors you're pushing onto the stack iterate over the values [a^3 + b^3, a, b] for all $1\leq a, b\leq N$  This means you're pushing $N^2$ items onto the stack over the course of the program.

Since each removal (and push, depending on the implementation of the PQ) takes $\Theta (\lg N)$ time, your algorithm would run in $\Theta (N^2\lg N)$ time.  There's a straightforward $\Theta (N^2)$ solution, so you're not optimal yet.


Show language is not regular Show that the following languages are not regular in two ways: first by using
closure properties then by using the Pumping lemma:

$$\text{(1) L1} = {a^n b^k c^{n+k} : n >= 0; k >= 0}$$

$$\text{(2) L2} = {a^n b^k : n \ne k}$$

So far for

What I tried: Assume that L is regular. By P.L, there exists a P such that $w = a^pb^pc^{2p}$  there is $w_i = xy^iz  , \mid y \mid \ge 1 , \mid xy \mid \le p $. We can imply  $y = a^k$ and assuming k = 1  $w_0 = xy^0z = xz = a^{p-1}b^pc^{2p}$ which is not an element in L. Therefore there a contradiction and it is not regular.
I don't know what to do for the closure properties
Assume that L is regular. By P.L, there exists a P such that $w = a^pb^p$ from here im lost since it says $n \ne k$
for 2) can we say that $ w \notin L $ since $n = p = k$ thus it is a contradiction?

For these hints, I'm assuming that you know (and are allowed to use) the fact that $\{a^nb^n\mid n\ge 0\}$ is not regular.

For (1), if $L_1$ was regular, then since regular languages are closed under intersection, we'd have $L_1\cap b^*c^*$ was regular. What's that language?

For (2), if $L_2$ was regular, then since regular languages are closed under complementation, we'd have $\overline{L_2}$ was regular, and so $\overline{L_2}\cap a^*b^*$ was regular. What's that language?


How can I compute the average weight of an undirected graph? Given a weighted, undirected graph $G = (V,E)$, how can I compute the average weight of edges?
It seems an easy problem (divide the total weight to the number of edges!)
but I couldn't manage to find the sum of the edge weights since each
edge can be counted several times while iterating through the vertices.

If $w(i,j)$ is the weight of edge $ij$ then:

$avg = \frac{1}{2|E|}\sum_{i\neq j}w(i,j)$.

Why $2E$ ? Because when traversing vertices you will calculate both edges $ij$ and $ji$. Since it's the same edge, you are adding its weight twice, so you need to remove this redundancy by dividing by 2.


Algorithm to calculate average weight from every pair of nodes I'm trying to solve a puzzle where I need to calculate the average weight between every node in the graph.

For example, for the following graph:

The results is calculated like this:

1 -> 2 = 3;

1 -> 3 = 7;

1 -> 4 = 5;

2 -> 3 = 4;

2 -> 4 = 2;

3 -> 4 = 7;

Average = 3+7+5+4+2+7 / 6;

NOTE: I'm visualizing the problem as a Graph, I might be wrong. The following constraints apply to this problem:

There is exactly one path between any two nodes, but all nodes are connected to every other node.

So we can assume that in the example, there will not be a path from 1 -> 4 directly

I'm looking for a recommendation of an algorithm that I can study in order to solve this type of problems. Not the actual solution.

One possible approach is Floyd-Warshall algorithm. This algorithm computes shortest paths between each pair of nodes. Since there is only one path between each pair of nodes, the shortest path will correspond to the weight of path between each pair of nodes. After computing all shortest paths you sum them and divide by the total number of paths (which is trivial given the number of nodes). This algorithm works in $O(|V|^3)$ time.

Also note that your graph is a tree. You may take a time to think over better algorithm which would work faster.