# Question
Title: Code optimization - syntax tree vs. intermediate representation
I'm working on a compiler for my own custom language. As I was reading an article on code optimization, I noticed that it assumed that the intermediate representation of the code had already been formed. Though I haven't yet started writing the optimization section of my compiler, I've been going through it in my head and it seems preferable to have the optimizer operate on the syntax tree before converting to the intermediate representation.

Is there a reason to prefer one approach to the other or is mostly a matter of personal taste?

For example, suppose I have an `if` block like

```
if ( some_expression ) {
    do_stuff
}

```

If it could be recognized by the compiler that `some_expression` will always evaluate to true and have no side effects, then I could remove its computation simply by pruning the tree.

However, if I had already converted the tree to an intermediate representation, such as an assembly-ish list of simple instructions, the processes of recognizing and resolving the scenario would be (in my imagination since I haven't yet attempted to implemented this) far more complicated.

# Answer
> 3 votes
These days, the trend is to do optimization with the intermediate representation. Check out LLVM for example:

> The LLVM Core libraries provide a modern source- and target-independent optimizer, along with code generation support for many popular CPUs (as well as some less common ones!) These libraries are built around a well specified code representation known as the LLVM intermediate representation ("LLVM IR"). The LLVM Core libraries are well documented, and it is particularly easy to invent your own language (or port an existing compiler) to use LLVM as an optimizer and code generator.

LLVM can provide a source-independent optimizer because it is performs its optimization passes over the code only after it is represented in LLVM IR.

Why might it be far more complicated to do this? It depends on your intermediate representation. One of the design goals for the intermediate representation would be to facilitate various optimizations rather than make them needlessly complicated. See all the optimizations that LLVM can achieve working on the LLVM IR, for example, in this list of analysis and transform passes.

---
Tags: optimization, compilers, syntax-trees
---


# Question
Title: Algorithm to generate a token as survey summary
I'm searching for an algorithm but struggle to find anything, as I'm not sure how to formulate it correctly. I created a simple survey app in Angular with 24 questions and each has 2-5 answers. When the user answered all the questions I'd like to give him a token (as short as possible) on the result page that he can note down, so the next time he can enter the token instead of having to answer all the questions again.

My thought process so far:

* I can store the information in an array with 24 entries `[1, 4, 2, ..., 2, 3]`
* As all values have 1 digit I can remove everything but the numbers `142...23`

This still leaves me with a 24 digits long number. Nothing one would like to note down and type out by hand. So next I tried to convert this number (with ().toString(2)) to a binary with the goal to turned that binary into a human readable string with String.fromCharCode. But all I got was the rather not so human readable `æ\u000f\u0000³KH\u0000\u0000\u0000` for my test input.

I could break down the number into digit pairs (e.g. 120422... -\> \[12, 04, 22, ...\]) and map each of these to a character (00 -\> A, 01 -\> B, ...), but I think there must be something more elegant and efficient, as it would only half the original size. Although using 3 digits for mapping would result in 125 combinations which is rather hard to map to the alphabet, even with upper/lowercases and special characters. But I'd be very happy to hear your ideas. Many thanks in advance!

# Answer
I think you should try converting your 24-digits (in base 10) number, in another base, which would reduce a lot the length of your token, while keeping the same information.

You should try experimenting with this website for example, which convert in base 36 (10 number + 26 letters):

http://www.unitconversion.org/numbers/base-10-to-base-36-conversion.html

Here, the number 986541236547896541258745 becomes 4GNE5T9XUQO08CKK

I'm sure you can devise an algorithm in base 62 (10 number, 26 lower cases letters, 26 upper cases letters), or event more if you use other characters, such as +-\*&"# ... etc

EDIT:

found this website that allows you to convert from and to any bases between 2 and 62: https://www.dcode.fr/base-n-convert

Here, the number 986541236547896541258745 becomes 4VMCgFPOG10DLH
> 3 votes

---
Tags: algorithms
---


title: CFG that generates $1^*$ is decidable

text:
# Question
Title: CFG that generates $1^*$ is decidable
I read somewhere that the problem which asks whether or not a CFG $G$ generates $1^\*$ is decidable. The proof goes like this:

> $1^\* \cap L(G)$ is context free since it is the intersection of a regular language and a CFL, therefore we can test if $1^\* \cap L(G)$ is empty since it is decidable to check if the language produced by a CFG is empty. If $1^\* \cap L(G)$ is empty, reject, otherwise, accept.

I have doubts however with this proof since it only shows that *some* string in $1^\*$ is generated by $G$, but not whether $G$ generates *all* strings in $1^\*$.

Moreover, if this proof is correct, we can use the same proof outline under the alphabet $\Sigma=\\{0,1\\}$ to show that $G$ generates $\Sigma^\*$, or that $\Sigma^\* \subseteq G$. However, it is known that it is undecidable whether $R \subseteq G$, where $R$ is a regular language, and $G$ is a CFG (by setting $R=\Sigma^\*$, and $\Sigma=\\{0,1\\}$.

But to show that a CFG generates $1^\*$ is decidable, the only way I can think of is to use something similar to the proof that it is decidable for a PCP instance to generate some string in $1^\*$ (i.e., $w=v$, where $w,v \in 1^\*$), i.e. we can check if the CFG has rule $S \rightarrow S1$, then accept. Otherwise, if it has rules of the form $S \rightarrow 1^aS1^b$ such that $a \> b$, and rules of the form $S \rightarrow 1^cS1^d$ such that $c \< d$, then accept... But is there a simpler way to solve this problem?

# Answer
Maybe you're confusing two different problems. The algorithm you are describing shows that the problem of testing whether a CFG generates some string from $1^∗$ is decidable (e.g., see here at page 21). Anyway, the problem of testing whether a CFG generates all the strings of the language $1^∗$ is truly decidable. Consider all production rules to be simple (I mean, no "$|$" on the right), and eliminate all productions including a terminal character different from 1 on the right. Now you have a CFG over a terminal alphabet of a single letter, and then it generates a regular language (see here). All that remains is to test if two regular languages are equal. Moreover, there are effective procedures to convert a CFG over a one-letter (terminal) alphabet into a regular grammar (e.g., see here).

---

On the last part of your question: the fact that it is undecidable whether $R\subseteq G$, where $R$ is a regular language, and $G$ is a CFL, does not imply that for some specific regular languages you can not decide the inclusion. For example, if $R$ is finite (possibly empty), then testing for $R\subseteq G$ is decidable (see the first link above).
> 4 votes

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


# Question
Title: Prove: If $T'$ is not a MST one of its edges may be replaced by a lighter edge in order to get a lighter spanning tree
Prove: If $T'=(V,F')$ is a spanning tree, but not a MST of $G=(V,E)$, then there are edges $e' \in F'$ and $e \in $ $E$ \ $F'$ such that $w(e)\<w(e')$ and $T'$ \ $\\{e'\\} \cup \\{e\\}$ is a spanning tree.

My idea:

Let $T=(V,F)$ be a MST of $G$

for all $e \in T$, try to insert it into $T'$ and see if there is an edge in the cycle created that is heavier than $e$. If we found such $e$ we are done.

If not, define $G'=(V,F \cup F')$

This graph obviously has a MST, because $F \subset F' \cup F$

We didn't find a suitable $e$ in the previous part so all edges in $F$ may be colored in red in the generic algorithm for finding a MST in the graph $G'$.

That means there is a MST $T''=(V,F'')$ such that $F'' \subseteq F'$ but that is impossible because $T'$ is not a MST of $G'$, because $T$ is lighter (by definition $w(T)\<W(T')$)

Does that seem correct?

# Answer
I have a proposal for a proof that doesn't involve "coloring" since it sounds vague.

Let $T' = (V,F')$ be a spanning tree but not a MST of $G=(V,E)$. Let $T = (V,F)$ be a MST of $G$.

---

**You already did the following:**
Now go through all $e \in F-F'$ and add $e$ to $T'$. Resulting graph contains a cycle if there is another edge $e'$ on the cycle such that $e\neq e',w(e) \< w(e')$ we are done because $T'$ could be augmented.

---

**My approach for the rest using Kruskal's algorithm:**
Otherwise we construct a graph $G' = (V,F'\cup (F-F')) = (V, F'\cup F)$. For all $e \in F-F'$ and for all cycles $e$ lies on (in $G'$) $e$ is clearly one of the edges with the max weight.

Now run Kruskal's algorithm on $G'$ with a modified sorting procedure. Every edge is primarily sorted by its weight and secondary by the boolean if it belongs to $F'$ or not in such a way that for two edges with different weights the edge with the least weight comes first, but if two edges have the same weight the one belonging to $F'$ comes first (if both belong to $F'$ the order doesn't matter). We are allowed to make this modification to the sorting procedure because Kruskal's algo doesn't care in which order edges with equal weight appear.

The algorithm proceeds to sort all edges in mentioned order. Thus for every cycle in $G'$ all edges in the cycle are considered before the an edge $e\in F- F'$ is considered. Since we know that Kruskal's algo connects two nodes always when they do not create a cycle and we know that edges $F-F'$ are considered last for every cycle the MST found by the algo is $T' = (V,F')$.
**Contradiction:** But from our assumption we know that the weighted sum of $T$s edges is clearly lower than that of $T'$s edges and that $T$ is a spanning tree of $G'$. So actually $T$ is the MST of $G'$. Thus we have a contradiction and can conclude that there must be an $e \in F- F'$ such that it augments $T'$.
> 0 votes

---
Tags: minimum-spanning-tree
---


# Question
Title: Runtime difference bewteen Union by Rank and Union by Size for union-find
I was studying Union Find, and according to Wikipedia, there are 2 types of union: union by rank and Union by size. My question is, what is the runtime difference between the two (if any)?

Intuitively, it feels like Union by size would always be better, since each time we merge, we are increasing the rank of every node in one tree by 1, and to minimize overall runtime, we want to increase that one tree to be the one with smaller number of nodes, even though the final tree height might be greater.

But does this make a big difference in runtime?

# Answer
If you combine union by rank or union by size with e.g. path compression the amortized complexity is the same \[$O(m\alpha(m,n))$\]. **But** notice that Wikipedia uses union by rank in order to prove the upper bound $O(m\log^\*(n))$ because for proof purposes the ***union by rank*** algorithm is simpler to handle. On the other hand if you are implementing such a data structure you usually want to allow the user to access the sizes of the sets in the structure and thus use ***union by size*** method in order to keep track of the sizes and don't waste space for an extra array.

---

Its worth mentioning if we don't combine them with e.g. path compression both work in amortized $O(log(n))$.

---

This is a good lecture on this topic. It contains references to all the papers proving bounds for the problem. It also contains explanation of what $O(m\log^\*(n))$ and $O(m\alpha(m,n))$ mean.
> 7 votes

---
Tags: algorithms, graphs, trees, union-find, disjoint-sets
---


# Question
Title: What is the difference between SIZE(n^k) and P/poly?
What is the difference between $\text{SIZE}(n^k)$ and $\text{P}/\text{poly}$?

For reference:

* $\text{SIZE}(n^k)$ is defined as the class of problems solvable with Boolean circuits (of fan-in two) with $O(n^k)$ gates.
* $\text{P}/\text{poly}$ is defined as those problems over $\\{0,1\\}^\*$ which can be solved by an infinite family of polynomial-size circuits ${C\_n}$.

What is the difference between these classes?

# Answer
> 2 votes
SIZE($n^2$) consists only of problems that can be solved by circuit families of size at most $O(n^2)$. P/poly contains problems that can be solved by circuit families of size at most $O(n^3)$, and those solved by families of size at most $O(n^4)$, and so on.

In particular, P/poly = $\cup\_k$ SIZE($n^k$).

