title: Efficiently find maximum XOR on a graph

text:
# Question
Title: Efficiently find maximum XOR on a graph
We are given an **undirected** graph $G=(V,E)$, $|V| \leq 50$. We are also given a starting vertex $s$. Each vertex $v$ of the graph is associated with a natural number $N\_v$. Initially our profit is $R=N\_s$.

Now we have to traverse the graph beginning from $s$ in an order. We can visit each vertex or edge any number of times. Whenever we reach a vertex $v$, $R=R \operatorname{XOR} N\_v$. (Note that if we visit $k$ times a vertex $v$, then we will XOR $k$ times with $N\_v$.)

Find the maximum value of $R$ that can be obtained while traversing $G$.

Note: Here traversal means walk beginning from $s$.

# Answer
> 1 votes
I'm going to first assume that your graph is connected; that is, every node of the graph is reachable from $s$. We'll relax this condition down the line, but for now, it simplifies the problem.

Now, let's start with what we know. If $G$ is connected, then we can visit every vertex; that is, there's some path $p$ that goes to each vertex $t$.

Let's examine such a path $p = (p\_0 = s), p\_1, \dots, p\_{n-1}, (p\_n = t)$. By definition, we know that the value of such a path is just $R(p\_0, \dots, p\_n) = \bigotimes\_k N\_{p\_k}$. In addition, if at $p\_n = t$, we immediately turn back and travel backwards on $-p$ (the reverse path of $p$), then we would eventually arrive back on $s$ with a value of \begin{align\*} R(p, -p) &= R(s, \dots, p\_{n-1}, t, p\_{n-1}, \dots, s)\\ &= \left(\bigotimes\_{0 \le k \le n} N\_{p\_k}\right) \otimes \left(\bigotimes\_{0 \le k \le \bf n-1} N\_{p\_k}\right) \\ &= (N\_{p\_0} \otimes N\_{p\_0)} \otimes (N\_{p\_1} \otimes N\_{p\_1)} \otimes \dots \otimes (N\_{p\_{n-1}} \otimes N\_{p\_{n-1}}) \otimes N\_t \end{align\*}

Recall that xor has the property that $x \otimes x = 0$, the identity. therefore, any path from $s$ to $t$ and back to $s$ just gives a value of $N\_t$. In fact, any conjunction of paths $$ s \stackrel{p\_1}{\to} v\_1 \stackrel{-p\_1}{\to} s \stackrel{p\_2}{\to} v\_2 \stackrel{-p\_2}{\to} s \stackrel{p\_3}{\to} \dots \stackrel{-p\_n}{\to} s $$ gives a value of $$ N\_s^{n + 1} \otimes \bigotimes\_k^n N\_{v\_k} $$ Furthermore, we can get rid of the $s^{n+1}$ term by deciding to stop the final path immediately before the terminal vertex if it falls on an even $n$.

In essence, this tells us that it is possible to construct a walk starting at $s$ such that the value of this walk is $\bigotimes\_{v \in S \subseteq V(G)} N\_v$ for any subset of vertices of $G$.

This then suggests that your problem reduces down to finding a subset of vertices $S \subseteq V(G)$ such that $\bigotimes\_{s \in S} N\_s$ is maximum over $V(G)$.

At first glance, this might seem like a non-trivial covering/knapsack problem. For one thing, the naive strategy here seems to be to try out every subset of $V(G)$. In addition, there doesn't seem to be any sort of monotonicity, continuity, or even some form of "optimal substructure" property for us to exploit.

Fortunately for us, this problem admits a relatively nice representation in terms of a linear algebraic system, and its solution process is equivalent to finding the rank of an induced matrix, or alternatively, Gaussian Elimination.

Now, suppose that we have a set of annotated vertices $N = \\{N\_v \mid v \in V(G)\\}$, how do we represent this as a linear system?

Well, given an integer $N\_v = 1011\cdots01\_2$ in binary, then we can think of it as the column vector $$ \[\\!\[N\_v\]\\!\] = \left(\begin{array}{c}1\\0\\ \vdots \\ 0 \\ 1\end{array}\right) $$ Now, let's consider the semi-ring $(+ = \otimes, \times = \max = \times\_{\mathbb{N}})$ over bits (0, 1). Here the addition operation is bit xor and the multiplication operation is the usual integer multiplication, which also happens to be the $\max$ operation or the $\wedge$ conjunction operation.

We wish to find coefficients $c\_0, c\_1, \dots, c\_n$ such that $$ c\_0 \[\\!\[N\_{v\_0}\]\\!\] + \dots + c\_n \[\\!\[N\_{v\_n}\]\\!\] $$ is "maximized". In particular, we wish to analyze the $A\_N: k \times n$ system $$ \left(A\_N = \left(\begin{array}{ccc}\[\\!\[N\_{v\_0}\]\\!\] & \cdots & \[\\!\[N\_{v\_n}\]\\!\]\end{array}\right)\right) \left(\begin{array}{c} c\_0 \\ \vdots \\ c\_n \end{array}\right) $$ where $k$ is the size of your bit-vectors (likely $32$ or $64$). Now, chances are, this system is over-determined (but also rank-deficient). Therefore, our first instinct will be to reduce this system to reveal its rank structure.

Doing this ends up giving us an efficient algorithm: Gaussian Elimination.

The idea is as follows. We **try** to solve the problem of $$ A\_N c = \left(\begin{array}{c}1 \\ \vdots \\ 1\end{array}\right) $$ through Gaussian Elimination. Now, I need to emphasize that we are only **trying** to solve this problem because, chances are, there is no solution! Think about it, $A\_N c$ gives the bit-vector that corresponds to the final value of a walk, so if $A\_n c = 1$ always has a solution, then it means that our problem is trivial: always return $2^{32} - 1$. In fact, in pretty much all interesting cases, there's no way to satisfy this attempted equality.

"What? Why are you doing this to me then?"

Simple, we actually inspect a trace of the algorithm rather than the final solution. In particular, at each iteration of Gaussian Elimination, we might find ourselves in one of two situations. Either everything still goes fine and dandy, and we can continue elimination, or we reach a contradictory state where we realize that we can't proceed. In the latter case, this corresponds to a case where you need to add a row of zeros and somehow magically pull a one out. In such cases, rather than aborting, we will just concede the impossibility and replace that row in the output with a zero.

More concretely, after $m$ iterations of elimination, we are left with a subproblem in which we only have to analyze the subsystem starting at the $m^{th}$ row. All of the prior rows will be zeros or part of the identity grid.

At the $m^{th}$ row, either there is some column $\[\\!\[N\_{v\_i}\]\\!\]$ in our intermediate matrix that has a leading $1$ in that row, or it's impossible to fill that row in the output.

* In the former case, we will select one such column to pivot (and with a bit of thought, you should choose the largest column), and add (subtract, since the inverse of $\otimes$ is still $\otimes$) it from every other column that still has a leading $1$ in that row.
* Otherwise, we will be forced to concede that the only solution is to place a $0$ in the output at that row and move on.

This then gives an algorithm find a maximum subset with respect to $\otimes$:

```
for each i from 31 down to 0, do
  if there's some maximal vertex v such that N(v) >= 2^i, then
    select v as a pivot and remove it from future considerations
    for every other vertex u such that N(u) >= 2^i, do
      N(u) := N(u) xor N(v)
    end for
  else,
    // Here, we can't possibly hope to fill this row with a one, so
    do nothing
  end if
end for

```

Now, the set of pivots that you have selected will give you the maximum xor-subset; just xor them together to find the maximum. The number of pivots also corresponds to the rank of your system, and if there are 32 pivots, then that immediately means that your maximum value is $2^{32} - 1$. If there are 31 pivots, then that means that there's a single 0 somewhere in your bit vector; 30 pivots means that there are two holes; etc.

Finally, we relax the restriction that our graph be connected. Rather, we will simply preprocess the graph and identify the connected component that contains the vertex $s$, and proceed similarly afterwards.

Best of luck!

---
Tags: algorithms, graphs, optimization, graph-traversal
---


# Question
Title: What is 'K' in the Bounded Post Correspondence Problem?
I'm only just starting to learn about the PCP, and I'm especially interested in the Bounded version. From Wikipedia:

> One of the most important variants of PCP is the bounded Post correspondence problem, which asks if we can find a match using no more than k tiles, including repeated tiles.

I am not sure I understand what Wiki means by a 'tile' in this context.

I do understand that a typical PCP problem takes as input two equal-length lists of nonempty strings, each of which contains some number of words. An example is this:

`M = (abb, aa, aaa)` and `N = (bba, aaa, aa)`

In terms of the Bounded PCP, what would the integer K be here? Is it the length an individual word can be (which in this case is maxed at 3)? Is it the length of a single list?

Hope this is clear. I appreciate any help profusely in advance.

# Answer
Suppose your list is M=(bba,ab,bba,a) N=(bb,aa,bb,baa) Then its equivalent tile representation is as follows

Now your pcp problem is equivalent to finding a sequence of tiles(repetition allowed) such that concatenating all upper halves and concatenating all lower halves gives you same string. K here is nothing but number of tiles that can be used

Edit : As Yuval Filmus subtly mentions in his comment, there are many other interpretations of K. In an another formulation K can also be the maximum length of concatenated string, in which case the bounded PCP problem is Pspace complete. But usually many books refer to K as being number of tiles that are allowed.Please refer to Sipser book for more.
> 4 votes

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


# Question
Title: Reference request: optimizing procedures on lists in dynamic languages by performing safety checks in advance
For my science fair project, I implemented an optimization to Python's sort routine. The idea is to move the safety checks that have to be carried out during each comparison, e.g. type checks and character-width checks, outside of the sort loop and just get them all done in one pass. An optimized comparison function is then selected from a portfolio based on the results of the checks. So, for example, if the checks determine that all the objects are of the same type, the selected comparison function can skip the usually-required "are the object types compatible" check. Etc.

I have to write this up as a paper, and am currently working on a literature review. Are there any papers describing similar techniques in other dynamic languages/generally?

# Answer
> 7 votes
I'm not aware of anything exactly like this, but there are some things that are arguably related.

For specifically sorting this is related to the Schwartzian transform, though with a very different goal. In the Schwartzian transform, you run through the input applying an expensive function and pairing the input and output together, then sorting on the output. This is in contrast to performing that expensive function on each operation. In your case, your "expensive function" would be the type checks and the dynamic dispatches. A bit differently you would be checking a property for the whole list as well and then choosing which comparison operation to use based on that.

In a totally different vein, there's a general technique called polymorphic inline caching (pioneered by the Self team and covered, among many other things, in Craig Chamber's thesis) and more generally adaptive optimization that is used in some virtual machines. Polymorphic inline caching solves the problem that if we do a dynamic dispatch, then we are jumping to some completely unknown code, and thus we can't inline it and optimize it and the current function. The solution is simple: just do an `if` to test if we are in some specific case, and if so, we can inline that code, else we do the dynamic dispatch. The problem is there is an unbounded, unknown number of possible cases. This isn't a problem, though, for a Just-In-Time (JIT) compiler which can just do this for the cases actually seen at runtime.

This doesn't solve your problem since dynamic dispatch is based on the runtime class of an object, not on some arbitrary predicate like "all the elements of this array have the same type". This is where adaptive optimization comes in and things like tracing JIT compilers. It's quite conceivable that unrolling a loop a few times or inlining a couple levels of recursion can lead to many type checks being eliminated with simple constant propagation style optimizations, and possibly entirely eliminated by more sophisticated optimizations in some cases. Nevertheless, it will often not do the same thing as you are suggesting and would need to see a trace first for each use of the sort function. On the other hand, if it knows all the elements are numbers, say, from earlier code, it can eliminate checking entirely.

