# Question
Title: Why is it that Btrees most of the times have a degree that is odd? What happens if they are even?
I was watching a lecture video and the Professor states that it would be very rare to see the order of a Btree to be even. I was hoping for an explanation but he cut it off there and moved on with the lecture.

# Answer
I don't think there's a right answer to this but you could argue for a preference either way.

Let's define B-tree order `m` like this

* max children/values `m`
* min children/values `m/2`
* max keys `m-1`
* min keys `Math.ceil(m/2)-1`
    + `Math.ceil` is only needed if `m` is *odd*

If `m` is even, the you have an odd number of keys. For example `[a b c]`, we could split this either `[a b] [c]` (left bias) or `[a] [b c]` (right bias). If `m` is odd you have an even number of keys. `[a b c d]` would always split into `[a b] [c d]`.

The opposite is true for values. i.e. when you have an even number of keys you have an odd number of values. In which case you need to pick either a left or right bias.

If you declare upfront that you won't deal with odd or even you get a little bit less to think about.

Other than that, it's an arbitrary decision. There's no benefit to either choice.
> 2 votes

# Answer
One thing that distinguishes real-world B-trees from "lecture B-trees" is that real B-trees tend to have nodes and leaves where the size *in bytes* is fixed. So the "degree" of a B-tree is determined by the number of keys that will fit on a page.

So if the keys vary in size (e.g. strings), the "degree" of different nodes may be different. Roughly 50% of them will have even degree.
> 3 votes

---
Tags: b-tree
---


# Question
Title: Is the Clique Problem polynomial time reducible to the graph-Homomorphism Problem and if so what does the reduction look like?
Is the k-Clique Problem (given a Graph G and a natural number k does G kontain a Clique of size k)
polynomial time reduzible to the graph-Homomorphism Problem (given two graphs, G and H, is there a Homomorphism from G to H)

And if so what would the reduction look like?

Since i am a little confused by the subject, is the following correct?

A polynomial time reduction from Clique to graph-Homomorphism is a funktion that can be calculated in polynomial time and for which if you input a yes instance of clique it returns a yes instance of graph-Homomorphism, same for no instances.

# Answer
> 1 votes
The $k$-clique problems asks whether there is a homomorphism from the $k$-clique to a given graph. Therefore in principle, given an instance $\langle G,k \rangle$ of $k$-clique, you can just output $\langle K\_k, G \rangle$, which is an instance of graph homomorphism.

However, in general $\langle K\_k, G \rangle$ could be much larger than $\langle G,k \rangle$, since encoding $k$ takes $\Theta(\log k)$ bits, whereas encoding $K\_k$ probably takes $\Theta(k^2)$ bits (depending on your encoding). Assuming that graphs are encoded as adjacency matrices, the solution is to compare $k$ to the number of vertices in $G$. If $k$ is larger than the number of vertices in $G$, then the answer is No, and so you can output a fixed No instance (say $K\_2,K\_1$). Otherwise the size of the output instance is polynomial in the size of the input instance, and so there is no problem.

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


# Question
Title: An NP-hard problem reduces to its complement?
I found this statement in a true/false test section:

Could someone explain in laymans why this is a true statement?

My understanding is that if $X$ is $\mathcal{NP}$-hard, then its complement must be $\operatorname{co-\mathcal{NP}}$-hard. However, here we are assuming that a language that is $\operatorname{co-\mathcal{NP}}$-hard ($\overline X$) is reduceable to an $\mathcal{NP}$-complete language (3SAT). This is where I get lost. I think this means $\mathcal{NP}$-hard = $\mathcal{NP}$, and thus $X$ will reduce to its complement in this world.

# Answer
First note that $\overline X$ is $\operatorname{co\mathcal{NP}}$-hard since $X$ is $\mathcal{NP}$-hard (try to see why). Since 3SAT is in $\mathcal{NP}$, any problem that can be reduced to 3SAT is in NP as well. So the statement suggests that the $\operatorname{co\mathcal{NP}}$-hard language $\overline X$ is in $\mathcal{NP}$.

On the other hand, saying that $\overline{X}$ is in $\mathcal{NP}$ is equivalent to saying that $X$ is in $\operatorname{co\mathcal{NP}}$. So in total we have $X \in \operatorname{co\mathcal{NP}}$ and $\overline X$ is $\operatorname{co\mathcal{NP}}$-hard. So we get $X \leq\_m^p \overline X$ by the definition of hardness.

---

Here is a bit of intuition of the fact that, if $X$ is $\mathcal{NP}$-hard, then $\overline{X}$ is $\operatorname{co\mathcal{NP}}$-hard.

Let $A$ be an arbitrary language in $\operatorname{co\mathcal{NP}}$. We have to show that $A \leq\_m^p \overline{X}$. Let $B := \overline{A}$. Then $B$ is in $\mathcal{NP}$ and hence, $B \leq\_m^p X$. This means there is a function $f$ computable in polynomial time, such that for an arbitrary word $x$, $x \in B$ if and only if $f(x) \in X$.

Now we show that $A \leq\_m^p \overline{X}$. For a given word $x$. Using the same reduction $f$, we have $x \in A$ if and only if $x \notin B$ if and only if $f(x) \notin \overline{X}$ if and only if $f(x) \in X$.

---

Another note. Your intuition was right, but in the sentence

> I think this means $\mathcal{NP}$-hard = $\mathcal{NP}$, and thus $X$ will reduce to its complement in this world.

You should have probably said $\mathcal{NP}$ = $\operatorname{co\mathcal{NP}}$.
> 1 votes

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


# Question
Title: What happens when the xor inBlock chaining returns false?
"With block cipher, each plaintext block is XOR-ed with the previous ciphertext block and then encrypted, this is known as block chaining. This prevents identical blocks of plaintext from producing the same ciphertext each time they are encrypted"

What happens inside the clause of the "XOR" statement, to make two equal plain text blocks encode into two different cipher text blocks?

# Answer
> 1 votes
Say you have blocks ABCDEA that you want to encrypt. If you do this naively, then the first and second A produce the same encrypted result, and an attacker would know that your first and last block are the same.

Instead you encrypt to A’B’C’ etc. by encrypting A -\> A’, A’ XOR B -\>B’, B’ XOR C -\> C’, ..., E’ XOR A -\> F’. It looks like you are encrypting random data, nothing an attacker can do.

The identical plain text blocks are XOR-ed with different previously encrypted blocks, that what’s making them different.

---
Tags: encryption, xor, blockchain
---


# Question
Title: How much time (in hours) will it take to check if the number with 20 binary digits is the prime number?
How much time (in hours) will it take to check if the number with 20 binary digits is the prime number, in problem it's mentioned that for number with 10 digits it took 1 hour it's also said that the number has been checked using AKS pirmality test and it's also given that log(n) is the lenght of the number to be verified.

# Answer
> 4 votes
Primality testing is very fast with the Miller–Rabin algorithm \[1\]. You can use the deterministic variant with witnesses 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37 to test any 64 bit number in $O(\log^3 n)$ time. This should take less than one second with any reasonable implementation.

\[1\] https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin\_primality\_test

---
Tags: algorithms, primes, binary
---


# Question
Title: Dominating set in bounded degeneracy and bounded degree graphs
I believe Minimum Dominating Set (MDS) is NP-hard for bounded degeneracy and their subset bounded degree graphs, but a paper appear to suggest tractability. Enumeration of Minimal Dominating Sets and Variants p.5

> Proposition 1. Dom admits a polynomial delay algorithm when restricted to

1. Strongly chordal graphs.
2. Graph classes of bounded degeneracy.

The delay of the algorithm is the time between enumerating two MDSs after polynomial preprocessing (unless I have misunderstood the definitions on p. 3). According to graphclasses.org MDS is linear for strongly chordal graphs.

Does the paper imply $\exp(o(n))$ complexity of MDS for graphs of bounded degeneracy (and bounded degree)?

# Answer
> 2 votes
No it does not. The problem DOM considered by the paper seems to be the enumeration of **minimal**, not minimum dominating sets. Usually minimal means a solution $X$ such that there is no other solution $X'$ with $X' \subsetneq X$. The solution $X$ is not necessarily the minimum size. While minimal dominating sets can be enumerated with polynomial delay in bounded degeneracy graphs, there seems to be no guarantees that this enumeration finds the minimum dominating set before enumerating an exponential number of dominating sets that are minimal, but not minimum.

---
Tags: algorithms, complexity-theory, graphs
---


# Question
Title: why is the NL solution PATH negated unsufficient to prove unreachability
I'm currently reading into complexity classes and one think will not fit into my head. We are investigating NLogSpace with the Path/reachability problem. There is a nondeterministic LogSpace algorithm which can solve reachability, but its inversion does not prove nonreachability because "it could miss a path". How is it possible to miss a path? Wouldn't it imply that the reachability test might doesn't work? Can somebody please explain it to me? Thank you.

# Answer
> 0 votes
maybe i was a bit to specific, i had a general misunderstanding in how non-deterministic machines work. Here is what i figured:

an accepting nondeterministic turing machine always gives the right answer ("found something, therefore a solution exists", on the other hand, a reject means "did not find anything" which is not the same as "there is no solution"

therefore a reject can't be trusted and any algorithm which uses a reject from a non deterministic (Existance) machine has to double check. Also this implies, that a non-deterministic machine could give a false negative.

---
Tags: complexity-theory
---


# Question
Title: Fastest algorithm for transforming points into graph
Given a set of $n$ two-dimensional points in the plane $$\\{ (x\_1, y\_1), (x\_2, y\_2), \dots, (x\_n, y\_n)\\}$$ and a real number $M$, I want to transform this set of points into a graph with the points as vertices with an edge between points $A$ and $B$ if the distance between $A$ and $B$ is at most $M$.

What is a fastest algorithm that can perform this task?

# Answer
> 2 votes
As you can imagine, evaluating every pair of points is very expansive ($O(N^2)$ for $N$ points).

If your set of point is sufficiently dense with respect to $M$, a simple solution is to use a grid. Build a grid of $M \times M$ cells, then for each cell, compute the list of points inside (doing one loop on points $O(N)$). Finally you just have to compare every point with every other point in the same cell or in one of the 8 surrounding it.

If you set of points is very dense you even can use a second grid of $\frac{M}{\sqrt{2}} \times \frac{M}{\sqrt{2}}$ cells so the points in the same cells have necessarly pair-wise distance lower than $M$. This may save some computation.

Note that in the case you have lot of empty cells (small density), it may generate memory issue. Imagine for instance 2 pairs of points very distant to each other (with respect to $M$). It may require a tremendeous grid, just to process 4 points... In this case, the basic "all-pair" comparison would be largely more efficient. k-d tree may be a solution to this problem. Or you can either identify the empty zones to process the points subset by subset.

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


# Question
Title: How to construct a DFA which accepts all the strings endig with aa and no two consecutive b (bb)
I have to construct a DFA which ends with aa and does not contain any pair of b-s. A = {a,b}, {aa,baa,aaa,abaa,babaa,...}. I know how to construct them as separate DFAs but not together merged.

# Answer
If you know how to construct DFAs for two languages separately, you can use systematic methods to build the DFA which recognises the intersection of the languages (e.g. https://math.stackexchange.com/questions/147457/intersection-of-two-deterministic-finite-automata). However to achieve a minimalist and elegant result (as well as for learning purposes) you may want to try and find ad-hoc methods. NB: You can always apply a DFA minimization procedure to 'clean up' the automaton obtained via the above general method (https://en.m.wikipedia.org/wiki/DFA\_minimization).
> 2 votes

---
Tags: graphs, finite-automata, strings
---


# Question
Title: NFA equality for automata with partial transition functions and all states accepting
Given two nondeterministic finite state automata with partial transition functions, such that all states are accepting, except for the implicit failure sink state, is it possible to decide in polynomial time whether the two automata recognize the same language? Or is it perhaps PSPACE-hard, like the same problem for general NFAs?

# Answer
The problem is PSPACE-complete, by reduction from the equivalence problem for NFAs.

Suppose we are given two NFAs $A\_1,A\_2$ over an alphabet $\Sigma$. Let $\dashv$ be a new symbol. To each of the NFAs we add two new states $q\_f,q\_t$, and the following transitions:

* An $\epsilon$-transition from the initial state to $q\_t$.
* A self-loop on $q\_t$ labeled $\Sigma$.
* A transition labeled $\dashv$ from every accepting state to $q\_f$.

Let $B\_1,B\_2$ be the new NFAs, after making all of their states accepting. Then $$ L(B\_i) = \Sigma^\* \cup (L(A\_i)\dashv). $$ Therefore $L(A\_1) = L(A\_2)$ iff $L(B\_1) = L(B\_2)$.
> 3 votes

---
Tags: automata, finite-automata, theory
---


# Question
Title: In which paper is written that you can transform one problem to another to show NP-completeness?
For example in this post they discuss how to construct a reduction between problems to show that one probleme is NP-Hard: Post

I am searching for a scientific paper to cite where it is written, that this is a valid method.

Does anybody knows one?

# Answer
> 1 votes
If I may make an assumption, you want such a reference to be able to put it in one of your works, right ? I don't why you would wanna do that as if you have a problem A, reducting a NP Hard problem to problem A quite clearly shows that A is NP Hard. No one bothers proving it as it's such a straightforward and fundamental result. If you need to prove it for some reason you can do it in two lines. If you still want a reference for a reader to read about NP in general then just quote Arora and Barak's book on complexity theory.

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


# Question
Title: Can someone explain me the Credit-Debit proof method for calculating operations?
I've started taking a data structure course and we are currently learning about different data structures. We also learned when to increase the capacity of an array by creating another array with double the size of the original one.

The proof used to demonstrate this was a credit-debit proof where each operations has a cost. ex: doubling an array cost 2 dollars reducing an array by half cost 1 dollar.

I simply don't understand how proof of that type works. Doing a quick online search I haven't find the term credit-debit used to refer to this. Maybe It's not its name? Would be nice if someone could give me some links that explain those proofs.

# Answer
I believe you are referring to the *accounting method* for amortized analysis. With these keywords you should be able to find the explanations you are looking for.
> 3 votes

---
Tags: complexity-theory, proof-techniques
---


title: Primitive word and cyclic rotations

text:
# Question
Title: Primitive word and cyclic rotations
**Definition.** A word $w \in \Sigma^\*$ is primitive if $w=u^n \rightarrow n=1$.

Is it true that a word is primitive if and only if its all cyclic rotations are dstinct?

# Answer
> 5 votes
Yes, this is true. The direct implication ($\Rightarrow$) is the hardest to prove, and you will need the following lemma: two words commute if and only if they are powers of the same word (R.C. Lyndon and M.P. Schützenberger, The equation a M = bncp in a free group, Michigan Math. J. 9 (1962) 289-298. Or in this: H. Petersen, On the language of primitive words, Theor. Comp. Sci., 1996 https://doi.org/10.1016/0304-3975(95)00098-4). The rest of the proof should be straightforward enough.

---
Tags: strings, word-combinatorics
---


title: Even Odd problem

text:
# Question
Title: Even Odd problem
"A" represents all the odd natural numbers and "B" represents all the even natural numbers. For a given integer v, we can reduce it either by A0 or (A0)+1 then B0 or (B0)+1 and so on until the value of v becomes \<=0. Considering that we chose (Ai) or (Ai)+1 and (Bi) or (Bi)+1 optimally where i is the index, we want to know whether the last reduced value is from set A or B.

For example if v=1 or v=2, the answer will be A but for v=3 answer will be B.

# Answer
> 0 votes
I think we can phrase the question in game playing terms as follows:

Starting from some positive integer value $v$, players $A$ and $B$ take it in turn to subtract numbers until the running total is equal to or less than $0$. On their first turn player $A$ may subtract $1$ or $2$; then player $B$ may subtract $2$ or $3$, then player $A$ may subtract $3$ or $4$ and so on. The player who makes the final move, making the running total less than or equal to $0$, wins. With optimal play from both $A$ and $B$, which player wins for a given value of $v$ ?

Here is an approach this problem:

1. The running total after $1$ turn is $v-1$ or $v-2$. The running total after $2$ turns is $v-3$, $v-4$ or $v-5$. Show that the running total after $n$ terms lies between $v-T\_n$ and $v-T\_{n+1}+1$, where $T\_n$ is the nth triangular number (the sum of $1 \dots n$).
2. Suppose $T\_n \le v \< T\_{n+1}$. If $n$ is even show that $A$ will want to maximise the running total after $n$ turns and so will always choose to subtract the lower value on their turn; whereas $B$ will want to minimise the running total after $n$ turns and so will always choose to subtract the higher value on their turn. If $n$ is odd show that the strategies are reversed; $A$ will always choose to subtract the higher value and $B$ will always choose to subtract the lower value.
3. Show that if both players follow their optimal strategy as described in (2) then the running total after $n$ turns is $v-\frac{n^2+2n}{2}$ if $n$ is even or $v-\frac{(n+1)^2}{2}$ if $n$ is odd.
4. Show that $B$ will win if $2m^2+1 \le v \le 2m^2+2m$ for some integer $m$ and $A$ will win otherwise.

---
Tags: algorithms
---


# Question
Title: Operating System code suffers more cache misses than user code
I was going through the text of the book Computer Architecture: A Quantitative Approach. It has a section in Chapter 5 where it discusses the fact that OS code undergoes more cache misses as compared to user code. Here is the text:

> Although the user code executes more instructions, the behavior of the operating system can cause more cache misses than the user processes for two reasons beyond larger code size and lack of locality. **First, the kernel initializes all pages before allocating them to a user, which significantly increases the compulsory component of the kernel’s miss rate.** Second, the kernel actually shares data and thus has a nontrivial coherence miss rate. In contrast, user processes cause coherence misses only when the process is scheduled on a different processor, and this component of the miss rate is small. This is a major difference between a multiprogrammed workload and one like the OLTP workload.

What is the first argument trying to explain? My doubt is that although the kernel has to initialize the pages for allocation to a user, it(the kernel) is not required to retrieve data from those pages into cache. That is the user code's responsibility. Hence, the argument seems confusing.

# Answer
There's cache misses when you access a page for the first time, then you get hits. Since the kernel initialises the page, it gets all the cache misses. Then it passes the page to the user code, which gets cache hits.

The same misses would happen in user code if the kernel didn't initialise the page.
> 2 votes

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


# Question
Title: Policies for handling symbols leaking out of a lexical scope
Suppose it's possible for a symbol to escape the scope in which it is defined. What are considered the possible policies for handling that? I mean possible in the sense of what choices of language design that could be implemented -- different choices yield languages which differ in this respect.

For example, it's conceivable that two lexical scopes might each contain a symbol named "x". If these symbols escape from their respective scopes, what can we say about that? I can see three possibilities: all symbols named "x" are the same, so the symbol leaked out of the first scope is the same as that leaked out of the second; or each symbol named "x" is actually a distinct symbol, so the leaked symbols are not the same; or when a symbol escapes from its scope, something about that lexical context is carried along with the symbol, so that the result of the leakage is not a symbol but a more complex object representing the lexical context or environment and the symbol together. No doubt there are other possibilities.

I know Common Lisp implements the first policy -- `(eq (let (x) 'x) (let (x) 'x))` yields T. I think Scheme does too. I don't know enough about other languages to say what might happen. I'm not aware of languages which implement the second or third ideas, but, as I was saying, my awareness is limited, and I would be interested to hear about any such languages.

I'm sure this is a topic which is well-known in the programming languages field, but through some reading and searching I haven't found it yet.

# Answer
> 1 votes
Your `(let (x) 'x)` will just return the atom `x`, and obviously all of those are the same. That you define variables called `x` (and give them no value whatsoever, and never use them) is just confusing the issue. I.e., your code is a roundabout way to write `(eq 'x 'x)`.

How could a name "escape" from a lexical scope? The scope is precisely where the name has a particular meaning, an "escape" would just expand that scope somehow.

E.g. in Steelbank Common Lisp:

```
* (let (x) 'x)
; in: LET (X)
;     (LET (X)
;       'X)
;
; caught STYLE-WARNING:
;   The variable X is defined but never used.
;
; compilation unit finished
;   caught 1 STYLE-WARNING condition
X

```

enter code here

---
Tags: programming-languages, closure-properties
---


title: Can a DFA have an unreachable state?

text:
# Question
Title: Can a DFA have an unreachable state?
I am trying to prove or disprove the following statement:

> If $A = (\Sigma, Q, \delta, q\_0, F)$ is a complete DFA where $F \neq \emptyset$ then $L(A) \neq \emptyset$

So my initial thinking is to find a counter example. If say we were to construct a DFA with one accepting state, and that state is never reached then the proposition is false.

For instance :

Assume we have the following automaton

So my question is , are we allowed to have such a state in a DFA ?

# Answer
> 14 votes
You are indeed allowed to have unreachable states in DFAs (or NFAs, or various other automata models).

You may wonder what is the point of having them, given that they are unreachable and have no effect on the language.

Well, automata are typically not designed by hand. Rather, they are usually obtained *algorithmically* by translation from other types of specifications, models, etc.

These translation algorithms often don't guarantee that there are no unreachable states, and very often there are many unreachable states. For example, take the subset construction, that transforms an NFA to an equivalent DFA. There are typically many unreachable states in the naive construction (although it can be optimized to construct only the reachable states).

However, there are other constructions that are much more involved (e.g., the translation of Linear Temporal Logic to Nondeterministic Buechi automata).

In fact, one of the most fundamental algorithms on automata is that of emptiness -- check whether the language is empty. To do so, we look for a reachable accepting state. If automata only had reachable states, we would only have to check whether there *are* accepting states, but this is not enough.

Finally, I'll remark that this algorithm is often symbolic, in that you don't run it on an explicit automaton, but on a symbolic representation. For example, you can check emptiness of a DFA constructed by determinizing an NFA without actually contstructing the whole thing.

# Answer
> 8 votes
Check the definition. It usually goes like $M = (Q, \Sigma, \delta, q\_0, F)$, with $Q$ a finite set of states, $\Sigma$ the (input) alphabet, $\delta \colon Q \times \Sigma \to Q$ the transition function, $q\_0 \in Q$ the initial state, $F \subseteq Q$ the set of final (accepting) states. Note that the only condition on $\delta$ is it being a function. To exclude "nonsense" like unreachable states would complicate the definition enormously, and force complex pŕoofs to otherwise quite elegant constructions (like the subset construction for NFA to DFA, where you just declare all subsets of states of the NFA as states of the DFA -- often the vast majority of the subsets are impossible).

Most mathematical definitions are given in such a way as to capture what is relevant and make the concept easy to work with, perhaps allowing nonsense that doesn't hurt. Simplicity (of proofs) is key.

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


title: Minimum spanning tree formulation

text:
# Question
Title: Minimum spanning tree formulation
Can any expert explain the reasoning behind the constraint in the following formulation of the minimum spanning tree?

> To formulate the minimum-cost spanning tree (MST) problem as an LP, we associate a variable $x\_e$ with every edge $e \in E$. Each spanning tree $T$ corresponds to its *incidence vector* $x^T$, which is defined by $x^T\_e = 1$ if $T$ contains $e$ and $x^T\_e = 0$ otherwise. Let $\Pi$ denote the set of all partitions of the vertex set $V$, and suppose that $\pi \in \Pi$. The *rank* $r(\pi)$ of $\pi$ is the number of parts of $\pi$. Let $E\_\pi$ denote the set of edges whose ends lie in different parts of $\pi$. Consider the following LP: $$ \begin{align\*} \min &\sum\_{e \in E} c\_ex\_e \\ \text{s.t. } &\sum\_{e \in E\_\pi} x\_e \geq r(\pi) - 1 \quad \forall \pi \in \Pi, \\ & x \geq 0. \\ \end{align\*} $$

# Answer
> 1 votes
The constraint expresses the following fact:

> Let $T$ be a spanning tree, and suppose that we partition the vertex set into $r$ parts. There are exactly $r-1$ edges of $T$ which connect different parts.

For example, if $T$ is a tree and $C,\overline{C}$ is a cut, then exactly one edge of $T$ crosses the cut, that is, connects $C$ and $\overline{C}$.

---
Tags: integer-programming, minimum-spanning-tree
---


# Question
Title: Using a point as an input for a perceptron
Can a point be used as the input for a perceptron/neural net?

The relationship between the two numbers that make up a 2D point does not affect the output, but does this not matter when the satisfactory weights are found?

If I wanted to use a point $(x,y)$ as an input for my perceptron, would I simply have two input nodes, one for $x$ and one for $y$?

# Answer
Yes, you can do that. Nothing prevents it. Yes, you'd have two inputs, one for $x$ and one for $y$. You might want to normalize those values so they are in the range $\[-1,1\]$ or $\[0,1\]$.
> 0 votes

---
Tags: machine-learning, neural-networks, perceptron, neural-computing
---


title: Finding lost bottle (algorithm problem)

text:
# Question
Title: Finding lost bottle (algorithm problem)
The question is as follows:

> A scientist creates a new compound, called compound A, that will explode 10 days after being mixed with compound B. This compound A was stored in a label-less bottle on a shelf with $n-1$ bottles of non-reactive material, and the scientist doesn't know which is compound A. There is exactly one bottle of compound A among the $n$ bottles on the shelf. The scientist has $O(log(n))$ beakers full of compound B. How can he determine which of the $n$ bottles is the compound A in exactly 10 days time?

I am a little stuck because I don't know how to narrow down the specific bottle in only 10 days. It is pretty obvious that you can just apply the first half of the bottles to the first beaker, and then if it doesn't react you know that the desired bottle is in the second half and so forth. But how do I narrow it down without witnessing the results of the first few tests?

We need to create something where a series of explosions will help us narrow down which one it is (lets say at first its amongst n/4, then n/10, then n/100, etc). How the heck do I do this?

# Answer
This is a classical problem that I have previously seen framed as a puzzle rather than a CS question (with some fixed $n$ and fixed number of beakers), though I don't remember any source for it.

You can solve it as follows: Number your bottles from $0$ to $n-1$, and label your beakers from $1$ to $\lfloor\log\_2(n-1)\rfloor+1$ (the number of bits needed to represent numbers $0$ to $n-1$ in binary).

Now for every bottle, do the following: let $x$ be the label of the bottle. For every $i$ such that there is an $1$ at the $i$'th position in the binary representation of $x$, put a bit of that bottle's compound in beaker $i$.

Now after 10 days, the beakers which explode will exactly spell out the number of the explosive bottle in binary.
> 2 votes

---
Tags: search-problem, algorithm-design
---


# Question
Title: Time complexity of combinations of n pairs of parentheses
I have the following code snippet for combinations of n pairs of parentheses.

```
def parens(n):
    if n <= 0:
        return ['']
    else:
        combinations = []
        helper('', n, n, combinations)
        return combinations

def helper(string, left, right, combinations):
    if left <= 0 and right <= 0:
        combinations.append(string)
    else:
        if left > 0:
            helper(string + '(', left - 1, right, combinations)
        if right > left and right > 0:
            helper(string + ')', left, right - 1, combinations)

```

What's the reasonable estimation of the time complexity of it?

My trials:

1. (2n)!/n!n! since it's permutations of multisets with more limitations.
2. Resolve recurrence: T(n) = 2T(n-1) =\> O(2^n).

# Answer
Actually, for every combination of parenthesis, your algorithm performs $\Theta(n)$ amount of work (to build the string and append it to your list of combinations).

The number of valid combinations of $n$ pairs of parenthesis is the $n$'th Catalan Number $C\_n = \frac{1}{n+1}\binom{2n}{n}$.

Thus, your algorithm runs in $\Theta(nC\_n)$ which is also equal to $\Theta(\frac{4^n}{\sqrt{n}})$, because $C\_n$ grows as $\Theta(\frac{4^n}{n^{3/2}})$ (see the linked Wikipedia article).
> 2 votes

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


# Question
Title: Find the closest sum possible to a given sum from rows of a matrix
I should design an algorithm, using dynamic programming, that gets as an input a matrix, named A, with n rows and k columns. Each cell in matrix A contain a natural number. You also get a number that represents a limited sum, and you should choose only one number from each row, to get the closest sum possible to the limited sum that you were given (calculated sum should be \<= limited sum)

For example:

```
A:
1 2 3
4 5 6
7 8 9

```
* Limited sum: 20
The answer should be: 18
* Limited sum: 17
The answer should be: 17

---‐------------

I thought about taking another matrix, called B, with n rows and the limited sum that I got as the columns number. At the first row of B, to put the value 1 only in the indexes that exists in row 1 in matrix A. At the second row of B, to take every element in the second row of matrix A and add it to every index value in the first row of B that contains 1 in it (if you exceed the limited sum, you're jumping to the next element in row 2 on matrix A). And so on until you get to the final row of B. At the end of the process, you take from the final row of B the largest index that contains the value 1, and this is the answer.

I thought about this solution, but I'm pretty much sure that it's not the most efficient that i can get.

If someone has another direction, clue or suggestion, I'll really appreciate it!

# Answer
Your algorithm is pseudo-polynomial, since it is polynomial in the parameter $\operatorname{max\\\_sum}$ that is inputted using $\log(\operatorname{max\\\_sum})$ bits. However we will show that your problem is NP-complete, therefore your algorithm, although in practice exponential, is a reasonable choice.

Let's define the Subset Sum Problem (SSP):

given $a\_1, \dots a\_n \in \mathbb{Z}$ decide whether exists $S\subseteq \\{1,\dots n\\}$ such that $\sum\_{i \in S} a\_i = 0$.

SSP is NP-complete, thus it is sufficient to reduce an instance of SSP to your problem to get the hardness result.

As an intermediate step let's reduce SSP to a particular case of SSP, having only one negative value. To do so split $\\{1, \dots n\\}$ into $P = \\{i \in \\{1, \dots n\\} \\, | \\, a\_i \geq 0 \\}$ and $N = \\{1, \dots n\\} \setminus P$ and define another instance of SSP of size $n+1$ as follows:

\begin{equation\*} b\_i = \begin{cases} a\_i & \text{if }\\, i \in P\\ -a\_i & \text{if } \\, i \in N \\ \sum\_{j \in N}a\_j & \text{if } \\, i = n + 1 \end{cases} \end{equation\*} Here $b\_{n+1}$ is the only negative value. Now define a bijection (computable in polynomial time) between feasible solutions of the two problems:

$$ S \subseteq \\{1, \dots n\\} \mapsto S^\prime = (P \cap S) \cup (N \cap S^c) \cup \\{n + 1\\}$$

Then it holds

$$ \sum\_{i \in S} a\_i = \sum\_{i \in S^\prime} b\_i$$

and solving the new instance we solve the original one as well in polynomial time.

To conclude it suffices to notice that the solution of the new instance of SSP is entailed by the solution of your problem for $k = 1$ setting $\operatorname{max\\\_sum} = b\_{n+1}$, in fact it admits a soliuton if and only if the closest sum is exactly $\operatorname{max\\\_sum}$ .
> 1 votes

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


title: How can I apply Rice's theorem?

text:
# Question
Title: How can I apply Rice's theorem?
I am learning for my computability and complexity exam in which there is always an exercise to decide whether some problem is decidable or not.

In one of the past exams, there was the following problem:

*Given Turing Machine M, decide whether there exists a prime number on which M halts.*

I am supposed to decide whether the problem is decidable or not.

I guess I can rewrite the problem into the language $L = \\{ \langle M \rangle | \exists p \in \mathbb{P} : M(p) \downarrow \\}$. I have been given a hint that I can use Rice's theorem to prove the language is undecidable. I am actually struggeling, since I have no idea how should I apply Rice's theorem to (generaly any) problem.

I am interested in these questions:

1. How can I find out whether Rice's theorem is applicable or not?
2. If I find it out, how to apply it? (In this excercise in particular)

Any help appreciated.

# Answer
> 1 votes
Here's another, elementary proof technique that does not use Rice's theorem which is way overkill for this simple problem.

We have Turing machine family $F(A)$ that goes into an infinite loop for any input except 2, in which case it will run program $A$, which can be arbitrary.

Now if we could decide your original problem we could decide for arbitrary inputless Turing machines whether they halt using $F$. But this is obviously undecidable and therefore your original problem is as well.

---
Tags: undecidability, rice-theorem
---


title: Is this grammar LL(1) grammar?

text:
# Question
Title: Is this grammar LL(1) grammar?
Is this grammar LL(1)? Would it be a problem that S can be both E/S and E?

```
S -> E / S
S -> E
E -> letter
E -> ‘ S ’

```

Can it derive ‘a / e / ‘g / s’ ’ / q like this?

```
S - >  E / S
S - > ‘S’ / S
S - > ‘E / S’ / S
S - > ‘a / S’/ S
S - > ‘a / E / S’ / S
S - > ‘a / E / ‘E / S’’ / S
S - > ‘a / e / ‘g / s’’ / q

```

# Answer
Plugging it into my LL(1) computer, loner gives false:

```
<S> ::= <E> | <S>;
<S> ::= <E>;
<E> ::= 'letter';
<E> ::= '"' <S> '"';

```

(Note there are some duplicate rules here, which become apparent in the formatted version.)

Proving it (e.g., via the set properties or a pumping lemma) is left an exercise.

---

If `/` is intended to a be terminal (and not alternation!), then we have

```
<S> ::= <E> '/' <S>;
<S> ::= <E>;
<E> ::= 'letter';
<E> ::= '"' <S> '"';

```

is still not LL(1).

---

The derivation would be more readable (and more obviously correct) if shown like (e.g.)

```
S ->  E / S
(with E -> 'S')
-> 'S' / S
(with S -> E / S)
-> 'E / S' / S
(with E -> letter)
-> 'a / S'/ S
(with S -> E / S)
-> 'a / E / S' / S
(with S -> E -> 'S' -> 'E / S') ; note the application of several steps, here
-> 'a / E / 'E / S'' / S
(with S -> E -> letter) ; and again. better to be explicit
-> 'a / e / 'g / s'' / q

```
> 1 votes

---
Tags: formal-grammars
---


# Question
Title: Find vertices of a convex polytope, defined by intersecting half-spaces
I am looking for a algorithm that returns the vertices of a polytope if provided with the set of intersecting half-spaces that define it.

In my special case the polytope is constructed by the following constraints on $x \in \mathbb{R}^d$:

* $\sum\_i x\_i = 1$ (i.e., $\\|x\\|\_1 = 1$).
* $0 \le a\_i \leq x\_i\leq b\_i \leq1$, where the $a\_i,b\_i$ are given

This can either be thought of as the intersection of the hyper-plane (defined by the first constraint, in combination with the range restriction of the second constraint) with a hyper-cube (defined by the second constraint) or as the intersection of half-spaces where the first constraint is the intersection of two half-spaces that only intersect on a hyper-plane.

This always generates a convex polytope, if I am not mistaken, as long as the intersection creates a bounded set.

I would like to have an algorithm that returns the set vertices of the polytope if provided with the set of $a\_i$'s and $b\_i$'s.

There is a special case where there exists no $x$ that satifies this condition. Ideally, this would be picked up on. Therefore, I would wish for an algorithm that checks if such a polytope exists and if so returns the vertices.

# Answer
Your problem is a special case of enumerating the vertices of a convex polytope, and there is an efficient (polynomial-delay) recursive algorithm for your special case, which I will describe next.

If $a\_1+\dots+a\_d \> 1$, then there is no solution, and you can terminate. If $a\_1+\dots+a\_d=1$, there is a single solution $(a\_1,\dots,a\_d)$, so output it and terminate. Otherwise, I'll assume $a\_1+\dots+a\_d \< 1$, so you use the following:

* For each index $i$ such that $a\_i\<b\_i$:
    + Let $c\_i = 1-a\_1-\dots-a\_{i-1}-a\_{i+1}-\dots-a\_d$.
    + If $c\_i \le b\_i$, output $(a\_1,\dots,a\_{i-1},c\_i,a\_{i+1},\dots,a\_d)$; it is a vertex of the original polytope.
    + Otherwise, replace $a\_i \le x\_i \le b\_i$ with $b\_i \le x\_i \le b\_i$ (i.e., replace $a\_i$ with $b\_i$) and recurse to output the vertices of the resulting polytope.

---

To help others find this by search: it's the intersection of the unit simplex (points of L1 norm exactly one) and an axis-aligned box.

---

In general, if the polytope is defined by an intersection $m$ half-spaces, then a vertex is defined by choosing a combination of $d$ out of the $n$ of the corresponding hyper-planes; if their intersection is a single point, and it is in the polytope, then it is a vertex. This gives an exponential-time algorithm for enumerating all vertices for a general polytope. There are other algorithms for the general case, but that's beyond the scope of this answer.
> 4 votes

# Answer
In the following I will call $C:=\\{x:\forall i.a\_i\le x\_i\le b\_i\\}$ the cuboid and $H:=\\{x:\sum\_i x\_i=1\\}$ the hyperplane. I claim that all defining vertices of the polytope $C\cap H$ lie on the intersection of the $1$-dimensional skeleton $S:=\\{x:\exists j.\forall i\neq j.x\_i\in\\{a\_i,b\_i\\}\\}$ with $H$, which can be evaluated by $\mathcal{O}(2^{d-1})$ operations (not very good, but still something, I guess).

A point $x$ is defining vertex of the polytope $P$ if and only if there is no non-zero $y$ and $\epsilon\>0$ with $(x-\epsilon y,x+\epsilon y)\subseteq P$ (i.e. there is no axis along which $x$ can be moved in a small neighbourhood without leaving $P$).

Assume $x\in P$ doesn't lie in $S$, then w.l.o.g. $a\_0\<x\_0\<b\_0$ and $a\_1\<x\_1\<b\_1$. So $e\_1-e\_0$ is an axis along which we can move $x$ without leaving $P$ and $x$ is no defining vertex of $P$.

On the other hand, assume $x\in P$ lies in $S$. If $a\_j\<x\_j\<b\_j$ then $e\_j$ is the only axis along which we can move without leaving $S$, but moving along $e\_j$ immedeately places us out of $H$, so $x$ is a defining vertex of $P$. If all $x\_i$ lie in $\\{a\_i,b\_i\\}$ then $x$ is even defining vertex of $C$ hence defining vertex of $P$ as well.
> 2 votes

# Answer
The polymake tool/library can do exactly what you asked for, if you are interested in a practical solution. See here for a brief tutorial.
> 2 votes

---
Tags: algorithms, computational-geometry
---


# Question
Title: Algorithm to generate inputs with certain properties, but not accepted by a given regular language
## General

Given a regular language $L \subset \Sigma^\star$, I wish to generate *at least one* string **not** in $L$. (Obviously, this requires that there exists such a string; i.e., that $L \neq \Sigma^\star$. I would be interested in ways to decide this, if any exist.)

(Harder) I wish also to generate *at least one* string **not** in $L$, but such that the property $P$ holds. (Again, this requires $\exists w \not\in L : P(w)$ and $\exists w \in \Sigma^\star : P(w)$, but of course one must know $\Sigma,L,P$ to prove any of these.)

A somewhat naïve approach, when we can reliably generate $w : P(w)$, is to do so until $w \not\in L$. For the specific case below, this is not terribly difficult once we can generate strings from a context-free grammar. Is there better?

## Specific

After thinking about Balanced braces, my stack-based implementation, and my slight rant about students knowing regular expressions are not sufficient for this problem, I would love to be able to do the following:

Given a regular expression1 that *supposedly* solves the balanced parentheses problem2, I would like to generate a string in the (context-free) language of balanced parentheses that is rejected by the regular expression.

This would be a nice way to highlight, based on intuition, that some languages are more bigger than others. It would also prove that the given RE is not equivalent to the desired language, though of course it does not constitute a proof that *no* RE is equivalent.

So, to recap:

* $L$ is an attempt to recognize all strings in the language of balanced parentheses (doomed to fail);
* $\Sigma = \\{(, )\\}$;
* $P$ is the property that the given string is in the language of balanced parentheses

---

1. We can stick with the "proper" definition: concatenation, alternation, and Kleene-star repetition)
2. Again, stick with just `(` and `)` for simplicity

# Answer
> 1 votes
For your specific question, you are asking to generate a string in $\bar{L} \cap P$. Note that since $L$ is regular, so is $\bar{L}$; and note that $P$ is context-free. It is known that the intersection of a regular and context-free language is context-free. So, you're asking: given a context-free language, how do we generate a word in that language? This is straightforward.

Concretely: you could represent $L$ as a DFA, then take the complement to get a DFA for $\bar{L}$. You could represent $P$ as a context-free grammar. Then, using a product construction, you can obtain a context-free grammar for $\bar{L} \cap P$, remove all non-productive nonterminals, and then generate a random derivation in the grammar (or, if you want to get fancier, you can search for the shortest word in the grammar using a simple algorithm).

The product construction works by replacing each nonterminal $T$ from $P$ with nonterminals of the form ${}\_sT\_t$, with the intended meaning that $L({}\_sT\_t)$ is the set of all words $w \in L(T)$ such that if you start the DFA in state $s$ and then feed in $w$, it ends in state $t$. You can figure out how to modify all the rules of the grammar, e.g., $T \to UV$ becomes the collection of rules ${}\_sT\_u \to {}\_sU\_t {}\_tV\_u$ for all states $s,t,u$.

You can find the shortest word in a context-free grammar by a simple iterative algorithm. For each grammar symbol $T$, let $\ell(T)$ denote the length of the shortest word generated by $T$, i.e., the shortest word in $L(T)$; we assume $\ell(a)=1$ for all terminals. As a notational convenience, if $\alpha=\alpha\_1\cdots \alpha\_k$ is a string of terminals and non-terminals, set $\ell(\alpha)=\ell(\alpha\_1)+\dots+\ell(\alpha\_k)$. Initially, set $\ell(T) := \infty$ for all nonterminals $T$ and treat all rules as unmarked. Then, repeat the following. Pick an unmarked rule $A \to \alpha$ where $\ell(\alpha)\<\infty$, set $\ell(A) := \min(\ell(A), \ell(\alpha))$, and mark that rule. Repeat until convergence. After this is finished, $L(S)$ tells you the length of the shortest word output by the grammar, if $S$ is the start symbol of the grammar. You can augment the algorithm to keep track of the word itself as well as its length, and then you'll be able to output the shortest word in the grammar.

This might be handy for your application, because it gives you the shortest counterexample: the shortest string that has balanced parentheses but isn't accepted by your regexp.

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


# Question
Title: 4-digit 5's complement of a negative number
Let $n = -13, \ k = -24$

How do I find the 4-digit 5's complement of each number? What would be the result of $n + k$ in complement representation?

I understand how to calculate $n$-digit, 2's complement. I convert it to base 2, invert and add one.

Also, with positive numbers, let's say $n = 13, \ k = 24$, the 4-digit 5's complement would be $(5542)\_{10}$ and $(5531)\_{10}$. Correct? What would their addition be?

# Answer
> 1 votes
Let me demystify $b$'s complement.

Let $b \geq 2$ be an integer. Given a $d$-digit integer $x$ is base $b$, we want to find a $d$-digit integer $y$ such that $y \equiv -x \pmod{b^d}$. Why is this useful? Suppose that $z$ is also a $d$-digit integer, and assume that $z-x \geq 0$. Then $z-x \equiv z+y \pmod{b^d}$, and so if we add $z$ and $y$ and ignore the carry, we will get $z-x$ to achieve subtraction.

How do we find $y$, the $b$'s complement of $x$? We take $y =k\times b^d-x= b^d-x = (b^d-1-x)+1$ (with $k\in \mathbb{Z}$, let $k = 1$). Now the representation of $b^d-1$ in base $b$ consists of $d$ digits of $b-1$, so $b^d-1-x$ is obtained by inverting all the digits of $x$ (subtracting them from $b-1$). This is *$b$'s complement*: the $b$'s complement $y$ of $x$ is obtained by inverting all digits and adding 1.

# Answer
> 0 votes
$n$'s complement of $x$ in the base of $n$ means finding $x'$ such that $x+x'=0$.

@Yuval Filmus has given clear explanation on the general method of finding $b$'s complement; while in your case, **it is easy to find mistakes that there shouldn't be any $5$ in the digit**: $$|n|=13\_{10}=0023\_5\\\|k|=24\_{10}=0044\_5$$ Subtracting each digit of $n,k$ from $(b-1=4)$ and adding $1$, we get: $$-n=4422\_5\\\-k=4401\_5$$ Quick check: $-(n+k)=4422\_5+4401\_5=4323\_5\Rightarrow n+k=0122\_5=37$

---
Tags: base-conversion, numeral-representations
---


# Question
Title: Given a network flow find if there's a min cut that only one of the given edges lay on it
Given a network flow $G=(V,E)$ with capacity function $C$ source $s$ and hole $t$, and given 2 edges $e\_1 , e\_2 $.

Find if there exists a min-cut such that only one of the edges belongs to the min-cut.

Hope to get help.

# Answer
First, compute the minimum cut value $c$ of the network.

Second, remove edge $e\_1$ and increase the capacity of $e\_2$ to infinity, then compute the minimum cut value $c\_1$ of the new network.

Third, remove edge $e\_2$ and increase the capacity of $e\_1$ to infinity, then compute the minimum cut value $c\_2$ of the new network.

Now you can check if $c-c\_1\ge c(e\_1)$ or $c-c\_2\ge c(e\_2)$ to see if there exists a min-cut in the initial network that contains exactly one of $e\_1,e\_2$.
> 3 votes

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


title: if there is no reduction from A to B

text:
# Question
Title: if there is no reduction from A to B
I'm facing the following question :

> If there is no $\leq\_$ reduction,
>
> does this necessarily mean that A is not decidable?

for any choice of B.

thanks in advance.

# Answer
The language $A$ is not necessarily undecidable if we allow any arbitrary but fixed choice of $B$. For example set $B$ to be the empty language. The only language reducible to $B$ is $B$ it self.

On the other hand, if you mean there is exists a language $B$ such that $A \leq\_m B$, then for each language $A$ no matter if it is decidable or not there is such a $B$, namely choose $B$ to be the language $A$ it self.

Note that the only meaningful way to read the statement, is to fix $B$ to a language that is complete for the class of decidable languages. Clearly, decidable languages are closed under$\leq\_m$ reductions, however, I don't think a complete language for this class is known (or whether such a language can be constructed). However, for such a language $B$, a language $A$ is decidable if and only if $A\leq\_m B$ per definition of complete languages.
> 0 votes

---
Tags: computability, reductions
---


title: Is Google search personalized?

text:
# Question
Title: Is Google search personalized?
Pardon me if this is a very naive question.

Suppose I search for something on Google and my next-door neighbour searches for the same thing (on Google) at the same time. Do we get the same or different results?

# Answer
I asked Google about that, and the second result was: Google personalizes search results even when you’re logged out, new study claims

From there:

> Google says it still personalizes for location and “immediate context from a prior search.”

I don't know exactly how Google personalizes searches (are there any other parameters?), but I'd say it is likely you'd get the same results (because you are both approximately at the same location), while it is also possible that they differ.
> 1 votes

---
Tags: search
---


# Question
Title: Is "imperative computing" just a fancy way of saying "scripting"? Or is there more to it?
Maybe this is a very ignorant question. I don't understand imperative computing very well, would it be correct to think of it as simply scripting (as in, running one or a few commands at a time, typically run through a shell language, as opposed to writing a fully fledged program)?

# Answer
> 3 votes
Your understanding is not correct. There are two major programming paradigms: *imperative programming* and *declarative programming*.

In imperative programming you basically tell your computer *what to do* to solve a certain problem by providing an algorithm which might be implemented as a composition of different functions and/or methods. Often one distinguishes between object-oriented and procedural programming as the two main subparadigms of imperative programming, where the latter one is often scripting but the lines between scripting and "software engineering" (i.e. writing fully fledged programs) is blurry. Procedural programming can be engineerish, too.

In declarative programming you do not tell your computer how to solve the problem but rather *what is the problem*. Again, one might distinguish between subparadigms where one might be more frequent for hacky scripts where others are more profound.

You might want to check out C, Java, and Haskell (for instance) as procedural, object-oriented (i.e. the two mainly imperative languages) and a functional (i.e. a declarative language) language. Maybe implement functions to sort a list of integers in each of them, the differences between the latter as opposed to the first two should become very clear, but also the corresponding Wikipedia pages should provide good insights. However, e.g. in C++ (object-oriented) there are some features whose origins are in functional (declarative programming), e.g. lambda functions. On the other hand Haskell also has some sort of loops which are strictly speaking a rather imperative concept, so programming language designers adapt concepts from other languages from another paradigm, the line is blurred and not as clear as 30 years ago.

---

The difference between *scripting* and *software engineering* is even less clear. I would say it depends on the size of the program, reliability, use cases, how well it is documented, ... whether a certain program is a script or "fully fledged".

---
Tags: imperative-programming
---


# Question
Title: Can a computable program have an infinite output?
Can a computable program produce an infinite output from its (presumably finite) input?

\*I wouldn't think so for similar argument as to why it can't compute over an infinite input.

A follow on (basically the same?) question: Are there non-halting programs that are computable?

Thanks!

# Answer
Our general rule is one question per post. I'll answer the first question.

A program can certainly produce infinite output. It can enter an infinite loop producing output. Consider everyone's first program in Basic:

```
10 PRINT "Hello World!"
20 GOTO 10

```

It makes no sense to talk about a program being computable. There's no need to you write a program to output a program. Instead, you can just write the program you want in the first place. Instead of talking about computable programs, computability is about languages. We talk about languages being computable. Check the definition of computability.
> 2 votes

---
Tags: computability
---


# Question
Title: How many different languages over the unary alphabet {a} are recognized by 2-state DFAs?
I am struggling to answer the following question:

> How many different languages over the unary alphabet {a} are recognized by 2-state DFAs?

According to the textbook, the hint was to first calculate the number of 2-state DFAs over that alphabet and then see if any of those DFAs accept the same language.

I am able to calculate the number of 2-state DFAs over that alphabet (Because a DFA is defined as a quintuple $(Q, \Sigma, \delta, q\_0, F)$, there are:

1. $Q$: 1 possibility (The number of states is already defined in the problem)
2. $\Sigma$: 1 possibility (The alphabet is already defined in the problem)
3. $\delta$: 4 possibilities (2 possible input states * 1 possible input character * 2 possible output states) = 4 possibilities)
4. $q\_0$: 2 possibilities (The start state can be one of the 2 states)
5. $F$: 4 possibilities ($\emptyset$, $\\{q\_0\\}$, $\\{q\_1\\}$, $\\{q\_0, q\_1\\}$)

Total possibilities = 4 * 2 * 4 = **32**. However, I am having trouble figuring out how many of the 32 DFA's accept the same language. The textbook says that there are 12 different DFAs that need to be considered due to symmetry, yielding 6 different languages—but I do not understand how the author got to that result.

# Answer
> 2 votes
There are many ways to perform this enumeration. Note first that you can count the number of cases in half by postulating that $Q = \\{q\_0,q\_1\\}$, that is, fixing which among the two states is initial; the choice doesn't matter due to symmetry. Now you are left with 16 possibilities. At this point there are many ways to cut the search space even further. Here is one of them.

Case 1: $\delta(q\_0,a) = q\_0$. In this case we don't care about $\delta(q\_1,a)$, since $q\_1$ is unreachable. This case gives the two languages $\emptyset$ and $a^\*$, depending on whether $q\_0$ is a final state or not.

Case 2: $\delta(q\_0,a) = q\_1$. Since $F = \emptyset$ and $F = \\{q\_0,q\_1\\}$ will give the languages $\emptyset$ and $a^\*$, respectively, it suffices to consider $F = \\{q\_0\\}$ and $F = \\{q\_1\\}$. Together, there are 4 machines to consider:

* $\delta(q\_1,a) = q\_1$, $F = \\{q\_0\\}$: the language is $\epsilon$.
* $\delta(q\_1,a) = q\_1$, $F = \\{q\_1\\}$: the language is $a^+$.
* $\delta(q\_1,a) = q\_0$, $F = \\{q\_0\\}$: the language is $(aa)^\*$.
* $\delta(q\_1,a) = q\_0$, $F = \\{q\_1\\}$: the language is $a(aa)^\*$.

These are the six different languages produced by unary two-state DFAs.

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


# Question
Title: Show that UPrime = {1^n : n ∈ N is prime} is in P
I have this question to solve. According to my understanding, it basically requires a turing machine that outputs lines on the tape, with the number of the lines being any prime number.

My idea is to take the AKS test's conclusion and making a case that since, calculating primes is a problem that can be solved in polynomial time complexity as already proven by AKS, hence this problem is also in P.

Is this the right way? what would be a more formal/mathematical way of expressing this if it is?

# Answer
You can use the following algorithm:

* Input: number $n$ encoded in unary
* For $k$ from $2$ to $n-1$, check whether $k \mid n$, and if so, output "Not prime".
* Output "Prime".

This algorithm runs in time polynomial in $n$.

The AKS test, in contrast, runs in time polynomial in $\log n$, assuming that the input $n$ is encoded in binary. If the input is encoded in unary, the running time (at least on a multitape Turing machine) will be $O(n)$.
> 4 votes

# Answer
Hint: Notice that your input is unary.
> 4 votes

---
Tags: algorithms, complexity-theory
---


title: Towers of Hanoi First Move

text:
# Question
Title: Towers of Hanoi First Move
I've finally more or less understood the recursive algorithm for solving the Towers of Hanoi. My Python code is below.

However one thing still bugs me - I can't yet work out how this simple seeming algorithm can "know" which move to make first - whether to the destination peg or the spare peg.

I can see it depends on whether there is an odd or even number of discs, and I understand how the algorithm works, thanks to this great article: https://www.geeksforgeeks.org/c-program-for-tower-of-hanoi/

It's just that first move that remains a mystery to me. Any clarification musch appreciated.

```
def hanoi(n, from_peg, to_peg, spare_peg):
    if n == 1:
        print("Moving disc from " + from_peg + " to " + to_peg)
        return
    hanoi(n-1, from_peg, spare_peg, to_peg)
    print("Moving disc from " + from_peg + " to " + to_peg)
    hanoi(n-1, spare_peg, to_peg, from_peg),

print (hanoi(4, 'A', 'C', 'B'))

```

# Answer
> 2 votes
If you trace the recursion calls that your algorithm makes before it prints its first line, you will have if the first call is `hanoi(n, 'A', 'B', 'C')` :

```
hanoi(n, 'A', 'B', 'C')
hanoi(n-1, 'A', 'C', 'B')
hanoi(n-2, 'A', 'B', 'C')
...
hanoi(1, 'A', $ , €)
Moving disc from A to $

```

To see if $ is equal to B or C, you just have to remark that the value of `to_peg` and `spare_peg` alternate each time so the disk to move only depends on the parity of n. In our example :

If n is odd then \\$ = B and otherwise, \\$ = C

# Answer
> 1 votes
The first move is produced by the first recursive call in the code, which is repeatedly invoked many times, until the base case is reached -- printing the first move.

We note that `hanoi(n, from_peg, to_peg, spare_peg)` makes as its first recursive call `hanoi(n-1, from_peg, spare_peg, to_peg)`, so this swaps the last two arguments, and decreases `n`.

Hence, the last two arguments will be swapped `n-1` times, until we reach `n=1` triggering the base case.

Concluding, performing `n-1` swaps, leaves those arguments where they are if `n` is odd, or swaps them (once), if `n` is even.

# Answer
> 1 votes
The broad idea behind solving Tower of Hanoi problem by recursion is this:

The whole stack of n disks needs to be transferred to the **to** pole from **from** pole. Imagine there are n disks (instead of 3 shown) on the **from** pole. The idea behind recursive solution is to consider the top $n-1$ disks as a single combined disk, transfer this combined disk to **using** pole, place the $nth$ disk on the **to** pole, and then place the *combined* disk on the top of the $nth$ disk on the **to** pole. Now, how do I move that *combined* disk to the **using** pole ? Apply the above procedure to the top $n-1$ disks forgetting about the bottom $nth$ disk, and that's what recursion is.

So, in order to find out the first move, we keep reducing the size of our *aggregated disk* until we reach the top 2 disks, or just simply call your code with n=2.

`def hanoi(2, from_peg, to_peg, spare_peg):`

Now this line below

`hanoi(1, from_peg, spare_peg, to_peg)`

moves $1st$ disk from **from** pole to **aux** peg. Following which

`print("Moving disc from " + from_peg + " to " + to_peg)`

moves $2nd$ disk from **from** pole to **to** pole. And finally,

`hanoi(1, spare_peg, to_peg, from_peg),`

places $1st$ disk from **aux** back to **to** pole on top of $2nd$ disk.

# Answer
> 0 votes
You shall make an research with the state table and graph theory. Than You shall find the shortest path in graph. It usually is for games (and It's for chess too and complex games).

---
Tags: algorithms, recursion, towers-of-hanoi
---


# Question
Title: Streaming digit-to-digit conversion from decimal to hexadecimal
I am looking for a streaming algorithm for converting a decimal number to a hexadecimal number. I am assuming the input is a string represention of a decimal number (i.e., each character is a decimal digit) in digit-reversed order, and I'd like the output to be a string represention of a hexadecimal number (i.e., each character is a hex digit) in digit-reversed order.

By streaming, I mean that I'd like the algorithm to start producing hexadecimal digits without having to look at the entire decimal-string input first (i.e. up to some fixed number of digits of input can be looked at before producing digits of output); and ideally with only a constant amount of memory.

Is there a way to do this?

I know one can convert from hexadecimal to binary in a streaming way. For single-digit numbers, we can use the following table:

```
hex -> bin
0 -> 0000
1 -> 0001
2 -> 0010
3 -> 0011
4 -> 0100
5 -> 0101
6 -> 0110
7 -> 0111
8 -> 1000
9 -> 1001
a -> 1010
b -> 1011
c -> 1100
d -> 1101
e -> 1110
f -> 1111

```

For multiple-digit numbers, we can do the same by applying the mapping above to each hexadecimal digit individually.

```
1234 -> 1, 2, 3, 4 -> 0001, 0010, 0011, 0100 -> 0001001000110100

```

Is there a way to do something like this, converting from decimal to hexadecimal?

# Answer
> 4 votes
I don't think this is possible. Changing a high-order digit in a base-10 number -- say, changing 5000000 to 6000000 -- can change bits in its binary equivalent all the way from high-order bits to fairly-low-order bits:

* 10**0**1**10001**001**01**1**01**000000
* 10**1**1**01110**001**10**1**10**000000

It doesn't change the very lowest bits: Since $10 = 5\times 2$, the digit in position $k$ in a decimal number is a multiple of $10^{k-1} = (5\times 2)^{k-1} = 5^{k-1}2^{k-1}$, so changing it will never change the lowest $k-1$ bits of the binary representation. But it can change the $k$-th bit, and bits in positions up to $\log\_2(9\times 10^{k-1}) = (\log\_2 10)(k-1) + \log\_2 9 \approx 3.322(k-1) + 3.170$. This is true for any $k$, so the range of affected digits grows indefinitely as $k$ increases.

If you were, say, trying to convert between base 4 and base 8, you could group each block of 3 base-4 digits into a base-64 "superdigit", which you could then convert back down to 2 base-8 digits since 8^2 = 64.

But there is no "right" superdigit base for the bases 10 and 2, since 10 contains 5 as a factor and 2 does not: every positive integer power of 10 contains 5 as a prime factor, and no positive integer power of 2 does, so by the uniqueness of prime factorisations there is no integer that is a power of both 2 and 10.

# Answer
> 2 votes
You can't do this - if you don't know whether the input is k digits or k+1 digits, then the additional decimal digit changes all or most of the hexadecimal digits. For example 100 -\> 64, but 1000 -\> 3e8.

Also, consider the numbers $16^k-1$ and $16^k$. In hexadecimal, one is k f's, the other is 1 followed by k zeroes. Since $16^k$ in decimal doesn't end in zero, all their decimal digits except the last one are equal. So *all* the decimal input digits must be processed before we can output the first hexadecimal digit.

---
Tags: substrings, string-matching, base-conversion, numeral-representations
---


# Question
Title: What's the decoding time complexity of LT codes?
LT codes are practical fountain codes that are near-optimal erasure correcting codes.

Simply stated, for encoding a $n$-block message, each packet first chooses a *degree* $d\in\\{1,\ldots,n\\}$ according to a specific distribution, and then $d$ random blocks are xor-ed to create the packet's message.

The analysis shows that $O(n)$ **packets** that make to the receiver are enough for decoding, by allowing finding degree-one packets and xoring its content from all other packets that contain the same block (decreasing their degree by one).

What I haven't found in Luby's paper, or anywhere else, is the **runtime** complexity of the decoding. That is, what's the overall time spend on computing the original message.

A simple argument shows that $O(n^2)$ **time** is enough. Can we do better?

# Answer
> 1 votes
The approach you describe can be implemented to run in linear time.

Build a bipartite graph where left-vertices are blocks and right-vertices are packets, and with an edge from block $b$ to packet $p$ if $b$ is one of the blocks xor-ed to create $p$'s message. Store the bipartite graph in adjacency list format. Also keep track of the degree of each packet, so given a packet $p$ you can compute its degree in $O(1)$ time.

Then it's easy to implement the algorithm you describe in $O(n)$ time, using a worklist algorithm. The worklist is a list of all packets of degree one. In each iteration, you remove a degree-one packet $p$ from the worklist, then process it as follows. Find the corresponding block $b$, then find all other packets $p'$ containing the block. Xor $b$ into $p'$, and delete the edge $(b,p')$ (and update the degree of $p'$). This can be done in $O(1)$ time. If the new degree of $p'$ is 1, add $p'$ to the worklist. Repeat until the worklist is empty.

The running time is $O(1)$ per edge in the bipartite graph, i.e., $O(m)$ time where $m$ counts the number of edges in the graph (the sum of degrees of all of the packets).

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


# Question
Title: how is the set of undecidable programs related to the set of non-halting programs?
Is there a non-halting program for every undecidable program? is undecidable the "same thing" as non-halting?

Thanks!

# Answer
> 2 votes
The notion of an "undecidable program" doesn't make sense, for the same reasons I gave in response to your last question. It makes sense to talk about whether a language is decidable or undecidable. It doesn't make sense to talk about whether a program is decidable or undecidable. If you check the formal definition of decidable, you'll see that decidability is only defined for languages.

Undecidable is not the same as non-halting. Check the definition.

---
Tags: undecidability, halting-problem
---


# Question
Title: Time complexity of algorithm inversely proportional to size of sub problem?
Let's say I have an algorithm with time complexity $T\_n = T\_\frac{n-1}2 + 1$, $T\_0 = 0, T\_1 = 1$.

Assume (Induction hypothesis) $T\_n = C\log\_2(n+1)$ for some $C$. $T\_1$ imposes $C \geq 1$.

Therefore from I.H. (plugging in the formula at $\frac{n-1}2$):

$$T\_n = C\log\_2(\frac{n-1}{2}+1) + 1$$ $$T\_n = C\log\_2(\frac{n+1}{2}) + 1$$ $$T\_n = C\log\_2(n+1) - C + 1$$ Setting $C = 1$ gives

$$T\_n = C\log\_2(n+1)$$

And so by induction

$$T\_n = \log\_2(n+1)$$

This result makes very little sense to me. How come reducing the size of the subproblem from $n/2$ to $(n-1)/2$ increases the time it takes? (From Master's theorem, $T\_n = T\_{n/2} + 1 \Rightarrow T\_n = \log\_2(n)$. Similarly, increasing to $(n+1)/2$ gives $T\_n = \log\_2(n-1)$. What am I failing to see here?

# Answer
> 1 votes
I am afraid that you fell prey to ambiguous notations.

To clarify, the subscript $\frac{n-1}2$ in the recurrence relation, $T\_n = T\_\frac{n-1}2 + 1$ must mean the integer division of $n-1$ by 2 as used in most programming languages, i.e., $\frac 22=1$ and $\frac32=1$. The following equality does NOT hold,

$$\log\_2(\frac{n+1}{2}) = \log\_2(n+1) - 1,$$ where the division on the left hand side is the integer division. For example, you can check the case when $n=2$. In the light of that clarification, $T\_n = C\log\_2(n+1)$ with any constant $C$ cannot be a solution to that recurrence relation.

Now, you might insist that $\frac{n-1}2$ means the usual math division of $n-1$ by 2, i.e., $\frac{3-1}2=1$ and $\frac{4-1}2=1.5$, so that $T\_n = C\log\_2(n+1)$ could be a solution to that recurrence relation. Well, in that case, that recurrence relation, together with the initial conditions $T\_0 = 0$ and $T\_1 = 1$ does not define the value of $T\_2$, since $T\_2=T\_{0.5}+1$, where $T\_{0.5}$ is not defined. That means, it does not make any sense to involve $T\_2$, $T\_4$, etc in any equality, since they are not defined!

By the way, it is wrong that "from Master's theorem, $T\_n = T\_{n/2} + 1 \Rightarrow T\_n = \log\_2(n)$". What Master's theorem tells us is, $T\_n = T\_{n/2} + 1 \Rightarrow T\_n = \Theta(\log\_2(n)).$

---
Tags: time-complexity, master-theorem
---


# Question
Title: Is "promoting a key" a part of deleting internal node key in B+ Tree?
I was trying to learn B+ tree deletion operation and trying to contrast it with B tree deletion operation. However barely any book provided detailed step by step B+ tree deletion operation. So I was referring B+ tree key deletion from here.

The page says deleting 15 from this:

yields this:

Thus this somehow demotes key 13 to its right child and promotes key 11 to its parent. I do not find "promoting" any key specified in the B+ tree deletion algorithm given on the same page.

In step 4 of the B+ tree deletion algorithm on the same page, it says:

> If the node has too few keys to satisfy the invariant, and the next oldest or next youngest sibling is at the minimum for the invariant, then merge the node with its sibling; if the node is a non-leaf, we will need to incorporate the “split key” from the parent into our merging.

If I am not wrong, if we follow this step, it should yield something like this:

So is the example wrong? I am not able to confirm as I am not able to find precise step by step procedure. The steps given on this page sounds a bit fuzzy.

# Answer
> 1 votes
I'd not attach too much importance to such kind of boundary cases: both solutions here are valid according to the definition of B+-Tree and depending on the order of operations, it is very common that B-Trees have different shapes for the same data. Here the difference between the two results is just the one between $\<$ and $\leq$ in some condition and the choice is not imposed by an invariant of the data structure.

It seems to have a drastically different result because the tree is so close to be as sparse as possible and so close to be collapsible -- at most two more deletions will trigger that. The reason is not that trees close to the boundary are typical, it is because making readable pictures is easier in that case, in practice the number of buckets per node is greater than 4 and fewer nodes are just half-full. Being able to steal one element from the neighbor is more typical than having to merge with it.

Obviously if you know something about the patterns of insertion and deletions, you may prefer one version over other, but it will be a second order effect.

# Answer
> 1 votes
I share your perception of the problem. The literature on B trees (and it's variants) are written by people who already understand the problem and as such they easily gloss over some details. This does make it difficult to understand.

The case of the B+ tree delete operation is somewhat absurd because in contrast with the insert operation (which is comparatively straightforward) the delete operation is not and is riddled with edge cases.

1. Leaf with more than minimum required keys, delete.
2. Leaf with less than minimum required keys, underflow!
3. Internal `->` leaf underflow, can borrow from left?
4. Internal `->` leaf underflow, can borrow from right?
5. Internal `->` leaf underflow, merge with left!
6. Internal `->` leaf underflow, merge with right!
7. Internal `->` internal underflow, can borrow from left?
8. Internal `->` internal underflow, can borrow from right?
9. Internal `->` internal underflow, merge with left!
10. Internal `->` internal underflow, merge with right!

Note that we have to treat children of internal nodes differently wether they are internal or leaf nodes. This is why we have two sets of borrow and merge operations to consider.

For each of the borrow and merge operations we also must consider the left or right case. I've decided to favour the left case, and only use the right case when the left case is impossible. This is an implementation detail and completely arbitrary (and I bet it is also a source of additional confusion).

I choose to illustrate how to implement B+ tree delete with the follow JavaScript snippet. However, this is only a high level overview of the actual code, it will not run as is.

```
function remove(node, value) {
  if (isLeaf(node)) {
    return deleteIn(node, value)
  } else {
    // internal node

    const [k, v] = node

    const index = findIndex(k, value)
    const subtree = v.get(index)
    const underflow = remove(subtree, value)

    if (underflow) {
      if (isLeaf(subtree)) {
        // can we borrow?

        if (leafBorrow(node, index, v, -1)) {
          return false
        }

        if (leafBorrow(node, index, v, +1)) {
          return false
        }

        // we must merge!

        if (0 < index) {
          return leafMerge(node, index, subtree, -1)
        } else {
          // we only merge right when we cannot merge left

          return leafMerge(node, index, subtree, +1)
        }
      } else {
        // can we borrow?

        if (internalBorrow(node, index, subtree, -1)) {
          return false
        }

        if (internalBorrow(node, index, subtree, +1)) {
          return false
        }

        // we must merge!

        if (0 < index) {
          return internalMerge(node, index, subtree, -1)
        } else {
          // we only merge right when we cannot merge left

          return internalMerge(node, index, subtree, +1)
        }
      }
    }
  }
}

```

The underflow condition is triggered when the a B tree of order `m` falls below it's minimum required keys `Math.ceil(m / 2) - 1`. I've omitted this from the code above but that's what the code would do to signal underflow.

Leaf node underflow is just `node.size < Math.ceil(m / 2) - 1` while internal node underflow is `node[0].size < Math.ceil(m / 2) - 1`. I use positional notation to select either the internal node keys `node[0]` or children `node[1]`, this is abbreviated in the example as `const [k, v] = node` (deconstructing syntax).

`leafBorrow` and `internalBorrow` return `true` on success. Borrowing only succeeds when there are more than minimum required keys so that the result of borrowing does not itself lead to an underflow condition. That's why we opt out if we succeed in borrowing.

`leafMerge` and `internalMerge` can modify the tree in such a way that the tree keeps underflowing until we hit the root, so they may propagate the underflow condition.

The devil is in the details of `leafBorrow`, `internalBorrow`, `leafMerge` and `internalMerge` but at least by doing this we can break down the delete operation into 4 distinct parts. What I recommend now is studying each of these cases in isolation with an small tree of order `3` and `4` (the smallest possible B+ trees).

The B+ tree visualizer is a great tool but it doesn't properly illustrate what's actually going on in great detail. There's too much movement in one go. However, it will help.

# `leafBorrow`

Given a B+ tree of order `3` like this:

```
{
  "k": [2],
  "v": [[1], [2, 3]]
}

```

To delete `1` we trigger underflow.

```
{
  "k": [2],
  "v": [[], [2, 3]]
}

```

Borrow `2` from right.

```
{
  "k": [2],
  "v": [[2], [3]]
}

```

And update separator. Always left most value (which may or may note be imminently accessible).

```
{
  "k": [3],
  "v": [[2], [3]]
}

```

Note that a helper function that will get the first value (the value to use as separator) from a subtree will come in handy. In this case the value is right there but this isn't the case for `internalBorrow`.

# `internalBorrow`

Given a B+ tree of order `3` like this:

```
{
  "k": [3],
  "v": [
    {
      "k": [2],
      "v": [[1], [2]]
    },
    {
      "k": [4, 5],
      "v": [[3], [4], [5]]
    }
  ]
}

```

To delete `1` we trigger underflow, as per usual.

```
{
  "k": [3],
  "v": [
    {
      "k": [],
      "v": [[2]]
    },
    {
      "k": [4, 5],
      "v": [[3], [4], [5]]
    }
  ]
}

```

Borrow from right by going via the parent. We'll bring over the leftmost right subtree by concatenating the keys `[]` and `[3]`, and the children `[[2]]` and `[[3]]` in that order because we are bringing over a subtree from the right side of the tree.

```
{
  "k": [3],
  "v": [
    {
      "k": [3],
      "v": [[2], [2]]
    },
    {
      "k": [5],
      "v": [[4], [5]]
    }
  ]
}

```

Update separator to `4` (the smallest value found in the right subtree). This is where that helper function to find the smallest value in a subtree is useful.

```
{
  "k": [4],
  "v": [
    {
      "k": [3],
      "v": [[2], [3]]
    },
    {
      "k": [5],
      "v": [[4], [5]]
    }
  ]
}

```

# `leafMerge`

A leaf node must merge with it's left or right sibling when it cannot borrow from it's left or right sibling.

Given a B+ tree of order `3` like this:

```
{
  "k": [2],
  "v": [[1], [2]]
}

```
* To delete `1` we need to merge with the right leaf.
* To delete `2` we need to merge with the left leaf.

When we merge, we also delete one separator key.

```
{
  "k": [],
  "v": [[2]]
}

```

```
{
  "k": [],
  "v": [[1]]
}

```

Given a B+ tree of order `4` like this:

```
{
  "k": [5],
  "v": [
    {
      "k": [3],
      "v": [[2, 3]]
    },
    {
      "k": [11],
      "v": [
        [5, 7],
        [11, 13]
      ]
    }
  ]
}

```

To delete `2` we merge with right.

```
{
  "k": [5],
  "v": [
    {
      "k": [],
      "v": [[3]]
    },
    {
      "k": [11],
      "v": [
        [5, 7],
        [11, 13]
      ]
    }
  ]
}

```

This will trigger an `internalMerge`.

# `internalMerge`

An internal node merge operation happen in response to an underflow condition triggered by `leafMerge`.

Given a B+ tree of order `4` with a present underflow condition like this:

```
{
  "k": [5],
  "v": [
    {
      "k": [],
      "v": [[3]]
    },
    {
      "k": [11],
      "v": [
        [5, 7],
        [11, 13]
      ]
    }
  ]
}

```

To me, this looks like a three-way merge. We'll be concatenating the keys `[]`, `[5]` and `[11]` to construct `[5, 11]` and concatenating the children `[[3]]` and `[[5, 7], [11, 13]]` to construct `[[3], [5, 7], [11, 13]]`. It's worth pointing out that the empty *containers* are only empty because the B+ tree is of order `3` or `4`. They wouldn't empty completely (for a non root node) if `m` was greater than `4`. Don't make the mistake of thinking that they are irrelevant because they are empty (in this **small** example) it will depend on what the required minimum number of keys are, i.e. `Math.ceil(m/2)-1`.

The result should be:

```
{
  "k": [5, 11],
  "v": [[3], [5, 7], [11, 13]]
}

```

---
Tags: data-structures, search-trees, balanced-search-trees
---


# Question
Title: Find number of triples that sum up to zero in query-intervals
My problem is that we have an array of $N$ integers $(N \<=5000)$ on the interval $\[-10^6,10^6\]$. We also have $Q$ queries $(Q \<= 10^5)$ giving us some range in the array.

For each query, we want to find the number of triplets of indices in the range such that the sum of those array values equal to zero. More formally we want to find the number of ways we can choose unordered distinct triples $i, j$ and $k$(within the given query range) such that $a\[i\]+a\[j\]+a\[k\] = 0$.

I'm thinking of doing an $O(N^2)$ pre-computation and $O(\log N)$ time for each query but I am unable to come up with a concrete working idea. Any help would be appreciated.

Edit: queries can be processed offline, as the array does not need to be updated.

# Answer
Let us call the input array $A$. We build the solution in three steps:

First, for each value $v$ between $-10^6$ and $10^6$, build a list with all the indices in $i \in \\{1, \dots N\\}$, where $A\_i = v$ and keep all these lists sorted. One way to achieve this is to iterate over $A$ and append the index of each element to its corresponding list. Let $L\_v$ be the list corresponding to a value $v \in \\{-10^6, \dots 10^6\\}$.

In the second step, we will build a two-dimensional array $C\[N\]\[N\]$, where \begin{equation} C\[i\]\[j\] = \begin{cases} |\\{k: i+j+k = 0, k \in \\{i, \dots j\\}\\}| &;i\leq j,\\ 0 &;\text{Otherwise}. \end{cases} \end{equation} We can compute $C$ by iterating over all pairs $i, j \in \\{1, \dots N\\}$, $j\geq i$, and for each such pair, let $u = A\_i$ and $v = A\_j$. Let $w = -(u + v)$. Note that $u + v + w = 0$, Using binary-search twice, find in $L\_w$ the lowest index not less than $i$ and the highest index not greater than $j$. The difference of the indices of these two values plus 1 is the number of elements $w$ between $A\_i$ and $A\_j$, such that $A\_i + A\_j + w = 0$, which is exactly $C\[i\]\[j\]$.

Now as a last pre-processing step, Let us compute the two-dimensional array $S$, the prefix-sums over $C$, that means: $$ S\[i\]\[j\] = C\[i\]\[j\] - C\[i-1\]\[j\] - C\[i\]\[j-1\] + C\[i-1\]\[j-1\], $$ where we consider $C\[i\]\[j\] = 0$ for $i = 0$ or $j = 0$ (since we considered 1-indexed arrays).

Now for each query $i, j$, output $$S\[j\]\[j\] - S\[i-1\]\[j\] - S\[j\]\[i-1\] + S\[i-1\]\[i-1\],$$ where again, we consider $S\[i\]\[j\] = 0$ for $i = 0$ or $j=0$.

Based on the previous definitions, try to see why this yields the answer you are looking for.

The running time is $O(N^2\log N)$ pre-processing and $O(1)$ per query. The space complexity is $O(N^2 + M)$, where $M$ is the largest value (equal to $10^6$ in your case), which is needed to keep track of the start of each list $L\_i$ for each $i \in \[-M, M\]$.
> 1 votes

---
Tags: algorithms, data-structures, arrays, binary-search
---


title: Max clique in interval graph

text:
# Question
Title: Max clique in interval graph
According to Efficient algorithms for interval graphs and circular arc graphs there is an $O(n \log n)$ algorithm for finding the max clique in an interval graph, assuming you have the interval model. Unfortunately, neither the paper nor the references actually elaborate on what the algorithm is, beyond saying that you can modify the well-known algorithm for optimally coloring interval graphs (where you greedily color the graph in the order generated by sorting the intervals lexicographically) to compute the max clique. This makes sense, as the largest color used in an optimal coloring is the size of the max clique in a perfect graph (and interval graphs are perfect). Unfortunately, beyond that, I am lost as to how to compute the max clique. The obvious approach is to modify some data structure every time the max color increases, but I can't figure out precisely what data structure to use or how to modify it.

Does anyone know a reference for this algorithm or can reinvent a description of it?

# Answer
> 2 votes
Interval graphs are chordal graphs, so you can use a linear time algorithm for finding max clique in a chordal graph. This can be done by first finding a perfect elimination ordering, and then using the fact that every time a vertex is eliminated it forms a clique together with its neighbors that are not eliminated yet. Furthermore all maximal cliques appear in this process.

To find the perfect elimination ordering, maximum cardinality search (MCS) is the simplest algorithm and it works in linear time. (I don't know why Wikipedia mentions lexbfs first, it is much more complicated.)

# Answer
> 0 votes
```
def mex(m):
  for i in [0 ..]:
    if not(m.contains(i)):
      return i

def maxCliqueOfIntervals(intervals):
  maxClique = []
  map = {}
  for interval in intervals.sort():
    // map should only contain intervals that overlap with the current interval
    map.filter(lambda x: overlaps(x, interval));
    // choose the smallest color not in the map to color the current interval
    map.insert(mex(map), interval);
    // the map now comprises a clique, if it is larger than the current max clique,
    // replace the max clique with the current map
    if map.size() > maxClique.size():
      maxClique = map.elems();
  return maxClique;

```

I believe this is a correct implementation based on the interval coloring algorithm that runs in $O(n \log n)$ time.

If you just care about the max clique, then it can be simplified a bit:

```
def maxCliqueOfIntervals(intervals):
  maxClique = []
  active = []
  for interval in intervals.sort():
    active.filter(\x -> overlaps(x, interval));
    active.push(interval);
    if active.size() > maxClique.size():
      maxClique = active;
  return maxClique;

```

---
Tags: graphs, intervals, clique
---


# Question
Title: Thought process to solve tree based Dynamic Programming problems
I am having a very hard time understanding tree based DP problems. I am fairly comfortable with array based DP problems but I cannot come up with the correct thought process for tree based problems and I was hoping somebody could please explain their thought process.

I will talk about my thought process behind array based problems and then explain my troubles with tree based DP problems.

---

**My thought process for array problems**

The way I think about DP in array based problems is as follows. Let us consider a problem like Minimum Path Sum. Here the objective is to get from the top left to bottom right positions in a matrix such that we minimize the cost of the path. We can only move left and right.

The way I would approach problems like this is as follows:

* First I would construct a recurrence. In this case the recurrence is as follows

The recurrence is:

```
f(i, j) = a[i][j] // if i == m and j == n
f(i, j) = a[i][j] + f(i, j+1) // if i == m
f(i, j) = a[i][j] + f(i+1, j) // if j == n
f(i, j) = a[i][j] + Math.min( f(i, j+1), f(i+1, j) ) // Otherwise

```
* Next I look at the equations which tells me the problem can be solved using DP as there are overlapping subproblems in `f(i+1, j) and f(i, j+1)`. There is also an optimal substructure.
* I can also tell the time/space complexity just by looking at the recurrence.

+ Because we must compute all states which is all (i,j) pairs and because time per state is O(1) (adding a\[i\]\[j\] to result) the time complexity is O(n^2).
    + Looking at the recurrence, i depends only on i+1 and not on i+2, i+3 ... similarly j depends only on j+1 and not on j+2, j+3... so we can get away with using only 1 extra row (either i+1 or j+1) instead of the entire matrix so space complexity is O(n).

Hence I would come up with a n^2 time and n space solution. I can do this without any problems.

---

**My thought process for tree problems**

However I am having a hard time applying the same thought process to tree based DP problems. As an example let us consider the problem Diameter of Binary Tree where the objective is to find the longest path between any 2 nodes in the tree.

I can come up with a recurrence for this problem which is as follows:

```
f(n) = 0 // if n == null
f(n) = max( 1+height(n.left) + height(n.right),         // longest path passing through root
            f(n.left),                                  // longest path in left subtree
            f(n.right) )                                // longest path in right subtree

```

Because `f(n.left)` for example is computed by doing `1+height(n.left.left) + height(n.left.right)` I can tell that DP must be used.

So my approach would be to create a cache of size 'n' that stores all the heights of the nodes. So the space complexity would be O(n).

However the optimal solution of this problem has a space complexity of O(1) and I am having a hard time figuring that out just by looking at the recurrence. How does the recurrence tell you that space complexity can be reduced and that O(1) space is enough and O(n) is not needed? How do you know what value(s) to store in this case? In array based problems I can get the answers to both these questions just by looking at the recurrence but for tree based dp it is not so obvious to me.

---

**My questions:**

1. What can you tell about this problem just by looking at the recurrence for the tree problem? Putting aside my own thought process, if I gave you this recurrence and nothing else what conclusions would you reach and how would you write the program? I am curious about your thought process.
2. For array based problems I can tell just by looking at the recurrence both how much space I needed to solve the problem AND what exactly I needed to store (I need to store values of row i+1 in min path sum and nothing else). How can I do the same for the tree problem?

Thanks.

# Answer
## Question 1

The reason why its O(1) space and not O(n) comes down to top down vs bottom up.

Let us first consider the array based problem - min path sum.

If you do it top down you will need O(n^2) space. Remember that when you do top down/memoization, all the state results need to be stored - its essentially just recursion with caching.

However when you do bottom up, you are building up to the solution. Only the state results needed to build up to the next state is required. So in the case of min path sum only states in (i+1, j) is required to build the states in (i, j). We can discard the rest of the states.

This is why when you do bottom up, you can reduce space complexity to O(n).

For the tree problem what you have described is the top-down approach. For the solution you want, you need the bottom-up approach.

---

**Top-down approach for the tree problem**

What you have out there is an pre-order traversal. It can be thought of as the same as top-down DP or memoization. And as we have seen in the above example to use top down DP, all the state results need to be stored in the cache.

Here the states you care about is the heights of the nodes so height of each node needs to be stored bringing the complexity to store states upto O(n).

So think about how the tree problem would be implemented top down - you have all the heights in a cache and you call it each time you need to access the height of a node.

So every time you get to a node, you use the cache to get the heights and then you do some simple arithmetic in constant time to get the diameter. In this case that arithmetic is `height[n.left] + height[n.right]`.

Top down is simply recursion with caching so for the top down variant, you are storing only the heights to get a cache size of O(n). The code is as follows:

```
Map<TreeNode, Integer> dp = new HashMap<>();

public int diameterOfBinaryTree(TreeNode root) {
    if(root == null)
        return 0;
    else
        return Math.max(
            height(root.left, dp)+height(root.right, dp),
            Math.max( diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right) )
        );
}

private int height(TreeNode root, Map<TreeNode, Integer> dp) {
    if(dp.containsKey(root))
        return dp.get(root);

    if(root == null)
        return 0;
    else
        dp.put(root, 1 + Math.max(height(root.left, dp), height(root.right, dp)) );

    return dp.get(root);
}

```

---

**Bottom-up approach for the tree problem**

The bottom up approach to any tree problem uses post-order traversal instead of pre-order traversal. We construct the postorder traversal to compute the states we want to store in the cache - in this case it is the height.

Since we compute the children before computing the current node, for every node we visit, we have the height of the children available to us. Since the heights of nodes are available to us, for a given node we also have the diameter passing through that node available to us while we are processing the node.

So if we want the max diameter, we simply need to compute the diameter of the current node and then compare it with the max diameter seen so far - we do this for all nodes. All this is done within a single post-order traversal of the tree.

The code is as follows:

```
int maxDiameter = 0;

public int diameterOfBinaryTree(TreeNode root) {
    postorderHeight(root);
    return maxDiameter;
}

private int postorderHeight(TreeNode root) {
    if(root == null)
        return 0;
    int leftSubtreeHeight = postorderHeight(root.left);
    int rightSubtreeHeight = postorderHeight(root.right);

    maxDiameter = Math.max(maxDiameter, leftSubtreeHeight + rightSubtreeHeight);

    return 1 + Math.max(leftSubtreeHeight, rightSubtreeHeight);
}

```

Technically the space complexity of this is proportional to recursion stack size however cache size is constant.

---

## Question 2

Ask yourself if the states you need to store can be reduced if you do bottom up (post-order). If yes do that - in this case yes we can obtain heights for free if we use post order.
> 2 votes

# Answer
I don't know if this helps, but I also struggled a great deal with DP problems on trees, and what helped for me was considering some simpler problems first, and really do a bunch of exercises of this type. It also really helps to program them in (e.g.) Python so that you get some hands-on experience.

So, perhaps it is better to start with a simpler tree problem first, like (weighted) Vertex Cover or (weighted) Independent Set?

In both these cases (they are similar, but let us focus on Vertex Cover), the entire solution of a subtree can be summarized in the root of the subtree with two numbers: the optimal solution if the root of the subtree is *in* the vertex cover, and the optimal solution if the root of the subtree is *not in* the vertex cover (but covered from below).

So the plan is to store, for each node $u$, two numbers, $u\_{\text{in}} = c\_i$ and $u\_{\text{in}} = c\_o$, and in the end, we will look at what are the values in the root node $r$, i.e. $r\_{\text{in}}$ and $r\_{\text{out}}$.

**The Algorithm**

The algorithm is then quite simple. For the base case, starting at the leaves, in leaf node $v$, you store $v\_{\text{in}} = w(v)$ and $v\_{\text{out}} = 0$. Clearly, in the subtree with only one node, there are no edges to cover, so this is quite easy.

Then the rest of the algorithm is given a node $v$ with children $u\_1, \dots, u\_d$, we need to compute two cases.

1. $v$ is *in* the vertex cover: then the optimal solution is $v\_{\text{in}} = w(v) + \sum\_{u \in u\_1 \dots u\_d} \min(u\_{\text{in}}, u\_{\text{out}})$
2. $v$ is *not in* the vertex cover, so *all children must be*, hence $v\_{\text{out}} = \sum\_{u \in u\_1 \dots u\_d} u\_{\text{in}}$

Now, the only thing we need to do is return the result of the root node $r$, which can either be *in* or *not in* the vertex cover, so we return $$ \min( r\_{\text{in}}, r\_{\text{out}}) $$

---

In other words, we found out what information we need in the "separator" of a subtree, and how can combine the information from the subtree with the rest of the tree.

1. Exercise: Solve Weighted Vertex Cover and Weighted Independent Set on trees.
2. Exercise 2: Solve Weighted Dominating Set, which needs one more state, namely *in the dominating set*, *not in the dominating set but dominated*, *not yet dominated (dominated from above)*.
> 4 votes

---
Tags: algorithms, trees, dynamic-programming, recurrence-relation, recursion
---


# Question
Title: How does a TLB lookup compare all keys simultaneously?
I am reading OS Concepts dinosaur book which says, "Each entry in the TLB consists of two parts: a key (or tag) and a value. When the associative memory is presented with an item, the item is compared with all keys simultaneously."

I checked How does a TLB and data cache work? but it does not say anything about the implementation that allows this parallel checking of the keys.

I read something about a parallel hash table here: http://www.cs.cmu.edu/afs/cs/academic/class/15210-s12/www/lectures/lecture27.pdf

Is this the basic idea? The insertion of a key outputs a frame number and this could either be a hit or miss?

# Answer
Computer hardware is fundamentally parallel. Even a modern single CPU core is pipelined, meaning that at the same instant in time, one physical part of the CPU is initiating a fetch of an instruction, another is decoding a slightly earlier fetched instruction, another is calculating the new result of a slightly earlier decoded instruction, and another is writing back the results of a slightly earlier calculating instruction.

One of the reasons a layer 1 cache in a CPU is so small, and so much more expensive per bit of storage, is that the tag cache portion of the address is broadcast to multiple cache lines, and each of them has some independent hardware logic to compare this tag value against its own tag value in parallel, each independently calculating "that tag matches what I have" or "it doesn't match me".
> 5 votes

---
Tags: memory-access, paging, cache
---