---
Tags: complexity-theory, circuits
---


# Question
Title: If A is polynomial-time reducible to B and B is NP-Complete, can I say that A is NP-Complete as well?
I searched a lot on internet, including here, but I couldn't find an explanation that could convince me. The problem is the same of the title, if A is polynomial-time reducible to B and B is NP-complete, can I say that A is NP-complete too?

Actually, I would say yes, because if I can convert a problem that I don't know how to solve to one that I know, then that problem must be at least as hard as the reducible one. So, A should be NPC.

However, I got to another idea that I can convert an easier problem to a hard one, so I could say that A is NP, but I couldn't guarantee that it's NPC.

Which ideia is correct?

# Answer
> 2 votes
You can indeed not guarantee that A is NP-complete.

Problem A: Given is a single number X ≥ 1. Is X equal to 1? Clearly in P, and in NP, but of course not NP-complete.

Problem B: Given n items of size $s\_i$ ≥ 1, a bin size B ≥ 1, and an integer k ≥ 1, can the n items be put into k bins of size B? This one is NP complete.

A can be reduced to B in polynomial time: Just take 1 item of size X, let B = 1 and k = 1.

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


# Question
Title: Count number of ways in which atomic operation(s) of n different processes can be interleaved
**PROBLEM:** Count the number of ways in which atomic operation(s) of **n** different processes can be interleaved. A process may crash mid way before completion.

Suppose there are a total of **n** different processes - P1, P2, P3 .... , Pn.

Each process can have a variable number of atomic operation(s) that constitutes that process, but it should have at least one operation.

---

**EXAMPLE**

> Consider two processes, P1 and P2
>
> * P1: 1o1; 1o2; 1o3; 1o4; 1o5; 1o6;
> * P2: 2o1; 2o2; 2o3;
>
> where 1o1 denotes first operation of process P1.

**Attempt**:

Fix position of all operations of process P1, then count the number of ways in which the operations of process P2 can be placed in empty positions( \__ ) created between operations of process P1, as shown below:

> `__ 1o1 __ 1o2 __ 1o3 __ 1o4 __ 1o5 __ 1o6 __`
>
> There are seven empty positions numbered 1 to 7.

Counting: (*Note that the numbers below (like `1 2 3`) denote the empty position number.*)

```
> Case1: When all three operations of P2 are placed in consecutive empty positions.

  1 2 3

  2 3 4

  3 4 5

  4 5 6

  5 6 7

  We have a total of 5 ordering possible for empty positions.

> Case2: When operations of P2 are placed in two consecutive empty positions taken together.

  1 2 3   2 3 4   3 4 5   4 5 6   5 6 7

  1 2 4   2 3 5   3 4 6   4 5 7

  1 2 5   2 3 6   3 4 7

  1 2 6   2 3 7

  1 2 7

  First cell in every column has already been counted in previous case. We have a total
  of (5 - 1) + (4 - 1) + (3 - 1) + (2 - 1) + (1 - 1) = 10 ordering possible for empty
  positions.

  A similar argument can be made for last two consecutive empty positions taken together,
  that gives us a total of another 10 ordering possible for empty positions.

> Case3: These are those cases that do not have empty positions numbered 8 and 9 for them.

  6 7 8

  7 8 9

> Case4: When operations may crash mid way before completion.
  An 'x' denotes position where a crash is possible and process (here P2) terminates.

  1x 2x 3

  2x 3x 4

  3x 4x 5

  4x 5x 6

  5x 6x 7

  6x 7x 8

  7x 8x 9

  There is a total of 14 'x's possible.

  Note: I have not put a cross after last empty position number because I am assuming that
  a process will complete at this stage. You may correct my assumption if this is
  wrong and should not be assumed in the first place.

```

Adding all 4 cases: `5 + 2*10 + 2 + 14 = 41`. There are 41 possible ways to interleave operations processes P1 and P2.

---

As you can see, counting like this is cumbersome and error prone. I have missed cases.

**How can this counting problem be generalised?** *Please see the problem statement at the top of the question.*

# Answer
This is a classical combinatorics problem, where we view each operation in a process as *indistinguishable*. We can always label the $i$th operation as such after permuting all operations without distinguishing between the operations of a single process.

The number of different permutations of $n$ objects, where there are $n\_1$ indistinguishable objects of the first kind, $n\_2$ indistinguishable objects of the second, etc, is

$$\frac{n!}{n\_1!n\_2!\cdots n\_k!}.$$

See e.g. this for a proof.

---

So in your example we find solution $\frac{9!}{6!3!} = 84$. Here are all 84 to confirm:

```
111111222
111112122
111112212
111112221
111121122
111121212
111121221
111122112
111122121
111122211
111211122
111211212
111211221
111212112
111212121
111212211
111221112
111221121
111221211
111222111
112111122
112111212
112111221
112112112
112112121
112112211
112121112
112121121
112121211
112122111
112211112
112211121
112211211
112212111
112221111
121111122
121111212
121111221
121112112
121112121
121112211
121121112
121121121
121121211
121122111
121211112
121211121
121211211
121212111
121221111
122111112
122111121
122111211
122112111
122121111
122211111
211111122
211111212
211111221
211112112
211112121
211112211
211121112
211121121
211121211
211122111
211211112
211211121
211211211
211212111
211221111
212111112
212111121
212111211
212112111
212121111
212211111
221111112
221111121
221111211
221112111
221121111
221211111
222111111

```
> 2 votes

---
Tags: concurrency, counting
---


# Question
Title: Binary-ish search through partially ordered set
I have an interesting function. It takes subsets of {1,...,N} to positive integers, i.e. $f:P(\[N\]) \rightarrow Z^+$. I know that if S is a subset of S', $f(S) \< f(S')$. Also, if S and S' have the same cardinality, the ordering induced by f is lexicographic, so for example $f(\\{1,2,4\\}) \< f(\\{1,3,4\\})$. Given a value *z*, I'd like to find S such that $f(S) \<= z$ and $f(S) \<= f(T) \<= z$ implies $f(S)=f(T)$ -- that is, I want to do a search on the lattice of subsets of \[N\].

If I knew the ordering were perfectly lexicographic, I'd use a simple binary search. I don't know that, and I believe it is not (e.g., $f(\\{1,2,3,4,5,6\\})$ is possibly greater than $f(\\{7\\})$). Is there a good O(N) algorithm to do this search on the poset? Obviously for N of any appreciable size I have to compute f on-the-fly and can't rely on in-memory storage.

Clarification after a discussion in the comments: The particular $f$ I am dealing with is additive -- specifically, $f(S) = \sum\_{k\in S} g(k) + f(\emptyset)$, with $g$ a monotonically increasing function. This may be easier than the general case (which is also interesting, but not my particular problem).

# Answer
> 4 votes
Here is a simple algorithm that runs in $O(N^2)$ time and $O(N)$ space, assuming that $f(\emptyset)$, $f(\\{1\\})$, $f(\\{2\\})$, $\cdots$, $f(\\{N\\})$ are given in an array.

The starting idea is about the same as what has been given by the OP in his comment. "We will search on subsets of size K using the lexicographic order, for each $K$ from $0$ to $N$. Retain the one with the best value of $f$."

The problem is then how to search the best value of $f$ on subsets of size $K$, named $b\_K$, in $O(N)$ time. Instead of binary search, we will check whether $N$, $N-1$, \cdots, $1$ should be included in the best subset one by one, by taking the real advantage of the lexicographic order on subsets.

1. Initialize $b\_K = f(\emptyset)$. $\ b\_K$ will be the best value on subsets of size $K$ at the end of this procedure.
2. Initialize $count = 0.$ $\ count$ is the number of elements that we have included in the best subset so far.
3. Check $f(\\{N\\})$. If $b\_K + f(\\{N\\}) + f(\\{1, 2, \cdots, K-count -1\\})\le z$, $N$ must be included. Add $f(\\{N\\})$ to $b\_K$ and add 1 to $count$.
4. Check $f(\\{N-1\\})$. If $b\_K + f(\\{N-1\\}) + f(\\{1, 2, \cdots, K-count-1\\})\le z$, $N-1$ must be include. Add $f(\\{N-1\\})$ to $b\_K$ and add 1 to $count$.
5. And so on.
6. Until either we have checked $f(\\{1\\})$ or $count == K$.

We might wonder, if it will take $O(N)$ to compute each $f(\\{1,2, \cdots, K-count-1\\})$, computing each $b\_K$ alone will take $O(N * N)$ time. However, since $f$ is additive, we can compute all prefix sums of $f(\\{1\\})$, $f(\\{2\\})$, $\cdots$, $f(\\{N\\})$ upfront in $O(N)$ time. Then it takes $O(1)$ to access each prefix sum.

Since searching $b\_K$ takes $O(N)$ time, for each $K$ from $0$ to $N$, the total running time is $O(N^2)$.

---

The description above of the algorithm skips the easiest case when $f(\emptyset)\gt z$. In that case, the algorithm should return that there is no such subset.

---
Tags: search-algorithms, binary-search
---


# Question
Title: Best algorithm to find highest possible number of points from unique cards
I am looking for the optimum algorithm for the following:

* 10-15 players
* Each player has between 20 and 40 cards.
* Each card can have one of up to 200 possible characters, and a separate numerical rating (higher is better). Card's characters may duplicate between players, or in players hands. Ratings are highly unlikely to exactly duplicate, though they may be close.

I need to select 5 'active' cards from each players' hands to meet the following criteria:

1. All characters must be unique - no duplicates in any of the 'active' cards of any of the players, or across all players.
2. The total of the players' active cards' ratings must be as high as possible.

Right now I:

```
1) go through all players and find the highest rated card still available;
2) mark it as active for the player whose card it is; and
3) mark that character as used for all other players (so it doesn't get used again).

```

Repeat 1-3 until all players have 5 characters

This gives a pretty good result. But what if we had the following:

```
Player A:
Character 1, rating 100
Character 2, rating 99
Character 3, rating 98

Player B:
Character 1, rating 97
Character 4, rating 2
Character 5, rating 1

```

For the sake of the example, assume we only need two active cards per players.

If Player A uses Character 1 per my algorithm then:

* Player A: Character 1 + 2 = rating 199
* Player B: Character 4 + 5 = rating 3
* **Total rating 201**

Instead if Player A doesn't use Character 1 then:

* Player A: Character 2 + 3 = rating 197
* Player B: Character 1 + 4 = rating 99
* **Total rating 296**

So my algorithm does not produce the best team total rating.

Can anyone suggest a better algorithm, other than just brute force trying all the possible combinations to find the highest total rating? I wonder, for example, if there's something about finding the optimum ratings for each player and then adjusting them to avoid duplication with other players; or perhaps something completely different.

# Answer
> 3 votes
I don't know why D.W. believes this is NP-complete, because it isn't. In order to solve the problem let us first change it (without loss of generality):

1. For each player only keep the highest rated card of a particular character. The lesser rated card(s) will never be part of the optimal solution.
2. For each player add a virtual card to their hand for each character they're missing, with rating -1 (or -inf if ratings can be negative). This ensures this card is never picked, but normalizes the problem.
3. Duplicate each player 5 times.
4. Negate ratings to turn them into costs.

Let's assume we had $p$ players and $c$ characters in the roster. After this transformation we have a typical assignment problem, where we have $5p$ workers and $c$ tasks. Viewing cards as tasks and 'player hand slots' as workers, we have an associated cost $c(w, t)$ for a worker $w$ and task $t$ combination, and our goal is to minimize the total cost.

---
Tags: algorithms
---


