# Question
Title: Survival algorithm for Network deterministic failures
Consider an undirected network $G = (V,E)$ in which edge $e$ $\in$ $E$ fails after (deterministic) time $t(e) \> 0$. Network failure occurs at the first instant in which $G$ is no longer connected. Let $m = |E|$ and assume the values $\\{t(e): e \in E\\}$ are distinct.

You wish to determine the instant $\tau$ at which the network fails.

1- Suppose you solve this problem via an intuitive algorithm in which you first sort the edges according to $t(e)$ and then remove the edges, one at a time, to determine if the network has failed. Establish the complexity of this algorithm.

**My Answer: We can sort edges in $O(m\log n)$ time + removing edges takes $O(1)$ * the number of edges to be removed $O(m)$. So the complexity is $O(m^2)$.**

2- Show that a variation of your intuitive algorithm from part a can determine $\tau$ in a reduced time complexity in which a factor of m is changed to log m.

**My expectation: I think we might use a heap for storing edges but I am not sure how to implement it.**

3- Using what you know about spanning trees, can you write a new algorithm to improve upon (or equal) the complexity of your algorithm from part b? (Hint: The network will be failed as soon as every spanning tree. contains a failed edge.)

**My expectation: I believe we need to find all spanning trees but I am not sure if this will help reduce complexity**.

Can anyone help me solving the given problem or direct me towards a reasonable solution?

# Answer
> 0 votes
# Part b

Suppose $t(e\_1)\>t(e\_2)\>\cdots$, what you want is $e\_i$ such that the graph with $e\_1,\ldots,e\_i$ is connected. Part a checks the graph with $e\_1,\ldots,e\_m$, then the graph with $e\_1,\ldots,e\_{m-1}$, and so on. This process can be improved by binary search, i.e. checking the graph with $e\_1,\ldots,e\_{m/2}$, then graph with $e\_1,\ldots,e\_{m/4}$ or with $e\_1,\ldots,e\_{3m/4}$ depending on the result of the first check, and so on.

# Part c

You don't need to check all spanning trees. You only need to find the spanning tree of whose edges the earliest failure time is maximized. This is known as a minimum bottleneck spanning tree (cost of an edge is the negative of its failure time).

---
Tags: algorithms, graphs, time-complexity, spanning-trees
---


# Question
Title: Complexity of divide and conquer algorithm with a quadratic merge function
Consider the following pseudocode:

```
int divide(int l , int r){
    if r - l > 3 then
        mid = (l + r) / 2
        divide(l , mid)
        divide(mid + 1, r)
        return merge(l, mid, r)
    else
        return bruteforce_solution(l, r)
}

```

If merge function takes $O(n^2)$ time, then total complexity can be found as a solution of the reccurence: $T(n)=2T(n/2)+n^2$
The solution of a the reccurence is $T(n)=2n^2-n$
So $O(log(n))$ calls of an $O(n^2)$ function takes $O(n^2)$ time?

# Answer
> 1 votes
Let $S(n) = T(n)/n^2$. Then $$ S(n) = \frac{T(n)}{n^2} = \frac{2T(n/2)}{n^2} + 1 = \frac{2(n/2)^2S(n/2)}{n^2} + 1 = \frac{S(n/2)}{2} + 1. $$ Assuming a base case of $S(1) = 2$ and that $n$ is a power of $2$, one can prove by induction that $S(n) = 2$. Indeed, this holds for $n = 1$, and if it holds for $n/2$, then $$S(n) = S(n/2)/2 + 1 = 2/2 + 1 = 2.$$ We conclude that if $T(1) = 2$ and $n$ is a power of $2$ then $T(n) = 2n^2$.

What happened here? First we had one call to a routine that takes time $n^2$. Then we had two calls to a routine that takes time $(n/2)^2 = n^2/4$, taking a total time of $n^2/2$. Then we had four calls to a routine that takes time $(n/4)^2 = n^2/16$, taking a total time of $n^2/4$. And so on. The amount of work at each level decreases exponentially, and so the total amount of work stays $O(n^2)$ although there are $\log n$ different levels.

If we replaced $2T(n/2)$ by $aT(n/b)$, then the behavior of the recurrence would depend on the relation between $\log\_b a$ and $2$. This is covered by the well-known *master theorem*.

---
Tags: complexity-theory, time-complexity, divide-and-conquer
---


title: Time complexity of Ackermann's Function

text:
# Question
Title: Time complexity of Ackermann's Function
How would one go about classifying the time complexity of Ackermann's function, and can we say that all primitive-recursive functions are asymptotically bounded by the complexity of the Ackermann function as an asymptotic upper bound?

Edit: I want to make it clear that I am interested in the time complexity of computing Ackermman's function and whether the time complexity of computing any primitive recursive function is asymptotically bounded by the time complexity of computing Ackermman's function. I am not interested in the actual values of those functions.

I am asking because I remember seeing an assertion of my second question in an old book but no proof was shown and no time complexity for computing Ackermman's function was listed, so the assertion was by no means rigorous.

# Answer
You are asking (or at least typing) multiple questions that are unrelated.

### Time Complexity of the Ackermann function

First, understand that this is not a meaningful query. The Ackermann function, let's call it $A$ (assume a one-parameter variant), is a function, not an algorithm. You can certainly talk about $\Theta(A)$.

What you likely mean is the time $T\_A(n)$ required to compute $A(n)$. I do not know of any algorithm besides explicitly computing the recurrence; the runtime of this approach can be investigated using the standard approach. It's unlikely that the result will be a meaningful $\Theta$-asymptotic in terms of the "usual" basic functions; you'd get runtime bounds expressed in $A$ itself.

That does not mean that there is no faster algorithm; it would not contradict the growth of $A(n)$ per se. Depending on your computational and cost model, you can compute huge numbers with little cost.

### Are all primitive-recursive functions in $O(A)$?

Yes. That is (a consequence of) how we show that $A$ is not primitive recursive.

Note that here we are back to comparing values of the functions again; no mention of "time complexity" is being made.

### Can all primitive-recursive functions be computed in time $O(T\_A(n))$?

Not knowing $\Theta(T\_A)$, I do not have an answer to this question.
> 7 votes

# Answer
On the phone, so forgive brevity, however, I think you're looking for the concept of tetration and the arrow notation.

With those concepts in hand, I think runtime complexity of Ackermann function ($A~a~b$), as defined in Structure and Interpretation of Computer Programs book, has the time complexity of $O (n (↑))$ where $n(↑)$ means $n$ number of arrows and $n = a - 2$. $(A~1~x)$ will take $x$ steps. $(A~2~x)$ will take $2x$ steps, $(A~3~x)$ will take $2↑x$ or $2^x$ steps. $(A~4~x)$ will take $2↑↑x$ steps, and so on.

I'm not certain this is exactly right, but this is the neighborhood. I'm just wrapping my head arround arrow notation in this context.

So, regarding whether Ackermann function (as implemented in SICP) can be used as an upper bound on some other algorithm, I think can be reduced to the question if primitive recursive algorithms are upper bounded by $O(n(↑))$
> 1 votes

---
Tags: complexity-theory, time-complexity, primitive-recursion
---


# Question
Title: Why is it that O(N + P) where P < N/2 reduces to O(N)?
My book says that

> If $P \< N/2$ then we know that N is the dominant term so we an drop the $O(P )$."

If it was $O(N + P)$ where $P \> N/2$ what would it reduce to?

# Answer
In the Big-O notation, constant factors are irrelevant.

Then if $N\>P$, $O(N+P)$ reduces to $O(N)$, by swapping $N$ and $P$ we have that if $P\>N$, $O(N+P)$ reduces to $O(P)$.
> 3 votes

# Answer
$f = O(N+P)$
if $P\<N/2$ , $f = O(P+N)$ implies $f = O(N+N/2)$
$O(N+N/2) = O(N)$
$f=O(N)$
if $P\>N/2$ then same reduction for $f=O(P)$
> 0 votes

---
Tags: asymptotics
---


# Question
Title: Computation complexity of an exponential function
How we compute the computation complexity of an exponential function like $a^x$ where $a,x \in \mathbb{Z}$ with $|a|=l$ bits and $|x|=m$ bits? Can anyone please explain using big notation?

# Answer
The result has roughly $l\cdot x=l\cdot 2^m$ bits. Hence $\Omega(l\cdot 2^m)$ is a lower bound both for the time complexity and thus for the running time of every specific algorithm.

On the other hand, let's look at one specific algorithm. The exponentiation can be done with $\Theta(m)$ multiplications, the $i$-th of which dealing with numbers of $\Theta(l\cdot 2^i)$ bits. Multiplication of $n$ bit numbers can be done in $\Theta(n\cdot\log n)$ time. This gives a total of

$\Theta\left(\sum\_{1\leq i\leq m}l\cdot 2^i\cdot\log(l\cdot 2^i)\right)$

$=\Theta\left(l\cdot\log l\cdot\sum\_{1\leq i\leq m}2^i + l\cdot\sum\_{1\leq i\leq m}2^i\cdot i\right)$

$=\Theta\left(l\cdot\log l\cdot 2^m+l\cdot m\cdot 2^m\right)$

$=\Theta(l\cdot(\log l+m)\cdot2^m)$

Here we have a matching upper and lower bound for the running time of the algorithm. On the other hand, it is just one algorithm, so for the time complexity all it gives us is an upper bound $O(l\cdot(\log l+m)\cdot 2^m)$. Observe that it does not match the lower bound from above.
> 1 votes

---
Tags: complexity-theory, time-complexity
---


# Question
Title: Algebraic (spectral) algorithms for the minimum spanning tree problem
Are there any algorithms that use the **spectral** properties of a graph to solve the minimum spanning tree problem?

To clarify further what I have in mind, starting with the Laplacian matrix I want to algebraically arrive at the required set of edges. This is opposed to Prim's or Kruskal's algorithm where the result is obtained by operating on the edges/vertices sets directly.

# Answer
In short: no, not that I know of and I would be surprised if they exist. For something longer, read on:

---

I don't think the spectrum of a graph can be of much use in finding an MST. The main reason is this: weights of a graph aren't part of the spectrum of a graph! An MST only makes sense on a weighted graph.

The only thing I see we could try, if all weights are integral, 'unfold' the graph such that all weights are unit-weights (so an edge of weight $32$ becomes $32$ edges and $31$ nodes in them) and mark the original nodes and make a min-cost tree that spans the original edges. After this transformation, the spectrum *might* contain all relevant info, but this transformation step makes our new graph simply horribly large, so any algorithm based on this will have an awful running time. This is simply a bad idea.

I've never heard of a useful way to 'attach' weights to edges in the adjacency matrix and connect them to the spectral properties, either. It doesn't seem likely to work, although proving a vague method won't work is of course impossible.

---

Of course, the fact that spectral properties likely aren't useful doesn't mean algebraic methods in general won't work. What is important is that you don't leave the edge weights behind. However, most other algebraic methods are used for exponential time algorithms and I'm not aware anyone has constructed something algebraic for MST.
> 3 votes

---
Tags: algorithms, graphs, minimum-spanning-tree
---


# Question
Title: How can blank be written on the tape if it is not part of input alphabet?
I have read that input alphabet of Turing machine is subset of tape symbols because in input alphabet we don't allow blank symbol. But when ever there is a transition to final state the transition as (Blank,Blank,R/L) (First parameter here is input,second is what machine will write on tape,third is direction).It means whenever we have processed input,we will read Blank and replace Blank by Blank and goto final state.But how can blank be written on the tape if it is not part of input alphabet?

