texts: Find the shortest sub-tree with node deletion

texts:
Let $T=(V,E)$ be a tree rooted in $r$ and let $L$ denotes the set of leaves of $T$. For a given $v \in V$, let $C(v)$ be the out-neighors of $v$ i.e. its children in $T$ and $p(v)$ be its in-neighbor i.e. its predecessor in $T$. We have a metric $d : V \times V \rightarrow \mathbb{R}^+$ (respecting the triangular inequality). The length of the tree is then $\sum_{u \in V} d(u,p(u))$.

For a subset of internal non-root nodes $V' \in V \setminus (L \cup \{r\})$,  the rooted "sub-tree" $T'$ corresponds to the tree we get after removing each $v\in V'$ and connecting its parent $p(v)$ to all $C(v)$. An example:

My problem is to find the subset of internal $V'$ to remove such that the sub-tree $T'$ has the minimum length. Below are some observations I made (maybe the problem is well-known but if it's not then they may provide some insight). Any remark/reference is most welcome!

Steiner tree related problem?

My first thought was that this problem is a special case of the Steiner tree problem. We can construct a graph $G=(V,A,d)$ with $A = \{(u,v) \in V \times V : u  \text{ is an ancestor of } v \text{ in } T\}$, edge length $d$ and $L$ as the set of terminal nodes. However a Steiner tree of $G$ may correspond to solutions that are impossible to get via node removal on $T$. Indeed, node removal preserves the siblings relations existing in $T$. This may not the the case for Steiner trees in G.

That being said I would be interested to know the complexity of the Steiner tree problem for graphs constructed like G. I suspect the problem to still be NP-hard.  Note that the approximate solution obtained by taking a minimum spanning tree according to shortest-paths distances would be the star graph connecting the terminal nodes to $r$ (since $d$ respects the triangular inequality).

Iterative/Recursive solution or approximation?

Assuming $T$ is of height $2$, we only need to check if each internal node $u$ respects the inequality

\begin{equation}
\sum_{l \in C(u)} d(l,r) > d(u,r) + \sum_{l \in C(u)} d(l,u) \text{        (Ineq. 1)}
\end{equation}

and add it to $V'$ if it does not. In the general case, a possible approach is therefore to iteratively remove the nodes that do not respect the Ineq. 1. However, such "local" approach may lead to the best solution. For example assume the distances $d$ for the example in Figure 1 are (sorry for the formatting):

   d(.,.) | r | a | b | l_(1,2,3) | l_4 | l_5 |
   ____________________________________________
   r      | 0 | 2 | 2 | 1         | 3   |   1 |
   a      |   | 0 | 1 | 2         | 1   |     |
   b      |   |   | 0 | 1         |     |     |

Here Ineq. 1 is respected for both internal node $a$ and $b$. However, the shortest tree is the one obtained after the removal of both nodes.

I therefore tried to apply Ineq. 1 in a recursive fashion. I check it not only for the direct parent but for all the ancestors. The procedure is as follow:

Procedure ShortestSubTree$(T,u,d)$:

For $v \in C(u) \setminus L$ do

ShortestSubTree$(T,v,d)$

$a \leftarrow p(u)$
While $a$ is defined do

If $\sum_{v \in C(u)} d(a,v) \leq d(u,a) + \sum_{v \in C(u)} d(u,v)$ then

remove $u$ from $T$
stop

$a \leftarrow p(a)$

However it seems that ShortestSubTree removes too many nodes. In some experiment, the "iterative" approach can produce shorter sub-trees.


texts: It is well known that if some computing apparatus is Turing-complete, then the halting problem is undecidable for that computing apparatus. However, is it true that if the halting problem is undecidable for some computing apparatus, then it is Turing-complete?


texts: Counting words that satisfy SAT-like constraints with BDDs

texts:
I have the following #P-complete problem:

Given an alphabet $\Sigma$ and a matrix $M$ where each entry can be a symbol from $\Sigma$ or the wildcard symbol $*$, find the number of strings $s$ with the property that there exists $i$ such that for all $j$, $M_{i,j} \neq *$ implies $s_j = M_{i,j}$.

Example:
If $\Sigma = \{a,b,c\}$ and $M$ =
$$\left(\begin{matrix}
a&*&b \\
*&c&*
\end{matrix} \right)$$
then there are three satisfying strings: $aab,abb,acb$.

I was told this can be solved using BDDs, somehow, such that a lot of caching is possible. How does that work? Also, what are other algorithms for this?

Proof of #P-completeness:
We reduce from #UNSAT, the problem of counting the number of unsatisfying assignments for a boolean formula. Given a formula $\varphi$ with $n$ variables and $m$ clauses, make an $m$ by $n$ matrix $M$ over the alphabet $\Sigma = \{0,1\}$ such that
$$M_{i,j} = \begin{cases}
1\text{ if the $j^{th}$ literal is unnegated in the $i^{th}$ clause,} \\
0\text{ if the $j^{th}$ literal is negated in the $i^{th}$ clause,} \\
*\text{ otherwise.}
\end{cases}
$$
Then the number of strings with the above property equals the number of unsatisfying assignments for $\varphi$.


texts: How to design an algorithm to generate balanced teams?

texts:
I am trying to design an algorithm that allows to create balanced teams for a summer camp. There are about a 100 campers of different ages. Gender ratio isn't necessarily 50/50. Also there are a different number of campers for each age group.
The idea is to create fair and well-balanced teams while having approximately the same amount of boys and girls in each team as well as the same number of kids in each age group per team.
The usual approach is to make a list and manually make the teams (prior to the camp), but this is stupid and has a lot of balancing issues.

My idea is to create an algorithm based on some kind of score (eg. time to run an obstacle course) simple enough to be programmed in excel or some other tool everybody knows how to use. My first idea of how it could look like is:

Separating boys and girls into different categories
Ordering them from fast to slow (this should still make it so that the oldest kids are roughly at the top of the list and the slowest at the bottom)
Design algorithm that creates teams with the same averages while taking kids from all over the list. This is the part I'm having trouble with because I don't want to use iterative methods.
Once I have the boys teams and girl teams ready mix them together so that

4.1 Each group has the same amount of kids (number of boys + number of girls)

4.2 The average time of each team should be as close as possible (here are iterative methods ok because there are less combinations)

If anyone has experience, ideas or has seen something similar I'd gladly read it.


texts:
Please help me regarding this one! What will be the communication and computation complexity of this code??

While (m>0) do
{
   While ((m mod 2)==0) do
       {
          m ← ⌊m/2⌋
         //parties communicate m times;
       }
m = m – 1;
}

This code been modified from the book "Fundamental of computer algorithm" by Sahni.So according to that, it seemed computational complexity is O(logm) as m decreases by a factor of at least 2. But can i say communication complexity is O(logm) as well?? Probably not; i'm really confused!!


texts: Is a degree-$d$ pseudo distribution always a relaxation?

texts:
The optimization problem we are generally concerned with looks like the following,
\begin{eqnarray*}
&\inf \{ p(x) \vert x \in K\} \\
&K = \{ x \in \mathbb{R}^n \vert q_i(x) \geq 0, i = 1,..,m \}
\end{eqnarray*}

where $p(x)$ is some polynomial objective function and $q_i(x)$ are polynomial constraints.

One can look at this corresponding question,

\begin{eqnarray*}
&\inf_D \{ \tilde{\mathbb{E}_D} [p] \} \\
&s.t \\
&D : \{ 0,1\} ^n \rightarrow \mathbb{R} \\
&\sum_{x \in \{0,1\}^n} D(x) = 1 \\
& \forall u \in SOS_d \\
&\tilde{\mathbb{E}}_D [u] \geq 0 \\
&\tilde{\mathbb{E}}_D[q_i] \geq 0
\end{eqnarray*}

Here we use the ``pseudo-expectation" notation" whereby we have for any function $f$, $\tilde{\mathbb{E}}_D[f] = \sum_{x \in \{ 0,1\}^n } D(x)f(x)$ And $SOS_d$ is the cone of all real polynomials in $n-$variables which can be written as a sum of squares of polynomials of degree at most $\frac{d}{2}$

Is it clear that for all $d$ the later is a relaxation of the former?

If we restrict the polynomials to be valued on the hypercube $\{0,1\}^n$ then I can think of an argument which shows that the latter is a relaxation of the former by going through an intermediate Lassere relaxation. But if the polynomials are valued on the whole of $\mathbb{R}^n$ (as written above) then my above argument works only if $n^d < 2^n$.
Is there a proof that if one keeps increasing the $d$ then at $d=n$ the later will exactly hit the infimum being searched for in the first?


texts: Algorithmic Complexity of Statistical Estimators

texts:
This might be very basic but I am interested in evaluating the algorithmic complexity of an estimator of the form:

$$\hat{\theta} = \text{argmin}_{\theta} \;\; Q_n (\theta)$$

where $Q_n(\theta)$ denotes some objective function of interest (e.g. - log likelihood) computed on a sample of length $n$. $\hat{\theta}$ is assumed to be obtain through some numerical optimization methods (typically a stepwise procedure). Under this setting, how could I compute the algorithmic complexity of $\hat{\theta}$?

I am really not sure if this makes sense but here is how I approach this problem:

Suppose that the numerical procedure used to compute $\hat{\theta}$ requires $S$ steps to converge.
Assume that there exist a deterministic function, say $f(p)$, where $p$ denotes the dimension of $\theta$ such that $S \leq f(p)$ and that $f(p) < \infty$ for $p < \infty$.
Assume that $\mathcal{O} (Q_n(\theta)) = g(n)$ for all $\theta$.
Then $\mathcal{O}(\hat{\theta})$ is simply given by

$$\mathcal{O}(\hat{\theta}) = \mathcal{O}(Q_n(\theta) S) = g(n),$$

since $p$ is assume to be fixed (and bounded). This seems really too simple... Any comments would be more than welcome. Thank you very much.


texts: Fixed-length decision-tree-like feature selection to minimize average search performance

texts:
I have a complex query $Q$ used to search a dataset $S$ to find $H_\text{exact} = \{s \in S \mid \text{where $Q(s)$ is True}\}$. Each query takes on average time $t$ so the overall time in the linear search is $t\cdot |S|$. I can break a query down into simpler sub-queries q_i and find $H_\text{approx} = \{s\in S \mid \forall q_j(s) \text {is True}\}$  and where $H_\text{exact}\subseteq H_\text{approx}$. Each subquery $q_i$ is much faster to compute, so overall it is faster to find $H_\text{approx}$ and then use $Q$ to find $H_\text{exact}$.

Each $Q$ has many $q_i$. The overlap between different $Q$ is high. I'm looking for a way to determine a decision-tree-like set of fixed questions $q_j$ which minimize the average time to find a H_exact, based on a large sample of search queries.

To make this more concrete, suppose the data set contains the 7 billion people in the world, and the complex queries are things like "the woman who lives in the red house on the corner of 5th and Lexington in a city starting with B."

The obvious solution is to check every person in world and see who matches the query. There may be more than one such person. This method takes a long time.

I could pre-compute this query exactly, in which case it would be very fast .. but only for this question. However, I know that other queries are for the woman who lives on the blue house on the same corner, the man who lives on the same corner, the same question but in a city starting with C, or something totally different, like 'the king of Sweden.'

Instead, I can break the complex question down into a set of easier but more general sets. For example, all of the above questions have a gender-role based query, so I can precompute the set of all people in the world who consider themselves a 'woman.' This sub-query takes essentially no time, so the overall search time decreases by roughly 1/2. (Assuming that by other knowledge we know that a Swedish "king" cannot be a "woman." Hatshepsut was an Egyptian woman who was king.)

However, there are sometimes queries which aren't gender-based, like "the person who lives on 8th street in a red house in a city starting with A." I can see that the subquery "lives in a red house" is common, and pre-compute a list of all those people who live in a red house.

This gives me a decision tree. In the usual case, each branch of the decision tree contains different questions, and the methods to select the optimal terms for the decision tree are well known. However, I'm building on an existing system which requires that all branches must ask the same questions.

Here's an example of a possible final decision set: question 1 is 'is the person a woman?', question 2 is 'does the person live in a red house?', question 3 is 'does the person live in a city starting with A or does the person live in a city starting with B?', and question 4 is 'does the person live on a numbered street?'.

When a query $Q$ comes in, I see if its $q_i$ match any of the pre-computed questions $q_j$ I've determined. If so, then I get the intersection of those answers, and ask the question $Q$ on that intersection subset. Eg, if the question is "people who live in a red house on an island" then find that "person lives in a red house" is already precomputed, so it's only matter of finding the subset of those who also live on an island.

I can get a cost model by looking at a set of many $Q$ and check to see the size of the corresponding $H_\text{approx}$. I want to minimize the average size of $H_\text{approx}$.

The question is, how do I optimize the selection of possible $q_j$ to make this fixed decision tree? I tried a GA but it was slow to converge. Probably because my feature space has a few million possible $q_j$. I've come up with a greedy method, but I'm not happy with the result. It too is very slow, and I think I'm optimizing the wrong thing.

What existing research should I be looking at for ideas?


texts: Algorithm for converting (coordinates + reach radius) data to directed graph

texts:
I am trying to find a solution better than O(n2) for the following problem:

There are N points on a 2-D plane (N $\le$ 106), with integer coordinates between -105 and 105. Each point has an associated integer "reach radius" Ri (0 < Ri < 105).

Build a directed graph (represented by adjacency lists) in which these points are the vertices and there is an edge from A to B if and only if point B falls in the reach of point A (i.e. euclidean_distance(A,B) $\le$ RA).

I am thinking of dividing the plane into 4 equal regions, and solving the same problem for the regions, but don't know how to combine the partial solutions...

Thanks in advance for any ideas!


texts: Interview Question with Arrays and Consecutive Subintervals

texts:
I recently came across this question and honestly am pretty unsure of how to solve it, or even begin to develop an algorithm to properly solve it..

The question is:

  "An array of $n$ integers is correctly positioned with respect to an
  integer $k$ if for any $k$ consecutive indices in the array, there
  does not exist values at two indices, $x$ and $y$ such that $x \geq 2$
  * $y$ (where $x$ and $y$ are values at 2 indices of the array in a subarray of size $k$). What is an $O(n \log k)$ algorithm to determine
  if an array is correctly positioned?"

For example: $[5, 6, 7, 4, 5, 9]$ is not correctly positioned if $k = 4$ since in in the interval $[7, 4, 5, 9]$ we have that $9 \geq 4 * 2$.

My thought is to check all potential subintervals like $[0..k]$, $[1..k+1]$, $[2,..k+2]$ using a min-heap but I really can't think that would satisfy the time constraint since it's resulting in building far too many heaps.

Does anyone know how to approach this problem, or have a solution for it?

Having trouble figuring out how to keep track of this sliding window using heaps, and thinking maybe I have to use a min-heap and max-heap? And compare the max to the min for every subinterval using insertions and deletions?


texts: Relation between logspace-uniform circuits and P-uniform circuits

texts:
In the book "Computational complexity" of Barak and Arora, on page 112, they state that:

  Theorem 6.15: A language has logspace-uniform circuits of polynomial size iff it is in P.

The proof of this one is left as an exercise to the reader.  I think both directions are trivial:

=> seems trivial, as a logspace TM that generates a circuit also runs in polynomial time, and hence is a P-uniform circuit, which is part of P.

<= seems trivial, as a language that has a polynomial-time TM can be transformed into a circuit with Cook-Levin's theorem in logspace.

However, what I don't get is why the theorem 6.15 explicitly states that the circuits must be of "polynomial size".  How can there exist a logspace-uniform circuit that isn't polynomial in size?  The logspace computable function itself cannot exceed a polynomial bound, how can it produce a circuit of superpolynomial size?

Also, this theorem would imply that logspace-uniform circuits comprise the same languages as P-uniform circuits, which seems very unintuitive to me.
I can't find any information on the relation between logspace-uniform and P-space uniform circuits on the web, so my assumption that they are equal is probably false, but I fail to see see why.


texts: Find the Pumping Length for Language L of (2+3k) a's or (10+12k) b's

texts:
The following question on the theory of computation is GATE 2019 CS question 24:

For $Σ = \{a, b\}$, let us consider the regular language: $$L = \{x \mid
 x = a^{2+3k} \text{ or } x = b^{10+12k}, k \geq 0\}$$  Which one of the
following can be a pumping length (the constant guaranteed by the
pumping lemma) for $L$?
(A) 3$\quad$(B) 5$\quad$(C) 9$\quad$(D) 24

My Attempt
I tired to solve like this. I divide the minimum string possible into $x(y^i)z$ that is $a^2$ so getting i value $2$ but option not available.
Then I take second minimum $a^5$ i.e., taking $x=\epsilon$ and $y=a^5$ and $z=\epsilon$.
I am getting $i=5$. So is it correct answer??


texts: Are the regular languages closed against injecting single letters?

texts:
Let $L$ an arbitrary regular language and

$\qquad L_2 = \{uav : uv \in L\}$.

Am I correct to say that this language is not regular by saying:

$L$ has an even number of $a$'s. So $u$ and $v$ have an even number of $a$'s. However, $uav$ will have an odd number of $a$'s so $L_2$ is not regular?


texts: What is the intuition that 2-phase locking achieves serializability (also known as before-or-after atomicity)?

texts:
I am learning 2-phase locking and its unclear to me how it achieves/guarantees before-or-after atomicity (i.e. serilizability).

I went to the following notes

http://ocw.mit.edu/resources/res-6-004-principles-of-computer-system-design-an-introduction-spring-2009/online-textbook/atomicity_open_5_0.pdf

on page 9-73 it argues informally:

"Informally, once a transaction has acquired a lock on a data
object, the value of that object is the same as it will be when the transaction reaches its
lock point, so reading that value now must yield the same result as waiting till then to
read it. Furthermore, releasing a lock on an object that it hasn’t modified must be harm
less if this transaction will never look at the object again, even to abort. A formal
argument that two-phase locking leads to correct before-or-after atomicity can be found
in most advanced texts on concurrency control and transactions"

But I didn't really understand the argument and it seems that a formal proof is not trivial or maybe too complicated. So I was seeking an alternate intuitive argument to its correctness. I don't really understand why that is the reason but if someone else has a better way of explaining it or a different perspective, it would be greatly appreciated!


texts: How many operations does this algorithm require?

texts:
I have the following algorithm

x = 0
S = {}
k = 1
while x + a[k] < n do
    S = S + {k}
    x = x + a[k]
    k = k + 1
end

where a[k] is a positive integer.

What is the time complexity in terms of number of iterations of this algorithm?

I tried to compute the number of operations. As I understand, I should find how many steps are required in order for $x$ to be equal to $n$ by adding $a_k$ in each step. If $a_k=1$ for all $k$, then I need $n$ steps. If $a_k=2$ for all $k$, then I need $n/2$ steps. In general, if $a_k=a$ for all $k$, then I need $n/a$ steps. But, if $a_k$ are arbitrary, how many steps are required? I guess it is $n/\min a_k$.


texts: The difference between a sequence and a set

texts:
I am new to discrete mathematics and the theory of computation I am trying to learn and understand the terminology.

I am having a difficult time understanding the difference between a set and a sequence. I understand that unlike a set, in a sequence order and repetition does matter and sequences contain objects rather than elements or members. However, I don't see how sequences can be logically applied to the real world.

Can someone please give a clear and simple example of when a sequence would be used as opposed to a set and explain how is a sequence is different that a set?

I appreciate any clarification.


texts: Does the circuit value problem require only log space in alternating Turing machines

texts:
Why does the circuit value problem run in log space on an alternating Turing machine? It is claimed to be so in my university's lecture notes. Also, it is claimed that monotone circuit value problem has the same space complexity on an alternating Turing machine.

I think it requires at least linear space because it needs to store the current assignment that we are checking and also some bits for the working and storing outputs of sub circuits.


texts: Why is the quantity of sentences not finite?

texts:
I'm currently studying formal languages. My lecture states that, while the words of a language are finite, the sentences build with the underlying grammar are not. But I don't get why this should be generally true. I can imagine grammar which leaves me with a finite amount of sentences.

I agree that one could create a language with infinite amount of sentences but I can't see why it should be generally the case.


texts: Are process-safe mutexes shared between OSes?

texts:
I understand you can use process wide mutexes, but does this still apply if you have an additional virtualized operating system provisioned?

For example, take two OSes: O1 and O2 where O2 is a virtualized OS provisioned on O1. Now take some code C that uses a process-wide mutex. Run C on O1 and O2. Assuming they have access to the same resource through some file sharing mechanism (e.g. guest additions.) Does the mutex still work?


texts: Prove that x and y in extended Euclid's algorithm won't overflow an Integer (If a,b <= 1e8, ax+by=gcd(a,b))

texts:
We are given a and b <= 1e8.

The extended Euclid's algorithm always finds a solution for ax+by=gcd(a,b) (assuming it exists) which can always be stored in an Int.

How to prove the x and y won't overflow an Int?

code: https://cp-algorithms.com/algebra/extended-euclid-algorithm.html


texts:
Let $M$ be an arbitrary Turing machine and $w \in \{0, 1\}^{*}$ be a binary string.

The language $\text{HALT} = \{\langle M, w \rangle : M ~\text{halts on input} ~w \}$ is undecidable by the famous diagonalization proof.

But what happens when we either fix the Turing machine $M$ or the input $w$?

Formally, for a fixed $M_{0}$ in the first case and a fixed $w_{0}$ in the second case, are these two languages still undecidable? Is there any dependence on the nature of $M_{0}$ or $w_{0}$?

$\text{HALT}_{M_{0}} = \{w : M_{0} ~\text{halts on input} ~w
   \}$
$\text{HALT}_{w_{0}} = \{\langle M \rangle : M ~\text{halts on input $w_{0}$}
   \}$

For the first language, I found a proof online (Proposition 17.2), but it seems specific to the nature of $M_{0}$ which is probably intuitive. I am more intrigued by the second case.


texts: Converting Moore to Mealy When first Node has Output

texts:
This is a homework question, which I am able to do, except my teacher failed to mention what to do when the very first node has a 1 output. I've looked through online examples, and I'm sure this has a very simple answer, but I cannot figure out what the convention would be.
On the left, we have a Moore Machine. It's first node outputs 1. Ok, no problem.
But when I convert this to a Mealy, the only time q1 outputs 1, is when being traversed from q2.

But if it's the first node, it should be outputting when the whole thing begins (on lambda) AND when being traversed from q2.
I had two theories, one-- I make a new beginning node, or, I actually put λ/1 on the entry arrow/line (which I have not seen done in any example). But I'd rather not guess my way through this otherwise simple operation.


texts: When proving NP-completeness do I only need one instance of a problem or all of them?

texts:
I saw a proof of reduction of hamiltonian path to spanning tree with inner vertices having degree of k.

The person, who proved it, constructed a spanning tree from a hamiltonian path, basically u-x1-...-xi-...-xn-v, and where xi are inner vertices and then appended k-2 leaves to each one of those vertices.

I understand that that is indeed a correct spanning tree for the problem, and the u-v path does form a hamiltonian path.

But my question is, is this reduced algorithm supposed to find all such spanning trees or not?

I can create a spanning tree with inner vertices of degree k, in which there's no such hamiltonian path that spans all inner vertices, for example, and clearly this method won't work. So this makes the shown construction isolated, meaning it doesn't describe a general case of a spanning tree.

So is it enough to to just construct a certain instance of the problem B we want to prove to be NP-complete, or do we need to reduce a known problem A to the general case of B?

I am confused about this, because, for example, we can prove INDEPENDENT-SET to be NP-complete by reducing CLIQUE to it, and it involves just taking the inverse of the graph and then finding a clique in it. This case does reduce problem CLIQUE to the general case of INDEPENDENT-SET.

P.S. I am very new to NP-completeness.


texts: How to select a good window size in the Running Gaussian Average method for Selective Background Updating?

texts:
I have been studying the Selective Background Updating in Running Gaussian Average Method, as discussed in the Wikipedia (the Variant method). The details of the algorithm, as I understand, is as follows:

For each pixel, at initialization $(t=0)$, set $\mu_0=I_0$ (the initial intensity of the pixel), and $\sigma^2_t=c$ (here I use $c = 10$).

At each turn $t$, calculate the following in order for each pixel:

$\mu_t=\rho I_t + (1-\rho) \mu_{t-1}$

$\sigma^2_t=(I_t - \mu_t)^2 \rho + (1-\rho) \sigma^2_{t-1}$

$q_t = |I_t - \mu_t| / \sigma_t $

If $q_t \gt k \rightarrow $ pixel is foreground, and we don't update the mean and variance

(i.e. $\mu_t=\mu_{t-1}$ and $\sigma^2_t=\sigma^2_{t-1}$),

else pixel is background.

I have written a small C program to test the effect of different $\rho$ values. The input data is a 1-D array of nearly 2000 elements, with values ranging from 132 to 147, with a generally gradually increasing trend (but sometimes have an occasion drop of 1 or 2), to represent a slightly increasing light intensity on the background. Three different values of $\rho$: 0.0001, 0.001 and 0.01 are used, and for each of the three cases, two graphs are then plotted: Variance $\sigma^2_t$ against $t$ (above), and $q_t$ against $t$ (below). The plots look like this (click link to see the enlarge version):

To my surprise, when $\rho = 0.01$ (a short history), the variance becomes so small $(<0.2)$ near the end, that even when the next data increases or decreases by $1$, the value $|I_t - \mu_t| / \sigma_t$ becomes larger than $2.5$ and is hence considered a foreground. But when $\rho = 0.0001$ (a long history), the variance does not change much from the initial value $(10)$ at all. However, the best result in my case is when $\rho = 0.001$, where the variance becomes quite large $(\simeq25)$ at the end, making the value $|I_t - \mu_t| / \sigma_t$ always smaller than $2.5$, and is considered background correctly.

So it seems to me that while getting the correct $\rho$ is important, it is also a bit by luck. Would you tell me what is the criteria of getting a good $\rho$, or have I made any mistake in my program code?


texts:
I am trying to solve a problem and I am really struggling, I would appreciate any help.
Given a graph $G$ and an integer $k$ , recognize whether $G$ contains dominating set $X$ with no more than $k$ vertices.
And that is by finding a propositional formula $\phi_{G,k}$ that is only satisfiable if and only if there exists a dominating set with no more than k vertices, so basically reducing it to SAT-Problem.
What I have so far is this boolean formula:
$\phi=\bigwedge\limits_{i\in V}   \bigvee\limits_{j\in V:(i,j)\in E} x_i \vee x_j$
So basically defining a variable $x_i$ that is set to true when when vertix $v_i$ is in the dominating Set $X$, so all the formula says that it is satisfiable when for each node in $G$ it is true that either the vertex itself is in $X$ or one of the adjacent vertices is.
Which is basically a Weighted Satisfiability Problem so its satisfiable with at most $k$ variables set to true.
My issue is now that I couldn't come up with a boolean formula $\phi_{G,k}$ that not only uses Graph $G$ as input but also integer $k$.
So my question is now how can I modify this formula so it features $k$ , or possibly come up with a new one if it cannot be modified?


texts: Reduction of the diagonalization language to the universal language

texts:
I'm going through Jeffrey D. Ullman's Introduction to Automata Theory, Languages, and Computations. The author reduces an instance of the membership problem in $L_d$ (diagonalization language) to a membership problem in $L_u$. Those are defined as follow:

$L_d = \{\langle M\rangle \mid \langle M\rangle \notin L(M)\}$
$L_u = \{\langle M, u\rangle \mid u \in L(M)\}$

We start off with assuming $L_u$ is recursive, reduce the problem in $L_d$ to a problem in $L_u$, and solve $L_d$ using the assumption that $L_u$ is recursive, now since $L_d$ is not even recursively enumerable, our assumption that $L_u$ is recursive turns out to be wrong, and since $L_u$ has a TM which accepts it, we conclude $L_u$ is a RE but not recursive language. A few pages later, the books says:
Theorem 9.7: If there is a reduction from $P_1$ to $P_2$ then
a) If $P_1$ is undecidable then so is $P_2$
b) If $P_1$ is non  RE then so is $P_2$
I'm confused about the part b) of this theorem, it says reducing a non RE problem to another problem gives you a non RE problem, but having reduced an instance of $L_d$ to an instance of $L_u$, we have reduced a non RE problem to a RE but not recursive problem.


