# Question
Title: How to determine the maximum valued play in Rummikub?
This question is meant as a follow-up this question and my answer here.

The question asked multiple questions about algorithms for playing Rummikub and my answer provided an algorithm that, given a set of Rummikub pieces $S$, determines whether they can be arranged as a set of valid plays (called an *arrangement*).

However, when we actually play Rummikub, the situation is slightly different: there is a given board state $B$ and a hand $H$. We want to empty our hand by adding pieces to the board. We assume the board $B$ has a valid arrangement.

So, the problem now becomes:

> 1. Does there exists a subcollection $S\subseteq H$ such that there exists a valid arrangement for $S \cup B$; and
> 2. What is the largest such subcollection $S$ ?

Obviously, we can iterate over every subcollection $S$ of $H$ and test validity for each of them, but that is inefficient. To make precise what I mean by 'efficient' here, consider the game to be played with $3,4$ or $5$ colours and the numbers $1\ldots n$ for each color.

Does there exist an polynomial (in $n$) time algorithm that solves problem 1 or 2? Or this 1 or 2 intractable (e.g. NP-hard)? Feel free ignore complications such as jokers or assume all tiles are distinct.

# Answer
> 2 votes
I will describe a polynomial time algorithm that solves both problem 1 and problem 2. I learned of the algorithm from this paper.

I am going to make the following assumptions:

1. No jokers (adding them is a small change).
2. There are only four colors.
3. There are at most two copies of each tile.
4. The face values range from 1 to 13.

To find the maximum value play, complete these steps:

1. Recursively enumerate every valid configuration that can be built from tiles in $hand \cup board$
2. Ignore any configuration where not all tiles from board are used (the **board constraint**).
3. Of the visited configurations, choose one with maximal score. Where score is the sum of values of tiles played or number of tiles played (whichever you prefer to maximize).

# Step 1

How do we build a configuration from a given set of tiles? We proceed by playing tiles in order of their face value. First play all tiles of value 1. Then play all tiles of value 2, and so on. We can visit every configuration by recursing for each way to play tiles of the current value.

Let's look at the different ways to form runs. Assume we are playing tiles of value 5, that we have a red 5, and that we will use it in a run. Our tile can be used to start a new run or it can be used to extend any existing run (or partial run) that contains a red 4. If we extend an existing run then there is at most two choices for where to put it since there is at most two runs that contain a red 4 (there are at most two red 4's). If we have two copies of our tile then we can extend or start two runs.

In forming runs there is an optimization that can be made. We should not start a new run if we know in advance that there is no way we could finish the run. This can be implemented by counting the number of tiles of greater value.

Now on to forming groups. For a given way to play runs we should recurse for every way to play groups using the remaining tiles since we want to enumerate all possible valid configurations. However this would be very slow and in the end we really only care about finding the best configuration. So instead we recurse for only the best way to play groups. Notice, for a given choice of how to form runs, how we form groups does not effect what choices we have in forming groups and runs using tiles of greater value. So given a choice of how to form runs, we should use as many of the remaining tiles in groups as possible. To do this enumerate all ways to pick groups and choose the one containing the most tiles.

Finally after choosing how to play all tiles, discard any tile not used in a valid set.

# Step 2

How do we ensure every valid configuration we visit uses all tiles from board? After choosing how to play all tiles and discarding invalid sets, do not accept the configuration as valid if not all tiles from board are contained in it. This is correct but it would be inefficient. Instead we check at each step, after choosing how to form runs and groups, whether we have used enough tiles of the current value. For example, if the current value is 5 and we have chosen a way to play the red 5's, then we need to check if we have played at least as many red 5's as are contained in board. If we have not, then we choose another way to play red 5's before moving to the next value. Note if we have played $n+m$ red 5's where $n$ is the number of red 5's in board, then we have played $m$ red 5's from our hand. If there is no way to play red 5's (including not playing red 5's) then this branch of the recursion tree does not lead to a valid configuration and we should return.

However, these checks are not sufficient to guarantee we never violate the board constraint. Why? Because when forming runs using tiles of value 6 we can choose to not extend a run that has length one or two. The tiles in that run would have to be discarded which could violate the board constraint due to not having enough 4's or 5's. In this case we would not be able to catch this error because so far we only know how to check the board constraint for the current value. The way to fix this is to keep count of how many tiles we have played of the previous two values (for each color separately). Then when forming runs with red 6's we can check if not extending a red run (of length one or two) puts us in a state where not enough red 4's or 5's have been played. Note that if a run has length at least three then not extending it does not force us to discard any tiles and so can not violate the board constraint (so we do not have to check in this case).

We do not have to do anything special for choosing groups. In the following proof of this I will use 'configuration' to mean a set of groups. Also, I will use 'maximal configuration' to mean a configuration containing the most tiles possible among all configurations where tiles come from some set $S$. Note that if we have $n$ tiles of color $c$ in a configuration then there are at least $n$ groups in the configuration. Also if a subset of the available tiles can be arranged into a configuration of $n$ groups then a maximal configuration contains at least $n$ groups (there are at most three groups, if using two jokers, and at most two groups of four in any configuration). Now assume a subset $S$ of the available tiles can be arranged into a configuration with $n$ tiles of color $c$ and that we have arranged some maximal configuration $M$. If $M$ contains $k \< n$ tiles of color $c$ then $M$ contains at least $n - k$ groups which do not contain a tile of color $c$ (groups of size three). In this case we can add $n-k$ tiles of color $c$ from $S$ to $n-k$ groups of three in $M$ which contradicts that $M$ is a maximal configuration. Thus $k\geq n$. This shows that if there are $n$ tiles of color $c$ in the set of tiles of current value that remain after playing runs and if those $n$ tiles can be played in some configuration then every maximal configuration contains those $n$ tiles. So choosing a maximal group guarantees that we satisfy the board constraint if it is possible to satisfy the board constraint by playing groups. TBH I do not know if the above "proof" is correct or not but I did brute force check that it is true for various Rummikub game parametrizations (4/5 colors, 2/3 tiles per color, 2/3 jokers). That it is true is kind of interesting to me because it boils down to a somewhat general sounding statement about multisets of integers.

# Step 3

A simple way to do step 3 would be to compute the score of a configuration when you accept it as valid then update some global variable with the configuration of max score ('configuration' meaning set of runs & groups). But this solves the same subproblem many times (compute score for sets common to more than one valid configuration). Instead make use of the fact that we know at each step how many tiles of the current value we will play. Multiply this number of tiles by the current value to find how much these choices contribute to the score. Sum the contribution with the return value of the recursive call and then update the max if necessary. Instead of updating a global max variable, we will update a local (available only in scope of recursive call) max variable which will hold the score of the best way to play tiles of the current value. The recursive function should return the value of this max variable. After attempting to play tiles of current value in all ways, if no play leads to a valid configuration (every play violates the board constraint), then return $-\infty$. Returning $-\infty$ is useful because even if we have a high contribution (from runs & groups), adding that contribution to $-\infty$ is still $-\infty$.

Note that we cannot know the contribution of extending a length zero or length one run. This is because, when playing tiles of the next greater value, we may choose to not extend a run of length one or two and so the tiles in those runs would be discarded. Instead we say the contribution of extending a length zero run (starting a run) or length one run is 0. When a run is extended from length two to length three then we say it's contribution is the sum of the values of the three tiles in the run. When extending a run that has length at least three then the contribution is just the value of the tile played into the run.

There are other things you can do here too. For example, It may be desireable to find a configuration that is maximally similar to the previous configuration of the board. This can be done by maximizing score and then maximizing some similarity function. This would inflate the dp table size by two.

# State, Memoization, & Time Complexity

The only state we need to know is the current value and the length of the runs that we could possibly extend. The length of runs can be recorded in a list of pairs, for example \[(0,0), (0,0), (0,1), (0,3)\], where the $i^{th}$ pair is the length of the two possible runs of color $i$. The order of the numbers in the pairs does not matter so the above state is the same as \[(0,0), (0,0), (1,0), (0,3)\]. A particular extension (i.e. child state) of those runs could be \[(1,1), (0,1), (0,0), (1,3)\]. Also, we never need to know if a run is longer than three tiles (so an extension of (3,3) is (3,3)). We will only need to distinguish between when a run is of length 0, 1, 2, or 3. A benefit of this is the size of the state space is reduced which makes memoization much more effective.

This algorithm is exponential in the number of distinct values in $hand \cup board$. However it can be made linear by memoization.

To memoize, store in a dictionary the key-value pair key=(currentTileValue, runLengthsList) and value=localMaxValue. Other inputs like the board, $hand\cup board$, number of jokers available, number of tiles played per color on the last two turns, etc, are just used to bound the search and so we do not need to memoize them.

Hopefully I have been able to effectively communicate most of the ideas of this algorithm. For more details see the paper and my implementation. Note, the paper claims that the dynamic programming state space (number of unique inputs, max size of dp table needed, i think) is of size $n * k * f(m)$. Where $n$ is the number of possible tiles, $k$ is the number of colors, $m$ is the max number of copies of a tile, and $f(x)$ computes 4 choose $x$ with replacement. This might be a typo, I do not know. In any case the state space of the algorithm I've described is $n * f(m)^k$.

Note both the paper and my implementation refer to what you call the board as the table.

By the way, before learning of this algorithm, I tried to understand the algorithm you gave here. I could not understand how to deal with duplicates. I can see how breaking into sublists, ordering those sublists, and then combining them into a single list again would allow your recursive formula to handle duplicates for some inputs. But you did not describe how exactly to break the original list into sublists nor how to combine them into a single list again. For some inputs, your recursive formula will give different answers depending on how sublists are split/recombined. Unfortunately, I do not have enough stackoverflow reputation to comment on your answer to ask for clarification. Thanks for giving the answer though, your recursive formula is nice.

# Answer
> 0 votes
I did not read your long answer at the linked thread. However, you did mention proceeding in order of number and using a recursive relation. You can do the same here. Define $Q(x,k,m)$ to be true iff there is a valid grouping $G$ of $B∪S$ for some $S⊆H$ such that exactly $k$ pieces in $S$ have numbers at most $m$ and $x$ is the multiset of colours of runs in $G$ that include the number $m$. Since there are a fixed number $c$ of colours, $x$ is encoded as a $c$-tuple of naturals with sum $O(n)$. Each state transition either stops or extends each of these runs (by adding an $m{+}1$), and may also form groups of $m{+}1$, such that all $m{+}1$-tiles from $B$ with number are used (either in extending runs or in forming groups), and the number of $m{+}1$-tiles used from $H$ are reflected in the change in $k$. I will leave the details as an exercise for you.

Also, there seems to be an incorrect assumption in your question, because the actual games rules do not allow arbitrary rearrangement of the played tiles. For instance, if the played tiles are the three sets 1a 1b 1c + 2a 2b 2c + 3a 3b 3c, then you cannot play 4a by rearranging the tiles to form 1a 2a 3a 4a + 1b 2b 3b + 1c 2c 3c. In other words, a solution to your question does not provide a solution to finding the maximal number of tiles that can be played given an actual game position. I did not check but I do think there is an algorithm along the same lines as above to solve that actual game-based problem.

---
Tags: algorithms, combinatorics, board-games
---