With this knowledge I am trying to answer the following statement

**"It is decidable that Turing machine will print some non blank character "**.

Because Turing machine will always write something on the tape so it should be decidable. But is it possible that there are only two states and there is only one transition as "(Blank,Blank,R/L)"?

# Answer
The formal definition of a turing machine is a 7-tuple $(Q, \Sigma, \Gamma, \delta, q\_0, q\_{\text{accept}}, q\_{\text{reject}})$, where:

* $Q$ is a finite set of states.
* $\Sigma$ is a finite set of input symbols (input alphabet).
    + $\Sigma$ does not contain the blank symbol ($\sqcup$).
* $\Gamma$ is a finite set of tape symbols (tape alphabet).
* $\sqcup \in \Gamma$ and $ \Sigma \subseteq \Gamma$.
* $\delta : Q^\prime \times \Gamma \rightarrow Q \times \Gamma \times \\{L,R\\} $ is the transition function.
    + $Q^\prime = Q - \\{q\_{\text{accept}}, q\_{\text{reject}}\\}$
* $q\_0 \in Q$ is the start state.
* $q\_{\text{accept}} \in Q$ is the accept state.
* $q\_{\text{reject}} \in Q$ is the reject state.

The part you want to pay attention to is the definition of the transition function:

> $\delta : Q^\prime \times \Gamma \rightarrow Q \times \Gamma \times \\{L,R\\} $

Note that the transition function accepts inputs that are of the tape alphabet, and writes output that is also of the tape alphabet.

The turing machine is decidable only if it recognizes some language L and and halts for every input.
> 4 votes

# Answer
You asked two questions. The usual rule is to ask one question post, so I will answer the first.

The head can write any symbol in the tape alphabet. It is not restricted to the input alphabet.

The input alphabet is the symbols that can appear in the input (which is initially placed on the tape). That has nothing to do with what the Turing machine can write to the tape during its operation.
> 3 votes

---
Tags: turing-machines, computation-models
---


title: Calculate the Time complexity

text:
# Question
Title: Calculate the Time complexity
$T(n)=\sqrt{2T(n-1)}$ what will be the time complexity if $T(n)$ is given as this? I tried substitution but no result was reached.

# Answer
> 1 votes
The answer depends on the initial value. For example, if $T(0) = 2$ then you can prove by induction that $T(n) = 2$ for all $n$. More generally, let $S(n) = T(n)/2$. Then $$ S(n) = \frac{T(n)}{2} = \frac{\sqrt{2T(n-1)}}{2} = \sqrt{\frac{T(n-1)}{2}} = \sqrt{S(n-1)}. $$ Simple induction now shows that $S(n) = \sqrt\[2^n\]{S(0)}$, and so $$ T(n) = 2 \sqrt\[2^n\]{\frac{T(0)}{2}}. $$ In particular, this shows that $T(n) \to 2$.

We can estimate the speed of convergence using the estimate $$ \sqrt\[2^n\]{x} = \exp \frac{\log x}{2^n} = 1 + O\left(\frac{\log x}{2^n}\right). $$ This shows that $$ T(n) = 2 + O(2^{-n}). $$