# Question
Title: Build a tree for $(-\infty,+\infty)$ similar to dyadic interval trees for $\left[0,+\infty\right)$
Using dyadic intervals, I can build a binary tree for $\left\[0,+\infty\right)$ by having a node the $i$-th at level $l$ representing the range $\left\[i\cdot2^l,(i+1)\cdot2^l\right)$ and has the $(i)$- and $(i+1)$ at level $l-1$ as children.

I would like to build a similar tree for $(-\infty,+\infty)$, but it is not clear to me how this can be done using a single tree. One solution would be to use two binary trees as described above, one for positive and one for negative numbers. Is there a solution that uses a single tree? The tree does not have to be binary, but it would be good if there is a bound on the branching factor.

The intended use of this is to maintain information about floating point values. That is, $l$ can also be negative. It can be used, for example, to do approximate percentile queries. See for example: https://github.com/twitter/algebird/blob/develop/docs/src/main/tut/datatypes/approx/q\_tree.md and https://github.com/twitter/algebird/blob/develop/algebird-core/src/main/scala/com/twitter/algebird/QTree.scala.

# Answer
Maybe the surreal numbers will work as dyadic intervals.

Surreal numbers have a reduced form containing a left and right surreal which is like a range. I think these ranges match the description of "dyadic intervals" in the link you provided.

Nan (the empty set) is considered to be positive or negative infinity depending on whether it is on the left or right side of the reduce surreal form.

The bit form of these dyadic intervals will be the right/left path down the surreal tree diagram (https://en.wikipedia.org/wiki/Surreal\_number)

They start like this:

```
Surreal No.  Tree path  Binary Form   Reduced Form    Interval
   0            nan
   1            ""            1           {0|0}      {-inf,+inf}
   2           "L"           10           {0|1}      {-inf,0}
   3           "R"           11           {1|0}      {0,+inf}
   4           "LL"         100           {0|2}      {-inf,-1}
   5           "LR"         101           {2|1}      {-1,0}
   6           "RL"         110           {1|3}      {0,1}
   7           "RR"         111           {3|0}      {1,+inf}

```

You would also have to imagine that half way between + and - infinity is zero. Then half way between zero and +inf is 1. Then half way between 1 and +inf is 2. etc for all integers. Maybe that makes it unsuitable.

I am unsure whether surreal numbers are related to your question. I had already noticed that the surreal numbers have a quality of half ranges when I read your post.

Edit:

* a "1" bit is prefixed to the L/R path of the given surreal. Where L=0 and R=1. Ex:-1/2 is LR on the surreal tree diagram. LR converts to 01 and then we prefix a "1" to get "101". 101 is the binary form of the LR path.
* Surreal numbers are listed as their birth number. Not their value number. Their values of their left/right reduced sides are used to determine the ranges they represent.
* I can provide python code which produces these list if you want to see how these numbers and ranges are created.
* the example provided above was made by hand and certainly contains mistakes.
> 0 votes

---
Tags: binary-trees
---


# Question
Title: Is Monotone 3-SAT with exactly 3 distinct variables untractable?
I have given the following SAT variation:

> Given a formula F in CNF where each clause C has exactly 3 distinct literals and for each C in F either all literals are positive or all literals are negated. Example:

> $F= (x\_1\vee x\_2 \vee x\_4) \wedge (\neg x\_2\vee \neg x\_3 \vee \neg x\_4) \wedge (x\_3\vee x\_4 \vee x\_5)$

> Is this variation of SAT tractable?

My findings so far:

I suspect the problem is NP-complete and therefore not tractable. Thus I would like to perform a poly-reduction from 3-SAT to the variation described above.

An arbitrary 3-SAT formula can be converted to monotone 3-SAT.

Take following example:

$C\_1=(x\_1\vee x\_2 \vee \neg x\_3)$ and define $z\_3$ by $\neg x\_3 \leftrightarrow z\_3$ and $x\_3 \leftrightarrow \neg z\_3$ which is equivalent to $(x\_3\vee z\_3)\wedge(\neg x\_3 \vee \neg z\_3)$.

From that we get the monotone form of $C\_1$ by

$(x\_1\vee x\_2 \vee \neg x\_3) \leftrightarrow (x\_1\vee x\_2 \vee z\_3)\wedge (x\_3\vee z\_3)\wedge(\neg x\_3 \vee \neg z\_3)$

By applying this transformation to all clauses I get a monotone 3-SAT formula which is equally satisfiable.

My reduction produces additional 2 clauses with 2 literals for each non-monotone clause, but how do I get only monotone clauses with exactly 3 distinct literals?

# Answer
> 3 votes
I will try to answer now my own question and would be glad about some feed back concerning the corectness.

Like in the question above discussed and pointed out by Kyle Jones we can reduce arbitrary 3-SAT formulas to monotone 3-SAT formulas.

For example a clause $C=(x\_1\vee x\_2 \vee \neg x\_3)$ can be converted to $C'(x\_1\vee x\_2 \vee z\_3)\wedge (z\_3 \vee x\_3) \wedge (\neg z\_3 \vee \neg x\_3)$. One can check if $C$ is satisfiable $C'$ is also satisfiable and if $C$ is not satisfiable $C'$ is also not satisfiable.

The next step is to convert all the clauses with less than 3 literals to clauses with exactly 3 distinct literals.

Therefore take for example $C\_1=(x\_1 \vee x\_2)$ and transform it to $C\_1'=(x\_1 \vee x\_2 \vee y\_1)\wedge (x\_1 \vee x\_2 \vee y\_2) \wedge (x\_1 \vee x\_2 \vee y\_3) \wedge (\neg y\_1 \vee \neg y\_2 \vee \neg y\_3)$ then again if $C\_1$ is satisfiable $C\_1'$ is also satisfiable and if $C\_1$ is not satisfiable $C\_1'$ is also not satisfiable. The same can be done for the negative case i.e. $C\_2=(\neg x\_1 \vee \neg x\_2)$ can be transformed to $C\_2'=(\neg x\_1 \vee \neg x\_2 \vee \neg u\_1)\wedge (\neg x\_1 \vee \neg x\_2 \vee \neg u\_2) \wedge (\neg x\_1 \vee \neg x\_2 \vee \neg u\_3) \wedge ( u\_1 \vee u\_2 \vee u\_3)$

By applying the two transformations one can convert an arbitrary 3-SAT instance to a monotone 3-SAT instance with exactly 3 distinct literals. As can be seen easily above the transformations have polynomial complexity. Therefore since 3-SAT is NP-hard the reduction aswell must be NP-hard.

---
Tags: np-complete, satisfiability, propositional-logic, 3-sat, polynomial-time-reductions
---


# Question
Title: What does route aggregation is an automatic process means?
Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 5 (The Network layer), page 448:

> When aggregation is turned on, it is an automatic process. It depends on which prefixes are located where in the Internet not on the actions of an administrator assigning addresses to networks. Aggregation is heavily used throughout the Internet and can reduce the size of router tables to around 200,000 prefixes.

My question is: in this context, what does "when aggregation is turned on, it is an automatic process" mean? Is aggregation (route aggregation) like a function available in the router which an administrator can simply turn on or off? And what does "automatic process" here means? I mean, aren't processes, especially on the network, always automatic?

# Answer
> 1 votes
Firstly, I assume you know the purpose of route aggregation (if you need more clarification on that, feel free to post another question, as it is another topic by itself).

Secondly, in this context, what Tanenbaum is saying is that aggregation can be done manually, but it is done normally done automatically by the routing processes. Manual aggregation is when a human looks at the various network destinations and decides which ones can be aggregated, and then enters the aggregated network destination info into the router configuration (during the process where we have, as Tanenbaum writes it, "an administrator assigning addresses to networks"). The alternative is, for the routing processes to handle it automatically.

Yes, it can be turned on or off through the router configuration. In fact, it can be turned on or off separately for each routing protocol being run on the router (if more than one routing protocol is operating). It is perfectly fine to turn aggregation off for edge routers that are not connected to many networks. Then, their routing table will have individual entries for more networks (not aggregated), but would still not be too big. However, for routers in the Internet core, normally aggregation must be turned on so the routing tables don't become too big (200,000 prefixes is the size Tanenbaum mentions; without aggregation, they could be much bigger with many more prefixes).

It is an "automatic process" in the sense that the routers will exchange information as part of the routing protocol(s), and they can figure out the aggregation automatically, as part of their logic. "I mean isn't process especially on network is always automatic?" -\> some things can also be configured manually. Hence, Tanenbaum tries to make the point that most aggregation is handled through the processes automatically.

---
Tags: computer-networks
---


# Question
Title: How to solve a problem about balancing parentheses with smileys?
I'm new to dynamic programming and find a problem about balancing parentheses and smileys ":)" and "(:" at HackerRank, which is impossible to do.

I've been trying to solve it by 3 days now. The main issue with this problem is that the input string size is in range of 10^9 (creating a dynamic programming 2d array of size 10^9\*10^9 takes forever) and no matter what I try the execution time out. Someone please help.

Here is the problem about balancing parentheses and smileys ":)" and "(:"

# Answer
> 2 votes
The problem confused me as well until I understood that smileys can be separated into a colon and a parentheses if required (because a colon as the text says is also a valid character.) Now you can write a linear algorithm. By counting how many brackets are open, how many could be opened by smileys and how many could be closed by smileys:

```
int main() {
    int n; string s;
    getline(cin,s); n = stoi(s); // get value of n
    for(int i = 0; i < n; i++){
        getline(cin,s);          // read line
        ll open = 0, smiopen = 0, smiclose = 0;
        bool colon = false;      // was the last character a colon?
        bool balanced = true;
        for(ll j = 0; j < s.size(); j++){
            if(colon){
                if(s[j] == '(') smiopen++;  //you COULD open an expr.
                if(s[j] == ')' && open > 0) {open--; smiclose++;} // you COULD close an expr.
            }else{
                if(s[j] == '(') open++; // you HAVE TO open an expr.
                if(s[j] == ')') {       // you HAVE TO close an expr.
                    if(open > 0) open--;
                    else if(smiopen > 0) smiopen--;   //open an optional expr. for balance
                    else if(smiclose > 0) smiclose--; //unclose optional close
                    else{ balanced = false; break;}   //not possible to match found ')'
                }
            }
            colon = false;
            if(s[j] == ':') colon = true;
        }
        if(balanced && open == 0) cout << "YES"<<endl;
        else cout << "NO"<<endl;
    }
}

```

You might notice `smiopen` and `smiclose` could be fused into one variable. But I separated them for clarity.

---
Tags: dynamic-programming
---


# Question
Title: Isn't this Commentz-Walter algorithm buggy?
I've been trying to piece together an implementation of the Commentz-Walter string search algorithm. The idea is to construct a state machine from a trie, working backwards from the earliest feasible position.

The paper is available here, though it is a scanned printout from 40 years ago. I have also found a better quality pseudocode for the core search loop (image below). But it seems that neither description of the algorithm provides a way to 'back out' of a dead end: The current trie node `v` is only ever assigned to its own child. It seems that there is a missing step: once the inner loop has exhausted the possibility of a match, the current node should be changed.

An example of an input that fails my implementation tests is to find the string `bb` in `abb`: The search begins on the first `b`, finds that `ab` is invalid, and fails

Can anyone put me right?

---

Pseudocode of search algorithm:

# Answer
> 2 votes
I figured it out, you have to reset `v` to `root` at the same time as you reset `j` to `0` (in fact if you just add `depth` to your node, you can skip `j` and just use `v.depth`)

---
Tags: search-algorithms, strings
---


# Question
Title: Worst Case for AVL Tree Balancing after Deletion
After deleting a node in an **AVL** tree, self-balancing (zig-zag rotation or the left-right balancing) maintains **O(logn)** time that is not guaranteed in other unbalanced trees (like BST).

The Balancing operation is said to be **O(logn)**.

What is the worst case for balancing? (I guess it will require balancing at every node all the way up till the root)

***Any specific type of tree providing the worst case?***

# Answer
To make a lot of rebalancing, you would like to make your AVL tree as imbalanced as possible. And the worst case is a Fibonnachi-like tree:

, where $T\_n$ is a tree with $T\_{n-1}$ as a left child and $T\_{n-2}$ as a right child ($T\_1=T\_2=$single-node tree).

On this example, if you remove `19`, then node `18` must be rebalanced. After that, node `13` must be rebalanced. Essentially, you will have a rebalance at every level above node `20`. You can build an arbitrary large such tree. I didn't check, but it should be simple to prove that removing the rightmost node always suffices for the worst case.
> 4 votes

---
Tags: complexity-theory, graphs, time-complexity, balanced-search-trees, avl-trees
---


# Question
Title: Label groups of vertices in a graph in an efficient manner without BFS/DFS
I have a graph with a set of vertices $\mathcal{V}$ and a set of edges $\mathcal{E}$. There exists a path between every 2 vertices in the graph. To each edge there is an associated weight $w(e), e \in \mathcal{E}$. I define a (global) threshold $T$ such that if $w((u,v)) \< T$ the two vertices $u,v \in \mathcal{V}$ are in the same group: $g \in \mathcal{V} \rightarrow \mathbb{Z}, g(v\_1) = g(v\_2)$. This behaviour is transitive. The goal is to label the distinct groups starting from zero (the order of the groups is irrelevant). I know that this can be achieved trivially with BFS or DFS, but I want to avoid using those.

The idea I came up with is to iterate over the vertices, go over their 1-ring neighbourhood, and create a new group every time that $w((u,v)) \< T$ for any of the edges and neither $u$ nor $v$ have been assigned a group (for example $g(u) = g(v) = -1$). Additionally, each group is assigned a label, which is initially equal to the index of the group: $h:\mathbb{N} \rightarrow \mathbb{N}, h(g(u)) = g(u)$. If at some point $w((x,y)) \< T$ and $w((y,z)) \< T$, but $g(x) \ne g(z)$ then set $h(g(x)) \leftarrow \min(h(g(x)),h(g(z))$ and $h(g(z)) \leftarrow h(g(x))$. After this procedure it should hold: $h(g(u))=h(g(v)), u,v \in \mathcal{V}$ if there exists a path from $u$ to $v$: $\pi = e\_1,...,e\_n$ such that $w(e\_i) \< T$. Is the algorithm I came up with correct or did I miss something? As it is currently it requires $|\mathcal{V}|$ memory for each array $g,h$. Is there a way to optimize this further?

# Answer
As you highlight in your comments, a reasonable approach is to delete all edges with weight $\ge T$, then compute the connected components of the resulting graph (using any standard algorithm for computing connected components).
> 1 votes

# Answer
I believe my algorithm is correct. A sketch of the proof is presented below:

There are 2 cases: either $u \ne v \in \mathcal{V}$ need to be from the same group, or they need to be from different groups (depending on whether there exists a path between them such that $w(e) \< T, \forall e \in \pi$). It needs to be shown that the algorithm produces the resulting groups (the proof for each case will be done by contradiction).

1. Case 1: Let $u,v \in \mathcal{V}$ and there is a path from $u$ to $v$: $\pi=e\_1,...,e\_n$ such that $w(e\_i) \< T$. Then $h(g(u))$ should equal $h(g(v))$ for the algorithm to be correct.
2. Assumption of algorithm incorrectness: Assume that this is not the case, and that $u$, $v$ belong to different groups based on the result of the algorithm. For simplicity assume that $\pi = \pi\_1,x,y,z,\pi\_2;\\, x,y,z\in \mathcal{V}$ such that all vertices from $\pi\_1,x$ belong to $h(g(u))$ and all vertices on $y,z,\pi\_2$ belong to $h(g(v))$ based on the algorithm. The case following the above assumption will be proven, but it should be clear that the same will hold by induction even if $\pi$ is split into more groups based on the algorithm.

Proof by contradiction: From (1), it follows $w(x,y)\<T, w(y,z)\<T$, and from (2) it follows: $h(g(x)) \ne h(g(z))$. From the definition of the algorithm it follows that it never splits groups, and it merges two groups if $w(x,y) \< T, w(y,z)\<T$ but $h(g(x)) \ne h(g(z))$. Since the algorithm goes over all edges it should have merged $h(g(x))$ and $h(g(z))$.

3. Case 2: $u,v \in \mathcal{V}$ and there is no path $\pi$ from $u$ to $v$ such that $w(e) \< T, \forall e \in \pi$, then $h(g(u)) = h(g(v))$.
4. Assumption of algorithm incorrectness: Assume $h(g(u)) = h(g(v))$.

Proof by contradiction: Both at group creation and at group merging (the only two ways for vertices to end up in the same group) there needs to exist a path between $u$ and $v$ such that $w(e)\<T, \forall e \in \pi$. (3) states that no such path exists, then $h(g(u)) \ne h(g(v))$.

Clearly the proof is fairly informal, so I may have missed something. I will leave the question open for a while, because 1) somebody may come up with a better & more optimized algoritm, and 2) I may have some mistake in my proof.
> 0 votes

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