texts: Is there an algorithm that can solve chess within the span of a human lifetime?

texts:
According to Shannon (in his 1949 paper) the game of chess has too much complexity to be solved by a brute-force search of the game tree:

  A machine... would require over $10^{90}$ years to calculate the first move!

But his paper ends with a section entitled "Another Type of Strategy" and provides vague guidance on other options to solve chess.

Can it be proven whether chess can or cannot be solved with some algorithm (other than brute force) within some defined amount of time (for example, 100 years)?


texts: If an algorithm has running time of $\Theta(n^2)$, is it possible to have a best-case running time of $\Omega(n)$? Or is the fastest running time only $c n^2$ for some constant factor $c$?


texts: Efficient update to rational flow network?

texts: Once we've computed the max flow in a flow network with integral capacities, we can change one of its edges' capacity by a unit and recompute a maxflow in linear time using BFS. Is there something similar for rational networks where we might change a capacity by an arbitrary amount, or delete edges (which amounts to setting their capacities to 0)?


texts: Can we define an ε deterministic finite automaton?

texts: I am studying automata and I was wandering if there is a definition of ε-DFA automaton. Is it feasible to define it?


texts: Counting solutions of a particular type in HORN SAT

texts:
I am interested in counting the number of solutions of a particular type (say #) in HORN SAT. I have 2 questions concerning the same.

Suppose we have a HORN SAT -: $(x_1) \land (x_2 \implies x_1)$, then the solutions are $(1, 0)$ and $(1,1)$. For solutions of type #, I would like to eliminate $(1,1)$ as after negating $x_2$ we will still have a valid solution. In some sense $(1,1)$ is not a minimal solution. Do solutions of type # have a formal name? It seems natural that SAT solvers must strive to obtain solutions of type # and use those to generate other solutions.
Since the problem of HORN satisfiability is easy, are there efficient algorithms for counting HORN sat solutions? If so, could someone please point me to a good reference.


texts: I find binary confusing. I have watched minecraft redstone videos on binary adders, real binary adders, diagrams, etc and yet I have not learned much at all. How does electrons flowing through wires made of gold "add/subtract" to make numbers through some logic gates?!


texts: Concrete example of Vertex Cover to Subset Sum reduction

texts: In Computational Intractability, we often come across a need to reduce Vertex Cover (VC) problem to a Subset Sum problem, mostly to prove Subset Sum is NP-Complete. I also see a reduction in the line of - A graph G has VC of size k if and only if there is a subset S that sums exactly to t. However, not able to find out (understand) exactly what is this t. I think providing a concrete example will help many like me. Request any one to provide a concrete graph with |VC| 3 or something manageable, and then show exact value of t i.e. what would be the exact instance of subset sum problem. Finally, explaining/clearly mentioning elements of S would be of great help.


texts: TM to detect repeats of any other TM and input value

texts:
I read a previous question,
Is a secondary TM sufficient to detect all loops?, which asks if there is a TM1 that takes the description and input of any other TM2 to detect if TM2 will loop for the input.

One answer was to run two copies of TM2, the second at 1/2 the speed.If the second machine ever reaches the same configuration as the first, a loop was detected. Seems to me that the process requires a third entity to do the comparison at every step. Since neither copy output their complete configuration, it is not obvious this third entity and the complete system of all three entity can be a TM.
Another easy way is for a second TM2 to keep a list of all configuration of TM1 and check to if there any repeats. This can surely work. But again, what is not obvious is if this complete system of the checking process on TM2, the running of TM1 and outputting TM1's complete state configurations to TM2 can be realized as a TM. TM1 can't output its own states to TM2, so TM2 somehow has to grab these from TM1, not just its output but TM1's complete state information or there has to be a third entity that does the communication.

My question: Can this process be implemented as a Turing machine?


texts: What do these arrows in design pattern diagrams mean?

texts:
I am learning about software design patterns by reading Wikipedia pages about them. A lot of the patterns such as the bridge pattern have diagrams with boxes and different kinds of arrows:

Source: Wikipedia

Do these diagrams stem from a standard? Why do some arrows have different ending markings? Also, why are some of them dotted?


texts: Clustered Regions by Each Neuron in Self Organizing Map (SOM)

texts:
I was given a question about SOM.

There is a SOM which have 4x4 neurons and each neuron's x1 and x2 values (coordinates) given. Also neighborhood function and weight update rule given. How can i find and show the regions which are clustered by each neuron?

Thanks for answers.

Regards...


texts: Minimize $f(r,X)$ over all sets $X$ using Dynamic Programming

texts:
If a set of numbers $a_1, a_2, \cdots, a_n$ $($such that each $a_i \in \mathbb{N} \cup \{0\})$ and an $r \in \mathbb{N}$ are given, find set $X = \{x_0, x_1, \cdots, x_r \ | \ x_0 = 0 < x_1 < \cdots < x_r = n\}$ such that $f(r,X) := \displaystyle\max_{j=0}^{r-1} \sum_{i = x_j}^{x_{j+1}-1} a_i$ is minimized over all possible $X$.

I can think of a brute force approach, that is, generate $\Theta ({{n-1} \choose {r-1}})$ sets $X$ and calculate the $\max$ for each $X$, each of which takes as many as $r$ steps. This is a very inefficient approach. How do I make it better? I feel like there is a way using DP. (Please feel free to edit the title if this is not DP).
This seems like a possible solution. What if we pre-compute $\displaystyle\Sigma_{i=j}^{j+k} {a_i}$ $(k \geq 0)$ for all $1 \leq j \leq n$ first and then create a DP with function $$\text{best}(p,q) = \text{best way of having } q \text{ intervals such that we end at } [p-x,p] \text{ for some } x \geq 0$$ Our goal is to find $\text{best}(n,r)$ and backtrack to find the intervals.
$\text{best}(p,q) = \min \{ \text{best}(p,q-1), \ \max(\text{best}(p-1,q-1), \text{dist}(p-1,p)), \ \max(\text{best}(p-2,q-1), \text{dist}(p-2,p)), \dots) \}$
where $\text{dist}(x,y)$ = $\displaystyle\Sigma_{i=x}^{y} a_i$ which is pre-computed. This probably works but the backtracking seems difficult and time-hungry.
I tried greedy and I could generate counter-examples right away. Was not very helpful.