# Question
Title: Combinator terminology: What is "strong" about strong composition?
A strong composition operator seems to be very fundamental. (Hindley and Seldin use the notation S for "strong" composition combinator). It abstracts the pattern $f(x, g(x))$, i.e. a direct and a $g$-mediated effect of $x$. It's probably my inexperience but, why is this "strong"? Is it because normal (weak?) composition looks like a special case of this (where $f$ just ignores the argument $x$)?

I'm probably cheating and squeezing in another question here, but is there an intuition for why this form of composition seems to be the more fundamental one in combinatory logic?

# Answer
> 1 votes
I'm not familiar with the "strong" terminology. However, the 'obvious' answer to the other question is that it both duplicates the $x$ argument and exchanges the relative positions of (one copy of) the $x$ and $g$ arguments:

$$\mathsf s\ f \ g\ x = f\ x\ (g\ x)$$

The other combinator it's usually paired with:

$$\mathsf k\ x\ y = x$$

discards an argument. Together, this is all three of the structural rules for a variable context (contraction, exchange, weakening), *and* it includes composition as well.

---
Tags: terminology, combinatory-logic
---


# Question
Title: Is the minimum bottleneck spanning tree also a minimum spanning tree for an undirected graph with unique edge weights?
I can see a counterexample such as this:

But I can also see in some cases it could be the same. I am trying to understand what property makes a MBST also a MST?

# Answer
Let $G = (V,E)$ be the input graph. And, let $G\_{M} = (V,E\_{M})$ be an MST of this graph. First, note the following properties of the MST and BMST.

1. An MST is always a BMST
2. If all edges in the graph have distinct edge weights, there is always a unique MST.
3. Let $e$ be any edge in $E\_{M}$. Let $(S\_{e},V \setminus S\_{e})$ be the cut obtained after removing $e$ from the graph $G\_{M}$ and $C\_{e}$ denote the edges of $G$ that goes across this cut. Then, $e$ is the minimum weight edge among the edges in $C\_{e}$.

Following is the property that is required for a BMST to be an MST.

> **Property:** Every BMST is an MST if and only if for every $e \in E\_M{}$, all edges in $C\_{e} \setminus \\{e\\}$ have weight greater than $w$, where $w$ denote the weight of the bottleneck edge in a BMST or MST.