# Question
Title: Existence / non-existence of a sequence with short longest increasing subsequence and decreasing subsequence?
Can there exist any integer sequence $A$ of length $N$ with all unique elements such that the length of its Longest Increasing Subsequence as well as that of its Longest Decreasing Subsequence is less than $ \displaystyle \lfloor \frac{N}{2} \rfloor $?

If yes, then give an example of such a sequence. Otherwise, can anyone present a proof that there cannot exist such a sequence?

(Just to add some substance, can it be shown there can exist such sequences, given any arbitrary value of $ N \> 1 $?)

# Answer
> 7 votes
The answer to the OP's question is, no if $N\le 7$ and yes otherwise.

---

For given any positive integer $r$ and $s$, the celebrated Erdős–Szekeres theorem shows that for any sequence of distinct real numbers with length at least $(r − 1)(s − 1) + 1$ contains an increasing subsequence of length $r$ or a decreasing subsequence of length $s$.

It turns out that bound, $(r-1)(s-1)+1$ is tight. That is, for any positive number $r$ and $s$, there is a sequence of distinct numbers with length $(r-1)(s-1)$ that contains no increasing subsequence of length $r$ and no decreasing subsequence of length $s$.

Here is such an example.

$$\begin{array} {} &s-1, &s-2, &\cdots,&2, &1\\ &2(s-1), &(s-1)+ s-2, &\cdots, &(s-1)+ 2, &(s-1)+ 1\\ &\vdots &\vdots &\vdots &\vdots &\vdots \\ &(r-2)(s-1), &(r-3)(s-1)+s-2, &\cdots, &(r-3)(s-1)+2, &(r-3)(s-1)+1\\ &(r-1)(s-1), &(r-2)(s-1)+s-2, &\cdots, &(r-2)(s-1)+2, &(r-2)(s-1)+1\\ \end{array}$$

Consider the numbers above, reading from left to right and then from top to bottom. In other words, the sequence is $s-1$ down to $1$, followed by $2(s-1)$ down to $(s-1)+1$, etc and finally followed by $(r-1)(s-1)$ down to $(r-2)(s-1)+1$, all in step of $1$.

It is easy to see that there is no increasing subsequence of length r and no decreasing subsequence of length $s$.

For example, when $r=s=5$, we have $$4,3,2,1,\ \\, 8,7,6,5,\ \\,12,11,10,9,\ \\,16,15,14,13$$ which does not have increasing subsequence of length $5$ nor decreasing subsequence of length $5$.

---

If we let $r=s$, the section above implies that, for any positive number $N$, there exists an integer sequence of length $N$ with all unique elements such that the length of its longest increasing subsequence as well as that of its longest decreasing subsequence is at most $\lceil\sqrt N\rceil$. And $\lceil\sqrt N\rceil$ is the tight upper bound.

Since $$\lceil\sqrt N\rceil\ge \lfloor\frac N2\rfloor\ \text{ for all } N\le 7$$ and $$\lceil\sqrt N\rceil\lt \lfloor\frac N2\rfloor\ \text{ for all } N\gt 7,$$ the answer to the OP's question is, no if $N\le 7$ and yes otherwise.

For example, for $N=8$, we have sequence $3,2,1,6,5,4,9,8,7$.

# Answer
> 2 votes
Such sequences do exist. It suffices to generate a large enough random sequence. If you check Dan Romik's book, *The Surprising Mathematics of Longest Increasing Subsequences*, Theorem 1.1 states that

$$\frac {\ell\_n} {\sqrt n} \to 2,$$

where $\ell\_n$ is an expected length of increasing subsequence in a random permutation of size $n$. The same for decreasing. Therefore, for large enough $n$ there must exist a sequence with both increasing and decreasing sequences of lengths at most $5 \sqrt n$, otherwise:

$$2 E\[\ell\_n\] = E\[|decr\_n| + |incr\_n|\] \ge 5 \sqrt n,$$

which contradicts the theorem.

# Answer
> 2 votes
There are also short sequences that satisfy your request. Consider for example the first 16 terms of the binary Van der Corput sequence $$ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15. $$ In general there exists a sequence $T$ of length $n\geq1$ containing a longest increasing subsequence of length $x\geq 1$ and a longest decreasing subsequence of length $y\geq 1$ if and only if the numbers $x$, $y$ and $n$ satisfy the conditions $x\cdot y\geq n$ and $x+y\leq n+1$, see here. Notice that the reference gives a constructive proof.

# Answer
> 2 votes
Here's a direct construction of such a sequence for any multiple of four. It's made up of four equally sized runs of consecutive integers.

The first and third runs are increasing. The second and fourth runs are decreasing. The runs use ranges of numbers such that $R\_2 \< R\_3 \< R\_1 \< R\_4$. For example, with $4n=16$,

$$ 9,10,11,12 |4,3,2,1|5,6,7,8|16, 15,14,13 $$

The longest increasing subsequence is length $n+2$. For example, in the above where $4n=16$, the longest increasing subsequence has length $6$ ($1| 5, 6, 7, 8|16$). No increasing subsequence is longer:

* It's not possible to pick an element from both increasing runs, since any element in the first increasing run disqualifies all of them from the second increasing run.
* It's not possible to pick more than one element from either decreasing run

A symmetric argument applies for the decreasing subsequences.

Since $n+2 \<\< 2n$, this works as a counterexample for any multiple-of-four sequence. You can easily pad with extra sequence elements for non-multiple-of-four lengths.

I came across this construction by considering a sequence that was a "hill" (increasing, then decreasing), which meets your condition perfectly. Breaking up those long runs could be done making two hills (increasing, decreasing, increasing, decreasing), which this sequence does by ensuring the up/down slope of one 'hill' isn't continued by the other.

---
Tags: algorithms, correctness-proof, subsequences
---


# Question
Title: Randomized Algorithms: High-Probability vs. Expectation
Hopefully this question isn't too general, but I was wondering what the relationship is between randomized algorithms that perform well with high-probability and those that perform well in expectation. My question is motivated by the definition of a randomized $\alpha$-approximation algorithm given here, namely that it is a polynomial-time algorithm that produces a solution within $\alpha$ of OPT in expectation ***or*** with high probability. I also found that the first few pages of this source provides some good insight into the high-probability vs. expectation approaches, but I still have questions.

* Can you always transform an algorithm that achieves an $\alpha$-approximation in expectation to one that achieves this with high probability, and vice versa? (Ostensibly by rerunning the algorithm multiple \[a polynomial number\] of times.)
* If not, is one harder than the other to obtain? (I would think that if you fix $\alpha$, a high-probability algorithm would always be harder to find/less likely to exist. Or maybe you can always find one, but the approximation ratio will become worse.)