texts: composite number Pumping Lemma for L = {$0^p$∣$p$ is a composite number}

texts:
Consider the language $L = \{0^p \mid p \text{ is a composite number}\}$.

I know that this is not a regular language. I have thought that to prove this language is not regular take the complement (prime numbers) which must be regular, but its complement has prime numbers and 0 and 1 occurrences of 0's.

Could anybody give me a hint to prove without taking complement?


texts: Find any of the 3 largest among $n$ elements

texts:
I have two questions. Both are about finding any of the 3 largest among $n$ elements.

How to show that $n-3$ comparisons suffice to find any of the $3$ largest among $n$ given numbers $(n \geq 4)$?
How to show that $n-3$ comparisons are necessary to find any of the $3$ largest among $n$ given numbers $(n \geq 6)$?

My Idea: I have tried to solve 1. using a heap but could not derive any such bound.

The place where I found this question gave one hint which said to analyze the number of connected components in a comparison graph.

I shall appreciate if anyone can throw some light on a comparison graph.


texts: Dealing with test condition '=' for a while loop when determining a bound function/loop variant

texts:
The following is the definition of what a bound function for a while loop must satisfy:

The bound function is an integer-valued, total function of some of the inputs, variables and global data that are defined when the loop is reached.
When the loop body is executed, the value of this function is decreased by at least one before the loop’s test is checked again, if at all.
If the value of this function is $≤ 0$ and the loop’s test is checked then the test fails (ending this execution of the loop).

