Is there a concept of information that distinguishes between "computed" and "non-computed" information? I always tend to think of information as follows: If we have an information set $I$, and it is possible to derive from $I$ another information set $X$, then $I$ really contained $X$ all along, and we haven't actually discovered "new information". We've merely found out something new about the information we already had.

But sometimes, deriving $X$ from $I$ is computationally very complex, so that it may take 1000 years to do it. In this case, any reasonable person in every day life, would say that we don't have the information $X$, even though we have $I$ and $X$ can theoretically be computed from $I$.

My question is, is there a concept that captures this notion of not having a piece of information merely because it is hard to compute? i.e. it could be something like: $I_{405}^*$ is the information set containing all information that can be generated by at most 405 computational steps from $I$. This is a somewhat vague definition, but I'm wondering if there is something more formal

The distinction between information theoretic and computational knowledge is an issue which is fairly common in cryptography.

Consider for example the one-time-pad encryption, that given a message $m\in\{0,1\}^l$, encrypts it using a secret key $k$ (chosen uniformly at random) by $m\oplus k$. Clearly, one learns no information from seeing the encryption of one message (it is a uniformly distributed string), so you could say that you have information theoretic security, which should make you very happy. However, if you insist on such a strict notion of security, it turns out you cant encrypt messages who are longer than the key, and if you want to do that, you should settle for a weaker notion, which is security against bounded resources adversaries (see semantic security).

One example which seems to fit your question well is one way permutations. A function $f:\{0,1\}^*\rightarrow \{0,1\}^*$ is called a one-way permutation if for every $n\in\mathbb{N}$, $f|_{\{0,1\}^n}$ is a permutation of $\{0,1\}^n$, and for some bounded resources adversaries, almost no knowledge of $x$ is exposed from $f(x)$. Since $f$ is a permutation, $f(x)$ completely determines $x$, but it is extremely hard to recover.

That said, I will strengthen Raphel's comment and say that there isn't a general definition for information (or what you call computational information), this is an issue which strongly depends on the context.


Find the minimum sum of distances between sets of points to a straight line in a plane Given $n$ dots on a plane, such as: n couples ($x_i$,$y_i$)
I would like to find a line parallel to y-axis ( $x=b$ ), such that the sum of all of the point's distances from that line will be minimal
In order to do that, I need to write an alogrithem with a linear run-time ( $O(n)$ )

MY METHOD I relate only for the $x$ values of each point as an
element in an Array called $A$ So I used the Select(A,left, right, p) & Partition Alogorithm in order to find the median of
medians of the array

pseudo-code:
Select(A,left,right,p)
 n<-right-left+1
 if n=1 then
  return A[left]
 m<-⌈n/5⌉
 let B array with length m
 for i <-1 to m
  B[i]=medianOf5(A,left,right,x)
 x<-Select(B,1,m, ⌈m/2⌉)
 q <- partition(A,left,right,x)
 k <-q-left+1
 if p<k then
  return Select(A,left,q,p)
 if p>k
  return Select(A,q,right,p)

But, using median of medians seems unnecessary
If so, is there an easier way to that? if not ( or if yes for that matter ) was my way correct?

Given a line $L = b$, the distance from any point $(x, y)$ to $L$ is
$\left| y - b\right|$.
The sum of a distances for a set of points $S = \{(x_1, y_1), \dots,
(x_n, y_n)\}$ is then
$$\left| y_1 - b \right| + \cdots + \left| y_n - b \right|$$
which is minimized for which $b$?


What can be the time complexity of an algorithm that calculates the weights of the nodes in a graph? I am trying to find the best time complexity of an algorithm that calculates the weights of all the nodes on a graph. The weight of the node is defined as the sum of the weights of the edges adjacent to it. I can argue that the algorithm is similar to the one which would calculate the degree of all the nodes and that certainly takes O(|V|+|E|) but can we say the same thing if we are trying to calculate the weights of nodes?

for i in V:
    weight(i) = 0
for e=(i,j) in E:
    weight(i) = weight(i) + weight(e)
    weight(j) = weight(j) + weight(e)


Maximum weighted subgraph Problem: Given a graph G with positive integral weights on nodes as well as edges, find an induced subgraph H with maximum total weight per node, i.e., the goal is to maximize
$$
\frac{ \sum_{e \in H}w(e) + \sum_{v \in H} w(v) }{|V(H)|}.$$
If you allow negative weights, then it is NP-hard (easy reduction from Clique). I have a strong feeling that the above is not NP-Hard.
I would love to have some first-thoughts on the above, if not a full-fledged optimal algorithm. Does it seem to be NP-Hard? What is the closest known problem -- my thoughts were Prize Collection, Clique -- but both seem much harder.

The Dense Subgraph Problem (thanks @PalGD) is a special case of the above problem--with no node weights and unit edge weights. See the solutions for the dense subgraph problem here. These solutions (LP and 2-approximation Greedy) easily generalize to the above problem (generalizing LP requires a bit of understanding/effort, but generalizing Greedy is trivial).


Policy dependent on initial state distribution in finite horizon MDPs Consider an MDP defined as the tuple $\langle S,A,R,P,\mu,\lambda\rangle$ where $S$ is the state space, $A$ the action space, $R:S\times A\times S\to\mathbb{R}$ the reward function, $P$ the transition probabilities, $\mu$ the initial state distribution, and $\lambda$ is the discount factor.
Let the decision horizon be finite. The expected discounted return under a given policy $\pi = (\pi_1,\ldots,\pi_{T-1})$, where each $\pi_t:S\to A$, is defined as
\begin{align*}
F(\pi,\mu) = E_{\pi,\mu}\big[\sum_{t=1}^{T-1}\lambda^tR(s_t,a_t,s_{t+1}) + \lambda^TR(s_{T-1},s_T)\mid s_1\sim \mu\big]
\end{align*}
where $a_t = \pi_t(s_t)$ and the expectation is taken with respect to the probability distribution on the states induced by the initial state distribution $\mu$ and the policy $\pi$. An optimal policy is defined as $\pi^*\in\arg \max_\pi F(\pi,\mu)$.
It seems to me that the math says that since we are only maximizing over $\pi$, there is still a residual dependence of the optimal policy on $\mu$, i.e., mathematically it should be written: $\pi_{\mu}^*\in\arg \max_\pi F(\pi,\mu)$.
Question: Are optimal policies in MDPs dependent upon the initial state distribution? If not, what conditions allow us to rule out this dependence?

On an MDP the main assumption is that states are independent (Markov Decision Process). Any policy in such environments will decide an action on a given state independently of previous visited states, taken actions and received rewards.
This means that the optimal policy doesn't depend at all on the initial distribution. However the initial distribution might affect the expected reward but it won't affect the optimal policy.
To be clear on your second question, the condition that allow us to rule out this dependency is the markov property: The future is independent from the past given the current state. So the optimal policy will have a distribution of actions to take depending only in the state, without caring about the weight of such state in the initial distribution.


Detecting overflow in summation Suppose I am given an array of $n$ fixed width integers (i.e. they fit in a register of width $w$), $a_1, a_2, \dots a_n$. I want to compute the sum $S = a_1 + \ldots + a_n$ on a machine with 2's complement arithmetic, which performs additions modulo $2^w$ with wraparound semantics. That's easy — but the sum may overflow the register size, and if it does, the result will be wrong.

If the sum doesn't overflow, I want to compute it, and to verify that there is no overflow, as fast as possible. If the sum overflows, I only want to know that it does, I don't care about any value.

Naively adding numbers in order doesn't work, because a partial sum may overflow. For example, with 8-bit registers, $(120, 120, -115)$ is valid and has a sum of $125$, even though the partial sum $120+120$ overflows the register range $[-128,127]$.

Obviously I could use a bigger register as an accumulator, but let's assume the interesting case where I'm already using the biggest possible register size.

There is a well-known technique to add numbers with the opposite sign as the current partial sum. This technique avoids overflows at every step, at the cost of not being cache-friendly and not taking much advantage of branch prediction and speculative execution.

Is there a faster technique that perhaps takes advantage of the permission to overflow partial sums, and is faster on a typical machine with an overflow flag, a cache, a branch predictor and speculative execution and loads?

(This is a follow-up to Overflow safe summation)

You can add $n$ numbers of size $w$ without any overflow if you are using $\lceil \log n\rceil + w$ bits arithmetic.  My suggestion is to do just that and then check if the result is in the range.  Algorithms for multiprecision arithmetic are well-known (see TAOCP section 4.3 if you need a reference), there is often hardware support for addition (carry flag and add with carry instruction), even without such support you can implement it without data dependant jump (which is good for jump predictors) and you need just one pass on the data and you may visit the data in the most convenient order (which is good for cache).

If the data doesn't fit in memory, the limiting factor will be the IO and how well you succeed in overlapping the IO with the computation.

If the data fit in memory, you'll probably have $\lceil \log n\rceil \leq w$ (the only exception I can think of is 8-bits microprocessor which usually have 64K of memory) which means you are doing double precision arithmetic. The overhead over a loop doing $w$-bits arithmetic can be just two instructions (one to sign extend, the other to add with carry) and a slight increase of register pressure (but if I'm right, even the register starved x86 has enough registers that the only memory access in the inner loop can the data fetch). I think it is probable that an OO processor will be able to schedule the additional operations during the memory load latency so the inner loop will be executed at the memory speed and thus the exercise will be one of maximising the use of the available bandwidth (prefetch or interleaving techniques could help depending on the memory architecture).

Considering the latest point, it is difficult to think of other algorithms with better performance. Data dependant (and thus not predictable) jumps are out of question as are several passes on the data. Even trying to use the several cores of today's processor would be difficult as the memory bandwidth will probably be saturated, but it could be an easy way to implement interleaved access.


Why are regular expression used in lexical analysis instead of grammars? Even though grammars can do what regular expressions do, why are regular expression employed instead of grammars in lexical analysis?

Regular languages are faster to recognize, and so they are preferred whenever possible. Fortunately, regular expressions are usually good enough for describing the lexemes of a language.

Indeed, in some sense the separation between lexical analysis and parsing is exactly due to this fact, that lexical analysis can be done more efficiently than parsing.