Thanks for the help!

# Answer
> 4 votes
If you have an algorithm that is an $\alpha$-approximation in expectation, then you can construct an algorithm that is a $(1+\epsilon)\alpha$-approximation with high probability, for any $\epsilon\>0$. In particular, by Markov's inequality, if you run the algorithm, then with probability at least $1-1/(1+\epsilon)$ it will output a $(1+\epsilon)\alpha$-approximation. So, if you run the algorithm about $(c \log n)/\epsilon$ times and keep the best output among all of those trials, with probability about $1-1/n^c$ you will find a $(1+\epsilon)\alpha$-approximation.

If you have an algorithm that is an $\alpha$-approximation with high probability, there are no guarantees about the expectation. It's possible that with very small probability (probability $1/n^c$), it outputs an extremely bad solution (one with exponentially large approximation factor), and in all other cases it outputs an $\alpha$-approximation. In this case, the expected value of the approximation factor will be very large, even though it has a very small probability to output such a bad solution.

---
Tags: randomized-algorithms
---


# Question
Title: $\Phi_1=1$ or $\Phi_1=2$ for the dynamic $\text{Table-Insert}$ , where $\Phi_i$ is the potential function after $i$ th operation, as per CLRS
The following comes from section *Dynamic Tables*, *Introduction to Algorithms* by Cormen. et. al.

---

In the following pseudocode, we assume that $T$ is an object representing the table. The field $table\[T\]$ contains a pointer to the block of storage representing the table. The field $num\[T\]$ contains the number of items in the table, and the field $size\[T\]$ is the total number of slots in the table. Initially, the table is empty : $num\[T\] = size\[T\] = 0$.

> $\text{Table-Insert(T,x)}$
>
> $1\quad \text{if $size\[T\]=0$}$
>
> $2\quad\quad \text{then allocate $table\[T\]$ with $1$ slot}$
>
> $3\quad\quad size\[T\] \leftarrow 1$
>
> $4\quad\text{if } num\[T\] =size\[T\]$
>
> $5\quad\quad\text{then allocate $new{\text{-}}table$ with $2 \times size\[T\]$ slots}$
>
> $6\quad\quad\quad\text{insert all items in $table\[T\]$ into $new{\text{-}}table$}$
>
> $7\quad\quad\quad\text{free $table\[T\]$}$
>
> $8\quad\quad\quad table\[T\] \leftarrow new{\text{-}}table$
>
> $9\quad\quad\quad size\[T\] \leftarrow 2 \times size\[T\]$
>
> $10\quad \text{insert $x$ into $table\[T\]$}$
>
> $11\quad num\[T\] \leftarrow num\[T\] + 1$

For the amortized analysis for the a sequence of $n$ $\text{Table-Insert}$ the potential function which they choose is as follows,

> $$\Phi(T) = 2 \times num\[T\]-size\[T\]$$

To analyze the amortized cost of the $i$th $\text{Table-Insert}$ operation, we let $num\_i$ denote the number of items stored in the table after the $i$ th operation, $size\_i$ denote the total size of the table after the $i$ th operation, and $\Phi\_i$ denote the potential after the $i$th operation.

Initially, we have $num\_0 = 0, size\_0 = 0$, and $\Phi\_0 = 0$.

If the $i$ th Table-Insert operation does not trigger an expansion, then we have $size\_i = size\_{i-i}$ and $num\_i=num\_{i-1}+1$, the amortized cost of the operation is $\widehat{c\_i}$ is the amortized cost and $c\_i$ is the total cost.

> $$\widehat{c\_i}=c\_i+\Phi\_i- \Phi\_{i-1} = 3 \text{ (details not shown)}$$

If the $i$ th operation does trigger an expansion, then we have $size\_i = 2 \times size\_{i-1}$ and $size\_{i-1} = num\_{i-1} = num\_i —1$,so again,

> $$\widehat{c\_i}=c\_i+\Phi\_i- \Phi\_{i-1} = 3 \text{ (details not shown)}$$

---

***Now the problem is that they do not make calculations for $\widehat{c\_1}$, the situation for the first insertion of an element in the table (line 1,2,3,10,11 of code only gets executed).***

In that situation, the cost $c\_1=1$, $\Phi\_0=0$ and $num\_1=size\_1=1 \implies \Phi\_1 = 2 \times 1-1 =1$

We see that $\Phi\_1=1 \tag 1$

So, $$\widehat{c\_1}=c\_1+\Phi\_1-\Phi\_0=2$$

But the text says that the amortized cost is $3$, (I feel they should have said the amortized cost is at most $3$, from what I can understand)

Moreover in the plot below,

The text represents graphically the $\Phi\_1=2$ which sort of contradicts $(1)$, but as per the graph if we assume $\Phi\_1=2$ then $\widehat{c\_i}=3, \forall i$

I do not quite get where I made the mistake.

# Answer
> 4 votes
You have caught an instance of the infamous off-by-one error in that popular textbook whose name we shall not mention again.

To repeat, it is correct that "the cost $c\_1=1$, $\Phi\_0=0$", "$num\_1=size\_1=1$ $\implies$ $\Phi\_1 = 2\cdot1-1 =1$" and " $\hat{c\_1}=$ $c\_1+\Phi\_1-\Phi\_0$ $=2$". It is incorrect to state that $\widehat c\_i=3$ for all $i$.

The first $\text{T}\scriptsize{\text{ABLE}}\small\text{-I}\scriptsize\text{NSERT}$ operation is indeed very special. It is not considered as an expansion, an event that is defined as "in which lines 5–9 are executed". However, it does not maintain $size\_i = size\_{i-1}$, either. So neither computation for $\widehat{c\_i}$ in the textbook is fit for $\widehat{c\_1}$.

That error is confusing given that we tend to trust fully an exemplary textbook where so much attention have been paid to detail and correctness.

On the other hand, that error is not very significant since, as you noted, it still holds that "the amortized cost is at most 3".

By the way, if you take a closer look at the figure at the end of question, it shows the potential at the end of first $\text{T}\scriptsize{\text{ABLE}}\small\text{-I}\scriptsize\text{NSERT}$ operation, $\Phi\_1=1$, the correct value.

---
Tags: algorithm-analysis, runtime-analysis, arrays, amortized-analysis, check-my-answer
---


# Question
Title: Two languages such that their Kleene closures are equal
I am trying to solve the following problem:
Find languages S and T over the alphabet $\\{a, b\\}$ such that $ S \not\subset T $ and $ T \not\subset\ S $ ($S$ is not contained in $T$ and not equal to $T$, $T$ is not contained in $S$ and is not equal to $S$) but $S^\* = T^\*$.

It might be trivial, but I would appreciate some help.

# Answer
I had originally assumed that the sets are disjoint, but there's no such requirement in the question. I'll post my solution in case anyone might have the same problem in future.

S = {a, b, ab}
T = {a, b, ba}

S\* = T\* since the intersection has all the letters of the alphabet plus ab and ba can easily be obtained from a and b.
> 2 votes

---
Tags: formal-languages, automata, kleene-star
---


title: CFG-Infinite recursion

text:
# Question
Title: CFG-Infinite recursion
As you see, the string production process never ends.

Can someone explain me if this language is regular or not ?

$ S \to Α Β S $

$ A \to S $

$ B \to a B b $

# Answer
The language is regular: $$ L = \\{\\}$$ It doesn't contain any word not even the empty word $\varepsilon$. The automaton recognizing it has only one state; a reject state. Or if you are using DFA the automaton just wouldn't have an accept state.

Notice that the language is regular but that the grammar is written in a form that's usually used for context free grammars, but the language produced by it is still regular.
> 1 votes

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


# Question
Title: Number of ways to bicolor a graph with some constriants
Given a graph `G`, I need to find the number of ways to color it using two colors `Black` and `White`.
Constraints:

> 1. `G` will already have some nodes colored `Black`.
> 2. Every node of color `White` needs to have one or more Neighbors of color `Black`.

The nodes that are colored `Black` will always be leaf nodes.

Vertices\<=32
Edges\<=Vertices^2

# Answer
> 1 votes
If you only care about graphs with at most $32$ vertices then just list all possible colorings. They are only a constant number ($2^{32}$). For each of them you can decide in constant time whether it is valid according to your constraints.

If you care about graphs with any number of vertices, then the problem is a generalization of the problem of counting the number of dominating sets in a graph, which is #P-complete even for special classes of graphs.

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


# Question
Title: How to define enumeration of the set of finite state machines?
I want to write a function that takes N (maximum number of states) as a parameter, enumerates all possible finite state machines up to N states, and returns random FSM with a probability in proportion to the number of states (fewer states more probable). Alphabet = {0,1}

Can you please suggest how to implement this enumeration, encoding / decoding.

Something similar to how in Kolmogorov complexity there is an enumeration for Turing machine programs.

# Answer
One simple encoding is to represent each of the $N$ states by a partial function $f\_n:\\{0,1\\} \rightarrow \\{1, \dots, N\\}$. Input $x$ in state $n$ will cause a transisition to state $f\_n(x)$ if $f\_n(x)$ exists and an error condition if not. You can assume that the initial state is always state $1$.

For $N$ states there are $(N+1)^2$ such partial functions (because either $0$ or $1$ or both may fail to have an image), so there are $(N+1)^{2N}$ encodings. However, some of the encodings will represent FSMs that are isomorphic (because they represent the "same" FSM with a re-labelling of states).

For example, for $2$ states there are $9$ partial functions from $\\{0,1\\}$ to $\\{1,2\\}$ and each state can be represented by one of these partial functions, so there are $9^2=81$ representations of FSMs. The $2$ state FSM which stays in the same state on input $0$ and changes to the opposite state on input $1$ is represented by the two functions

$f\_1(0)=1 \quad f\_1(1)=2\\ f\_2(0)=2 \quad f\_2(1)=1$
> 2 votes

---
Tags: complexity-theory, automata, finite-automata, enumeration, kolmogorov-complexity
---


# Question
Title: Is a compiler a kind of Gödel numbering program?
**Question:** Is a compiler a kind of Gödel numbering program?

Wikipedia tells us that a compiler is: "In computing, a compiler is a computer program that translates computer code written in one programming language (the source language) into another language (the target language)". https://en.wikipedia.org/wiki/Compiler

Also wikipedia tells us: "a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number". https://en.wikipedia.org/wiki/G%C3%B6del\_numbering

**Work done**: My intuition says yes. Here is my line of thought: a programming language is a formal language. Every program is a well-formed formula and a compiler assigns each symbol of this formula to a binary representation of a number that the computer can read. (detail: a computer is a universal Turing machine, so it can perform arithmetic)

But, I don't know the details of how compilers work, so I came here to ask if my reasoning is correct.

# Answer
No. Consider the following two C functions:

```
int f(int a) {
    return a * 2;
}

int g(int a) {
    return a + a;
}

```

If we're being a bit liberal here, both are "well-formed formula of some formal language". Yet most C compilers with optimization turned on will compile these two functions to the exact same code. This violates the uniqueness of a Gödel numbering.
> 3 votes

---
Tags: formal-languages, compilers
---


title: Number of sequences of given type

text:
# Question
Title: Number of sequences of given type
Consider that there is sequence $a$ of length $n$ ,$a=\[a\_i,0\le i\le n\]$. Now you are given with $\text{lcm}$ of some pairs of number from list that is, $\operatorname{lcm}(a\_i,a\_j)=k$ for $0\le i,j\le n$ and $i\neq j$ and $k$ is specific for given pair. Find number of sequences of $a$ that satisfy given $\text{lcm}$'s.