I am given a while loop as such,

while (j ≤ n) {.....; j = j + 1}

where j is not touched by the rest of the body of the loop.

I am trying to find a bound function for this simple while loop. Here is what I tried:

$n-j$ is not a bound function since point (3) fails.
$n-j-1$ is not a bound function since the loop would not run initially if $n=j$ (since $n-j-1=-1 \ge f(j,n)$), and I am not sure if the latter is a total function due to the presence of $-1$.

How do I deal with the '=' in the '≤' to determine a bound function that satisfies the while loop?


texts: How to show that language L is NOT context-free?

texts:
True or false: To show that a language L is not context-free, one can alternatively show that the union between L and a known context-free language is not context-free.
I know that you can prove closure under context-free languages using union, but does the above work, too? Any help you can provide would be greatly appreciated!


texts: LR(0) parsing: how can I know sets of items corresponding to states?

texts:
I'm studying LR(0) parser. But I don't understand how sets of items corresponding to states can be calculated. I think The author would miss some information readers must know. Given the following LR(0) automaton, How the set of items corresponding to I1, I2, I3, ... , and I11 can be calculated?

In addition, is closure of item sets related to with calculating them? If so, what exactly every item in I1, I2, ... , and I11 is?


texts: Context free grammar for $L = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b-1\}$

texts:
I'm trying to find a grammar for $L = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b-1\}$, which is proving to be tricky.
I know that $L_2 = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b\}$ has the following one, so I have been trying to modify it so that I "force" to have one more $b$, but I don't see how to do this. The obvious choice would be to replace $\epsilon$ with $b$, but that would potentially get two more $b$'s. Is there a trick for this one?
$$\begin{align}
  S &\to \epsilon \\
  S &\to aSbS \\
  S &\to bSaS \enspace.
\end{align}$$


texts: Detect cycles of odd total weight in a graph with {0,1}-weighted edges

texts:
Given an edge-weighted digraph $G = (V, E \subseteq V^2, w \in E \to \{0, 1\})$, is there an algorithm that returns TRUE if there is a cycle in this graph whose total weight is odd and FALSE otherwise, which runs faster than $O((|V| + |E|)(c + 1))$ (where $c$ is the number of simple cycles in the graph, which is of course $\Omega(2^{|V|})$)?

As the question implies, I already came up with an algorithm that runs in $O((|V| + |E|)(c + 1))$ time. This algorithm involves first running Johnson's simple cycle enumeration algorithm, which gives us all the simple cycles in the graph. Since even + even = even, and all cycles are made by adding together simple cycles, the graph contains a cycle of odd length iff it contains a simple cycle of odd length. Thus, we just compute the parity of the simple cycles and return TRUE if any of them are odd, and FALSE otherwise.

Can anyone come up with a more efficient approach? Ideally, one that is not just "replace Johnson's algorithm with another simple cycle enumeration algorithm that has slightly better asymptotics", since the graphs I'm dealing with really aren't that large, and constant factors may well dominate as a result.


texts: optimal flow for index multiple source and destination in directed graph

texts:
I am facing the similar problem to max flow in multiple source-destination directed graph (which has a familiar solution of connecting all the sources to one source and the same for the destination, and solving it with some algorithms like Ford-Fulkerson), but the difference in my problem is that :