# Answer
> 0 votes
With substitution, we will get $T(n) = \sqrt{2\sqrt{2\sqrt{\cdots\sqrt{2}}}}$ with length $n$. Now, suppose $n$ goes to $\infty $, we will have $A = \sqrt{2A}$. Therefore, $A^2-2A = 0$ and $A = 2$. Hence, $T(n)$ would be constant as $T(n)$ is increasing. And we can write $T(n) =\Theta(1)$.

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Minimum path cover--- Disjointed paths with minimum total number of edges
Let $T=(\mathcal{V},\mathcal{E})$ be an udirected acyclic graph and $|\mathcal{V}|=n$. Let $\mathcal{V'}$ be $\mathcal{V'}\subset \mathcal{V}$ where $|\mathcal{V'}|=2m\leq n$. There are $2m \choose 2$ pairs of nodes in the set $\mathcal{V'}$. For each pair of nodes $(w,w')$ in the set $\mathcal{V'}$, there is a unique path form $w$ to $w'$ lets call it $\text{path}(w,w')$ and it contains all the edges in the path of $w,w'$. I would like to find a collection of pairs of nodes of $\mathcal{V'}$, where each node of $\mathcal{V'}$ appears in one pair exactly, thus we have $m$ pairs in total in the final desired collection. Lets call that collection of pairs $F(\mathcal{V'})$, also, $F(\mathcal{V'})$ should be found such that the total number of edges in the paths $\text{path}(w,w')$ is minimum, where $(w,w')\in F(\mathcal{V'}):$$$\min\_{F(\mathcal{V'})} \sum\_{(w,w')\in F(\mathcal{V'})} |\text{path}(w,w')|. $$ Notice that a necessary condition for the choice of pairs $F(\mathcal{V'})$ is that the paths should be disjointed (have no common edges), otherwise we have a total number of edges greater than the minimum possible.

I would like to know what the algorithm is that finds $F(\mathcal{V'})$ in polynomial time. Is this related to the Hamiltonian cycle problem? My graph is acyclic which should help to get a polynomial time algorithm. \*By disjointed paths I mean paths with no common edges, they may have common vertices. \**By minimum path cover I mean the total number of edges in the collection of paths is minimum since the number of paths is always chosen to be $m$.

# Answer
# A Trivial Algorithm

You can compute the lengths of all-pair shortest paths among $\mathcal{V}'$, and solve a minimum perfect matching in a complete graph on $\mathcal{V}'$ where the weight of an edge $(u,v)$ is the length of the shortest path from $u$ to $v$.

# A Smarter Algorithm

Consider the connected component containing $\mathcal{V}'$, it must be a tree.

At each step we move the deepest nodes in $\mathcal{V}'$ to their fathers. If two nodes move to the same node, we decide to match them and do not consider them any more in following steps. If more than two nodes move to the same node, repeatedly match arbitrary two of them until no more than one node is left.

This algorithm runs in $O(|\mathcal{E}|)$.
> 3 votes

---
Tags: algorithms, graphs, optimization
---


# Question
Title: The Entropy of the phrase "Eile Mit Weile"
I want to calculate the Entropy of the phrase "Eile mit Weile". I found the probability of each letter as the following

$$P(e)=\frac{4}{12}$$ $$P(i)=\frac{3}{12}$$ $$P(l)=\frac{2}{12}$$ $$P(m)=\frac{1}{12}$$ $$P(t)=\frac{1}{12}$$ $$P(w)=\frac{1}{12}$$

Then I used the formula for entropy $$H(p\_1,...,p\_k)=-\sum\_{i=1}^{k}p\_i\log\_2(p\_i)$$ $$H(p\_1,...,p\_k)=-(\frac{4}{12}\log\_2(\frac{4}{12})+\frac{3}{12}\log\_2(\frac{3}{12})+\frac{2}{12}\log\_2(\frac{2}{12})+\frac{1}{12}\log\_2(\frac{1}{12})+\frac{1}{12}\log\_2(\frac{1}{12})+\frac{1}{12}\log\_2(\frac{1}{12}))≈2.355388542 \ Bits$$ But the correct answer is $1.63263$ Bits. I've made a mistake somewhere but can't figure out what I did wrong.

# Answer
The two answers agree, with the following change: it's 1.63263 *nats*, not *bits*. That is, the value 1.63263 is calculated using the natural logarithm.
> 10 votes

---
Tags: algorithms, complexity-theory, optimization, information-theory, entropy
---


# Question
Title: How can I prove that $T(n)=\sqrt{n}T(\sqrt{n})+n$ grows as $\Theta(n\log \log{n})$?
How can I prove that if $T(n) = \sqrt{n}T(\sqrt{n}) + n$ then $T(n) = \Theta(n\log\log n)$?

I tried to define $T(n)$ by $G(n)$, prove about $G(n)$, and then to return to $T(n)$, but it's not working..

# Answer
> 2 votes
You can use repeated substitution: $$ \begin{align\*} T(n) &= n + \sqrt{n}T(\sqrt{n}) \\ &= n + n + n^{3/4} T(n^{1/4}) \\ &= n + n + n + n^{7/8} T(n^{1/8}) \\ &= \cdots \end{align\*} $$ You reach the base case after after $\ell$ iterations when $n^{1/2^\ell} = 2$ (say), whose solution is $\ell = \log\_2\log\_2 n$. Assuming for simplicity that $T(2) = 0$, we get $T(n) = n\log\_2 \log\_2 n$.

---
Tags: complexity-theory, recursion
---


title: Finding Big O of 1/n + 1/n+2 ... 1/n'

text:
# Question
Title: Finding Big O of 1/n + 1/n+2 ... 1/n'
The number of computations of an algorithm is $n'm\sum\_{x=0}^{n'-m} 1/(m+x)$. What is the complexity of the algorithm ?

Thanx for help.

# Answer
> 0 votes
The series $\sum\_{m=1}^\infty 1/m$ is known as the harmonic series. Its partial sums are the harmonic numbers $H\_n := \sum\_{m=1}^n 1/m$. It is known that $H\_n = \ln n + O(1)$. In fact, there are much more accurate asymptotic estimates, such as $H\_n = \ln n + \gamma + O(1/n)$, where $\gamma$ is Euler's constant.

In your case, you have a more general type of sum of the form $$ \sum\_{m=a}^b \frac{1}{m} = H\_b - H\_{a-1} = \ln \frac{b}{a} + O\left(\frac{1}{a}\right). $$

# Answer
> 1 votes
Selah, instead of asking for more references and definitions, you can just use the fact that for the n values n ≤ k \< 2n, we have $1/{2n} ≤ 1/k ≤ 1/n$. So the sum of $1/k$ for n ≤ k \< 2n is between 1/2 and 1.

Not nearly as nice as Yuval's result, but it should be more than good enough to solve your problem.

---
Tags: asymptotics
---


# Question
Title: Big O of an algorithm that relies on convergence
I'm wondering if its possible to express the time complexity of an algorithm that relies on convergence using Big $O$ notation.

Is it fair to say that we can't reason about an algorithm's scalability based on input size if we also have to rely on convergence - unless there's some facet of the algorithm's manner of convergence whereby we can mathematically prove that the number of iterations to reach convergence is related to input size (essentially showing that convergence of the algorithm is a function of the input size $N$)?

For instance, I'm using an algorithm called TextRank, which is based on PageRank - except each vertex is a sentence instead of a webpage and each edge represents the similarity between two sentences (or vertices). The algorithm iterates over the vertices in the graph, carrying out a computation to calculate the score of each vertex for an indefinite amount of iterations until the difference between scores from one iteration to the next is below a threshold (we've reached convergence).

I'm thinking that we cannot reason that an input of size N sentences will always converge in the same manner. Two different bodies of text with say $30$ ($N=30$) sentences, could theoretically require a noticeably different number of iterations over the graph to converge.

Is it possible to represent the limiting behaviour of the function in a polynomial expression due to reliance on convergence?

# Answer
> 1 votes
Usually we prove something about the rate of convergence. For instance, we might prove that after $k$ iterations, the relative error is $1/2^k$. Thus if each iteration takes (say) $O(n^2)$ time, and we want an answer that has relative error at most $\epsilon$, then we have found an algorithm whose running time is $O(n^2 \lg (1/\epsilon))$. Notice how the running time now depends both on the input size and on the desired accuracy of the answer.

For instance, PageRank uses power iteration. As you can see from the Wikipedia page on power iteration, it is possible to prove results about its rate of convergence (as a function of the first two largest eigenvalues $\lambda\_1,\lambda\_2$).

---
Tags: algorithms, algorithm-analysis, asymptotics
---


# Question
Title: Does the circuit value problem require only log space in alternating Turing machines
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.

# Answer
It is a classical result that ALOGSPACE=P. You can find a proof in lecture notes of Madhu Sudan. Both the circuit value problem and the monotone circuit value problem are P-complete, and in particular in P, and so can be solved in alternating logarithmic space.

One thing which might be confusing you is that we only measure space on *work tapes*. Space on the input tape is for free, though this comes at a price: you are not allowed to modify it.
> 3 votes

---
Tags: complexity-theory, turing-machines, space-complexity
---


# Question
Title: Can a computable function converge to an uncomputable number?
Does there exist a computable function $f:\mathbb{N}\rightarrow \mathbb{Q}$ such that:

* For all $t\in\mathbb{N}: 0\le f(t) \< X$
* $\lim\limits\_{t\rightarrow\infty} f(t) = X$

Where $X$ is an uncomputable real number.

The only reference to this question I have found was the answer to this question: https://math.stackexchange.com/a/1052579/168764, where the function seems that it would hold, but I have no idea how to prove that the limit of this function is an uncomputable real number.

# Answer
> 31 votes
Consider the real number encoding of the (almost) halting problem, i.e. $0.r\_1r\_2...$ where $r\_i=1$ if the i'th Turing machine (relative to the lexicographic ordering) halts on the empty input, and $r\_i=0$ otherwise. Let us denote this number by $R$.

Now, consider the machine $M$ which on input $n$ simulates all Turing machines of length $\< n$ on the empty input for $n$ steps, and returns $0.\hat{r\_1}...\hat{r\_{2^n-1}}$ where $\hat{r\_i}=1$ if the $i$'th Turing machine halts on the empty input in less than $n$ steps, and $\hat{r\_i}=0$ otherwise. Clearly for all $n$ it holds that $M(n)\< R$, and it is not too hard to show that $\\{M(n)\\}\_{n\in\mathbb{N}}$ converges to $R$. The key point is that rate of convergence is not computable, meaning that given $\epsilon$, you cannot compute the index such that beyond it the series is $\epsilon$-close to $R$.

---
Tags: computability
---


# Question
Title: Can we load the data on the bus on multiple registers at the same time?
So in the book that I'm reading it says at a time only the data of one register can be on the data bus and only one register can load the data. the first part i get but what about the second part?

why can't we just turn on the load parameter for both of the registers at the same time?

I'm studying for computer architecture and this is the bus that I'm talking about:

Computer

so can we transfer the data from one register to multiple registers with 1 clock?

like transfer the content of AC to PC and DR with one clock?(turn on the load parameters for both of DR and PC at the same time? why can't we do that?)

# Answer
If we somehow turned on multiple load signals at the same time, in theory it should work to transfer the same value to multiple registers in the same cycle.

(Depending on the hardware design technology, there may be some power considerations, such as amplification of the data bus lines as they go into the various registers, since more gates are consuming the data bus lines concurrently; it is possible that such is required anyway, though.)

However, the diagram you're showing doesn't reveal the answer. Here's the issue: it doesn't show how the load signal is generated and delivered to the various registers. So, we can't really tell.

If the load signal is driven by an ordinary MUX (under control of say, instruction decode, e.g. some field of the IR), then by design, it would only ever turn one line on at a time, meaning the answer is no.

But an alternate implementation could turn on multiple registers' load signal simultaneously, so in that case, then yes.

See also Register File, regarding "ports", in how processors with general purpose registers deal with the need to read and write them concurrently.
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: How can a 64KiB computer do the same task as a modern computer?
I took an extremely interesting intro to CE course, learning about transistors/memory/logic gates up to LC-3 assembly. Something that was really interesting to me was learning about how a processor's frequency is its speed, determined by the clock signal (if anyone can point to a link of how a clock cycle is made/works or explain, highly appreciated) but my main question is about his claim that any turing-complete computer can accomplish the task of another - performing the same binary operations, just in different amounts of time - that the processor doesn't matter. This depends on memory, though, right? A modern video game wouldn't be able to run on a 64 KiB computer, so I'm wondering if when the textbook and my prof make that claim, it's simply referring to the frequency of the clock cycle (and assuming unlimited/uncapped memory). Thanks!

# Answer
The key considerations are infinite memory and unlimited time. If those two considerations were met, then all modern computers are equivalent. Since no real computers have infinite memory, and no real humans can afford to wait forever for a calculation, that equivalence is more conceptual than real.
> 4 votes

# Answer
The concept of *Turing Complete* is purely about data manipulation rules (i.e. a computer's instruction set), not its memory capacity. A machine is said to be *Turing complete* or *computationally universal* if it can be used to *simulate* any Turing machine. A Turing machine is conceptual and has *infinite memory*. All *real* machines are necessarily constrained by actual memory.

Your question is answered directly in the Wikipedia entry on Turing Completeness in the section *Comparison with real machines*

The proposition put forward in the class/lecture you have attended is that both the LC-3 and a modern processor both have *instruction sets* capable of implementing a Turing Complete machine - what both lack however is the *infinite memory* and *infinite time*. Instruction sets and higher-level programming languages are often described as Turing Complete in this context.
> 3 votes

---
Tags: turing-completeness
---


# Question
Title: Could a standardized ternary system be more efficient than the binary system?
Could a standardized ternary (base-3) system be more efficient than the binary (base-2) system? Binary is efficient for processing using logic gates, but can be bulky when using for file storage or file transfer. I am interested in the feasibility of a ternary system both for file storage, file transfer, and computational processing.

The following three examples show an ASCII word converted to both binary and ternary, along with the length of the sequence:

**ASCII Example 1**: Hello

Binary: 0100100001100101011011000110110001101111 (40 characters)

Ternary: 210011101002200222 (18 characters)

**ASCII Example 2**: Test

Binary: 01010100011001010111001101110100 (32 characters)

Ternary: 220200002020100202 (18 characters)

**ASCII Example 3**: Cat

Binary: 010000110110000101110100 (24 characters)

Ternary: 22022100102101 (14 characters)

As denoted by the character count, the length of the ternary sequence can sometimes be less than half the length of the binary sequence. Having shorter sequences would be beneficial for file transfer, file storage, and computational processing speeds. On the surface this seems preferable, but perhaps there are disadvantages or implementation flaws which I am overlooking. The following contains additional observations (which may or may not be feasible), for implementation.

**File Storage**

Ternary would be highly beneficial for file storage but would require hardware changes. For example, manufacturers of flash memory storage devices such as flash drives or solid state drives would have to re-architect the transistors in order to store the representation of a 0, 1, or 2. If these transistors could maintain the same size dimensions as the current transistors that store the representation of a 0 or 1, the storage capacity has the potential to double.

**File Transfer (Focus on wireless transmission)**

File transfer speeds appear to have potential to increase with a ternary system. In the case of wireless transmissions, binary is generally preferred over analog due to its increased ability to maintain information integrity and is easier to distinguish when interference is present. The following diagram demonstrates this principle.

Image source: https://www.predig.com/whitepaper/reducing-signal-noise-practice

I imagine the implementation of ternary in wireless systems to appear like the following diagram (drawn quickly), having the peak and trough like a binary signal along with an ‘in-between’ to represent a 2. Having an ‘in-between’ might make the signal become less interference-tolerant than binary, which could be a disadvantage.

Thanks in advance for responses. Feel free to address unconsidered factors of why ternary may or may not be feasible and/or a beneficial alternative to the binary system.

**EDIT**: This question was flagged as a possible duplicate question. Keep in mind that an important aspect of this question is file transmission, which has been unaddressed in previous related ternary questions.

# Answer
Whether this is more efficient depends on the physical properties of the medium, not on any fundamental principle of computer science. And of course there's no reason to limit yourself to ternary systems; we can consider systems with $k$ levels, where $k$ is any integer with $k \ge 2$ (it doesn't have to be limited to $k=2$ or $k=3$).

For instance, Wifi apparently uses BSK (a binary system, $k=2$), QPSK (a quad-level system, $k=4$), 16-QAM (a 16-level system), or 64-QAM (a 64-level system). Cable TV apparently uses 64-QAM and 256-QAM, which is a modulation scheme that uses $k=64$ or $k=256$ different levels. Why? Because this is more efficient than using a binary ($k=2$) system. There are many other examples like this in the communications world.

On the other hand, digital circuits -- as typically used in a CPU -- seem to be most effective with two-level modulation (i.e., binary, $k=2$). Why? The physics are different.

So, yes, sometimes this is more efficient, and sometimes it is not. It all depends on the specific properties of the hardware you're working with. Those properties are a matter of electrical engineering and physics, rather than of computer science.

There's lots more on this subject at Ternary processing instead of Binary, Why Do Computers Use the Binary Number System (0,1)?, and Could computer architecture be reworked to support switching from binary to ternary, for example?, for starters.
> 6 votes

---
Tags: algorithms, computer-architecture, communication-protocols, storage, binary
---


# Question
Title: Meaning of "pushing x down" and "pulling x up" in database query handling
In this book there is a lot of mention of "pushing x down". For example:

> ### Pushing NOT operations down and eliminating them
>
> NOT operations need to be **pushed downwards** for correctness reasons. Attention has to be paid to the IS NOT NULL and IS NULL predicates. XXX complete set of rules go into some table
>
> ...
>
> Typical steps during this rewrite phase are unnesting nested queries, **pushing selections down**, and introducing index structures.
>
> ...
>
> When **pushing down projections**, we only apply them just before a pipeline breaker
>
> ...
>
> Logical query optimization turned out to be a little difficult: **pushing selections down** and reordering joins are mutually interdependent.
>
> ...
>
> In this section, we consider **pushing down (pulling up)** unary operators into (from) the arguments of binary operators. Thus, we are interested in equivalences of the form $f(e\_1 ◦ e\_2) ≡ f(e\_1) ◦ e\_2$ and $f(e\_1 ◦ e\_2) ≡ e\_1 ◦ f(e\_2)$.

From that last example I can vaguely see that e.g. $f(e\_1 ◦ e\_2) ≡ f(e\_1) ◦ e\_2$ there is a "moving out" of $e\_2$ from the equation, but I'm not sure what direction up/down and not sure what the meaning/purpose is in doing this. Wondering what exactly this means.

# Answer
> 3 votes
I would normally say "pushing inward"/"pulling outward", but "down"/"up" make sense if you are thinking in terms of syntax trees and, being a computer scientist, your trees grow downward.

In (classical) logic there are rules like De Morgan's rule which says $\neg(P\land Q)\equiv(\neg P)\lor(\neg Q)$ and many others that allow you to move negation either outward/upward toward the outermost connective (reading the equivalence from right to left), or inward/downward towards the leaves of the syntax tree (reading the equivalence left to right). If we actually draw out the syntax tree it will look like

```
    ¬             ∨
    |            / \
    ∧      ≡    ¬   ¬
   / \          |   |
  P   Q         P   Q

```

which illustrates the down/up movement. In general, we can use any available equivalences for any sort of expression to move operations around. In the case of negation, since we have $\neg\neg P\equiv P$ it is often desirable to try to move them toward each other. Systematically moving them towards the leaves, i.e. inward/downward, is one way to accomplish this. Often these types of cancellations are one of the goals of applying these equivalences. There are other concerns too. For example, if it is possible to remove duplicates before a join rather than after, that could be extremely advantageous.

> Logical query optimization turned out to be a little difficult: pushing selections down and reordering joins are mutually interdependent.

This just states that sometimes the available equivalences are not so simple, and an equivalence might simplify a selection at the cost of making a join more complicated or vice versa and so the equivalences can't just be blindly applied in a fixed direction (at least not if you want a good result).

---
Tags: database-theory
---


# Question
Title: sub-optimal but fast partition generation
I have a set of N integers that I want to partition into m subsets. I want these subsets to be well-balanced wrt some criterion say that minimize the max difference between the size of all subsets. But I am not really interested in **THE** optimal solution. I am interested in a **FAST** algorithm that generates some ***good*** partition wrt the criterion.

Let us say a set is \[1,23,12,2456,234,16,188,22\] and needs to be divided 3-ways. When partitioning we try to minimize the max difference between the size of all subsets.

One quick partition that can be generated is {\[1,23,12\],\[2456,234,16\],\[188,22\]}. This may not be optimal or maybe it is. It does not matter in this context.

We could have an algorithm: put 1st element in 1st set, 2nd element in 2nd set, all others in 3rd set. This would give us: {\[1\],\[23\],\[2456,234,16,188,22\]}. One can see this algo will be very fast but wrt to our criterion, it does not necessarily give a good-looking solution.

Can someone suggest existing work in this direction?

# Answer
The following is directly taken from pages 358-360 of The Nature of Computation by Moore and Mertens and I think addresses your problem directly.

> Imagine that you run a computer center with $p$ identical machines, or a parallel computer with $p$ processors, for some constant $p$. You are given $n$ jobs with running times $t\_1,t\_2,...,t\_n$. Your task is to find a schedule - a function $f:\\{1,...,n\\}\rightarrow\\{1,...,p\\}$ that assigns the $j$th job to the $f(j)$th machine.
> The *load* on the $j$th machine is the total time it takes to run the jobs assigned to it, $$ L\_j = \sum\_{i:f(i)=j} t\_i\\,. $$ Since the machines run in parallel, the time it takes us to finish all the jobs is the maximum load on any machine, $$ M=\max\_{i\leq j\leq p} L\_j\\,. $$ We call this time the *makespan*, and your goal is to minimize it. This gives the following problem:
>
> > **Makespan**
> > Input: A set of $n$ running times $t\_i\geq0,\\,i=1,...,n$
> > Output: A function $f: \\{1,...,n\\}\rightarrow\\{1,...,p\\}$ that minimizes the makespan $$M = \max\_{1 \leq j \leq p} \sum\_{i:f(i)=j}t\_i$$
>
> **Exercise 9.3** Reduce Integer Partitioning to the case of Makespan where $p=2$.
>
> There is, however, a simple algorithm that comes with a quality guarantee. The idea is to divide tasks into two groups, "large" and "small", and schedule the large tasks first. Let $T\_{\text{tot}}=\sum\_{j=1}^n t\_j$ be the total running time of all the tasks. We choose some constant $\eta \> 0$, say $\eta = 1/10$. We call the $j$th task *large* if its running time is at least a fraction $\eta$ of the total, $t\_j \geq \eta\\,T\_{\text{tot}}$, and *small* if $t\_j \< \eta\\,T\_{\text{tot}}$.
> The algorithm then proceeds in two phases:
>
> 1. Find a schedule that minimizes the makespan of the large tasks, using exhaustive search.
> 2. Distribute the small tasks by giving each one to the machine with the smallest load so far, regardless of that tasks's running time.
>
> How long does this algorithm take? Since there are at most $1/\eta$ large tasks, there are $p^{1/\eta}$ ways to schedule them. Since $p$ and $\eta$ are constants, this gives a constant number of possible schedules to explore in phase 1, and we can check all of them in polynomial time using exhaustive search. Phase 2 clearly runs in polynomial time as well.
> Now let $M$ denote the makespan of the schedule produced by this algorithm. How does it compare to $M\_{\text{opt}}$? Let $M\_{\text{large}}$ denote the maximum load of a machine after phase 1, i.e., the minimum makespan of the large tasks. Since adding the small tasks can only increase the makespan, we have $M\_{\text{large}} \leq M\_{\text{opt}}$. If the algorithm manages to fit all the small tasks in phase 2 without increasing the makespan, putting them on machines with load less than $M\_{\text{large}}$, then $M = M\_{\text{large}}$. But since $M\_{\text{opt}} \leq M$, in this case $M = M\_{\text{opt}}$ and the algorithm performs perfectly.
> So, we will focus on the harder case where the makespan increases in phase 2, so that $M \> M\_{\text{large}}$ and our schedule for the small tasks might not be optimal. Let $L\_j$ denote the load of machine $j$ after phase 2. Without loss of generality, we can assume that $L\_1 \geq L\_2 \geq ... \geq L\_p$. Since $L\_1 = M \> M\_{\text{large}}$, we know that at least one small task was added to machine 1.
> Let $t$ be the running time of the last such task. Since our strategy greedily assigns small tasks to the machines with the smallest load, the load of machine 1 must have been less than or equal to the others just before this task was added. This means that, for all $2 \leq j \leq p$, $$ M-t \leq L\_j \leq M\\,. $$ Since $t\<\eta\\,T\_{\text{tot}}$, we also have $$ T\_{\text{tot}} = M + \sum\_{j=2}^p L\_j \geq pM-(p-1)t\geq pM-\eta(p-1)T\_{\text{tot}}\\,. $$ Rearranging this gives an upper bound on M, $$ M \leq \frac{T\_{\text{tot}}}{p}(1+\eta(p-1))\\,. $$ On the other hand, the best schedule we could hope for would be perfectly balanced, keeping all the machines busy all the time. Thus the optimum makespan is bounded below by $$ M\_{\text{opt}}\geq\frac{T\_{\text{tot}}}{p}\\,. $$ Combining this lower bound on $M\_{\text{opt}}$ with the upper bound we have on $M$ gives an approximation ratio $$ \rho \leq \frac{M}{M\_{\text{opt}}} \leq 1+\eta(p-1)\\,. $$ By setting $\eta = \epsilon/(p-1)$, we can approximate $M\_{\text{opt}}$ within a factor of $\rho = 1+\epsilon$ for arbitrarily small $\epsilon \> 0$. In fact, we can define an algorithm that takes both the problem instance and $\epsilon$ as inputs, and returns a $(1+\epsilon)$-approximation. For each fixed $\epsilon$, this algorithm runs in polynomial time. Such an algorithm is called a *polynomial-time approximation scheme* or PTAS.
> On the face of it, a PTAS seems to be sufficient for all practical purposes. It allows us to find solutions within 1%, 0.1%, 0.01% ... of the optimum, each in polynomial time. However, improving the quality of the approximation comes at a cost, since the running time increases as $\epsilon$ decreases. Our PTAS for Makespan, for example, has to explore $p^{1/\eta} = p^{(p-1)/\epsilon}$ possible schedules in phase 1, so its running time grows exponentially as a function of $1/\epsilon$. Even for $p=2$ and $\epsilon = 0.01$, this number is $2^{100}$ - hardly a constant that we can ignore.
> We would prefer an algorithm whose running time is polynomial both in $n$ and in $1/\epsilon$. Such an algorithm is called a *fully polynomial-time approximation scheme*, or FPTAS for short. There is, in fact, an FPTAS for Makespan, which we will not describe here.

The end of chapter notes further recommend the "outstanding" book Approximation Algorithms by Vazirani, from which this algorithm is apparently taken.
> 4 votes

---
Tags: algorithms, combinatorics, discrete-mathematics, partitions, integer-partitions
---


# Question
Title: Interval scheduling problem with priorities
I have a problem that is similar to the interval scheduling algorithm but it involves priorities. My data sets consist of the following data:

* **Cars** with the start and end time of parking, along with their one or more attributes (e.g. electric vehicle, motorcycle, handicapped).
* **Parking spots** along with zero or more attributes and lot number.
* **Attributes** with their priorities. For example if the property `handicapped` is given a value of 1, cars that have that attribute should be assigned a parking spot first. Attributes are *hard constraints*, the priorities of the attributes determine the order of assignment.

There is no overnight parking so I have divided the data into buckets of days. Start and end times are in increments of 5 minutes (not sure if this is important).

To be considered a valid assignment, a car's attributes must be a subset of the attributes for the assigned spot. See examples below.

### Objectives

This problem comes from overhauling an existing algorithm, which after observing how users interact with the system, it could definitely use improvement.

My first step is to get something going that can **produce one or more possible solutions that meet all of the provided attributes**. For example, a limo cannot be assigned to a motorcycle spot. There may not be a complete solution given the inputs, if there are 5 electric vehicles but only 4 spots, the algorithm should still try to assign 4 of them (the 4 that have the highest priority).

Given multiple solutions, the "best" solution would minimize the number of open lots at any given time (ideally all the cars parked in the same lot). Even if it is a small block of time in the middle of the day, the lot can still be closed to minimize the cost of security guards.

### Example input/output

**Set 1**

* Attributes: \[bus: -1; electric: -2; handicapped: -2\]
* Cars: \[C1: bus, electric; C2: handicapped, C3: electric\]
* Spots: \[P1: bus, electric; P2: bus, electric; P3: electric, handicapped\]
* Valid assignments: **`[C1-P1, C2-P3, C3-P2]`** and **`[C1-P2, C2-P3, C3-P1]`**

**Set 2**

* Attributes: \[bus: -1; electric: -2; handicapped: -2\]
* Cars: \[C1: bus, handicapped; C2: bus, C3: electric\]
* Spots: \[P1: bus, handicapped, electric; P2: bus, electric; P3: handicapped\]
* Valid assignments: **`[C1-P1, C2-P2, C3-null]`**

Spot 1 is the only spot that can accommodate car 1. Both cars 2 and 3 can take spot 2 but priority is given to the bus, leaving car 3 unassigned.

**Set 3**

* Attributes: \[bus: -1; electric: -2; handicapped: -2\]
* Cars: \[C1: bus, electric; C2: electric, C3: bus\]
* Spots: \[P1: bus, electric; P2: electric; P3: electric, handicapped\]
* Valid assignments: **`[C1-P1, C2-P2, C3-null]`** or **`[C1-P1, C2-P3, C3-null]`**

There are two buses but only one bus parking spot. Since C1 has a greater priority sum, it is assigned to the available spot even though C3 could have taken it.

## Verifying a solution

1. For each assigned car *A*, if any, verify the assigned spot (P) that it has been assigned to has all of its attributes. In other words, Attributes(A) is a subset of Attributes(P).
2. For each unassigned car *B*, let X be the set of spots in the input data that meet the car's attribute criteria.
    * If one or more spots in X is unassigned, abort these steps and mark the solution as invalid
    * If one or more cars assigned to spots in X has a greater maximum priority than MaxPriority(B), abort these steps and mark the solution as invalid
    * Let Z be the subset of cars assigned to spots in X where the maximum priority of the car = MaxPriority(B). If one or more cars in Z has a greater priority sum than SumPriority(B), abort these steps and mark the solution as invalid

## What I have tried

1. Find all the valid parking spots for each car.
2. Sort each parking spot list in ascending order of the sum of priorities for the parking spot.
3. Sort the list of cars in descending order of sum of priorities.
4. Attempt to assign each car in order of the sorted parking spots. If the spot is taken for that time then try the next one and so on.

I am hoping to make this more efficient by taking into account the interval for each car, as it currently isn't being taken into account when sorting.

I stumbled upon Google Optimization Tools and it looks similar to the nurse scheduling problem but with more constraints. A key difference is that each shift in the NSP is defined whereas the intervals in my problem can partially overlap.

## Questions

1. How can I model the problem?
2. Are tools like Google OR-Tools or pyschedule appropriate for solving this?

# Answer
> 0 votes
The problem is probably fairly hard. One approach is to formulate it as an instance of integer linear programming. Divide the time period into short time segments. Let $x\_{i,j,t}$ be a zero-or-one variable, with the intended meaning that car $i$ is assigned to parking spot $j$ at time segment $t$. Also let $y\_i$ be a zero-or-one variable, with the intended meaning that car $i$ is assigned a parking spot (somewhere). Then you can express each of your requirements as a set of linear inequalities on these $x$'s:

* If car $i$ needs a parking spot for the time window $t\_0..t\_1$, then add the constraint $\sum\_j x\_{i,j,t\_0}=y\_i$, to require that it is assigned exactly one slot if $y\_i$ says it should be. Here the sum is over all parking spots $j$ that are compatible with car $i$ (given their attributes).
* Also, add the constraint $x\_{i,j,t\_0} = x\_{i,j,t\_0+1} = \cdots = x\_{i,j,t\_1}$ for all $j$, to indicate that if car $i$ is assigned to parking spot $j$, then it should be there for its entire time window.
* To take into account that you can't have two cars parking in the same spot at the same time, add the constraint $\sum\_i x\_{i,j,t} \le 1$ for all $j,t$.
* To take into account the priorities, if cars $i,i'$ are both vying for a parking spot at the same time $t$, and if $i$ has higher priority than $i'$ for parking spot $j$, then add the constraint $x\_{i,j,t} \ge x\_{i',j,t}$. (Add this for all times $t$ in the intersection of their time windows.)

Finally, maximize the objective function $\sum\_i y\_i$. This is a system of linear inequalities, with a linear objective function, so it can be solved using an off-the-shelf integer linear programming (ILP) solver.

Keep in mind that solving ILP can take exponential time in the worst case, so on large problems, it's possible that the ILP solver might take a very long time. However, the hope is that if your problem is not too large, then an ILP solver might be able to find a good solution in a reasonable amount of time.

---
Tags: algorithms, optimization, scheduling, integer-programming
---


# Question
Title: Analysis of time complexity of travelling salesman problem
Recursive definition for travelling salesman problem can be written like this :-

`T(i,S)=min((i,j)+T(j,S-{j})) for all j belonging to S, when S is not equal to NULL`

`T(i,S)=(i,S) when S is equal to NULL`

Here, T(i,S) denotes the tour starting from `i` covering all vertices in Subset `S` and then travel back to `i`.

I built the recursive tree and calculated the subproblems at each level. For k elements, number of subproblems comes out to be :-

(n-1)+(n-1)(n-2)+(n-1)(n-2)(n-3)+.......+(n-1)(n-2)(n-3)......(n-k).

For k=4, number of subproblems at level 1,2 and 3 are 3,6 and 6 respectively.

I tried to solve it but couldn't find the actual solution but it can be seen clearly that the time complexity is factorial. Now, in the recursion tree there are repeated function calls at the last level which we use to improve our time complexity using dynamic programming. Now, half of the function calls at last level are repeated that would reduce the number of subproblems to :-

(n-1)+(n-1)(n-2)+(n-1)(n-2)(n-3)+.......+((n-1)(n-2)(n-3)......(n-k))/2.

But, I think the time complexity is still factorial. I read on various resources that time complexity of travelling salesman problem using dynamic programming is $O(n^2\*2^n)$ which is exponential.

Is there something wrong in my analysis? Can anyone prove how the time complexity comes out to be $O(n^2\*2^n)$ ?

# Answer
When solving TSP using dynamic programming you get something akin to the following:

```
TSP(graph, start, target) {
  if start == target {
    return 0;
  }

  min = infinity;
  for neighbor in neighbors(graph, start, target) {
    tour_length = TSP(remove(graph, start), neighbor, target)
                  + distance(graph, start, neighbor);
    if tour_length < min {
      min = tour_length;
    }
  }
  return min;
}

```

(neighbors only returns target as a viable neighbor if no other choice is available)

This algorithm recursively finds the shortest tour starting from each neighbor and returns the minimum of those. If you do all this with dynamic programming you can calculate the amount of work you're doing like so:
There are $n$ possible start vertices and $2^n$ possible subgraphs. So this function will be called on at most $n\cdot2^n$ distinct arguments (the target never changes). Each call performs at most $O(n)$ work (there are at most $n$ neighbors). Hence the total work you're doing is $O(n^2\\,2^n)$.
> 2 votes

---
Tags: algorithms, graphs, time-complexity
---


# Question
Title: Why is the number of digits (bits) in the binary representation of a positive integer $n$ is the integral part of $1 + \log_2 n$?
I've stumbled on this definition on Wikipedia, and I can't figure out why.

I could probably start the demonstration by saying that, with $n$ bits, you can create $2^n$ possible different numbers, so $2^n=x$. If I rewrite the expression with logarithms, I find $\log\_2x = n$, so the *base-2-log of the total number of possible combinations of 0 and 1* is $x$.

And I'm stuck here. I'm probably seeing this from the wrong angle. Also, I wonder what is that $+1$ for?

Sorry if it's a dumb question, but the only way I can memorize a formula is to give a meaning to its numbers.

# Answer
> 7 votes
If you have $n$ bits available you can represent the numbers $0$ to $2^n-1$ in binary. Therefore, if you want to represent a number $x$ in binary, you need a number of bits $n$ that is large enough so that

$$ \begin{split} 2^n - 1 & \geq x\\ n & \geq \log\_2(x+1)\\,. \end{split} $$

Now there are two cases for $\log\_2(x+1)$:

* It is an integer. Then $\log\_2(x)$ won't be. It'll be slightly less. So $\lfloor\log\_2(x)\rfloor + 1$ will yield the same value. (The exception where $x=1$ can be checked separately.)
* It isn't an integer. In this case $\lfloor\log\_2(x)\rfloor + 1$ yields the next largest integer just as $\lfloor\log\_2(x+1)\rfloor + 1$ would.

In either case, because $n$ is always an integer we can write

$$ n \geq \lfloor\log\_2(x)\rfloor + 1\\,. $$

# Answer
> 1 votes
Here is a more general results:

> The base $b$ expansion of the positive integer $n$ uses $\lfloor \log\_b n \rfloor + 1$ digits.

To prove this, note that the minimal integer whose base $b$ expansion requires $d$ digits is $b^{d-1}$, and the maximal integer whose base $b$ expansion required $d$ digits is $b^d-1$.

Let us compare this to the set of values satisfying $\lfloor \log\_b n \rfloor + 1 = d$, or rather $\lfloor \log\_b n \rfloor = d-1$. These are the values for which $d-1 \leq \log\_b n \< d$, or equivalently, $b^{d-1} \leq n \< b^d$. This is exactly the same condition as above.

---
Tags: combinatorics, arithmetic
---


# Question
Title: For multi-tape Turing machines, can we assume that each tape can be in its own state independently of the other tapes?
When we consider multi-tape Turing machines, we can assume that each tape is accessed with a separate head and each head can move independently of the other heads. But can we assume that each tape can be in its own state independently of the other tapes (for example, tape 1 in state A, tape 2 in state F, tape 3 in state X simultaneously)?

Then, for example, the table of instructions for some three-tape two-symbol ("0" and "1") machine can look like this:

```
    | 000         | 001         | ...
----------------------------------
AAA | 011/BXZ/LRL | 010/XYB/RRR | ...
----------------------------------
AAB | 001/TSH/LLR | 110/AET/LLL | ...
----------------------------------
...

```

where the first cell of the table can be interpreted as follows: if the first tape is in state A, the first head is over the cell with symbol 0, the second tape is in state A, the second head is over the cell with symbol 0, the third tape is in state A, the third head is over the cell with symbol 0, then the first head writes "0" instead of "0", then the first tape goes into state B, then the first head moves to the left, then the second head writes "1" instead of "0", then the second tape goes into state X, then the second head moves to the right, then the third head writes "1" instead of "0", then the third tape goes into state Z, then the third head moves to the left.

# Answer
Yes. You can equivalently transform such multi-state multi-tape Turing machine to a normal multi-tape Turing machine where each state in the new Turing machine represents a combination of states in the multi-state multi-tape Turing machine.

For your example, you can encode state "AAA" into state 1, state "AAB" into state 2, and so on (so there are in total $26^3$ states). Now it becomes a normal multi-tape Turing machine.
> 2 votes

# Answer
A Turing machine has just one state, even if it has multiple tapes. If you give each tape a separate state, it’s easy to forget that the action of each tape head can depend on the global state and on the character under every head, which is crucial, because it is the only way the tapes can communicate with each other. A multi-tape TM is a single computer with multiple I/O devices, not multiple computers each with one I/O device.

xskxzr’s answer shows that one state per tape doesn’t actually change the computational power of Turing machines. But it’s important to note that this requires the actions of all tape heads to be allowed to depend on every tape’s state and every tape’s current character. Thinking about each tape having its own state is likely to make you forget this, resulting in a less powerful machine. Conceptually, it’s usually not a good way to think about Turing machines.
> 4 votes

---
Tags: turing-machines
---


# Question
Title: Does the inverse of a one-way function $f$ being reducible to a predicate $b$ imply that $b$ is a hard-core bit for $f$?
I'm working with this definition for one-way functions:

> We call $f$ a (strong) one-way function if
>
> 1. it is computable in polynomial time
> 2. for any polynomial time randomized algorithm $B$ and any constant $c$ $$ \mathbb{P}\big(f(B(f(x))) = f(x)\big) = o(n^{-c}) $$ where $x\in\\{0,1\\}^n.$

And this defintion for hard-core bits:

> Let $f : \\{0,1\\}^n \rightarrow \\{0,1\\}^k$ and $b : \\{0,1\\}^n \rightarrow \\{0,1\\}$ be computable in polynomial time. We say that $f$ is a one-way function with hard-core bit $b$ if, for all randomized algorithms $B$ and all constants $c$, $$ \mathbb{P}(B(f(x)) = b(x)) = \frac{1}{2}+o(n^{-c})\\,. $$

And I'm asking myself whether, if $f$ is one-way and finding $x$ from $f(x)$ is polynomial time reducible to finding $b(x)$ from $f(x)$, $b$ must be hard-core. One way to structure this argument is like so: $$ \text{finding $x$ reduces to finding $b(x)$} \implies \big(f\text{ is one-way} \implies b\text{ is hard-core}\big) $$ Or by contrapositive: $$ \text{finding $x$ reduces to finding $b(x)$} \implies \big(b\text{ isn't hard-core} \implies f\text{ isn't one-way}\big) $$

So suppose finding $x$ reduces to finding $b(x)$ and $b$ isn't hard-core. Then the obvious strategy is to go through the reduction but instead of computing $b(x)$ deterministically, we make a good guess using some algorithm $B$ which must exist because $b$ isn't hard-core. Since we have a non-negligible chance of success to guess $b(x)$ correctly, we end up with a non-negligible chance to guess $x$ correctly and so $f$ isn't one-way.
But there's a point here where trouble comes in. That is, the reduction might involve computing $b(x)$ multiple times for various values of $x$. While we know the probability of computing a single $b(x)$ for a random $x$ correctly, I don't have any handle on the probability of success for a sequence of calls $b(x\_i)$ where the $x\_i$ are arbitrarily correlated.

# Answer
> 2 votes
Before addressing your question, we should note that there are some subtleties when defining "inverting $f(x)$ reduces to finding $h(x)$". Suppose we aim towards something along the lines of a standard Turing reduction, then what does our oracle do? When feeding the oracle some string $y\in\\{0,1\\}^\*$, where the only promise about $y$ is that it lies in the image of $f$, then what do you expect it to return? If $f$ is a permutation, then this is easy. However, when $f$ is not one to one, it isn't clear what to expect. One possibility is to require that the oracle returns $h(x)$ for some $x\in f^{-1}(y)$, though it might make the oracle pretty much useless (I'd guess that there exists a one way function $f$ and a hardcore predicate $h$ for $f$ such that any function in $2^{\\{0,1\\}^\*}$ is an $h$-oracle for $f$ under this definition).

Back to your original question. Suppose $f$ is a one way permutation and define $g(x,i,j)=(f(x),i,j,x\_i)$. Inverting $f$ reduces to (under the above definition) evaluating $h(x,i,j)=x\_j$, since you can feed the oracle different values of $j$. However, $h$ is not hardcore for $g$, since for a uniformly chosen triplet $(x,i,j)$ where $x\in\\{0,1\\}^n$ and $i,j\in \[n\]$, with probability $\frac{1}{n}$ it holds that $i=j$ and you can recover $x\_j$.

---
Tags: one-way-functions
---


# Question
Title: Proof that AND-OR graph decision problem is NP-hard
Given an directed acyclic AND-OR graph, where each non-terminal nodes are labelled as either AND or OR. The terminal nodes are the nodes which have no outgoing edges. Children of a node are the vertices all the outgoing edges of the node points to.

A solution graph for a node $S$ on an AND-OR graph $G$ is defined as a subgraph $G'$ which satisfies the following

(1) $S\in G'$

(2) If $v\in G'$ and $v$ is an AND node, then all of $v$'s children in $G$ are in $G'$

(3) If $v\in G'$ and $v$ is an OR ndoe, then at least one of $v$'s children in $G$ also belongs to $G'$

I want to show the following decision problem is NP hard:

Instance: An AND-OR graph $G$, a node $S$ in $G$ and a number $k$.

Question: Does there exist a solution graph for $S$ in $G$ which contains $\leq k$ nodes?

I am thinking about reducing some well known NP-hard problem to this problem. However, I am not sure which problem is the most suitable to pick. Please enlighten me! Thank you!

# Answer
> 1 votes
Hint: Given an instance of vertex cover problem, build an AND-OR graph whose terminal nodes represent the vertices and the OR nodes represent the edges.

One further hint: Make the root an AND node that has outgoing edges to all the OR nodes (that represent the edges in the vertex cover problem).

# Answer
> 1 votes
Hint: given an instance of set cover problem, build an AND-OR graph whose terminal nodes represent elements and whose OR nodes represent sets.

---
Tags: np-complete, np-hard, np, decision-problem
---


# Question
Title: Do we generally store the degree of each vertex in the linked list implementation? if not, why?
So generally speaking, when we implement the graph using linked list, do we store the degree of each edge too?

I'm asking this because if a question in my exam stated that we implemented this graph using linked list, do i assume we can access the degree of each edge in o(1) or not? this matters because it effects the time complexity of algorithms like finding if the graph has euler cycle which i should check the degree of each edge

and the exams are SAT type of questions so i can't write down anything i should just choose one of the 4 answers which for example says the time complexity of finding if the graph has euler path in linked list implementation

# Answer
Normally we don't; the adjacency list representation is a list of out-edges, but doesn't separately store the degree. However, you can certainly store that additional information if you want. You can choose how you want to represent the graph, and it's not hard to modify the standard data structure to keep track of the out-degree of each vertex.
> 2 votes

---
Tags: graphs, data-structures
---


# Question
Title: How to solve this mapping reduction problem by proving the computability of this function?
I am working on a mapping reduction problem. Define the union of two languages $L\_1,L\_2\subseteq\\{0,1\\}^\*$ to be $L\_1 \cup L\_2 = \\{x0\mid x \in L\_1\\} \cup \\{y1\mid y \in L\_2\\}$. I want to prove that $L\_1 \le\_m L\_1 \cup L\_2$.

I was reading about the mapping reduction. According to mapping reductions, for any $w \in \Sigma^\*$, $w \in L\_1$ iff $f(w) \in L\_1 \cup L\_2$.

I am thinking of making my computable function $f=\\{x \mid x\text{ ends with }0\\}$. If I can prove that this function is computable, then I can complete my reduction. I just have two following questions:

* Am I thinking correctly about this problem?
* How to correctly prove that this $f$ is computable? I am thinking to create a TM $M$ that enumerates $w \in L\_1 \cup L\_2$. If the string ends with a 0, then I halt the machine and accept the result. I am not sure how to formally prove the computability of $f$.

# Answer
The reduction function is simply

$$ f(x)=x0 $$

which is computable, since a TM can move to the end of $x$, append a $0$, and halt. It is also total, by definition.

Note that to prove that $f$ is computable we do NOT have to consider the decidability / enumerability of any sets. I think your confusion is caused by thinking about c.e. sets when crafting $f$, but defining a reduction function does not involve enumerability. You only have to ensure that $f$ is total computable, and that $x\in A \iff f(x)\in B$ for all $x$.
> 0 votes

---
Tags: turing-machines, computability, reductions
---


# Question
Title: Parikh's Theorem: CFL's "contain" regular languages?
The first sentence of the Wikipedia article for Parikh's Theorem states:

> "Parikh's theorem in theoretical computer science says that if one looks only at the relative number of occurrences of terminal symbols in a context-free language, without regard to their order, then the language is indistinguishable from a regular language."

I'm having some trouble understanding this sentence. I understand that unary CFL's can be described as the union of finitely many arithmetic sequences. Does this mean that if we apply a morphism $h$ to some CFL $L$ which, say, maps $a \longrightarrow a$ and $c \longrightarrow \epsilon$ for some $a \in \Sigma$ and for all $c \in \Sigma$ with $c \neq a$, then $h(L)$ is a unary regular language? Could someone elaborate on this?

# Answer
> 12 votes
The Parikh image $\Psi$ of a word is a vector counting the number of each of the letters in the alphabet: for example $\Psi( abbabaaca ) = (5,3,1)$ assuming the alphabet is $\\{a,b,c\\}$.

The Parikh image of a language is the set of Parikh images of the strings in the language: $\Psi( \\{a^nb^nc^n\mid n\ge 0 \\}) = \\{(n,n,n)\mid n\ge 0 \\}$.

The theorem states that the Parikh images of context-free languages are in fact Parikh images of regular languages, as example $\Psi( \\{( ab)^n c^n\mid n\ge 0 \\}) = \Psi( (abc)^\*) $.

(In a previous edit I had the example $\Psi( \\{a^nb^nc^n\mid n\ge 0 \\}) = \Psi( (abc)^\*) $. Technically correct, but the reader will note that language is not context-free.)

# Answer
> 5 votes
I agree the wording on Wikipedia isn't very clear, but I believe it refers to the following relationship:

Call two words *letter equivalent* iff they are equal when disregarding the order of the characters. That is to say: lexicographically sorting their characters (preserving duplicates) produces the same word. (In other words: their Parikh images are the same.)

Call two *languages* letter equivalent iff their words are, that is to say: lexicographically sorting their words produces the same language. (In other words: their Parikh images are the same.)

The theorem implies that every context-free language is letter equivalent to a regular language. For instance, $\\{ a^nb^n \mid n \geq 0\\}$ is letter equivalent to $(ab)^\*$.

(The notion *letter equivalent* can be found in e.g. *A simplified proof of Parikh's theorem*, by J. Goldstine (1977).)

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


title: Group tuples to satisfy constraints

text:
# Question
Title: Group tuples to satisfy constraints
This is a problem that involves matching students with various skills into groups so that there are as many groups as possible while ensuring that each group has certain skills present. I've reduced it to this:

1. Given a set of $N$ people with $S$ skills where $A\_{n,s}$ is the quantity of skill $s$ that person $n$ has.
2. Group the $N$ people into as many groups as possible, such that there are no more than $G$ people in any group, and so that the sum of each skill in each group is at least $B\_s$.

Constraints: $N, S, G \< 100$ and $A\_{n,s}, B\_s \< 10$

I haven't been able to come up with a better solution that a brute force so far. Would be very keep for some pointers as to what I should be searching for to find an algorithm for this class of problem.

# Answer
I suggest expressing this as an instance of integer linear programming (ILP). Express boolean logic operations in zero-one integer linear programming (ILP) might be useful to you in figuring out how to do that.

In particular, introduce zero-or-one variables $x\_{n,j}$, which is one if person $n$ is placed into group $j$, or zero otherwise. You can now express each of your requirements as a linear inequality, and then use an ILP solver to test for feasibility. Now do binary search (or simple iterative search) over the number of groups, to find the maximum number of groups for which you can find a feasible solution.
> 3 votes

---
Tags: algorithms, combinatorics, matching
---


# Question
Title: The set of valid sentences in FO is not decidable as a consequence of rec. inseparability
Two given languages $L\_1$ and $L\_2$ are called *recursively separable* iff there exists a recursive languge $R$ such that $L\_1 \subseteq R$ and $L\_2 \cap R = \emptyset$.

Now consider first order logic, and some finite axiomatisation of $\mathbb N$ in it (surely this is way to weak, as we have no induction). Then we have three sets, 1) the set of valid sentences, i.e. the ones derivable the the rules of first order logic, 2) the set of provable sentences using the axioms of $\mathbb N$, and the set of truth sentences, i.e. the ones fullfilled by $\mathbb N$. Also as a superset of all these, we have the set of first order sentences that have some model, and contrary to that the set of sentences that are unsatisfiable, i.e. have no model, which equals (by Completeness of first order logic) the set of inconsistent sentences.

Now, the following holds:

**Theorem:** The set of unsatisfiable sentences and the set of sentences provable from the choosen axioms of $\mathbb N$ are not recursively separable.

From this it follows that the set of provable sentences from the axioms itself, as well as the set truth sentences, as well as the set of satisfiable sentences, are all not recursive/decidable.

But does this implies that the set of valid sentences is not decidable? This is states in the classic text *Computational Complexiy* by Cristos H. Papadimitriou, on page 133. But as this set is a proper subset of the provable sentences, I do not see that this is implied by the above Theorem? Or am I missing anything?

# Answer
> 1 votes
The chosen finite axiomatization of $\mathbb N$ is consistent, since $\mathbb N$ is a model for them. Hence, any sentence provable from it must be satisfiable (e.g. by $\mathbb N$).

From this, we get that the set of provable sentences is disjoint from the set of unsatisfiable formulas.

Hence, the set of unsatisfiable formulas must be undecidable, otherwise we would have separability (taking $R$ to be the set of unsatisfiable formulas), and we would contradict the theorem.

Hence, the set of valid formulas must be undecidable as well, since we have the reduction "$P$ unsatisfiable $\iff \lnot P$ valid" (also mentioned by SimonJ above).

# Answer
> 0 votes
Suppose the set of valid sentences is decidable, then so is the set of satisfiable sentences, I believe, as:

$\varphi$ is satisfiable iff $\neg \varphi$ is not valid.

Thus if the set of satisfiable sentences is not decidable, the set of valid sentences cannot be.

---
Tags: complexity-theory, computability, logic, undecidability, first-order-logic
---


# Question
Title: Saving time finding a result by guessing first?
I am currently taking a graduate course about Image Processing in electrical engineering and while this question doesn't particularly relate to the class itself but rather some concepts in the algorithms we utilize.

One of the algorithms that we utilized was called, "Image Correlation" in order to find a "match" from using a segment of the picture and almost convolving it into the main picture. Below is an example of how this algorithm is implemented to find the correlation in the picture.

From *Digital Image Processing* by Rafael C. Gonzalez and Richard E. Woods...

My question is, instead of starting from the top left, why can't we estimate where the result is first before implementing the algorithm? Wouldn't it save time to know where you would like to start the process?

# Answer
Yes, it absolutely would save time. You are quite right, and you are onto a good idea -- that idea is frequently used to speed up image matching.

The core challenge is: how do we come up with an estimate where the result might be, more efficiently than using the correlation algorithm? It's not obvious how to do that, short of doing a correlation (which wouldn't actually save any time).

Fortunately, there are ways to do that. A standard approach is to use an image pyramid. You downscale the image to a lower resolution, then look for a downscaled version of the T in that smaller image (again using correlation). Because the image is smaller, the correlation calculation goes faster. Then that gives you a pretty good estimate where the T is, and instead of searching the entire full-resolution image, you only need to check a small portion of the full-resolution image. If you find multiple matches in the downscaled image, you can check all of them on the full-resolution image.
> 2 votes

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


# Question
Title: Removing vertices that belong to a given set from a graph
If I'm given a graph $G$ with the set of vertices $V$ and a set $B \subseteq V$, can I remove all the vertices $\in B$ from $G$, as well as all edges that connect any other vertex to a vertex $\in B$ in linear time ($O(V + E)$)? It can be assumed that checking if a vertex $\in B$ is $O(1)$.

My thoughts on this are- If I represent $G$ as an adjacency list, this is not possible as I'd have to loop over all vertices and the vertices that they're connected to. So worst case would be $O(n^2)$.

In case I have an adjacency matrix, I feel like this would be possible in $O(n)$ as I could zero out the entire row and column of the vertices in $B$. However, actually getting rid of the vertices themselves would require shifting elements of the array so overall $O(n^2)$.

My end goal is to be able to perform graph traversals (specifically, finding strongly connected components in the set $G - B$) over the leftover subset in a directed graph. Would simply ignoring any edges leading to vertices in $B$ and ignoring any vertices in $B$ work just fine?

# Answer
Yes, this can be done on an adjacency list representation in $O(|V|+|E|)$ time. Looping over all the edges can be done in $O(|V|+|E|)$ time. As you look at an edge, you can check both endpoints; if either one is in $B$, you can delete it. Afterwards, you can iterate through the vertices and remove the vertices in $B$ (their adjacency lists will be empty, so no need to do anything with their adjacency lists); this takes $O(|V|)$ time. The entire process takes $O(|V|+|E|)$ time.
> 0 votes

---
Tags: graphs, graph-traversal
---


# Question
Title: how to mapping reduce any r.e. language to the diagonal language K?
We know that the halting problem $A\_{TM}$= $\\{(e,x) \mid M\_e(x)$ accepts$\\}$ and the diagonal language K= $\\{e \mid M\_e(e)$ accepts$\\}$ are mapping reducible to each other. Recall that A mapping reducible to B means there exists a computable function from A to B s.t. for all x in A, x in A iff f(x) in B. Furthermore both are complete with respect to this mapping reduction relation.

I would like to prove that any r.e. language is mapping reducible to K directly without reducing to ATM. How can this be done?

# Answer
For any r.e. language $L$, it is the domain of some M\_l.

Consider the machine $M\_n(x,y)=M\_l(x)$, and now let $f(x)=s\_1^1(n,x)$ (obtained from snm theorem). Hence for any $y$, $M\_{f(x)}(y)=M\_l(x)$

Then $L$ can be reduced to $K$ by $f$ :

if $x\in L$ iff M\_l(x) halts iff $M\_{f(x)}(f(x))$ halts iff $f(x)\in K$.
> 1 votes

---
Tags: complexity-theory, computability
---


title: Sorting a stack using Bubble sort

text:
# Question
Title: Sorting a stack using Bubble sort
How to sort a stack using bubble sort? Can use another stack if necessary.

# Answer
> 1 votes
You must need an extra stack to sort an stack. With the help of two stacks this problem can be solved.

So, suppose you have n elements in the stack. and you have an other stack, which is empty.

Now, in bubble sort, after each iteration highest element reaches to its final position. So, to implement this algorithm, we can make use of that second stack.

**For the first Iteration:**
There are n elements in the stack, pop each element one by one in the empty(second stack) stack and keep track of highest element at each stage. After the first stack is completely empty, you will have the highest element of the stack. Now push that highest element in the first stack and then pop all the elements from the second stack and push them in first stack. So, after this iteration, highest element is set to its position. and we now have n-1 unsorted elements. Be alert to not to push highest element again in the first stack.

> for example, elements are 5,10,7,2,15. So, after first iteration stack content is 15,5,10,7,2.

**For the next Iterations:**
So, after 1st iteration highest element is set, and we are remaining with n-1 unsorted elements in first stack, while the second stack is empty. So, during this iteration, instead of n elements, pop only n-1 elements to the second stack and keep track of maximum. After n-1 elements are pushed to second stack we have highest element among those n-1 elements, which second highest element of original stack. Push that element in the first stack, above the highest element already there. And then push all the elements back in the first stack from second stack.

> So, after first iteration stack content is 15,10,5,7,2.

Then reduce the size to n-2 and follow same method.

Complexity of this method is same as bubble sort, which is $O(n^2)$.

---
Tags: algorithms, sorting, stacks
---


# Question
Title: Generating all words of length $n$ avoiding $A^2$ and $B^3$
I need to find a way to iterate over all sequences of words in two letters $A,B$ avoiding the sequence $A^2 = AA$ and $B^3 = BBB$. First of all, what is the regular expression for such a thing?

I need a way of iterating over all such possible words. I tried this one: $$ w \mapsto \\{ wA, wB, wBB\\} $$

however, if I run this function again, we obtain: $$ w \mapsto \\{ wAA,wAB,wABB,wBA,wBB,wBBB,\dots \\}$$ and you can see we have obtained the expressions we are trying to avoid.

I need way of generating all the words in $\\{A,B\\}$ of length $n$ avoiding these two patterns.

# Answer
Instead of constructing a regular expression, it is better to construct a DFA, or rather, a DFA with some "missing transitions". The DFA has the following states:

* $q\_0$: initial state.
* $q\_A$: state after seeing one A.
* $q\_B$: state after seeing one B.
* $q\_{BB}$: state after seeing two Bs.

The transition function is $$ \begin{array}{c|cccc} & q\_0 & q\_A & q\_B & q\_{BB} \\\hline q\_0 & & A & B & \\ q\_A & & & B & \\ q\_B & & A & & B \\ q\_{BB} & & A & & \end{array} $$ This is read as follows: when at row $q$, upon reading $\sigma$, move to the appropriate column, if any. If there is no appropriate column, we have reached the (invisible) sink state.

Using this, it is not hard to see that the number of words of length $n$ in your language is $$ \begin{pmatrix} 1 & 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix}. $$ Calculation shows that for $n \geq 1$, the number of words of length $n$ in your language is $$ \mathrm{round}(C \lambda^n), \text{where } C \approx 1.678735602594163 \text{ and } \lambda \approx 1.324717957244746. $$ The eigenvalue $\lambda$ is also the unique real root of $x^3-x-1$.

A glance at the OEIS reveals that your sequence is A164001, and has the recurrence $$ a\_n = \begin{cases} n+1 & n \leq 3, \\ a\_{n-2} + a\_{n-3} & n \geq 4. \end{cases} $$ (The recurrence $a\_n = a\_{n-2} + a\_{n-3}$ is of course related to the polynomial $x^3-x-1$ above.)
> 3 votes

---
Tags: regular-expressions, recursion, iteration
---


title: Self loops in max flow problem

text:
# Question
Title: Self loops in max flow problem
So, there can be different types of edges in a directed graph while solving the max flow problem. There can be reverse edges, multiple edges and self loops.

What is the significance of self loops in it?

How is it related to flow in the graph?

Let there be a graph like this `1->2->3` and 2 has a self loop. So, can I interpret it like this-

`1->2a--2b->3` ? where `--` denotes an edge from `2a->2b` and an edge from `2b->2a`.

So, How would I represent this in a graph using adjacency list?

# Answer
for the max flow problem you should remove the self loops and solve it. self loops don't effect on final solution because when there exists a loop on a vertex, it means a flow from the vertex (with an arbitrary capacity) goes on pipe that connect to itself, it means the flow doesn't waste, it just return to the vertex. it's like you connect a water hose from a tank to itself. you don't limit the input flow to the tank or output flow from it. so you can ignore self loops and solve the problem.
> 3 votes

---
Tags: algorithms, graphs, network-flow
---


# Question
Title: Show a sequence of distinct Primes number is O(log n)
Suppose I have a sequence:

$$n = \prod\_{i=1}^{r(n)} p\_i^{d\_i}$$

for some primes $p\_1 \< p\_2 \< \dots \< p\_{r(n)}$, and each $d\_i \geq 1$ an integer. The function $r(n)$ denotes the number of distinct primes divisor of $n$.

I'm trying to show $r(n) = O(\log n)$.

What I have tried: I think I can establish an upper bound on $\prod\_{i=1}^{r(n)} p\_i^{d\_i}$ to show its asymptotic bound.

To simplify and without loss of generality, let $d\_i = 1$. Then,

$$n = \prod\_{i=1}^{r(n)} p\_i$$ $$\log n = \log (\prod\_{i=1}^{r(n)} p\_i)$$ $$\log n \geq \Sigma\_{i=1}^{r(n)} \log p\_i$$

Then not sure where to go from here.

I think I want to show something like:

$$\log n \geq \frac{r(n) + 1}{2}$$

# Answer
Since each of the prime numbers is at least 2, we have $$n \geq \prod\_{i=1}^{r(n)} p\_i \geq \prod\_{i=1}^{r(n)} 2 = 2^{r(n)}, $$ from which it follows that $r(n) \leq \log\_2 n$.

In fact, since the prime numbers are generally larger than 2, we can obtain a better bound, namely $$ r(n) \lesssim \frac{\log n}{\log \log n}. $$ See for example MathWorld, which states the number of distinct prime factors in a primorial.
> 1 votes

---
Tags: primes
---


# Question
Title: Why does the ouput of an NC0 circuit depend on only a constant number of input bits?
I understand that NC0 circuits have a constant depth and bounded gate fan-in of two, but I'm struggling how to understand why the language is in NC0 iff there is a constant c such that for every n, there is a set c variables that determine it's membership.

# Answer
> 2 votes
An $\mathsf{NC}^0$ circuit *with single output* of depth $\ell$ has $O(2^\ell)$ nodes, and in particular can depend on at most $O(2^\ell)$ many input bits.

$\mathsf{NC}^0$ circuits become more interesting when we allow them to have many outputs. Amazingly, there are some things you can actually do with some circuits. Check out the classic paper Crypography in $\mathsf{NC}^0$ by Applebaum, Ishai, and Kushilevitz.

---
Tags: complexity-theory, trees, binary-trees, circuits
---


# Question
Title: What is $\sum_{k=1}^\infty \frac{1}{k^2 H_k}$?
According to this answer, $\sum\_{k=1}^\infty \frac{1}{k^2 H\_k}$ is approximately 1.33275. How?

# Answer
To get a rough idea, you just use a spreadsheet and add the first 1000 numbers. The result is about 1.33263641018923. With no idea if that is a good or bad approximation without a proof, but any such sum is a lower bound.

Obviously $\sum\_{k=1}^\infty \frac{1}{k^2 H\_k} = \sum\_{k=1}^m \frac{1}{k^2 H\_k} + \sum\_{k=m+1}^\infty \frac{1}{k^2 H\_k}$ for every m. We can calculate the first sum for moderately large m. We can then replace the second sum with a slightly larger one that we can calculate exactly:

$\sum\_{k=1}^\infty \frac{1}{k^2 H\_k} ≤ \sum\_{k=1}^m \frac{1}{k^2 H\_k} + \sum\_{k=m+1}^\infty \frac{1}{k^2 H\_{m+1}} = \sum\_{k=1}^m \frac{1}{k^2 H\_k} + \frac{1}{H\_{m+1}}\sum\_{k=m+1}^\infty \frac{1}{k^2}$

The sum of 1/k^2 for k ≥ m+1 is calculated by starting with $\sum\_{k=1}^\infty \frac{1}{k^2} = π^2 / 6$ and subtracting the first m reciprocal squares. For m = 1000 this gives an upper bound of 1.332,769,917,72819.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: How to find max margin for non-separable SVM?
I am new to Machine Learning. Suppose a training set of positive (square) and negative (circle) points is given like:

Obviously there would be no nice linear separator of positive and negative points. So assume there exist a transformation for (x1,x2) points as: `y1 = (x1-5)^2, y2 = (x2-5)^2` in (y1,y2) space. We will then map all positive points to (25,25) and all negative points to (1,1).

Now, the question is how can I find the maximum-margin separator in new space? That is, what curve in the original space transforms to the straight-line boundary in the transformed space? Using that I need to determine that should a new point be considered positive or negative.

# Answer
Map all the points to the new space. Then find the maximum-margin linear separator of those mapped points. Algorithms for finding a maximum-largin linear separator are described in the literature on SVMs (that's exactly what you need to do to train a linear SVM). In other words, you can map the points to the new space, then can take those mapped points and train a linear SVM on them. That's conceptually how to do it.

In practice, nonlinear SVMs use clever tricks to do the same thing, but do it faster (using the kernel trick).
> 1 votes

---
Tags: machine-learning, svm
---


# Question
Title: Time Complexity of a Union Find algorithm
I'm trying to understand the time complexity of an example algorithm. My conclusion was O(n^2) but this was considered wrong. The algorithm is as follows:
input: data: array of sorted n integers
input: n: size of data
input: c:a positive integer between 1 and n-1
delta = Array(n-1)
map=HashMap()
for I =1 to n-1 do:
delta\[i\] = data\[i+1\] - data\[i\]
map.Insert(delta\[I\],i)
end
heap=MinHeap(delta)
uf = UnionFind(n)
for I =1 to c do:
t=heap.deleteMin()
x=map.Search()
uf.Union(x,x+1)
end
return uf

To my knowledge the first for loop runs in O(n) time, building the heap takes O(n), and the second for loop would run at O(n^2) times dominating the other complexities.

# Answer
Figured this out. Since uf.Union is an inverse ackermann it grows so slowly that it could be considered constant. thus the second loop would run O(c*lgn) giving and expected output of O(n + c*lg n))
> 2 votes

---
Tags: time-complexity, asymptotics, union-find
---


# Question
Title: How to solve this recurrence involving binomial coefficients?
How to solve the following recurrence involving binomial coefficients, where $c$ is a constant non-negative integer, and $n$ and $k$ are non-negative integers ($n \ge k \ge 0$)?

$$ A(n,k) = A(n-1,k) + A(n-1,k-1) + c, \\ A(n,0) = 1, A(n,n) = 1 $$

---

***My Attempt:*** Without the constant $c$ (or $c=0$), $A(n,k)$ is just $\binom{n}{k}$.

I have tried the generating function $$ g(x,k) = \sum\_{n=0}^{\infty} A(n,k) x^n. $$ I need to evaluate $$ \begin{align} \sum\_{n=0}^{\infty} A(n+1,k) x^n &= \sum\_{n=0}^{\infty}\big(A(n,k)+A(n,k-1) + c\big)x^{n} \\ &= g(x,k) + g(x,k-1) + \frac{c}{1-x} \end{align} $$

On the other hand, $$ \begin{align} \sum\_{n=0}^{\infty} A(n+1,k) x^n = \frac{1}{x} \big(\sum\_{n=1}^{\infty} A(n,k) x^n\big) = \frac{1}{x}\big(\sum\_{n=0}^{\infty} A(n,k) x^n - A(0,k)\big). \end{align} $$ How to handle with $A(0,k)$? How to establish an equation for $g(x,k)$?

# Answer
Let us guess that $A(n,k) = \alpha \binom{n}{k} + \beta$. The recurrence reads $$ \alpha \binom{n}{k} + \beta = \alpha \binom{n-1}{k} + \beta + \alpha \binom{n-1}{k-1} + \beta + c, $$ from which we deduce $\beta = -c$. The base cases are $$ \alpha \binom{n}{n} - c = \alpha \binom{n}{0} - c = 1, $$ From which we deduce $\alpha = c+1$. All in all, the solution is $$ A(n,k) = (c+1) \binom{n}{k} - c. $$
> 3 votes

---
Tags: recurrence-relation, generating-functions
---


# Question
Title: Understanding time complexity of a while loop that will look over all vertices and edges
I need a little clarification on differing time complexities. My analysis for the below algorithm was $O(n +nm)$, but the correct analysis would be $O(n+m)$. I know that `Color` takes $O(n)$ time to initialize and the inner for loop takes $\mathrm{deg}(v)$ time, which by the handshaking lemma, wouldn't the inner for loop then be $O(m)$ and since the outside while loop iterates over all vertices in worse case so shouldn't that be $O(n)$, Giving $O(n) + O(nm)$?

# Answer
> 2 votes
Because each edge contributes to two degrees, we have $$\sum\_v\mathrm{deg}(v)=2m.$$

The time taken by the whole loop is $O(m)$.

Your analysis is of course correct, but since you replace $\mathrm{deg}(v)$ with the upper bound $m$, you get a loose bound finally.

By the way this is BFS if you ignore the "color" action.

---
Tags: graphs, time-complexity, asymptotics, graph-traversal
---


title: Test a bit substring function

text:
# Question
Title: Test a bit substring function
How do we test the following function?

`bits(bitstring, i, j)`

which returns a copy of the substring from `i` to `j` of some `bitstring`.

Consider the fixed 32-bit value:

`bitstring=0x12345678`

We could manually pre-determine the correct return values for ~500 different combinations of `i` and `j`. But this only covers `0x12345678`.

There are 232 ≈ 4 billion different strings like `0x12345678`.

Even for a non-exhaustive test, manually recording the constants we expect to get from any combination of (`bitstring`, `i`, `j`) does not seem like the best solution.

I imagine we can use the fact that bit strings map to unsigned integers and do some arithmetic to compare the return value of `bits` to `bitstring`.

Any help with vocabulary or classifying this validation problem would be appreciated, too.

*Technical side note: My uncertainty lies in whether the bit manipulations are being performed correctly, since the bit substring does not necessarily begin or end on a byte boundary.*

*Another note: After a few edits I have realized the important question here is **what are the different ways we can check that one bit string is a substring of another**? But the original question has a broader scope so I will leave it as it is.*

# Answer
You test the function in the same way you test anything else: you identify some example inputs and the desired outputs, and you run the function on those inputs and see if it gives you the desired output. You can still do that despite "not falling on a byte boundary".

In this case the function `bits` is a stateful interface, so you have to deal with that, but the same techniques for testing stateful interfaces should work fine here. In particular, the "input" is a sequence of operations on the data structure / API, and the "output" is the sequence of results from those operations. For instance, the first operation might be to set the contents of the underlying byte stream, and the second operation might be to invoke `bits()`.

I'm not sure where you're getting $512 \times 2^{32}$ from (presumably you mean $32 \times 2^{32}$), and those aren't permutations; but in any case that doesn't change anything. Testing almost never exhaustively tries all combinations. I don't see why this would be any different. Instead, the idea behind testing is that we try a small fraction of the possibilities, and if there is a bug, we hope that one of the test cases we try will expose it. This doesn't provide any guarantees, since there could always be a bug that only triggers on one of the test cases we didn't try -- testing is not verification, and does not prove correctness -- but it is useful nonetheless.

So, nothing prevents you from testing this function. Standard methods work fine.
> 0 votes

---
Tags: strings, software-testing, bit-manipulation, testing
---


# Question
Title: Kolmogorov Complexity proving there exists a constant for when if two strings are equal length
When talking about kolmogorov complexity, I understand that it describes true randomness of given (for now) a string $x$, if we can describe x in less than the $|x|$ then its complexity is said to be

> $C(x) \leq |x| + c$

my question lies in finding that c for a given problem.

Given this problem

> there is a constant $c$ $∈$ $\mathbb{N}$ such that, for $\forall$ x,y ∈ $\\{0,1\\}^+$ with $|x|=|y|$
>
> $H(x,y)$ is the hamming distance between $x$ and $y$
>
> $ C(y)$$C(x)$ $+ 2·H(x,y)·$(1 + $ \lceil log|x|\rceil $)$ + c$

How would I go about mathematically proving there there is a constant $c$ $∈$ $\mathbb{N}$ what does finding a constant tell us

> Constant is defined as follows
>
> as in what does this given a TM M and universal TM $u$ s.t. there exists a constant $c\_M$ s.t. $C\_u(x) \leq C\_M(x) + c\_M$(From Solomonoff and turing's theorem)?

# Answer
> 2 votes
Consider a procedure which has two inputs, $P$ and $DIFF$. Here $P$ is a self-delimiting program, and $DIFF$ is a list of indices, stored in some self-delimiting fashion (we leave the encoding vague for now). The procedure runs $P$, flips all the indices in $DIFF$, and prints the output. Using the invariance property of Kolmogorov complexity, we immediately get that there is a program of length $|P|+|DIFF|+O(1)$ which simulates the procedure above.

Now take any two vectors $x,y$. Let $P$ be a self-delimiting program of size $C(x)$ producing $x$, and let DIFF be the list of differences, which can be encoded using $H(x,y)(1+\lceil \log |x| \rceil)$ bits (this improves on your exercise; we're using the fact that $|x|$ is known by the procedure). It follows that $C(y) \leq C(x) + H(x,y)(1+\lceil \log |x| \rceil) + O(1)$.

---
Tags: turing-machines, information-theory, kolmogorov-complexity
---


# Question
Title: Where is the second face in a graph with 3 nodes?
I understand that to work out the number of faces of a connected planar graph, you use Euler's formula F = A - N + 2, where A is the number of arcs and N is the number of nodes.

For a triangle node (3 arcs and 3 nodes), the number of faces would therefore be 3 - 3 + 2 = 2.

But I can't count two faces, only one (the triangle itself). Where is the second face, or where have I misunderstood?

# Answer
> 3 votes
You probably smack your head against the wall for this but: One face "inside" the triangle, the other one is "outside".

---
Tags: graphs, planar-graphs
---