I thought that if $\text{lcm}$ pairs are less than number of distinct number of pairs from sequence,than answer if infinity and if there is any contradicting pair then answer is $0$ and for remaining case that is where $\text{lcm}$ involving every element is present then i do not know how to solve. Could anyone help me with this question.

# Answer
> 0 votes
This problem is at least #P-hard. I'll describe the algorithm which reduces the problem to the simplest case where its hardness can be seen.

Note that if there are numbers that don't participate in any constraints, then the answer is either $0$ or $\infty$. We solve the problem for the rest of the numbers and return $0$ if there are $0$ combinations for them, and $\infty$ otherwise.

The idea is the following.

* Like @orip suggested, represent each number as a product of primes, e.g. $40 = 2^3 * 5^1$.
* For all primes $p\_1, \ldots, p\_k$, which we encounter in any numbers, we solve the problem separately. In the end, the final answer is $ans(p\_1) \times \cdots \times ans(p\_k)$.

So, we have to solve a problem for each prime number $p\_i$. We replace each number with its power of $p\_i$. E.g. when we process prime $2$ and encounter number $40$, we replace $40$ with $3$, since $40$ contains $2$ in the third power. As @orip mentioned, each $lcm$ constraint becomes a $max$ constraint: $lcm(a\_i,a\_j) = 40 \to \max(a\_i, a\_j) = 3$.

The algorithm is the following:

1. First pass: we find a bound on all $a\_i$'s. For each $a\_i$, find all constraints it participates in, and take the minimum of them. E.g. if $\max(a\_i, a\_1) = 2$, $\max(a\_i, a\_3)=5$ and $\max(a\_i,a\_9) = 10$, then we know that $a\_i \le \min(2, 5, 10) = 2$.
2. Now we can find that some constraints can't be satisfied (because $\max(a\_i, a\_j)=b\_{ij}$, but we have bounds $a\_i \< b\_{ij}$ and $a\_j \< b\_{ij}$). In this case, we just report $0$. Otherwise, the problem has some solutions.
3. We can determine some values of $a\_i$'s. For example, if we know that $a\_1 \le 2$, $a\_2 \le 3$ and $\max(a\_1, a\_2) = 3$, then we know that $a\_2=3$.
4. Now for some constraints $\max(a\_i, a\_j)=b\_{ij}$ we still don't know the answer. Note that it means that $a\_i$ and $a\_j$ have the same bound (namely, $b\_{ij}$) (otherwise we would have fixed one of them in the previous step).

Therefore, we can build the following graph: for each unknown $a\_i$ we create a vertex $v\_i$, and for each constraint $\max(a\_i,a\_j)=b\_{ij}$ we create an edge $(v\_i, v\_j)$. Note that for any connected component in this graph, all its vertices correspond to the same bound. We solve the problem for each connected component separately and, again, multiply the answers.

Now, we want each edge in this graph to have at least one endpoint with value $b$ (our bound). In other words, we want to find a *vertex cover*, and assign $b$ to all vertices from the vertex cover. We can assign any number $0,\ldots,b-1$ ($b$ options) to all other vertices. Therefore, the total number of acceptable assignments is the following:

$$\sum\_{k=1}^n |\text{vertex covers of size $k$}| \cdot b^{n-k}$$

where $n$ is the number of vertices in the connected component. In the simplest case, when $b=1$, the problem becomes to find the number of vertex covers of a given graph. This problem is known to be #P-hard, and you don't have a hope to solve it efficiently.

For some specific cases, there may be a simple solution. For example, when we have constraints for all pairs (and therefore the graph is a clique), the expression is just $(b+1)^n - b^n$ (all possible assignments except assignments when no vertex has value $b$).

---
Tags: algorithms, combinatorics, number-theory
---


# Question
Title: Myhill-Nerode to prove a language is non-regular
L = {a^n b^2n c^3n | n∈N^+} I'm trying to prove that L is a non regular language using Myhill-Nerode theorem.

# Answer
Look at the basic principle: A regular language has a finite state machine. If we are given x and y, and there exists a z such that xz is in L and yz is not, or xz is not in L and yz is, then parsing x and parsing y leaves us in different states.

If we find an infinite number of pairs (x, y) such that parsing x and parsing y produces a different state, then the language is not regular.

So find these pairs. It is actually quite obvious. For example a^5 b^5 c^15 is in L but a^6 b^5 c^15 isn't, therefore...
> 1 votes

---
Tags: formal-languages, regular-languages
---


# Question
Title: Given arbitrary integers of $K$ and $M$, can deciding $2^K$ + $M$ is a prime be in $P$?
Given arbitrary integers of $K$ and $M$, is $2^K$ \+ $M$ a prime?

```
K = int(input('enter exponent K: '))
M = int(input('enter integer for M: '))

if AKS.Primality(2**K + M) == True:
    OUTPUT 'yes'
else:
    OUTPUT 'no'

```

I am not knowledgeable enough in number theory or any other field of mathematics to know the answer to this question.

## Question

Is there a polynomial-time algorithm for this decision problem?

# Answer
Assuming you mean "polynomial in the size of the binary representation of K and M", then it is extremely unlikely, but proving that it is impossible will also be very difficult.

There are polynomial time algorithms for checking primality, but they would be applied to a number whose size is K, which is a lot bigger than checking a number whose size is the same as the size of K.
> 2 votes

---
Tags: polynomial-time, number-theory
---


# Question
Title: DFAs are regular languages, but regular languages are closed under concatenation
I have course notes which claim the following two facts:

First, DFAs recognize exactly the regular languages.

Second, regular languages are closed under union, concatenation, and \*.

Now I have as an exercise constructed a DFA which recognizes strings from {0,1} which have an odd number of 1s. So the language of strings of any odd number of 1s is a regular language. However, if you concatenate any two words from the language it contains an even number of 1s and is therefore not closed under concatenation.

I must be misunderstanding something, but what?

I think maybe what I'm doing is saying that the language itself is closed under concatenation, when that's not true. Maybe the claim is actually that the concatenation of one regular language with another regular language is a third regular language?

# Answer
The third paragraph is the correct description how to interpret the statement from your notes. This is also easy to prove: Say $L$ and $L'$ are regular languages described by some regular expressions $r$ and $r'$ respectively. Then $rr'$ describes the concatenation $LL'$ of $L$ and $L'$.
> 2 votes

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


# Question
Title: Is any randomized Algorithm a probability distribution over the set of deterministic Algorithms?
If there is a finite set of Instances of size n and the set of (reasonable) deterministic algorithms is finit.

Can any randomized Algorithm be seen as a probability distribution over the set of deterministic Algorithms? And if yes, why?

# Answer
You can think of a randomized algorithm as having access to a random variable $\mathbf{r}$, which informs its random decisions. For any fixing of $\mathbf{r}$, you get a deterministic algorithm, and in this way you can view the original randomized algorithm as a distribution over deterministic algorithms.

As an example, consider the randomized algorithm for solving MAX-3SAT. The algorithm chooses a random assignment. You can think of this assignment as specified by $\mathbf{r}$. Any particular assignment corresponds to a deterministic algorithm, and the original randomized algorithm is just the uniform distribution over these deterministic algorithms.
> 4 votes

---
Tags: algorithms, probability-theory, randomized-algorithms, minmax-algorithm
---


# Question
Title: Why is this language Turing recognizable and not not-Turing recognizable
I read that the following language is r.e. but not not-Turing recognizable

*$L$: On input $M$ (where $M$ is a Turing Machine), $M$ accepts at least 20 inputs*

I am not sure why it is not not-Turing recognizable., since I could perhaps make the following reduction from $\overline{A\_{TM}}$ to $L$ given this procedure $R$ namely:

> $R$: On input $\<M,w\>$:
>
> > 1. Construct TM $M\_1$, where on input $x$, if $x=1$, accept
> > 2. If input $x$ is not equal to $1$, run $M$ on input $w$ for $|x|$ steps. If after $|x|$ steps, $M$ does not accept $w$, then accept $x$

From this reduction, if $M$ does not accept $w$, i.e. $\<M,w\> \in \overline{A\_{TM}}$, then $M\_1$ accepts any input word, i.e. $M\_1 \in L$.

Am I missing something here?

# Answer
What you are missing is that if $\langle M, w\rangle \notin \overline{A\_{\mathrm{TM}}}$, i.e. if $M$ halts on input $w$, you don't know whether or $M\_1 \notin L$. If $M$ does halt on $w$, but this takes longer than $20$ steps, it would also hold that $M\_1 \in L$. Thus, you don't have a reduction here.

That the language $L$ cannot be co-RE is an immediate consequence of Rice's theorem.
> 3 votes

---
Tags: complexity-theory, turing-machines, computability, undecidability
---


# Question
Title: Largest set of 10-digit numbers where none have Hamming Distance = 1 with any other
I'm working on a system that will require manual data entry of 10-digit numbers (Σ = `0123456789`). To help prevent data errors, I want to avoid generating any two strings that have a hamming distance of 1.

For example, if I generate the string 0123456789 then I never want to generate any of these strings: {1123456789, 2123456789, 3123456789, ...}

What is the largest set of unique strings in the universe of possible strings that satisfy the constraint where no two strings have a hamming distance of 1? If this set can be identified, is there any reasonable way to enumerate it?

# Answer
There is a simple solution: use exactly the strings with sums of digits being divisible by $10$. There are $10^9$ such strings and it is easy to enumerate them, find $i$-th of them in the lexicographic order, generate random such string, et cetera.

Indeed, if two strings differ in exactly one position, then their sums of digits are also different modulo $10$. For example, the sums of digits for strings $0123456789$, $1123456789$, $\ldots$, $9123456789$ are $45$, $46$, $\ldots$, $54$ respectively.

Moreover, this solution is largest possible. Indeed, there are $10^9$ such strings: for every way to choose first $9$ digits, there is an exactly one way to choose the last digit to make the sum divisible by $10$. Hence, there are $10^9$ strings in our set.

On the other hand, *any* set of strings with minimal Hamming distance $2$ has at most $10^9$ elements. Indeed, consider $10$ strings with a given prefix of length $9$. They all are within Hamming distance $1$ of each other (because they differ only in the last position). Hence, at most one of them can belong to any "good" set. Therefore, any "good" set contains at most $10^9$ elements.
> 4 votes

---
Tags: formal-languages, strings, hamming-distance
---


# Question
Title: Proof for time complexity of Insertion (k-proximate) Sort equals O(nk)
***The following is the definition for Proximate Sorting given in my paper:***

An array of distinct integers is k-proximate if every integer of the array is at most k places away from its place in the array after being sorted, i.e., if the $i$th integer of the unsorted input array is the $j$th largest integer contained in the array, then $|i − j| ≤ k$.

***The following is the proof for time complexity of k-proximate insertion sort:***

To prove $O(nk)$, we show that each of the n insertion sort rounds swap an item left by at most $O(k)$.

In the original ordering, entries that are $≥ 2k$ slots apart must already be ordered correctly: indeed, if $A\[s\] \> A\[t\]$ but $t − s ≥ 2k$, there is no way to reverse the order of these two items while moving each at most $k$ slots. This means that for each entry $A\[i\]$ in the original order, fewer than $2k$ of the items $A\[0\], . . . , A\[i−1\]$ are less than $A\[i\]$. Thus, on round $i$ of insertion sort when $A\[i\]$ is swapped into place, fewer than $2k$ swaps are required, so round $i$ requires $O(k)$ time.

My problem with the proof is this line : "This means that for each entry A\[i\] in the original order, fewer than 2k of the items $A\[0\], . . . , A\[i−1\]$ are ***less*** than A\[i\]". The preceding statements just proved that $t-s \< 2k$, otherwise the elements are sorted (as elements with distance greater than $2k$ cannot be swapped.) Isn't the correct statement : "This means that for each entry A\[i\] in the original order, fewer than 2k of the items $A\[0\], . . . , A\[i−1\]$ are **greater** than A\[i\]"?