all edges has capacity of 1 (the flow is discrete so once an edge is used - it can't be used again)
each source need to flow to a specific destination (e.g. $v_1$ needs to flow to sink $u_1$ - other sinks can't consume $v_1$ flow).

I need to find the max sources that can reach to their destination on a given graph. Is there a solution for this or I have to compute all the possiblities ?


texts: Regular expressions with backreferences over unary alphabet

texts:
Setting:

regular expressions with backreferences
unary language (1-symbol alphabet)

Is the following problem decidable in this setting:

Given a regular expression with backreferences, does it define a regular language?

For example, (aa+)\1 defines a regular language, while (aa+)\1+ doesn't. Can we decide which one is the case?

For concreteness, "regular expressions with backreferences" here refer to e.g. the following subset of the usual Perl-compatible regular expressions:

a matches character a (the only character in the alphabet)
X* matches 0 or more occurrences of X
X|Y matches X or Y
parentheses can be used for grouping and capturing
\1. \2, etc. match the same string as the 1st, 2nd, etc. pair of parentheses

We can also use the normal shorthands e.g. X+ = XX*.


texts: Most efficient known priority queue for inserts

texts:
In terms of asymptotic space and time complexity, what is the most efficient priority-queue?
Specifically I am looking for priority queues which minimize the complexity of inserts, it's ok if deletes are a little slower.

 If you're looking for a survey of priority-queues which minimises complexity of deletes over inserts, see: Does there exist a priority queue with $O(1)$ extracts?.


texts: Structural parametrization for weighted vertex cover

texts:
Let $G$ be a graph which is a tree with $\ell$ added edges. I wish to show that VWVC ((Vertex-)Weighted Vertex cover) is FPT with respect to $\ell$. In particular, I'd like an algorithm running in $O(2^\ell n^c)$ time, where $n$ is the number of vertices and $c$ is a constant.
I tried to approach this by finding a tree and find VWVC there with polynomial time and then brute forcing the rest $\ell$ edges in $O(2^{\ell})$, unfortunately i found a counterexample very quickly. Also I attempted to somehow assign all edges a weight (maybe for $uv\in E$ set $w(uv)=w(u)+w(v)$) and compute the minimal spanning tree and do something with that but I couldn't show that this would yield optimal vertex cover either. I'm kinda lost. Any hints appreciated.


texts:
Lets have an arbitrary complexity class $C$.

Does $C$-complete = co-$C$-complete imply that $C$ = co-$C$?

I think that the answer is yes, but I am not sure whether my reasoning is correct. I tried to prove it like this:

Let $L$ be a $C$-complete language, so all problems in $C$ are polynomially many-to-one reducible to it. If $L \in C$ and $\bar{L} \in C$, then $C-complete = co-C-complete$ (because all complements of problems in co-$C$ are reducible to both $L$ and $\bar{L}$). That implies that $C = co-C$ so $C$ is closed under complement.

Is this a correct approach?


texts:
In pseudo direct addressing mode (For the MIPS architecture) the 26 bit of the jump instruction are joined to the upper 4 bits of the PC .

how could this help in jumping to relative positions suppose I want to jump backward instead of forward ( i.e. if i want to jump to the beginning of a loop after executing it's body ),
What I get is this will limit the jump to be 2^28 from the following instruction but Is this applicable backward too ?
I am really confused by this so excuse me for such a silly question...


texts: Finding invariant when detecting a cycle

texts:
Let consider a connected graph $G = (V, E)$ which is not oriented. One way to detect a cycle in such a graph is :

Create an array : seen of size $\mid V \mid$ with seen[i] = false for all $i$

Perform a DFS (or BFS) starting at the node $0$.

When we see a node $i$ : we have two cases : if seen[i] = false then seen[i] = true else we found a cycle.

One idea to prove the correction of this algorithm is saying the following : if the algorithm return true it means there two  nodes $x$ and $y$ such that when we looked at $y$ we have : seen[y] = false and seen[x] = true thus there is a cycle namely the cycle which begin at $x$ and use the only path that connect $x$ and $y$ in the DFS tree and then use the edge $(y,x)$.
The problem is that this is not really rigourous and I am really lokking for an invariant that we help me do the correction of this algorithm rigourously.
So is there any invariant I can use here ?
Thank you very much  !


texts: Minimum difference between two subsets of an array of integers

texts:
The Problem

Suppose we have an array A[1...n] of integers, with values ranging from 0 to K (so 0<=A[i]<=K for each i). We need to describe an algorithm to find an (X,Y) partition from the set {1,2,...,n} such that |Sx-Sy| is minimum, where Sx and Sy are the sums of the elements in X and Y. i.e., if A=[1,3,1,1], then X={1,3,4} and Y={2} and the solution is optimal with Sx=3, Sy=3, |Sx-Sy|=0.

My Solution (In pseudocode)

For i=0 to n
    if A[i]==K //If this element is the highest element in the array, put it in Sy
        Sy.add(A[i])
Else if A[i]=/=0 //We don't care about zeroes, the rest goes in Sx
    Sx.add(A[i])
min = |Sx-Sy| //Calculate our min as it is
DO
    go=false
    //Move the smallest element from the biggest group to the other one
    if Sx>Sy
        SyTemp = Sy + min(Sx)
        SxTemp = Sx - min(Sx)
    else if Sy>Sx
        SxTemp = Sx + min(Sy)
        SyTemp = Sy - min(Sy)
    //if this improves on our min, save it and check for another iteration
    if |SxTemp-SyTemp|<min
        Sx=SxTemp
        Sy=SyTemp
        min = |Sx-Sy|
        go=true
    else
        Return Sx,Sy //if the new sets are worse than the ones before, return the old ones
While(go)

My question

Apparently, this problem is NP complete (At least that is what my professor told me), and my question comes from the way he scored my solution. I got 3 points out of 9 because a dynamic programming solution is what was requested - while this is a greedy approach - and my solution has edge cases in which it won't work.

the example he gave me to prove that these edge cases exist was [1,2,5,5] and he said that in this case the algorithm would return {1,2,5},{5} instead of {1,5},{2,5}. Now, to me it seems like my solution would actually return what he wants, and I can't really think of an example this algorithm couldn't deal with, so I'm here to ask the community if you see any errors in my solution, if you think my professor is right in saying that his example wouldn't be solved optimally (or that there are edge cases in which this approach won't work), and if you think this will perform better than O(K(n^2)), where K is the sum of all values of the array (which apparently is the time complexity of his DP solution).


texts: Why some Huffman codes have efficiency better than others?

texts:
Consider the alphabet $\mathcal{A}=\{a_0,a_1,a_2,a_3\}$ with the the following corresponding probabilities:

$\, p_{A,1}=\{0.5,0.3,0.15,0.05\}$
$\, p_{A,2}=\{0.5,0.25,0.125,0.125\}$

The entropy for the first case is $H(A,1)= 1.65$, and for the second is $H(A,2)=1.75$. The Huffman code for both can be $\{0, 10, 110, 111 \}$ or $\{1, 01, 001, 000 \}$. The average lengths are $\bar{L_{A,1}}=1.7$ and $\bar{L_{A,2}}=1.75$. The efficiencies are $97.14 \%$ and $100 \%$ for case $1$ and $2$ respectively. Why is that? The only reasonable explanation is the probabilities themselves. In the second case, it is somehow equally divided. Can anyone explain?


texts: What is an array that can be iterated circularly an infinite amount of times called?

texts: I have a feeling that the answer is either a "circular linked list" or a finite state machine, but the answer is probably a circular linked list.


texts: What is the time complexity of this algorithm?

texts:
In my class my teacher calculated the time complexity for this algorithm, relative to the number of sum operations executed:

She represented the cost of the algorithm  by the following sum:

$\sum\limits_{i=1}^n \sum\limits_{j=1}^i\sum\limits_{k=1}^j 3 = \frac{n^3}{2} + \frac{3n^2}{2} + n $

The step by step used to solve the sum bellow:

n = 10
count=0
for i in range (0, n):
    for j in range (0, i):
        for k in range (0, j):
            count+=3

print count

Then, I wrote a algorithm in python to verify the solution, but it not produce the expected output, for example, for n = 10 we expected 660 operations, but it print 360.

Change the index to start with 1 like in the bellow didn't worked either, in fact it got more distance from the expected (252).

n = 10
count=0
for i in range (1, n):
    for j in range (1, i):
        for k in range (1, j):
            count+=3

print count


texts: How to find specificity of a regex match?

texts:
I'm thinking about a routing system. Imagine I have the two following regexes

pathpart1/pathpart2 => specific match that routes to controller1
.* => catch-all that routes to controller2

And I let them match on a URL, e.g. 'pathpart1/pathpart2'.

They both match, but I would want to give prevalence to the most specific regex, i.e. the regex where the cardinality of all possible matches of that regex is the lowest.

  Is there a good way to calculate that the first regex has a low cardinality on its match-set (so I want to to go with that match) and the second has a very high cardinality on its match-set (i.e. it is completely not specific, so a match is basically a catch all last resort)...?

I do not know upfront which routes are registered with the router, so I can't loop over them in order of cardinality by hand (i.e. low cardinality first, and the catch-all last if all others don't match).


texts:
I know about the concept of the "model" of a logical proposition in the context of mathematical logic: It is a mathematical structure in which that proposition is true.

However, it's not clear to me what a "model" of lambda calculus is. Wikipedia states the following:

  To formulate such a denotational semantics, one might first try to construct a model for the lambda calculus, in which a genuine (total) function is associated with each lambda term. Such a model would formalize a link between the lambda calculus as a purely syntactic system and the lambda calculus as a notational system for manipulating concrete mathematical functions. The combinator calculus is such a model.

What confuses me about this statement is that it seems to me that the combinator calculus (i.e. combinatory logic) is on the same footing as lambda calculus, in the sense of being a model of computation. It's unclear to me why lambda calculus would be considered a "syntactic" entity while the combinator calculus is a "semantic" entity. I am generally confused by this article.

So what exactly does it mean for something to be a "model of lambda calculus"?


texts: How to prove that a language is not regular?

texts:
We learned about the class of regular languages $\mathrm{REG}$. It is characterised by any one concept among regular expressions, finite automata and left-linear grammars, so it is easy to show that a given language is regular.

How do I show the opposite, though? My TA has been adamant that in order to do so, we would have to show for all regular expressions (or for all finite automata, or for all left-linear grammars) that they can not describe the language at hand. This seems like a big task!

I have read about some pumping lemma but it looks really complicated.

This is intended to be a reference question collecting usual proof methods and application examples. See here for the same question on context-free languages.


texts: What can a quantum query to a function do?

texts:
The $n$-qubit Hadamard gate acts as,
$$H (\otimes^n \vert 0 \rangle ) = \otimes ^n ( H | 0 \rangle ) = \otimes ^n ( \frac { |0\rangle + |1\rangle }{\sqrt{2} } ) = \frac{1}{\sqrt{2^n} } \sum_{x \in \{ 0,1\}^n} |x\rangle $$
So it is capable of producing the uniform superposition state over an exponential number of states in what is to be seen as a ``single" step.

Now if one is given a boolean function $f$ then how is it that the above uniform superposition state can be converted into   $\frac{1}{\sqrt{2^n} } \sum_{x \in \{ 0,1\}^n} f(x) |x\rangle$ by a ``single query to $f$ in superposition" ?
Can someone give a mathematical or a gate picture of this ''single query to $f$ in superposition" ? What is the unitary operator which corresponds to this ''single query to $f$ in superposition"  ?

A part of this confusion arises because I am under the impression that if kets are indexed by elements of $\{0,1\}^n$ then a ''single" quantum query to a Boolean valued function $f$ is ``by definition" a transformation of the form  $\vert x \rangle \vert y \rangle \rightarrow \vert x \rangle \vert y \oplus f(x) \rangle$ or which is often thought of as the operator $O_f(x)$ acting as $O_f(x) \vert y \rangle =  \vert y \oplus f(x) \rangle$
But I can't see the transformation in the question as a any combination of $O_f(x)$ kind of operators!


texts: How to prove that $\lfloor{\sqrt{n}\rfloor} = \Theta(\sqrt{n})$?

texts: It is quite direct to prove that $\lfloor{\sqrt{n}\rfloor} = O(\sqrt{n})$. But how can I prove that $\lfloor{\sqrt{n}\rfloor} = \Omega(\sqrt{n})$?


texts: Trouble understanding how to pick constants to prove big theta

texts:
So I'm reading Introductions to Algorithms and sometimes I wish it would be a little bit more friendly with how it explains topics. One of these topics is proving big-theta.

I understand that the definition of $\Theta$ is as follows:

  $\Theta(g(n)) = f(n)$ if there exists positive constants $c_1$, $c_2$, and $n_0$ such that $0 \le c_1 g(n) \le f(n) \le c_2 g(n)$ for all $n \ge n_0$.

In other words, for $f(n)$ and $g(n)$, $f(n)$ can be bounded by $c_2 g(n)$ from above and bounded below by $c_1 g(n)$.

So the example in the book goes:

  Show that $\frac{1}{2} n^2 - 3 n = \Theta(n^2)$.

From the definition of big theta:

$$ c_1 n^2 \le \frac{1}{2} n^2 - 3 n \le c_2 n^2$$

CLRS begins by dividing by the largest order term of $n$ which is $n^2$ to get

$$ c_1 \le \frac{1}{2} - \frac{3}{n} \le c_2 $$

From here we split the problem into two parts, the right-hand inequality and the left-hand inequality.

On the right hand side: CLRS chooses $c_2 \ge \frac{1}{2}$ because for $n \gt 1$, $\frac{1}{2} - \frac{3}{n}$ can never be less than $\frac{1}{2}$ since $\frac{3}{n}$ goes to $0$ as $n$ goes to infinity. (I'm assuming they choose $n \gt 1$ here because if $n=0$ then we would be dividing by $0$.)

Now this is where I start to get lost.

On the left hand side: CLRS chooses  $c_1 = \frac{1}{14}$ (not sure why) and $n \ge 7$. I'm not sure what the significance of these choices is. At $n \le 6$, $\frac{1}{2}-\frac{3}{n}$ becomes negative. But why $\frac{1}{14}$ for $c_2$? I'm just not sure how they arrived at solving the left hand side and the book doesn't really explain it well for me.


texts: Design Hashing function from known distribution of bits to be set

texts:
How to design Hashing function when the distribution for the bits that will be set are known before hand? Given that the number of bits to be set is constant. The intention is to minimize the hash collisions and resizing of the hash table.

Mentioned query is more of an open-ended question. What I am interested is in the known existing approach for such scenarios?

More description: Design a hashing function where the keys are formed from 64 bits. The number of bits $(l)$ that will be set is fixed which is $3 \leq l \leq 15$ of the 64 bits in the key. Further clarification, any $l$ bits in of the given 64 bit will be set.

Approximate distribution for the respective bit to be set is also known beforehand. The approximate probability of the $k^{th}$ bit will be set in the keys that will be inserted is known. In other words, for most keys that will be inserted in the hash table $k^{th}$ bit will not be set.

Implementation is to be done in C++ if this information helps in anyway.

I have tried with bit mixing from link which has the following function:

UInt64 MurmurHash3Mixer( UInt64 key )
  {
  key ^= (key >> 33);
  key *= 0xff51afd7ed558ccd;
  key ^= (key >> 33);
  key *= 0xc4ceb9fe1a85ec53;
  key ^= (key >> 33);

  return key;
  }

But the number of key collisions wasn't much affected. Also, the execution time worsened in comparison to hashing scheme that comes with std::ordered_map.

For my case, most of the keys have the property that last certain will never be set and the probability of initial bits will be set is lower than the bits in the middle section.

std::ordered_map - I believe uses the initial bits to map to a memory location. Since, many of keys share the property more time is spent in re-hashing.


texts: string concatenation vs language concatenation

texts:
What exactly is the difference between
$$
C = \{a^*\}\{b\}\{a^*\}\{b\}\{a^*\}\{b\}
$$
and
$$
D = \{a^nba^nba^nb | n \geq 0 \}
$$
It is known that D is non-regular and C is regular, but I am not sure why.


texts: A specific version of a job scheduling problem

texts:
I'm looking for a solutions or book references to a given variation of a job scheduling problem:

Given $n$ machines (let's denote it by $m_1, m_2, \ldots, m_n$) and $r$ tasks ($t_1, t_2, \ldots, t_r$). Each task $t$ can be described as a tuple $\left( (a_1, b_1), (a_2, b_2), \ldots, (a_k, b_k) \right)$, where $a_i$ is a number of some machine and $b_i$ is a required time to complete task $t$ on machine $a_i$. To complete the task, you need to start it on the first machine in the sequence ($a_1$) for a given amount of time ($b_1$), then start it on the second ($a_2$) and so on, until you finish your job on all of the given machines. It could be possible that number of machines in job description is smaller than $n$.

We will assume that tasks are atomic and one machine can do only one task in the same time, so it's possible that some task need to wait for a moment when a given machine is free.
Finally, we want to find the ordering of tasks to given machines to minimize the total time of all tasks.


texts: How to Reconcile Apparent Discrepancy in this Algorithm's Runtime?

texts:
I'm currently working through Algorithms by Dr. Jeff Erickson. The following is an algorithm presented in the book:
NDaysOfChristmas(gifts[2 .. n]):

    for i ← 1 to n
        Sing “On the ith day of Christmas, my true love gave to me”

        for j ← i down to 2
            Sing “j gifts[j],”
        if i > 1
            Sing “and”

        Sing “a partridge in a pear tree.”

Here's the runtime analysis of the algorithm presented by Dr. Erickson:

The input to NDaysOfChristmas is a list of $n − 1$ gifts, represented here as an array. It’s quite easy to show that the singing time is $\Theta(n^{2})$; in particular, the singer mentions the name of a gift $\sum_{i=1}^ni = \frac{n(n + 1)}{2}$ times (counting the partridge in the pear tree). It’s also easy to see that during the first $n$ days of Christmas, my true love gave to me exactly $\sum_{i=1}^{n}\sum_{j=1}^{i}j = \frac{n(n + 1)(n + 2)}{6} = \Theta(n^3)$ gifts.

I can't seem to grasp how it is possible your $``$true love$"$ had given you $\Theta(n^3)$ gifts, while a computer scientist looking at this algorithm would say the algorithm's runtime complexity is $\Theta(n^2)$?
Dr. Erickson also says the name of a gift is mentioned $\frac{n(n+1)}{2}$ times, which is in $\Theta(n^2)$.


texts: Efficiently generating a prime polynomial of a given degree

texts: I'm playing around with finite field arithmetic and implementing it in a little library. I'd like to be able to handle arbitrary finite fields given their size and characteristic. I don't want to write down a prime polynomial for every given possible finite field though. How can I generate a prime polynomial of a given degree for use in multiplication? To be clear I don't care which polynomial I get, and I don't want all of them. I just want any old one of a given degree. If this is an open research question what if we only try to solve it for $GF(2^n)$?


texts: Is it possible to prevent arithmetic errors with a dependent type system?

texts:
In a functional programming language I have functions like
$$f\colon Int \times Int \times \cdots \times Int \to Int$$ which do some computation. However for certain arguments $(x_0, \dots, x_n)$ the function will cause arithmetic errors like Integer overflows, Integer underflow or even Division by zero. I do not want to handle those special cases within the function. Instead I would like to throw a type error at compile-time if someone calls the function with a undefined input.

So, my question is: Is possible to prevent arithmetic errors with a dependent type system?

And if so, does Adga, Idris or any other dependent type language support this?


texts: Terminology about the word Function : General vs Computable

texts:
I've seen two different concepts referred to by the term "function":

A small part of a program specified by the composition of constants and other functions as paramaters, such as the "functions" in Lisp
A set of tuples, as referred to in formal logic, which is not necessarily computable

The first concept is very fundamental to software design.  The second concept is very fundamental to formal reasoning.  However, a task I've been working on is analyzing software with formal logic, so the conflation of the terms is a bother.

Is there any agreed upon, concise, unambiguous terminology to distinguish these two ideas?  I can think of several verbose terms, such as "Computable Function" and "General Function", but imagine having to type that out with the specification of every modular component.

Any references, ideas, or supported opinions are appreciated, thanks.


texts: Algorithm to determine which vertices/edges would disconnect undirected graph if removed

texts:
Is anyone aware of an algorithm to determine which vertices/edges would disconnect an undirected graph if removed? For all vertices/edges.

Of course I could run a BFS for each vertex and for each edge to test if the remaining graph would be connected. But is there anything more efficient?

In the end I would like to uniformly draw a vertex/edge out of those that would not disconnect the graph, to make simulations for fail-over routing in a computer network.


texts: Karnaugh map with don't care: increasing the number of groups instead of simplifying

texts:
AB
        00  01  11  10
    00 | x | 1 | 0 | 1 |
CD  01 | 0 | 1 | x | 0 |
    11 | 1 | x | x | 0 |
    10 | x | 0 | 0 | x |

The answer to the above Karnaugh map is $F(ABCD) = B D + \bar B \bar D + \bar A \bar C \bar D + \bar A C D$
according to my book and the K-map solvers online.

But what I don't get is that I can further reduce the terms in this answer:
$F(ABCD) = \bar B \bar D + \bar A CD + \bar A B \bar C$
also covers all the min terms in lesser groups.

The answer in my book just has a bigger group covering additional don't cares. Since they are optional shouldn't my answer be correct?


texts:
I'm working on a problem set for my algorithms course and we're asked to solve the recurrence relation

$$
T(n) = 7T(n/2) + n^2 + \log(n).
$$

Since this recurrence relation is not of the form $T(n) = aT(n/b) + n^d$ and therefore the master theorem does not apply, I'm confused about where to begin in solving it.

Could anyone give me an idea of what method(s) might be useful in solving this? I'm flipping through our textbook and don't see anything on solving general recurrence relations where master's theorem is unusable.


texts: Question about time-complexity for MST-like algorithm

texts:
I have got a problem with an excercise about graphs:

Your friend has been hired by a brewery to work out the most efficient
delivery route for the beer-delivery truck drivers. A typical delivery has about 50 stops and the company wants to save money by driving the
shortest possible distance. Your friend ignores your advice and decides on an algorithm, as follows:

Start at the depot,
Go to the nearest location that has not yet been
delivered to:

Deliver
Repeat until you have delivered all the beer

Return to depot

And the quesiton is:
What is the Big-O complexity of this approach? Why?

I do not think this way of solving problem is any algorithm like Prim's algorithm, and I have no clue what can be a complexity. Could anyone explain me?


texts: Set of all countably infinite strings over a finite alphabet >1

texts: Is the set of all countably infinite strings over a finite alphabet that contains more than one letter countably infinite?


texts:
The game on the graph $G$ is defined as follows. Initially, the chip is located at one of the vertices (let's call it the starting one). The players take turns, on each move it is necessary to move the piece along any outgoing edge to the vertex, where the piece has never been.
The one who cannot make a move loses. How to Prove that the former wins if and only if
the starting vertex lies in all maximal matchings?


texts:
Certain architectures have "dismissible loads" in addition to normal loads: when the load is denied, instead of issuing an exception (leading to a segmentation fault), a default value (e.g., zero) is written to the destination register. This allows the compiler to move loads before a conditional branch, which may be important for performance on non speculative cores.
I was wondering if there was a Risc-V extension for this. I haven't found any.


texts:
I was asked a question in an exam

You are given an array A[1..n] of length n with each cell containing a ⟨height,weight⟩ pair. All height values are distinct, and so are all weight values. The array is sorted in increasing order of the height values.
Your task is to design a recursive divide-and-conquer algorithm that given an integer k ∈ [1, n], finds the entry with the kth smallest weight value. You are allowed to use only O (1) extra space in every level of recursion. Though your algorithm is permitted to reorder the entries of A if required, it must restore the original order of the entries before termination. Your algorithm must run in Θ (n) time.

Does such an algorithm exist? I can use the Deterministic Select Algorithm to find the kth smallest weight value. But this would require some shuffles to find pivots where any element before pivots location is lesser and any element above pivots location is greater.


texts: What is the relation between EXPTIME and NP HARD complexity classes?

texts: Need to know the relation between EXPTIME and NP HARD complexity classes.


texts: How does it possible that $ZPP=RP\cap coRP$?

texts:
How does it possible that $ZPP=RP\cap coRP$ ?
After all, it must be that $RP\cap coRP = \emptyset$
Where Am I wrong ?


texts: Algorithm for getting the outer boundary of a large graph

texts:
I am trying to create an isochrone based on the OpenStreetMap data set. Everything works fine, I extracted data, processed it into a DAG, ran a Dijkstra algorithm over it. The result is a subset of the complete graph. This is an impression of the covered parts of the subset displayed over Google Maps:

However, when the area gets larger, the number of reached vertices gets very large and displaying like this gets slow. What I would like to do is convert the set of edges and vertices into a polygon. Basically, this should be posible by removing all of the inner edges, leaving just the edges around the boundary of the area and the edges pointing out from it. I know coordinates for all vertices and approximating each edge as a line would be fine. Larger inner areas should become holes inside the polygon.

My first attempt was to use an geospatial library (in my case the SqlServer spatial extensions), create a multiline from all of the edges and doing an ST_Buffer on it. Turns out to be very slow and memory consuming for large numbers of edges (> 1000)

I was thinking along the lines of finding small polygons in the set (turning left at every turn?) and removing every edge that is part of 2 of these polygons.

Extra image to use in comment below:


texts: Weight of lowest common ancestor satisfies strong triangle inequality

texts:
How do I prove that $d(x,y)$, defined as the weight of the lowest common ancestor of $x,y$, satisfies the strong triangle inequality:
$$ d(x,y) \le \max(d(x,z), d(y,z)) $$
How do I even start such a proof?


texts:
I am solving UVa--1229 https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=671&page=show_problem&problem=3670
From the problem I have understood what is required - given a list of dictionary words and their definitions, choose minimum set of words such that the whole dictionary can be constructed, if one is given meaning of those words. So words in dictionary must not introduce a new word in definition which has no meaning in dictionary. This implies I have to find SCC.
But there may be several SCCs, I think I must choose which is first in toposort of contracted DAG. Am I correct or is there another way to do it? I have read hints but its' mentioned to find SCC, then use dfs that will be answer. I don't get that. Can someone explain approach to this problem.
That's my first question on SCC's :)


texts:
https://cseweb.ucsd.edu/~mihir/cse200/ss6.pdf shows $NP$ in $BPP$ implies $NP$ in $RP$ by showing $SAT$ is in $RP$ if $NP$ is in $BPP$ and since $SAT$ is $NP$ complete we have $NP$ is in $RP$.

However since $UP$ does not have a complete problem and so can we still show $UP$ in $BPP$ implies $UP$ is in $RP$?


texts: I don't understand why O notation is the worst case. If this notations describes a function f such that 0 <= f(n) <= cg(n), we can see that in any case f will be smaller that the original function g that describes the running time. In my idea, f(n) describes a better option because the running time is less for any input n. Someone can explain me please why O notation is the worst case?


texts:
From this book and other study in complexity theory, I have seen the following statement:

  The definition of NP is not symmetric with respect to yes-instances and no-instances.  For example, it is an open question whether the following problem belongs to NP: given a graph G, is it true that G is not Hamiltonian?

However, I was wondering if this this problem was NP-Complete.  Could someone let me know if the following statement true?

  Determining a that a Graph is not Hamiltonian is an NP-Complete problem.


texts: Will quantum computers out-scale classical computers at P-problems?

texts:
It is my understanding that quantum computers have gained interest, because some interesting problems are suspected to be in the BQP-class, but not in the P-class (integer factorization, ...). Quantum computers would then be able to solve these problems efficiently, while classical computers are not.

However, I'm wondering if quantum computers will also be able to out-scale classical computers at P-problems. Part of my reasoning leading to this question is the idea that quantum computers might be able to solve "classical" P-problems with a relatively small number of qubits. Exponential scaling of the number of qubits over time, might lead to "quantum suppremacy", not only for BQP, but also for P-problems.

Are quantum computers only useful to tackle specific problems, i.e. BQP-problems that are (potentially) not in the P-class? Or is it reasonable to assume that quantum computers might gain superiority for all types of problems?


texts: Succinct data structure to return occurences of letters until an index

texts:
I want to try and use a succinct type data structure in order to find the amount of occurences of a letter $C$ in a string $S$ until a given index $I$.

Assume we have a string $S$ of length $n$ over the alphabet $\Sigma = \{1,2,3,\ldots,n\}$. I want to build a data structure whose space usage is at most $O(n)$ machine-size words.

Given $C$ (a valid letter from $\Sigma$) and an index $i$ such that $0 \le i \lt n$, the data structure should be able to return the number of occurrences of $C$ in $S[1..i]$ as efficiently as possible (but not necessarily in $O(1)$ time). This is the only query possible.

The data structure is aware of $S$ when created.

What I've tried to far is to split the string $S$ into blocks and to store info about each block with the number of occurrences of each letter in the  previous block. I couldn't find how to make it lighter so the memory complexity be as requested.


texts: Clock solitaire game and principle of deferred decision

texts:
I have been reading the randomized algorithm book by Rajeev Motwani and Prabhakar Raghavan. In section 3.5 they have introduced principle of deferred decision which is a different probability space. The example they provided is a clock solitaire game. The game is as follows. Initially 52 cards are randomly grouped into 4 cards of 13 piles. The piles are labeled $1,2,3,...,10,Q,J,K,A$. The game starts by drawing a card from $K$ labeled pile. The next draw will be taken place from the pile with the face value of the drawn card. For an example suppose the drawn card is 7, then we go to the pile labeled $7$ and pick a card from this pile. We continue in this fashion. The game ends when we reach an empty pile. And one wins if all the piles are empty when the game ends. It is easy to show that the last card drawn must have face value $K$.

Now, to analyze the probability of winning, the author assumes a different probability space named "Principle of deferred decision". The idea is to "let the random choices unfold with the progress of the game, rather than fix the entire set of choices in advance." With this, they conclude that the probability of winning i.e., the probability that 52nd card being $K$ is 1/13. Can anyone explain why this is 1/13?


texts: Can a transcendental number like $e$ or $\pi$ be compressed as not algorithmically random?

texts:
The related and interesting fields of Information Theory, Turing Computability, Kolmogorov Complexity and Algorithmic Information Theory, give definitions of algorithmically random numbers.

  An algorithmically random number is a number (in some encoding,
  usually binary) for which the shortest program (e.g using a Turing
  Machine) to generate the number, has the same length (number of
  bits) as the number itself.

In this sense numbers like $\sqrt{e}$ or $\pi$ are not random since well known (mathematical) relations exist which in effect function as algorithms for these numbers.

However, especially for $e$ and $\pi$ (which are transcendental numbers) it is known that they are defined by infinite power series.

For example $e = \sum_{n=0}^\infty \frac{1}{n!}$

So even though a number, which is the binary representation of  $\sqrt{e}$, is not alg. random, a program would (still?) need the description of the (infinite) bits of the (transcendental) number $e$ itself.

Can transcendental numbers (really) be compressed?

Where is this argument wrong?

UPDATE:

Also note the fact that for almost all transcendental numbers, and irrational numbers in general, the frequency of digits is uniform (much like a random sequence). So its Shannon entropy should be equal to a random string, however the Kolmogorov Complexity, which is related to Shannon Entropy, would be different (as not alg. random)

Thank you


texts: What is the fastest way to check if an integer is divisible by another?

texts:
What would the Big O be?
Can something like this be done in O(log(n)) where n is the number of bits?


texts: Linear programs with strict inequalities and supremum objectives

texts:
Linear programming can solve only problems with weak inequalities, such as "maximize $c x$ such that $A x \leq b$". This makes sense, since problems with strict inequality often do not have a solution. For example "maximize $x$ such that $x<5$" does not have a solution.

But suppose we are interested in finding supremum instead of maximum. In this case, the above program does have a solution - the supremum is $5$.

Given a linear program with strict inequalities and a supremum or infimum objective, is it possible to solve it by reduction to a standard linear program?


texts: Proving the following chain of implications

texts:
I'm struggling with a proof in the text for my logic course, and I'm wondering if someone could offer a hint or some help. The question is basically as follows. Show that if the decision problem for satisfiability is solvable  iff the decision problem for implication is solvable. Then, show that the decision problem of implication is solvable iff the decision problem of validity is solvable.

My attempt so far is as follows. Suppose we can decide whether or not a given sentence is satisfiable. If not, implication problem for the sentence A is true. If it is satisfiable, we must ensure that all interpretations in which A is satisfiable, B is also true.

I'm assuming the second part proceeds similarly, but I'm not exactly sure, and would appreciate any guidance.

Thanks


texts: Given some abstract problem how can I prove that this problem is not in P. I mean, what is the method for proving such thesis?


texts: Quantitatively speaking, what's the most popular area of computer science research?

texts: Like this one, for example, but for computer science. Maybe some survey of that kind was conducted for CS as well?


texts:
Alice and bob play a game.
Bob has a well-shuffled deck of $M=4999$ white cards and $N=4999$  green cards. Each permutation of cards in the deck is equally likely. Alice has set some rules for Bob.

Every time Bob flips a white card he gets one coin, otherwise he loses one coin. At any moment (even at the beginning), Bob is allowed to stop playing the game and keep the number of coins that he has.
During the game-play the balance of coins that Bob has may be negative.

If Bob plays optimally, what the expected amount of coins Bob will have?

Can any body give me an idea or a hint how to solve it.


texts: minimum number of adjacent swaps to remove any instances of "ab" in a string

texts:
How can I get started at finding a recursive/dynamic solution to the problem?

For example, how many adjacent swaps is at least needed to convert the given string abaaccbabaabcab (representing all other characters as c) to one without any instances of "ab"? It's elusive for me to come up with a way of breaking the problem into (independent) sub-problems.

For strings consisting of only as and bs, the problem reduces to taking all bs before as, but it becomes complicated with other characters involved.

PS: Can we assert that in at least one scenario of minimum swapping, swaps do not go beyond any block of c...c, where ... simply consists of a pile of as and bs? In that case, as either place after bs, or before first c, depending on which is closer. Vice versa for bs. I'm not sure if it helps though.

Thanks for your help.


texts:
I understand the difference in the parsing tables of the above 4 parsers.
I understand that CLR>LALR>SLR>LR(0) in terms of power.

Are shift and goto moves for all LR parsers ( LR(0), SLR(1),CLR(1),LALR(1) ) same?. I think goto should vary as reduce moves vary?
Also, if a grammar is accepted by CLR(1) parser, for which parser it would have highest and lowest no. of reduce moves or would it be the same?
Please explain


texts:
Example: Suppose $H:${$1,...,n$} $\rightarrow ${$1,..,n$} be a uniform hash function. for input $x$, $z$ is equal to number of trailing zero in the right side of $H(x)$. for $0 \leq c \leq 1$ what is the order of probability $ z \geq c \log n$? $C$ is constant here.
Answer: $O(1/n^c)$
How  this this is can be achieved?
I think this is same with this question:
Source: introduction to algorithm CLRS Page 652 Ex.11-C


texts: Minimize cost of recursive pairwise sums: how to prove the greedy solution works?

texts:
The problem is in this other question.

Why does this always work? It's not clear to me how one would use induction.

For $n = 3$, a quick calculation shows it works, however, I don't think it generalizes well.


texts: What is an example of set $A$, that is decidable if $AA$, but which is not decidable if it is $A$ alone

texts:
I encountered a question to give an example of a set $A$ that is not decidable as $A$, but which becomes decidable if it is concatenated with itself, i.e. $AA$.

In case a set $A$ is decidable, then it is easy to see that $AA$ is also decidable, since a $TM$ that decides $A$ can be modified to also recognize $AA$... But I am having a hard time to look for examples given its converse.


texts: About the definition of "differential privacy" in communication complexity

texts:
In the context of communication complexity I see a definition of differential privacy which isn't totally clear to me as to why it makes sense.

So the two parties $A$ and $B$ draw two strings $X$ and $Y$ from the set $S^n$ where $S$ is some finite set. Let $P$ be the protocol. Now if $z_1 = (X_1,Y_1)$ and $z_2 = (X_2,Y_2)$ are two instances drawn with a probability distribution $\mu$ over the set $S^n \times S^n$ then the protocol $P$ is called "$\epsilon$-differentially private" if the following holds:

$$e^{-2 \epsilon n}  \leq  \Pr[P(z_1) = p]  /  \Pr[P(z_2) = p]   \leq e^{2 \epsilon n}$$

Now why does this make sense? What's the intuition?
How is this related to the bounded derivative definition?


texts: What is the time complexity of the following program?

texts:
Please help me calculate the time complexity of the following program.

int fun (int n) {
  if (n <= 2)
   return 1;
  else
   return fun(sqrt(n)) + n;
}

Please explain.

There were four choices given.

$\Theta(n^2)$
$\Theta(n \log n)$
$\Theta(\log n)$
$\Theta(\log \log n)$


texts: Bound covariance of two discrete random variables

texts: Let $X,Y$ be two random variables over a discrete probability space, such that $X \in [0,1]$ and $Y \in [0,1]$.  I want to prove that $$ |\text{Cov}[X,Y]| \leq \sqrt{0.5 \; I[X,Y]}$$ where $I[]$ is the mutual information of the variables.  Is there an "elegant" way to prove that?  Some smart argument rather than technical analysis.


texts: Are fully connected layers required for convnets?

texts:
I have a reinforcement learning model I'm trying to create for a grid based game. One of the features of the game is that the game board can get bigger mid game, although I know this is a problem that machine learning isn't very good at. However, one idea that I had was to train a convolutional neural net model that doesn't have a fully connected layer at the end, so that the input and output size of the net can vary together, and the model will still work because it won't need any additional weights to produce an output. In addition, adding a fully connected layer or two at the end would be a very large amount of extra weights to train, since the action space of the problem is very large (15232 discrete actions if I remove the expanding grid portion of the game). If my calculations are correct, a single fully connected layer would become 464 million more weights. Which seems like a lot compared to my existing 223,350 trainable parameters.

Here is one iteration of this network type I've tested:

For this model, the observation space is 92 layers deep, and 28 wide by 16 tall. And the action space is 34 layers deep, and 28 wide by 16 tall. I'm not getting amazing results from this network (although better than random choice), which could be due to a multitude of reasons. However, I don't know if this is bad idea as I'm having trouble reasoning about this design generally.

Is a fully connected layer at the end necessary for the network to learn global ideas about the observation space?


texts: Given a set of sets, find the magnitude (number of elements) of the smallest set containing at least one element from each set

texts: I know that the hitting problem is NP hard, but is it possible to find the magnitude of the smallest set? Also, provide the runtime.


texts:
A lot of articles say that hash tree traversal cost to any randomly chosen leaf is $\mathcal{O}(\log_2 N)$ ($N$ is a number of leafs) and that is right. If we have a tree of 8 leafs it will take us at most 3 operations to get to any leaf, if we have a tree of 64 leafs it will take us at most 5 operations etc.

But lets say I need to check every leaf sequentially to check if all blocks of a file are correct, then I would need $\mathcal{O}(N \log_2 N)$ operations. Or if I would check every second leaf (just left leaf of every pair) I would need $\mathcal{O}((\frac{N\log_2 N}{2}))$ operations. That is, I will need $\mathcal{O}(\log_2 N)$ operations for every leaf? Which leads to exponentially growing evaluations curve and it would be better to use simple hash list or hash chain? Am I right?

Or I just don't see/know something?

*Note, chart has logarithmic scale


texts: Feature selections : Still a high dimentionality

texts:
One of the advantage of using a features reduction/sub feature selection is to avoid a high dimentionality.

The most known method is the Forward selection, where it finds the best combinations of features among others, iteratively. Now please have a look at this picture retrieved from a ppt slide on the internet.

The second row of the table shows that the 11 features are the features selected/reduced from initial 20 features. My question is that, the 11 features are still considered as a high-dimensional features set, indeed one can't just subtitute it over a KNN function. Now I'm confused as to how he/she then adapt it to the KNN classifier for the 11 features?


texts: How to Generate Münchhausen Numbers in High Radices?

texts:
A Münchhausen number is a whole number equal to the sum of its digits raised to powers of themselves. For the purpose of such calculations, the convention is that $0^0 = 1$. For example, in radix 10, the number 3435 is a Münchhausen number, since $3435 = 3^3 + 4^4 + 3^3 + 5^5$. In radix 4, the number 313 is a Münchhausen number, since $313 = 3^3 + 1^1 + 3^3$. On a curious property of 3435 covers more details, and shows that Münchhausen numbers in radix $b$ must be less than or equal to $2b^b$.

Münchhausen numbers for base $b$ can be generated with a brute-force search, by checking whether each number from 1 to $2b^b$ is equal to the sum of its digits raised to powers of themselves. One way to improve upon this is to generate multisets of digits, and for each combination check whether the sum of digits raised to powers of themselves produces a number with the same multiset of digits. Even with parallelization, this seems infeasible for large bases. For example, for base 35, a Münchhausen number would have at most 36 digits. The number of combinations (with repetitions) of 36 elements from 35 digits is $\binom{35 + 36 - 1}{36}=\binom{70}{36}=109,069,992,321,755,544,170.$ This is in addition to those multisets with fewer than 36 elements that would also be checked.

If any, what algorithm(s) can be used to generate Münchhausen numbers feasibly for high bases (e.g., base 35)? OEIS sequence A166623 includes Münchhausen numbers for bases between 2 and 35.


texts: Intrinsic matrices in stereo camera calibration

texts:
Suppose I have two cameras, c1 and c2, observing the same scene. I can now

Calibrate each camera independently (e.g., with MATLAB's Camera Calibration App)
Calibrate both cameras simultaneously (e.g., with MATLAB's Stereo Camera Calibration App).

Interestingly, the values calculated for the intrinsic parameters of both cameras are different using method 1) and method 2). To me it is not clear why this should be the case. The intrinsic parameters of camera 1 are independent of the ones of camera 2 and vice versa, why should they influence each other? I suppose there is some form of optimization aiming to optimize simultaneously in the stereo case, however I would think that the "stereo optimum" is the same as the combined "single optimum".

Any insight?


texts:
When talking about general data structure design, my lecture notes talk about one of the concerns being cost of operations. As well as the individual cost, it mentions amortized cost. But then it goes on to say:

  Amortized cost can be:

  absolute (e.g. for every sequence σ of operations (O(n log n))
  competitive (e.g. for every sequence σ of operations O(OPT(σ)))

  where OPT(σ) is the optimal cost of clairvoyant algorithms

I can't really make any sense of this. Googling throws up this but I can't see the relevance to data structures more generally. Can anyone help me understand the quoted text?


texts: Space complexity of Travelling Salesman Problem

texts:
I am having trouble coming up with the space complexity of the TSP algorithm.

https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/

To me the space complexity for the brute force is the cost of storing all possible permutations right ? That should take space O($N!$) where N is the number of cities/nodes/vertexes.

Similarly for the Dynamic Programming algorithm it stores all tours, that is also O($N!$), but the site says the space complexity is O($2^{N}$)

Can someone explain if my logic for space complexities is correct, especially for the Dynamic Programming algorithm.

Thank you


texts: Hard vertex 3-coloring for easily edge-colorable graph

texts:
Suppose we want to use a reduction of 3-colorability to a certain problem to prove said problem is NP-c. But to pull off the reduction, one needs to take a graph-class for which 3-coloring is NP-c and for a given input graph decompose its edges into as few independent groups as possible - basically edge-coloring the graph.

The function of this edge-decomposition is to allow replacing edges from each group by gadgets - gadgets from the same group would undesirably influence each other's function if they coincide. The issue is that the more groups there are, the higher complexity of the problem we reduce to (more gadget types) and thus less interesting result.

So, the question is: what classes of graphs can we allow as an input so that the task (vertex 3-coloring) remains NP-c, but also the maximum edge-chromatic number is minimized (and at most 6)?

Also, does the particular question change if we do not require the edge-coloring of the class to be P?

Clearly, one can take any graph and replace vertices od degrees 6 and higher by gadgets to reduce the max degree to 6 (maintaining equivalent problem). Vizing's theorem then guarantees the edge-chromatic number to be at most 7, in a constructive way. Is it possible to at least get to a vizing's class one while maintaining NP-c?

Any suggestions regarding where one might find some research tackling vertex-coloring hardness in respect to edge-coloring parameter?


texts: Help understanding how to make a simple 3D minimum bounding sphere?

texts:
I need to develop a minimum bounding sphere. It'll only ever be in 3 dimensions, and the numbers of points are relatively small (500-5000 total). Performance is important however.

I was looking for some help finding/understanding an algorithm to do this.

Getting an exact answer would be preferred, but I think if the radius is ~3-5% larger that might still be doable.

From the Wikipedia page the most promising algorithms seemed to be the ones by Emo Welzl, Fischer or Larsson.

However, I'm not following how any of the algorithms actually...work.

Fischer's has an open-source implementation here but there's so much boilerplate, error-checking, generality, logging and fluff that I can't follow the algorithm part of it. (And using it as-is wouldn't work, I really need something much smaller and simpler that I can write myself) I couldn't follow the paper very well, but maybe it's much simpler than I realize.

Larsson's (Extremal Points Optimal Sphere) seems promising but the pseudo-code in the paper seems to be leaving a lot out (FindExtremalPoints, MinimumSphere, GrowSphere, etc), and I'm confused what the array of N is for, among other things.

Emo Welzl's is the one I think I understand the most but again the example isn't making any sense, that seems like it's just the entry point and not the actual code to create the sphere. B_MINIDISK I think is where the bulk work is being done in the paper, but it feels like there's a step missing or something is getting brushed over.

EDIT: Maybe MTFDISK and B_MTFDISK are actually what I need? I still don't follow what b_md is though, and it's said that it's "non-trivial".

Could anyone explain in simpler terms how one of these three works or suggest an alternative? I think partially because these are intended to work for many dimensions I've gotten very confused.


texts: Prove that if $\mathsf{P^k}=\mathsf{NP}$ then $\mathsf{NP}=\mathsf{co\text{-}NP}$

texts:
Prove if a oracle machine $K$ is given with $\mathsf{P^k}=\mathsf{NP}$ then $\mathsf{NP}=\mathsf{co\text{-}NP}$.

Lets assume that $\mathsf{P^k}=\mathsf{NP}$ then $\mathsf{co\text{-}P^k}=\mathsf{co\text{-}NP}$.  I am stuck here, I don't know how to prove this. Can someone help?

I know that $\mathsf{P}=\mathsf{co\text{-}P}$ but can I also say $\mathsf{P^k}=\mathsf{co\text{-}P^k}$ or do I have to prove it ?


texts: Can we convert an NFA to a regular expression of polynomial length?

texts:
Can we convert an NFA having $n$ states to a regular expression of length $\mathrm{poly}(n)$?

In contrast, it is well known that a regular expression of length $n$ can be easily converted to an $\mathcal{O}(n)$-state NFA.


texts: How to calculate the dimension of a convex polyhedron?

texts:
A convex polyhedron can be represented by a set of linear inequalities. If the inequalities involve $n$ variables, then the polyhedron can be $n$-dimensional, but it can also be of a smaller dimension - in case some of the inequalities in fact define equalities. As a simple example, the following inequalities:
$$x_1 \geq 0, x_2\geq 0, x_3 \geq 0\\
x_1 \leq 1, x_2\leq 1, x_3 \leq 1
$$
define a 3-dimensional polyhedron (a cube). But if the last inequality is changed to $x_3 \leq 0$ then the polyhedron becomes 2-dimensional (a square).
What is an algorithm for determining the dimension of a polyhedron given by a set of linear inequalities?
EDIT: By "convex polyhedron" I meant any object that can be represented by the intersection of a finite number of half-spaces (i.e., conjunction of finitely many linear inequalities).


texts: How can the max-flow and min-cut problems, if dual to one another, both have unbounded optimal value?

texts:
The max-flow min-cut theorem states that the value of the maximum flow is equal to the minimum cut capacity.

It is possible that the max-flow and min-cut is equal to $\infty$.

However, reading Introduction to Linear Optimization by Bertsimas and Tsitsiklis, I get the impression that the max-flow and min-cut problems are dual to one another.

From duality theory, I know that, if the primal has finite optimal value then the dual has finite optimal value. Also, if the primal has unbounded optimal value, then the dual is infeasible and vice versa.

In the case of the max-flow and min-cut problems, how can they both have unbounded optimal value ??