Is $L = \{ w : \#_a(w) = \#_b(w) \}$ regular? Is $L = \{ w : \#_a(w) = \#_b(w) \}$ regular? I do not think it is. I recently posted a question and from there I was thinking if this language is regular.
If we assume on the contrary, then there exists a pumping length $p$. In that case, the word looks like $xyz$ where $|xy| \leq p$. If $y$ does not have the same number of $a$'s and $b$'s then $xy^iz$ for $i>1$ will give us a contradiction. Otherwise $y$ has the same number of $a$'s and $b$'s. This does not lead me to anywhere. I tried creating cases where this would fail -- seems like there isn't any.
This link answers it, but I do not understand what they mean by "a regular language is one that uses finite memory". I have encountered similar reasoning before, I have not been able to figure it out.
This answer seems to check if a number satisfies the criteria using regex. Is that a different form of regex?

This can also be proved easily using Myhill-Nerode theorem.

Myhill-Nerode Theorem: Given a language $ L \subseteq \Sigma^* $, Suppose  $$ \forall x,y \in S, (x \neq y) \wedge (\exists z \in \Sigma^*
 ,L(xz) \neq L(yz))   $$ where S is an infinite set. Then L is not a
regular language.

(Here $L(w) = 1$ if $w \in L$ and $L(w) = 0$ if $w \notin L$.)
For the given problem, We have $L=\{w:\#_a(w)=\#_b(w)\}$.
Take $S = a^*$ (note: the set $S$ is infinite).
Now take any two distinct elements from set $S$, $x=a^i$ and $y=a^j$,
and take $z=b^i$.
So $xz \in L$ and $yz \notin L$.
Hence, we will get an infinite number of distinct quotients as $S$ is an infinite distinctive set.
Thus, $L$ is not regular.


How to categorize an undirected triangular graph with top, bottom, and intertwining paths Background:
I worked on finding the maximum path from the top to the bottom of a tree-like graph. During the process I found that the algorithm for finding the maximum path from the top to bottom of a binary tree also worked for my graph. My problem arose when trying to name the program, because the graph it works on is clearly not a binary tree.

The problem:
My graph looks like this:
    ·······a······
    ······/··\·····
    ·····b···c····
    ····/··\··/··\···
    ···d···e····f··
    ··/··\·/··\··/··\·
    g····h····i····j
Due to that all the inner nodes at lower levels have multiple "parents" from the level above, it cannot be classified as a binary tree. From the perspective of finding the maximum path from the top to the bottom, it could be classified as a DAG, but because there strictly are no directed edges in the input graph, this also seems wrong. If presented in the following way:
a - c - f - j
|····|····|·
b - e - i
|····|·
d - h
|··
g
It could be argued that it is a lattice graph. But that would conceal that it has a defined "top" and "bottom", and that I have worked with a root and leaves. One could always fall back to calling it a general graph I guess, but that would conceal that it follows a very rigid structure.

My question:
What should I call this bastard that can be processed by many of the algorithms applied to binary trees but violates some of the properties of trees, for the sake of my problem can be considered a DAG but has no directed edges, and somehow resembles a lattice?

Your algorithm relies on some properties of the input graph for its correctness. You should isolate these properties, and then you will know how to name your program.

The most likely answer is that your algorithms works on DAGs oriented source-to-sink, as you and David mention. However, there are many possible variants:

Your algorithm might rely on the DAG having a single source.
Your algorithm might rely on the outdegree being at most 2 or perhaps exactly 0 or 2.
Your algorithm might work on every (possibly connected) graph, implicitly considering say the BFS tree (or forest) of the graph, from a given starting node.

Only you can tell which of these is correct for your algorithm.


Goldbach Conjecture and Busy Beaver numbers? Background: I am a complete layman in computer science.

I was reading about Busy Beaver numbers here, and I found the following passage:

  Humanity may never know the value of BB(6) for certain, let alone that of BB(7) or any higher number in the sequence.

  Indeed, already the top five and six-rule contenders elude us: we can’t explain how they ‘work’ in human terms. If creativity imbues their design, it’s not because humans put it there. One way to understand this is that even small Turing machines can encode profound mathematical problems. Take Goldbach’s conjecture, that every even number 4 or higher is a sum of two prime numbers: 10=7+3, 18=13+5. The conjecture has resisted proof since 1742. Yet we could design a Turing machine with, oh, let’s say 100 rules, that tests each even number to see whether it’s a sum of two primes, and halts when and if it finds a counterexample to the conjecture. Then knowing BB(100), we could in principle run this machine for BB(100) steps, decide whether it halts, and thereby resolve Goldbach’s conjecture.

  Aaronson, Scott. "Who Can Name the Bigger Number?" Who Can Name the Bigger Number? N.p., n.d. Web. 25 Nov. 2016.

It seems to me like the author is suggesting that we can prove or disprove the Goldbach Conjecture, a statement about infinitely many numbers, in a finite number of calculations. Am I missing somehing?

The statement is about infinitely many numbers, but its demonstration (or refutation) would have to be a finite exercise. If possible.

The surprise may come from the (false) assumption that finding BB(100) would be a "theoretically easier" problem, only made impossible for practical reasons - since there are so many machines, and they can run for such a long time before stopping, if at all - after all, they're just machines...

The truth is that discovering BB(n), for n large enough, has to be an unsurmountable task, for both theoretical and practical reasons.


Can I change the input of my reductionduring the proof? To prove that a problem $\Pi_2$ is NP-hard one has to:

select a known NP-hard problem $\Pi_1$;
from an arbitrary instance of $\Pi_1$, create an instance of $\Pi_2$ in polynomial-time; and
show that solve $\Pi_1$ with the given instance $\iff$ solve $\Pi_2$ with the created instance.

Now, my question is the following.

Suppose now I did 1., 2. and only solve $\Pi_1\Rightarrow$ solve $\Pi_2$ but when I am trying to show the inverse, i.e., solve $\Pi_2\Rightarrow$ solve $\Pi_1$, the instance of $\Pi_1$ is changed a little. Is this proof correct?

More precisely, let $I_1=(n, a_1,\ldots,a_n,b_1,\ldots,b_n,\alpha,\beta,k)$  be an arbitrary instance of $\Pi_1$. The created instance (in polynomial-time) of $\Pi_2$ is $I_2=(n, a_1,\ldots,a_n,b_1,\ldots,b_n,\Delta,k)$. Now when I tried to show solve $\Pi_2$ with $I_2\Rightarrow$ solve $\Pi_1$ with $I_1$, I found another instance of $\Pi_1$, $I_1'=(n, a_1,\ldots,a_n,b_1,\ldots,b_n,a,b,k)$ where $a\neq \alpha$ and $b\neq\beta$. Hence I did not solve $\Pi_1$ with $I_1$ but with $I_1'$.

My guess is that the proof still correct, right?

No, you may not modify $I_1$. By the time you get to Step 3, everything is determined and you might not change your instances. Say $f$ is the polytime transformation from Step 2. Then you need to show

$I_1$ is a yes-instance of $\Pi_1$ if and only if $f(I_1) = I_2$ is a yes-instance of $\Pi_2$.

If after arriving at Step 3 you notice that your $I_2$ instance does not allow you to prove the statement, then you might want to change $f$ in your Step 2, and redo Step 3.


Recognizability and complements I'm learning about Turing Machines, decidability, and recognizability, and read that if a language is recognizable, its complement is sometimes recognizable. I don't really understand how this could be, can someone give me an example where a language has a recognizable complement and an unrecognizable complement? Thank you!

Example 1.
The empty language is recognizable and its complement (the language containing all the words) is also recognizable.
Example 2.
Any regular language is recognizable and, since regular languages are closed under complement, its complement is also recognizable.
Example 3.
The language $H = \{ \langle T, x \rangle : T \mbox{ is a Turing Machine}, x \in \{0,1\}^*, T(x) \mbox{ halts}\}$ is recognizable.
In order to recognize $H$ it suffices to build a Turing machine $M$ that checks if  $T$ is a valid description of a Turing machine, simulates $T$ on $x$ until $T(x)$ halts (possibly forever), and accepts.
The complement $\overline{H}$ of $H$, however, is not recognizable as if it was recognizable a Turing machine $M'$ for $\overline{H}$, together with $M$, would allow to solve the Halting problem. To do so simply simulate in parallel $M$ and $M'$ until one of them accepts.


Big-O with nested loops and "variables" in the T(n) So, I need to find the T(n) and then Big-O (tight upper bound) for the following piece of code:

int sum = 0;
for(int i = 1; i < n; i *= 2) {
    for(int j = n; j > 0; j /= 2) {
        for(int k = j; k < n; k += 2) {
            sum += i + j * k;
        }
    }
}

Now from what I calculated for the loops, first loop runs log(n) times, second loop runs (log(n) * log(n)) times and the third loop is the one which is causing confusion, because I believe it runs for (n - j)/2 times. My question is can I assume it to be n/2 times, because I think it won't be a tight upper bound if I do that. Or is there a different approach that I am missing?

One common way to arrive at a tight big-$O$ upper bound of the complexity of an algorithm is to estimate one. Then prove that estimate works.

Let me take your computation by nested loops as an example.

In this post $\log(x)$ means $\log_2(x)$. The first loop runs $\lceil\log(n)\rceil$ iterations. For each iteration in the first loop, the second loop runs $\lfloor\log(n)\rfloor+1$ iterations. For each iteration in the second loop, the third loop runs $\lfloor(n - j+1)/2\rfloor$ iterations, where $j>0$ is the loop variable of the second loop. Ignoring the floor function, the addition by the constant 1, the subtraction by $j$, the division by the constant 2 and the constant number of operations executed by each iteration in the third loop, I will estimate the upper bound of the number of total operations as $O(\log(n)\log(n)\,n)$.

Is that $O(n\log^2n)$ a tight upper bound of the the number of total operations $T(n)$? Yes, it is indeed.

Firstly, let us show it is an upper bound. We can assume $n>2$. Let $c_3$ be the number of operations executed by each iteration of the third loop.
$$ T(n) \le (\lceil\log(n)\rceil) (\lfloor\log(n)\rfloor+1)(n/2)c_3\\
\le (2\log(n))(2\log(n))(n/2)c_3\\
\le (2c_3)n\log^2n
$$

Now let us show it is tight. Let us do not count the first iteration of the the second loop. That is, let us only consider the operation done by the second loop starting from $j=\lfloor n/2\rfloor$. Then for each iteration in the second loop, the third loop runs $⌊(n−j+1)/2⌋ \ge n/2-1$ iterations. Then for $n\ge6$,
$$ T(n) \ge (\lceil\log(n)\rceil) (\lfloor\log(n)\rfloor)(n/2-1)c_3\\
\ge (\log(n))(\log(n)/2)(n/3)c_3\\
\ge (c_3/6)n\log^2n\\
$$

So we have proved from the ground up.

The above proof, although rigorous and clear, is not the usual way to reason about the big-$O$ because it is so exact as to require too much thinking. That is almost the kind of computation needed to get the exact asymptotic approximation. Here is a simpler version assuming you are familiar with the big-$\Theta$ notations.

The first loop run $\Theta(\log(n)$ iterations. For each iteration in the first loop, the second loop runs $\Theta(\log(n)$ iterations. For all but the first iteration in the second loop, the third loop runs between $n/2$ to $n$ iterations, which is $\Theta(n)$ iterations. In the first iteration of the second loop, the third loop runs no iteration. So $$T(n)=\Theta(\log(n)(\Theta(\log(n)-1)\Theta(n)=\Theta(\log(n))\Theta(\log(n))\Theta(n)=\Theta(n\log^2(n))$$
which implies $O(n\log^2n)$ is the tight upper bound.

By the way, in all computations above we are not counting the operations to maintains the indice $i,j,k$. That is ignored by convention, because they will not change our approximation in big $O$-notations unless in extraordinary situations. Or because in many situations we are only interested in the number of the "real" operations.

The reasoning about the big-$O$ notations can be an art or a precise process. On the one hand, you can be very "sloppy" when you are trying to get an estimate and even when you are reasoning. That is because you can hide or absorb constant factors into the notations. That way you can arrive at a possible answer very quickly. With practice and experience, you can be certain immediately most of the times once you got an estimate. On the other hand, you can also verify every part of the "sloppy" process by rigorous mathematical deduction or by applying a set of valid shortcut rules. In the end, we will arrive at a precise conclusion using the big-$O$ notations.


Minimal-envy land division There is a land divided to $D$ districts.

There are $C$ citizens.

We want to divide the land to the citizens, such that each citizen receives a single land-plot in a single district.

Each citizen prefers certain districts, however, the preference also depends on the size of plot. For example, Johnny prefers a plot of 1 dunam in the North to a plot of the 1 dunam in the South, however, he also prefers a plot of 1 dunam in the South to a plot of 0.5 dunams in the North.

Ideally, we would like to divide the land in an envy-free manner, such that no citizen thinks that the plot given to another citizen is better (according to his subjective preferences) than the plot given to him.

However, this is not always possible. For example, suppose there are 2 districts (North and South), each of size 1 dunam, and 3 citizens, all have the same preferences as Johnny. If two of them get a plot in the North and the third gets a plot in the South, then the first two get only 0.5 dunam each, and so they envy the third who gets 1 dunam. The other divisions are even worse (In the singular case where all citizens get 1/3 dunam in the North and the South remains empty, assume that it is invaded by a fourth citizen, so that all 3 citizens now envy the invader).

So, I am looking for a procedure that will minimize the envy - whatever that means.

Note that, in contrast to the standard envy-free cake-division algorithms, I am not interested in geometric cuts of the land - the division of land to districts is pre-determined, and each person can get a plot in only one district.

If the number of citizens is large enough, such that the effect of one citizen changing his/her selection is negligible, then an envy-free division is equal to a Nash equilibrium in a congestion game.

Specifically, Igal Milchtaich's papers are relevant to this problem.

Additionally, Yonatan Aumann and Yair Dombb define several quantitative measures of unfairness: alpha-unproportionality, alpha-envy and alpha-inequitability, which may also be relevant.


NP Problem that cannot be solved by a quantum computer in polynomial time Is there any NP-Problem that can't be (maybe even proven) solved by quantum computers. I'm not talking about quantum NP-Problems (if that's even a thing), but about normal NP.
If that NP Problem exists could you also use it for cryptography, since I don't want to buy a quantum computer just to be secure.

EDIT:
I'm not talking about NP-complete, because that would have no use (I think) in cryptography and also not about symmetric key encryption.

Nobody really knows whether quantum computers can solve all NP complete problems in polynomial time or not. There is strong evidence that they cannot: Strengths and Weaknesses of Quantum Computing, but no definite proof.


lower bound proof with adversary argument We have to run a song on a Walkman, for that we need 2 full batteries. Let's say we have a mixed set of 30 batteries (15 are empty and and 15 are full) and then only way to test if the battery is full or empty is to put them in the Walkman and try it out. We cannot tell which one is empty or full if we put inside one full and one empty.

The question is to find the minimum needed step to run the walkman (to find 2 full batteries)

I modeled the problem like that :

  Let the Walkman br a function $f$ which take two arguments and returns 1 if the walkman works, and 0 otherwise.
  $$ f\colon \{b_1,b_2 \dots b_{30}\} \times \{b_1,b_2 \dots b_{30}\} \rightarrow\{0,1\}$$

I was given a hint to use the Turán lemma:

  When a graph $G=(V,E)$ with $V$ the vertex set and $|V|=n$ does not contain a $k$-clique with $k >1$, then
  $$ |E|\leq \left(1-\frac{1}{k-1}\right)\frac{n^2}{2} $$

The idea was to consider the batteries as vertex and create a complete graph and then when $ f(b_i,b_j)=0$ we delete the edge between $b_i$ and $b_j$.

Using the adversary argument I have to prove that the lower bound to find the battery must be 18, so any help how to solve this?

Here comes $A$ (is it Apass?), the simple smart adversary Walkman.

For the first 18 pairs of batteries you put into $A$ to test, $A$ will just not operate. So you will need at least 18 tests before finding 2 full batteries. On the other hand, the accepted answer to another question by OP shows 18 tests is enough. So the desired lower bound is 18 tests.

The real question is, of course, does this behavior of $A$ come from an actual combination of batteries regardless of whichever 18 pairs of batteries are chosen to be tested?

The answer is yes.

Instead of proving for the case of 30 batteries and 18 tests, let us prove the general cases, which is actually easier since we can use mathematical induction.

(Consistency of $A$) Let $n\ge2$ be a positive integer. $S=\{\{i,j\}\mid 1\le i\lt j\le 2n\}$ with $\#|S|\le n+3$. Let $B=\{i\mid1\le i\le 2n\}$. Then there exists a function $f: B\to \{0,1\}$ such that $|f^{-1}(0)|=n$ (and hence $|f^{-1}(1)|=n$ as well) and for each $\{i,j\}\in S$, if $f(i)\ne 0$, then $f(j)=0$ (If we interpret 0 as an empty battery, this means no pair in $S$ will make $A$ operate).

Proof by induction on $n$

$n=2$. $|S|\le5$. Since there are 6 different pair of numbers can be drawn from $\{1,2,3,4\}$, there is one pair of numbers which is not in $S$. WLOG, let that pair of numbers be 1 and 2. Let $f(1)=f(2)=1$ and $f(3)=f(4)=0$. Case proved.
Suppose it is true for $n$. Let us consider the case of $n+1$, where
$S'=\{\{i,j\}\mid 1\le i\lt j\le 2(n +1)\}$ with $\#|S'|\le(n+1)+3$ and $B'=\{i\mid1\le i\le 2(n+1)\}$.
Since $\#|S'|=n+4$ and each element of $S'$ has two numbers, the total number of appearances of numbers in all elements of $S'$ is $2(n+4)$, which is smaller than the double of $2(n+1)$. So there must be one number that appears less than 2 times. WLOS, let that number be $2n+2$. There are two cases.

If $2n+2$ appears in $\{j, 2n+2\}\in S'$ for some $j$, WLOS we can assume $j=2n+1$ since we can switch $j$ and $2n+1$ otherwise.
If $2n+2$ does not appear in any element of $S'$, choose any element $j$ that appear at least once in some element of $S$. WLOS we can assume $j=2n+1$ since we can switch $j$ and $2n+1$ otherwise.

Consider $S=\{\{i,j\}\in S'\mid 1\le i\lt j\le 2n \}$. Since either $2n+2$ or $2n+1$ appears in one of elements of $S'$, $\#|S|\le\#|S'|-1\le n+3$. By induction hypothesis, we can define $f$ on $B$ such that $f^{-1}(0)=n$. Extend $f$ by letting $f(2n+2)=1$ and $f(2n+1)=0$. Now we can see that $f^{-1}(0)=n+1$ and for each $\{i,j\}\in S'$, if $f(i)\ne 0$, then $f(j)=0$, thus concluding our proof.

Apparently, Turán lemma is not needed if it can be useful here at all.

Here are several related exercises I designed for the interested readers.

Exercise 1. Check that the original question is the case when $n=15$.

Exercise 2. Verify the last statement of the above proof.

Exercise 3. (the case of 3 batteries) Another Walkman needs 3 full batteries to operate. Let's say we have a mixed set of 30 batteries, 20 of which are empty and the remaining 10 of which are full. The only way to test whether a battery is full or empty is to put 3 of them in the Walkman and try it out. However, we can not tell which one is empty or full when the Walkman does not operate. What is the minimum number of tests that guarantees to identify 3 full batteries? Prove your answer.

Exercise 4. What is the average number of steps for the testing strategy shown here? Can we do better (this last question is a research topic)?


$\ell_1$ Minimization of Probability Distribution and KL-Divergence Suppose through $\ell_1$ minimization I obtained two sparse probability distributions $P, Q$ which may contain many zero terms. Then I would like to compute the KL-Divergence of them $D(P || Q) = \sum_i {p_i\log(\frac{p_i}{q_i})}$.  However, since the probability distribution is sparse, it might occur that $p_i \not= 0$ and $q_i = 0$. In that case, KL-Divergence is not well defined.  One solution is to incorporate Dirichlet Prior. However, I am afraid by doing so the sparsity of the probability distributions is violated.  Is there any other way to compute the KL-Divergence of the two probability distributions?

Have you looked into Jensen-Shannon Divergence? It avoids the situation you described by adding a midpoint. Formally we have,
$$\mathrm{JSD}(P||Q) = \frac{1}{2} \mathrm{KL}(P||M) + \frac{1}{2} \mathrm{KL}(Q||M)$$ where $M = \frac{1}{2}(P + Q)$. Informally, JSD is nice when you want to compare distributions that seem to have the same shape, but dont completely overlap.


What is the difference between modulo and modulus? Throughout my education in computer science, I feel like I've heard the terms "modulo" and "modulus" used interchangeably.  It looks like even Wikipedia claims that "modulo" is "sometimes called 'modulus'" (see the first sentence of the page on 'modulo').

I've looked into this issue a little and it seems that "modulo" finds singular use in modular arithmetic (e.g. "19 and 64 are congruent modulo 5").  In addition, I've seen the symbol % be referred to as "modulo."

Meanwhile, "modulus" appears to have several definitions, including "absolute value" and "constant factor" as well as referring to the "5" in "modulo 5."

Is it ever correct to use these terms interchangeably in the context of computer science?  Are they simply different types of words that represent the same idea (such as "run" and "runner")?  Are there important differences in other disciplines?

Bonus: Etymologically, what gave rise to these two terms?

"modulo" is an operator.  For instance, we might say "19 and 64 are congruent modulo 5".

"modulus" is a noun.  It describes the 5 in "modulo 5".  We might say "the modulus is 5".

No, the two should not be used interchangeably.  It would be incorrect to say "19 and 64 are congruent modulus 5".  It would also be incorrect to "the modulo is 5".

See also https://en.wikipedia.org/wiki/Modular_arithmetic and https://en.wikipedia.org/wiki/Modulo_operation.  Both define the word "modulus", and as far as I can see they use it correctly.


connected components - determining "groups" in Go I would like to write an analysis of go positions.  Part of it requires me to determine the "groups" on the board and count their "liberties".

Any Go "position" is a collection of black x white o and empty . on the board.  So I using an 2D array.

o.x.xxx..x
xoo.xoxxoo
....x...ox
.ox.o.o.o.
xox..xx...
.xox.x.xx.
o..oxxoooo
..o..xxo.o
.o...oxoo.
.xo..oxxox

I need to identify the components of the same type (o, x or .)  connected by horizontal or vertical moves.  Diagonal does not count.

...o...    vs    .x.x
oo...oo          x.x.

Once I have identified a group, I need to count the liberties or empty spaces around that group.

Here is a group of x pieces with 9 spaces around it

 234       ..ox
1xxx5     .xxxo
 89x6      o.xo
   7         .

However, 4 of them are covered with o pieces, and 5 of them have empty spaces . around it.  So our gropu of x pieces only has 5 liberties.

. should count as 1 liberty, the o pieces should not count (contribute 0) and the x pieces should have been included in the group to begin with.

Is there a systematic way to identify connected groups on the board?  And then to count the liberties.

To count connected groups

Form an undirected graph, with one vertex per location on the board, and an edge between each two locations are are adjacent (horizontally or vertically).  Then, use any standard algorithm for connected components.  See https://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29 or your favorite CS algorithms textbookk.

You'll probably want to run the algorithm twice: once for x's (build a graph where you retain just the vertices with x's on them, and find all connected components), and once for o's (build a graph where you retain just the vertices with o's on them, and find all connected components).

To count liberties

If I understand the definition, this looks like a simple matter of programming.  Find a connected component of x's, look at each cell which is adjacent to it, and count how many are empty.  That's straightforward programming -- no fancy algorithms needed.  Programming questions are better on StackOverflow, but make sure you show your effort.


Language of TM is Undecidable why is this Problem$$L = \{ \langle M\rangle \mid L(M) \text{ is undecidable}\}$$ undecidable?

I thought if we know $L(M)$ the turingmaschine accepts all $x \in L(M)$, so $L(M)$ is in every case decidable and $L=\emptyset$ especially finite and decidable.

I know we cannot find an algorithm but every TM has a language and we even if we don't it, we know it is decidable.

Can someone help me where I do have a misunderstanding?

You're very close!

The key is the difference between recognizable and decidable.

A language $R$ is recognizable if we can build a TM $T$ such that $L(T) = R$. In other words, there's a Turing machine that accepts exactly those strings in the language—and for strings not in the language, it might halt in a non-accepting state (i.e. it might reject), or it might run forever without halting (i.e. it might diverge).

A language $D$ is decidable if we can build a TM $T$ such that $L(T) = D$, and $T$ rejects (halts in a non-accepting state) on strings not in $D$.

It turns out that a whole lot of languages are recognizable but not decidable. The language $H_0 = \{ \langle M \rangle | M \textrm{ halts on empty input} \}$ is undecidable (this is the Empty-Input Halting Problem), but $H_0$ can be recognized by the following procedure (call it $RH$):

  Simulate $M$ on empty input. If it ever halts, accept.

Now we have a Turing machine whose language, $L(RH) = H_0$, is undecidable! Which means the property in question is non-trivial, so by Rice's Theorem that property is undecidable.


Is radix sort really O(n) for sorting 32 bit integers? I was trying to analyze radix sort in terms of time and space. Assume that we are given $n$ 32-bit integers which we would want to sort by looking at the least significant digits first.

$k$ is the total amount of bits that you will be working with at every step. So at first you look at the first $k$ bits, and sort the elements with counting sort. Then you look at the next $k$ bits etc.

In total we would have to run counting sort $\frac{32}{k}$ times. In the counting sort phase we will both have to scan the input array and also the bucket array, where the input array is of size $n$ and the bucket array is of size $2^k$. In other words the running time is going to be $ \Theta (\frac{32}{k}(n+2^k))$. As for space, we will need an extra temporary array of size $n$ during the counting sort phase, and also an array for the bucket, so in total the space will be $\Theta (2n + 2^k)$

So we have:

Time: $ \Theta (\frac{32}{k}(n+2^k))$

Space: $\Theta (2n + 2^k)$

Am I the only one who can't see why this is $O(n)$?

You can choose $k = 1$ and then the time is $\Theta(32(n+2)) = \Theta(n)$ and the space is $\Theta(2n + 2) = \Theta(n)$. In general, if you replace 32 by any fixed number, the complexities will be $\Theta(n)$. If, however, you try to use radix sort with integers of non-constant width $m$, the complexities will be as stated (with $32$ replaced by $m$), or even worse, since you are assuming that operations on these integers take constant time, which might not be the case for integers of arbitrary size (depending on your computation model).


Is human being a Turing Machine? We may not have a determinate answer to this question. But is there any evidence for or against this question? Or is there any study on it?

A Turing machine is a tuple consisting of an alphabet, a tape, some transition, etc.

I am not one of those. So no. A human being is not a Turing machine (or at least, I am not).


Vertex Cover without covering all edges What would be the name of the problem of a vertex cover that covers all the vertices without the requirement of covering all the edges?

Vertex cover has to answer whether or not there is a set of $k$ vertices that covers all the edges of the graph, covering therefore, all the vertices. What is the name of the problem that, similarly to vertex cover, select a subset of $k$ vertices that has direct edges to all the vertices, but without necessarily covering all the edges of the graph?

If I understand your description correctly, you are looking for a dominating set.


Is every PSPACE-complete problem complete with respect to logspace reductions? A remarkable feature of the reduction showing that TQBF (True Quantified Boolean Formulas) is PSPACE-complete is that it actually runs in logspace, i.e. for any $A \in \mathsf{PSPACE}$,
$$
A \le_L TQBF.
$$
(See for example, comment at the end of section 7.4 in these notes.)
Therefore, TQBF is complete with respect to logspace reductions.
It is still possible, however, that there are some other standard PSPACE-complete problems for which this is not true. Of course, the problem would reduce in logspace to TQBF, but maybe the reduction the other way would not go through.

Question: If $A$ is PSPACE-complete, must $A$ be complete with respect to logspace reductions? In other words, if $A \in \textsf{PSPACE}$ and $TQBF \le_p A$, then must $TQBF \le_L A$?

Some thoughts:

I tried the generalized geography problem, and it seems to be true in that case. I'm not sure about universality for NFAs.

To prove it, the most straightforward idea would be to show that if $A \le_p B$ and $B \le_L A$, then $A \le_L B$. But this is false for general $A, B$, assuming $\mathsf{L} \ne \mathsf{P}$. In particular, take $A \in \mathsf{P}$ and $B = \varnothing$.

If every PSPACE complete problem is also complete under logspace reduction, then $\mathsf{P\neq PSPACE}$.

To see why, suppose for the purpose of contradiction that the definition of completeness remains unchanged when replacing polynomial time with logspace reductions, and simultaneously $\mathsf{P=PSPACE}$. Since $\mathsf{P=PSPACE}$, every nontrivial language in PSPACE is complete under polynomial time reductions, e.g. undirected connectivity which lies is $\mathsf{L}$. Seeing that we assumed that polynomial time completeneess is equivalent to logspace completeness, undirected conectivity is also PSPACE complete under logspace reductions, which implies $\mathsf{L=PSPACE}$, contradicting the space hierarchy theorem.

This question is probably still open (though I am unaware of any important/strange implications of the negation of your statement). You can find similar discussions about NP-completeness, where it appears the same question is also open.


Implementing general vertex folding procedure in an undirected graph I'm implementing the algorithm presented in "Improved Parameterized Upper Bounds for Vertex Cover" paper (PDF).
I'm a bit stumped by the General-Fold procedure.
What it should do is reduce the number of vertices (and) edges in the graph by finding specific structures (almost-crowns) and replacing them with a single vertex. (There is also a separate case, but I'm focusing on the described one now).

It goes like this:

  Let $I$ be an independent set in $G$ (the graph) and let $N(I)$ be the neighbors of I. Suppose that $|N(I)|=|I|+1$ and for every $\emptyset\neq S \subset I$ we have $|N(S)|\geq{S}+1$.

  1) If the graph induced by $N(I)$ is not an independent set, then there exists a minimum vertex cover in $G$ that includes $N(I)$ and excludes $I$). (This is a 'standard' crown case - I have it implemented already with a separate approach.)

  2) If the graph induced by $N(I)$ is an independent set, let $G\prime$ be the graph obtained from $G$ by removing $I\cup N()$ and adding a vertex $u_I$ and then connecting $u_I$ to every vertex $v \in G\prime$ such that v was a neighbor of a vertex $u \in N(I)$ in $G$.

My problem is  how to find a structure that would fulfill the suppositions about size as well as having an independent neighborhood?
It's all roses when every vertex in $I$ is of the same degree, e.g. ($I$ is yellow, $N(I)$ is green):

which reduces to

or

which reduces to

.

If only that was the case - I'd just check the vertices of a specific degree, descending.

But unfortunately this reduction may apply to a set of vertices of differing degrees. An example:

note the different edges between yellow and green. It also reduces to:

What baffles me is what would the algorithm for that be, since the paper states that given a maximum size $k$ of a vertex cover existing in the graph, it is possible to be done in $O(k^{2}\sqrt{k})$.

Can anybody offer any help or advice or intuition on this?

EDIT:
I think I might be understanding neighborhood incorrectly here - if we suppose that $N(I)$ contains the intersection of neighborhoods of every vertex in $I$, this would come down to the first two examples - where every vertex in $I$ is of the same degree...

Any thoughts?

Take a look at the full version of the paper: http://www.sciencedirect.com/science/article/pii/S0304397510003609. What you want is described in Proposition 2.6.


Context switch in an Text Editor I am new to operating systems and have been wondering about this.
Consider a normal text editor, and it's process running in the CPU. Since text editors include IO operations, do the process keep switching it's state from Wait -> Run -> Wait etc. While the user is typing and the same is reflected on the screen or some processing such as auto-correct etc. And while the current process is in Wait, other process is in Run state (Context Switching).
OR
Text - Editor itself creates multiple processes, one for handling IO operation and other for processing the data and it is being established through Inter-Process Communication.
New to OS and stuck with this, thank you for any kind of help .

There is no single answer: you could build a text editor in any way you want.
One simple architecture for a text editor is to have a single process, which blocks on I/O when it is waiting for the user to provide input.  But it's also possible for a text editor to be built in a multi-threaded way with multiple processes, e.g., spawning one thread to do spellchecking in the background or anything else.


motivation and idea of defining non-deterministic Turing machine This is a very basic question but I spent some time reading and find no answer. I am not computer science majored but have read some basic algorithm stuff, for example, some basic sorting algorithms and I also have some basic knowledge of how computers operate. However, I am really interested in the idea of a Turing machine, especially the non-deterministic one.

I have read Wiki about the definitions of a Turing machine (and watched some youtube videos) and I sort of accept that, although I really feel that this is a huge jump from an algorithm to an abstract machine. From my understanding (you are more than welcome to correct me):

A Turing machine is a machine performing works specified on a cookery book (algorithm).
The pages of the cookery book represent the "states" of your machine and each page contains a table saying that which state and which cell your machine will move to given the alphabet the machine read and your current state. (NB. This is not a function but a partial function because it is possible that the machine stops.)
So, to guess the idea and motivation of defining an abstract Turing machine, I imagine that the algorithm corresponds to the partial map, the memory of the computer corresponds to the (infinitely long) tape and what's finally on the tape is the answer to the question you wanna solve.

So, Turing machine looks like a machine to realize any algorithm to solve problems. One just "translates" any algorithm to a set of mysterious simple rules (i.e. the partial function) and let the machine do the laboring job and then we get the solution.

In this respect, Turing machine is always deterministic, because algorithms are deterministic. It tells you what to do next precisely. This is no uncertainty. Turing machine is just a machine to realize any algorithm.

OK, This is very abstract and I sort of accept it. However, then I read something called non-deterministic Turing machine (NTM) and then I was knocked down. A NTM is pretty much similar to a Turing machine except that the partial function is now replaced by a "relation". That is, it is a one-to-multiple map and it is no longer a (partial) function.

Could someone explain to me why we need such multiple options? I would never expect to encounter something uncertainty in the implementation of an algorithm. It is like telling the machine: you first do A, then if you find yourself in a state B and find the data is now B' then you choose for yourself one of the 10 allowed next steps?

Are NTM's corresponding to a set of algorithms that need uncertainty? for example the generation of random numbers? If no, why do we need to allow multiple choices for a Turing machine?

Any help will be appreciated!

update From the linked post, it looks like the introduction of NTM naturally leads to a class of "problems" (not algorithms because a problem can be solved by several algorithms with different efficiencies) called NP problems. Forgive me that I still feel that every step is such a huge jump... Could someone close the gaps a little bit? thanks a lot!

Motivated by @reinierpost's answer, I found this explanation of NP problems on CMI website. The example problem is to choose 100 students from 400 candidates subject to some constraint that some pairs of students cannot be included. In this case, I can imagine that a Turing machine trying to solve this may naturally equip itself with a cloning ability such that it is able to generate the solution with multiple choices in the steps. Then, as long as some choices or branches of the NTM work, the machine finds the solution(s). In this sense, an NTM looks like a multi-threading parallelization to save time?

Could someone explain to me why we need such multiple options? I would never expect to encounter something uncertainty in the implementation of an algorithm.

I think this is your primary misconception: an NTM is not supposed to be a realistic machine. That is, no one has ever tried to build a NTM, no one knows how to implement it, and algorithms in the real world are not written in this way with "multiple options".

An NTM is, instead, supposed to be a hypothetical more powerful computer; in contrast to the Turing machine, which corresponds to real computers, NTMs can do even more. Why can they do more? Basically, because they can branch off on several different options, or parallel universes; and they accept a string if and only if one of those universes accepts. A regular Turing machine corresponds to just having one parallel universe.

Let's see an example. Consider the following problem: Given as input an integer $x$, is the square root of $x$ an integer? Accept if yes, reject if no.

A Turing machine would have to do some math and figure out how to calculate the square root. So we have to do the hard work of designing a correct algorithm :(
An NTM doesn't have to do any of that hard work, and can just cheat :) It works in the following way: just nondeterministically guess the number $y$. Then check if $y^2 = x$. If so, accept.

This is how NTMs are unrealistic: they can just cheat and try all possibilities in different universes, even though when we know in the real world that this is impossible.
For example, if we input $9$ to the NTM we just described,
then there are lots of parallel universes that try different values of $y$: one tries $y = 1$, one tries $y = 2$, one tries $y = 3$, one tries $y = 4$, and so on. In many of these universes the NTM does the wrong thing: for example, it picks $y = 4$ and finds that $4^2 \ne 9$, and rejects (incorrectly). But those universes are just ignored; we don't care about them. The only thing that matters is that there is some universe where the machine accepts, namely the universe where we picked $y = 3$, and found that $3^2 = 9$.

  It is like telling the machine: you first do A, then if you find yourself in a state B and find the data is now B' then you choose for yourself one of the 10 allowed next steps?

It isn't exactly like "choosing for yourself"; it's that each choice is tried in a different parallel universe.

  Are NTM's corresponding to a set of algorithms that need uncertainty? for example the generation of random numbers?

No, they are a little bit different than uncertainty choosing random numbers, mainly because we only care about the parallel universes where the machine accepts (in particular, we care if there is at least one parallel universe where it accepts), and we ignore all the universes where the machine rejects.

  If no, why do we need to allow multiple choices for a Turing machine?

We don't need them to describe real computations, but they are a useful tool for understanding the limits of computation. In particular, there are many problems that NTMs can solve efficiently, that we don't know how to solve efficiently with TMs; these are the famous "NP-complete" problems, and it is useful in practice to know what problems will be hard to design an algorithm for.

  In this sense, an NTM looks like a multi-threading parallelization to save time?

Yes, it is a lot like this, except a little bit less general: the thing is that the multiple parallel universes cannot communicate, but they only work independently, and then we care if at least one universe accepts.

In other words, with a multi-threading machine, you could try lots of different parallel threads, and then at the end you could have all the threads come together, and then decide what to do with all the outputs of the different threads. NTMs can't do that; they just spawn off lots of parallel universes and accept if at least one universe accepts.

Another difference (in terms of practicality) is that multi-threading on a real computer usually only allows for a small (probably constant) number of parallel threads. On the other hand, NTMs can spawn off as many parallel universes as you like; if the input is size $n$, they often might spawn of $2^n$ threads, which is a larger number than is possible in practice. This is why NTMs are not a realistic type of machine, and are just a theoretical object of study.


Is this an $NP$-complete problem: Product-2-Partition I want to prove the NP-hardness of some problem P in scheduling theory. I was trying with Partition, 3-Partition and Subset product, But neither was successful.

Now, I can reduce a problem, say PRODUCT-2-PARTITION to P, but I am not sure whether such problem is $NP$-complete or not?

The problem PRODUCT-2-PARTITION is as follows:

Given $n$ integers. Can we partition them into $n/2$ subsets, where each subset contains exactly $2$ integers, and the product of the elements of any subset is equal to a given value $B$?

Denote these integers by $x_1\ge x_2\ge\cdots\ge x_n$. We assume these integers are all positive (it is not hard to revise the following algorithm for instances including both positive and negative integers).

In a valid solution, the greatest element must match the smallest element. Otherwise, say $x_1$ matches $x_i$ where $x_i>x_n$, and $x_n$ matches $x_j$, then $B=x_1x_i>x_1x_n\ge x_jx_n=B$, a contradiction. Hence a valid solution can only be $\{x_1,x_n\},\{x_2,x_{n-1}\},\ldots$ We only need to check whether this partition is valid, i.e. whether $x_1x_n=x_2x_{n-1}=\cdots=B$.


Using bit arrays to solve crossword puzzles I  have read Crossword Puzzles and Constraint Satisfaction by Connor, Duchi and Lo and I am trying to implement this variation of crossword solving algorithm. I can't understand the bit array data structure described on page 3, under "Lexicon". Could someone please give me an example?

PS: I have already implemented an efficient crossword solving algorithm but now I want to get even more serious in this difficult task.

Suppose we are looking for the set of all words of length 5 with a in first position and b in second position (an example is the word about).

Our lexicon contains up to $N = 2000$ words of each length. For each length, for each position in the word, and for each possible letter, we store the set of words of given length in which the letter at the given position is the given letter.

For example, suppose that there are 100 words of length 5. We identify these words with the numbers 1,2,...,100. There is an array of length 100 in which the $i$'th value is 1 if the $i$'th word starts with a, and 0 otherwise. There is another array of length 100 in which the $i$'th value is 1 if the second letter of the $i$'th word is b, and 0 otherwise. We can take these two arrays and compute their entrywise AND:
$$
\begin{array}{l|l}
\text{First array}  & 01110010\ldots \\
\text{Second array} & 11010011\ldots \\\hline
\text{Result}       & 01010010\ldots
\end{array}
$$
The $i$'th value of the new array is 1 iff the $i$'th word starts with ab.

Bit arrays are a space-efficient way to store Boolean arrays like the two arrays considered above, which also support fast operations like bitwise AND. The idea is simple – you store every value as one bit.


Can we create binomial heaps in linear time? I'm studying binomial heaps in anticipation for my finals and the CLRS book tells me that insertion in a binomial heap takes $\Theta(\log n)$ time. So given an array of numbers it would take $\Theta(n\log n)$ time to convert it a a binomial heap. To me that seems a bit pessimistic and like a naive implementation. Does anyone know of a method/implementation that can convert an array of numbers to a binary heap in $\Theta(n)$ time?

Wikipedia claims that insertion takes $O(1)$ amortized time, and so converting an array of numbers into a binomial heap should indeed take time $O(n)$. This is also supported by these lecture notes, and probably mentioned in CLRS.


finding a an object with constant velocity on an infinite grid in discrete time steps Assume you have an object moving at a constant velocity(up, down, left, right) in a grid. You have unlimited resources (memory, time). At any given time step in the grid, you can "guess" the location of the object, and you win if it is currently at that position. Without relying on probability techniques, what would be the best way to approach catching this object?

Hint: "Guess" the starting point and the velocity, and use diagonalization. (I.e. make a list $\langle p_i, v_i \rangle$ of pairs of starting points and velocities, and at time $t$ test $p_i + tv_i$.) I'll let you figure out why it works.


Is there an undecidable decision problem that computable algorithm for it leads to an algorithm for halting problem? Suppose, to the contrary, that there exists a computable algorithm for some undecidable decision problem. Would this mean that halting problem would be solved by a computable algorithm? I know that the converse is true for a decision problem in RE complexity class, but not for the other way around.

Let me rephrase your question. Suppose $O$ is undecidable; can Turing machines with an $O$-oracle solve the halting problem? There are some undecidable $O$ for which this is false. Constructing such $O$ is known as Post's problem, solved using the priority method; Wikipedia has some details.


Problems solvable in time $f(n)$ but not in time $o(f(n))$ Suppose I have some (increasing, nice asymptotics) function $f(n)$. Does there exist a complexity theoretic problem (e.g. PATH, 3-SAT, GO etc.) that can be solved in time $\Omega(f(n))$ on a deterministic Turing machine. In other words is there a problem proven to be an element of $\mathsf{DTIME}(f(n))$, but not $\mathsf{DTIME}(g(n))$ for any function $g$ such that $\frac{f(n)}{g(n)} \to \infty$ as $n \to \infty$?

Consider the language of all binary words which consist only of zeroes. It can be decided on a deterministic Turing machine in time $O(n)$, but not in time $o(n)$.
For general time-constructible functions $f(n)$, the time hierarchy theorem shows that the problem of deciding whether a Turing machine halts in time $f(n)$ can be solved in time $O(f(n)\log f(n))$ but not in time $o(f(n))$. It is not known how to eliminate this logarithmic gap in general.


Can the higher-order oracle Turing machines simulate the lower-order machines so that the current oracle does not contradict the simulated oracle? Here is a quote from the Source 1:

  For example, if $M$ is a machine with an oracle for the halting problem, then obviously there isn't in general an equivalent machine that can simulate the oracle.

But here is a quote from the Source 2:

  If you have an oracle for the halting problem, then you can compute the Busy Beaver function. Given an input $n$, just search through all Turing machines with $n$ states and check whether they halt or not. For the TMs that halt, run them through to completion, and count the number of steps or symbols printed. Keep track of the maximum score. After you have run through all possible Turing machines, you will have the Busy Beaver number.

I can imagine how this would work for the first-order oracle machine simulating a no-oracle machine, but I cannot understand how an oracle machine of the arbitrary order would simulate the lower-order oracle machine, assuming that the simulated machine can also simulate another machine with the arbitrary level of "nested" oracles!

For example, consider the computation process of a 4th-order oracle Turing machine equipped with a halting oracle for the 3rd-order oracle Turing machine. At some moment the program starts simulating some program for, say, 2nd-order machine. But how does the oracle interprets the content on the oracle tape when the simulated program goes into ASK state? If the oracle interprets this content as the question for the 4-th order machine, then the simulation is absolutely meaningless because the answer would not correspond to the answer provided by the simulated (2nd-order) oracle.

But if the mathematically correct simulation cannot be performed, then how would an $x$-th-order Turing machine with a halting oracle for the $(x-1)$-th-order machine compute the Busy Beaver number of any $(x-y)$-th Turing machine (where $1 \geq y \geq x$ and $y$ is a natural number)?

If such simulations can be performed without logical paradoxes, then is it possible to provide a pseudocode (similarly to this answer) that shows how some 5-th order oracle Turing machine obtains a value of $BB_4(x)$, and then the value of $BB_2(x)$?

The halting problem $\mathrm{Halt}_O$ for Turing machine with oracle access to $O$ is the language consisting of all oracle Turing machines $M$ that halt on the empty input when the oracle calls are interpreted as membership in $O$. A Turing machine with access to $\mathrm{Halt}_O$ can compute the busy beaver number for oracle Turing machines with oracle access to $O$.

Now to your other question. Let $O_0 := \emptyset$, and $O_{i+1} = \mathrm{Halt}_{O_i}$ (so $O_i = 0^{(i)}$ using the usual terminology). Let us show that given oracle access to $O_{i+1}$ you can simulate oracle access to $O_i$. Consider the following program:

  If $x \in O_i$ then halt, else run an infinite loop.

Using oracle access to $O_{i+1} = \mathrm{Halt}_{O_i}$ you can determine whether this program halts, which happens if and only if $x \in O_i$.

Applying this construction inductively, you can simulate access to $O_i$ given access to $O_j$ for all $j \geq i$. This shows that having an oracle for $O_j$ is indeed stronger than having an oracle for $O_i$ (when $i < j$).


How to find expected number of slots of a certain size k in hash table? If you can make no assumptions about the hash function, how can you find the expected number of slots of certain size k in a hash table? Looking more for a theoretical proof type of answer than a programming answer.

I assume under "size of slot" you mean length of chain in hash table with separate chaining collision resolution.

From Knuth, TAoCP, Vol. 3, 6.4, ex. 34 probability of k-length chain in hash table with $M$ slots and $N$ entries is

$\binom{N}{k} \left ( M-1 \right )^{N-k} / M^N$

Assuming "ideal" hash function, however practical real-world hash functions are often very good and could be considered as "ideal" for applying theoretical results.

Applying famous $e$ representations via limits and Stirling's approximation, I derived that the probability in terms of $α=N/M$ (load factor) is approximately equal to k-th value in Poisson distribution with parameter $λ=α$, i. e.

$\alpha^k e^{-\alpha}/k!$

Seems reasonable and was my first assumption before analysing the formula from TAoCP, because average chain length is obviously $α$, which correspond Poisson distribution expected value.

If $α$ (load factor) is equal to 0.75, then probabilities of slot chains to be of the specific length are:

k = 0 -- 0.47
k = 1 -- 0.35
k = 2 -- 0.13
k = 3 -- 0.03
k > 3 -- 0.01


How are data types related to information theory? I was just reading from wikipedia the following about information:

  From the stance of information theory, information is taken as a
  sequence of symbols from an alphabet, say an input alphabet χ, and an
  output alphabet ϒ. Information processing consists of an input-output
  function that maps any input sequence from χ into an output sequence
  from ϒ. The mapping may be probabilistic or determinate. It may have
  memory or be memoryless.

I'm just guessing here, but is the input alphabet the two states of a bit (0 and 1) and the output alphabet governed by the datatypes of the executing program when those bits are accessed?

Interpretation: The Link Between Data Types and Information Theory
I believe the missing link between these two topics, information theory and data types, is interpretation. Interpretation is essentially the "input-output function" for which output (meaning) is derived from input (data). Whether the interpretation is being performed by a computer, at compile-time or run-time, or a human is relative to the task at hand.

At any rate, data types are language-defined/user-defined interpretations of an input alphabet to an output alphabet. Also, language-defined data types usually have a direct relation to the size of storage locations on a computer.

Probabilistic vs. Deterministic "Mapping"
When determining the output based on a given input, is the output definite (deterministic) or is the output uncertain/ambiguous (probabilistic)?

Memory vs. Memoryless "Mapping"
When determining the output based on a given input, does the determining process require memory?


Turing machine: errata in computable numbers paper? I'm reading Turing On Computable Number 1936, specifically the section pictured here:

Does anyone see errata here?  Should the second m-configuration "c" in the table, have the "final m-config" be gothic e instead of the gothic c used?

If this were the case then 010101... could be printed.  If not, I'm unsure how 010101... is printed.

Thanks for your input.

The final m-config for the second configuration is an "e".


Is a kind of reverse Kleene star of a context-free language context-free? Recently I had a question on one of my assignments asking to prove or disprove the following:

Let $L$ be a language. If $L^*$ is context-free then $L$ is context-free.

Now obviously this is false since we can take some non-context free language $L_1$ and the alphabet $\Sigma$, then make $(L_1 \cup \Sigma)^* = \Sigma^*$ is context-free and clearly $L_1\cup \Sigma$ is not.

Now I was thinking about a similar problem but now with respect to the words in the language, and was wondering if it is true or not. If $C$ is a context-free language then $C'$ is a context-free language where $w\in C'$ if and only if $\{w\}^*$ is contained in $C$.

My suspicion is that this is also false, but I can't come up with a counterexample. Somehow one needs to construct a CFL $C$ such that the subset of all the "periodic" words of $C$ together are not context-free.

Let me solve a simpler question first. Suppose we'd like to know

  If $C$ is context-free, must $F(C)=\{w: ww \in C\}$ be context-free?

The answer is no: $F(\{a^i b^i c^j a^j b^k c^k\})=\{a^i b^i c^i\}$.

As for the original problem, consider the context-free language that contains words of the form $\{a^i b^i c^j d a^j b^k c^k d\}$ or those which don't contain exactly two $d$'s.

Define $D=\{w: w^\ast \subseteq C\}$. Suppose $D$ is context-free. Then $E=D\cap a^\ast b^\ast c^\ast d$ is context-free.

I claim $E=\{a^i b^i c^i d\}$, which is not context-free. Suppose $w = a^i b^j c^k d$. We have $w \in E$ exactly if $w^n \in C$ for every $n$. This condition is clearly satisfied when $n \neq 2$, because $w^n$ will not have exactly two $d$'s. For $n=2$, $w w=a^i b^j c^k d a^i b^j c^k d\in C$ which is equivalent to $i=j=k$.


What do queues and stacks correspond to in math? Many (and I suspect all) abstract data types in CS correspond to some math concepts, and even share the same names, for example, set, map, record/tuple, ....

As abstract data types, what do queues and stacks correspond to in math?
For example, some special paths in graph theory?

Have stacks and queues been treated mathematically and, if so, how are they usually treated within mathematic?

What mathematical concepts form the basis for stacks and queues?

Are there references that introduce data structures as models of monoids and other algebraic concepts? (Raphael said  data structures are)

As a practical matter, how you treat data structures mathematically largely depends what you're trying to do.

For example, suppose that you're trying to reason about the correctness of programs that use stacks and/or queues. In that situation, you'd want to treat the stack/queue as an abstract object, and axiomatise its properties. So you develop (say) a theory of stacks which can be layered on top of a general theorem prover.

You can do this quite straightforwardly in constructive type theories, such as the calculus of constructions. It's worth taking a look at the theories that come with Coq (the proof management system); it has a theory of strings, a theory of lists, a theory of maps, and so on.

Having said that, stacks and queues in some contexts do model mathematical objects. I'm going to run with the example of pushdown automata. In this case, the stack symbols are a fixed finite set (and they have no structure; it makes no sense to do maths on the stack symbol names themselves!), and so the stacks form an interesting algebra.

I'm going to start with regular languages, which we can axiomatise as a Kleene algebra. A Kleene algebra is an idempotent semiring plus the Kleene star operator. The two ring-like operations $\cdot$ and $+$ correspond to concatenation and set union, and $0$ and $1$ correspond to the null set and the empty string.

We know that DFAs and regular expressions are basically the same thing. We also know that pushdown automata are like DFAs, only they also do stack operations. There's no reason why we can't put stack operations in regular expressions; in this way, we could express context-free languages using a regular expression-like operation.

So let's do that. We'll denote a stack push of symbol $i$ using the notation $\left\langle i \right|$ and a pop using the notation $\left| i \right\rangle$. Now we need to work out how these stack operations work algebraically.

Terminal symbols commute with stack operations, in the sense that reading as symbol followed by a stack push or pop is the same as doing the stack operation followed by reading the symbol:

$$a \left\langle i \right| = \left\langle i \right| a$$
$$a \left| i \right\rangle = \left| i \right\rangle a $$

Finally, we need to work out what happens when two stack operations meet. A push of a symbol followed by a pop of the same symbol is equivalent to reading the empty string (i.e. doing nothing):

$$\left\langle i \right| \left| i \right\rangle = 1$$

However, pushing a symbol followed by trying to push a different symbol cannot happen. This is equivalent to the empty set (i.e. the language with no strings in it):

$$\left\langle i \right| \left| j \right\rangle = 0, \hbox{if}\,i \ne j$$

In other words, we're looking at something very like a vector space. Strings of terminals behave like scalars, and stack operations behave like vectors and one-forms. When a push meets a pop, they behave like an inner product where the basis vectors are orthonormal.

Moreover, if the stack is nonempty, then any pop followed by a push of the same symbol should be a no-op:

$$\left| 1 \right\rangle \left\langle 1 \right| + \left| 2 \right\rangle \left\langle 2 \right| + \cdots + \left| n \right\rangle \left\langle n \right| = 1$$

Using this algebra, we can (say) express $a^n b^n$ as $\left\langle 1 \right| (a \left\langle 2 \right|)^* (b \left| 2 \right\rangle)^* \left| 1 \right\rangle$. It's a little unwieldy, but it works.

Attentive readers might have caught on why I used this notation (lovingly stolen from Mark Hopkins): this is a Dirac algebra, as used in quantum mechanics.

It turns out that the analogy goes quite deep. A Turing machine can be thought of as an automaton with two stacks, and if you allow gradations between $0$ and $1$, you can axiomatise quantum Turing machines.

However, this is not the point I'm trying to get across. The point is that in this case, the stack operations form an interesting algebra which was discovered in a completely different context.

This alone answers your question with a resounding "it depends".


Why can't we mimic a dog's ability to smell COVID? As far as I can tell, we have invented tools and algorithm to:

Detect a wider range of colors at a larger range than humans or any other animals on the planet
Detect sound with wavelengths inaccessible to humans or most animals on the planet

But why is it that dogs can smell COVID or Cancer and we can't produce a similar tool to "smell diseases"? Why can't we mimic the dog's sense of smell: is it a hardware limitation or a software one? Am I mistaken in thinking that this sense is the hardest to mimic?

We can actually detect some diseases via smell, and the term to search for is olfaction.  The general problem is known as breath analysis.
However, the research into olfaction and machine learning is rather new (perhaps even surprisingly new).  As Lötsch et al. point out, little research (prior to the very recent research) on olfaction and machine learning has been performed, with a few exceptions:

Quantifying olfactory perception: mapping olfactory perception space by using multidimensional scaling and self-organizing maps, Mamlouk et al., Neurocomputing, 2003.
Relationships between molecular structure and perceived odor quality of ligands for a human olfactory receptor, Sanz et al., Chem Senses, 2008.
Diagnosis and Classification of 17 Diseases from 1404 Subjects via Pattern Analysis of Exhaled Molecules, Nakhleh et al., ACS Nano, 2017.
And the one mentioned above, Machine Learning in Human Olfactory Research, Lötsch et al, Chemical senses, 2019.

I don't know whether the problem in general is harder, but as you are touching  on in your question, the problem is much harder from a hardware perspective.  Where imaging only needs a simple camera, and hearing only need a simple microphone, to detect smell you need a so-called
as chromatography–mass spectrometry instrument. As the Wikipedia article mentions:

Breath gas analysis consists of the analysis of volatile organic compounds, for example in blood alcohol testing, and various analytical methods can be applied.

Here are some pointers from popular science that should assist you in getting into the literature:

Scientists Invent An AI That Can Smell 17 Diseases From Your Breath, Including Cancers

Innovative AI Breath Analyzer Diagnoses Diseases by “Smell”

AI is acquiring a sense of smell that can detect illnesses in human breath


Finding the maximum disjoint weight in a weighted node graph I have a graph of nodes that reflect resource allocation. Each node has a weight to reflect this. A well formed graph is disjoint, so there will be no edges, and the weight of the graph is just the sum of the nodes. Any graph that contains edges needs to be reduced by removing one of the two nodes on an edge, until all edges are removed and the graph becomes disjoint. After reducing a graph the total weight should be the maximum possible.

I have already tried an algorithm that simply picks the largest node and discards the connected nodes. This has the problem that it may give a total that is too low.

So I need to find a new algorithm that will be accurate more consistently. My current idea is to look at the graph around each node and determine the difference between that node's weight and the total weight of the connected nodes.

Select the node with the largest difference
A positive difference means select the node and ignore the others
A negative difference means ignore this node and select the others
For a difference of zero it's not as clear which side to select
Repeat

At each stage, at least one node (and it's related edges) will be discarded from the graph. Eventually the graph will be made fully disjoint.

Are there any other approaches, and what are the differing costs in terms of time and memory?

Below are some simple examples

Case 1

AA:2, AB:3

No edges, so total weight is 5.

Case 2

BA:3, BB:2, BC:5, BD:2

BB <> BC, BC <> BD

Total weight is 8 (BA + BC)

Case 3

CA:2, CB:3, CC:5, CD:3

CB <> CC, CC <> CD

Total weight is 8 (CA + CB + CD)

My current approach would report 7 (CA + CC)

Case 4

DA:4, DB:3, DC:3, DD:3, DE:4

DA <> DB, DA <> DC, DA <> DD, DC <> DE, DC <> DE

Total weight is 9 (DB + DC + DD)

My current approach would report 8 (DA + DE)

Case 5:

EA:4, EB:3, EC:3, ED:3, EE:4

EA <> EB, EA <> EC, EA <> ED, EB <> EC, EC <> EE, EC <> EE

Note there is complete sub graph between nodes EA, EB, and EC

Total weight is 8 (EA + EE)

The problem that you are trying to solve is called "maximum weight independent set". It is NP-hard so not much hope for exactly solving it efficiently. There exist efficient approximation algorithms though (see e.g. this question).


$P$-complete problems and Logspace reductions It is known that HORN-3SAT is complete for $P$ under Logspace many-one reductions ($<_L^m$).

This implies that $\bar{A} <_L^m A$ for any $P$-complete problem $A$, where $\bar{A}$ means the complement of $A$. This immediately follows from that fact that $P$ is closed under complement and the $P$-hardness of $A$.

My question is to find such Logspace many-one reduction $\bar{A} <_L^m A$ for any $P$-complete problem $A$ (such as HORN-3SAT). The reduction must show the mapping between short certificates of $A$ and $\bar{A}$.

EDIT: As David stated in his comment on the case of HORN-3SAT problem,  we know that Logspace function exists but it seems that it is hard to find explicitly.

The circuit value problem: input is a Boolean formula and a truth assignment to its variables; accept if, and only if, the input is well-formed and the formula evaluates to true under the given assignment. The complement is to accept iff the input is malformed or the formula is false.

The reduction is to check that the input is well-formed.  If so, output the negation of the formula, with the same truth assignment; if not, output either $X; X=\mathrm{t}$ or $X; X=\mathrm{f}$, depending on which way you're going.


Best approach to resource allocation problem Problem

The enemy army has taken $n$ of our cities. In each city $i$ the enemy has placed $e_i$ soldiers. We have $n$ teams, each team $j$ with $d_j$ soldiers. If we place more soldiers in a city than the enemy, we retake the city. Our aim is to distribute our teams so that we maximise the number of retaken cities if:

We can only place one team per city
There is no limit to the number of teams we can play in each city.

Question
I'm trying to figure out which approach might be best for each option (greedy algorithm, divide-and-conquer, dynamic programming, backtracking). I'm not necessarily looking for the particular algorithm, although I'd be happy to get it too.
Previous work
One team per city
The best approach would be a greedy algorithm, which would assign to each city the smallest team which can defend it, starting from the smallest team. If at some point the smallest remaining team cannot take the smallest remaining city, we can simply dump that team.
No restriction for the number of teams per city
I can think of a greedy algorithm similar to the previous one, in which we assign the smallest teams to the smallest city until it's defended, and then move to the next one. However, I am not certain this would lead to an optimal solution, unlike the previous case.
Backtracking explores the solution space exhaustively, so it would work but it's ineffective. Dynamic programming looks promising, as this superficially looks like a variation of the knapsack problem, but I know that generalisations/variations might not necessarily be tackled with the same approach.

Let us first show that your proposed greedy algorithm for the second restriction is not optimal.
For this, consider a scenario with $e_1 = 1, e_2 = 3$ and $e_3 = 4$ as well as $d_1 = 1, d_2 = 2$ and $d_3 = 3$.
The greedy algorithm would assign $d_1$ and $d_2$ to the first city and $d_3$ to the second one, leading to only one city being retaken.
However, if we assign $d_2$ to the first city and $d_1$ and $d_3$ to the second one we could retake both of them and hence, the greedy algorithm is not optimal.
As for algorithmic approaches, note that your problem given the second restriction (let's denote it by $L$) is $\mathsf{NP}$-complete which can be shown by reducing $\mathrm{Partition}$ to $L$:
For a $\mathrm{Partition}$ instance given by a multiset $S$ of integers define an $L$-instance where the multiset of the $d_i$s is given by $S$, i.e. for every element of $S$ we create a team of the same size.
Denote by $X$ the sum of the elements of $S$ and set $e_1 = e_2 = X/2 - 1$ as well as $e_i = X + 1$ for all $i > 2$.
Now note that we can retake at most $2$ cities (as we don't have enough forces to retake any city which is held by at least $X$ soldiers) and we can only retake both of them if we can split our forces exactly in half, sending $X/2$ soldiers to the first and second city, respectively.
It follows that $S$ is a yes-instance of $\mathrm{Partition}$ if and only if we can retake 2 cities in our constructed $L$-instance (I left out some technical details but this reduction should work out just fine).
Assuming $\mathsf{P} \neq \mathsf{NP}$ this result implies that $L$ has no (deterministic) polynomial time algorithm. For some further lower bounds, see the other answer.


What is the usage of CYK algorithm in the real world considering we have algorithms with a much better Time complexity? So considering CYK is O(n^3) and since we can just use LR(k) algorithms for DCFG's which they can check if a string is in the language in O(n) then whats the usage of CYK?

is it being used anywhere?

If I'm not mistaken(correct me If I'm wrong) the benefit of CYK is that since we can convert any CFG to CNF form therefore i guess we can apply this to non deterministic CFG's and also Inherently ambiguous grammars which are CFG

but are these really benefits? i mean whats the usage of using membership algorithm for Inherently ambiguous CFG's or non deterministic CFG's? where would we use a Inherently ambiguous CFG or non deterministic CFG ?!

Isn't the main usage of membership for compilers? which they already use LR algorithms?

Here is one benefit:

Some grammars aren't LR(k).  Then it's useful to have CYK or some other form of GLR parsing.  GLR parsing is used in some compilers, where the most natural way to express the grammar leads to a grammar that isn't LR(k), or where ambiguities are resolved in a later pass (not part of the parser).


If a key in a red-black tree has exactly one child (which isn't null) then it is always red I have the following claim:

Prove or disprove: If a key in a red-black tree has exactly one child (which isn't null) then it is always red.

My attempt:
Disproof.
We will exhibit a counterexample:

This tree satisfies the conditions of being a red-black tree,
since:

The root is black.
All leaves are black.
There isn't any red key.
In each path there is the same amount of black keys, in particular, we have three black keys in such paths.

However, we have two keys in level 1, which have one child and it is black.
$\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad  \blacksquare$

Is this counterexample correct?

The disproof is wrong because in your Red-Black tree, all possible leaves need to be represented (see exemples on wikipedia). That means that the real tree represented should be:

It is easy to see that it does not respect the fourth condition of the definition.
In the claim, when it is said that:

a key […] has exactly one child (which isn't null)

it actually means that it has two children, and exactly one of them is null. It is due to the fact that in the representation of a red-black tree, you can either represent ALL null leaves or represent none.
I will let you try to prove or disprove the claim knowing that and edit this answer if necessary.


Decidability of languages with dfa/turing-machines For any alphabet and any natural number k, a language of strings at least k is decidable.
So my question is having some alphabet (let's say (0,1)) and some number let's say k=5 then my language has every string of 1's and 0's that are 5 or more characters at length (ie 01101, 011011 belong to language, while 011,10,1100 does not). Can such language be decidable and how so?

The easy and immediate way to see this is to note that the language of strings of length at most $k$ is finite, therefore it is regular. Regular languages are closed under complementation (just switch the accept and reject states), so your language of strings of length greater than $k$ is also regular.


Partial path known in Single source shortest path problem I'm using the A* algorithm with a consistent heuristic on a graph to determine the shortest path.

If the algorithm is exploring a node $p_1$ for which there is a existing knowledge about the optimal $k$ ($p_q,p_r,p_t,p_5$) successive nodes, then can we store $p_5$ directly into the open list? Or do we have to store the intermediate milestones (each node in the known successive optimal nodes) into the open list?

Weights are positive real numbers.

Your question is strongly related to the idea of macro-moves which are defined as follows: $M(p, q)=\langle p, n_1, n_2, \ldots, n_k, q\rangle$, i.e., as a list of successive states which are known to get to $q$ from $p$. Additionally, macro moves might guarantee that the path they store is also optimal, i.e., that the path $\langle p, n_1, n_2, \ldots, n_k, q\rangle$ is the shortest path between $p$ and $q$. Let us denote such macro-moves as $M^*(p, q)$.

In the following I'll assume you are interested in computing the optimal path from a start state $s$ to an arbitrary goal state $t$ ---as you actually mention the "shortest path" at the beginning.

So now, regarding your question:

In case that $M^*(p,q)$ is known to be a subpath of the optimal path from $s$ to $t$, or if alternatively, it is known that the optimal path from $s$ to $t$ does not go through $p$, then you can safely substitute each generation of $p$ in OPEN by $q$ with a cost equal to the cost of the path to generate $p$ plus the cost of the path $M^*(p,q)$.
In case none of the preceding conditions hold then you can still use the macro-moves but you have then to store each node in $M(p,q)$, but $p$ of course, into the OPEN list ---i.e., the intermediate milestones you mention.

Hold on! You might think then that the second case is a waste of time/space, but it ain't if you break ties in favour of nodes with larger $g$-values, i.e., while nodes in OPEN are sorted in increasing order of their $f$-value, breaking ties in favour of nodes with larger $g$-values place those nodes with larger $g$-values first ---within the same $f$-layer. This way, in case that an optimal path (as there might be several paths with the same cost and equal to the minimum cost) goes through $p$ there is an opportunity that you will find it without generating other descendants.

To see why, consider that a subpath of $M^*(p,q)$ is part of the optimal path from $s$ to $t$, $\langle p, n_1, n_2, ...,n_\ell\rangle$, such that $\ell\leq k$, and let $g(n)$ denote the cost of the path from $s$ to $n$ and $g(p, n_i)$ denote the cost of the path $\langle p, n_1, n_2, ..., n_i\rangle$ where $\langle p, n_1, n_2, ..., n_i\rangle\subset M^*(p,q)$. The second case suggests to insert into open $n_1, n_2, ..., n_\ell$ each with a cost equal to $g(p)+g(p,n_i)$, $1\leq i\leq\ell$. If the heuristic function is consistent (as you mention) there is a good opportunity that $f(n_\ell)=f(n_i)$, $\forall i, 1\leq i<\ell$. Now, breaking ties in favour of nodes with larger $g$-values, $n_\ell$ will be placed before the others so that A$^*$ will expand it first. If $f(n_\ell)$ equals the cost of the optimal path then A$^*$ will find the optimal solution with out expanding nodes $n_i$.

Maybe you think there are many "maybes and ifs" here but consider: first, breaking ties in favour of larger $g$-values is customary practice; second, inserting the intermediate states of $M^*(p, q)$ causes no harm so that proceeding as in the second case is usually a good idea.

Hope this helps,


Is there an efficient algorithm for determining whether or not a graph has a non-trivial automorphism? I'm working on a problem related to Latin squares, and I want a method for what essentially boils down to the decision problem:

Input: A finite, simple graph G.
Output: YES if G has a non-trivial automorphism, NO otherwise.

Hence...

Question: Is there an efficient algorithm for determining whether or not a graph has a non-trivial automorphism?

We could use Nauty or Bliss (and possibly some other packages) to compute the whole automorphism group, but I don't need it;  all I need to determine is whether or not it's trivial.

It's possible this decision problem is theoretically equivalent in complexity to "compute the whole automorphism group" in some way.  I'm not sure.

For my purpose, "efficient" basically means "faster in practice than computing the whole automorphism group", but I'm also interested in the theory behind it.

Since you are also interested in the theory behind it, I would give you a quasi-polynomial time algorithm for your problem.

For each pair of vertices $u\neq v$ (of same degree) in $G$, we try to see if it it possible to swap $u$ and $v$.

To do this, make a copy of $G$, call it $G'$. Now, delete $u$ from $G$, delete (copy of) $v$ from $G'$.

Then, for each $w\in N(u)$ attach to it a very long path, but only polynomially long.

Then, for each (copy of) $w\in N(copy\ of\ v)$ attach to it a very long path, but only polynomially long.

All the mentioned above very long path, but polynomially long, should be of the same length.

Call Babai's algorithm on the input of this newly produced pair of graphs.

If for any pair $(u, v)$, we have a $YES$ answer from Babai's, answer $YES$ and halt.

If none returns a $YES$ answer, answer $NO$ and halt.

Clearly, attaching to all vertices in $N(u)$ and $N(v)$ forces the graph isomorphism of Babai's inner working mechanism of his algorithm to only map vertices in $N(u)$ to $N(v)$. Thus, if Babai's answer is $YES$ then we can safely plug in back $u$ and $v$ to have a non-trivial automorphism of $G$, since $G'$ is a copy of $G$.

The run-time complexity is still quasi-poly.


proving that if $\{w\$w^R | w \in L\}$ is context-free then $L$ is regular I am trying to prove this following theorem, can someone help please?

Let $L$ be a language over the alphabet $\Sigma = \{ a,b \}$.
If $L' = \{ w\$w^R \mid w \in L\}$ is context-free, then $L$ is regular.

Here is a proof sketch. The idea is to take a context-free grammar for $L'$ and come up with a regular grammar for $L$.

Start with a grammar for $L'$. Say that a language $M$ is symmetric if it is of the form $\{w \$ w^R : w \in P\}$ for some $P \subseteq \Sigma^*$. Prove that every non-terminal in $L'$ generates a language of one of the forms $w, wM, Mw$, where $w \in \Sigma^*$ and $M$ is symmetric. Consider two cases: the non-terminal generates a word without $\$$, or it generates a word with $\$$. In the first case, it's easy to see that it must generate a unique word. In the second case, every word it generates must contain $\$$, and the words need to be "compatible" in some sense, which implies that it generates a language of the form $wM$ or $Mw$.

For each non-terminal generating $wM$ or $Mw$, we can come up with a non-terminal generating the language $M$. This is because context-free languages are closed under this operation. So we can assume without loss of generality that each non-terminal either generates a unique word or a symmetric language.

Substitute all non-terminals generating unique words. All remaining productions must be of the form $A \to w B w^R$ or $A \to w \$ w^R$. We can come up with an equivalent grammar in which $w$ is always a symbol in the first case and empty in the second, so that all productions are now either $A \to a B a^R$ or $A \to \$$. If we replace these productions with $A \to a B$ and $A \to \epsilon$ then we get a right regular grammar for $L$.

For completeness, let me mention that the converse to the theorem also holds. You can see this by reversing the construction: from a right regular grammar for $L$, construct a context-free grammar for $L'$.


Can someone help me understand the time and space complexity? Can anyone help me understand the time and space complexity here? I know zip() is O(1) and sorted() is O(n). The loop has the operation min() inside but is operating on just 2 values so is that also O(1)? If so then every operation in the loop is O(1) so the overall time complexity is O(n) correct? For space, z could grow to n as a and b grow to n as well so space is O(n)?
a = [3, 1, 2]
b = [1, 2, 3]
c = 4
def foo(a: list[int], b: list[int], c: int) -> int:
    ans = 0
    if not a:
        return ans
    z = sorted(zip(a, b), reverse=True)
    for x, y in z:
        if c > 0:
            x = min(x, c)
            ans += x * y
            c -= x
    return ans

Assuming that sorted() really takes time $O(n)$, then the time and space complexities are indeed $O(n)$. Hoewever there are some catches.
You say that the zip function takes $O(1)$ time. This is technically true, but you should be aware that zip is not creating a list that contains pairs of elements from a and b but just returning an iterator to these pairs. Going through the list implicitly returned by this iterator takes $O(n)$ time, even just to construct it (e.g., list(zip(a,b))). In your particular case this doesn't really matter since the time complexity will be $\Omega(n)$ anyway.
You say that sorted() takes $O(n)$ time. This is not impossible, but it's at least suspicious (have you checked in the python documentation/implementation?). There is no algorithm that can sort a list of $n$ elements in time $O(n)$ by only performing comparisons. The implementation of sorted() would need to be particularly clever and recognize that you are sorting small integers.
Probably sorted() just takes $O(n \log n)$ time and $O(n)$ space, which would result in the same overall time and space complexities for your algorithm.