# Answer
> 0 votes
Yes if you sort the array in ascending order you are right it should be less than $2k$ elements in $A\[0\],...,A\[i-1\]$ are greater than $A\[i\]$. A simple array were the statement w is wrong ($k = 1$):

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

However is you sort in descending order it's the other way around. But you have a good point because this seems to imply that ascending is meant...

> "indeed, if A\[s\] \> A\[t\] but t − s ≥ 2k, there is no way to reverse the order of these two items"

---
Tags: time-complexity, algorithm-analysis, sorting, proof-techniques
---


# Question
Title: Math behind leetcode problem 47 permutations II
Please tell me why the expression `i>0 && nums[i] == nums[i-1] && !used[i-1]` works on getting unique permutations. And what is the math behind it?
The problem is as follows:
Given a collection of numbers that might contain duplicates, return all possible unique permutations. Example:

```
Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

```

Here is the code:

```
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> temp;
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end());
        backtrack(nums, temp, result, used);
        return result;
    }

    void backtrack(vector<int>& nums, vector<int>& temp, vector<vector<int>>& result, vector<bool>& used){

        if(temp.size() == nums.size()){
            result.emplace_back(temp);
        }else{

            for(int i=0; i<nums.size(); i++){
                if(used[i] || i>0 && nums[i] == nums[i-1] && !used[i-1]) continue;
                used[i] = true;
                temp.push_back(nums[i]);
                backtrack(nums, temp, result, used);
                used[i] = false;
                temp.pop_back();
            }
        }
    }
};

```

# Answer
(1) You are sorting the vector so duplicate values will be consecutively present in the vector.

(2) Now we come to the logic behind that condition:

* As the vector can contain the duplicates we should make sure not to repeat the same sequence by starting with the same element again(duplicate)
    + example :
        - `1,1,2` (starting with `first` one) and 1,1,2 (starting with `second` one) =\> both are same (we should make sure this doesn't happen)

Example: In `[1, 1, 2]`

* If the first element in the sequence is chosen as 1, then we should make sure we are not going to create another sequence starting with another 1 (duplicate of the element).
* So for that, we need to skip the loop for all the consecutive duplicate elements.
* In your case, after creating a sequence staring with first 1, when we enter the loop for the second time we check whether the current element is a duplicate `nums[i] == nums[i - 1]` (this is sufficient as you have already sorted the vector) and whether the current element is the first element of the sequence `!used[i - 1]`.

+ In your case, due to this condition, the second one cannot be the first element of the sequence.
> 1 votes

---
Tags: algorithms, permutations, c++
---


# Question
Title: Is IP masquerade and Network Address Port Translation(NAPT) the same?
Is IP masquerade and Network Address Port Translation(NAPT) the same? I'm not sure whether it is the same thing or not but I realized the mechanism is almost the same where both IP masquerade and NAPT changes TCP/UDP port and many-to-one relation is allowed:multiple private addresses share one global IP address. If it is different which part is IP masquerade and NAPT is different?

# Answer
IP masquerade is the same as NAPT and the only difference is that when NAPT is used in Linux, it is called IP masquerade. The mechanism is the same, it's just the place where the technology is implemented is different.
> 1 votes

---
Tags: computer-networks, ip
---


# Question
Title: How do I calculate the time complexity of this memoized algorithm?
The problem is: count all increasing subsequence of s.

```
def main():
    print(count([3,2,4,5,4]))

def count(s: list) -> int:
    n = len(s)
    counter = 0

    result = {}

    if n == 0:
        return 0

    for i in range(n):
        counter += recurse(s[i+1:], s[i], result)

    return counter

def recurse(s: list, x: int, result: dict) -> int:
    n = len(s)
    counter = 0

    if n in result:
        return result[n]

    if n == 0:
        return 1

    for i in range(n):
        if s[i] > x:
            counter += recurse(s[i+1:], s[i], result)

    result[n] = counter + 1

    return counter + 1

```

Can anyone help me what is the time complexity of this algorithm?
What I know is `T(count())` is `O(n) * T(recurse(n))`. Correct me if I'm wrong, `T(recurse(s1, ...))` will be `O(1)` if I already calculated `recurse(s1, ...)` and that will make `T(count(s)) = O(n)`.

# Answer
> 4 votes
Usually when trying to figure out a dynamic programming solution's time complexity, you need to find two values:

1. The number of elements that will be calculated (or a bound on this number. Notice that "elements that would be calculated" refers to the elements you save with the memoization technique)
2. The time it takes to process an item, assuming you know the results of every recursive call it would have done (or a bound on this number)

In your case:

1. The memoization saves elements up to $n=len(s)$ (every element in the dictionary is smaller or equal to $n$ and therefore you will calculate at most $n$ values)
2. Processing each element takes $O(n)$ time (in the `recurse` function, there is a `for i in range(n):`)

Therefore, for every **new** element you calculate (there are at most $n$ such values) you will spend $O(n)$ time, and thus the algorithm will take $n\cdot O(n)=O(n^2)$ **in the worst case analysis.**

Notice this is **not** an improvement from any naive algorithm that goes through every sublist - as by combinatorical counting there are ${n\choose2}={n!\over2!\cdot(n-2)!}={n\cdot(n-1)\over2}=O(n^2)$ different sublists

---
Tags: time-complexity, dynamic-programming, recursion, memoization
---


title: How private IP address is determined?

text:
# Question
Title: How private IP address is determined?
Today I presented about IP address during my online class based on Computer Networks by Andrew S. Tanenbaum and during QnA session, I was asked about private IP Address range.

```
10.0.0.0 – 10.255.255.255
172.16.0.0 – 172.31.255.255
192.168.0.0 – 192.168.255.255

```

The questioner asked my why private IP address is determined in such range. I haven't really think much about the range because I accept it as something that had been decided by the people who came up with this technology but I eventually have to present again because I couldn't answer the questioner's question. Perhaps there are reason behind why the private IP address is determined in such ways?

For example why it starts with 10 and not 9? or why it starts with 172 and not 173?

I tried to read in RFC 1918 but I couldn't really find the answer about why they chose 10 or 172 or 192.

If anyone can share link that I could refer to or know the answer, I would highly appreciate it.

Thank you.

# Answer
> 0 votes
"*The questioner asked my why private IP address is determined in such range*"

IMO a good answer is "Because it has been established in RFC-1918; which is a "Best Current Practice" RFC :-)

The three ranges allow private networks to "resemble" the class A-B-C subdivision (and probably this is what the questioner wanted to hear from you). See older RFC791: *.... To provide for flexibility in assigning address to networks and allow for the large number of small to intermediate sized networks the interpretation of the address field is coded to specify a small number of networks with a large number of host, a moderate number of networks with a moderate number of hosts, and a large number of networks with a small number of hosts....*. Also see Wikipedia Classful network for more details / references.

The reasons for the particular numbers are not well known (and are only interesting from a historical-folklore point of view), and probably the main criteria was to use address spaces that were free/unused at the moment.

* 10.x.x.x comes from the old ARPANET and is easy to remember
* 172.x.x.x was marked by IANA as "Special purpouse" block of IP addresses
* 192.168.x.x was used by Sun in its workstations (?!?)

---
Tags: computer-networks, ip
---


# Question
Title: How can i solve a recursion equation with square root using recursion tree method?
> $T(n) = \sqrt{2}T(\frac{n}{2}) + \sqrt{n}$

I am trying to solve this question by recursion tree method, do we have any way in which we can draw a recursion tree for this eqn.

I just don't want to use master or extended master theorem

# Answer
If you apply the recursive formula again to $T(n/2)$ you get the following: $$ T(n) = \sqrt{2}\cdot T(n/2) + \sqrt{n} \\T(n)= \sqrt{2}(\sqrt{2}\cdot T(n/4) + \sqrt{n/2}) + \sqrt{n} \\T(n)= 2\cdot T(n/4) + 2\sqrt{n}$$

For this formula you are now probably able to draw a recursion tree.
> 1 votes

# Answer
The first step is that you go and evaluate T(1024) by hand. You will find a factor $2^{27.5}$ in there and a lot more. Figure out the pattern, write down a conjecture what $T(2^k)$ would be, and prove it.
> 0 votes

---
Tags: algorithms, data-structures, computability, recurrence-relation
---


# Question
Title: Proving $\lceil \lg n \rceil -1 = \lfloor \lg n \rfloor$
I recently came across the question:

Show that there are at most $\lceil n / 2^{h + 1} \rceil$ nodes of height hh in any nn-element heap.

I looked for some solutions and found this one: Binary heap: prove that number of nodes of height h is not bigger than $\lceil \frac{n}{2^{h+1}} \rceil$

But I got confused with the answer which used the expression: $$\lceil{\log\_2n}\rceil-1$$ as the height of the tree.

But, I am confused because I have earlier proved that the height of the tree is:

$$\lfloor \lg n \rfloor$$

Even if I consider both are the same it could only be true if $\lg n$ returns a decimal value instead of an integer.

For example, consider an example of taking $n=4$ the example would fail as:

$$\lfloor \lg n \rfloor \le \lg n \le \lceil \lg n \rceil$$

Please help.

Thank you.

# Answer
> 1 votes
The expression $\lceil \log\_2 n \rceil - 1$ for the height of a $n$-element heap is wrong. For $n=1$ the expression yields $-1$ instead of $0$, for $n=2$ it yields $0$ instead of $1$, etc...

In general, for $i \in \mathbb{N}^+$, an heap with $2^i$ nodes has height $i$ but $\lceil \log\_2 2^i \rceil - 1 = i-1$.

The equality $\lceil \log\_2n \rceil -1=\lfloor \log\_2 n\rfloor$ is also wrong, as it can be seen by picking $n=2^i$ for any $i \in \mathbb{N}^+$.

---
Tags: algorithms, heap-sort
---


# Question
Title: Finding the connected subgraph of a given size with maximum number of edges, that includes a given vertex
Consider an undirected graph $G = \[V,E\]$. Let $V$ be the set of vertices: $V = \\{v\_1,..,v\_n\\}$ and $E$ be the set of edges. Let $C$ be the connected component that contains vertex $v\_1$. I want to find the connected subgraph (not sure about this terminology) with **maximum number of edges**, among all the connected subgraph of $C$ that satisfy the following:

1. includes vertex $v\_1$
2. has exactly $m$ number of vertices (including $v\_1$)

By connected subgraph of $C$, I mean a subgraph of $C$, such that each pair of vertices in it are connected by a path.

# Answer
> 5 votes
It's NP-hard (by reduction from clique problem).

Let $G$ be an arbitrary graph, and we want to check if there exists a clique of size $m-1$ in this graph. This problem is NP-hard. By adding $v\_1$ to the graph and connecting it to all vertices in $G$, we reduce the clique problem to your problem (since clique, when exists, has the maximum number of edges).

---
Tags: graphs, connected-components, subgraphs
---


# Question
Title: Why do we consider enumeration up to $\omega$ instead of leaving it to as many ordinal numbers?
A few minutes ago I asked a question about a "proof" that $\mathbb{R}$ is enumerable that crossed my mind: What's wrong with this "proof" that $\mathbb{R}$ is enumerable?

I was told to look into ordinal numbers, and that after crossing $\omega$ we stop considering something to be an enumeration.

Why is this the case? Are there negative consequences if we don't put this limitation?

Edit: I always thought of $\mathbb{N}$ as the "counting numbers" - but... when we cross over to ordinals like $\omega$, $\omega+1$, etc, aren't we still effectively counting?

# Answer
> 2 votes
A set $S$ is enumerable (or, countable) if we can enumerate it: $$ S = \\{s\_1,s\_2,s\_3,\ldots\\} $$ In other words, there is a mapping from $\mathbb{N}$ onto $S$.

Cantor showed that $\mathbb{R}$ isn't enumerable.

We can consider more relaxed notions of enumeration. For example, a set $S$ is well-orderable if there is a linear order $\<$ on $S$ such that any non-empty subset of $S$ has a minimum. This encompasses your examples, and much more.

The axiom of choice is equivalent to the well-ordering principle, which states that every set can be well-ordered. Hence if you assume the axiom of choice, *every* set can be enumerated in this sense.

---
Tags: enumeration
---


# Question
Title: Textbooks about non-RE languages for undergraduate students
I'd like to read up on non-recursively enumerable languages. Which textbooks should I look into to get a decent understanding about the subject?

Thank you.

# Answer
> 3 votes
Despite its name, Soare's book Recursively enumerable sets and degrees has lots of information about this. In particular, it covers in pretty good detail the **arithmetical hierarchy**.

(Incidentally, note that the non-r.e. elements of the arithmetical hierarchy aren't all "r.e.-hard." For example, consider any *minimal $\Delta^0\_2$ degree*, that is any Turing degree $\le\_T{\bf 0'}$ which is nonzero but not strictly above any nonzero Turing degree. There are infinitely many minimal $\Delta^0\_2$ degrees; by the Sacks Density Theorem, they are all non-r.e. and hence by minimality don't compute *any* nonrecursive r.e. sets. The way in which the r.e. degrees sit inside the $\Delta^0\_2$ degrees is actually fairly complicated.)

# Answer
> 2 votes
Any book on computability will cover the subject.

In any case, if a language is not recursively enumerable, it means no Turing machine (or program in any language, for that matter) is able to recognize it's members, not even given unlimited time to check. That essentially tells you that they are languages that are *very* hard to characterize.

There is an extension to Rice's theorem that characterizes languages that are recursively enumerable, that is a starting point for your quest.

---
Tags: books
---


# Question
Title: Time complexity of printing prime numbers within a range?
I've written an answer to this question, which asks about the following:

What is the time complexity for the given code that prints prime numbers from `start` to `end`? Is it $O(end\*\sqrt{n})$?

```
/**
 * Print prime numbers between start and end inputs
 * Time-Complexity: O(end * sqrt(n))
 * Space-Complexity: O(1) only one value as input
 * @param start, end
 * @return
 */
public void printPrimeSeries(int start, int end) {
    for (int i = start; i < end; i++) {
        if (findPrimeOrNot(i)) {
            System.out.println("The value " + i + " is a prime number");
        }
    }
}

public boolean findPrimeOrNot(int n) {
    for (int i = 2; i <= Math.sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    System.out.println("Enter start number for prime:");
    int startInput = scanner.nextInt();

    System.out.println("Enter end number for prime:");
    int endInput = scanner.nextInt();

    PrimeNoSeries primeNoSeries = new PrimeNoSeries();
    primeNoSeries.printPrimeSeries(startInput, endInput);
}

```

*Notice: That's not my code. It's by mahesh87.*

My answer to that is:

---

In your case $n$ is `end - start`. In $O$ notation $n$ represents the problem size, which is the range between `start` and `end` in your case. In $O$ notation you are interested in the worst case, therefore we can assume that `start` is always `0`. Now $n$ is just an alias for `end`.

As we have defined $n$, it's obvious that `printPrimeSeries` is just $O(n)$ (from `0` to `end`). The method uses `findPrimeOrNot` that iterates from `2` to `Math.sqrt(n)`, which is $O(\sqrt{n})$. Combining both is $O(n)O(\sqrt{n})$, which is just $O(n\sqrt{n})$.

Notice that the $O$ notation tells you something about the asymptotic behaviour of the algorithm. It doesn't matter too much if there are 2 parameters, at least in this case.

So yes, your assumption is fully correct (ignoring that you've written `end` instead of $n$).

---

Other users have proposed that the correct answer is $O((end - start)\sqrt{end})$. I think this is a valid point of view but it doesn't provide any beneficial information in terms of $O$ notation for the given case.

Now my question: What is the formally correct way to describe the time complexity of the given algorithm? Is my reasoning valid or is it just plain wrong?

# Answer
Both "the time complexity is $O( end \cdot \sqrt{end} )$" and "the time complexity is $O( (start-end) \cdot \sqrt{end} )$" are correct statements (assuming that arithmetic operations on the involved integers can be performed in constant time).

The second upper bound is tighter in some cases. For example, setting $start=end-10$ the first upper remains unchanged while the second one simplifies to $O(\sqrt{end})$.

Also notice that "In notation represents the problem size, which is the range between start and end in your case." is false. The size of (any reasonable encoding of) the instance is $O(\log end)$.
> 2 votes

# Answer
Your function findPrimeOrNot(n) runs in $O(n^{1/2})$ in the worst case. Often the execution time is faster. For example for even numbers n, the function returns after a single divisions. But for primes, where all divisors up to sqrt(n) are tested, the execution time is indeed $\Theta(n^{1/2})$. And the chance that a random integer x is prime is about x / log x.

You would have to check what exactly the average number of divisions is. With your algorithm, which can be improved, the number of divisions is at least about (end - start) * sqrt (n) / log n and at most about (end - start) * sqrt (n) divisions.

If you want to print the primes, you'll find that printing has such a large constant factor that the execution time of printing about (end - start) / log n primes is much larger than the time for printing the primes, for any reasonable range of primes.
> 1 votes

---
Tags: time-complexity, big-o-notation
---


# Question
Title: Call stack is hard to maintain in my brain. What should I?
When I study Binary Search Tree, I try to use a pencil and paper to scratch the process of in-order traversal. However, I find that it is hard to maintain the call stack in my brain without paper and notes when the height BST is high.

Question: What should I? Is it normal and should I practice more?

# Answer
> 2 votes
**Do not consider call stacks for recursive algorithms**. *Ever*. Forbidden!

Learn to understand recursive algorithms like any other algorithm that calls other procedures: *Assume* the calls do their work correctly, and concentrate on making sure the right calls are made, and the results are combined correctly.

Separately, try to find some criterion by which the recursive calls are to "smaller" instances of the problem (assuming instance sizes are e.g. positive integers), and that all "small enough" instances are solved correctly by "base cases" (without recursive calls).

Often the recursive algorithm is modelled on some recursive definition of the structure at hand, then the mapping is simple to prove correct. For an entertaining example of a recursive program that doesn't clearly fall into this category, read and *understand* Rob Pike's regexp matcher (exegesis by Brian Kernighan)

# Answer
> 1 votes
When you are traversing a search tree, the most recently visited node uniquely determines which node will be visited next. (*Visited* here means actually outputted by the traversal—a node can be at the top of the stack multiple times during a traversal but is only *visited* during a traversal once.) So there is no reason to try to keep the entire stack in your head when working something out on paper. You can figure out what the stack has to be at any point just by looking at which node you most recently visited.

Exercise: Try looking at a binary tree and just reading off the nodes in the order they will be visited by an in-order traversal *without* keeping track of the stack manually.

---
Tags: binary-search-trees, stacks
---


# Question
Title: With Σ = {a,b}, give a dfa for L= w1aw2 : |w1 |≥ 3, |w2 |≤ 5}
I racked my brain,I saw other people's solutions and it don't make sense. I think my biggest problem is I don't know when one string ends,like for example w1 is \>=3 and it can have how many ever b's or a's as long as it's 3 and above,so when do we get to have the First a that's after the W1?how do I make sure it's not a part of the W1? that's whats so confusing the W1 string can have as many a's as it likes which means it should have an a loop,but you can't have an a loop cause YOU NEED 1 A EXACTLY after the W1 string. this is a catch 22,damned if you don't damned if you do..help please I spent an hour on this to no avail. I tried every possible thing and saw people's solutions and I feel like when they solved it they are either dismissing what I mentioned above,or something is going COMPLETELY over my head.

# Answer
> 0 votes
Picture the strings you are interested in. You want an 'a' not farther than 5 from the end, and at least 3 away from the beginning. Translate the "at least 3 from the start" and "at most 5 from the end" into states...

---
Tags: computability
---


# Question
Title: Build PDA for a language with unknown input alphabet
$L\_1 ,L\_2$ are regular language. We form a new language $L\_{12}$ as follows: $$L\_{12}=\left \\{ w\_1\cdot w\_2\mid w\_1\in L\_1\land w\_2\in L\_2\land |w\_1|=|w\_2| \right \\}$$

In this exercise I am not given any alphabet and I'm required to build a PDA for $L\_{12}$. But by definition $M=\left \\{Q,\sum,\Gamma,\delta ,q\_0,\dashv,F\right\\}$ and I don't have any alphabet to work with. By intuition similar alphabets can affect the solution differently than dissimilar alphabets.

# Answer
> 0 votes
You might reason like this: If $L\_1, L\_2$ are regular, then $L\_2^R$ is regular ($L^R$: reverse words). You can build regular grammars $G\_1 = (N\_1, \Sigma\_1, P\_1, S\_1)$ and $G\_2 = (N\_2, \Sigma\_2, P\_2, S\_2)$ that generate $L\_1$ and $L\_2^R$. The crucial point is that the regular grammars have the lonely non-terminal always at the end (or beginning!) of the sentential form. Build a CFG with nonterminals $Q = N\_1 \times N\_2$, and productions that build up $L\_1$ to the left (using the first part of the nonterminal) and $L\_2^R$ to the right (using the second part of the nonterminal, building from the end). From the resulting grammar you can build a PDA.

The basic idea is similar to the construction for $\\{ w w^R \colon w \in \Sigma^\*\\}$ with $S \to x S x$ for all $x \in \Sigma$ and $S \to \varepsilon$ (or $S \to xx$ for purists).

# Answer
> 0 votes
Let $\Sigma\_1$ be the alphabet for $L\_1$ and $\Sigma\_2$ be the alphabet for $L\_2$. By definition, $\Sigma\_1,\Sigma\_2$ are both finite.

Then, assume $\Sigma\_1=\\{\sigma\_1,\sigma\_2,...,\sigma\_n\\},\Sigma\_2=\\{\mu\_1,\mu\_2,...,\mu\_k\\}.$

Now, define $\Sigma=\Sigma\_1\bigcup\Sigma\_2$ and let it be the alphabet for $L\_{12}$.

**Notice:** In general, when talking about languages - we **must** specify what language we are working with (by definition of what a language is) - **but** *usually* we assume the binary alphabet ($\Sigma\_{bin}=\\{0,1\\}$) or any other alphabet with 2 or more letters (more than two letters is just for ease of use), since you can encode every letter as a series of 0's and 1's. In rare cases, we might assume the unary alphabet ($\Sigma\_{unary}=\\{1\\}$) but that is more useful (and you will see it probably) in Complexity Analysis (and not for PDA's and DFA's).

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


# Question
Title: What is minimization (μ-function) in layman tems?
In Computer Science μ-function is used to extend set of primitively recursive functions to generally recursive functions, and I can't understand what this function does.

There is a lot of formulae, but I can't understand what is is. Let's say I'm writing in Python (or any other general purpose language). What are examples of μ-function IRL?

# Answer
This is minimization in Python:

```
def mu(p):
    n = 0
    while not p(n):
        n += 1
    return n

```

It is a slightly more complicated exercise to convert a `while` to $\mu$, but essentially, $\mu$ performs a search for the first (*minimal*) number satisfying a given condition, where there is no guarantee that the search will succeed.
> 2 votes

---
Tags: computability
---