---
Tags: reference-request, type-checking, program-optimization, interpreters
---


# Question
Title: Calculating Size of parts of tree cut by an edge in a tree
Suppose that there are $n$ nodes, and that edge $e$ of weight $w\_e$ cuts the tree into parts of size $k\_e,n-k\_e$. Then the average distance is $$ \sum\_e w\_e k\_e (n-k\_e). $$ For example : n=6,k=6 list=\[1,2,3,4,5,6\]

```
                    Node--------> 1
                                   \(1)<-----------Weight
                                    \
                                     3
                                (3) / \(2)
                                   /   \
                                  4     2
                             (4) / \ (5)
                                /   \
                               5     6

```

in this case we get $$ \ (1 \cdot 1 \cdot 5 + 2 \cdot 1 \cdot 5 + 3 \cdot 3 \cdot 3 + 4 \cdot 1 \cdot 5 + 5 \cdot 1 \cdot 5) ={87} $$

I'm storing the tree using adjacency lists.

1 approach might be to calculate size of elements of the list of the vertex connected by that edge recursively. For eg here if I cut $3-4$ I go the list of $4$ that contains $5,6$ then for every element in $4$ I go their list and calculate size of them and the vertex in it i.e go to list $5$ and $6$ and calculate size of their list. But I think this might be wrong or too long.

Now how do I find out the value of $k\_e$ in the tree in a better and fast way?

# Answer
> 1 votes
You can use dynamic programming in its version for trees. Choose a root arbitrarily, and calculate recursively the number of vertices in the subtree rooted at each node. This should give you enough information to calculate $k\_e$ for each edge $e$. The total running time should be $O(n)$.

I'm leaving the rest of the details for you to ponder.

---
Tags: algorithms, graphs
---


# Question
Title: Why does a reduction from a P-problem to an NP-complete problem not show that P=NP?
Consider the following problem, called BoxDepth:

> Given a set of $n$ axis-aligned rectangles in the plane, how big is the largest subset of these rectangles that contain a common point?

Say we proved these two statements:

1. There is a a polynomial-time reduction from BoxDepth to MaxClique.
2. There is a polynomial-time algorithm for BoxDepth with $O(n^3)$ runtime.

Why don’t these two results imply that P=NP?

# Answer
Part 1 shows how to solve BoxDepth using MaxClique.

Part 2 shows how to solve BoxDepth directly.

None of the parts says anything about solving MaxClique.
> 7 votes

---
Tags: complexity-theory, np-complete, reductions, np, p-vs-np
---


# Question
Title: Logarithmic guarantees for randomized search trees
In this paper \[1\], "treaps" and "randomized search trees" are introduced. The idea is to guarantee logarithmic update and query operations by assigning uniform random priorities to the keys being inserted into the tree.

The authors assume that randomness is "hidden" from the user:

> All expectations are with respect to randomness that is "controlled" by the update algorithms. For the time being we assume that the priorities are kept hidden from the "user." This is necessary to ensure that a randomized search tree is transformed into a randomized search tree by any update. If the user knew the actual priorities it would a simple matter to create a very "non-random" and unbalanced tree by a polynomial number of updates.

I don't actually understand what is meant by that. **Specifically, I don't understand what the user might be able to do to affect the runtime by observing the generated priorities.** My ideas of trying to understand that are:

1. The user might be able to provide keys in certain order to make the resulting trees unblanaced! However, I don't think this is right because the priorities are not generated based on key values.
2. I understood the paragraph wrongly and they actually mean that the priority generation is controlled by the user not just seen by the user.

\[1\] https://faculty.washington.edu/aragon/pubs/rst96.pdf

# Answer
> 1 votes
Let's consider a different example: a hash table. While usually the hash function is fixed in advance, it is also possible for it to be chosen randomly when the hash table is initialized.

If we want to mount a Denial of Service attack on a hash table, we need to feed it many keys that hash to the same value. If the hash function is weak and known, then we can easily do it. If the hash function is weak and unknown, then it could be difficult or even impossible.

When the authors say that the priorities are kept hidden from the user, they mean that the randomness used in the data structure is not "public". In our hash table example, it means that the user of the hash table doesn't know which hash function was chosen. If the user knew the hash function then she could mount a DoS attack. If she doesn't, then such an attack becomes much more difficult.

In practice we don't necessarily think of the user as malicious; however, we want a guarantee on the running time which is independent of how the data structure is used. Suppose that we use a treap or a randomized BST in some algorithm, in a very specific way. If the algorithm has access to the randomness—for example, if it is fixed—then perhaps its specific access pattern results in bad performance. However, if the algorithm acts independently of the randomness, then bad performance only happens with small probability.

---
Tags: binary-trees, search-trees, randomized-algorithms, randomness, pseudo-random-generators
---


title: Do CFGs generate many languages?

text:
# Question
Title: Do CFGs generate many languages?
Suppose we define a CFG such that it is possible to produce strings of the form $a^nb^n$ (in this case, I would think, we would need epsilon-productions). Then one such $L(CFG)$ is $a^nb^n$.

However, let's say it is also possible to produce strings not of the form $a^nb^n$ from this grammar.

Can we still call $a^nb^n$ a language generated by the grammar, even if it is not the only/unique language accepted by the grammar?

In other words, is the language accepted by a CFG the set of all strings that can be derived from the grammar? Or can it also be a proper subset of these strings, fulfilling some desired criterion?

# Answer
> 8 votes
Every grammar, by definition, generates a single, unique language.

The definition of "generating $L$" includes that $\overline{L}$ has to be *not* generated. That's obviously not the case for any proper subset of the "largest" generated language.

The definition has not been chosen without reason: using your approach, *every* formal language would be regular (as subset of $\Sigma^\*$). That would not be a useful model at all.

# Answer
> 5 votes
If

$$L(CFG) = \mathscr{L}$$

and

$$\mathscr{L} \supset \\{a^nb^n: n\geq 0\\}$$

then $CFG$ accepts $\mathscr{L}$ and not $\\{a^nb^n: n\geq 0\\}$. Maybe one way to avoid this confusion is to use the word *denote* instead of *accept*. The grammar $CFG$ denotes the language $\mathscr{L}$. Anyways this should be clear by reading the definitions.

And $CFG$ is going to need $\epsilon$-production rules only if $n$ can be $0$. You should be more specific in the future.

# Answer
> 5 votes
When in doubt, one should always consult the definition. The language generated by a context-free grammar $G = (V,\Sigma,R,S)$ is defined to be

$$L(G) = \\{ w \in \Sigma^\* \mid S \Rightarrow^\* w \\}$$

That is, $L(G)$ is the set of strings of terminal symbols that satisfy the condition, that they can be derived from the start symbol $S$ using the rules in $R$. By definition (and by the usual way of using set abstraction in mathematics), this set is unique.

---
Tags: formal-languages, formal-grammars
---


# Question
Title: Logspace algorithm for s-t connectivity in undirected forests
It has been shown that the decision problem
$\\{(G, s, t)~\mid~ G\text{ is an undirected forest and there is a path from }s \text{ to } t \\}$ is complete for logspace (and therefore in $L$).
But the proof involves a series of reductions which didn't seem very intuitive to me.
Is there any natural algorithm that directly solves this problem in log space?

# Answer
This is proved by Cook and McKenzie. We make use of the following notation:

1. $\deg(v)$ is the degree of a vertex $v$.
2. $N(v,1),\ldots,N(v,\deg(v))$ is some fixed ordering of the neighbors of $v$.

We construct a sequence $v\_1,v\_2,\ldots$ of nodes starting with $v\_1 = s$ and $v\_2 = N(s,1)$ (if $\deg(s) = 0$ then $s$ is connected to $t$ iff $s = t$). Given $v\_{i-2},v\_{i-1}$, we construct $v\_i$ as follows:

> Suppose that $v\_{i-2} = N(v\_{i-1},j)$. Then $v\_i = N(v\_{i-1},j+1)$.

(If $j = \deg(v\_{i-1})$ then $j+1 = 1$.)

It turns out that if the connected component of $s$ has size $m$ then the first $2(m-1)$ vertices contain each vertex $v$ in the connected component exactly $\deg(v)$ times, and after that the sequence repeats indefinitely. This is because the sequence essentially performs a depth-first search, as the following image from Wikipedia illustrates (the arrows should be ignored):

Here $s = F$ and the neighbors are ordered from left to right. The first 16 elements of the sequence are F,B,A,B,D,C,D,E,D,B,F,G,I,H,I,G. The sequence then repeats.

This implies the following simple algorithm: calculate the first $2(n-1)$ members of the sequence, and check whether $t$ ever appears. This can be implemented in logarithmic space.

---

Reingold gave a (significantly) more complicated algorithm that works for *any* undirected graph, still using only logarithmic space. If the graph is directed then the problem is complete for NL, and so probably cannot be solved using only logarithmic space (at least not on deterministic Turing machines!).
> 8 votes

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


# Question
Title: Find an algorithm that finds a minimal hitting set for sets limited in size
Given a family of sets $F=\\{S\_1,...,S\_m\\}$, where $S\_i{\subseteq}\\{1..n\\}$, with the assumption that the maximum size of any set $S\_i$ is at most $k$ ($|S\_i|{\leq}k\ {\forall}i\in\\{i..n\\}$).

I'm tasked with finding a hitting set $H$, a set that contains at least one member from each set $S\_i$ ($H{\cap}S\_i\ne\emptyset\ {\forall}i\in\\{1..n\\}$). And to prove that the algorithm gives produces a set that is at most k times larger than the minimal hitting set.

What algorithm does it and how do I prove that it does it.

I've tried the greedy algorithm (take the number that covers the most sets, remove those sets, repeat).

I've also tried making the problem into a two sided graph where one side is the numbers, the other side are the sets and edges connect sets with their members, and applying a minimum cover set algorithm.

For both instances I couldn't show that the hitting set it gives is at most a set k times larger than the minimum.

# Answer
> 6 votes
Here are two algorithms for the case $k=2$, also known as Vertex Cover; we think of the sets $S\_i$ as edges and of the elements $\\{1,\ldots,n\\}$ as vertices. We can assume that each edge connects *two* vertices, since singleton edges can easily be eliminated.

Both algorithms below can be extended to the case of general $k$.

**Algorithm 1: Maximal matching** Pick a maximal matching, and take all vertices containing it. This is a vertex cover since if there is an edge which isn't covered, the matching isn't maximal. Every vertex cover must contain at least one vertex per edge in the matching, and our solution contains two vertices per matching edge, hence it's a 2-approximation.

**Algorithm 2: Linear programming** Consider the following LP relaxation: there is a variable $0 \leq x\_i \leq 1$ for every vertex, and a constraint $x\_i + x\_j \geq 1$ for every edge $(i,j)$. Find a solution minimizing $\sum\_i x\_i$, and take all vertices such that $x\_i \geq 1/2$. This is clearly a vertex cover, and its value is at most twice the value of the LP, hence it's a 2-approximation.

---
Tags: np-hard, sets
---


# Question
Title: Solving divide & conquer reccurences if the split-ratio depends on $n$
Is there a general method to solve the recurrence of the form:

$T(n) = T(n-n^c) + T(n^c) + f(n)$

for $c \< 1$, or more generally

$T(n) = T(n-g(n)) + T(r(n)) + f(n)$

where $g(n),r(n)$ are some sub-linear functions of $n$.

**Update**: I have gone through the links the provided below and also sifted through all the recurrence relations in Jeff Erickson's notes. This form of the recurrence is not discussed anywhere. Akkra-Bazi method applies only when the split is fractional. Any poignant reference will be apprieciated.