> **Proof:** First, let us prove the 'only if' direction.
>
> ($\to$) Suppose every BMST is an MST. For the sake of contradiction assume that there is an edge $e \in E\_{M}$ such that there exist an edge $e'$ in $C\_{e} \setminus \\{e\\}$ that has weight smaller than $w$. Let us remove $e$ from $G\_{M}$ and add $e'$ to $G\_{M}$. Let this new graph is $G\_{M}'$. It is easy to see that this graph is a BMST. However, it is not an MST since
>
> $$\begin{align} Total\\\_Weight(G\_{M'}) &= Total\\\_Weight(G\_{M}) - w(e) + w(e')\\ &\> Total\\\_Weight(G\_{M}) \end{align}$$ Here, I have used the fact that $w(e) \< w(e')$ by Property 3 of MST. This contradicts the fact that every BMST is an MST. This completes the proof of the 'only if' direction. Now, let us prove the 'if' direction.
>
> ($\gets$) Suppose for every $e \in E\_{M}$, all edges in $C\_{e} \setminus \\{e\\}$ have weight greater than $w$. For the sake of contradiction, assume that there is a BMST $G\_{B} = (V\_{B},E\_{B})$ that is not an MST. Therefore, we can say that there is an edge $e$ in $E\_{M}$ that is not in $E\_{B}$. Now, remove this edge form the graph $G\_{M}$ and let $(S\_{e}, V \setminus S\_{e})$ be the corresponding cut. Let $u$ be a vertex in $S\_{e}$, and $v$ be a vertex in $V \setminus S\_{e}$. Let $p$ be a path from $u$ to $v$ in $G\_{B}$. It means, there exist an edge $e' \in p$ that goes across the cut. In other words, $e'$ belongs to $C\_{e}$. Now, note that since $e' \in G\_{B}$, the weight of $e'$ is $\leq$ $w$. It contradicts the fact that all edges in $C\_{e} \setminus \\{e\\}$ have weight greater than $w$. This prove the 'if' direction. Hence the proof is complete.
> 1 votes

---
Tags: weighted-graphs
---


# Question
Title: Reducing the Hamiltonian cycle to the travelling salesman problem and self loops
If this is my adjacency matrix for the hamiltonian cycle: $$\begin{pmatrix}0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\\ 1&0&1&0\end{pmatrix}$$ Then a reduction algorithm to reduce this to a TSP problem is to introduce 1 anywhere an edge is missing and let pre-existing edges have a cost of zero (according to this), applying this yields: $$\begin{pmatrix}1&0&1&0\\ 0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\end{pmatrix}$$ Now I see that I have also introduced weighted-loops to my undirected graph, would asking whether this has a zero-cost salesman tour be equivalent to asking whether the unreduced version has a hamiltonian cycle, or should I maybe have something else on the diagonal of the reduced matrix?

# Answer
> 2 votes
Suppose your original graph $G$ has a Hamiltonian cycle $C$. Then the cost of the tour induced by $C$ in the new graph $G'$ you defined is indeed $0$ and conversely, any TSP tour of cost $0$ can only use edges of cost $0$ as you did not introduce any edges with a negative cost.

Adding the loops does not change this, so the reduction works out if we are willing to allow non-simple graphs which isn't done usually as the definition of the TSP asks for a tour visiting each vertex exactly once, i.e. no valid tour would include loop edges anyways. Given this, we also see that you can remove the loop edges in $G'$ to make it a simple graph to obtain an equally valid reduction. From a technical standpoint this doesn't make much of a difference but since people like simple graphs, I would personally prefer the reduction yielding a simple graph.

---
Tags: np-complete, reductions, np-hard, traveling-salesman
---


# Question
Title: Integer set disjointness query on sketches with something like homomorphic hashing
Suppose I have two sets of integers $A$ and $B$ and I have a sketch data structure described by a function $\mathsf{sketch}\_n : \mathcal{P}(\mathbb{Z}) \to 2^n$ that returns a bitstring of size $n$. These sketches can be checked for disjointness with a function $\mathsf{disjoint}\_n : 2^n \times 2^n \to 2$, where if $\mathsf{disjoint}\_n(\mathsf{sketch}\_n(A), \mathsf{sketch}\_n(B)) = 1$, then $A \cap B = \emptyset$ (but $A \cap B = \emptyset$ may also be true when $\mathsf{disjoint}$ returns 0, i.e.: no false positives).

This can easily be accomplished with a bloom filter, where $\mathsf{sketch}\_n$ is the result of inserting each element of the set into a bloom filter and $\mathsf{disjoint}\_n(x, y) = (x \\,\\&\\, y) \equiv \mathbf{0}$ ($\\&$ being bitwise AND).

Now, suppose that I want there to exist a function $\mathsf{shift}\_n : 2^n \times \mathbb{Z} \to 2^n$ such that $\mathsf{shift}\_n(\mathsf{sketch}\_n(X), \delta) = \mathsf{sketch}\_n(\\{x + \delta \mid x \in X\\})$. Is there a data structure that supports this operation, perhaps using some variety of homomorphic hashing?

Alternatively, $\mathsf{shift}\_n$ need not exactly return the same sketch as $\\{x + \delta \mid x \in X\\}$, but rather a different sketch that still has the no-false-positives property when checked for disjointness with another set.

I'm also willing to consider answers where we can't ensure no false positives, but there is a good bound on the probability of a false positive.

Also, wherever I've said $\mathbb{Z}$ here, feel free to interpret that as some finite set of integers (e.g.: 32-bit integers).

Bonus points if there is a way to compute the union of two sketches, and if there is a way to extend this to sets of tuples in $\mathbb{Z} \times 2^p$ where $\mathsf{shift}$ only affects the first element of each tuple.

# Answer
> 1 votes
If you use bijective hash functions, you can recover the original keys from filter structures like cuckoo filters or quotient filters. The reason is that these are essentially quotienting dictionaries, not just filters. The problem, of course, is that the values in the sketch have to come from a universe as large as your input - otherwise you must not have a bijection!

If you store $m$ items from a set of size $2^w$, the space usage is $m (w - \lg m)$ plus low-order terms, or $(1 + \Omega(1))m(w-\lg m)$ if you don't know $m$ in advance. This is less than the brute force idea in which $\mathsf{sketch}$ is just the identity function, which has size $mw$, but the $-\lg m$ term doesn't pay off much until $\lg m$ get large compared to $w$.

So the sketch is just a quotienting filter, and $\mathsf{shift}$ just reverses the hash, adds the $\delta$, then creates a new filter. The fpp is 0.

The size can be made as low as $\Theta(m)$ by hashing your universe from size $2^w$ to $2^k$, for any $\lg m \< k \< w$, as long as your filter supports small universes. The fpp is then the probability of collision, which is $1-(1-2^{-k})^m$.

In total, this gets to a space usage of $m(\lg (1/\varepsilon))$, as long as you know $m$ in advance. This is tight for filters, as the lower bound is also $m(\lg (1/\varepsilon))$.

# Answer
> 2 votes
Here is one simple idea -- not sure if it's practical.

Define $\mathsf{sketch}\_n(X)$ to be a length-$n$ bitstring in which bit $i$ is set iff there exists $x \in X$ such that $x = i \mod n$. In practice, this means that inserting an element $x$ into a set involves turning on bit $x \mod n$. $\mathsf{disjoint}\_n(\cdot)$ is defined as before. Then $\mathsf{shift}\_n(\cdot, \delta)$ can be found by rotating the sketch right by $\delta$ bits (which can be done implicitly by storing a "rotation amount" in the data structure).

To reduce the false positive rate for membership tests (but increase the false negative rate for disjointness tests), you can store multiple bitstrings using different moduli -- e.g., if the moduli 100, 101 and 105 are used, there would be 306 bits in total. Intuition suggests relatively prime moduli would work best, but I have not tried looking into this in detail.

# Answer
> 1 votes
Yes. Use any linear function as your hash function. If $h(x)= \alpha x + \beta \bmod n$, where $\alpha,\beta$ are fixed constants, then

$$h(x+\delta) = h(x) + \alpha \delta \bmod n.$$

Consequently, $\mathsf{shift}$ can just rotate the bitstring right by $\alpha \delta$ positions. Note that if $n$ is prime this hash function is 2-universal, so it should be a pretty good hash.

Unfortunately, this isn't useful if you want to use a Bloom filter with multiple hash functions, because you'd need to use the same $\alpha$ for all hash functions, which means that a collision for one hash will cause a collision for all others; effectively it reduces to a Bloom filter with one hash. But, as j\_random\_hacker suggests, you can create a sketch with multiple bitmaps, one per hash function, and use different hash functions (e.g., with different values of $\alpha$) for each bitmap.

---

More generally, you can use any hash function that has the form

$$h(x) = f^{(x)}(1),$$

where $f^{(x)}$ denotes iterated function application (applying $f$ $x$ times), and $f:\\{1,\dots,n\\} \to \\{1,\dots,n\\}$ is any function. To make this hash function any good, you will probably want $f$ to be bijective and to be chosen so that you can efficiently iterate $h$.

A linear function is one way instantiate $h$, but there are other ways. For instance, you can use

$$h(x) = \alpha^x \bmod n,$$

where $\alpha$ is a fixed constant. I don't expect this to have any advantages over a linear hash function, but I mention it as an example of the more general framework.

---
Tags: data-structures, hash, bloom-filters, sketching
---


# Question
Title: How can a computer deal with real numbers
Computers are an exceptionally powerful tool for various computations, but they don't excel at storing decimal numbers. However, people have managed to overcome these issues: not storing the number in a decimal format, which is limited to very few decimal places, but as an integer instead, while keeping track of the number's precision.

Still, how can a computer *simplify* computations just like humans do? Take a look at this basic example

$$\sqrt{3} \times (\frac{4}{\sqrt{3}} - \sqrt{3}) = \sqrt{3} \times \frac{4}{\sqrt{3}} - \sqrt{3} \times \sqrt{3} = 4 - 3 = 1$$

That's how a human would solve it. Meanwhile, a computer would have a fun time calculating the square root of 3, diving 4 by it, subtracting the square root of 3 from the result and multiplying everything again by the square root of 3.

It would surely defeat a human in terms of speed, but it would lack in terms of accuracy. The result will be really close to 1, but not 1 exactly. A computer has no idea that, for instance, $\sqrt{3} \times{\sqrt{3}}$ is equal to $3$. This is only one of the uncountable examples out there.

Did people already find a solution, as it seems elementary for mathematics and computations? If they didn't, is this because it didn't serve any purpose in the real world?

# Answer
Sage is an open source computer algebra system. Let's see if it can handle your basic example:

> sage: sqrt(3) * (4/sqrt(3) - sqrt(3))
> 1

What is happening under the hood? Sage is storing everything as a symbolic expression, which it is able to manipulate and simplify using some basic rules.

Here is another example:

> sage: 1 + exp(pi\*i)
> 0

So sage can also handle complex numbers.

Computers never handle real numbers, since real numbers cannot be represented exactly on a computer. Instead, they either handle *approximate representations* of real numbers (usually floating point numbers but sometimes fixed point numbers), or they represent real numbers symbolically, as in the example above. Sage can convert between the two representations (in one direction!), and it can handle floating point numbers of arbitrary accuracy. For example,

> sage: RealField(100)(pi^2/6 - sum(1/n^2 for n in range(1,10001)))
> 0.000099995000166666666333333336072

This computes $\pi^2/6 - \sum\_{n=1}^{10^4} 1/n^2$ to 100 bits of accuracy (in the mantissa).

Another approach worth mentioning is interval arithmetic, which is a way of computing expressions with a guaranteed level of accuracy, using provable error brackets. Interval arithmetic is used in computational geometry, together with exact representation of rational numbers.

In theoretical computer science there are several other notions of real computation, but they are mostly of theoretical interest. See the answers to this question.
> 38 votes

# Answer
Computer algebra is a huge area, probably at least a semester-long university-level course to get most of the basics. However, I think we can cover some of the flavour of it here.

Your case is the easy case, because it is entirely within the language of algebraic numbers (i.e. roots of polynomials), and manipulating polynomials is really the foundation of modern computer algebra. Specifically, you need to understand the concept of a *field extension*.

A field, you will recall, is an algebraic structure which supports addition, subtraction, multiplication, and division.

Starting with the rational numbers $\mathbb{Q}$, we can extend this with a monomial, which we will call $x$. This gives us the field $\mathbb{Q}\[x\]$, where the elements of the field are *rational polynomials*:

$$\frac{p(x)}{q(x)}$$

where $p$ and $q$ are polynomials whose coefficients are rational numbers. We can go further and extend with more monomials, to form, say, $\mathbb{Q}\[x\]\[t\]$, whose elements are rational polynomials $\frac{p(t)}{q(t)}$ where the coefficients are in $\mathbb{Q}\[x\]$.

This gives us a language in which we can understand algebraic numbers such as $\sqrt{3}$. It is essentially a field extension with a constraint: $\mathbb{Q}\[x\]$ subject to the constraint that $x^2 - 3 = 0$.

(NOTE: I'm ignoring the negative solution for the moment, but note that it's not necessary to solve your specific problem! Which solution you use makes a difference when you introduce inequalities. Without knowing that $x \> 0$, $\sqrt{3}$ and $-\sqrt{3}$ are surprisingly difficult to tell apart, but that's a tale for another time.)

Technically, this is called an "ideal" rather than a "constraint". And we denote this field as a quotient, $\mathbb{Q}\[x\] / (x^2-3)$.

Using this machinery, simplifying equations in this form follows a mechanical procedure:

* Express the equation as an element of the appropriate field extension, applying ideals as you proceed.
* If the element is a fraction, reduce it using Euclid's greatest common divisor algorithm.

We can start with your equation and express it as a rational polynomial. Perhaps we use a naive method and get something like this:

$$x \times \left(\frac{4}{x} - x \right) = \frac{x}{1} \times \left( \frac {4 - x^2}{x} \right) = \frac{-x^3 + 4x}{x}$$

We can eliminate the $x^3$ by dividing the numerator by $x^2-3$ and taking the remainder. To see why this works, take $x^2 - 3 = 0$ and multiply both sides by $x$, giving $x^3 - 3x = 0$. Add that to the numerator to get:

$$\frac{-x^3 + 4x}{x} = \frac{x}{x}$$

In general, if the ideal has degree $2$, we should be able to reduce any polynomial to a polynomial of degree $1$.

Finally, we can apply Euclid's GCD algorithm to the numerator and denominator to reduce this fraction to $\frac{1}{1}$. And the problem is solved.

**EDIT** Having said all that, do keep in mind that it's not always obvious what it means to "simplify" a mathematical expression. In some circumstances, a polynomial may be "simpler" if it's expanded and in others, it may be "simpler" if it's factorised.
> 19 votes

# Answer
Here is your mistake:

> That's how a human would solve it. Meanwhile, a computer would have a fun time calculating the square root of 3, diving 4 by it, subtracting the square root of 3 from the result and multiplying everything again by the square root of 3.

You are assigning a mind to a computer. That's the analog of writing "that's how a gas stove would cook a fish curry". The stove, like the computer, provides mechanisms, like floating point arithmetic. Well, the gas stove actually is better at providing heat than the computer (though it depends on the computer). And either computer or stove certainly come in handy as tools in the process for solving a particular problem. But they are not responsible for the solution.

What is involved here is symbolic computation. You can easily write specific programs for solving particular classes of symbolic computation problems, and there are generic programs for doing that, too. Yes, computers are excellent tools for arriving at numerical solutions, but you can also create numerical solutions using pencil and paper (and many computer arithmetic methods are distilled from pencil-and-paper methods, sometimes after converting to binary arithmetic). Or slide rules.

When a computer produces symbolic output, like a human does when writing down symbols on paper, the scope and meaning of the produced symbols depends on the program that is being used for creating them. Some programs will just produce numerical results (which are easily converted into symbols using digits and a few special characters). Others are intended to produce symbolic results where feasible. Being a computer does not really play a whole lot into it except that humans tend to be a lot better at finding excuses for avoiding calculations (since they are so bad at calculating) and a lot of problems given to humans for practice thus tend to magically have solutions that are simpler than actual real-world problems.
> 5 votes

# Answer
Even for numeric, seemingly obvious computations, computers can struggle: most will have trouble simplifying expressions such as $0.1 + 0.2 - 0.3$.

The following paper gives another way of encoding real numbers, for numeric computations, but without those rounding problems:

Towards an API for the real numbers, H.J. Boehm (2020).

The idea is to represent each number as a *function* computing its decimal expansion (or a rational approximation with bounded error): common arithmetic operations then just combine those functions into other functions.

It is apparently used in the calculator app on Android phones.
> 2 votes

# Answer
First of all, you are mixing different concepts. In your example, you are using algebraic numbers. There algebraic numbers are countably infinite, while real numbers are uncountably infinite.

Generally, for every countably infinite set you can find a data structure that can represent each element of the set (size constraints notwithstanding).

Thus, if you want to simplify expressions of algebraic numbers you can find a way to represent algebraic numbers without loss and then apply a solving algorithm.

> √3×√3 is equal to 3. This is only one of the uncountable examples out there.

Again, there are only countably infinite examples. That's why it can work.

For the full set of real numbers, this would not be possible.
> 2 votes

# Answer
You are mistaking a map for the territory.

The first thing to realize is that computers don't work on numbers. Computers work on bits and volts. We abstract that work on volts into working on bits, and we abstract the work on bits to be working on numbers.

Most modern computers use IEEE floating point numbers, not because that is the only thing that they can use, but because IEEE floating point numbers are useful to solve certain kinds of problems. So special purpose hardware to make working with IEEE floating point numbers is added to computers, and they can do calculations using them that are extremely fast.

IEEE floating point numbers represent values as an integer times 2 to the power of another integer, essentially. Both the integer and the power are fixed precision -- they have a max and min size.

When you represent the square root of 3 (or even 0.1) as an IEEE floating point number, you end up with an **approximation** of the square root of 3. There is some error.

As this error is small, and by design each operation has a reasonably random rounding error at the scales we typically work with, you a likely to get decent approximations of the result of most calculations. But not all calculations.

In other domains, instead of IEEE floating point numbers computers use integers with an upper bound, or integers with no upper bound. These are all common ways to do math on a computer.

There is nothing forcing computers to use IEEE floating point values, or integers, or whatever. Computers are capable of doing symbolic manipulation.

They can represent $x^2=2$ as exactly that -- a string of characters, or tokenize it and turn it into a representation of the algebraic structure. They can do various things we teach high school and undergraduate students to do. They can go through everything you described a "human mathematician" doing to simplify the equation.

They can even do this faster than human mathematicians can do quite often.

This area is called "computer algebra".

In my experience, the hard part is usually explaining the problem to the computer. When you see $x^2=-2$ you probably assume we are working in the reals or the complex numbers, but not the quaternions, constructive reals, $\mathbb{Z}\_2$ or something more exotic.

$x^2=2$ in $\mathbb{Z}\_2$ means $x=0$. In $\mathbb{R}$ it is unsolvable. In $\mathbb{C}$ it is plus or minus the $i \sqrt{2}$. Etc.

Going further, the constructive reals are a way of axiomitizing real numbers that basically relies on algorithms and proofs.

In it, $\sqrt{2}$ "becomes" a series of values ${v\_i}$ and a (provably correct) algorithm that takes any $\epsilon \in \mathbb{Q}$ that is greater than zero, and produces an $N$ such that for all $i\>N$, $|v\_i^2 - 2| \< \epsilon$.

Using this you can produce $\sqrt{2}+\sqrt{3}$ by composing the two series with the algorithm. Even $\sqrt{\frac{2}{3}}$ can be done similarly using nothing but mechanics.

As it happens, $\sqrt{2}-\sqrt{2}=0$ cannot be done as simply; and, in fact, you need to know **more** about $\sqrt{2}$ than just the series and a black box copy of the algorithm to show that two instances of it when subtracted are zero. In constructive mathematics, equality is not something you get **for free**, because there is no general way **in the real world** to prove if two different numbers are equal or not.

The same is true in human mathematics; there are things that are probably provably zero, or equal, we cannot prove are zero.
> 1 votes

# Answer
Most people use a compiler, which creates operations with floating point numbers (which are not real numbers).

There are specialised tools that will try to manipulate formulas in symbolic form, and they can do exactly what a human can do. You can even do it yourself to sum degree, in any OOP language you can create objects that represent a number as the sum of rational numbers times square roots of integers for example, implement +, -, \*, / and you will get exactly what you are asking for.

In principle, question like yours can always be answered by saying "either the designer of the processor adds hardware that does what you want, or some software developer creates software to do it". (Or nobody is bothered doing it, sometimes because it is too difficult, and in some cases it's impossible, but those impossible problems are impossible for humans as well).
> -1 votes

---
Tags: real-numbers, computer-algebra
---


title: Must a Turing machine tape be binary?

text:
# Question
Title: Must a Turing machine tape be binary?
I once asked why does computer data bits are usually organized on binary (base 2) sets, rather than on unary (base 1) sets, aiming to also understand why its not also ternary (base 3), heptary (base 7), ennary (base 9) or even decimal (base 10).

One programmer commented that Turing machines are always binary because the tape includes at least one stage to go to and at least one stage to go back to (or something of that sort; translating from Hebrew without knowing the professional terminology in English).

Must a Turing machine tape be binary? --- Can't it be unary in any situation?
Was there an attempt to create a "similar" model which is unary just for the sake of research (putting efficiency aside)?

# Answer
> 1 votes
If there is just one symbol which can appear on the tape, then nothing about the tape can ever change. Thus, the tape is absolutely useless, and you are left with a finite bidirectional automaton.

However, the blank symbol $\bot$ is often treated as a special case. We could thus consider the situation where each cell on the tape can carry either $0$ or $\bot$, and where we can write a $0$ on a place previously containing a $\bot$, but we can never erase a $0$ and return that cell content to $\bot$. This is as close to unary as we can really get for a TM.

As long as we only consider decision problems, these machines still have the full power. Essentially, the idea is to insert a bunch of auxiliary bits between the bits containing the actual content, and then so simply copy everything to a fresh chunk of tape whenever we need to erase a bit, except for the bit to be erased.

Having a finite number of tape symbols greater than 1 doesn't make much a difference. So binary is just special here because its the smallest alphabet that easily works.

---
Tags: turing-machines, computer-architecture, information-theory, bit-manipulation, word-combinatorics
---


# Question
Title: DFA containing substring to not containing substring by flipping acceptability of all states?
For example, $D\_1 = \\{ w | w$ does not contain `baba` as substring$\\}$

For $D\_1$, I would make $F\_1 = \\{q\_4\\}$.

As I tried to design $D\_2$ as the complement of $D\_1$ which does *not* have `baba` as a sub-string, I've found that I can make $D\_2$ by inverting all the acceptability of all states, making $F\_2 = \\{q\_0, q\_1, q\_2, q\_3\\}$, since instead of accepting, the input string is *rejected* upon reaching the an acceptance state of its complement $D\_1$.

From this, I believe that we can get the complement of any DFA simply by accepting when $D\_1$ rejects, and reject when $D\_1$ accepts, meaning $F\_2$ is the complement of $F\_1$.

Is my generalized proof correct?

# Answer
Shortly, yes. Formally, for every DFA $\mathcal{A} = \langle \Sigma, Q, q\_0, \delta, F\rangle$, define the DFA $\overline{\mathcal{A}} = \langle \Sigma, Q, q\_0, \delta, F' \rangle$, where $F' = Q\setminus F$. That is, $\overline{\mathcal{A}}$ is obtained by *flipping* the acceptance of the states in $\mathcal{A}$. We calim the following.

**Claim:** $\overline{L(\mathcal{A})} = L\left(\overline{\mathcal{A}}\right)$.

**Proof:** for every word $w\in \Sigma^\*$, we have $$ w\in L(\mathcal{A}) \leftrightarrow\\ \text{the run $r\_0, r\_1, \ldots, r\_{|w|}$ of $\mathcal{A}$ on $w$ is such that $r\_{|w|}\in F$}\leftrightarrow \\ \text{the run $r\_0, r\_1, \ldots, r\_{|w|}$ of $\overline{\mathcal{A}}$ on $w$ is such that $r\_{|w|}\in F$}\leftrightarrow \\ \text{the run $r\_0, r\_1, \ldots, r\_{|w|}$ of $\overline{\mathcal{A}}$ on $w$ is such that $r\_{|w|} \notin Q\setminus F$} \leftrightarrow \\ \text{the run $r\_0, r\_1, \ldots, r\_{|w|}$ of $\overline{\mathcal{A}}$ on $w$ is such that $r\_{|w|} \notin F'$} \leftrightarrow \\ w\notin L\left( \overline{\mathcal{A}}\right)$$

Crucial points in the construction that you should ponder about:

* Both automata have the same structure, in particular, they have the same run over the same word $w$: can you tell where we relied on this fact?
* The automaton $\mathcal{A}$ is deterministic (in particular, there is a single run of $\mathcal{A}$ on $w$ that determines whether $w$ is accepted or rejected): if $\mathcal{A}$ is nondeterministic, then the construction does not work. Indeed, on input word $w$, there could be two runs of $\mathcal{A}$ on $w$: $r$ which is accepting, and $p$ which is rejecting. After flipping the acceptance of states, we get that $r$ is rejecting and $p$ is accepting, and so $w$ is still accepted.
> 1 votes

---
Tags: finite-automata, check-my-answer
---


# Question
Title: All strings in which every substring 000 appears after every 1
I found this given problem as follows:

Write a regular expression where all strings in which every substring 000 appears after every 1.

Now, I also found the answer from Illinois university study material which is available online. The given answer is as follows:

(1+01+001)\*0\*

However, I think this is not the correct answer as the RE can generate the given strings as 1, 10, 1010010 and so many. So the RE is not properly justified to the given problem.

Please, help me to get the correct information. Thanks for your kind consideration.

# Answer
> 2 votes
The formulation

> every substring 000 appears after every 1

is extremely ambiguous. However, given the proposed solution, here is how we are supposed to interpret it. Let $w$ and $x = x\_0 \ldots x\_{m-1}$ be words. We say that *$x$ occurs in $w$ at position $i$* if $$w\_i w\_{i+1} \ldots w\_{i+m-1} = x\_0 x\_1 \ldots x\_{m-1}.$$ The language in question consists of all words $w$ such that if $1$ occurs in $w$ at position $i$ and $000$ occurs in $w$ at position $j$, then $i \< j$. This means that after the first time that $000$ occurs, the word consists only of $0$s. Therefore we can break words in the language into two parts: the first part doesn't contain $000$ at all, and the second part, which is optional, contains $000$ followed by any number of $0$s.

---
Tags: regular-languages, automata, finite-automata, regular-expressions
---


# Question
Title: Understanding the coefficient matrix of Hermite Interpolation
I was not sure whether this is a computer science question or a math question, so I posted it here, hope that it is alright.

I am trying to learn the technique of Hermite interpolation. I do understand that it is a generalization of Newton polynomial interpolation, which also considers derivatives to ensure continuity of the interpolated curve at the provided points.

In the book Computer Animation — Algorithms and Techniques by Rick Parent, there is a definition of Hermite interpolation that looks like this:

> Hermite interpolation generates a cubic polynomial from one point to another. In addition to specifying the beginning and ending points $(P\_i,P\_{i+1})$, the user needs to supply beginning and ending tangent vectors $(P'\_i,P'\_{i+1})$ as well.

Here, just the first derivatives are considered, and the aim is to find a polynomial of degree 3 by finding appropriate coefficients $a\_3,a\_2,a\_1,a\_0$ such that we have $a\_3x^3 + a\_2x^2 + a\_1x + a\_0$. These are found by solving a system of linear equations. So far, so good.

Now, in the book, the matrices look like this:

> The general matrix form for a curve is $P(u) = U^TMB$. In the case of Hermite interpolation, $$ U^T = \begin{bmatrix} u^3 & u^2 & u & 1 \end{bmatrix} \\ M = \begin{bmatrix} 2 & -2 & 1 & 1 \\ -3 & 3 & -2 & -1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix} \\ B = \begin{bmatrix} P\_i \\ P\_{i+1} \\ P'\_i \\ P'\_{i+1} \end{bmatrix} $$

I do not understand the matrix $M$, I do not see where the values are coming from. Are these fixed, or can I somehow compute them?

# Answer
> 2 votes
We are looking for a curve $$ P(u) = a\_3 u^3 + a\_2 u^2 + a\_1 u + a\_0 $$ which satisfies the following properties:

1. $P(0) = P\_i$.
2. $P(1) = P\_{i+1}$.
3. $P'(0) = P'\_i$.
4. $P'(1) = P'\_{i+1}$.

In terms of the coefficients $a\_0,a\_1,a\_2,a\_3$, these are:

1. $a\_0 = P\_i$.
2. $a\_3 + a\_2 + a\_1 + a\_0 = P\_{i+1}$.
3. $a\_1 = P'\_i$.
4. $3a\_3 + 2a\_2 + a\_1 = P'\_{i+1}$.

In matrix form, this reads: $$ \begin{pmatrix} P\_i \\ P\_{i+1} \\ P'\_i \\ P'\_{i+1} \end{pmatrix} = \begin{pmatrix} 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 \\ 3 & 2 & 1 & 0 \end{pmatrix} \begin{pmatrix} a\_3 \\ a\_2 \\ a\_1 \\ a\_0 \end{pmatrix} $$ Inverting the matrix, we get $$ \begin{pmatrix} a\_3 \\ a\_2 \\ a\_1 \\ a\_0 \end{pmatrix} = \begin{pmatrix} 2 & -2 & 1 & 1 \\ -3 & 3 & -2 & -1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} P\_i \\ P\_{i+1} \\ P'\_i \\ P'\_{i+1} \end{pmatrix} $$ Therefore the equation of the curve is $$ P(u) = \begin{pmatrix} u^3 & u^2 & u & 1 \end{pmatrix} \begin{pmatrix} a\_3 \\ a\_2 \\ a\_1 \\ a\_0 \end{pmatrix} = \begin{pmatrix} u^3 & u^2 & u & 1 \end{pmatrix} \begin{pmatrix} 2 & -2 & 1 & 1 \\ -3 & 3 & -2 & -1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} P\_i \\ P\_{i+1} \\ P'\_i \\ P'\_{i+1} \end{pmatrix} $$

---
Tags: matrices, linear-algebra
---


# Question
Title: How to check if an algorithm's running time is linear/polynomial in its input size? Multiple variables
I am reading a proof that the Subset Sum decision problem is NP-complete.

I know that the time complexity is always calculated based on the number of bits of the input in binary, hence the $\log{W}$. Also, for this specific problem the size/length of the input is $(n+1)\log{W}$, with $n$ and $W$ being two integer variables ($n$ is the number of available elements in the set and $W$ is the sum we are seeking).

However I am having some trouble when trying to understand the terminology **be** linear/polynomial **in** the input size, specifically with these two lines:

> The input length is (n + 1) log W, and the running time of O(nW) is not **polynomial in** this input length.

and

> takes O(n log W) time, **linear in** the input size.

How can I mathematically prove the above two lines? Or what is the mathematical reasoning behind those two statements?

I don't have this conceptual problem when there is only one variable. For example, let's say I have an algorithm with a complexity of $O(x)$ and an input size of $\log\_2{x}$. Then, I can express $x$ in terms of the problem size like this: $O(2^{size})$. Now, I can see that the complexity is **exponential in** the size (in bits) of the problem.

But I don't know how to do this when there are two or more variables in the complexity function (in this case $W$ and $n$).

# Answer
> 1 votes
Suppose that the function $\ell$ represents the input length of an algorithm, in terms of several parameters $\vec{x}$, and suppose that the function $T$ represents its running time, in terms of the same parameters $\vec{x}$. Furthermore, there is a collection of valid parameter settings.

We say that $T$ is *linear* in $\ell$ if there exist $M,C$ such that for any valid parameter setting $\vec{x}$, if $\ell(\vec{x}) \ge M$ then $T(\vec{x}) \leq C \ell(\vec{x})$.

Similarly, we say that $T$ is *polynomial* in $\ell$ if there exist $M,C$ such that for any valid parameter setting $\vec{x}$, if $\ell(\vec{x}) \ge M$ then $T(\vec{x}) \leq C\ell(\vec{x})^C$.

(We get these definitions from the usual definitions of time complexity.)

In your case, $\ell$ and $T$ depend on two parameters $n,W$, and $\ell(n,W) = (n+1)\log W$. A parameter setting is valid if $n \geq 1$ and $W \geq 2$ (this unstated assumption is needed to guarantee that your running times are positive). You are interested in two functions $T$: $T\_1(n,W) = nW$ and $T\_2(n,W) = n\log W$.

Let us start with the second function $T\_2$. For any valid $n,W$ we have $n+1 \leq 2n$ and so $\ell(n,W) \leq 2T\_2(n,W)$. Therefore $T\_2$ is linear in $\ell$, with $M = 1$ and $C = 2$.

Now let us consider the first function $T\_1$. Suppose that $T\_1$ were polynomial in $\ell$, with parameters $M,C$. Thus if $n \geq 1$, $W \geq 2$, and $(n+1)\log W \geq M$, then $nW \leq C\[(n+1)\log W\]^C$. In particular, taking $n=1$, we get that for any $W \geq 2$, $W \leq C2^C(\log W)^C$. Equivalently, $W = O(\log^C W)$. However, this is clearly false. Therefore $T\_1$ is not polynomial in $\ell$.

---
Tags: complexity-theory, np-complete, asymptotics, polynomial-time, knapsack-problems
---


# Question
Title: Cook–Levin theorem and reduction as injective function
I saw that the injectivity "derives directly from the theorem", but i can't see how it's happen, any explanation?

# Answer
Your question is a bit unclear, but let me hazard a guess. Let $L$ be an NP language. According to the Cook–Levin theorem, there is a polynomial time reduction $\phi\_L$ from $L$ to SAT, that is, $\phi\_L$ is a polynomial time function that satisfies $x \in L$ iff $\phi\_L(x) \in \mathrm{SAT}$. You are asking why $\phi\_L$ is injective.

Roughly speaking, $\phi\_L(x)$ constructs a formula which describes the operation of a nondeterministic Turing machine for $L$ executing on $x$. The input $x$ is hardcoded in this description, and in particular, we can extract $x$ from $\phi\_L(x)$. This implies that $\phi\_L$ is injective.
> 1 votes

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


# Question
Title: Time complexity of similar-looking functions
What is the time complexity of the following functions, and why?

int f(int n)
{
    if (n <= 1) return n;
    return 2*f(n-1);
}

int g(int n)
{
    if (n <= 1) return n;
    return g(n-1) + g(n-1);
}
```
</code></pre>

# Answer
> 3 votes
The answer is actually subtler than it looks.

Let us first consider a naive compiler. This naive compiler will implement the recursive case of $g$ by actually running $g(n-1)$ twice. The recurrences for the running time will be \begin{align\*} T\_f(n) &= T\_f(n-1) + O(1) & T\_f(1) &= O(1), \\ T\_g(n) &= 2T\_g(n-1) + O(1) & T\_g(1) &= O(1), \end{align\*} whose solutions are $T\_f(n) = O(n)$ and $T\_g(n) = O(2^n)$.

Usually we allow the compiler to perform some optimizations. It could potentially optimize the calculation of $g(n-1) + g(n-1)$ by first computing $x = g(n-1)$, and then calculating $x + x$ or $2x$ (or potentially $x \ll 1$). However, this should be done with care, since it could have modified the semantics of the program. Suppose for example that we modify the code by adding *side-effects*:

```
int fx(int n)
{
    printf("x");
    if (n <= 1) return n;
    return 2*fx(n-1);
}

int gx(int n)
{
    printf("x");
    if (n <= 1) return n;
    return gx(n-1) + gx(n-1);
}

```

In this case $fx(2)$ results in printing $xx$ while $gx(2)$ results in printing $xxx$. Therefore an optimizer cannot convert $gx$ into $fx$, though it could convert $g$ to $f$. A smart optimizer will be able to detect, using static analysis, that there are no side effects in $g$, and so convert $g$ to $f$.

I tried it out with clang version 12.0.0. Without any optimizations (`-O0`), the function $g$ has two recursive calls. With optimizations (`-O1` and higher), the code of $g$ becomes identical to the code of $f$. The code of $gx$ is of course unaffected.

---
Tags: time-complexity, c++
---


# Question
Title: Question on the "Tutorial implementation of dependently typed lambda calculus"
I have a slight technical struggle with this marvelous tutorial. On page 5 the tutorial talks about typing rules for Simply Typed Lambdas and presents following judgement as derivable via rules on figure 3.

I was unable to prove neither `id` nor `const` by the same reason. Take for instance the `id` example.

* Say I am looking on type checking rule `CHK`. It says that in order to `check types` I should first perform inference and then compare result with what I expect.
* To do the inference on application, I have to use the `APP` rule that immediately forces me to infer the type of the left hand side of the application, namely `(id :: α -> α)`
* To do that I am using the `ANN` rule that forces me to check that `α -> α` is a type (and I can prove it no problem). Then I got this naked `id` symbol and have to prove it's type to be `α -> α`.
* Finally, here is a problem. In order to do that I will have to use `var` rule, which requires the type of `id` to be set in the context Gamma explicitly, but it is not done, therefore the proof is falling apart.

# Answer
$\mathsf{id}$ and $\mathsf{const}$ are not variables of the calculus, but syntactic sugar for $\lambda x \rightarrow x$ and $\lambda x \rightarrow \lambda y \rightarrow x$ respectively. This is stated at the end of §2.2 and subtly conveyed by the use of a sans-serif font rather than italics (this is a typographic convention of this particular document, not a common convention).

So for example the type judgement $$ \alpha :: \ast, y :: \alpha \vdash (\mathsf{id} :: \alpha \rightarrow \alpha) \\: y :: \rightarrow \alpha $$ is also the type judgement $$ \alpha :: \ast, y :: \alpha \vdash (\lambda x \rightarrow x :: \alpha \rightarrow \alpha) \\: y :: \rightarrow \alpha . $$ It's a different notation for the same mathematical object.
> 14 votes

# Answer
As an example, here is the full derivation for the type judgement $$\alpha::\ast,y::\alpha \vdash (\lambda x \rightarrow x :: \alpha \rightarrow \alpha) \\: y :: \alpha$$ where $\enspace \Gamma = \alpha::\ast,y::\alpha \enspace$ and $\enspace \Gamma' = \Gamma,x::\alpha \enspace$:

$$ { \dfrac { \dfrac { \Gamma \vdash \alpha \rightarrow \alpha :: \ast \qquad \dfrac { \dfrac { \dfrac { \Gamma'(x)=\alpha } { \Gamma,x :: \alpha \vdash x ::\_\uparrow \alpha } { \tiny VAR } } { \Gamma,x :: \alpha \vdash x ::\_\downarrow \alpha } { \tiny CHK } } { \Gamma \vdash \lambda x \rightarrow x ::\_\downarrow \alpha \rightarrow \alpha } { \tiny LAM } } { \Gamma \vdash (\lambda x \rightarrow x :: \alpha \rightarrow \alpha) ::\_\uparrow \alpha \rightarrow \alpha } { \tiny ANN } \qquad \dfrac { \dfrac { \Gamma(y) = \alpha } { \Gamma \vdash y ::\_\uparrow \alpha } { \tiny VAR } } { \Gamma \vdash y ::\_\downarrow \alpha } { \tiny CHK } } { \dfrac { \Gamma \vdash (\lambda x \rightarrow x :: \alpha \rightarrow \alpha)\ y ::\_\uparrow \alpha } { \Gamma \vdash (\lambda x \rightarrow x :: \alpha \rightarrow \alpha)\ y ::\_\downarrow \alpha } { \tiny CHK } } { \tiny APP } } $$
> 2 votes

---
Tags: logic, type-theory
---


# Question
Title: Notations for dealing with generators in algorithms
This question is about generators, which are functions that return an item from a (usually very large or infinite) set on demand, an example from Python is:

```
def all_natural_evens():
    n = 0

    while True:
        yield n
        n += 2

```

As can be seen, the above function `yield`s the even number `n` in an infinite loop, in other words, it yields all positive even numbers, but since they are infinite and computer memory is finite, they generate the numbers one by one, on demand (using `next(gen)` to get the next number of the generator `gen`, where `gen = all_natural_evens()`).

I am using generators to build an algorithm and when writing it in Latex, I didn't know how to express this in the algorithm, for ordinary return values there is `return`, but with generators in Python there is `yield` and `yield from` (`yield from` works like an intermediary generator, it generates from a generator...clearly). Is there any notation anywhere for dealing with this kind of generators?

At the moment I'm using keywords $\text{yield}$ and $\text{yield from}$ in the algorithm's pseudocode and explaining what they do.

# Answer
There is no standard way of writing pseudocode. Your main goal when writing pseudocode is that the reader understands it. If you are unsure that the reader will understand *yield* or *yield from*, explain what these keywords mean for you, and mention that they are borrowed from Python, to give due credit.
> 1 votes

---
Tags: algorithms, notation, python, pseudocode
---


# Question
Title: $Sat(EG^2\alpha)$ as a fixpoint of an operator
Currently I am studying CTL model checking. I found this **exercise**:

Consider the CTL formula $EG^2(\alpha)$ which means that there exists a path that satisfies $\alpha$ at every even position. Define $Sat(EG^2(\alpha))$ as a fixpoint of an operator and describe how to extend the CTL model checking algorithm for formulas that contain the operator $EG^2(\alpha)$.

# Answer
Let us prove that $EG^2\alpha$ is the greatest fixpoint of $\tau(Z):=\alpha\wedge EXEXZ$.

Suppose $s\_0\in Sat(\tau(EG^2\alpha))$, then $s\_0\in Sat(\alpha)$ and for some path starting at $s\_0$, we have $s\_2\in Sat(EG^2\alpha)$ where $s\_2$ is a successor of $s\_1$ and $s\_1$ is a successor of $s\_0$. That is, $s\_0\in Sat(\alpha)$ and for some $\pi\in Paths(s\_2)$, we have $\pi\[2i\]\in Sat(\alpha)$, $i\in \mathbb{N}$. Hence, $s\_0\in Sat(EG^2\alpha)$.

Now, assume that $s\_0\in Sat(EG^2\alpha)$, then for every $\pi\in Paths(s\_0)$, $\pi\[2i\]\in Sat(\alpha)$, $i\in\mathbb{N}$. Therefore, $s\_0\in Sat(\tau(EG^2\alpha))$.

We have seen that $EG^2\alpha$ is a fixpoint of $\tau(Z)$. Suppose, now, that $Y$ is a fixpoint of $\tau(Z)$, that is $Y=\tau(Y)$. Let us see that $Sat(Y)\subseteq Sat(EG^2\alpha)$. Let $s\_0\in Sat(Y)$, then $s\_0\in Sat(\alpha)$ and $s\_2\in Sat(Y)$ for some $s\_1\in suc(s\_0)$ and $s\_2\in suc(s\_1)$. But then again $Sat(Y)=Sat(\tau(Y))$, so we have $s\_0\in \alpha$, $s\_2\in Sat(\alpha)$ and $s\_4\in Sat(\alpha)$ for some $s\_3\in suc(s\_2)$ and $s\_4\in suc(s\_3)$. In the limit case, we get a path starting at $s\_0$ that satisfies $EG^2\alpha$. Hence, $s\_0\in Sat(EG^2\alpha)$.

To extend the CTL algorithm

$Sat(EG^2\alpha)$ is the largest $C\subseteq S$ ($S$ is the set of states) such that:

* $C\subseteq Sat(\alpha)$;
* $s\in C\Rightarrow\text{ for each }s'\in suc(s),\text{we have } suc(s')=C$.
> 1 votes

---
Tags: model-checking, computation-tree-logic
---


# Question
Title: substitution method on T(n) = T(floor(n/2)) + n recurrence
While studying recurrences and the methods for solving them, I'm get confused on the assumption made on the solution of the following problem.

Why we assumed that this inequality holds for all positive $m\<n$, in particular for $m=\lfloor n/2\rfloor$? on what basis do we choose this $m$ and why do we need it. Appreciate your answers.

**EDIT**: Excerpt is from **Introduction to Algorithms** by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein

# Answer
As Yuval has mentioned in the comment that the proof is based on the *complete induction*.

However, an important thing is missing in the screenshot that you have shared. The "base case" is missing. Without the base case, the induction hypothesis and proof make no sense.

Here, the base case is when $n = 1$. You might want to verify that $T\[1\] = O(1)$. And, if that is the case, then $T\[1\]$ satisfies the induction hypothesis, i.e., $T\[n\] \leq c \cdot n \log n$ for $n = 1$ and sufficiently large $c$. Now, you would like to prove that the hypothesis also holds for other values of $n$.

For this, you assume that $T\[m\] \leq c \cdot m \log m$ for any $m\<n$. And, suppose using this you could prove that $T\[n\] \leq c \cdot n \log n$. Then, it will imply that the *hypothesis* is indeed the correct *hypothesis* for every $n$. This is because you can apply this proof step to the base case. And, it will give you the correctness of the hypothesis on $T\[2\]$. Then, you apply the proof step on $T\[2\]$ and it will give you the correctness on $T\[3\]$, and so on... Therefore, it proves that the hypothesis is indeed the correct hypothesis for all value of $n$, for sufficiently large $c$.
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis, recurrence-relation
---


# Question
Title: Find original array from array with pairs of adjacent elements
Given an array composed of pairs, like this:

\[\[3,5\],\[1,5\],\[3,2\],\[1,4\]\]

Each element in the array (call it pair) means that pair\[0\] and pair\[1\] are adjacent in the original array. Note, they can come in either order. For instance, for the sample array above, the original array would be:

4,1,5,3,2 (or the reversed version of this)

**How can I do this quickly? I tried doing this as follows, which works, but it's too slow:**

Create a hashmap that maps adjacent elements. Map = {3: \[5,2\], 1: \[5,4\], 5: \[1,3\], 4: \[1\], 2:\[3\]}. My algorithm would then start with one of the keys that only has a corresponding value length of 1 (in this case either 4 or 2), and then add to an output array, and go through the hashmap. I.e. First I would add 4 to my output, and then go from key of 4 (with a corresponding value of 1), to the key of 1, with corresponding values of 5 and 4. I'd ignore 4 (since it's already in output), and add 5, then go to the key of 5, and so on and so forth. This is too slow! Is there a better algorithm?

# Answer
> 1 votes
Use indegree or DFS:

```
    unordered_map<int, int> indegree;
    unordered_map<int, bool> visited;
    unordered_map<int, vector<int>> mp;
    for (auto& vect: adjacentPairs) {
        mp[vect[0]].push_back(vect[1]);
        mp[vect[1]].push_back(vect[0]);
        indegree[vect[0]]++;
        indegree[vect[1]]++;
    }
    int start = 0;
    for (auto& in : indegree)
        if (in.second == 1) {
            start = in.first;
            break;
        }
    }
    int n = indegree.size();
    vector<int> result;
    result.push_back(start);
    visited[start] = true;
    while (result.size() != n) {
        for (auto& val : mp[start]) {
            if (!visited[val]) {
                result.push_back(val);
                visited[val] = true;
                start = val;
            }
        }
    }

    return result;

```

---
Tags: algorithms
---


title: Operations with Asymptotic Notations

text:
# Question
Title: Operations with Asymptotic Notations
I am wondering is anyone has something like a cheatsheet with all the operations between $O(n)$, $\Theta(n)$, $\Omega(n)$, $o(n)$, $\omega(n)$. For example, this is something I don't know how to solve: $$\frac{\Theta(n)}{o(n)} =?$$ There are not many combinations and I was wondering if anyone could help me.

# Answer
Classical resources: CLRS Introduction to Algorithms, 3d edition, pages 47, 1150, Donald Ervin Knuth TAOCP, 1997, volume 1, page 107.

More formal good resource for such cheatsheet you can find in Jeremy Avigad and Kevin Donnelly article.

And, at end, for non negative case, let me bring some well known properties:

$$ \begin{array}{l}O(f ) + O(g) = O(f + g) =O(\max(f,g))\\ C=Const. \Rightarrow C\cdot O(f) = O(C \cdot f) = O(f) \\ O(f ) O(g) = O(f g) \\ O( O( f)) = O(f ) \\ g \ne 0 \Rightarrow \frac{O(f)}{g} = O\left(\frac{f}{g}\right) \end{array} $$

For your case: $f \in \frac{\Theta(n)}{o(n)}$, if an only if $\lim\limits\_{n \to \infty}f(n)=\infty$.
> 2 votes

# Answer
Let's do your example, $$ \frac{\Theta(n)}{o(n)}. $$ Since asymptotic notation doesn't care about constants, we can mentally replace $\Theta(n)$ by $n$. We are then left with $$ \frac{n}{f(n)}, \text{ where } \lim\_{n\to\infty} \frac{f(n)}{n} = 0. $$ It follows that $$ \frac{\Theta(n)}{o(n)} = \omega(1). $$ A different way of expressing this is $$ \frac{\Theta(n)}{o(n)} \stackrel{(1)}= \frac{\Theta(1)}{o(1)} \stackrel{(2)}= \frac{1}{o(1)} \stackrel{(3)}= \omega(1). $$ Here (1) is reducing the fraction, (2) is hiding the constant, and (3) follows from the definitions.

Here is a third way. Let's substitute vague interpretations on both asymptotic notations: $$ \frac{\Theta(n)}{o(n)} = \frac{\sim n}{\mathop{\ll} n} \stackrel{(\*)}= \mathop{\gg} 1 = \omega(1). $$ We're dividing something that scales like $n$ by something which is much smaller than $n$, so we get something big. We use the convention $\omega(1)$ to represent a function tending to infinity. There are similar interpretations for other asymptotic notations involving $1$. For example, $O(1)$ represents a quantity bounded from above.

I did all of these calculations without any cheat sheet. Instead, I know the definitions of $\Theta,O,o,\Omega,\omega$, and this is enough to "generate" whatever rules are needed on-the-fly. The other answer contains some useful rules which it is good to remember, but there is no need to separately consider all possible combinations of different types of asymptotic notation. Instead, it is crucial to remember the spirit of the definitions.
> 0 votes

---
Tags: asymptotics, big-o-notation
---


# Question
Title: One tape nondeterministic Turing machine accepting non-palindromes
I have to design a nondeterministic one tape Turing machine that accepts only non-palindromes in $O(n \log n)$ time.

My best shot was only in $O(n^2)$ time. How can I use the properties of NTM on a single tape to find a faster solution?

# Answer
> 1 votes
**Hint**: to prove that a string $x\_1x\_2\cdots x\_n$ is *not* a palindrome, we only need a value $i$ for which $x\_i\neq x\_{n+1-i}$.

# Answer
> 1 votes
The Turing machine maintains a counter on a parallel track (that is, we increase the tape alphabet so that it can accommodate an additional track of information). The Turing machine begins scanning the input, maintaining its current position on the parallel track; the counter is moved along the way so that when considering position $i$, the counter starts at position $i$. At some point, the machine guesses that the current position $i$ is a mismatch, and remembers the symbol at position $i$. It then moves the counter all the way to the of the input, and counts $i$ positions backwards (in the same way, moving the counter along the way). Finally, it verifies that the symbol at position $i$ from the end differs from that at position $i$.

Since the counter is at most $\log n$ bits long, maintaining the counter (including moving it along) takes time $O(\log n)$ for each step. There are $O(n)$ steps, and so the total running time is $O(n\log n)$.

---
Tags: turing-machines, decision-problem
---


# Question
Title: How can I show mathematically the time complexity of this function is O(N)?
```
int foo(N){
   if(N <= 1){
       return 0
   }else{
       return 1 + foo(N-1)
   }
}

```

I can tell that the time complexity of this program is O(N) but I am unsure on how to prove it mathematically? If I can get some hints I'd grealy appreciate it.

# Answer
You can use induction on input.

For example, in your foo, to show that foo(N) uses exactly N comparisons,

**Base case:** foo(1) uses 1 comparison

**Induction hypothesis:** foo(N) uses N comparisons

**Step case:** foo(N+1) does one comparison and then call foo(N), thus in total, does N+1 comparisons.

You can prove similar statement for addition or all operations, and then you can give a time complexity based on those number of operations.
> 1 votes

# Answer
It depends on what you mean by *show mathematically*. If you want to be very formal, you will need to explain several things:

* Model of computation.
* Syntax and semantics of your programming language, and an algorithm for converting it into "machine code".

We don't typically explain these things explicitly. When analyzing algorithms, we typically assume that RAM machine model, which isn't really one concrete model, but an "idea" of a model; the exact definition usually doesn't matter.

(As an aside, if we worked in the bit complexity model, the running time would increase to $\Theta(n\log n)$.)

Often converting code or pseudocode to RAM machine "machine code" is rather unambiguous, as is the case here (although we have to be careful that our RAM machine is expressive enough to support recursion!). We can set up a recurrence for the running time $T(n)$ of your procedure in terms of the input $n$. If $n \le 1$ then $T(n) = \Theta(1)$, and otherwise $T(n) = T(n-1) + \Theta(1)$. At this point, it is routine to reach the solution $T(n) = \Theta(n)$.

Proving the recurrence *mathematically* would involve converting your C code to RAM machine "machine code", which you are probably not willing to do. Therefore the argument above isn't a completely formal proof. However, in computer science we are content with proofs at this level of detail. Similarly, in mathematics we often imagine we operate in a formal system, but we never actually write out proofs in this formal system; we are content with a level of detail which is enough to convince us that the proof is valid, that is, can be converted to a completely formal proof.

The field of *program verification* is in a sense a formalization of these informal techniques. There are systems which can take your program, convert it into some sort of intermediate code, set up the recurrence relation, and determine the asymptotic running time, possibly outputting a completely formal proof in the end.
> 0 votes

---
Tags: discrete-mathematics
---


# Question
Title: Must a word be binary (and never unary)?
I understand that a computer memory sequential word must always include at least two bits so it must be binary and therefore cannot be unary.

Must a word be binary (and never unary)?
That is to ask; can there be a "unary" computer memory sequential word?

---

This question might relate to my other question - Must a Turing machine tape be binary?

# Answer
> 1 votes
Machine words have fixed length. Denoting the length by $n$ and the base by $b$, each machine word has $b^n$ possible values, and so stores $\log\_2 (b^n)$ bits of information.

A base can be binary or decimal and so forth; if $b=1$ then the machine word has a single possible value, and so stores no information. It would be useless.

Unary encoding is only relevant in contexts where the length is not fixed.

---
Tags: memory-management, word-combinatorics
---


# Question
Title: How to multiply all odd numbers between 50 and 100 in python
I'm new to to python and tried a lot to solve this but can't get this right. I need help on this Thank you The code I wrote is -

```
prod=1
for i on range (50,100,2):
    prod = prod*i
    print(prod)

```

# Answer
> 1 votes
change `for i in range(50,100,2):` to `for i in range(51,100,2):`

---
Tags: python
---


title: Growth rate of roots vs logarithms

text:
# Question
Title: Growth rate of roots vs logarithms
I'm trying to prove that the tenth root of n grows slower than the logarithms but I have no clue. Also, how can I find which of two functions grows faster? It it related to derivatives?

Thanks a lot.

# Answer
> 1 votes
Using L'Hôpital's rule: $$ \lim\_{n \to \infty} \frac{n^{1/10}}{\log n} = \lim\_{n \to \infty} \frac{\frac{1}{10} n^{-9/10}}{n^{-1}} = \lim\_{n \to \infty} \frac{n^{1/10}}{10} = +\infty. $$

---
Tags: time-complexity
---


# Question
Title: What is the difference between speculative execution & branch prediction?
In computer architecture I'm confused between speculative execution & branch prediction. Are the same or different?

# Answer
“Branch prediction” will predict whether a particular branch is taken or not. The prediction can be right or wrong; whoever designs the hardware for it will want the prediction to be correct as often as possible.

Starting with a predicted branch, we don’t know if the instructions we execute should actually be executed, so we start with speculative execution. At some point the processor will learn correctly whether the branch should have been taken or not. If the branch was predicted correctly, the speculative execution is turned into non-speculative. If the branch was predicted incorrectly, all the results of speculative execution are thrown away and you continue with the correct branch.

Car analogy: You drive a car, I have the map. I say “I think you need to turn left” = branch prediction. You turn left = speculative execution. Later I tell you if the turn was correct or wrong.
> 3 votes

---
Tags: computer-architecture, program-optimization
---


# Question
Title: Time Complexity of Rabin-Karp matching algorithm
I asked a question on Rabin-Karp Searching algorithm here, which I am reading from the book "Introduction to Algorithms" 3rd edition Cormen et al..

After reading few para of the section on Rabin-Karp, I got some more confusions:

In the third paragraph the authors say that the if we could find **p** (decimal value of pattern P\[1....m\] ) in time O(m) *and all the **ts** values* (i.e decimal value of length-m sub-string T\[s+1....s+m\], s=0,1,2,,,,n-m) in time O(n-m+1), then we could determine all valid shifts s in time O(m) + O(n-m+1) by comparing **p** with each of the **ts** values.

How is this possible? O(m) is for finding p, O(n-m+1) is for finding all ts, so total pre-processing time so far is O(m) + O(n-m+1). This is the total pre-processing time; the comparison has yet to start, I have to spend some extra $ for doing comparison of a decimal p with each of the (n-m+1)-ts values.

1-Then why the authors say in the first para that the pre-processing time is O(m)? Why it is not O(m) + O(n-m+1) which include processing time of p and all ts values?

2- Now if we talk about worst case matching time, what should be that? So in the worst my decimal number p (already calculated ) will be compared with *each* of the another (m-n+1) decimal numbers, which are the values of ts (already calculated, no extra cash needed for doing this job now ). The worst case is when I am most unlucky and I have to compare every value of ts with p. Right?

Based on my understanding,(if I am right) the worst case matching time should be O(m-n+1) and not O((m-n+1)m) as claimed by the authors in the first para. For example let us say my Pattern is P\[1...m\]=226 and Text is T\[1....n\]=224225226. so my p is decimal 226, and ts is decimal value of T\[s+1, s+2, s+3\], for s=0,1,2...6 as n=9, and m=3. The ts values will be as follows:

> s=0 =\> T\[224\]=\> ts=224
>
> s=1 =\> T\[242\]=\> ts=242
>
> s=2 =\> T\[422\]=\> ts=422
>
> s=3 =\> T\[225\]=\> ts=225
>
> s=4 =\> T\[252\]=\> ts=252
>
> s=5 =\> T\[522\]=\> ts=522
>
> s=6 =\> T\[226\]=\> ts=226

Now you will be comparing p=226 with all these values. So are you not making n-m+1=7 comparisons to achieve search for 226 in T, and not (n-m+1)m =7 x3=21? So the worst case time should be O(n-m+1) and not O((n-m+1)m).

In short I understand that:

> Total pre-processing time = O(m) + O(n-m+1) (including for both p and all the ts values)
>
> Total matching time in worst case = O(n-m+1)

Where I am making mistake?

# Answer
As pointed out by vzn above, the wiki article has all the details you are looking for.

Firstly, what is pre-processing and what is the online runtime, depends on what is remaining constant and what is varying. For example, if we are given some fixed text and are asked to match various small strings with that text, pre-processing would be hashing the text.

In this case, let us say we have only one string to be compared with one text, to avoid confusion about pre-processing. The operations that we need to perform are

1. Hash for string to be searched for ($p$) = $O(m)$
2. Hash for each $m$-sized substring in the text ($T$) (assuming rolling hash) = $O(n-m+1)$
3. Number of hash comparisons (one per each $m$ sized substring in $T$) = $O(n-m+1)$
4. If there are $r$ matches in the hashes, then we compare each of those substrings of $T$ with $p$ (each comparison being $O(m)$) = $O(rm)$

But in worst case, the number of matches in hash can be as large as $n-m+1$. So worst case complexity will be $O(m(n-m+1))$.
> 6 votes

# Answer
1- Because what the authors did in the end as **preprocessing** is compute **p** (decimal value of pattern P\[1....m\]) and the first value for the **ts** (aka **tₒ**), each/both of which can be done in $O(m)$. The remaining $n-m$ **ts** are then computed during matching time with each being $O(1)$. You can confirm this by looking at the code:

2- We might as well use this to answer your second question, if we assume that the if condition in line 10 is never satisfied (hashes never match) then we have $O(n-m+1)$ due to the loop at 9 (matching) and $O(m)$ due to the loop at 6 (preprocessing).

Yet whenever the if condition at 10 is satisfied we need to pay more "cash" at that iteration to check if the strings are actually equal ( **$p$**$=$**$t\_s$** wasn't due to a collision) and this takes $\Theta(m)$ so in the worst case we have $O(m\*(n-m+1))$ as our matching time and $\Theta(m)$ as our preprocessing time.
> 0 votes

# Answer
```
 /*   Pattern string length is m
 *   Source text length is n
 *   Find the index of the first matched substring in text
 *   Runtime:
 *
 *
 *      int hashOfPattern = hash(pattern string);           //  m.
 *      for(int i=0; i<= n-m; i++){                         //  n-m+1.
 *        int currentStringHash = hash(current substring);  //  1. using rolling hash method,
 *        if( currentStringHash == hashOfPattern){
 *           if(current substing equal to pattern string){
 *                                                          //  m. only execute once.
 *                                                          //  Assume it is an effective rolling hash method good enough
 *                                                          // to avoid hash collisions.
 *              return i;
 *           }
 *        }
 *      }
 *   In worse case the whole runtime is m + (n-m)*1 + 1*m = n+m
 *   it is O(n+m)
 *
 *   If the hash function is not effective. The worse case runtime is O(nm).
 */

```
> -3 votes

---
Tags: algorithms, complexity-theory, time-complexity, search-algorithms
---


title: Further papers or code on SMA*+?

text:
# Question
Title: Further papers or code on SMA*+?
I'm interested in the Lovinger and Zhang paper Enhanced Simplified Memory-bounded A Star (SMA\*+). Are there any further papers on this algorithm or publicly-visible code (in any language) implementing it?

I have some things I'd like to understand better about the algorithm (apologies, they're quite basic).

1. What is the precise relationship between a *state* and a *node* in Algorithm 1? They are clearly not synonyms otherwise $s(n)$ would not exist.
2. How does one efficiently determine the parent of $w$ in Algorithm 2? Is it the case that $\forall n \vert n \in O$, $parent(n) \in O$? If yes, is this simply because we only cull leaves?
3. Some problems (including the one I'm interested in) exhibit cycles. If I encounter two identical states $n$, $m$ at different depths $g(n) \> g(m)$ I can always discount $n$. As far as I can see though, nothing would seem to stop SMA\*+ exploring some cycle $m \rightarrow x \rightarrow y \rightarrow z \rightarrow n \rightarrow m$ releatedly at ever-greater depth. If this idea is wrong, what prunes these cycles? If this idea is right, is there a simple way of avoiding this? Do I have to simply prune $m$ from the successors of $n$ when computing $N$?

# Answer
> 3 votes
1. Your third question provides a hint as to why $s(n) \neq n$, where $n$ is a node and $s(n)$ is the state of $n$. Different nodes may contain the same state but different parents, and the path of a node may contain the same state multiple times if it contains a cycle.

Theoretically, you could define $path(n) = n$. Practically, it is useful to define $n$ as a record or class containing useful data about $n$, which brings us to:
2. You can store $parent(n)$ in your data structure for $n$ to find the parent of node $w$ in $\mathcal{O}(1)$. There is no guarantee that $parent(n) \in O$ if $n \in O$. We remove a node from $O$ and add its children when it is expanded in Algorithm 1. In Algorithm 2, we add $parent(w)$ to $O$ if it is not already there, while removing $w$.
3. In terms of correctness, you typically don't have to worry about cycles. As long as the step cost from one state to another is always greater than $0$, which is almost always the case in practice, each cycle increases $f(n)$, making nodes without cycles more favorable.

In terms of performance, exploring cycles is a waste of time. In regular A\* search you can detect and remove nodes with cycles by either looking in the path of a node or maintaining a set of explored states. It has been a while since I worked on SMA\*+, but I think I tried to add cycle detection to SMA\*+ but ran into an issue. That could be a good area for future research .

The SMA\*+ code is part of a search library I was working on. It needs cleaning up before I would consider publishing it, but I'll post the node code here:

```
class _SMAStarPlusNode(Node):
    """Implements comparison for heapq."""
    def __init__(self, node, f_cost):
        # Copy attributes from node
        self.__dict__ = node.__dict__

        # Add SMA*+ attributes
        self.f_cost = f_cost
        self.num_successors = 0
        self.child_fs = {}
        self.open = True # Track whether in open list, to avoid scanning entire list

    def __lt__(self, other):
        return (self.f_cost, -self.depth) < (other.f_cost, -other.depth)
    def __le__(self, other):
        return (self.f_cost, -self.depth) <= (other.f_cost, -other.depth)
    def __gt__(self, other):
        return (self.f_cost, -self.depth) > (other.f_cost, -other.depth)
    def __ge__(self, other):
        return (self.f_cost, -self.depth) >= (other.f_cost, -other.depth)

class Node(object):
    """A node in a search tree.

    This class is very minimal, utilizing lazy evaluation for most attributes.
    Since thousands of instances of this class may exist at a time, every attribute
    adds greatly to the memory requirements of the program.
    """

    def __init__(self, parent, state):
        self.parent = parent
        self.state = state

        # Lazily evaluated attributes (added when needed):
        # _path_cost - added in Problem.path_cost
        # _depth
        # _path

    @property
    def depth(self):
        """Return the depth of this node."""

        # Lazily evaluate depth
        try:
            return self._depth
        except AttributeError:
            return self._make_depth()

    def _make_depth(self):
        try:
            # Non root have 1 more depth than their parent
            _depth = self.parent.depth + 1
        except AttributeError:
            # Root node has depth of 0
            _depth = 0

        # Cache and return
        self._depth = _depth
        return _depth

    @property
    def path(self):
        """Return the path to this node.

        Returns:
            tuple; a tuple of states.
        """

        # Lazy evaluation
        try:
            return self._path
        except AttributeError:
            return self._make_path()

    def _make_path(self):
        try:
            # Add current node to path to parent node
            _path = self.parent.path + (self.state,)
        except AttributeError:
            _path = (self.state,)

        # Add to cache
        self._path = _path
        return _path

class Problem(object):
    ...

    def path_cost(self, node):
        """Return the path cost to a given node.

        This method belongs to Problem instead of Node because Node does
        not store Problem (to minimize memory usage).
        """

        # Lazily evalute path cost
        try:
            return node._path_cost
        except AttributeError:
            if node.parent is None:
                _path_cost = 0.0
            else:
                _path_cost = (self.path_cost(node.parent) +
                              self.step_cost(node.parent.state, node.state))

            # Cache
            node._path_cost = _path_cost
            return _path_cost

```

I removed some code that only existed to work around Python recursion limitations while evaluating lazy attributes. It was big and messy and hopefully isn't an issue with the latest Python, but be aware if you copy this code verbatim.

---
Tags: graphs, search-algorithms, shortest-path
---


# Question
Title: LSTM : What should I do if I am always getting an output too close to one value?
I am training a model for ham and spam classification using LSTM. I am indicating the spams as 0, and the hams as 1. However, the dataset has much more hams than spams, so I tend to get an output very close to 1. That means the output is almost always above 0.5. So I have two questions about this :

Q1. Should I rate my answers based on the ratio between ham and spam in the dataset? (etc. If there are 4000 ham and 1000 spam, then should I count an output higher than 0.8 as ham and lower than 0.8 as spam?)

Q2. If this is not a legitimate way, do you have any solutions for my problem?

# Answer
> 1 votes
The usual starting point is that if the score is above 0.5, classify it as ham, otherwise as spam. If most emails are ham, then it makes sense that most emails give you a score above 0.5, so you have not said anything that indicates there is a problem.

This approach assumes that the proportion of ham vs spam in the training set is the same as the proportion at test time.

If that doesn't work, one standard approach is to choose a threshold, and everything with a score above the threshold is treated as ham, everything below as spam. A standard way to set a threshold is, after you've trained the LSTM, choose the optimal threshold based on the training set (i.e., that maximizes the accuracy on the training set, etc.), or on a validation set.

---
Tags: classification
---


# Question
Title: How does Gradient Descent treat multiple features?
As far as I know, when you reach the step, in a gradient descent algorithm, to calculate `step_size`, you calculate `learning_rate * slope`

Now, `slope` is obtained by calculating the derivative of the `cost_function` with respect to the feature you want to find the optimal coefficient for.

Let's say that the cost function for the purposes of this question is the sum of squared residuals.

My question is, how are coefficients of **other** features treated in the differentiation of the equation? For instance, if I have the equation $y = b\_0 + x\_1 + x\_2$, then by calculating the derivative of the cost function with respect to $x\_1$, one gets:

$\frac{d}{d\left(x\_1\right)}\left(\left(\hat{y}\\:-\\:\left(b\_0\\:+\\:x\_1+x\_2\right)\right)^2\right) =$

$2\times\\:\left(\hat{y}\\:-\\:b\_{0\\:}-x\_1-x\_2\right)\left(\frac{d}{d\left(x\_1\right)}(x\_2)\\:+\\:1\right)$

In this case, how is a value obtained by substituting a value for $x\_1$ while $\frac{d}{d(x\_1)}(x\_2)$ is still in the formula?

I watched a YouTube video (it starts at the right point) that says that $x\_2$ is a constant (while it's a different feature) and, therefore, when differentiating, $\frac{d}{d(x\_1)}(x\_2)$ is omitted and we are left with $2\times \\:\left(\hat{y}\\:-\\:b\_{0\\:}-x\_1-x\_2\right)(1)$. Is this the case or am I missing something?

# Answer
> 2 votes
That's correct. The derivative of $x\_2$ with respect to $x\_1$ is 0.

A little context: with words like derivative and slope, you are describing how gradient descent works in one dimension (with only one feature / one value to optimize). In multiple dimensions (multiple features / multiple variables you are trying to optimize), we use the gradient and update all of the variables in each step. That said, yes, this is basically equivalent to separately updating each variable in the one-dimensional way that you describe.

---
Tags: machine-learning, gradient-descent
---


title: 2's complement substraction

text:
# Question
Title: 2's complement substraction
I need to perform 2's complement operations on -50 - -48

From a mathematical point of view the following would be true.

-50 + 48 = -2

If I would follow the steps I would have:

I got to this result by getting the bite for 50 and 48 and then reversing

```
-50 = 11001101
-48 = 11001111

```

In 2's complement:

```
the bite result for 11001101 - 11001111 is - 00000010 which is 2
the decimal result for 11001101 - 11001111 is -2.

```

Is my logic correct? I think I am missing something.

# Answer
In two's complement, we compute $a-b$ by adding $a$ and $-b$. To compute $-b$ in two's complement, we invert all bits in $b$, and increment the result by $1$.

Let's see how it works in your example. You haven't specified the bit length, but it appears to be $8$. We have $50 = 00110010$, and so $-50 = 11001101+1 = 11001110$. Similarly, $48 = 00110000$, and so $-48 = 11001111+1 = 11010000$. In order to subtract $-48$ from $-50$, we first negate $-48$: $-(-48) = 00101111+1 = 00110000$. Now we add $-50$ and $-(-48)$: $11001110+00110000 = 11111110$. Since the MSB is $1$, we know that this is a negative number. To find out negative what, we invert it: $-(11111110) = 00000001+1=00000010$, which is $2$. Therefore $-50-(-48)=-2$.
> 0 votes

---
Tags: arithmetic, binary
---


title: Intuition for irregular languages

text:
# Question
Title: Intuition for irregular languages
I'm struggling in understanding how to recognize irregular languages. I know what the meaning of irregular language but still find it hard to recognize. Are there any tips to recognize better and to know which is regular and which not?

For example, which of the following is not regular, and what gives you the intuition? \begin{align} L\_1 &= \\{a^ib^i \mid i \ge 0 \\} \\ L\_2 &= \\{a^ib^j \mid i,j \ge 0\\} \\ L\_3 &= \\{a^nb^nc^md^m \mid n,m \ge 1 \\} \end{align}

# Answer
> 1 votes
The language $L\_1$ is the quintessential example of a non-regular language. Intuitively, finite automata cannot count, so they cannot ascertain that the number of $a$'s is the same as the number of $b$'s. Alternatively, an automaton must "remember" how many $a$'s it has seen, which is impossible since there are infinitely many possible number of $a$'s. This intuition can be formalized using Myhill–Nerode theory: if $q\_n$ is the state that a DFA for $L\_1$ is at after reading $a^n$, then $q\_n \neq q\_m$ for $n \neq m$, since $a^nb^n \in L\_1$ while $a^mb^n \notin L\_1$; so there must be infinitely many states.

The language $L\_2$ corresponds to the regular expression $a^\*b^\*$, so is regular.

The language $L\_3$ is a "generalization" of $L\_1$ (this can be made precise: $L\_1$ is a quotient of $L\_3$, $L\_1 = L\_3/\\{cd\\}$). Once again, an automaton needs to count how many $a$'s there are, which is impossible.

---
Tags: regular-languages, automata, finite-automata
---


# Question
Title: Sorting in computing longest increasing subsequence
I am currently reading the paper On computing the length of longest increasing subsequences by Michael L. Fredman.

I'm struggling to understand parts of the proof of Theorem 3.5,
especially this bit:

> Now consider the following enhancement $A^\*$ of $A$. Whenever $A$ concludes that $L \< k$, $A^\*$ continues to completely sort $S$ \[...\]

This is used to show a bound for $L \ge k$, but why are they sorting the sequence?

# Answer
Here is a sketch of the proof of Theorem 3.5:

* If there is a comparison-based algorithm for LIS using $m$ comparisons in the worst case, then we can convert it to an algorithm which answers the question "is $L \geq k$" (for some fixed $k$) using $m$ comparisons.
* Given an algorithm which answers the question "is $L \geq k$" using $m$ comparisons, we can convert it into an algorithm using $m + n \log k + O(n)$ comparisons which sorts the input whenever $L \< k$.
* Any comparison-based algorithm which sorts the input whenever $L \< k$ must perform at least $\log S(n,k)$ comparisons (since it has at $S(n,k)$ possible outputs).
* Consequently, every comparison-based algorithm for LIS must use at least $\log S(n,k) - n \log k - O(n)$ comparisons.
* The theorem follows by choosing $k = \lfloor 3\sqrt{n} \rfloor$ and using the asymptotics of $S(n,k)$.

We sort the input in order to use a lower bound on sorting.
> 0 votes

---
Tags: algorithms, sorting, strings, subsequences
---


title: Is big O notation additive?

text:
# Question
Title: Is big O notation additive?
For example, I have one program that requires $O(i)$ time complexity, and a second program requires $O(j)$ time complexity. Would the total time complexity be $O(i+j)$? And why?

# Answer
If $f(n) = O(A(n))$ and $g(n) = O(B(n))$ then $f(n) + g(n) = O(A(n) + B(n)) = O(\max(A(n),B(n))$. These are standard properties of big O, which follow almost directly from the definitions.
> 0 votes

---
Tags: time-complexity, asymptotics
---


title: Predicate variant of Assignment Problem

text:
# Question
Title: Predicate variant of Assignment Problem
Given two equally sized sets, $P$ of Boolean predicates and $E$, I want to decide if there exists a bijective function $f: P \rightarrow E$, such that \begin{align} \forall p \in P \\; p(f(p)) \end{align}

It seems like a special case of having a weight matrix $W$ where $w\_{ij}=0$ if $P\_i(T\_j)$ and otherwise $1$, and then solving the general Assignment Problem. For practical reasons calculating such a weight matrix up front is not desirable, as evaluating $p$ is not necessarily cheap.

I have also thought about whether it could be formulated as some variant of Stable Marriage Problem, where the men have a predicate that needs to satisfied instead of a ranked preference list over all women.

I don't think the proposed problem sounds very exotic, so I might just be looking in a wrong direction.

# Answer
> 0 votes
Your problem is known as *bipartite perfect matching*. Unfortunately, the query complexity of your problem is $n^2$ (where $n = |P| = |E|$), that is, in the worst case you might need to make a lot of queries of the form $p(e)$. The complexity remains $n^2$ even if you are allowed XOR queries, and remains $\Omega(n^2)$ even if you are allowed AND queries, or if you are allowed OR queries. See Gal Beniamini and Noam Nisan, Bipartite Perfect Matching as a Real Polynomial.

---
Tags: decision-problem, bipartite-matching, assignment-problem
---