# Question
Title: Space-efficent storage of a trie as array of integers
I'm trying to efficiently store a list of strings in an array with the following constraints:

* All strings consist of 8-bit characters (0..255).
* The final trie is static, i.e. once it is built, no strings have to be inserted or removed.
* Looking up a string of length $m$ must be done in $O(m)$ with a constant factor as low as possible.
* Looking up a string should be possible in an incremental manner, i.e. the end of a string to look up isn't known in advance.
* The only available memory structure to store the data is an array of integers. In particular, there are no pointers or dynamic memory allocation.
* Once an array is allocated, it cannot be resized and its memory cannot be released anymore.
* Memory is rare, so the final data structure should be as compact as possible and no unnecessarily long arrays should be allocated.
* Computation time is not important for the building phase, but for memory usage the consraints above apply.

The aim is to have a data structure to quickly find prefix matches of a long string. For example, if the input string is `foobar`, the match results will vary if the array has stored the strings `foo` and `bar`, or just `foobar`. For this incremental lookup is important.

**Preface**

My current approach is a trie that is stored in the array with the following structure:

$$ \fbox{$\vphantom{^M\_M} \\;i\_0 \\;\ldots\\;i\_{255}\\;$}\\, \fbox{$\vphantom{^M\_M} \\;i^\*\_0 \\;\ldots\\;i^\*\_{255}\\;$}\\, \fbox{$\vphantom{^M\_M} \\;w\\;$}\\, \fbox{$\vphantom{^M\_M} \\;\mathit{last}\\;$}\\, \fbox{$\vphantom{^M\_M} \\;B\_0\\;$}\\,\fbox{$\vphantom{^M\_M} \\;B\_1\\;$}\\,\ldots $$

where $i\_k$ is a mapping from each unique input character $k$ to an integer $1 \leq i\_k(c) \leq w$ with $i^\*$ being the corresponding reverse mapping of $i$. Each node in the trie is stored as a block $B$ of size $w+1$. The mapping $i$ is used to reduce the size of each block, because not the whole character range has to be stored but only the number of characters actually used. This comes at the expense of having one more indirection when looking up words. (The field $\mathit{last}$ here is used as a pointer to the field after the last block in the array, used to find the next allocation point.)

Each block looks like this:

$$ \fbox{$\vphantom{^M\_M} \\;b\\;$}\\, \fbox{$\vphantom{^M\_M} \\;c\_1 \\;\ldots\\;c\_w\\;$} $$

$b$ is either 1 if the word represented by that block is in the trie, and 0 otherwise. $c\_i$ represent all unique input characters (after the $i$ mapping). If the value of $c\_i$ is equal to 0, there is no entry for this character. Otherwise $c\_i$ is the index into the array at which the block to the following letter starts.

To build the trie, the first step is calculate the bijection $i$/$i^\*$ and $w$. Then new blocks are added with each prefix that isn't already present in the trie.

**Problem**

While this approach works so far, my main problem is memory usage. The current approach is extremly memory expensive when only few words share longer prefixes (which is usally the case). Some tests show that the typical number of non-empty fields is only about 2-3% of the whole array. Another problem is that the final number of needed array fields is only available after the trie has already been built, i.e. I have to be conservative when allocating the memory to not get out of memory while adding new blocks.

My idea now was to use a compressed trie/radix trie instead with two types of blocks: 1) the ones above that represent nodes with several children, and 2) compressed blocks (similar to C char arrays) that represent suffixes in the trie. For example, when the words `apple juice` and `apple tree` should be stored in the tree, there would be seven normal blocks for the common prefix `apple`  and a compressed block for each `juice` and `tree`. (Perhaps that would also allow to merge common suffixes for words with different prefixes.)

The problem with this is that is may lead to gaps in the array while building the trie. Consider the situation in the above example, in which only `apply juice` is stored as a compressed block in the trie. Now `apple tree` is inserted, which would lead to a removal of the `apple juice` block and addition of `juice` and `tree` blocks instead, which will not fit into the left hole in general.

Under the given constraints, can anyone see an algorithm to store strings most efficiently in the array while keeping the linear lookup time?

# Answer
> 3 votes
Instead of a trie, here is an alternative approach that is compact and easy to implement:

Sort the list of strings. Store the sorted list. Use binary search for lookups.

To store the string, have two arrays: $A\[1..n\]$ is an array with $n$ entries, where $n$ is the number of strings; $B\[1..M\]$ is an array with $M$ characters, where $M$ is the sum of lengths of all of the strings. $B$ stores the concatenation of all of the strings, in sorted order. $A\[i\]$ holds an offset into $B$ where the $i$th string is stored. In other words, the $i$th string is $B\[A\[i\]..A\[i+1\]-1\]$.

To look up a string, use binary search into the sorted list of strings. You'll be able to look up a string of length $m$ in at most $O(m \log n)$ time, and perhaps less (we're at the point where asymptotic analysis is not useful for distinguishing between these running times, as the constant factors may be more significant than the $\log n$ or $\log \log n$ terms).

Note that this can support character-by-character online lookups. In particular, suppose we have seen the first $k$ characters of the search query $Q$. Assume that we have used binary search to find the index $i\_\ell$ of the first string that starts with $Q\[0..k-1\]$ and the index $i\_u$ of the last string that starts with $Q\[0..k-1\]$. Now, we receive the $k+1$st character of the search query, namely, $Q\[k\]$. Then we can update $i\_\ell$ and $i\_u$ using binary search (within the narrow range of indices $i\_\ell..i\_u$); this takes $O(\log(i\_u-i\_\ell))$ steps of binary search.

As a performance optimization, notice that since you know all strings within $i\_\ell..i\_u$ start with the same $k$ characters, during the binary search, you don't need to compare all $k+1$ characters of the search query to the first $k+1$ characters of each string in your list. Rather, you can look only at the $k+1$st character: e.g., compare $Q\[k\]$ to $B\[A\[i\]+k\]$, when examining index $i$ during the binary search. As a result, each step of the binary search takes only $O(1)$ time. So, the entire binary search for processing a single character takes $O(\log(i\_u-i\_\ell))$ time, and it allows you to update the set of all matches in an online fashion as you receive the search query character-by-character.

This approach will be very compact, supports online searches, is easy to implement, and might be competitive in running time.

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


# Question
Title: Question about growth rates of functions involving n and logn
I was studying for an algorithm exam and was having trouble answering (or rather proving) one of the practice problems. I want to find the correct symbol among $o$, $\omega$, $\Theta$ that would best describe the relationship between two functions $f(n) = (\log n)^{100} + n^{0.01}$ and $g(n) = (\log n)^{50} + n^{0.05}$. Intuitively, it seems like $f(n) \in o(g(n))$ because the extra $n^{0.04}$ in $g(n)$ grows much faster than the $\log^{50} n$ in $f(n)$. However, I am not really sure how to prove this using first principles. Could anyone provide any suggestions? Thanks in advance.

# Answer
There exists some $n\_0 \> 0$ such that $\log n \le n^{0.0001}$ for all $n \ge n\_0$. This can be seen, e.g., by taking the limit: $$ \lim\_{n \to \infty} \frac{\log n}{n^{0.0001}} = \lim\_{n \to \infty} \frac{10000}{ n^{0.0001}} = 0. $$

This means that, for $n \ge n\_0$, $$ f(n) = \log^{100} n + n^{0.01} \le \left( n^{0.0001} \right)^{100} + n^{0.01} = 2n^{0.01}. $$

Therefore, using the fact that $g(n) \ge n^{0.05}$: $$ \lim\_{n \to \infty} \frac{f(n)}{g(n)} \le \lim\_{n \to \infty} \frac{2n^{0.01}}{n^{0.05}} = \lim\_{n \to \infty} \frac{2}{n^{0.04}} = 0, $$ implying that $f(n)=o(g(n)).$
> 1 votes

# Answer
Ok this is not a good way to do it but here is my approach.

So, here it suffices to prove $\lim\_{n\to\infty} \frac{f(n)}{g(n)} = 0$. That will imply $f(n) = o(g(n))$

---

proof of $\lim\_{n\to\infty} \frac{f(n)}{g(n)} = 0$

$\lim\_{n\to\infty} \frac{f(n)}{g(n)}$

$= \lim\_{n\to\infty} \frac{(log(n))^{100} + n^{0.01}}{(log(n))^{50} + n^{0.05}}$

$= \lim\_{n\to\infty} \frac{100.(log(n))^{99}. \frac{1}{n} + 0.01(n^{-0.99})}{50.(log(n))^{49}. \frac{1}{n} + 0.05(n^{-0.95})}$ $\because\text{(L'hopital's rule)}$

Now, multiply lower and upper term by $n$

$= \lim\_{n\to\infty} \frac{100.(log(n))^{99} + 0.01(n^{0.01})}{50.(log(n))^{49} + 0.05(n^{0.05})}$ ....

....

....

. repeating above two steps 100 times we'll get

$= \lim\_{n\to\infty} \frac{100! + 0.01^{100}(n^{0.01})}{0.05^{100}(n^{0.05})}$

$=0$
> 0 votes

---
Tags: time-complexity
---


# Question
Title: Would an optimization version of the 3-partition problem also be strongly np-complete / np-hard?
Anyone know if an optimization variant of the 3-partition problem (as explained there) would also be strongly np-complete?

This would be where the goal is to group a multiset whose size is evenly divisible by 3 into triplets that sum to as close to a target as possible and to produce this grouping. This would not be a decision problem but an actual optimization problem.

# Answer
> 3 votes
The objective function $f$ (to minimize) is not completely formalized in the question. It is written that the groups should "sum to as close to a target as possible", so it seems natural to assume that $f$ is $0$ if the sum of the elements in each group is equal to the target, and greater than $0$ otherwise.

Two examples of such functions are the maximum and the sum of the absolute differences between the sum of the elements in each group and the target.

Under this assumptions, the above optimization problem is strongly NP-hard since the answer to the decision problem is "yes" if and only if an optimal solution $S$ to the optimization problem satisfies $f(S)=0$.

It would not be NP-complete since it does not belong to NP (which only contains decision problems).

---
Tags: algorithm-analysis, np-complete
---


# Question
Title: Modifying digraph to make it strongly connected
I came across this problem and have not been able to find a solution.

Given directed graph $G$, devise an algorithm to find the minimum number of edges to flip/change/transplant such that the modified graph $G'$ has a path from any vertex to any other vertex. That is, we can remove any edge between any two vertices and add them back to the graph any which way.

Anyone have any idea how to solve?

Clarification for edge modification: You can edit edges any which way for a cost of one move. Once you remove an edge between any two vertices, you can reattach it to the same two vertices but flipped, or attach it to two different vertices entirely, or just have the edge go from the original source vertex to another vertex, or a different source vertex to the same destination vertex.