# Answer
> 6 votes
Let's say you have a recurrence $$ T(n) = \begin{cases} T(n - n^c) + T(n^c) + f(n) & \text{n \> 2} \\ 1 & \text{otherwise} \end{cases} $$ that ranges over positive reals.

What can we do with this function? Well, not a lot unless we superimpose certain structures upon it. I came from a numerical analysis background, which is paved with numerical recipes that somehow works even when the underlying problem is either not smooth enough (doesn't matter, let's still throw Newton's method at its divided differences) or too complicated to analyze (sort of like this problem). My gut reaction towards these problems is to make some handwaved assumption, cross our fingers, and hope for the best. In this case, it seems to give relatively good bounds.

In particular, I want to make two major assumptions. One of these assumptions is more or less baseless, but we won't get very far without it. The other has a somewhat nice visual intuition that you can hopefully grok, but it is still more handwavy than anything else.

1. I will assume that $T(n)$ is "smooth-ish". It's fairly easy to see that $T(n)$ is not everywhere differentiable. In fact, it isn't even continuous, since for $f(n) = \log(n)$ and $c = \frac{1}{2}$, $\lim\_{n \to 2^-} T(n) = 1$ and $\lim\_{n \to 2^+} T(n) = 2 + \ln 2$. Therefore, given the iterated maps generated by $n \mapsto \sqrt{n}$ or $n \mapsto n - \sqrt{n}$, $T(n)$ will contain a discontinuity at $n$ if its iteration tree contains $2$ somewhere in its trajectory. That is a lot of discontinuities, it might even give Dirichlet's function a run for its money. If we're getting to the point where we are comparing a function's behaviors to that of the prototypical example of a nowhere-continuous function, isn't it laughable to try to claim that it is "smooth-ish"? Well, it turns out that in practice, the effects of these discontinuities asymptotically diminishes, to the point that your graph looks almost smooth when $n$ tends towards infinity! Therefore, I propose that we put down our pitchforks and just look the other-way in this circumstance. In particular, I will assume that at any point of interest $n$ that is sufficiently far away from the origin, $T(n)$ is differentiable, or at least approximately differentiable around some neighborhood.
2. I will also assume an even stronger stance of smoothness when $n$ is sufficiently far away. Suppose that $\alpha(n)$ is some sublinear function such that $n \> \alpha(n)$ (for example $n^c$), then the derivative $T'(\xi \in (n - \alpha(n), n)$ does not vary significantly when $\alpha(n)$ is slow enough. Intuitively, as $n$ gets larger, the relative size of the neighborhood $(n - \alpha(n), n)$ decreases (since its size is just $\alpha(n)$, which grows much much slower than $n$ does). Eventually, the size of this neighborhood becomes so insignificant (relative to $n$) that the rate of change of $T(n)$ within this neighborhood no longer changes all that dramatically.

Now, both of these properties are assumed, and I have zero idea how to go about actually proving either in any rigorous way. But like I said before, let's cross our fingers and hope for the best.

Let's start with the recurrence relation: \begin{align\*} T(n) &= T(n - n^c) + T(n^c) + f(n) \\ T(n) - T(n - n^c) &= T(n^c) + f(n) \\ n^c\frac{T(n) - T(n-n^c)}{n^c} &= T(n^c) + f(n) \end{align\*} Now, I'll assume that $T$ is smooth enough on the interval between $n - n^c$ and $n$. Appealing to one of our classical analytic tools, the mean-value-theorem, gives us $$ \frac{T(n) - T(n-n^c)}{n^c} = T'(\xi \in (n - n^c, n)). $$ Furthermore, when $n$ is sufficiently large, we assume that $T'(\xi)$ is approximately the same throughout this interval, and hence takes the value of any of the finite differences within this interval as well. This then means that $$ T'(\xi) \approx \frac{T(n) - T(n - \epsilon)}{\epsilon} ~~~~ \epsilon \< n^c $$ In particular, take $\epsilon = 1$ to get a one-step divided difference approximation \begin{align\*} n^c (T(n) - T(n-1)) &\approx T(n^c) + f(n) \\ T(n) - T(n-1) &\approx \frac{T(n^c) + f(n)}{n^c} \\ \end{align\*} We can telescope this out to get $$ T(n) \approx \sum\_k^n \frac{T(k^c)}{k^c} + \sum\_k^n \frac{f(k)}{k^c} $$

Perturbing $T(n)$ reveals that $T(n)$ has two asymptotic phases, depending on the asymptotic nature of $f(z)$.

When $f(n) = o(n^c)$ ($f$ is faster than $n^c$), then the right sum dominates, and we have $T(n) = \Theta\left(\sum\limits\_k^n \frac{f(k)}{k^c}\right)$ which can often be approximated with the integral $\int\limits^n \frac{f(x)}{x^c} dx$.

When $f(n) = \omega(n^c)$, then the left sum dominates the right. Here, we have to analyze the sum $$ \left(\sum\_k^n \frac{T(k^c)}{k^c}\right) + F\_c(n) $$ where $F\_c(n) = \int\limits^n \frac{f(x)}{x^c}dx$.

By virtue of the smoothness argument, we can once again look at this as a left-anchored Riemann sum, approximating the integral $\int\_n \frac{T(x^c)}{x^c} dx$. Applying a similar mean-value-theorem over the integral gives $$ \sum\_k \frac{T(k^c)}{k^c} \approx \int^n \frac{f(x^c)}{x^c} dx = n\frac{T(\xi \< n^c)}{\xi^c} $$ We can just go ahead and approximate this by $n\frac{T(n^c)}{n^c}$, which gives the approximation \begin{equation} T(n) \le n M \frac{T(n^c)}{n^c} + F\_c(n) \end{equation} for some constant $M$ that bounds the series.

Now, suppose that we have the iterated sequence $(n, n^c, n^{c^2}, n^{c^3}, \dots, n^{c^k})$ where $n^{c^k} \< 2$, then we can use this sequence to telescope the above inequality to get: $$\label{eqn:meh} T(n) \le n \left(\sum\_i^{k-1} \frac{M^i}{n^{c^i}}F\_c(n^{c^i}) + \frac{M^k}{n^{c^k}}\right) \tag{\*} $$ Once again, we can bound the $F\_c(n^{c^i})$ term by some constant to find that $$ T(n) = O\left(F\_c(n) + n F\_c(n^c) \left(M n^{-c} + M^2 n^{-c^2} + \dots + M^k n^{-c^k}\right)\right) $$ where $k = \log\_c\left(\frac{\log(2)}{\log(n)}\right)$. Simplifying a bit and coalescing some of the $Mn^{-c}$ terms together (in particular, we know that $n^{-c^k}$ is a constant), we get $$ T(n) = O\left(n k F\_c(n) M^{k} \right) $$

However, this bound is relatively loose, and you should refer to $(\ref{eqn:meh})$ whenever possible.

Be aware that in no way is this rigorous. I have not provided any support that this ought to work beyond some clumsy approximations. Nevertheless, if you just need a quick asymptotic guess for the sake of informal analysis, then you can actually see that this scheme works well (for large enough values of $n$, usually $n \> 10$ suffices) in practice.

Anyways, for all of the choices of $c$ and $f$ that I've tried, the following computation \begin{align\*} \hat T(n) &= n \sum\_k^{\log\_c \log\_n 2} \frac{M^k}{n^{c^k}} F(n^{c^k}) \\ F(n) &= \sum\_k^n \frac{f(k)}{k^c} \end{align\*} where $$ M \approx \frac{\sum\_k \frac{T(k^c)}{k^c}}{n \frac{T(n^c)}{n^c}} $$ seems to give good approximations. This technique also generalizes to recurrences of the form $$ T(n) = T(n - \alpha(n)) + T(\beta(n)) + f(n) $$ which can be approximated with \begin{align\*} \hat T(n) &= n \sum\_k^{\\#\_\beta(n)} \frac{M^k}{\alpha^k(n)} F(\beta^k(n)) \\ F(n) &= \sum\_k^n \frac{f(k)}{\alpha(k)} \end{align\*} where $\alpha^k(n) = \alpha(\stackrel{k}{\cdots}(\alpha(n)))$ and $\\#\_\beta(n)$ denotes the number of elements of the sequence $n, \beta(n), \beta(\beta(n)), \dots, \beta^{\\#\_\beta(n)}(n)$ such that the last term is between $1$ and $2$.

---
Tags: proof-techniques, recurrence-relation
---


# Question
Title: Differences between $\text{BPP}$ and $\overline{\text{BPP}}$ vs $\text{co-BPP}$
Is $\overline{\text{BPP}}$ different from $\text{co-BPP}$? I am having trouble understanding the "co" part of these complexities.

I think yes and here is what I think: It seems given that $\text{BPP}$ is the class of languages decided by PTMs with error probability 1/3, then this is equal to $\text{co-BPP}$. But $\overline{\text{BPP}}$ is the class of languages decided by PTMs with success probability 1/3. So $\overline{\text{BPP}}$ is different from $\text{co-BPP}$.

Am I correct on these definitions? Thanks!

# Answer
> 5 votes
$\newcommand{\co}{\mathsf{co}\text{-}}\co A=\left\\{L\subseteq \Sigma^\* \mid \overline{L}\in A\right\\}$

Saying that the class $A\subseteq P\left(\Sigma^\*\right)$ is closed under complement is equivalent to saying $A=\co A$ (verify).

Note that $\overline{A}$ is not the same as $\co A$, here we're simply taking all the languages outside of $A$, and we require nothing about the complement of these languages.

$\newcommand{\BPP}{\mathsf{BPP}}\BPP$ is closed under complement, since we can simply flip the answer (verify yourself that this works), so $\co \BPP=\BPP$.

$\overline{\BPP}$ however is a whole new story, and even contains all undecidable languages, since $\BPP\subseteq \mathsf{PSPACE}$.

---
Tags: complexity-theory, complexity-classes
---


# Question
Title: Could computer architecture be reworked to support switching from binary to ternary, for example?
I was investigating *why* computers use binary instead of ternary and, from what I understand, found it's for precision. We want to avoid getting the wrong answer when computing math, and if we were to look at a bit at the wrong time in, for example, a base-10 system we might accidentally catch it switching states and accept the output before it's done switching states.

Please let me know if I've misunderstood this. I know there's a lot going on under the hood in computer hardware.

Assuming I understood correctly though, would it be feasible to redesign computers to be able to switch "languages" in some components **in real-time** in favour of speed/size instead of accuracy? It's well-known that 8 bits in base-10 can store 390,625 times more data than in binary, so there are obviously massive implications if possible.

To clarify: my question is about the feasibility of designing a computer which could switch between the two languages **in real-time** based on user-defined required output.

**Edit:** As clarified above, I am not asking about the benefits of binary *over* ternary. I am asking about the benefits of using them *together,* in real-time, and if that could even be possible. Thanks.

# Answer
Current computers use electronic parts which can easily distinguish between two states, by stating that high voltage = 0 and low voltage = 1, or vice versa. The hardware that is needed to combine two inputs x and y and produce an output equal to NAND (x, y) is very, very simple and any other logic can be produced very easily from this.

Your task in proposing ternary computers: Suggest how with current electronic parts, three states can be represented. Then suggest what would be a primitive operation that combines two ternary inputs and produces an output; what that operation would be, and how you would implement it. Then suggest how you could for example add two integer numbers that are made of 40 trits (I think that's the name, I might be wrong).

Of course your suggestion must *not* represent a trit using two binary states, because using two binary states you could easily represent four values with the same effort, which would surely be more efficient. So you might represent 0 = low voltage, 1 = medium voltage, 2 = high voltage. Have fun doing that reliably. (One problem that you have is that using low and high only, you can change states with force and therefore quickly. If you needed to change a state from high to medium voltage, you'd have to be careful not to overshoot to low voltage, so this would likely be slower).

Now it seems you not only want to implement ternary arithmetic, but you want to switch the hardware on the fly between binary and ternary. That's not running before you can walk, that's running before you even figured out that crawling might be a possibility.
> 4 votes

---
Tags: computer-architecture
---


title: Cards shuffling. Greedy algorithm

text:
# Question
Title: Cards shuffling. Greedy algorithm
We have n deck of cards. To shuffle i-th deck we need a(i) seconds. Our task is to give a greedy algorithm, which will merge two decks until we have one deck.

My idea is to create a priority queue. At top of the queue we have a minimum value of a(i). And then shuffle Q.top() with the next Q.top() while Q.size() \> 1.

Could you help my proving, if it works, or not?

# Answer
> 2 votes
Just like Wojciech said, there is a bijection between calculating Huffman Code and your problem. As you can see, we can treat your problem as:

> Find binary rooted tree with $n$ weighted (weights $a\_1,...,a\_n$) leafs, such that sum of distances from leafs to root multiplied by their weight would be minimal.

This problem can be solved by calculating Huffman Code. Now let's see why we can use that algorithm to solve our problem. We will treat each deck as a leaf and each shuffling as an inner verticle. If all inner vertices have exactly 2 kids then such tree is a result of some shuffling procedures. We can easily prove that every Huffman Code Tree don't have inner verticles with only one child (because we could reduce that tree otherwise).

---

For further reading:

In this lecture note you can read prove that you can use your algorithm to build Huffman Code.

---
Tags: algorithms, correctness-proof, greedy-algorithms
---


# Question
Title: What is a problem, a task, and a solution?
I am attending algorithms and data structures course in my University and my professor gave me an interesting question the other day. He told me to think about it.

**What is a problem, a task, and a solution?**

It seems to me like it's more of a philosophical question. All of those 3 things correlate to one another.

To me, it seems like if we have a problem, we then have a task to solve it, which we might be able to do with an algorithm, which is a solution.

What do you guys think would be the answer to this question? Does it have some kind of deeper meaning about algorithms, or am I just overthinking it?

# Answer
> 0 votes
A problem is that you're trying to study Algorithms(seriously, its a real world **problem**). By posting this question here, you've performed a **task**, in order to solve a part of that problem. A complete **solution** would be when you understand the problem, perform a set of tasks in order to solve that problem. Seems to be fun? Actually, it is.

Lets understand with a better example, You want to become a good Software(Don't get deep in this term or change it with Web or whatever you'd like) Developer. It is a **problem**. Now you're attending some courses to fulfill that dream, this a **task** for the solution of that problem. Another **task** could be that you practice & sharpen your CS skills on your own. And many more such tasks. All these tasks collectively form a **solution**.

# Answer
> -1 votes
philosophically, a problem isn't a problem until there is unrest, and a way to explain it as such. i.e. an understanding leads to determining if it really is a problem, or just misunderstood. Correctly specifying the problem then leads to its identification.

A bit morbid, but for ex, people dying from arsenic poisoning seems like a problem. Arsenic is poisonous, it will cause death. Is this the problem? No, the problem is exposure. (stated generally for brevity.) The task becomes solving exposure. And of course there may be multiple solutions. Detection, protective gear, isolation, etc.

---
Tags: algorithms, terminology
---


# Question
Title: Does applying Hadamard gate is identical to applying a measurement gate that is perpendicular to the current qubit state?
Cause applying H (hadamard gate) on a state |0\> will evolve to 50% |0\> and 50% |1\>, assuming we are meausring along the vertical axis (Z-axis).
While applying a measurement along a horizontal axis (e.g. X-axis), will force the state to "evolve" (destroied) and let it be perpendicular to the vertical axis. In another word the state now will have a 50% chance to be measured along the vertical axis to be |0\> and 50% to be |1\>.
I know that measuring a state will destroy the state, while H gate is unitary and conserves the state from destruction. But I really need to know how the physics behind the Quantum Computer gates.

# Answer
As Yuval points out, you have already answered your own question. If I have a state $|q\rangle = a|0\rangle + b|1\rangle$ and I apply a Hadamard gate to that state, I end up with a new state: $$H\cdot|q\rangle = \frac{1}{\sqrt{2}}(a+b)|0\rangle + \frac{1}{\sqrt{2}}(a-b)|1\rangle$$

However, if I measure the state $|q\rangle$ in the standard basis, I get either $|0\rangle$ with probability $|a|^2$ or $|1\rangle$ with probability $|b|^2$. Notice that both $|0\rangle$ and $|1\rangle$ are different states than what you would have gotten had you applied the Hadamard transform instead of a measurement. I admit that a Hadamard-transformed state of 50% $0$ and 50% $1$ looks very much like having done a measurement, but this is not true: you haven't done the measurement yet, and the state is still in superposition. This matters if you do other transformations afterward, or if you work in a multi-qubit system. Then when measuring later, it matters whether you did a Hadamard transform or a measurement.

A good thing to do to acquaint yourself with transformations and measurements is to just compute some by hand on one qubit and on two qubits, and to write out in full the intermediate states in Deutsch's algorithm. You'll get the hang of it.
> 1 votes

---
Tags: quantum-computing, circuits
---


# Question
Title: How to find the maximal set of elements $S$ of an array such that every element in $S$ is greater than or equal to the cardinality of $S$?
I have an algorithmic problem.

Given an array (or a set) $T$ of $n$ nonnegative integers. Find the maximal set $S$ of $T$ such that for all $a\in S$, $a\geqslant |S|$.

For example:

1. If $T$=\[1, 3, 4, 1, 3, 6\], then $S$ can be \[3, 3, 6\] or \[3, 4, 6\] or \[4, 3, 6\].
2. In $T$=\[7, 5, 1, 1, 7, 4\], then $S$ is \[7, 5, 7, 4\].

I have tried this recursive function.

```
function(T):
    if minimum(T) >= length(T):
        return T
    else:
        return function(T\minimum(T))

```

Is there any non-recursive algorithm. (I did not check my recursive algorithm, so it could has some flaw.)

# Answer
Sort T. Then take elements while `T[i] >= i+1`.

For example `sorted(T)=[6,4,3,3,1,1]`. Then, `T[0] = 6 > 1`, `T[1] = 4 > 2`, `T[2] = 3 <= 3` and finally, `T[3] = 3 < 4` so we have `S = [T[0], T[1], T[2]]`.
> 14 votes

# Answer
From my comment originally: This is closely related to a quantity ubiquitous in academic productivity assessment, the Hirsh index, better known as the $h$-index. In short it is defined as the number of publications $h$ one has such that each of them has at least $h$ citations (the largest such $h$).

The only way your problem differs is that you would be interested not only in *how many* publications satisfy the criterion but also *what their citation counts are*, but that's a trivial modification. The data's already there, the original algorithm just drops it.

The generally implemented calculation is rather straightforward and agrees with Karolis Juodelė's answer.

**Update:** Depending on the size and character of your data, it may be worth exploring methods which partially sort the array by filtering data above and below a pivotal point (quicksort comes to mind). Then depending on whether there's too little or too many adjust the pivot and redo on the subset that contains it and so on. You don't need an order between elements higher than $h$, and certainly not between those lower than that. So for example, once you found all elements greater or equal to $h\_1$ and there's less than $h\_1$ of them, you don't need to touch that subset again, just add to it. This converts the recursion inherent to quicksort to a *tail recursion* and thus can be rewritten as a loop.

My Haskell is a bit rusty but this should do what I described above and seems to work. Hope it can be understood to some degree, I am happy to provide further explanation.

```
-- just a utility function
merge :: [a] -> [a] -> [a]
merge [] ys = ys
merge (x:xs) ys = x : merge xs ys

-- the actual implementation
topImpl :: [Int] -> [Int] -> [Int]
topImpl [] granted = granted
topImpl (x:xs) granted
  | x == (1 + lGreater + lGranted) = x : merge greater granted
  | x > (1 + lGreater + lGranted) = topImpl smaller (x : merge greater granted)
  | otherwise = topImpl greater granted
  where smaller = [y | y <- xs, y < x]
        greater = [y | y <- xs, y >= x]
        lGreater = length greater
        lGranted = length granted

-- starting point is: top of whole array, granted is empty
top :: [Int] -> [Int]
top arr = topImpl arr []

```

The idea is to collect in `granted` what you know will definitely participate in the result, and not sort it any further. If `greater` together with `x` fits, we're lucky, otherwise we need to try with a smaller subset. (The pivot `x` is simply whatever happened to be the first item of the sublist that's currently considered.) Note that the significant advantage against taking largest elements one by one is that we do this on blocks of average size $remaining/2$ and don't need to sort them further.

**Example:**

Let's take your set `[1,3,4,1,3,6]`.

1. `x = 1`, `granted = []`, `greater = [3,4,1,3,6]`. Ouch, we hit a pathological case when the pivot is too small (actually so small that `smaller` is empty) right in the first step. Luckily our algo is ready for that. It discards `x` and tries again with `greater` alone.
2. `x = 3`, `granted = []`, `greater = [4,3,6]`. Together, they form an array of length 4 but we only have that limited from below by 3 so that's too much. Repeat on `greater` alone.
3. `x = 4`, `granted = []`, `greater = [6]`. This gives an array of 2 elements ≥ 4 each, seems we might have use for some more of them. Keep this and repeat on `smaller = [3]`.
4. `x = 3`, `granted = [4,6]`, `greater = []`. This together gives an array of 3 elements ≥ 3 each, so we have our solution `[3,4,6]` and we can return. (Note that the permutation may vary depending on the ordering of the input, but will always contain the highest possible terms, never `[3,3,6]` or `[3,3,4]` for your example.)

(Btw. note that the recursion indeed just collapsed to a cycle.) The complexity is somewhat better than quicksort because of the many saved comparisons:

Best case (e.g. \[2,2,1,1,1,1\]): a single step, $n-1$ comparisons

Average case: $O(\log n)$ steps, $O(n)$ comparisons in total

Worst case (e.g. \[1,1,1,1,1,1\]): $n$ steps, $O(n^2)$ comparisons in total

There are a few needless comparisons in the code above, like calculating `smaller` whether we need it or not, they can be easily removed. (I think lazy evaluation will take care of that though.)
> 8 votes

# Answer
There is nothing wrong with your algorithm, and of course most of recursive algorithms can be converted into loops, here a loop version of your recursive code:

```
function(T):
    while minimum(T) <= lenght(T):
         remove minimum(T) from T
    loop

```
> 6 votes

# Answer
Any recursive algorithm can be rewritten to use iteration. After all, a Turing machine knows nothing about recursion but can implement any algorithm. In principle, you can rewrite your recursive function by writing your own stack manipulation code to remember the values of the function's parameters and any local variables it might have. In this particular case, your function is tail-recursive (once a recursive call returns, the thing that called it immediately returns, too) so you don't even need to maintain the stack.
> 4 votes

# Answer
Use a min-heap to do a partial heapsort, since you don't need the whole array to be sorted.

Keep popping elements greedily until you exceed the threshold given.
> 3 votes

---
Tags: algorithms, optimization, sets
---


# Question
Title: Showing Optimal Substructure for Stacking Boxes DP Problem?
I am having trouble wrapping my head around the Stacking Boxes dynamic programming problem, and understanding how it has optimal substructure and overlapping subproblems. If it has the optimal substructure and overlapping subproblems, then I can use dynamic programming to solve the problem. How do I know that the stacking boxes exhibits the optimal substructure?

I have read that it is similar to the longest-increasing-subsequence problem which exhibits optimal substructure and overlapping subproblems, but I am unable to see how it relates to the stacking boxes problem.

# Answer
> 4 votes
When people talk about this notion of an optimal substructure, they're just saying that you can solve a bigger problem by looking at the best solutions to smaller (sub)problems and somehow transforming these solutions to these subproblems back into a solution of the bigger problem.

So let's look at a modified version of this box-stacking problem that is also used in G4G's solution. Let $\text{Stack-Boxes-No-Rotation}(\mathrm{B})$ be the problem of finding a maximum stack of boxes in $B$ such that we are not allowed to rotate any of the boxes. Later on, we'll relax this restriction of not being able to perform rotations.

Now, let's get to the meat and potato of this concept. First, let's break down the phrase. What is a substructure? Well, the prefix "sub" suggests that this is a smaller problem structure than the whole problem. However, it's still a bit hazy what we mean by smaller. Are we talking about the number of boxes in $B$ to stack? Are we talking about volume? The height?

Unfortunately, there's no singular prescription that you can follow to figure this out. You'll have to rely on your intuition, and there are usually multiple valid ways to compare two things. The intuition however always comes back to the idea that if you have the solutions to the smaller problems, then you should be able to easily use them to create a solution to the big problem.

It's pretty hard to get a good feel for this unless we work through an example. Here, I'll start off with a way of defining "smaller" subproblems that is different from the way that G4G is doing, but which may have been one of your first instincts. Let's say a problem is smaller than another problem if its height is smaller than the other.

First thing first, since we're defining comparisons in terms of height, we need to create a parameter for it. So let $\text{Stackable}(B, h)$ determine whether it's possible to stack boxes in $B$ to a height of $h$. We wish to find the largest $h$ such that $\text{Stackable}(B, h)$ is still possible.

Now, we've talked about using the height to determine which problem is smaller. We say that $\text{Stackable}(B', h') \preceq \text{Stackable}(B, h)$ if $h' \le h$ and $B' \subseteq h'$. Now, we haven't shown that $\text{Stackable}(B, h)$ has the optimal-substructure property with respect to the order $\prec$ yet. Before we do so, let's review what optimal-substructure claims if it applies to this problem.

> If we know $\text{Stackable}(B', h')$ for every subset of boxes $B' \subset B$ or every height $h' \< h$ (that is, $(B', h') \prec (B, h)$, then we would be able to use that information to find out whether $\text{Stackable}(B, h)$ is possible.

Okay, so how do we do that?

Well, a good approach is usually to think backwards. If it's possible for a set of boxes in $B$ to stack to height $h$, then let's consider the last move that we could have made. It could be any of the boxes in $B$. Suppose that we've picked a box $b$ to use as the top of the stack, then what? Well, it better be the case that the stack under it uses only boxes from $B - \\{b\\}$ and has height $h - h(b)$. In addition, it better be the case that the box immediately under $b$ must have an area large enough to accommodate $b$.

If you think about it for a moment, figuring out whether the stack under $b$ has height $h - h(b)$ can be accomplished by knowing $\text{Stackable}(B - \\{b\\}, h - h(b))$ (which literally tells me if it's possible to stack boxes from $B - \\{b\\}$ to a height of $h - h(b)$). However, there's no way to ensure that the box immediately under $b$ has to have a large enough area! Therefore, just knowing the solutions to the subproblems is not enough (in this formulation of the problem) to piece together a solution for the bigger problem.

But what went wrong here? It turns out that to stack a box on top of another box, we also need to know the area of the box on the bottom. Now, you have a few choices that you can make here. The problem at hand is that we're not tracking enough information, so one solution is to track more information. The other is to formulate an altogether different problem-structure.

Let's go with the former. How do we amend our process to keep track of the area of the box on top of a stack? Well, we could just add them as parameters of $\text{Stackable}$. Now, we interpret $\text{Stackable}(B, h, w, l)$ as whether it is possible to stack boxes from $B$ to a height of $h$ such that the box on the top of this stack has area $w \times l$. How's that for a mouthful. In addition, we need to also consider whether we should amend our denotation $\preceq$ of whether one subproblem is smaller than the other. While it's tempting to say that $(B', h', w', l') \preceq (B, h, w, l) \iff B' \subseteq B, h' \le h, w' \ge w, l' \ge l$, as you'll see, it's also okay if we just keep the original $\preceq$.

Now, let's see what optimal substructure claims here: If I have the answer to whether it is possible to stack boxes to a height of $h'$ using subsets of boxes that I am given, such that the final box of that stack is some $w' \times l'$, then I should be able to use that information to figure out whether it is possible to stack boxes to my desired height $h$ such that the final box has size $w \times l$.

Fortunately for us, it is now possible to do this. Once again, let's think backwards and consider the final box that we wish to stack: $b$. Now, we know that $b$ has an area of $w \times l$, so in order to stack it, we need to make sure that the preceding stack of boxes in $B - \\{b\\}$ has height $h - h(b)$ and whose final area is at least $w' \times l'$ where $w' \> w$ and $l' \> l$. Well, fortunately for us, this is literally what $\text{Stackable}(B - \\{b\\}, h - h(b), w', l')$ (for each $w', l' \> w, l$) answers. Therefore, we know that our subproblem candidate space is $$ \text{candidates}(B, h, w, l) = \bigcup\_{b = (h(b), w, l) \in B, \\ w' \> w, l' \> l} \text{Stackable}(B - \\{b\\}, h - h(b), w', l'). $$ Now, given these candidates, how do we find $\text{Stackable}(B, h, w, l)$? Well, it's simple; if any of the candidate subproblems are possible, then so is the bigger problem. Therefore, we just have $$ \text{Stackable}(B, h, w, l) = \bigvee\_{b = (h(b), w, l) \in B, \\ w' \> w, l' \> l} \text{Stackable}(B - \\{b\\}, h - h(b), w', l'). $$

Now, there are $2^{|B|} \times H \times W \times L$ possible ways to fill the parameters $(B, h, w, l)$, so that's definitely a horrible solution, since you might have to find the value of each of these possible arguments in order to find the best result. Don't worry; this actually happens quite a lot in practice. Not everyone finds an acceptable solution on their first try.

After one iteration of a possible Dynamic Programming formulation that you find lacking, you can think about alternative formulations of your problem structure. In my example, I used the formulation $\text{Stackable}(B, h, w, l)$ to structure the solution space. There, I interpreted the result of $\text{Stackable}(B, h, w, l)$ as whether it is possible to stack boxes in $B$ to a height of $h$ such that the final box has area $w \times l$. Now, is there a better formulation that I can make?

Well, in the spirit of gradually refining your process, it's quite obvious that in the formulation $\text{Stackable}(B, h, w, l)$, the final box must have an area of $w \times l$. However, it's probably the case that not that many boxes share the same area. Therefore, we can probably gain back some time if we just outright say what the last box is: $\text{Stackable}(B, h, b \in B)$. Now, our dynamic programming formula becomes $$ \text{Stackable}(B, h, b \in B) = \bigvee\_{b' \in B-\\{b\\}\\w(b') \ge w(b) \\ l(b') \ge l(b)} \text{Stackable}(B, h - h(b'), b') $$ Still, we're potentially looking at $|B| 2^{|B|} H$ arguments here.

Unfortunately, this is the extent of what the stackability formulation can do for us. However, we can try other substructure formulations.

And this is where the idea of the G4G solution comes into place. Let's number each of the boxes in $B$, so that $B = b\_1 \le b\_2 \le \dots \le b\_n$ (with respect to their area). Now, instead of looking at this problem in terms of whether it is possible to stack some boxes to some height, let's look at what the maximum height of the set of boxes $b\_1, \dots, b\_k$ can reach.

This then gives another sub-structure ordering. We say that a problem on $(b\_1, \dots, b\_k)$ is smaller ($\prec$) than another problem on $(b\_1, \dots, b\_{k'})$ if $k \< k'$. Now, let's consider the formulation $\text{Tallest}(b\_1, \dots, b\_k)$, which gives you the tallest stack you can build using just the boxes in $\\{b\_1, \dots, b\_k\\}$. Can we show that it has an optimal substructure?

Unfortunately, it's not all rainbows and sunshine: we run into the same problem that we've had before. Suppose we're considering the last box on a stack, we have no way to ensure that the box preceding it can fit the final box, just that its total area is larger. Therefore, let's try our parameterization trick from before; let $\text{Tallest}(n, b\_k)$ denote the tallest tower that we can build using just boxes in $(b\_1, \dots, b\_n)$, such that the final box is $b\_k$.

Third time's a charm, right? To see that this formulation has an optimal substructure property, let's try to build the tallest stack using the first $n$ widest boxes that ends at some $b\_k$. Well, if we have $\text{Tallest}(n-1, b\_{k'})$ where $b\_{k'}$ is both wider and lengthier than $b\_k$, then we could build an even taller stack. The tallest stack we can build is then the maximum of these candidates: $$ \text{Tallest}(n, b\_k) = \max\_{b\_{k'} \sqsubset b\_k} \left(\text{Tallest}(n - 1, b\_{k'})\right) $$ where $b\_{k'} \sqsubset b\_k$ if $k' \< k$ and $w(b\_{k'}) \ge w(b\_k), l(b\_{k'}) \ge l(b\_k)$. Now, shrinking $n$ is valid, but the astute reader will also notice that $$ \text{Tallest}(n, b\_k) = \max\_{b\_{k'} \sqsubset b\_k} \left(\text{Tallest}(n, b\_{k'})\right) $$ will work just as well. In fact, we no longer need to keep track of the range of boxes to consider, and we can simplify this formulation down to just $$ \text{Tallest}(b\_k) = \max\_{b\_{k'} \sqsubset b\_k} ~ \text{Tallest}(b\_{k'}) $$ which can be interpreted as the tallest stack that you can build if the final block is $b\_k$. This then concludes the formulation that G4G constructed.

I want to sign off with a few pieces of advice. Dynamic Programming is a very intuition-driven technique for problem solving. It might seem daunting at first, but with enough experience, you'll eventually view it as an extremely powerful tool. Personally, I find that the approaches that works best for me are:

* Don't worry about the implementation of the actual dynamic program, and instead focus on its interpretation. When you see $\text{Tallest}(b\_k)$, don't worry too much about what its code should look like; rather, stick to the high level interpretation and just read it out as "the tallest stack ending at the box $b\_k$". This way, it makes reasoning about the correctness of the approach much easier.
* Try to work backwards if possible. Dynamic programming is essentially just structural induction. It might seem daunting to have to build up the recursion tree in your head, so don't. Instead, the "inversion" trick of looking at the final operation of your program and working backwards is much less mentally taxing. On top of that, working this way will quickly tell you if your "induction hypothesis", or your "optimal substructure" hypothesis, actually holds or not.
* Dynamic Programming is about decisions. Whenever you formulate a dynamic programming problem, always ask yourself: what is it that I need to choose and decide at every point? In the case of $\text{Tallest}(b\_k)$, for each $b\_{k'} \sqsubset b\_k$, you have to decide whether you will include that box in your stack or not. You can explore all of these possibilities simultaneously, but at the end of the day, you have to commit to a concrete event. Therefore, it's important to figure out what your options/candidate subproblems are and how you can either combine them or choose the best outcome.

---
Tags: algorithms, dynamic-programming
---


title: Upper bound of of fib(n+2)

text:
# Question
Title: Upper bound of of fib(n+2)
I have a homework problem that is perplexing me because the math is beyond what I have done, although we were told that it was unnecessary to solve this mathematically. Just provide a close upper bound and justify it.

> Let $$f(n) = |\\{w ∈ \\{a, b\\}^n : aa \notin w \\}|. $$ Provide an asymptotic upper bound on $f$ as $n\to\infty$.

So far: $$ \begin{array}{c|c|c} n & \text{strings} & \text{compared to } 2^n \\\hline 1 & 2 & 2^n - 0 \\ 2 & 3 & 2^n - 1 \\ 3 & 5 & 2^n - 3 \\ 4 & 8 & 2^n - 8 \\ 5 & 13 & 2^n - 18 \\ 6 & 21 & 2^n - 43 \\ \end{array} $$

The math that will give me an exact bound is beyond me. Obviously $O(2^n)$ is an upper bound, though it is not particularly tight.

Any suggestions on what I should try?

# Answer
> 8 votes
So I'm not completely sure, but I think you're asking to count the number of strings of size $n$ (over the alphabet $\\{a, b\\}$) where the factor/substring $aa$ does not appear right?

In this case, there are a few combinatorial approaches that you can take. Both Yuval and ADG have given simpler and more intuitive arguments, so I definitely suggest checking their answers out! Here's one of my favorites, it's a little strange, but it's a very general (and kind of a fun) approach.

Let's start with a simpler language, that of words which starts and ends with $b$ (also with no substrings of $aa$). We can look at an admissible string (e.g. $bbb\textbf{a}b\textbf{a}bbbb$) as a list of sequences of $b$s separated by singular $a$s. This gives the construction: $$ w = (b^+a)^\*b^+ $$ Now, how do we count sentences that belongs to this language?

Let's imagine that we're expanding these expressions out. What does $e^\*$ denote? Well, it's simply $$ e^\* = \epsilon \mid e \mid ee \mid eee \mid eeee \mid \dots $$ Now, this will make very little sense, but let's imagine that $e$ is a variable over some numerical field. In particular, we'll treat $\epsilon \to 1$, $a \mid b \to a + b$, and $abc \to a \times b \times c$. This then says that $$ e^\* \to 1 + e + ee + eee + \dots $$ Let's try to see the motivation behind this strange interpretation. This is *almost* a bijective transformation. In particular, we want to preserve the *count* of each $e^n$ word, which, as you can readily see, we do. However, there's one crucial difference between the string expressions and numerical expressions: the multiplication (concatenation in strings, $\times$ in numerical expressions) is now commutative! Intuitively, commutativity lets us treat all permutations of the same word as the same; that is, we don't disambiguate between the expression $bbbab$ and $bbabb$; they both represent a string with 4 $b$s and one $a$. Therefore, this transformation allows us to preserve the count of each word of a certain number of $a$s and $b$s, but it now allows us to turn a blind eye on the superfluous details that we don't care about.

If you go back to precalculus, you might recognize this series as $\frac{1}{1 - e}$. I know that it doesn't make any sense to rewrite this regular expression as a numerically-valued function, but just bare with me for a moment.

Similarly, $e^+ = ee^\* \to \frac{e}{1 - e}$. Which means that we can translate $w$ into $$ w \to \frac{1}{1 - (\frac{b}{1 - b} \times a)} \times \frac{b}{1 - b} $$

In turn, we can simplify this down to $$ w(a, b) = b \times \frac{1}{1 - (b + ba)} $$

This tells us that the language $w$ is isomorphic to the language $b(b \mid ab)^\*$ (whose direct translation is already $\frac{b}{1 - b - ba}$) without ever having to resort to any language-theoretic tools! This is one of the power of treating these series as closed-form functions: we can perform simplifications on them that are nearly impossible to perform otherwise, hence reducing it down to a simpler problem.

Now, if you still recall any of your calculus course, you'll recall that certain types of functions (being well-behaving enough) admits these series representations known as Taylor expansions. Don't worry, we won't really have to worry about those pesky Calc 1 problem-sets; I'm just merely pointing out that these functions can be represented as the sum \begin{align\*} w(a, b) &= \sum\_{i,j} w\_{ij} a^i b^j \end{align\*} so that $w\_{ij}$ gives the number of words that satisfies $w$ such that it has exactly $i$ occurrences of $a$ and $j$ occurrences of $b$. However, we don't particularly care about whether something is an $a$ or a $b$. Rather, we just care about the total number of characters in the string. To turn a "blind eye" between $a$ and $b$, we can just (literally) treat them the same, e.g. let $z = a = b$ and get $$ w(z) = w(z, z) = \frac{z}{1 - z - z^2} = \sum\_k w\_k z^k $$

where $w\_k$ counts the number of satisfiable words of length $k$.

Now, all that's left to do is to find $w\_k$. The usual combinatorial approach here would be to decompose this rational function into its partial-fraction: that is, given the denominator $1 - z - z^2 = (z - \phi)(z - \psi)$, we can rewrite $\frac{z}{(z - \phi)(z - \psi)} = \frac{A}{z - \phi} + \frac{B}{z - \psi}$ (There's a bit of algebra involved here, but this is a universal property of rational (one polynomial dividing another) functions). To solve this, you can refactor $$ \frac{A}{z - \phi} + \frac{B}{z - \psi} = \frac{z}{(z - \phi)(z - \psi)} $$ which generates the constraints $A + B = 1, A\psi + B\phi = 0$. Irregardless of what $A$ and $B$ are, recall that $\frac{1}{1 - x} = 1 + x + x^2 + \dots$, well, we can rearrange \begin{align\*} w(z) &= \frac{-A}{\phi - z} + \frac{-B}{\psi - z} \\ &= (-A\phi)\frac{1}{1 - \frac{z}{\phi}} + (-B\psi) \frac{1}{1 - \frac{z}{\psi}} \\ &= (-A\phi)\left(1 + \phi^{-1} z + \phi^{-2} z^2 + \dots\right) + (-B\psi)\left(1 + \psi^{-1} z + \psi^{-2} z^2 + \dots\right) \end{align\*} therefore $$ w\_k = (-A\phi)\phi^{-k} + (-B\psi)\psi^{-k} $$ Here, $\phi$ is the golden ratio $\frac{1 + \sqrt{5}}{2}$ and $\psi = -\phi^{-1}$ is its conjugate. We then have an easy description of the asymptotic behavior of the $w$ language: it runs in $\Theta(\phi^n)$. In fact, if you expand everything out, you'll find that $$ w\_k = \frac{\phi^{k} - \psi^{k}}{\sqrt{5}} = \left\lceil \frac{\phi^{k}}{\sqrt{5}} \right\rceil $$ There's also an intricate connection to another common combinatorial class. This is just the Fibonacci numbers!

Now, suppose you have $w\_k$, which counts the number of strings of size $k$ that starts and ends with $k$ (and also contains no $aa$ substrings), how can we build a string that can start or end with an $a$? Well, it's simple: an admissible string is either in $w$ (starts and ends with $b$), or it is $a w$ (starts with $a$), or it is $w a$ (ends with $a$), or it is $a w a$ (starts and ends with $a$). Therefore: $$ f(n) = w\_n + w\_{n-2} + 2 * w\_{n - 1} $$ Recall that $w\_n$ is the fibonacci sequence, so $w\_{n-1} + w\_{n-2} = w\_n$, which means that \begin{align\*} f(n) &= (w\_n + w\_{n-1}) + (w\_{n-2} + w\_{n-1}) \\ &= w\_{n+1} + w\_{n} \\ &= w\_{n+2} \end{align\*} Therefore, $f(n) = \text{fib}(n + 2) = \left\lceil \frac{\phi^{n+2}}{\sqrt{5}} \right\rceil$

Now you probably don't have to do this analysis, but just by having the insight that this sequence is a shifted Fibonacci sequence ought to give you an idea of some other combinatorial interpretations that you can try.

# Answer
> 7 votes
Lee Gao's answer is excellent. Here is a different account. Consider the following automaton:

This is an *unambiguous finite automaton* (UFA) without $\epsilon$ transitions: an NFA such that each word has exactly one accepting path. The number of words of length $n$ is thus the number of paths of length $n$ from the starting state to an accepting state (since there are no $\epsilon$ transitions).

We can count the number of paths in a graph using linear algebra. Let $M$ be the *transition matrix* of the automaton: $M(q\_i,q\_j)$ is the number of arrows from $q\_j$ to $q\_i$ (each arrow is associated with a *single* symbol). Then $$ M^2(q\_i,q\_j) = \sum\_k M(q\_i,q\_k) M(q\_k,q\_j), $$ which is exactly the number of paths of length 2 from $q\_j$ to $q\_i$. Similarly, $M^n(q\_i,q\_j)$ is the number of paths of length $n$ from $q\_j$ to $q\_i$. In our case, we want to count the number of paths of length $n$ from $q\_0$ to $\\{q\_0,q\_1\\}$, and so $$ f(n) = \begin{pmatrix} 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \end{pmatrix} \\, . $$ The standard way to calculate such an expression is by diagonalizing $M$ (or, more generally, by computing the Jordan form of $M$). The eigenvalues of $M$ are easily calculated to be $\frac{1 \pm \sqrt{5}}{2}$, and so for some matrix $P$, $$ \begin{align\*} f(n) &= \begin{pmatrix} 1 & 1 \end{pmatrix} P \begin{pmatrix} \left(\frac{1+\sqrt{5}}{2}\right)^n & 0 \\ 0 & \left(\frac{1-\sqrt{5}}{2}\right)^n \end{pmatrix} P^{-1} \begin{pmatrix} 1 \\ 0 \end{pmatrix} \\ &= A \left(\frac{1+\sqrt{5}}{2}\right)^n + B \left(\frac{1-\sqrt{5}}{2}\right)^n, \end{align\*} $$ for some coefficients $A,B$. To determine $A,B$ we can either diagnoalize $M$ explicitly, or just set up a linear system using known values of $f$. Since $f(0) = 1$ and $f(1) = 2$, the latter approach shows that $$ A + B = 1 \\ \frac{1+\sqrt{5}}{2} A + \frac{1-\sqrt{5}}{2} B = 2 $$ Solving this system (e.g. using Gaussian elimination), we find out that $A = \frac{5+3\sqrt{5}}{10}$ and $B = \frac{5-3\sqrt{5}}{10}$. Therefore $$ \begin{align\*} f(n) &= \frac{5+3\sqrt{5}}{10} \left(\frac{1+\sqrt{5}}{2}\right)^n + \frac{5-3\sqrt{5}}{10} \left(\frac{1-\sqrt{5}}{2}\right)^n \\ &= \Theta(\lambda\_{\max}^n), \text{ where } \lambda\_{\max} = \frac{1+\sqrt{5}}{2}. \end{align\*} $$ The same approach works for every regular language.

# Answer
> 4 votes
@Lee Gao's is too complex (I haven't even read the whole thing), here is a simplistic approach:

Let f(n) be all desired strings out of which let a(n) be strings that end at a and b(n) be strings that end at b.

Now for every string that ends at b we can directly add a to get ba in ending and a valid string: $$a(n)=b(n-1)\tag{1}$$ Note than we cannot add a to end of strings that end at a otherwise we will have aa at the end.

We can add b to any string: $$b(n)=a(n-1)+b(n-1)\tag{2}$$

Now $n\mapsto n-1$ in $(1)$ and substitue in $(2)$: $$b(n)=b(n-2)+b(n-1)$$ So b(n) is fib(n) and since a(n) is b(n-1) hence a(n) is fib(n-1). Now f(n) is: $$f(n)=a(n)+b(n)={\rm fib}(n)+{\rm fib}(n-1)={\rm fib}(n+1)$$ As fib(n) is $(\varphi^n-\varphi^{-n})/\sqrt{5}$, hence f(n) is ${\rm O}(\varphi^n)$, $\varphi=\frac{1+\sqrt{5}}{2} \approx 1.618$. (Taking $\varphi/\sqrt5$ as constant and neglecting $\varphi^{-n}$ for large $n$ to get an asymptote)

**Note:** fib(0)=0, fib(1)=1.

---
Tags: asymptotics, combinatorics, upper-bound
---


# Question
Title: Remapping values to bias a uniform set towards a certain curvature
I'm trying to generate random numbers that would be distributed according to a sample curve that I provide in the shape of vertices.

I came up with this:

```
function curve_map(curve) {
    //  convert to sorted points
    var points = [];
    for (var x in curve) { var y = Number(curve[x]);
        points.push( {'x' : Number(x), 'y' : y} );
    }
    points.sort(function(a,b) {return a.x - b.x});

    //  create segments
    this.segments = [];
    var posy = 0;
    for (var i = 1; i < points.length; i++) {
        var n = points[i].y + points[i - 1].y;
        var seg = {
            'x0' : points[i - 1].x,     'x1' : points[i].x,
            'y0' : points[i - 1].y,     'y1' : points[i].y,
            'n0' : posy,                'n1' : posy + n
        };
        posy = seg.n1;
        this.segments.push(seg);
    }

    //  normalize n
    for (var i = 0; i < this.segments.length; i++) {
        this.segments[i].n0 /= posy;
        this.segments[i].n1 /= posy;
        this.segments[i].nr = this.segments[i].n1 - this.segments[i].n0;
    }

    //  func
    this.apply = function(x) {
        for (var i = 0; i < this.segments.length; i++) {
            var seg = this.segments[i];
            if (x >= seg.n0 && x <= seg.n1) {
                var along = (x - seg.n0) / seg.nr;
                //along = seg.y0 / (seg.y1 - seg.y0);

                var val = seg.x0 + (seg.x1 - seg.x0) * along;
                return val;
            }
        }
    }.bind(this);
}

```

What this does is

1. take 2 points and make a segment, preserving the original coordinates
2. each segment's length is equal to the sum of Y of both points
3. after creating a segment between all the points, normalize so the chain of segments reaches from 0 to 1

So now I have a chain of segments. If I feed it a value, it looks up which segment it belongs to, checks how far along in the segment it is and remaps the location to the original interpolated x coordinates of the segment.

In theory I expected this to shave off the corners of the original curve since I don't know how to account for the difference in Y values in each segment.

Anyways, the result is quite different:

The red curve is what I fed the "curve\_map" and what it should mimic

The black one is ~10k uniformly distributed random values put through the algorithm.

At least it *sorta* follows the line... but this is nowhere near good enough. Also I'm out of ideas on how to fix it.

Does anybody know if what I'm trying to do actually has a name? So I could read up on it or maybe find a neat algorithm to port..

# Answer
For continuous distributions, you can use the inverse transform sampling method. See also https://stats.stackexchange.com/q/176955/2921 and https://en.wikipedia.org/wiki/Ziggurat\_algorithm.

For discrete distributions, you just generate a random floating point number in the range \[0,1\], and then figure out which of the buckets $\[0,p\_1)$, $\[p\_1,p\_1+p\_2)$, $\[p\_1+p\_2,p\_1+p\_2+p\_3)$, ..., $\[..,1\]$ it falls into, where $p\_1,p\_2,p\_3,\ldots$ are the desired probabilities of the possible values. See also https://stats.stackexchange.com/q/26858/2921 and http://www.keithschwarz.com/darts-dice-coins/.
> 1 votes

---
Tags: algorithms, randomness, random-number-generator
---


# Question
Title: Clarifications about CPU working: as the functions to get the operands are physically generated?
I ask patience to help me to have clarity because I tend to equivocate between **formal rappresentation** like

`like operator is a token
bit
it is determined which operation is to be performed and how to get the operands, according to a function whose domain consists...`

and what is **physically-electronic-logic rappresentation** CPU elements operation like

```
CPU configuration signal
Registers
pulses

```

about some with respect to certain specific technical processes. The cause is related to mixing high bit, operator, operand when it working like functions.

I don't what mean for 'value' - what is this 'value' ? A logic state, adressing mode? i don't understand why operands may as a constant value

`Often, one group of bits (that is, a "field") within the instruction, called the opcode, indicates which operation is to be performed, while the remaining fields usually provide supplemental information required for the operation, such as the operands. Those operands may be pecified as a constant value`

What it mean 'pulses' ? I don't understand well the connection of bit like rappresentation and its physical state version. This pulses are generated about what electronic component ?

`the control unit produces the sequence of pulses on each control signal line required to implement that instruction`

I really don't understand if this functions are math or logic states about operand assembly (decode).

`Operand Assembly: once the word has been taken from memory, it is determined which operation is to be performed and how to get the operands, according to a function whose domain consists of the operating codes (typically the high order bits of the word) and the co-domain consists of the microprogram to be executed`

But..as these functions are generated to get the addresses from which electronic element ? Registers ? Addressing Mode ? I don't understand if it refers about instruction sets, a part of the architecture or if one process?

I don't understand well this electronic logic passage. Hardwired ? Multiple clock pulses ? Is there some link to understand better this ?

`In some CPU designs the instruction decoder is implemented as a hardwired, unchangeable circuit. In others, a microprogram is used to translate instructions into sets of CPU configuration signals that are applied sequentially over multiple clock pulses. In some cases the memory that stores the microprogram is rewritable, making it possible to change the way in which the CPU decodes instructions`.

what is configuration signals physically-logic ?

```
is used to translate instructions into sets of CPU configuration signals

```

But it is done by the ALU or not?

I don't understand Microcode

`The microcode is a layer of hardware-level instructions that implement higher-level machine code instructions or internal state machine sequencing in many digital processing elements`

Operand: numerical data on which the product is an arithmetic or logic

I understand mean of high-order bit and high word http://www.gamedev.net/topic/414290-please-explain-high-and-low-order-bitword-terminology/

I understand what is *word* http://whatis.techtarget.com/definition/word

and is ok also operand definition (wiki) but I don't understand WHAT THEY ARE like LOGIC\_PHYSICALLY ? **How they are made to logical-physical level?**

I don't understand why defined bit length of a word is equivalent to the width of the computer's data bus so that a word can be moved in a single operation from storage to a processor register.

# Answer
It seems that you have two texts here, one talking about CPUs in the most clumsy way imaginable, and one sounding like a quite reasonable text book, and you can't get the terms of that clumsy text explained by the text book.

I suggest you read that text book, and that text book alone, because the other text isn't going to help your understanding at all. Something like "the control unit produces the sequence of pulses on each control signal line required to implement that instruction" sounds like someone with no understanding at all trying to hide behind big words.
> 2 votes

---
Tags: cpu
---


# Question
Title: A special case for the subset sum problem: selecting from powers of two
Given a multiset $X=\\{x\_1,\dots,x\_n\\}$ where every element $w\_i$ is a power of two, and given an integer $M$, I'd like to determine if there is any subset of $X$ that sums to $M$.

(This question is based on a previous question about the subset problem where every number in the set is a multiple of two, but this time $X$ consists only of **powers of two**.)

Can we find an efficient algorithm for this problem? Could we make it any better than standard algorithms for subset sum or knapsack?

# Answer
First, look at the bits that are set in $M$ and write it as $M = m\_1+m\_2+\dots$ where each $m\_i$ is a power of two and such that $m\_1$ is the smallest power of two, and so on.

If the numbers $x\_i \in X$ are *distinct* powers of two and you can use each one zero or one times, the problem is trivial: If all $m\_i$ are found in $X$, then $M$ can be formed by them, otherwise it can't. This is because missing powers of two can't be formed by a) any combination of larger powers of two or b) distinct smaller powers of two.

If the numbers $x\_i$ aren't guaranteed to be distinct, it's a bit more complex. Missing powers of two still can't be formed by larger powers of two, but they can be formed by non-distinct smaller powers of two.

Let's look at how smaller powers of two can form larger powers of two. If you have powers of two $A = \[a\_1, \dots, a\_n\]$ that are smaller than a power of two $N$, and $S=\sum\_{i=0}^n a\_i$, then $N$ can be formed by them iff $S \ge N$. Let $b$ be the smallest power of two in $A$ and $c$ its number of occurences in $A$. If $c$ is odd, one $a\_i=b$ can't combine with anything to form a higher power of two and the corresponding bit will be set in $S$. The others can be replaced with $\lfloor \frac{c}{2} \rfloor$ copies of the number $2b$ in $A$. If we continue this with higher powers of two until we get to $N$, we find that we can form $\lfloor \frac{S}{N} \rfloor$ copies of $N$ with $A$.

So, start with $m\_1$. If it's found in $X$, we remove it and move to the next power of two. If it's not, we calculate the sum $S$ of all $x\_i$ smaller than $m\_1$ and remove them from $X$. If $S \lt N$, then $M$ can't be formed by $X$. Otherwise, we add $\lfloor \frac{S}{m\_1} \rfloor - 1$ copies of $m\_1$ to $X$ and continue in the same manner with the next smallest power of two in $M$.
> 2 votes

---
Tags: algorithms, complexity-theory, knapsack-problems
---


# Question
Title: What's the meaning of the $\top$ symbol in a Hoare triple?
I'm studying program verification and came across the following triple:
$$ \\{\top\\} \\;P \\; \\{y=(x+1)\\} $$ What's the meaning of the $\top$ symbol on the precondition? Does it mean $P$ can take any input?

# Answer
The symbol $\top$, known as *top*, stands for "True". There is also a symbol $\bot$, known as *bottom*, which stands for "False". Top is always true, and bottom is always false. In your case, having a precondition that always holds is the same as having no precondition.
> 2 votes

---
Tags: software-verification, hoare-logic
---


title: Group points by given shapes

text:
# Question
Title: Group points by given shapes
I am using a sensing board able to detect magnetic signals between the board and a display.

I have a set of objects that are represented (each of them) by a unique set of points (magnets) with a particular shape. For example: object #1 is made by three points that form an equilateral triangle with side length 1cm; object #2 is made by three points that form a right triangle with sides 3cm, 4cm, 5cm; object #3 is made by three aligned points with distance 2cm; and so on. I can have a multiplicity of objects with unique patterns.

Now I have a list of points with the coordinates w.r.t. the Cartesian plane, and I need to match them referring to the patterns I got from the objects. I also know that every point must be matched, therefore I can minimize the overlapping errors. In practice, every point in the set can belong to maximum one object, and at the same time also it must belong to an object of the initial set.

Any idea on how to do that in an efficient way?

# Answer
In the general case a problem like this is NP, however in the vast majority of real cases it should be easy.

20 points make 1140 triangles so it shouldn't be hard to pick out the triangles most similar to your basic shapes (unless the shapes can be more complicated). A little ugly backtracking may be needed when the top scoring triangles overlap.

Also, if most magnets move continuously, you can easily map old points to new points and old triangles to new triangles.

What I'm talking about are fairly obvious methods. There may be smarter ways to do this, but you don't necessarily need them.
> 0 votes

---
Tags: computational-geometry
---


title: CNF form of variable assignment problem

text:
# Question
Title: CNF form of variable assignment problem
There are n variables $x\_1$, $x\_2$,..., $x\_n$ and each one of them takes values from 1 to k (k\>= n) and all are distinct. How can I represent this in the CNF form? (I tried the trivial way of trying all assignments and then checking if they are distinct, but I think it could be done better)

# Answer
If you only have to encode this (and don't have any other constraints on $x\_i$), you can then use the following constraints: $x\_1 \< x\_2 \< \dots \< x\_{n-1} \< x\_n \leq k$ which is $n$ constraints.

Let $m=\lceil \log\_2 k\rceil$ and $x\_i = b\_{im}, b\_{i(m-1)}, \dots, b\_{i1}$, where $m$ is the high bit and $1$ is the low bit. Define $d\_{ij} = b\_{ij}\textrm{ XOR }b\_{(i+1)j}$. Then, the constraint $x\_1 \< x\_2$ is representable as: $$ \bigvee\_{i=1}^{m} \left\[\left(\bigwedge\_{j=i+1}^m d\_{1j}'\right)\left(b\_{2i}b\_{1i}'\right)\right\] = 1 $$ basically the i-th clause encodes that the top $m-i$ bits are identical and the $i$-th bit is $1$ in $x\_2$ and $0$ in $x\_1$.

Abusing notation slightly (taking the constants in the representation of $k$ for $x\_{n+1}$), a similar technique can be used for $x\_n \leq k$, where one would add an extra clause $\bigwedge\_i d\_{ni}'$ for handling the equality.

The above formula is a DNF. To get to CNF, one would simple encode $\textrm{NOT}(x\_2 \leq x\_1)$.

Finally, if it's needed to represent $x\_1 \geq 1$ one can do this by adding a CNF clause $\bigvee\_i b\_{1i}$.

Note that the complexity here is really good. $O(nm)$ clauses, and $O(nm^2)$ literals. In particular if $n$ and $k$ are large this is much better than for other techniques (but it isn't applicable in other settings where other constraints could change the ordering).
> 2 votes

# Answer
This is sometimes known as an "alldiff" constraint. There are some encodings listed here: Requiring at least one alldiff constraint to be satisfied converted to SAT.

Alternatively, you might do better to use a CSP solver, rather than trying to express this in CNF and then use a SAT solver. Handling "alldiff" constraints is exactly the sort of thing that constraint satisfaction solvers are designed to do well. See When to use SAT vs Constraint Satisfaction?.

Also relevant: Encoding 1-out-of-n constraint for SAT solvers, Reduce the following problem to SAT.
> 0 votes

---
Tags: optimization, modelling, normal-forms, assignment-problem
---


# Question
Title: Running time of an algorithm containing binary elements for cryptography
Hey guys sorry I'm new to cs and I'm trying to find the running time of algorithms... could you tell me about the algo given how much time is needed in terms of complexity? The actual algo I created is the same as below but the sum must be more or equal to 2^(n-2).Thank you\]

# Answer
> 0 votes
We take only one step for computing each $2^ix\_i$ (By using left-shift operation we can compute $2^i$ in constant time). So the complexity of Algorithm $\mathcal{A}$ is $\mathcal{O}(n)$.

I suspect you used loop for computing $2^i$, and this incurred your bad result.

PS : sorry for my bad english

---
Tags: complexity-theory, time-complexity, runtime-analysis
---


# Question
Title: Show that the diameter of a MST is sometimes larger by a factor $\Omega(n)$ than the diameter of the graph $G$
As my title points out, I don't understand how do you show that, in general, the diameter of a MST (minimal spanning tree) can be bigger than the diameter of G, by the factor $\Omega(n)$. $(n:= |V|, G =(V,E)) $.

And I don't understand, how big is $\Omega(n)$ and why $\Omega$?

I made a example where the distance of two nodes in $G$ is smaller than the distance of the two nodes in the MST.

Is it correct to write,

* $D\_{MST} = D\_{G} \cdot \Omega(n)$ ?
* $\Omega(n) = D\_{MST}/D\_{G}$ ?

$D\_{G} =$ diameter of graph $G$ and $D\_{MST} =$ diameter of MST.

# Answer
> 1 votes
You say that you don't understand how to show that the diameter of a MST can be $\Omega(n)$ larger than the diameter of the underlying graph.

However, it seems that what you don't understand is what it *means* that the diameter of a MST can be $\Omega(n)$ larger than the diameter of the underlying graph.

It is impossible to prove a theorem if you don't understand its statement.

Here is what you are asked to do. Given a weighted graph $G$, we will use the following notation:

* $n(G)$ is the number of vertices in $G$.
* $D(G)$ is the diameter of $G$.
* $D\_{MST}(G)$ is the minimum diameter of a minimum spanning tree of $G$.

> Give a sequence of graphs $G\_i$ such that $n(G\_i) \to \infty$ and $D\_{MST}(G) = \Omega(n(G)) \cdot D(G)$.

It seems that you are not familiar with the notation $\Omega(\cdot)$. It is the counterpart of big O, and described in the answers to this question.

Unpacking the big $\Omega$ notation, we can rephrase the question:

> Give a sequence of graphs $G\_i$ such that $n(G\_i) \to \infty$ and there exists a constant $C\>0$ such that $D\_{MST}(G\_i) \geq C n(G\_i) D(G\_i)$.

The question is somewhat ambiguous – it's not clear if you need to provide an example for *every* $n$ or just for *infinitely many* $n$. I assumed the latter, but in fact in your case there is a sequence $G\_i$ with $n(G\_i) = i$, so you can try proving this stronger statement instead.

---
Tags: graphs, spanning-trees
---


# Question
Title: PDA and CFG of language of regular expressions
I am stuck on a problem involving PDA's and CFG's. The problem is as stated:

> Give a CFG and a PDA for the language of regular expressions over the alphabet $\\{a, b, c\\}$. Give the formal tuple definition of each. You may use the shorthand for pushing a string in the state diagram of your PDA, but not in the tuple form. It will help if you expand out the shorthand in the state diagram. To avoid ambiguity, use the symbols $($, $)$, $λ$ for the language. The alphabet should be $\\{a, b, c,(,), +, λ,∗ \\}$. For brevity, you can define $δ$ by giving its output on the inputs that don’t return $∅$. Something like $δ(x\_1) = y\_1; δ(x\_2) = y\_2;$

My first attempt at it got me stuck after defining the Context Free Grammar and the PDA. I am having trouble understanding how this grammar could, for instance,

* Derive $(a + b)^\*(c + λ)a^\*$
* Make a PDA for this.

How can I make a PDA for this? How can I make a CFG for this?

# Answer
*Hint:* Let us assume an alphabet $\Sigma$. Now, the following are regular expressions (at least according to some textbooks):

* $a$ is a regular expression, if $a \in \Sigma$
* $\emptyset$ is a regular expression
* $r\_1 \cup r\_2$ is a regular expression, if $r\_1$ and $r\_2$ are regular expressions
* $r\_1 \circ r\_2$ is a regular expression, if $r\_1$ and $r\_2$ are regular expressions
* Nothing else is a regular expression.

How can you summarize these formation rules as a collection of context-free production rules where $r$ is a nonterminal?
> 1 votes

---
Tags: context-free, automata, pushdown-automata
---


title: Static vs dynamic allocated arrays

text:
# Question
Title: Static vs dynamic allocated arrays
I am trying to learn CS fundamentals and I am confused by static vs dynamic allocated arrays. My only programming experience is JavaScript and all online resources I am using refer to C language.

A dynamic allocated array is made when the application starts and it cannot be resized. So how is this different from static allocated array, if to expand the array you have to make a new and bigger array and copy over the contents?

# Answer
No, a dynamically allocated array is created when the program creates it, in the size the program wants to create it, and it exists until the point of time when the program destroys it.
> 2 votes

---
Tags: data-structures
---


# Question
Title: On complexity of the sieve, start crossing at the square of $p$
This question is about a common optimization in the basic sieve of Erathostenes.

If we look at this paper (page 3, footnotes), the author says:

> If we start crossing off at $p^2$ rather than $p$, the number of composites we cross off is $\frac{n}{p}−p+1$, but it makes no significant difference to our sum, because it only subtracts an irrelevant $O(n/ \log n)$ factor

Similarly, I have seen the same conclusion in other places, so according to them we have that the total cost counting crossings is about (ignoring the $\sqrt n$ optimization):

$\sum\_{p\leq n}(\frac{n}{p}-p+1)$

Where $p$ is prime.

But if we look at this algorithm (in pseudocode) implementing this same optimization:

```
//omitting sieve[2..n] initialization
for p:=2 to n
   if (sieve[p] is prime)
      for k:=p^2 to floor(n/p)
         sieve[k*p] := not prime     //cross multiples of p

```

I would say the total cost is:

$\sum\_{p\leq n}(\frac{n}{p}-p^2+1)$

because the cost of the inner loop is

$\sum\_{k=p^2}^{\frac{n}{p}}=\frac{n}{p}-p^2+1$

Am I wrong?

# Answer
> 5 votes
Your algorithm is wrong. The starting point should be $p$ rather than $p^2$, since in the body of the loop $k$ gets multiplied by $p$.

---
Tags: algorithm-analysis, time-complexity
---


title: how can a program be OS-dependent?

text:
# Question
Title: how can a program be OS-dependent?
I know the fact that you cannot run the same machine code on two different machines,

so the software must be **machine dependent** (i.e Arm program cannot run on either powerpc or x86).

but in reality the software is **OS dependent** (i.e linux programs cannot run on windows or mac).

how does this happen? my best guess for now is that every OS behaves like a virtual machine and the source is compiled for windows-machine,may be?? and this machine has its own assembly code?

# Answer
> 1 votes
You're asking a different question in the body than the title. I'll answer the question "how can a program be OS-dependent?".

There is no universal definition of an OS. At the very least you need a kernel (even then, are we building a monolith or microkernel?), but an OS also usually comes with standard (C) libraries and programs (including service daemons).

If a program uses dynamic linking to depend on a certain standard library (say the C math library), then we need to run on an OS on which that library is available. Likewise, a program may try to interact with other programs through IPC mechanisms, and if they're not running then the program will fail.

Even if we only make use of the kernel, different kernels may e.g. use different IPC mechanisms, and a program written using unix pipes will certainly not work on Windows.

# Answer
> 5 votes
Operating systems have Application Programming Interfaces, whose functionalities are available as libraries that are linked to the code produced by the programmer.

This does not mean they constitute virtual machines. They just encapsulate operations that are not directly accessible to the programmer, either because they depend on low level instructions or protocols that are protected, or because they are provided as high-level standard services.

What happens is simply that what you write in a language that compiles to machine code is only a part of what will be running. Usually a very small part.

---
Tags: computer-architecture, operating-systems
---


# Question
Title: Understanding details of NP-Hard definition
I am learning from this video: https://www.youtube.com/watch?v=eHZifpgyH\_4 at 21:17 he talks about his definition of NP-Hard.

The definition is: X is NP-Hard if every problem y which belongs to NP reduces to X.

I watched that part of the video several times but don't understand it. In particular, here's one thing I don't get:

P is also a part of NP so when we say every problem y which belongs to NP we are saying we can take a problem in P and reduce to some X. Then X is NP-Hard? That would mean that y we just converted would have an NP-Hard solution but it is actually polynomial? Sorry if this is confusing. I hope I can word it better but it to me that definition only makes sense if they talk about NP problems that are not part of P

# Answer
The definition of **NP**-hardness for a problem $X$ is that every problem in **NP** reduces to $X$. Informally speaking, "$L$ reduces to $X$" means that if you could solve $X$, you could use that to solve $L$.

So, if $X$ is **NP**-hard, you can reduce all problems in **NP**, including the ones in **P**, to $X$. There's no contradiction here: $X$ is a hard problem, so saying that you can reduce a problem in **P** to $X$ is just saying, "If I could solve this hard problem, I could use that to solve a pretty easy problem." Sure, there are easier ways of solving that easy problem (that's why we call it an easy problem!) but all you've done is to show that there's a hard way to solve it, too.

> P is also a part of NP so when we say every problem y which belongs to NP we are saying we can take a problem in P and reduce to some X. Then X is NP-Hard?

Maybe it's just inaccurate writing but you have the implication the wrong way around. *If* $X$ is **NP**-hard, *then* you can reduce a problem in **P** to $X$. The converse (if you can reduce a problem in **P** to $X$, then $X$ is **NP**-hard) is not true.
> 6 votes

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