# Answer
On solvable instances (not all instances are solvable; see narek Bojikian's comment on my other answer for a simple necessary and sufficient condition), this is **NP-hard by reduction from Directed Hamiltonian Path**. The basic idea is to add enough isolated vertices to the input digraph to force the only possible solution to be a single cycle, and then see whether it is possible to accomplish this with few enough moves that the unmoved edges must form a DHP in the original digraph.

Given an instance of Directed Hamiltonian Path consisting of a digraph $(V, E)$ with $n=|V|, m=|E|$, add $m-n$ isolated vertices. Observe that a single SCC can be formed by rearranging the $m$ edges into an arbitrary cycle that touches each of the $m$ vertices that now exist. This can be done trivially if we are prepared to move all $m$ edges, but if we limit ourselves to moving at most $m-n+1$ edges, then this is possible only if $m-n+1$ edges are moved from somewhere to form a path that connects some vertex $u$ of the original digraph to some new isolated vertex, visits each new isolated vertex in some order, and finally returns to some other vertex $v$ of the original digraph. (We have $u \ne v$ since $u=v$ would leave just $n-1$ edges available to visit all $n$ vertices of the original digraph, which is not enough.) In this case, the unmoved $n-1$ edges that remain necessarily form a path from $v$ to $u$ through the $n$ vertices of the original digraph, and thus constitute a DHP through it. This shows that a YES answer to the constructed instance implies a YES answer to the original problem.

To see that a YES answer to the original DHP problem implies a YES answer to the constructed instance, pick up the $m-n+1$ edges that are not part of the DHP, and construct a path as described above, forming a single cycle comprising all $m$ vertices using just $m-n+1$ moves.
> 3 votes

# Answer
Under the clarified definition of what moves are possible, the problem is unsolvable for many cases, e.g., the 2-vertex graph a-\>b. (a is not reachable from b, but the only allowed move is to change the graph to a\<-b, and then b is not reachable from a.)
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: Can algorithms of arbitrarily worse complexity be systematically created?
We’ve all seen this:

Can we get worse?

Part 1: Can mathematical operations of increasing orders of growth be generated, with or without Knuth’s up-arrow notation?

Part 2: If they can, can algorithms of arbitrary complexities be systematically generated?

Part 3: If such algorithms can be generated, what about programs implementing those algorithms?

# Answer
Yes, of course. $2^{f(n)}$ is asymptotically larger than $f(n)$, so you can come up with an unending sequence of larger and larger running times.

The answer to your other questions are also yes, by the time hierarchy theorem.
> 2 votes

# Answer
On the one hand, every algorithm *(by which I will mean a Turing machine which halts on all inputs)* has computable runtime. On the other hand, by diagonalization for every computable function $f$ there is a computable set $X\_f$ such that no Turing machine computing $X\_f$ runs in time $O(f)$.

* This is a good exercise. The obvious approach doesn't work: the set of Turing machines which have runtime bounded by a given function is not computable. So you need a trick ...

So the only bound on runtime is the trivial one, that runtime has to be computable.

*(If we drop the requirement that our machines halt on all inputs, things get more complicated - see the Busy Beaver function.)*
> 0 votes

---
Tags: complexity-theory, algorithm-analysis, code-generation
---


# Question
Title: How do we construct reductions for NP-Completeness
I'm wondering in what direction we construct reductions to prove that a problem is NP-complete. Say the question is asking to prove that the vertex cover problem is NP-complete given that the independent set problem is NP-complete.

In this case, do we start with an instance of the vertex cover problem and show how we can transform this instance into an instance of the independent set problem? Or, do we start with an instance of the independent set problem and transform it into an instance of the vertex cover problem?

I understand the relationship between vertex cover and independent set, however, I am confused on the direction of reduction.

# Answer
> 1 votes
You reduce Independent set to Vertex cover. You want to say that the vertex cover is atleast as hard as Independent set. One could way to remember is you are using a subroutine for vertex cover to solve Independent set. Since Independent set is Np-C you know you know the subroutine you used can't be polynomial. If you do the other way around using a subroutine of Independent set to solve Vertex cover. This does not say anything, as there might be a better way to solve vertex cover and does not show anything.

# Answer
> 0 votes
To prove a problem B is NP-complete given that problem A is NP-complete (A = independent set, B = vertex cover, in your case), you start with an instance of problem A and transform it into an instance of problem B.

This reduction from A to B implies that (every instance of) problem A can be reformulated as (an instance of) problem B. In other words, problem A is a special case of Problem B, and so Problem B is at least as hard as (or more general than) problem A. If problem A cannot be solved in polynomial time, then problem B also cannot be solved in polynomial time. If B is in NP and if problem A is NP-complete, then so is problem B.

# Answer
> 0 votes
You need two steps to show that a problem $T$ is NP-complete.

**Step 1. Show that $T$ is at least as hard as an NP-complete problem**
In other words, show that $T$ is NP-hard. To do this, you choose your favorite NP-complete problem $Q$, and then show that for every instance of $Q$, you can model an instance of $T$ that corresponds to $Q$. Thus, an algorithm which can solve $Q$ in polynomial time can also solve $T$ in polynomial time.

**Step 2. Show that a given solution to $T$ can be verified in polynomial time**
This is a crucial step if you want to show NP-completeness. For any feasible solution of $T$, you should provide an algorithm that checks whether the solution is true in polynomial time.

---
Tags: np-complete, reductions
---


# Question
Title: How do you prove the Natarajan's Lemma intuitively?
Let $H$ be a hypothesis class of multiclass predictors; namely, each $h\in H$ is a function from $X$ to $\[k\]$.

Denote the Natarajan dimension of $H$ by $Ndim(H)$. Hope you can give me an intuitive proof of the following lemma .

$|H|\le |X|^{Ndim(H)}\cdot k^{2Ndim(H)}$

The lemma is in the book **"Understanding Machine Learning: from theory to algorithms"**. You just search keywords **"Lemma 29.4"**.

# Answer
> 0 votes
You can check Natarajan, On learning sets and functions or Haussler and Long, A generalization of Sauer's lemma.

---
Tags: machine-learning, learning-theory
---


title: Halting problem vs Universal Language

text:
# Question
Title: Halting problem vs Universal Language
Wikipedia defines halting set as follows:

> $H = \\{(i, x) |$ program $i$ halts when run on input $x\\}$

Ullman defines universal language as follows

> $U = \\{(M, w) |$ Turing machine $M$ accepts $w\\}$

This link says:

> The universal TM, $U$, is a TM which takes as input an encoded machine/string pair, $(M,w)$, and performs the actions of $M$ running with input string $w$. The most important achievement is to simulate the accepting (i.e., halting) behavior of M. That is we want:
>
> $M$ halts on $w$ if and only if $U$ halts on $E(M,w)$
> or, in notational terms,
> $M↓w$ if and only if $U↓E(M,w)$

Note that $E()$ is encoding function. Also I feel above defines universal language somewhat different than what Ullman defines. While defining universal TM, Ullman says "$M$ **accepts** on $w$", whereas above link says "$U$ **halts** on $E(M,w)$". Its accept vs halt which is I am trying to point out. I feel TM can halt with or without accepting. So I feel the definitions of universal language differs in both sources. **Q1.** Right?

Thats why the link says:

> HALT $= \\{ x ∈ \\{c,1\\}^\*: x = E(M,w)$ where $M↓w \\}$
> HALT is precisely the language accepted by the Universal Turing Machine, U:
> $M↓w$ if and only if $U↓E(M,w)$

where $↓$ seems to be symbol indicating "halts"

But Ullman says:

> One often hears of the halting problem for TMs as a problem similar to $L\_u$ \- one that is RE but not recursive. In fact, the original TM of A. M. Turing accepted by halting, not by final state. We could define H(M) for TM M to be the set of the inputs $w$ such that it halts given input $w$, **regardless of whether or not $M$ accepts $w$**. Then, the halting problem is the set of pairs $(M,w)$ such that $w$ is in $H(M)$

By this, I feel Ullman disagrees that halting language is what is accepted by Universal TM.

The link also says:

> In particular, the universal TM accepts HALT, but no TM can decide HALT.

If I get it correct, I believe "universal TM accepts HALT" means Universal UTM can simulate HTM (accepting TM and w as input) which checks whether input TM halts on input w. **Q2.** Am I right with this? **Q3.** But then that does not mean L(UTM) = L(HTM) as said by the same link in fourth quote. Right?

**Q4.** Can you summarise halting problem vs universal language? I feel the link is somewhat incorrect and Ullman is correct. I believe:

* Halting language L(HTM) = {(TM,w) | TM halts on w with or without accepting}
* Universal language L(UTM) = {(TM,w) | TM accepts w by halting in final state}
* From above definitions, Halting language is not same as Universal language
* Universal language can simulate Halting language as follows: (HTM,(TM,w)) | HTM accepts (TM,w) by halting in final state when TM halts on w with or without accepting w

Am I correct with above summary understanding?

# Answer
> 1 votes
### So first Q1:

At first the definitions of *universal language* and the *universal machine*.

The universal language is defined as you mentioned in the question:

$$ U= \\{(M,w)\\:|\\:\text( TM\\:M\\:accepts\\:w)\\} $$

The Universal Turing Machine on the other hand is defined as follows:

A machine, which can simulate an arbitrary TM on arbitrary input. Or you can say: It's a TM U, which you can give a random other TM M and an input w. The Universal TM then simulates the given TM M on that input w.

So the Universal Turing Machine accepts, if and only if the TM M accepts w (because it simulates M on w). It rejects, if and only if, the TM M rejects w. It halts, if and only if the TM M is halting on w (because it simulates M on w). So the Universal Turing Machine accepts the above defined Universal Language.

Now to the question: The definition of the link is a little bit misleading. The Universal TM doesn't accept HALT on default, but you can modify the Universal Turing Machine in a simple way to accept HALT: The reject states are replaced by accept states. The now modified UTM (let's call it U') is accepting HALT. Because now it always accepts, if the machine M is accepting or rejecting the input w, without getting stuck in a loop: U' is accepting, if M is halting on w.

### Then Q2:

A "TM M is accepting a language L" means, that it definitely halts on w $\in$ L, but does not mean it halts on w $\notin$ L (it can loop forever). So that means, if the U' is accepting HALT, it holds for sure, only if $(M,w) \in HALT$. If $(M,w) \notin HALT$, the universal TM can halt or can loop forever. So it isn't deciding HALT, it's just accepting HALT.

(Actually it's the slightly modified Universal TM, which is accepting HALT as mentioned in answer Q1.)

### Q3:

If you mean the Universal Language with L(UTM) and the halting language with L(HTM), then yes L(UTM) $\neq$ L(HTM).

### Q4:

First three points you made are correct.

In the last point you have to be more exact: The (modified) UTM can accept the Halting Language, but cannot decide it. So you can check, whether M halts on w, but it may loop forever.

# Answer
> 0 votes
> So I feel the definitions of universal language differs in both sources. Q1. Right?

You quoted Ullman's definition for Universal language but didn't quoted the other source definition of universal language. The other source defined universal Turing machine *which is not language.* So the answer to your first question is that no you aren't right since the second source didn't have defined Universal language.

> I believe "universal TM accepts HALT" means Universal UTM can simulate HTM (accepting TM and w as input) which checks whether input TM halts on input w. Q2. Am I right with this?

If by HTM you mean Halting Turing machine $H$ that halts on its input string $w$, then your statement is correct because if you have a UTM (universal Turing machine) $U$, you can give $H$ and $w$ as its input and simulate $H$ behavior using $U$. By definition of the link, you give $H$ and $w$ as $E(H,w)$ to a universal Turing machine. Note that this Universal Turing machine can only accept whenever $H$ really halts on $w$ but it can't reject when $H$ stuck in infinite loop. So It can't decide $E(H,w)$ which means $U$ can just understand *accept* but not *reject* (And there is no TM which can understand when $H$ doesn't halt on $w$).

> Q3. But then that does not mean L(UTM) = L(HTM) as said by the same link in fourth quote. Right?

If by $L(UTM)$ and $L(HTM)$ you mean the languages you gave above in the summary part. No they aren't the same.

> * Universal language can simulate Halting language as follows: (HTM,(TM,w)) | HTM accepts (TM,w) by halting in final state when TM halts on w with or without accepting w
>
> Am I correct with above summary understanding?

Well, I don't think language can simulate each other. statement you can give about language is that one is subset of the other one that is $L(UTM)\subset L(HTM)$.

---
Tags: formal-languages, turing-machines, undecidability
---


# Question
Title: adding an edge, Is T still a MST to the new graph?
Suppose I have a minimum spanning tree $T$ in a graph $G=(V,E)$ with positive edge weights $w$. Provide an algorithm that after adding a new edge $e$ with a unique weight $w(e)$ to $G$, returns true if $T$ will still be an MST.

# Answer
> 1 votes
Let $n=|V|$ and $e=(x,y)$ be the new edge. Let $P$ be the unique path between $x$ and $y$ in $T$. Clearly $C = P + e$ is a cycle in $G+e$.

Let $f^\* = \arg\max\_{f \in P}{w(f)}$. $T$ is an MST of $G+e \iff w(e) \ge w(f^\*)$.

**The $\Rightarrow$ part:** If $w(e) \< w(f^\*)$ then $T - f^\* + e$ is a spanning tree of $G+e$ of cost $w(T) - w(f^\*) + w(e) \< w(T)$, showing that $T$ cannot be a MST of $G+e$.

**The $\Leftarrow$ part:** If $w(e) \ge w(f^\*)$ then $e$ is one of the heaviest edges of $C$ and, by the cycle rule, there exists a MST of $G+e$ that does not include $e$. In particular, any MST of $G$ will also be an MST of $G+e$ (the converse is not true in general, but it is in your case since you also know that $w(e) \> w(f^\*)$ and hence no MST of $G+e$ can contain $e$).

A reasonable representation of $T$ will allow you to find $P$ (and hence $w(f^\*)$ in time proportional to $|P| = O(n)$).

---

If you can preprocess $T$, then you can do better. For example you can build a lowest common ancestor (LCA) oracle in $O(n)$ time to find in constant time the LCA $z$ between $x$ and $y$. Then $w(f^\*)$ will be the maximum weight between the two heaviest edges in the unique paths in $T$ from $x$ and $y$ to $z$, respectively. These edges can be found in $O(\log n)$ time after a $O(n \log n)$ time preprocessing. For each vertex $v$ of the tree, and for each $i=1,\dots,\lceil \log n\rceil$ store:

* the farthest vertex $u\_v^{i}$ in the path from $v$ to the root of $T$, such that $u$ is at a distance of at most $2^i$ from $v$ in $T$; and
* the heaviest edge $e\_v^{i}$ in the unique path from $v$ to $u\_v^{i}$ in $T$.

To report the edge $M(x,z)$ of maximum weight between a vertex $x$ and an ancestor $z$ of $x$, let $\ell$ be the largest power of $2$ that is smaller than or equal to the distance in $T$ between $x$ and $z$. Return the heaviest edge between $e\_v^i$ and $M(u\_v^{i}, z)$ (if $u\_v^{i} \neq z$). Notice that the distance between $u\_v^{i}$ and $z$ is at most half the distance between $v$ and $z$, meaning that you will only need to look at $O(\log n)$ edges.

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


# Question
Title: Problem with understanding the Mathematical Equations related to Testing Tool
I have downloaded the slides from the site: \[Compliance and Violation Patterns It says No writes after calls. I can understand this concept. It’s a remedy for reentrancy problem. But it shows compliance and security patterns in some technical language related to Datalog or to some language related to software representation. Can some body please guide me what is the meaning of those equations?

Zulfi.

# Answer
> 1 votes
They are statements about patterns of correct and incorrect code:

1. For all call sites L1, there does not exist a store site L2 such that ... (and here I’m not clear—is that L2 may follow L1? Or that the truth of the statement may follow from the program, depending on L1 and L2?)
2. For all call sites L1, there exists a store site L2 such that ... (idem.)

---
Tags: security, software-testing
---


# Question
Title: Given a regular language, calculate its equivalence classes
I was given the following regular language:

For any $n$, the language $L\_{n}$ consists of all words over $Σ = \\{0, 1\\}$ whose $n$th character from the end is 1.

I know it's regular because it can be expressed as a regular expression ($\Sigma^{\*}1\Sigma^{n-1}$), and I constructed a DFA and an NFA for it. I need to calculate its equivalence classes. I thought that the equivalence classes will be words that have 1 in the same place later in the word - for example one of the classes will be $L(\Sigma^{\*}1\Sigma^{n-2})$, because no matter what digit will be added to all these words, the new words will belong to the original language. But I'm not sure I'm on the right track. I would love it if I could understand the process of thinking on this kind of question.

# Answer
> 2 votes
Whether a word and its extensions belongs to $L\_n$ or not depends on its final $n$ letters (we'll see later what happens if a word is shorter than $n$ letters). Indeed, we can "probe" all of these letters using the following: for $i=1,\ldots,n$, we have $w1^{n-i} \in L\_n$ iff the $i$th letter from the end is $1$. This shows that if two words have different length-$n$ suffixes, then they definitely belong to different equivalence classes.

In contrast, we can check that any two words with the same length-$n$ suffix are equivalent. Indeed, suppose $x,y$ are such words, and consider a word $z$. If $|z| \leq n-1$ then $xz \in L\_n$ if the $n-i$'th letter from the end of $x$ is $1$. Since $x,y$ have the same length $n$ suffixes, the condition for $yz \in L\_n$ is identical. If $|z| \geq n$, then whether $xz \in L\_n$ or not only depends on $z$, and in particular holds just as well for $yz \in L\_n$.

Finally, what about words which are shorter than $n$ letters? Recall the test we had above: $w1^{n-i} \in L\_n$ iff the $i$th letter from the end is $1$. If $|w| \< i$ then $w1^{n-i} \notin L\_n$, and so $w$ behaves as if the $i$th letter from the end is $0$. Pursuing this route, we find that the equivalence class of $w$ depends on the length-$n$ suffix of $0^nw$, and this definition works whether $|w| \geq n$ or not.

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


# Question
Title: How to find a path that connects all the dots in the matrix?
I have a matrix that consists of **0**, **1**, **2**.

* **0** \- dot.
* **1** \- block.
* **2** \- start dot (initial position in the path).

I have to create a path from the start dot, that

1. connects all the dots in the matrix and
2. visits each dot ONE time
3. doesn't visit blocks

In other words, create a Hamiltonian path in a matrix. A pic below exhaustively shows what I want.

# Answer
The problem of finding a Hamiltonian path in a partial grid graph (that is, an arbitrary subgraph of a grid, not necessarily even induced) remains NP-complete \[1\]. Thus, you are likely out of luck for a polynomial-time approach.

A good choice for a heuristic might depend on your instance size and further structure. However, in general, you could try say a genetic algorithm, ant colony optimization, or some more problem specific heuristic.

---

\[1\] Papadimitriou, Christos H., and Umesh V. Vazirani. "On two geometric problems related to the travelling salesman problem." Journal of Algorithms 5.2 (1984): 231-246.
> 4 votes

# Answer
Actually, grid graphs are a very specific class of input problems, and a good number of algorithms are known that can solve problems which remain hard in other instances, i.e., non-grid graphs.

Even if it is not directly related to your question, I could not avoid citing the following paper:

F. Keshavarz-Kohjerdi, A. Bagheri, A. Asgharian-Sardroud. A linear time algorithm for the longest path problem in rectangular grid graphs. Discrete Applied Mathematics, 2012 160(3) 210-217.

For your specific problem, the best (up to my knowledge) is a **polynomial-time algorithm** in solid grid-graphs:

W. Lenhart, C. Umans, Hamiltonian cycles in solid grid graphs, in: Proc. 38th Annual Symposium on Foundations of Computer Science, FOCS’97, 1997, pp. 496–505.

Hope this helps,
> 2 votes

# Answer
One simple way is to face this problem like a state-space search. Assume that going in each of 4 directions on a node that has not been visited is one action. Make a function that is responsible for producing all the next possible states given the current state. It produces a list of all next actions (at most 4 states). As you may know, we call this function the successor function. Then run a BFS\DFS search using this function. Run till all nodes on your matrice are visited.

Another better way is to face this problem like a traveling salesman problem \[1\]. Although it tries to find the path with the lowest cost, it is a good choice. There exists a dynamic programming algorithm for solving this problem. Tushar Roy has given a good explanation of this algorithm in his youtube channel (link).

I hope this can help you. Good luck!
> 1 votes

---
Tags: algorithms, graphs, search-algorithms, matrices, hamiltonian-path
---


# Question
Title: Data structure to report all axis aligned bounding boxes intersecting an axis aligned query line
I would like to build a Data structure that uses subquadratic space to quickly report a set of AABBs (axis aligned bounding boxes) in 3 dimensional space when it intersects a query line? I am only interested in the design, no coding. I believe I can use the approach of kd-trees assuming that the query line is also axis aligned, say x-axis. Any help will be pretty much appreciated. Thanks in advance

# Answer
If your query line is x-axis aligned, this is essentially a 2D problem, as you can project all AABBs on the $(y,z)$-plane and answer the following question: *Given $n$ axis aligned rectangles and a query point $p$, report the rectangles containing $p$.*

To answer this question you can build a 2D segment tree. This is similar to a 1D segment tree, except that you start building your segment tree according to the projections of your rectangles on one dimension (say $y$) and instead of having some interval $I$ as a leaf, you replace it with a segment tree storing all projections on the $z$-axis of rectangles whose projection on the $y$-axis contain $I$.

You can then query a point by going down the tree and looking for all rectangles which are potential candidates according to their $y$-coordinates and then check among those which "fit" according to their $z$-coordinates.

This leads to $O(n\log^2(n))$ space used, $O(\log^2(n))$ time per query and $O(n\log^2(n))$ construction time.
> 2 votes

# Answer
Assuming that the query line is long, you could split it into small pieces (let's talk about 'long' and 'small' later). For each segment you calculate the bounding box and then you can query with that bounding box any tree that stores AABBs (R-Trees/BVH, Quadtrees, ....). For each result you will have to check manually whether it really intersects with your query line, but this approach should greatly reduce the number of AABBs you have to check.

So, should you split your line into chunks? If it is axis aligned, then no, because the AABB of the line will be exactly the line itself. If the line is not axis aligned, then it depends on how long it is and how far away it is from being axis aligned. The best way is to try out different segmentation strategies, but a good start may be to mage segment at most 5 times as long as your average AABB. This should give a reasonable balance between having to execute many queries (one for each segment) and the number of false positives returned by each query.
> 1 votes

---
Tags: algorithms, data-structures, computational-geometry
---


# Question
Title: delete node from linked list (lang w/GC) -should deleted item 'next' be set to null
Regarding: delete a node from a linked list algorithm,in *procedural* languages with *garbage-collection*. Should there be a **step** in the algorithm, of **setting** the *removed-node-next-pointer* to **null** ?

(Several high-school-CS-teachers in my area teach YES, while others teach NO)

What is the right approach?

/thanks ran

# Answer
If you mean the next pointer of the node that was deleted, as far as I know it is normally not necessary to set the pointer to null. Once the node is deleted, if the code is not buggy, then the code should not access the node after it is deleted, so the value of its next pointer should be irrelevant. Sometimes some people do set the pointer to null, as a form of defensive programming (just in case the program is buggy and accesses that node after it was deleted).

I suggest that a useful exercise would be to ask your teachers why they teach yes or no. Hearing their reasoning might be instructive and interesting!
> 2 votes

---
Tags: algorithms, linked-lists, garbage-collection
---


# Question
Title: How are image processing and computer vision related to artificial intelligence.?
We have often heard both terms image processing and computer vision in AI sessions

But i am confused, how they both are related to artificial intelligence?

# Answer
The answer is simple.

Assume you are making a robot for interacting with other people. The first thing that it needs is to recognize people who it sees.

Another application is in self-driving cars. If the car is not able to see the road and read the signs or break when it sees a dangerous obstacle ahead, how could it drive in a safe way?

There are a lot of smart agents who need to see an recognize a scene or a person and many other applications; this is where computer vision and image processing come handy. One of the best techniques that is used in Computer Vision is machine learning which is one of the cutting-edge methods in AI.
> 1 votes

---
Tags: artificial-intelligence, computer-vision, image-processing
---


# Question
Title: Recursive Call Inside Argument List (C++)
So, my professor asked me to implement recursion in different ways to compute $a^n$ (a and n being integers) and rank them according to their space efficiency. Now, here is one of the methods I came up with:

```
  int Power (int a, int n)
 { if ( n == 0 )
  return 1;
   if ( n % 2 == 0)
  return Power(Power(a, n/2), 2);
   else return Power(Power(a, n/2), 2)*a;
  }

```

The code compiles well, but leads to a segmentation fault. On debugging, I came to the conclusion that recursive call within the argument list is not acceptable. That is, something like

```
  return Power(Power(a, n/2), 2)

```

or

```
  int m = Power(a, n/2);
  return Power(m, 2);

```

is not allowed but

```
  int m = Power(a, n/2);
  return m*m;

```

is allowed. Why is this the case? Is this true only in C++, or is it a general phenomenon?

# Answer
So I did a dry run of the algorithm as suggested by greybeard in the comments. It turns out that for any a and n, after a certain number of recursions, one ends up getting Power(1, 2). This leads to an infinite recursion because Power(1, 2) also leads to Power (1, 2) after a certain number of recursions.
> 1 votes

---
Tags: recursion, memory-allocation, c++
---


# Question
Title: 3-Dimensional Matching with at Most $2n$ Hyperedges
In 3 dimensional matching, we are given a set $M\subseteq X\times Y\times Z$ where $|X|=|Y|=|Z|=n$. A matching in $M$ is a subset $T⊆M$ such that no elements in $T$ agree in any coordinate. The goal is to find a matching in $M$ of size $n$.

If we assume that $n\leq|M|=m\<2n$, can we solve 3DM in polynomial-time?

I know that in a 2-bounded instance of 3DM, 3DM can be solved in polynomial-time. The 2-bounded instance is when no element appears in more than two triples in $M$. For $m\<2n$, we do not necessarily have a 2-bounded instance.

Further, in a 3-bounded instance of 3DM, 3DM is NP-hard. The 3-bounded instance is when no element appears in more than three triples in $M$, that is $m\leq3n$.

# Answer
The restriction $m \< 2n$ does not help to solve the problem in polynomial time. Note that any 3-dimensional matching instance can be polynomially reduced into an instance with $m \< 2n$ by adding $m$ elements to the sets $X$, $Y$ and $Z$ and $m$ hyperedges to connect these new elements. The resulting instance has $n' = n + m$ and $m' = 2m$, so $m' \< 2n'$ assuming $n\>0$. Also, this reduction can be generalized for any constant $c \> 1$ to show that 3-dimensional matching is NP-complete with the restriction that $m \< cn$.

For solving the problem faster I suggest to find some other restrictions in the instances you have. For example in graphs, the natural parameter to express sparseness would be degeneracy.
> 4 votes

---
Tags: algorithms, np-hard
---


# Question
Title: Total number of WW, WR, RW conflicts in the given example?
```
+---+------+------+
|   | T1   | T2   |
+---+------+------+
| 1 | W(A) |      |
| 2 |      | R(A) |
| 3 | W(A) |      |
| 4 |      | R(A) |
| 5 | W(A) |      |
| 6 |      | W(A) |
| 7 | W(A) |      |
| 8 |      | W(A) |
+---+------+------+

```

In the above scenario can someone tell me how many WW, WR, RW conflicts are there? Can we say that there is a WR(write read) conflict between transactions 1 and 2 from statement 1 to statement 4? As the A value is updated at statement 3, 4th statement read conflicts only with 3rd statement write but not 1st statement write. Can someone tell me in total how many WW, WR, RW conflicts are there between the two transactions?

# Answer
WW conflicts are --\> 1-6, 1-8 , 3-6, 3-8, 5-6, 5-8, 7-8, 6-7

RW conflicts are --\> 2-3, 2-5, 2-7, 4-5, 4-7

WR conflicts are --\> 1-2, 1-4, 3-4
> 0 votes

---
Tags: database-theory
---


# Question
Title: How to count near circular objects in image
I have a image similar to below. In that I need to find all red circles and count them. So, I am thinking to use MATLAB R2011a with Image Processing Toolkit for it. How could I possibly extract them?

# Answer
> 1 votes
A simple approach to start with is to extract just the red channel, do some binary thresholding (e.g., Otsu's method), and then use standard morphology operators to find the blobs. You could try applying a closing operation. Then, you could apply the watershed transformation or region flooding to identify the blobs where the tomatoes are.

A possibly better approach could be to convert to HSV representation, then generate a binary image as follows: every pixel whose hue matches the hue of a tomato (from some range you manually determine) is colored white, the rest are colored black. Then you could continue with morphology operators and watershed/region flooding.

How well this will work will depend upon your requirements (e.g., whether you need to deal with occlusion) and on application-specific details (e.g., how constant in color the tomatoes are).

Take a look at the following questions on StackOverflow; they are quite relevant and will be helpful to you:

and also these resources:

# Answer
> 0 votes
For finding all the circles, all you need is to use a feature extraction technique which I recommend SIFT. SIFT is easy and ready to use in VLFeat library.

Since SIFT is made for gray-scale images, a possible problem may be color. I suggest using it on a gray-scale image. In case it was not able to distinguish a red circle from a green one, you can think of CSIFT \[1\] which is an "A SIFT Descriptor with Color Invariant Characteristics".

An easier way is to employ a histogram of colors besides the SIFT to have the color description of each patch it extracts.

In case you needed a detailed explanation for each part, leave a comment below.

Hope I could help.

---
Tags: image-processing
---


# Question
Title: Read and write ports in a register file?
How many read and write ports in a register file? Moreover, what is the difference between a register and a register file?

# Answer
> 3 votes
A "register file" is an aggregation of registers. That is, it is one component that holds several different registers.

How many read/write ports? Well, this depends. It can be 1 and 1, or more, according to the specific system. If you are the engineer, you can design a register file with as many read and write ports as you desire. The maximal number would probably be the number of registers in the file because there is no point in placing more read/write ports than actual registers (=memory cells).

---
Tags: computer-architecture
---


# Question
Title: Fermat's last theorem: How to (partially) solve by programs
> No three distinct positive integers $a, b, c$ can satisfy the equation : $a^n + b^n=c^n$, if $n$ is an integer greater than two.

The above statement, known as the Fermat's last theorem is proven with rigorous mathematics. I happened to stumble on one particular statement:

> Proofs were eventually found for all values of $n$ up to around $4$ million, first by hand, and later **by computer**.

What I understand is, somehow a computer program assured the theorem was correct upto some value of $n$.

Let us simplify and only stick to $n=3$ (the smallest possible value of $n$). Now my question is, how do I write a program that can ensure that there is no integer solution for $a,b,c$? A complete program is not required, rather some discussion (preferably in pseudocode format) would be appreciated.

# Answer
> 6 votes
See for example Sophie Germain. Sophie Germain proved that every prime number p with certain properties could be used as an expoonent in Fermat's Last Theorem. She used her theorem to prove that all primes up to 100 would work. Apparently checking her theorem was quite a lot of work because later her theorem was used to check first the primes up to 187 and then up to about 1700. Having a computer and being able to check primes using software would have been very helpful. The "intelligent" work was done by Sophie Germain, a lot more boring work could have very well done by a (then non-existing computer).

Kummer proved an improved theorem, which unfortunately was even harder to verify. There were further improvements made, and this was used to check all primes up to 125,000 and later up to 4,000,000. Checking one prime took about 80 minutes on a 1970's computer - that would have been absolutely impossible to do by hand.

So there is a combination: Mathematicians find a way to decide for certain primes p that $a^p + b^p \neq c^p$ for all $a, b, c \geq 1$. The actual method to decide is too much work for a human to do in any reasonable time, so a computer comes very useful.

Wiles' theorem was completely different, all done by hand. However, if you follow the discussion at Wikipedia, you'll find there was mathematics beyond the reach of most mortals, based on more mathematics beyond the reach of most mortals, etc. quite a few levels deep.

# Answer
> 4 votes
First of all, it is well-known that it suffices to consider odd prime $n$

Kummer showed that if $p$ doesn't divide the numerators of any of the Bernoulli numbers $B\_2,B\_4,\ldots, B\_{p-3}$ then Fermat's last theorem holds for $n = p$. Such primes are called regular. Vandiver gave a criterion which handles irregular primes. The criterion is a bit complicated, and is stated in Section 4 of Wagstaff, The irregular primes to 125000.

The criterion requires one to provide an integer $t$ which satisfies some property. Wagstaff states that in practice $t = 2$ always works, but a priori we are not guaranteed that *any* value of $t$ works; and even if no value of $t$ works, that doesn't imply that Fermat's last theorem holds. So the criterion is sufficient but not known to be necessary, and furthermore, event a good $t$ exists, it's not clear how to find it. However, as stated above, in practice $t = 2$ always works.

The work you're describing, proving Fermat's last theorem for larger primes, likely uses the same framework. You can consult Buhler, Crandall, Ernvall and Metsänkylä, Irregular primes and cyclotomic fields to four million.

---
Tags: discrete-mathematics, mathematical-programming
---


# Question
Title: Is relational algebra a procedural, imperative, and/or declarative language?
In *Database System Concepts* 6ed,

> **6.2 The Tuple Relational Calculus**
>
> When we write **a relational-algebra expression**, we provide a sequence of **procedures** that generates the answer to our query.
>
> **The tuple relational calculus**, by contrast, is a nonprocedural query language. It describes the desired information without giving a speciﬁc procedure for obtaining that information. A query in the tuple relational calculus is expressed as: `{t | P(t)}`. That is, it is the set of all tuples `t` such that predicate `P` is true for t.

Does the above mean that relational algebra is a procedural language?

Is relational algebra a declarative language?

Is the tuple relational calculus a declarative language?

Is the tuple relational calculus more declarative than relational algebra is?

Is a procedural language an imperative language? (This is always what I heard, but I also heard that SQL is a declarative language (so is relational algebra) so is not imperative.)

What is the correct or most reasonable or most accepted definition of procedural languages, imperative languages, and declarative languages?

Thanks.

# Answer
> 4 votes
The terminology used in the database area calls the relational algebra “procedural” to contrast it with the languages based on “calculus”, since an algebraic expression describes an ordered set of steps to find the result: simply execute the operations in the correct order to produce the result.

In contrast, in an expression of a calculus based language, the result is described through a property that holds on it, without specifying which operations should be applied to find it, neither the order in which they should be applied. So it “declares” the properties of the result, not a “procedure” to obtain it.

This terminology has no particular relations with other terminologies in the field of programming languages (like imperative, functional, applicative, etc.)

---
Tags: programming-languages, database-theory, relational-algebra
---


# Question
Title: Quotient of languages, regular quotient and their closedness
Left quotient is defined as below at this link:

> Left quotient of $L1$ by $L2$:
>
> $L1\backslash L2:= \\{u\in \Sigma^\*|vu\in L1$ for some $v\in L2 \\}$

Wikipedia defines it as follows:

> $L\_1\backslash L\_2=\\{w|\exists x((x\in L\_1)\wedge (xw\in L\_2))\\}$

**Q1.** I feel both definitions differ. Which one is correct?

Also first link says:

> It can be shown that the families of regular, context-free, and type-0 languages are closed under quotient (both left and right) by a regular language. The family of context-sensitive languages does not have this closure property.

whereas wikipedia says:

> The quotient of a regular language with any other language is regular.

**Q2.** I again feel both differ especially in case of regular quotient with CSL. Which one is correct?

# Answer
All sources agree on the definition of *right quotient*: $L\_1/L\_2$ is the set of words which can be extended by a word in $L\_2$ to become a word in $L\_1$. In other words, $w \in L\_1/L\_2$ if there exists $x \in L\_2$ such that $wx \in L\_1$.

If $L\_1$ is regular and $L\_2$ is *any* language then $L\_1/L\_2$ is regular.

For many classes of languages, if $L\_1$ belongs to the class and $L\_2$ is regular then $L\_1/L\_2$ also belongs to the class. Examples of such classes include context-free languages and r.e. languages, but not context-sensitive languages. This is definitely the case for languages closed under homomorphism, inverse homomorphism, and intersection with a regular languages. Context-sensitive languages are only closed under $\epsilon$-free homomorphism, which is not enough here.

The left quotient is defined similarly, but we extend the word on the left instead of on the right. The notation is $L\_1\backslash L\_2$, but authors vary on which part is played by which language. One possible convention (used by Wikipedia) is that we are interested in words which can be extended on the left by a word in $L\_1$ to become a word in $L\_2$. Another convention (used by your link) reverses the roles of $L\_1,L\_2$. The alternate notations $L\_1 L\_2^{-1}$ and $L\_2^{-1} L\_1$ mentioned in your link are unambiguous. Note how the Wikipedia notation makes a bit more sense here: $L\_2^{-1} L\_1 = L\_2 \backslash L\_1$ per the Wikipedia notation, but not per the notation in the link.
> 3 votes

---
Tags: formal-languages, closure-properties
---


# Question
Title: What does the term "top-most" mean in the context of formal grammars?
I was learning about disambiguating grammars. In particular I was learning about enforcing right associativity on the sum language here:

$$ \mathit{Sum} ::= 0 \mid 1 \mid \mathit{Sum} + \mathit{Sum} \mid ( \mathit{Sum} )$$

I think I understand the intuition that in a string like:

$$ 0+1+0 $$

we want the `1` to be an argument to the left plus, so we put some sort of wall so that the symbol `+` cannot be right next to the `1`. So something like this:

\begin{align} \mathit{Sum} &::= \mathit{Ntp} \mid \mathit{Ntp} + \mathit{Sum}\\ \mathit{Ntp} &::= 0 \mid 1 \mid ( \mathit{Sum} )\end{align}

From my understanding this always enforces to put a parenthesis on the left side of any sum. Thus, putting a wall literally using the symbol `(`.

However, what I don't understand is that the 2nd rule is supposed to mean:

> Not top-most plus.

But I don't understand what "top-most" is supposed to mean. What does that mean?

Also, can someone give me a clearer argument to why the above grammar is indeed left associative? I feel my argument is a little to hand wavy or unclear to really be convincing.

---

Cross posted:

# Answer
> 1 votes
In the context of context-free languages, "top-most" refers to the root of a parse tree. Your rules guarantee that a sum of the form $1+1+1$ is parsed as $1+(1+1)$ rather than the opposite, since the nonterminal Ntp ("not top-most") doesn't allow + to be the top-most operator (you should imagine a parse tree in which + labels the root).

Consider the following two parse trees: (generated using Syntax Tree Generator)

On the left, the left child of the root has + as the top-most operator.

On the right, the right child of the root has + as the top-most operator.

Your grammar only allows the second parse tree, since the left child of + must not have + as the top-most operator.

---
Tags: formal-grammars
---


title: default TCP Maximum Segment Size

text:
# Question
Title: default TCP Maximum Segment Size
Why default TCP Maximum Segment Size is 536? If found this line in TCP/IP by behrouz forouzan

# Answer
> 1 votes
The short answer is because of RFC 791 which reads "All hosts must be prepared to accept datagrams of up to 576 octets (whether they arrive whole or in fragments)."

If you take 20 octets for IP and 20 octets for TCP then you're left with 536 for MSS.

Now why is 576 chosen? Mostly likely the fact that machine at that time wasn't that powerful and some reasonable minimum number had to be agreed that would be supported across all of the devices regardless how low-fi they are.

---
Tags: network-flow, tcp
---


title: Coinduction in mathematical analysis?

text:
# Question
Title: Coinduction in mathematical analysis?
Coinduction is a logical principle that is somehow dual to induction. I'm struggling to understand it.

Are there any interesting examples of coinduction in analysis?

A few examples seem like they could be promising:

* the $p$-adic numbers can be represented as infinite streams in such a way that the arithmetic operations are well-behaved. Therefore coinduction seems quite promising here.
* continued fractions for real numbers. Unfortunately, the arithmetic operations are not well behaved in this representation; so it's unclear if it's of any use.
* Real numbers with signed digits. Coinduction here is complicated by the fact that representations of real numbers become non-unique. But the arithmetic operations are well-behaved. Seems promising.
* Power series.
* Continued powers or "infinite radicals".

# Answer
> 2 votes
The signed digit representation of Real Numbers seems like an efficient approach for:

* Defining the arithmetic operations and proving their algebraic properties. This was done already in a Master's thesis by Michael Herrmann.
* Proving Cantor's theorem on the uncountability of the real numbers.
* Developing the notions of continuous and uniformly continuous functions.
* Proving the Extreme Value Theorem in the form that every function on $\[0,1\]$ has a finite supremum.
* Developing the Riemann integral.

This has the nice property of being constructive.

As demonstrated by Michael Hermann, the operations listed above can be *defined* using colagebraic coinduction and then *reasoned about* using set-theoretic coinduction.

This also suggests the possibility of proving analogues of the above in $p$-adic analysis. Here, a purely coalgebraic approach might actually work.

It's possible that vast swathes of General Topology (over separable spaces) can be developed using coinduction over $\mathbb N^\mathbb N$. Here, continuous functions would be defined by corecursion over $\mathbb N ^ \mathbb N$ and then reasoned about using set-theoretic coinduction. This appears to be the approach taken in Frank'a Waaldijk's Natural Topology (I'm not sure if it uses coinduction though).

The caveat of all the above is that I've never *seen* a full development of the above. But the possibility certainly exists if anyone has the time or motivation.

---
Tags: mathematical-analysis, coinduction
---


# Question
Title: Minimum number of bits to represent negative number
> Minimum number of bits required to represent $(+32)\_{base10}$ and $(-32)\_{base10}$ in signed two's compliment form?

My attempt:

32 = 0100000 ( 1st zero - sign bit as positive)

So to represent +32 we need 7 bits

-32 = 1100000 (1st bit 1 - sign bit as negative)

So to represent -32 we need 7 bits

> But answer is given as 6 bits to store -32 and 7 bits to store +32(positve case i understood, negative in my opinion it should be 7 bits). His reason - one 1 bit enough to represent negative number. I am confused. Please clarify here

Also i have following Questions:-

> Can we say number of bits required to represent a negative number is strictly less than( or less than equal to) number of bits required to represent that corresponding positive number?
>
> how can we generalise minimum number of bits required to represent a given positive and negative number say +N and -N in signed magnitude representation, signed 1's complement notation and signed two's compliment notation.

# Answer
The representations of the numbers as 6-bit two's complement binaries are \begin{align} +32\_{10} &= 10\\,0000\_2\\ -32\_{10} &= \overline{10\\,0000}\_2 + 1\_2\\ &= 01\\,1111\_2 + 1\_2\\ &= 10\\,0000\_2 \end{align} which would give the same representation for both numbers. That means you cannot use 6-bits numbers to represent both values using two's complement.

For 7-bit binaries it works, however: \begin{align} +32\_{10} &= 010\\,0000\_2\\ -32\_{10} &= \overline{010\\,0000}\_2 + 1\_2\\ &= 101\\,1111\_2 + 1\_2\\ &= 110\\,0000\_2 \end{align} As you can see, the most significant bit represents the sign of the number.

---

Another perspective on your question: What is the biggest positive/smallest negative number you can store in an $n$-bit two's complement binary? Then the answer is $2^{(n-1)}-1$ for the biggest positive and $-2^{(n-1)}$ for the smallest negative number.

That means that a 6-bit binary can hold values $-32, \ldots, 31$ and a 7-bit binary values $-64, \ldots, 63$. The number $-32$ then fits into the range of 6-bit binaries, while $+32$ doesn't. You'd need one more bit for the latter.
> 1 votes

# Answer
There are 65 values x with -32 \<= x \<= +32. You cannot represent 65 values in 6 bits. Either you misread the question, or the answer 6 is wrong.
> 0 votes

---
Tags: arithmetic, digital-circuits, binary
---


# Question
Title: Constructing preorder traversal from postorder of a Binary Search Tree in O(n)
We are given postorder traversal of a Binary "SEARCH" Tree (in an array) and we want to find (print) its preorder traversal.

A very naive solution is to check from end until we find element less than root so we can find left and right subtree and call the function on them. This is $O(n^2)$. Another way is to generate the BST from its postorder and then generate the preorder from postorder. it is $O$$($$n log n$$)$ because for generating tree we need $O(n log n)$ and for preorder traversal we need $O(n)$ and $O(n + n log n ) = O(n logn)$.

I think we can do it better in $O(n)$ because there is a lot known about the nature of the binary search tree and this extra information must help somehow. but I don't know how to use information we know about BST and implement this problem in $O(n)$.

# Answer
> 1 votes
This can indeed be solved in $O(n)$ time. What you mentioned (checking value of root, calling recursively for left and right subtree) almost works, the issue is just that we don't know the size of the right subtree, so we cannot immediately recursively solve the left subtree as we don't know where it ends. But this is not an issue: Just recursively solve the right subtree first, then have that return the subtree's size.

The following C++ program should solve the problem in $O(n)$. Please note that while I tested a few inputs but there could be bugs, though the idea behind the algorithm works for sure.

```
#include <iostream>
#include <vector>
using namespace std;

// Finds preorder traversal of a subtree of a binary search tree given the postorder traversal
// res: Vector to write preorder traversal to
// postorder: Vector containing the postorder traversal
// j: Position in array to write last node in preorder traversal to
// hv: Maximum value of a node in this subtree
// lv: Minimum value of a node in this subtree
// b: Position where this subtree ends in the postorder traversal
// Returns size of the subtree called on
int preorder(int b, int lv, int hv, int j, const vector<int>& postorder, vector<int>& res) {
    if (b < 0 || postorder[b] < lv || postorder[b] > hv) return 0;
    int rs = preorder(b-1, postorder[b], hv, j, postorder, res); // Size of     right subtree
    int ls = preorder(b-1-rs, lv, postorder[b], j - rs, postorder, res); // Size of left subtree
    res[j - ls - rs] = postorder[b];
    return ls + rs + 1;
}

int main() {
    int n; // Size of the tree
    cin >> n;

    vector<int> po(n); // Postorder
    for (int i = 0; i < n; ++i) cin >> po[i];

    int lv = po[0]; // Minimum value in the tree
    int hv = po[0]; // Maximum value in the tree
    for (int i = 0; i < n; ++i) {
        lv = min(lv, po[i]);
        hv = max(hv, po[i]);
    }

    vector<int> res(n); // Preorder
    preorder(n-1, lv, hv, n-1, po, res);
    for (auto v : res) cout << v << ' ';
    cout << '\n';
}

```

This is clearly $O(n)$, since the function "preorder" gets called exactly once per node, and (outside recursive calls) does $O(1)$ work.

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


# Question
Title: Graph of size n with girth >2k and minimum degree more than n^1/k
I'm stuck at a proof about Graphs in the context of Graph Spanners. A Lemma says:
Let $G$ be a graph with $n$ vertices and $m$ edges. If $G$ has girth more than $2k$, then $m\leq n^{1+\frac{1}{k}}$.
The proof is made by contradiction where repeatedly any node from $G$ of degree at most $\lceil n^\frac{1}{k}\rceil$ and any edges incident to that node is removed, until there is no such node anymore. This step leads to a subgraph $G'$ of $G$ of minimum degree more than $\lceil n^\frac{1}{k}\rceil$.
The conclusion is that $G'$ must have girth at most $2k$ and therefore also $G$, which is a contradiction.
I don't understand the conclusion: Why must $G'$ have girth at most $2k$? Why is it not possible that $G$ has girth more than $2k$ and minimum degree more than $\lceil n^\frac{1}{k}\rceil$?

I don't really see an answer to this question, so I would be very grateful if someone can help me.

# Answer
Suppose that $G'$ has girth more than $2k$. Pick an arbitrary node $v$. The node $v$ has $N\_1 \> \lceil n^{1/k} \rceil$ neighbors. Each neighbor of $v$ has more than $\lceil n^{1/k} \rceil$ neighbors, and at least $\lceil n^{1/k} \rceil$ of them are different from $v$. The neighbors of different neighbors are all different, since otherwise $G'$ would have a 4-cycle. Denoting by $N\_2$ the number of nodes at distance 2 from $v$, we have $N\_2 \geq \lceil n^{1/k} \rceil N\_1$. Continuing this way, we have $N\_\ell \geq \lceil n^{1/k} \rceil N\_{\ell-1}$ for all $\ell \leq k$ (here you use the lower bound on the girth; details left to you). In total, we get $N\_k \> \lceil n^{1/k} \rceil^k \geq n$, which is impossible.
> 3 votes

---
Tags: graphs
---


# Question
Title: Is O((n^2)*log(n)) greater than O(n^(2.5))?
I know that $O(n^2\times \log(n))$ is greater than $O(n^2)$, but is $O(n^2\times \log(n))$ greater than $O(n^{2.5})$?

# Answer
In order to compare 2 complexities just calculate a limit of their ratios as below:

$\displaystyle\begin{align\*} \lim\_{n\to\infty}\frac{n^2log(n)}{n^2\sqrt{n}} &= \lim\_{n\to\infty}\frac{log(n)}{\sqrt{n}} = \lim\_{n\to\infty}\frac{log(\sqrt{n})^2}{\sqrt{n}} = \lim\_{n\to\infty}\frac{2log(\sqrt{n})}{\sqrt{n}} \\ &\underset{\left| k = \sqrt{n} \right|}{=} \ \ \lim\_{k\to\infty}\frac{2log{(k)}}{k} = 2\lim\_{k\to\infty}\frac{log{(k)}}{k} \\ &\leq 2\lim\_{k\to\infty}\frac{ln{(k)}}{k} \\ &\overset{\ast}{=} 2\lim\_{k\to\infty}\frac{(ln{(k))'}}{k'} = 2\lim\_{k\to\infty}\frac{\frac{1}{k}}{1} = 2\lim\_{k\to\infty}\frac{1}{k} \\ &= 0 \end{align\*}$

We use L'Hôpital's rule to simplify calculating a limit for $\frac{\ln(k)}{k}$ at \*.

As you can see, $O(n^2\times\log(n))$ is lower than the other.
> 16 votes

# Answer
$O(n^2 \times \log(n))$ is greater than $O(n^2)$ but it is smaller than $O(n^{2 + \epsilon})$ for any $\epsilon \> 0$, however small $\epsilon$ is (see here).

In particular, it is smaller than $O(n^{2.5})$. You're basically comparing the growth of $\log$ and square root.
> 12 votes

# Answer
As $n^{0.5}$ is always greater than $\log(n)$, $O(n^{2.5})= O(n^2 \times n^{0.5})$ is always bigger than $O(n^2 \times \log(n))$. Anyway, you should consider your real algorithm usage scenario to choose one which fits the best.
> 5 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: Minimizing a multiple output circuit with K-maps - and without
I'm currently working on learning to minimize a circuit which has multiple outputs using K-maps. My universities script seems rather unhelpful to me which left me in a spot where I have a very rough understanding of the matter without actually being able to pull it through.

I currently am supposed to first minimize the functions on their own and then compare that to minimizing them together.

The resulting functions are:

$Fa = (bc)+(bd)+(\neg acd)$

$Fb = (b\neg c\neg d) + (b\neg cd) + (bc\neg d)$

So now I think I am supposed to minimize them together. My approach is to mark the 1s in the maps that are unique to one function red and group them first.
After that, I look at the ones that are shared. I can now group these the same way in both maps. The groups bordered by yellow are the ones that are shared. So I now created the functions for these two.

$Fa = (bcd) + (\neg acd) + (b\neg cd) + (bc\neg d)$

$Fb = (b\neg c\neg d) + (b\neg cd) + (bc\neg d)$

Here I count that they use two unique AND gates for Fa, one unique AND gate in Fb, two unique AND gates across the two and then one OR gate for each of these two. So all in all, they use 7 gates. This is exactly the same as before I minimized them together, thought the assignment heavily implies that the amount of gates should go down.
I simply cannot figure out what I am doing wrong here.

Furthermore, they tell me to then do this without K-maps, which is a task that I don't even know how to begin working on.

# Answer
> 1 votes
Good job on $f\_a = \overline acd \lor bc \lor bd$.
With $f\_b$, I'd denote it as $b\overline d\lor b\overline cd$ \- you missed overlap with $\overline d$: $f\_b = b\overline c \lor b\overline d$.
I'd tally that as *and inputs*: 11 *complemented*: 3 *ands*: 5 *gates/ors*: 2

In the combined implementation, groups are still allowed to overlap: both blue ones can be twice as large, use one input less.
One can share either $bc\overline d$:
$f\_a = b\overline cd \lor \overline acd \lor bc$
$f\_b = b\overline cd \lor b\overline d$
or $b\overline cd$:
$f\_a = bc\overline d \lor \overline acd \lor bd$
$f\_b = bc\overline d \lor b\overline c$
*and inputs*: 10 *complemented*: 3 *ands*: 4 *gates/ors*: 2

---
Tags: digital-circuits, karnaugh-map
---


# Question
Title: How many decidable decision problems are there?
Is there a "intuitive" way of understanding how many possible decidable problems there are, given some formal language to describe them?

# Answer
> 15 votes
There are a countable infinity of decidable problems. There must be at least a countable infinity, because all of the languages $\\{a\\}$, $\\{aa\\}$, $\\{aaa\\}$, ... are decidable. There cannot be more than a countable infinity, because there are only that many Turing machines (each Turing machine can be encoded as a finite string).

There can be no formal language that describes them all without also describing some undecidable problems. This is because the set of decidable languages is not recursively enumerable, but any formal language would give a way to enumerate them. At least, assuming it was decidable whether a string was in the formal language or not. And, if you can't even decide whether a string was in your formal language, it wouldn't be any better as a description than, "The set of all languages decided by Turing machines."

# Answer
> 0 votes
Expanding a little bit the trivial case in which the "given language" is Turing complete: as said by David in his answer, if the "given formal language" can be represented with a string, then there are countably many programs (problems) ... the interesting questions is whether they are (all) decidable or not.

For example if you pick Presburger Arithmetic i.e. first order statements on natural numbers with addition and equality; then all "problems" (first order sentences) are decidable. For example

$\forall y .(y \neq 0) \to (\exists x . y = x + 1)$

"Intuitively" you can say that there countably many first order sentences ... but "intuitively" you cannot say "how many" (all?) of them are decidable (indeed the proof of decidability of Presburger arithmetic is quite complicated).

If the given formal language is a standard programming language in which you can only define a single variable (which can contain an arbitrarily large integer) then again all problems are decidable. But as soon as you allow 2 variables then you get a Turing complete language.

*In summary*: proving the decidability of a given formal language is not always a trivial task; if there are clear evidences that it is Turing complete then you "get owned" by the halting problem (or - equivalently - by the first Godel's incompleteness theorem) otherwise you can be near the border between decidability and undecidability and proving on which side you are can be very hard :-)

# Answer
> 0 votes
A language is a decision problem. $L$, a generic language, is a subset of $\Sigma^\*$ (where $\Sigma$ is the alphabet).

Decidable languages are by definition countable, as every Turing Machine has a finite description.

We can prove that there is no bijective mapping between the set of all turing machines to the set of all subsets of $\Sigma^\*$ (ie the set of all languages), and further, that because the set of all languages (ie the set of all subsets of $\Sigma^\*$) is uncountably infinite, there are vastly more undecidable problems than there are decidable problems.

This is a direct corollary of Cantor's Theorem

---
Tags: computability, decision-problem
---


title: Semantic, total and partial correctness

text:
# Question
Title: Semantic, total and partial correctness
I encountered the following question:

> 1. Provide a definition of the semantic correctness of algorithm $A$ with respect to pre-condition $\alpha$ and post-condition $\beta$. A well-presented precise and complete definition is expected.
> 2. Explain the difference between the total correctness and the partial correctness.

Can someone explain both of these to me or point me in the direction with good material on this topic? I somewhat understand the second question in the sense that partial correctness does not require/make the algorithm terminate and total correctness = partial correctness + termination, but that's it.

# Answer
The correctness of an algorithm is asserted when it is said that the algorithm is correct with respect to a specification, in this case, starting from the pre-condition $\alpha$ if the algorithm executes and land in states described by $\beta$ where the pre-condition is as weakest as possible and post-condition is as strongest as possible. The algorithm is said to be correct. Proof of Correctness can be proved using invariants. Refer this for more information about Hoare logic and program correctness.

A distinction is made between partial correctness, which requires that if an answer is returned it will be correct, and total correctness, which additionally requires that the algorithm terminates. Refer this for more info.

Hope this helps!
> 0 votes

---
Tags: correctness-proof
---


# Question
Title: Time Complexity: Why does $n^n$ grow faster than $n!$?
Seeing the title, you will probably like to give your explanation as

$n!=n\times (n-1)\times (n-2)\times (n-3)\times\cdots\times 1$

where as

$n^n$ = $n\times n \times n\times n \times\cdots\times n$ $\text{($n$-times)}$

but consider one thing: if we do $\log(n!)$ then it comes out to be $O(n\log n)$.

On the other hand, if we do $\log(n^n)$ it also comes out to be $O(n\log n)$. So, aren't they equal asymptotically?

# Answer
> 9 votes
The core source of your confusion is that you have assumed that the asymptotic behavior of functions is closed under taking $\log$, which is false. There are countless examples, take: $$f(n)=n^{100}, \quad g(n)=n$$ If you take their logarithm they become: $$\log f(n) = 100 \log n,\quad \log g(n) = \log n $$ So their logarithms are both linear in $\log n$, while it's obvious they do not have a similar growth rate. Another example can be: $$f(n)=\exp(2 n), \quad g(n)=\exp(n)$$ and their logarithms are: $$\log f(n) = 2n, \log g(n) = n$$ You can see that $f(n) = g(n)^2$ and it has faster growth rate, but both their logarithms are linear in $n$. The intuitive reason is that, when you compare $\log f(n)$ and $\log g(n)$, you are basically comparing their exponents. Showing that the exponents of two functions have a similar growth rate is not the same as showing that the functions have the same growth rate.

In case you are wondering, the reversed direction would actually hold most of the time: If $\log f(n)$ grows faster than $\log g(n)$, and $g(n)=\Omega(1)$, then $f(n)$ grows faster than $g(n)$, and the condition $g(n)=\Omega(1)$ prevents cases like $f(n) = \exp(1/n), g(n) = \exp(1/n^2)$.

# Answer
> -1 votes
The first part is right. But you have a wrong conclusion! If $g(n) = \Theta(f(n))$, you **cannot** say for $every$ function $h(n)$, $h(g(n)) = \Theta(h(f(n))$.

For the case, we know that $\log(n!) = \Theta(n\log(n))$, but you can not conclude that it is also true if we apply $h(n) = e^n$ over the functions. In your case, intuitively, the main difference in $\log$ cases and exponential cases is we sum limits in $\log$ cases and multiply limits in the exponential case!

---
Tags: time-complexity
---


# Question
Title: Reduction from Vertex Cover to Dominating Set
I am trying to reduce the vertex cover (decision) problem to the dominating set (decision) problem in order to prove that the latter is NP-hard. After some research online, I found that many articles use a reduction that transforms the input for the vertex cover problem to an input for the dominating set problem by creating a triangle for each edge. Here is one of such articles (See question 7 in the link).

The question that I would like to ask is, if we drop isolated vertices in the input to the dominating set problem, then, we could easily find a counterexample to the reduction - Let the input to the vertex cover problem be a graph containing $N$ isolated nodes and parameter $k=N$. Now, the input to the dominating set problem will clearly be an empty graph with the parameter $k=N$. Now, there is a vertex cover of size $N$. But it is not a dominating set of the transformed graph (i.e. the answer to the vertex cover problem is yes but the answer to the dominating set cover problem is no).

How could I fix the reduction? Could someone please advise me?

# Answer
> 1 votes
If I understand correctly you only have a problem when the graph $G = (V,E)$ of the vertex-cover instance has isolated vertices. In this case you can transform $G$ into a related graph $G' = (V \cup \\{x,y \\}, E')$ by adding a two new vertices $x$ and $y$ such that $x$ and $y$ are connected to each other by an edge, and there is an edge between $x$ and each other vertex in $V$. Formally: $E' = E \cup \\{ (x,v) \mid v \in V \cup \\{y\\}\\}$.

If $G$ admits a vertex-cover $C$ of size at most $k$, then $G'$ admits a vertex-cover of size at most $k+1$, namely $C \cup \\{ x \\}$.

If $G'$ admits a vertex-cover $C$ of size at most $k+1$, then $G$ admits a vertex-cover of size at most $k$. This can be easily seen by noticing that $C \setminus \\{ x, y\\}$ must cover all the edges in $E$, and that $(x,y) \in E'$ ensures that at least one of $x$ and $y$ is in $C$, i.e., $|C \setminus \\{ x, y\\}| = |C| - |C \cap \\{x,y\\}| \le |C| - 1 \le k$.

Since $G'$ has no isolated vertex, you can now safely transform it to the graph $H$ of the dominating-set instance (using the known reduction). In this way you show that $G$ has a vertex-cover of size at most $k$ $\iff$ $H$ has a dominating set of size at most $k+1$.

---
Tags: reductions, np-hard, correctness-proof, polynomial-time-reductions
---


# Question
Title: Proving that max flows of undirected graph and equivalent directed graph are equal
There is an undirected graph $G$. A graph $H$ is constructed by changing each edge $(a,b)$ in $G$ to a pair of directed edges $(a,b)$ and $(b,a)$. How to prove that the maximum flow in $H$ is equal to the maximum flow in $G$?

I don't really have any idea how to start it. I just know that I can use Ford-Fulkerson on $H$ and update the reverse edge such that $f(a,b)+f(b,a)=c(a,b)$ but that's it.

# Answer
If $f\_G$ is a valid flow for $G$, then there exists a valid flow $f\_H$ for $H$ such that $|f\_G| = |f\_H|$. This is true since there is always a flow $f'\_G$ for $G$ such that $|f'\_G| = |f\_G|$ and no edge is traversed in both directions in a flow decomposition of $f'\_G$. If some edge $(u,v)$ is traversed by $x$ units of flow from $u$ to $v$ and $y \le x$ units of flow from $v$ to $u$ then you could redefine the flow to only send $x-y$ units of flow from $u$ to $v$. If $(u,v)$ is used from $u$ to $v$ you can then define $f\_H(u,v) = f'\_G(u,v)$ and $f\_H(v,u)=0$. (If $(u,v)$ is unused then $f\_H(u,v) = f\_H(v,u) = 0$).

If $f\_H$ is a valid flow for $H$, then there exists a valid flow $f\_G$ for $G$ such that $|f\_H| = |f\_G|$. Notice that if $f\_H$ uses both $(u,v)$ and $(v,u)$ (assume w.l.o.g., that $f\_H(u,v) \ge f\_H(v,u)$) then the flow $f'\_H$ defined by $f'\_H(u,v) = f\_H(u,v) - f\_H(v,u)$, $f'\_H(v,u)=0$, and $f'\_H(x,y) = f\_H(x,y)$ for $(x,y) \not\in \\{ (u,v), (v,u) \\}$ is also a valid flow for $H$ and $|f'\_H| = |f\_H|$. This shows that you can define $f\_G(u,v) = f'\_H(u,v)$.
> 3 votes

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


# Question
Title: Difference between dynamic loading and dynamic linking in the OS
First of all, I saw many answers of this topic in Quora, Stackoverflow, and this site. But, I couldn't definitely understand the difference between dynamic loading and dynamic linking.

What I understood until now is this.

> **Dynamic loading** : system library or other routine is loaded during run-time and it is not supported by OS.
>
> **Dynamic linking** : system library or other routine is linked during run-time and it is supported by OS.

What I'm confusing is the behaviour of this two concepts. I know that loading occurs after linking like below image. (from Operating System concepts 9th edition, Chapter 8 figure 8.3)

Then, my question is that does dynamic loading is occured after dynamic linking? If I'm wrong, what is the exact difference between two concepts?

# Answer
Let me explain these terms in the simplest way possible. Now since both the terms have the word ***dynamic*** in them, both occur during execution.

**Dynamic Loading :** Suppose our program that is to be executed consist of various modules. Of course its not wise to load all the modules into **main memory** together at once(in some cases it might not be even possible because of limited main memory). So basically what we do here is we load the main module first and then during execution we load some other module **only when its required** and the execution cannot proceed further without loading it.

**Dynamic Linking :** Suppose our program has some functions whose definition is present in some **system library**. We do know the header file only consists of declarations of functions and not definitions. So during execution when the function gets called we load that system library into main memory and **link** the **function call** inside our program with the **function definition** inside system library.
> 2 votes

# Answer
Dynamic Loading https://www.youtube.com/watch?v=qfGql6sGlZg
Dynamic Linking https://www.youtube.com/watch?v=RKmAJMe3t9E

Assume the code of a program is consists of several source codes and All of these source codes are compiled. As a result of these compilations, there exist several modules per source codes. Then, Assume a linker is called to link those modules into an executable module. In dynamic loading, after the linker is called, only main module is loaded into memory. During execution, if main module needs another module which is already linked in executable module, then calling module calls relocatable linking loader to load the called module into apporiate location in the processes logical adress space.

In Dynamic Linking, When a module needs to be called, that module is loaded into memory and a link between the calling module and called module is established by the stub which is a piece of code that is linked in linking time of the program. Dynamic Linking mostly used with shared libraries which different users may use.
> 2 votes

# Answer
Dynamic loading is the process of loading the dependent library or routine on-demand or at some time at run-time after load-time (the time at which the main program executable is loaded). This is contrast to loading all dependencies at load-time together with the main program. The Windows loader for example supports both techniques. The loading process completes when the library has been successfully loaded into main memory.

When the program attempts to call an imported function for the first time, that library that contains that function may or may not have been loaded yet. Initially, the compiler places a temporary small function, called a stub, that gets called instead of the imported function. The stub calls into the OS. If the library is currently not loaded, it gets loaded (this step is called dynamic loading). Then, the stub is modified so that it calls the imported function directly the next time it gets called. This process is called dynamic linking. The component of the OS that performs both steps is called the dynamic linker or the dynamic linking loader.
> 0 votes

---
Tags: operating-systems, compilers
---


# Question
Title: Simple Uniform Hashing Assumption and worst-case complexity for hash tables
Is the Simple Uniform Hashing Assumption (SUHA) sufficient to show that the worst-case time complexity of hash table lookups is *O*(1)?

It says in the Wikipedia article that this assumption implies that the average length of a chain is $\alpha = n / m$, but...

* ...this is true even without this assumption, right? If the distribution is \[4, 0, 0, 0\] the average length is still 1.
* ...this is a probabilistic statement, which is of little use when discussing *worst case* complexity, right?

It seems to me like a different assumption would be needed. Something like:

> The difference between the largest and smallest bucket is bounded by a constant factor.

Maybe this is this implied by SUHA? If so, I don't see how.

# Answer
I think the answer is *no*, SUHA does *not* imply anything regarding worst-case time complexity.

The bottom line is that

* the hashing is (even though uniform) still viewed as random, and
* the keys are unknown.

Regardless of how small the probability is for all keys to hash to the same bucket, it's still a theoretical possibility, thus the theoretical worst-case is still *O*(*n*).

When discussing hash tables and complexity, I think this is mentioned briefly, regarded as irrelevant in practice and then the discussion moves on to expected run time complexity, and we're in *O*(1) land.

With the assumption mentioned in the question...

> The difference between the largest and smallest bucket is bounded by a constant factor.

...(which is strictly stronger than SUHA) it can indeed be shown that the worst-case run time complexity is *O*(1). This assumption implies that even the largest bucket is within a constant factor of the load factor limit. This in turn means all linked lists are bounded by a constant and we get *O*(1) as worst case.

This assumption however is somewhat unreasonable. While it's quite *probable* that it holds true for any descent hash function and non-pathological set of keys, how would one *guarantee* such property? One would have to push this assumption further down and make constraints on what keys are allowed to be stored in the hash table and so on. This is what makes it unreasonable in a sense.
> 1 votes

# Answer
Not only is SUHA insufficient to show that the largest bucket has size $O(\alpha)$, but if $m = n$, then there is a high probability that for any particular set of keys, the longest chain has length $\Theta(\lg n / \lg \lg n)$. There is a proof of this in CLRS and many proofs available in lecture notes.
> 1 votes

# Answer
Let $h:\[U\]\to\[m\]$ be a uniform hash function, and $x\_1,\dots,x\_n\in\[U\]$ be the elements currently stored in the hash table, and we want to look up the query $q\in\[U\]$. Finally let $X\_i$ be the indicator variable for the event that $x\_i$ collides with $q$: $$X\_i = \begin{cases}1 && h(x\_i)=h(q)\\0 &&h(x\_i)\ne h(q)\end{cases} \Rightarrow P(X\_i=1) = \frac{1}{m}$$ Then the time $T$ to loop up $q$ is equal to the number of elements that collide with it: $$T=\sum\_{i=1}^n X\_i$$ By linearity of expectation we have: $$\mathbb{E} \[T\] = \sum\_i\mathbb{E} X\_i = \frac{n}{m}=\alpha$$ And finally by Markov's inequality: $$ P(T\>t) \le \frac{\alpha}{t}$$ Now if we set $t:={\alpha}/{\delta}$, we will have: $$P(\text{look-up time}\ge \frac{\alpha}{\delta}) \le \delta$$ Think of $\delta$ as the failure rate. So for $\delta=0.1$, the query time is bounded by $10\alpha$ with probability $0.9$. If you strengthen the assumption about $h$ to a $k$-wise independent hash, the failure rate rouhgly drops to $P(\text{fail})\approx\delta^k$ and so you can have a much better complexity/failure-rate trade-off.

Now, a more conservative analysis is, what is the length of the longest chain in your table? In this case, we can define indicator variables $X\_{i,j}$ for $i,j\in\[n\]$, that indicate the event that $x\_i$ and $x\_j$ collide. Clearly, $P(X\_{i,j})=1/m$. Then the expected total number of collisions $S$ is: $$\mathbb{E} S = \sum\_{i,j\le n} \mathbb{E} X\_{i,j} = \binom{n}{2}\frac{1}{m}$$ If the maximum chain length is $\ell$, there is $\binom{\ell}{2}$ pairs of elements in that chain that collide with each other, implying $S\ge \binom{\ell}{2}$. We have: $$P(\text{max chain length}\ge \ell) \le P\left(S\ge \binom{\ell}{2}\right) \le\frac{ \mathbb{E} S} { \binom{\ell}{2}}\approx (n^2/m\ell^2) $$ If you set $\ell:=n^2/m\delta$ the probablistic bound is: $$P(\text{max chain length}\ge \ell) \le \delta \qquad \text{ for } \ell = \frac{n}{\delta \sqrt{m}}$$ So if $m\approx n$, your maximum length grows like $\ell\approx \sqrt{n}/\delta$ with $1-\delta$ probability. This is because the simple uniform hash assumption is really weak. The more independence you assume, the better the guarantee. For a universally uniform (meaning completely iid) hash function, you will get a logarithmic maximum chain $log(n)$ for $m\approx n$.
> 1 votes

---
Tags: hash, hash-tables, hashing
---


# Question
Title: Is it decidable "Given a TM M, whether M ever writes a non blank symbol when started on the empty tape."
I came across below problem in this pdf:

> Given a TM M, whether M ever writes a non blank symbol when started on the empty tape.

Solution given is as follows:

> Let the machine only writes blank symbol. Then its number of configurations in the com computation on w is q × 2, where q is the number of states of M; the factor 2 is for the choices re. the direction of heads movement; there is no factor for the written symbol because that is always blank. So the problem is decidable, decided by the following machine: input (M,w), run M on w for q × 2 steps; if it M ever writes a non blank symbol, stop with yes answer; if M never writes a non blank symbol, stop with no answer

**Doubts:**

**Q1.** How be sure all q x 2 configurations will happen while running q x 2 steps on w? Some configuration may get repeated in q x 2 steps.

**Q2.** Question says "when started on the empty tape", but the answer tried to simulate TM on non empty string w. How does it makes sense?

# Answer
> 1 votes
**Q1:** A state can get repeated. The point is that if a state gets repeated and no non-empty symbol has even been written, then you known the that the Turing machine will never halt as it is necessarily stuck cycling through some of the states encountered so far. Since none of the states of the cycle caused the TM to write a non-blank symbol, the TM will never write a non-blank symbol.

After $2q$ steps, either a non-blank symbol has been written, and you can answer "yes", or all the written symbols were blank and (at least) one state must have been encountered two or more times, meaning that you can answer "no".

**Q2:** My guess is that $w$ is defined somewhere to be the empty string. If the TM can be started with some arbitrary string $w$, then a variation of the above solution still works. Suppose that the head of the TM starts at the beginning of $w$. The number of states increases by a factor of at most $1+|w|$ in order to take into account all possible states of the tape (if only blank symbols are written, then the tape always contains one of the $1+|w|$ suffixes of $w$). If the head can start anywhere then this factor will be at most $1+|w|^2$.

---
Tags: formal-languages, turing-machines, undecidability, semi-decidability
---


# Question
Title: An iterative algorithm for finding the partitions of a set into subsets of a fixed size
The question is whether someone could provide an algorithm for finding all the partitions of a set S into subsets of fixed size (assume the fixed size is 2, to make things simpler, in which case the cardinality of S is even) which is iterative and not recursive and which runs in time proportional to the output (and produces no duplicates). The algorithm, being deterministic, will produce the output in some sorted way. Ideally, it is possible to give a partition as input and generate all the partitions that follow the given one in the ordering in which the algorithm outputs the partitions. Please advise if the question is not clear.

# Answer
> 2 votes
Let's first describe a notation for our partitions. Let $p\_i$ represent the $i$th partition which is made up of $|S|/2$ disjoint pairs of $S$. We can represent $p\_i$ as $$p\_i=b\_{i,1},b\_{i,2},...b\_{i,S/2}$$

In order to ensure uniqueness of partitions, we will enforce a sorting on each partition. For each partition $p\_i$, each pair in $p\_i$ must be sorted. The pairs must also be sorted among themselves i.e.

$$b\_{i,j}\[0\] \< b\_{i,j}\[1\] \\;\\;\text{and} \\;\\; b\_{i,j} \< b\_{i,j+1} \\;\\;\forall j$$

The ordering of the partitions is then defined similarly to other lexicographic orderings.

$$p\_i \> p\_{k} \iff \exists j \\;\\; \text{s.t.}\\;\\; \forall j'\in\[1, j) \\;\\; b\_{i,j}=b\_{k,j} \land b\_{i,j'}\>b\_{k,j'}$$

Now, given some partition $p\_i$, we can return the next lexicographically larger partition $p\_{i+1}$ by using logic similar to the algorithm for obtaining the next permutation of a set of elements. Let us first describe a function $swap(p\_i, j)$ and $sort(p\_i, j)$.

* $swap(p\_i) \rightarrow \\;\\;$ Find the largest $j$ such that there exists a larger element in any of the pairs $b\_{i,j'}$ for $j'\>j$. Let $x$ be the smallest such element i.e. $x = \min(\\{x'\in b\_{i,j'} | j' \> j \land x' \> b\_{i,j}\[1\]\\}).$

Then swap $b\_{i,j}\[1\]$ and $x$ and return $j$.

* $sort(p\_i, j) \rightarrow \\;\\;$ Sort all of the elements from $b\_{i,j}\[0\]$ to $b\_{i,S/2}\[1\]$ i.e. after calling $sort(p\_i, j)$, the sequence $b\_{i,j}\[0\], b\_{i,j}\[1\], ..., b\_{i,S/2}\[0\],b\_{i,S/2}\[1\]$ should be non-decreasing.

Now, we claim that given a partition $p\_i$, we can obtain $p\_{i+1}$ by running $sort(p\_i, swap(p\_i)+1)$. The reasoning is identical to that of the "next permutation algorithm" - We must find the largest $j$ such that we can swap $b\_{i,j}\[1\]$ with the next largest value while not changing anything in $b\_{i,j'}$ for $j' \< j$. After the swap, we must sort the remaining elements to ensure that it is the smallest increase possible. If the remaining elements were not sorted, then by sorting them we would obtain a partition greater than $p\_i$ but less than $p\_{i+1}$, which is a contradiction.

---
Tags: algorithms, combinatorics
---


# Question
Title: $O(k)$ Algorithm to find the first $k$ pairs of Magic numbers $a$ and $b$ such that $\sum_{i=1}^{a-1} i = \sum_{k=a+1}^b k $, with restrictions
Provide an $O(k)$ algorithm to find $k$\- magic pairs of positive integers a and b of type signed int where a magic pair is defined as $\sum\_{i=1}^{a-1} i = \sum\_{k=a+1}^b k $. You can't use the summation formula $\frac{N \cdot (N+1)}{2}$ as it would result in an overflow. Even you can't run sums such as sum1 and sum2, it's still going to overflow.

Example: (6,8) (35,49) (204,288) are the first three Magic Pairs.
**P.C**: This was our recent examination question, I am curious to know the algorithm.

# Answer
> 2 votes
There are different ways you can use to solve that problem.

One simple but inefficient solution is just that of just computing the two sums in parallel while only keeping track of **the difference** between their partial sums. I.e., if you added the first $x$ terms of the first sum and first $y$ terms of the second sum, then you'll only remember $x$, $y$, and $\Delta = \sum\_{i=1}^x i - \sum\_{k=a+1}^{a+1+y} k$. If $\Delta$ is non-positive, then consider the next term of the first sum (i.e., increment $x$ by one and add $x$ to $\Delta$). If $\Delta$ is positive, then consider the next term of the second sum (i.e., increment $y$ by one and subtract $a+1+y$ from $\Delta$). In this way $|\Delta|$ will never exceed $\max\\{a,b\\}$.

---

Another more efficient solution is as follows. Using the summation formula you can write: $ \sum\_{i=1}^{a-1} i = \frac{a(a-1)}{2} = \frac{b(b+1)}{2} - \frac{a(a+1)}{2} = \sum\_{k=a+1}^{b} k$, and some simplifications lead to: $2a^2 = b(b+1)$.

This means that, once you fix $b$, you can find the corresponding value of $a$ as follows: $$ a= \frac{1}{\sqrt{2}} \cdot \sqrt{b} \cdot \sqrt{b+1}. $$

Notice that $\sqrt{b} \cdot \sqrt{b+1}$ must always be greater than $b$ and smaller than $b+1$, meaning that $\frac{b}{\sqrt{2}} \< a \< \frac{b}{\sqrt{2}} + \frac{1}{\sqrt{2}}$ and, since $\frac{1}{\sqrt{2}} \< 1$, there is at most one integer in that interval, namely $ 1+ \left\lfloor \frac{b}{\sqrt{2}} \right\rfloor = 1+ \left\lfloor \frac{\sqrt{2} b}{2} \right\rfloor $.

---
Tags: algorithms, discrete-mathematics
---


# Question
Title: If A is polynomial time reducible to B and B is in NP, then A is in NP
*If $A\leq\_p B$ and $B$ is in $NP$, is it true that $A$ is in $NP$*?

What about : *"if $A\leq\_p B$ and $B$ is in $coNP$, then $A$ is in $coNP$"*?

Thanks in advance.

*I think both hold. If $B$ is in $NP$, then the yes-instances of $B$ can be verified in polynomial time. If $A \leq\_p B$, I can "translate" an instance of $A$ to a instance of $B$. Then I can use the verification algorithm for $B$ to check the yes-instances of $A$. The same should be valid for the second affirmation. I'm not sure though.*

# Answer
I think both hold too.

Co-NP version:some Problem A reduce to B,

if B is co-NP,$\overline{B}$ is in NP,and no-instance of B has some verify way and certificate bit. and A's no-instance can use it too.

So this A is complement of NP problem $\overline{A}$. this means complexity class of A is co-NP.
> 2 votes

---
Tags: complexity-theory
---