# Question
Title: Is polynomial over x with real roots decidable?
Today while I'm looking at definition of Algorithm from Sipser's textbook, he defined the following language:

$$D\_1 = \\{ p \mid\ p\text{ is polynomial over }x\text{ with integral roots}\\}$$.

This language is decidable since we can bound the integral roots between two values and we can try all possible values between these two numbers.

Now, I'm thinking about a the following language:

$$D\_{1}^\* = \\{ p \mid\ p\text{ is polynomial over }x\text{ with }\mathbf{real}\text{ roots}\\}$$

Is this language $D\_{1}^\*$ decidable? I don't think so since we have an infinite number of solutions between any two numbers in real numbers. Is my argument correct?

# Answer
Maybe I should summarize what I was saying in the comments.

Yes, the problem should be formulated precisely in order to give an answer.

**About the cases in which the answer is NO:**

For those formulations in which the answer is NO it is usually for a trivial reason. For example, one case that is mildly interesting is if we are considering the polynomials with coefficients that are computable numbers. These are numbers for which there is an algorithm such that for any given precision it terminates and gives you the digits of the number up to that precision. So, the input of $D\_1^\*$ in that case, would be a finite collection of such algorithms, one for each coefficient. Well, in this case $D\_1^\*$ cannot be decided, even for a constant polynomial. This is just because we cannot tell if that constant is zero or not.

**The context in Sipser's book:**

Now, I looked at the book by Sipser. They mention $D\_1$ in the context of the Hilbert's tenth problem, which concerns polynomials (in several variables) with integer coefficients. In this context and many others you can indeed decide $D\_1^\*$.

**The interesting part:**

If the coefficients are such that we can (algorithmically) perform the following operations:

* sum, subtraction, multiplication, division,
* test if positive, test if negative, and test if zero.

Then we can decide if a polynomial has a real root.

For example, we can consider $D\_1^\*$ as a problem about polynomials with integer coefficients, or rational numbers, or constructible numbers, or algebraic numbers, or perhaps consider the problem with arbitrary real numbers but in a Blum-Shub-Smale machine instead of a Turing machine. As long as we can do the six basic operations above, we should be okay.

One way to decide could be using Sturm's theorem. Sturm's theorem says that the number of real roots of a square free polynomial with real coefficients in an interval $(a,b\]$ is equal to the difference of the number of changes of sign at $a$ and the number of changes of sign at $b$ of the values of a Sturm sequence. See in the link above.

If the polynomial input $p$ has complex coefficients we can just work with the $\gcd$ of its real and imaginary parts. If the polynomial is not square-free, then we divide it by the $\gcd(p,p')$ to make it square-free. These transformations don't preserve the answer. Remember that one can compute $\gcd$ using using the Euclidean algorithm. So, we only need the arithmetic operations mentioned above.

One way to construct a Sturm sequences is the following: The first term is $p$, the second term is $p'$, the derivative of $p$. If $q\_i,q\_{i+1}$ are two consecutive terms of the sequence constructed so far, then the next term $q\_{i+2}$ is equal to the remainder of $q\_{i}$ divided by $q\_{i+1}$ and with the sign switched. This procedure is always finite since remainders always have smaller and smaller degrees.
> 4 votes

# Answer
You have said what roots you care about, but not what the coefficients of the polynomial might be. We have various options here:

1. We could use integer coefficients. Then it is decidable whether there are real roots or not. We don't go and do an exhaustive search over the reals for this, but instead essentially exploit that an integer polynomial can't get arbitrarily close to $0$ without reaching it.
2. We could use rational coefficients. It is still decidable, this case reduces to the one above by multiplying with some common multiple of the denominators.
3. We could use algebraic numbers. Here the coding becomes a bit tricky - we code algebraic numbers by giving their characteristic polynomial plus a rational interval in which the desired number is the only root of the polynomial. It is still decidable whether a polynomial has a zero, this can be deduced by an appeal to the theory of real closed fields being decidable.
4. We could use real number coefficients. We can no longer use finite words to code our inputs, but a Turing machine can process infinite sequences just fine. However, the real numbers (and subsequently the space of polynomials with real coefficients) is connected, and as a consequence has no non-trivial decidable subsets.
> 1 votes

# Answer
Yes, but to formalize it you might need to do a bit more work. First, what is the encoding of a polynomial? This is a tricky thing: since we can't have all polynomials representations available to us, since we can't encode all real numbers. This will mean that the decidability of this language is somewhat not interesting, since it comes from the impossibility of representation as strings rather than the actual language and its properties.

Moreover, I would argue it does not even make sense to ask this question when condsidering all reals, because it is impossible to represent as a language, while decidability and other similar definitions all talk about languages.

**But**, if you would restrict yourself to some finite representation of polynomials, you might not cover all real polynomials, but you can be not too far away from it. For example, you can represent all rational polynomials, and because the rationals are dense in the real line, then we would get a "close enough" representation. Defining like that would make the question more tangible, and the undecidability could be proven from *more* interesting properties than just that its impossible to represent.
> 0 votes

---
Tags: decision-problem
---


# Question
Title: What is the generated grammar for this language?
I want to construct a regular grammar that generates words that contain both "ab" and "bc" as subwords with the alphabet of the terminal symbols {a,b,c}

My solution so far is

**G=(Vn={S,X,Y},Vt={a,b,c},S,F={ S-\> aS | bS | cS | abX | cbX, X-\> aX | bX | cX | ε})**

# Answer
> 0 votes
Your solution so far is incorrect. According to your solution, we have the derivation

S -\> abX -\> ab

which does not contain bc as a substring.

Your solution also has a non-terminal Y, but does not appear in any production rules.

A correct grammar follows, with start symbol $S$:

$S \to aS$
$S \to bS$
$S \to cS$
$S \to abcA$
$S \to abX$
$S \to bcY$

$A \to aA$
$A \to bA$
$A \to cA$
$A \to \epsilon$

$X \to aX$
$X \to bX$
$X \to cX$
$X \to bcA$

$Y \to aY$
$Y \to bY$
$Y \to cY$
$Y \to abA$

---
Tags: complexity-theory
---


# Question
Title: Regarding Backus' Commentary on von Neumann-style Programming
in John Backus' 1978 FP paper "Can Programming Be Liberated from the von Neumann Style" he says

> To help assemble the overall result from single words \[von Neumann ie. conventional mutation-based\] languages provide some primitive combining forms in the statement world--the for, while,and if-then-else statements--but the split between the two worlds \[ie. between the expression-only and statement-only, as I understand him\] prevents the combining forms in either world from attaining the full power they can achieve in an undivided world.

He shows the expressiveness of functional programming, that's what the paper is about, but he implies there's a similar expressiveness that can be got from the statements-only part, per the above quote. However I don't know what he means by this; he gives no examples.

The only language that appears ruthlessly statement-y that I can think of is (pure) prolog (eg. see https://en.wikipedia.org/wiki/Prolog#Quicksort, there's no expressions as such only statements giving relationships) and it's not statements so much as the backtracking that gives it the power.

So what did Backus mean by this? What example languages are there that are statement only (but without backtracking)?

Edit: belated link to orginal paper https://dl.acm.org/doi/10.1145/359576.359579 for interest.

(The question has nothing to do with BNF form. Also, if someone can edit the title to better summarise the long quote, please do Edit: that's much better, thanks!)

# Answer
> 4 votes
Reading the quote literally without the interpolated interpretation, I think what Backus is saying is that a powerful language is one which makes no distinction between expressions and statements.

That is, where all statements are also expressions, like a functional language.

I don't think Backus was claiming that an "all statement" language - the meaning of which is not entirely clear in this context - would be powerful or even feasible. Rather, he is claiming that the existence of certain statements that cannot be analysed as expressions, is a defect in language design.

# Answer
> 0 votes
Backus says in that quote that splitting statements from expressions makes the “combining forms” (such as **if**-**then**-**else**) less powerful, because they can only be applied to statements, but not to expressions. He wants to see a language all of whose elements may be combined in the same ways.

That quote does not say that a language consisting only of statements could be more powerful, nor yet that the statement part of a von Neumann language on its own could be. What he actually says is that in an undivided world (without the distinction between expressions and statements) combining forms can be more powerful.

Since he is not talking of declarative languages such as Prolog, your follow-up question about languages without backtracking is not relevant.

---
Tags: programming-languages, functional-programming, language-design
---


# Question
Title: Single-source shortest path problem with diameter
> Given that a graph G has only positive integer weights and its diameter D which is the greatest of the shortest paths among all pairs of vertices in G. For a single-source shortest path problem and design an algorithm runs in O(V+E+D) time.

As we know, in a single-source shortest path problem, we could use the Dijkstra Algorithm and it's running time is $O((V+E)log V)$ using a min-heap. So we can explore the minimum known distance. But the bottleneck is to insert and delete a min-heap structure.

With the information, how to reduce the running time to $O(V+E+D)$?

\**Update \**

From https://stackoverflow.com/questions/66570124/single-source-shortest-path-in-a-graph-with-positive-weights-and-diameter-d

> We continually increment i until we find some i such that Arr\[i\] is not empty.

This tells where does the $O(D)$ come from. But what I don't understand is why inserting and deleting take a constant amount of time if min-heap is still using. Or is it another data structure? Many thanks

# Answer
Instead of a min-heap use an array of $D +2$ lists indexed from 0 to $D+1$. The $i$th list contain vertices whose distance to the source equals $i$ except for the last one which contains vertices with unbounded distance.

Iterate over this array from $0$ to $D$ and for each list, while not empty choose the head of the list as the vertex whose incident edges are to be relaxed in this iteration (the vertex with min distance to the source) and remove this element from this list.

To ensure updates add an array of $n$ pointers such that each vertex points to its occurance in the lists .

It is easy to see that updates run in constant time, hence we get $O(m)$ for updates over all edges. Since we iterate over empty lists and each vertex only once in the array we have amortized running time $O(n+m)$ for iterations.
> 1 votes

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


title: Two-color hitting set

text:
# Question
Title: Two-color hitting set
Let $n,m$ be a positive integer with $m\ge 2n$. In the set $M=\\{1,2,\dots,m\\}$, some elements are black and others are white. Given $2n$ nonempty subsets of $M$, the task is to determine whether there exists a subset $T\subseteq M$ consisting of $n$ black and $n$ white elements such that each of the $2n$ subsets has a nonempty intersection with $T$. Can this be done in polynomial time?

Without the color constraint, this is very similar to the hitting set problem. Choosing a subset $T$ of size $2n$ without the color constraint is easy, by choosing one representative from each of the $2n$ subsets and, if the union of these representatives has size less than $2n$, fill in with arbitrary remaining elements of $M$. But having $n$ black and $n$ white elements is not always possible, for instance if there are not enough elements of one color.

# Answer
> 4 votes
> Can this be done in polynomial time?

No, it cannot (unless P equals NP, of course).

Consider the case where all the $2n$ sets only contain elements that are colored (say) black. Finding a "white-black hitting set" with $n$ pairs is now exactly the same as finding a regular hitting set with n elements. A reduction from Hitting Set

> Find a set of at most $k$ elements that hits all sets in the collection $\mathcal{C}$, where $\mathcal{C} = r$

to your specific scenario

> Find a set of $n$ pairs of white and black elements that hits all sets in the collection $\mathcal{C}$, where $|\mathcal{C}| = 2n$

follows easily. The only extra thing to take care of is if $2k \< r$ (just add $r-2k$ black elements to $M$ and make each one a singleton set, now $n = r-k$), or if $2k \> r$ (just take some arbitrary set $C\in \mathcal{C}$, add $2k-r$ extra elements to $M$ and, for each one make a set containing the union of it and $C$).

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


title: Constructing a context-free grammar

text:
# Question
Title: Constructing a context-free grammar
I want to design a *context-free grammar* that generates words that either both start and end with $c$, or contain the same amount of $a$-s and $b$-s. Here is what I have. The nonterminals are $S,X,Y$, the terminals are $a,b,c$, the start symbol is $S$, and the productions are

\begin{align} &S \to aYS \mid cXc \mid bXS \mid cYc \mid \varepsilon \\ &X \to a \mid bXX \\ &Y \to b \mid aYY \\ \end{align}

# Answer
> 5 votes
Your grammar doesn't seem to generate $caac$. Indeed, in order to generate this work, a simple case analysis shows that the derivation must start $$ S \to cYc \to caYYc, $$ at which point it is clear that we cannot generate $caac$.

I assume you know how to generate the language $c\Sigma^\*c$, as well as the language of all words with an equal number of $a$-s and $b$-s. Instead of combining them in a complicated way, write grammars for both, and then join them together using a rule of the sort $S \to S\_1 \cup S\_2$.

---
Tags: formal-languages, context-free, formal-grammars
---


# Question
Title: Binary exponentiation of matrix - complexity
I want to calculate complexity for binary exponentiation of matrix of size $k$. Let's say that I'm using the simplest approach to multiply matrices (so with three `for` loops). The complexity of this operation would be $O(n^3)$. Now, the powering of matrix. Pseudo code (n is the power, A matrix):

```
power(n, A)
 if n == 0
  return 1
 else
   res = power(n/2, A)
   if n%2 == 0
     return res * res
   else
     return res * res * A

```

If I write the equation: $$T(n)=T(n/2) + O(k^3)$$ where $T(n)$ is the complexity, is it correct to think of cost to be $O(k^3)$? Then we sum $$\sum\_{i=0}^{\log\_2n}O(k^3) = O(k^3\log\_2n)$$ and for us $k=27$ is constant. Hence $T(n)=O(\log\_2n)$

# Answer
> 2 votes
The solution of the recurrence $$ T(n) = T(\lfloor n/2 \rfloor) + O(1) $$ (this is the correct form of your recurrence) is $T(n) = O(\log n)$. If you want to be more accurate, the solution of the recurrence $$ T(n) = T(\lfloor n/2 \rfloor) + C $$ is (for $n \geq 1$) $$ T(n) = C\lfloor \log\_2 n \rfloor + T(1). $$ In your case $C$ is not really constant, but rather depends on the parity of $n$. Accordingly, we can consider the recurrence $$ T(n) = T(\lfloor n/2 \rfloor) + C\_{n \bmod 2}, $$ whose solution is $$ T(n) = C\_1 \\#\_1(\mathrm{bin}(n)) + C\_0 \\#\_0(\mathrm{bin}(n)) + T(0); $$ here $\mathrm{bin}(n)$ is the binary representation of $n$, and $\\#\_0,\\#\_1$ is the number of $0$-s and $1$-s, respectively.

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


# Question
Title: In the PCP, can we remove all dominos with the same top and bottom strings and still get a match?
Suppose we have an instance P of the PCP, and there exists a match for it. I am wondering if we remove all dominos that has the same string on the top and bottom, would there still be a match?

My intuition is yes, there would still be a match, but i don't know how to justify.

Can someone please give me some hints or give a counterexample?

# Answer
> 1 votes
Intuitively this seems like it would be true at first, but it's because we think too literally about the domino example. Remember in the PCP the strings on the top and bottom of the domino are not necessarily the same length (i.e, the dominos are not necessarily rectangular) Consider the following example \begin{align\*} P=\left\\{\left(\begin{array}\[ccc\] \\ 1 & & \\ 1 & 2 & 3 \\ \end{array} \right), \left(\begin{array}\[c\] \\ 2 \\ 2 \\ \end{array} \right), \left(\begin{array}\[cc\] \\ 3 & 2 \\ 4 & \\ \end{array} \right), \left(\begin{array}\[cc\] \\ 4 & 4 \\ 4 & \\ \end{array} \right) \right\\} \end{align\*} Here notice there is a match by placing each of the dominos exactly once, and in the order they appear above. On the other had let's try another version. \begin{align\*} P'=\left\\{\left(\begin{array}\[ccc\] \\ 1 & & \\ 1 & 2 & 3 \\ \end{array} \right), \left(\begin{array}\[cc\] \\ 3 & 2 \\ 4 & \\ \end{array} \right), \left(\begin{array}\[cc\] \\ 4 & 4 \\ 4 & \\ \end{array} \right) \right\\} \end{align\*} Notice $P'$ was obtained from $P$ by removing $\left(\begin{array}\[c\] \\ 2 \\ 2 \\ \end{array} \right)$, which has the same string on top and bottom.

If there were a match in $P'$ it must start with $\left(\begin{array}\[cc\] \\ 4 & 4 \\ 4 & \\ \end{array} \right)$ since that is the only time starting and ending with the same letter that can be added to (there is no tile starting with $2$ on top to place after $\left(\begin{array}\[ccc\] \\ 1 & & \\ 1 & 2 & 3 \\ \end{array} \right)$. This can be followed by either another $\left(\begin{array}\[cc\] \\ 4 & 4 \\ 4 & \\ \end{array} \right)$, or $\left(\begin{array}\[cc\] \\ 3 & 2 \\ 4 & \\ \end{array} \right)$. The first is not helpful, and the second places the substring $32$ on the top, which can never be formed on the bottom. So $P'$ does not have a match.

---
Tags: computability
---


# Question
Title: Scheduling algorithm for a student's study times given assignments, expected time, due dates, and class times
I would like to create an algorithm that advises a student when they should work on certain assignments given the expected time each assignment will take, and the due date of each assignment.

Say that for a students' weekly schedule, there are class times and events that must be attended. With the remaining time slots in the week, how can I assign times to work on each assignment so that the recommended assignment time is fulfilled before the due date.

This is very similar to single-machine scheduling problems, and usually a greedy algorithm of closest-due-date-first would work, but I want to implement constraints based on human factors. For example: don't work on one assignment for more than 2 hours in a row, don't schedule a study time right after a class, etc.

How would I go about including these human factor constraints within my algorithm?

# Answer
A pragmatic solution might be to use methods from operations research, e.g., formulate this as an integer linear program or an instance of SAT, and use an off-the-shelf solver. It's hard to say exactly what the best solution might be without knowing the specific constraints, but these approaches will be the most flexible in accommodating a wide range of possible constraints.
> 1 votes

---
Tags: algorithms, optimization, greedy-algorithms, scheduling, process-scheduling
---


# Question
Title: How to find the reverse of a binary string with simple binary operators?
I was wondering is it possible to create a simple circuit that detects if an input (a binary string) is a palindrome?

So my approach is to feed the input to a circuit that reverses the input, ie if the input is 0111010, I need the output to be 0101110. Is this possible to achieve with only, and/or/xor/not and these simple operators in a generic way (on paper, not looking to implement a circuit with a predefined number of bits)?

Once I have this reversed output, I can use it with an "and" gate to compare to the original input and see if they match, but I'm stuck at the first part.

I appreciate your suggestions Thanks in advance

# Answer
Yes, absolutely. Every boolean function can be implemented by a circuit. In this case, it suffices to XOR bits 1 and $n$; bits 2 and $n-1$; and so on; and then take the NOR of all of the outputs of these XOR gates.
> 1 votes

---
Tags: circuits, boolean-algebra
---


# Question
Title: Maximum weight perfect matching in general graphs
Let $G(V,E)$ be a graph (not necessarily bipartite), where edge $e \in E$ has weight $w\_e$ (non-negative real). Then one can write the LP relaxation for maximum weight perfect matching as follows $$ \text{maximize}~~\sum\_{e\in E} w\_e x\_e \\ \text{subject to}~~\sum\_{e\in E: v\in e}x\_e=1\text{ for all }v\in V \\ 0\le x\_{e}\le 1\text{ for }e\in E. $$ In the corresponding Integer Program $x\_e$ is a binary variable s.t. $$ x\_e = \begin{cases} 1 \text{ if } e \text{ is in the perfect matching}\\ 0 \text{ otherwise} \end{cases} $$ I am unable to come up with an example where given $G$ has a perfect matching, the LP does not have an all integral optimal solution $x\_e^{\text{\*}}$. I tried taking small examples with odd length cycles, though there was a fractional optimal for the LP, there was an all integral optimal as well (in the examples I took).
I am aware that for bipartite graphs if the LP is feasible, then there always exists an all integral optimal for the LP. Does it hold for general graphs as well? If not I would appreciate hints so I can come up with such an example.

# Answer
> 2 votes
Consider the graph consisting of two triangles $123,456$ connected by an edge $34$. The graph has a unique perfect matching $12,34,56$. Give the edges of the triangles weight $1$, and the edge $34$ weight $\epsilon$. The maximum weight perfect matching has weight $2+\epsilon$. Conversely, the fractional matching giving a weight of $1/2$ to each edge of each triangle has weight $3$.

# Answer
> 3 votes
AB, CD, EF is the unique perfect matching

Assigning $x\_e = 0.5$ to all edges except CD gives the optimal LP solution.

---
Tags: graphs, linear-programming, integer-programming, matching
---


# Question
Title: Regularity of language obtained by interleaving $a,b$
> Let $L$ be a regular language on an alphabet $\Sigma$. and let $L^{ab} = \\{\sigma\_1a\sigma\_2b...\sigma\_n \mid \sigma\_1...\sigma\_n \in L\\}$ be the language obtained by add between any two letters of any word of $L$ the letters $a$ and $b$, except before the first and after the last. Prove that $L^{ab}$ is regular.

I tried to prove it by induction on the length of $r$, the regular expression that the language corresponds to. There are 3 cases, the case of $r$ is union I understand but in the cases of concatenation and \*, the induction doesn't work.

# Answer
> 3 votes
There are several issues here. Let's first see what happens if you need to insert only $a$-s. We will construct an operator $A\[r\]$ which generates a regular expression for $$\\{\sigma\_1 a \sigma\_2 a \ldots a \sigma\_n : \sigma\_1 \ldots \sigma\_n \in L\[r\], n \geq 1\\}.$$ If $\epsilon \in L\[r\]$ (which can be determined inductively), then it would need to be added explicitly as an additional final step. The construction is inductive:

* $A\[\epsilon\] = A\[\emptyset\] = \emptyset$, $A\[\sigma\] = \sigma$.
* $A\[r\_1 + r\_2\] = A\[r\_1\] + A\[r\_2\]$.
* $A\[r\_1r\_2\] = A\[r\_1\] a A\[r\_2\] \stackrel?+ A\[r\_1\] \stackrel?+ A\[r\_2\]$, where the first additional term is present if $\epsilon \in L\[r\_2\]$, and the second if $\epsilon \in L\[r\_1\]$.
* $A\[r^\*\] = (A\[r\]a)^\*A\[r\]$.

When you have both $a$-s and $b$-s the general idea is the same, but you have to keep track of the parity of the generated words. We construct operators $E\[r\],O\[r\]$ for extracting only the words of even length and odd length (respectively) in $L\[r\]$. The construction is inductive:

* $E\[\epsilon\] = \epsilon$, $O\[\epsilon\] = \emptyset$.
* $E\[\sigma\] = \emptyset$, $O\[\sigma\] = \sigma$.
* $E\[\emptyset\] = O\[\emptyset\] = \emptyset$.
* $E\[r\_1 + r\_2\] = E\[r\_1\] + E\[r\_2\]$, $O\[r\_1 + r\_2\] = O\[r\_1\] + O\[r\_2\]$.
* $E\[r\_1r\_2\] = E\[r\_1\]E\[r\_2\] + O\[r\_1\]O\[r\_2\]$, $O\[r\_1r\_2\] = O\[r\_1\]E\[r\_2\] + E\[r\_1\]O\[r\_2\]$.
* $E\[r^\*\] = E\[r\]^\*(O\[r\]E\[r\]^\*O\[r\])^\*E\[r\]^\*$, $O\[r^\*\] = E\[r^\*\] O\[r\] E\[r^\*\]$.

At this point we have all the ideas required to solve your actual exercise. That's a task for you.

---
Tags: regular-languages
---


# Question
Title: Relation between programming languages requiring declaration of variables before use and using the token class $\text{id}$ while parsing
I was going through the text *Compilers: Principles, Techniques and Tools* by *Ullman et. al.* where I came across the following excerpt.

> Example 4.11. Consider the abstract language $L\_1 = \text{ { $wcw$ | $w$ is in $(a|b)^\*$}}$. $L\_1$ consists of all words composed of a repeated string of $a$'s and $b$'s separated by a $c$, such as $aabcaab$. It can be proven this language is not context free. This language abstracts the problem of checking that identifiers are declared before their use in a program. That is, the first $w$ in $wcw$ represents the declaration of an identifier $w$. The second $w$ represents its use. While it is beyond the scope of this book to prove it, the non-context-freedom of $L\_1$, directly implies the non-context-freedom of programming languages like $\text{Algol}$ and $\text{Pascal}$, which require declaration of identifiers before their use, and ***which allow identifiers of arbitrary length.***
>
> ***For this reason, a grammar for the syntax of $\text{Algol}$ or $\text{Pascal}$ does not specify the characters in an identifier.*** Instead, all identifiers are represented by a token such as $\text{id}$ in the grammar. In a compiler for such a language, the semantic analysis phase checks that identifiers have been declared before their use. □

I can understand that since $\text{Algol}$ and $\text{Pascal}$, require declaration of identifiers before their use we cannot check this property using context free grammar. But what is the connection of this with the point of "allowing identifiers of arbitrary length"?

Moreover the authors add, that instead of using the characters in an identifier, identifiers are represented by the token class $\text{id}$. That the identifiers are represented by the token class $\text{id}$, was known to me as a fact, but I did not quite know what is the significance of this as far as the explanation in the example of the text is concerned.

Please explain me.

# Answer
In order for their example to work, the authors need identifiers to be of unlimited length. This is because the language $$ \\{ wcw : w \in \\{a,b\\}^\*, |w| \leq n \\} $$ is context-free (indeed, regular).

The syntax of a language like Pascal or Algol is context-free. This accomplished by waiving the requirement that an identifier be declared before its usage; this will be checked on-the-fly by the parser. This idea is implemented by representing identifiers as a single token in the grammar of Pascal or Algol.
> 5 votes

# Answer
Defining the grammar in terms of an abstract $id$ token allows you to write a *context-free* grammar for a language which would otherwise be context-sensitive, by dropping restrictions from the grammar. Something like

```
FUNCDEF ::= 'func' ID '(' PARAMDEF ')' FUNCBODY

```

and

```
FUNCCALL ::= ID '(' ARGS ')'

```

This is perfectly context-free, by simply treating the $id$ as an abstract token and *ignoring the restriction that a FUNCCALL with some $id$ must be preceded by a FUNCDEF with the same $id$*.

Instead, we either declare this restriction to be a *semantic restriction*, not a syntactic one, and ship the responsibility for checking it off to the semantic analyzer, not the syntactic analyzer (aka parser). Or we declare it an *additional syntactic retriction* not captured by the grammar.

See, for example the ECMAScript specification, which pulls this latter trick quite often.

If you look at the specification of variable declarations, you will find a good example of a restriction that is not context-free: you cannot declare the same variable twice. But, that is not specified in the grammar, it is specified in a subsection called "Static Semantics" (which many clauses in the spec have):

> It is a Syntax Error if the BoundNames of *BindingList* contains any duplicate entries.

So, here you can see that the specification says "this is a syntactic error, but we are specifying that part of the syntax outside of the grammar, in plain English".
> 2 votes

---
Tags: context-free, programming-languages, compilers, semantics, syntax
---


# Question
Title: is advice function and an oracle the same thing?
In the context of P/poly complexity class, an advice function is mentioned.

How is the advice function different than an oracle(/certificate)?

https://en.wikipedia.org/wiki/Advice\_(complexity) https://en.wikipedia.org/wiki/P/poly

# Answer
No, they are not the same. An oracle is something that an algorithm can send inputs to, and get back outputs, possibly many times. Advice is a single value that is provided to the algorithm, and depends only on the length of the input to the algorithm.
> 1 votes

---
Tags: complexity-theory, polynomial-time
---


# Question
Title: Is there a concept of probabilistic quantum computers?
Answering my question Yonatan N said a statement from which follows that there are computable functions of quantum time complexity strictly above polynomial.

Accordingly a Quora answer

> Quantum computation is fully deterministic. A given computation applied to a given starting state will always produce the same final state, every time. What is potentially non-deterministic is extracting the output in classical terms.

So, it looks like it makes sense to introduce probabilistic quantum computation (as opposed to "fully deterministic"). Does it make sense? Does such thing as probabilistic quantum computation exist in physics?

So maybe, for probabilistic quantum computation there is no known proof that there are computable functions of (probabilistic) quantum time complexity strictly above polynomial, is there?

# Answer
> 5 votes
It is true that unitary gates used in quantum algorithms (and indeed any unitary evolution in quantum mechanics generally) is deterministic and measurements are the only non-deterministic elements in a quantum algorithm (and indeed in quantum mechanics generally). However, it is not true that measurement is always the final step in a quantum algorithm, see for example my answer to this question for a few prominent instances of the use of intermediate measurements. The misconception might originate in the *principle of deferred measurement* which says that any quantum algorithm with intermediate measurements is equivalent to one where all measurements are moved to the final step. In particular, the principle enables us to replace classical control of quantum gates based on results of intermediate measurements with quantum controlled gates.

Returning to the question of probabilistic quantum computation, note that any probabilistic quantum algorithm (understood here as one that chooses gates to apply based on random bits) can be simulated by a quantum algorithm with intermediate measurements. This follows from the fact that measurement of the state $|+\rangle = (|0\rangle + |1\rangle)/\sqrt{2}$ in the computational basis generates a random bit which can subsequently be used to make random choices about which quantum gates to apply. By the principle of deferred measurement we can turn such a probabilistic quantum algorithm into a quantum algorithm where all measurements are terminal. In conclusion, probabilistic quantum computing is subsumed by regular quantum computing. This is why no distinction is generally made between probabilistic and deterministic quantum algorithms.

---
Tags: complexity-theory, time-complexity, quantum-computing, probabilistic-algorithms
---


# Question
Title: Would increasing system memory speed reduce a Von Neumann Architecture bottleneck?
A Von Neumann Architecture bottleneck is a limit on the amount of data a computer can process due to limited bandwidth between the CPU and RAM. Possible mitigations to the problem according to Wikipedia are...

> * Providing a cache between the CPU and the main memory
> * Providing separate caches or separate access paths for data and instructions
> * Using branch predictor algorithms and logic
> * Providing a limited CPU stack or other on-chip scratchpad memory to reduce memory access
> * Implementing the CPU and the memory hierarchy as a system on chip, providing greater locality of reference and thus reducing latency and increasing throughput between processor registers and main memory.

I know that increasing the number of data lanes between the CPU and RAM would help, but would increasing the system memory speed also help?

# Answer
> 2 votes
No, increasing the memory speed won't help solve the Von Neumann architecture bottleneck. The reason is **as memory size is increased the time required to access the memory contents increases**. So no matter how fast the memory is, if it is large it will be slower. So faster, smaller memories called caches are used to provide the illusion of a large, fast memory to the user.

---
Tags: computer-architecture, cpu-cache, cpu, memory-access, cache
---


title: O(n+m) vs O(n+2m) time complexity

text:
# Question
Title: O(n+m) vs O(n+2m) time complexity
Are $O(n+m)$ and $O(n+2m)$ the same?

If $m\>n$, then both complexities are $O(m)$. Likewise, if $n\>m$, then they are $O(n)$. Is this correct?

# Answer
I would like to try an intuitive explanation.

Assume your algorithm works in $2m$ time units on your current machine. If you run it on a machine twice as fast, then it takes $m$ times units. As we do not know (and do not care) on which machine(s) the algorithm will run, this makes the $2$ factor irrelevant. This is what the big-$O$ notation captures, in a sense.

(In addition, if we know that $n\>m$ then we have $3n \> n+2m$, and so anything *below* $n+2m$ also is *below* $3n$. As big-$O$ deals with upper bound, this means that $O(n+2m)$ complexity is, in this case, in $O(3n)$ complexity which, as explained above, is nothing but $O(n)$.)

Hope this helps.
> 1 votes

# Answer
Assuming $n, m$ independent variables let me use definition for big-$O$ for multiple variables, which I discussed in Big O of multiple variables:

$O(f(n,m)),(n,m) \to \infty$ is set of functions $g$, such, that $\exists C\_g\>0$ and $\exists M\_g\>0$ such that for $\forall \left\Vert (n,m)\right\Vert\_\infty \> M\_g$ holds $g(n,m) \leqslant C\_g f(n,m)$, where $\left\Vert(m,n)\right\Vert\_\infty = \max\\{n,m \\}$ based on intention to infinity by squares. It's well known Chebyshev norm or the infinity norm and is equivalent to intention to infinity by rectangles.

As case $O(n+m) \subset O(n+2m)$ is obvious, let me go to reverse subset direction: assume we have $f\in O(n+2m)$, which means $f(n,m)\leqslant B\_f (n+2m)$ in appropriate conditions for some constant $B\_f$. Now we need such $C\_f$ for which holds $B\_f (n+2m) \leqslant C\_f(n+m)$. It's easy to see, that any $C\_f \gt 2 B\_f$ satisfy this condition, so $O(n+2m) \subset O(n+m)$, which means, that we obtain equality.

At end let me say, that if $n, m$ are not independent variables, then it requires more context as well as if/when we decide to consider other types of intentions to infinity such as intention to infinity by circles, by triangles etc.
> 0 votes

---
Tags: complexity-theory
---


# Question
Title: On the recurrence $T(n) = T(n/a) + T(n/b) + n^c$
Consider the recurrence $$T(n)=T(\tfrac{n}{a}) + T(\tfrac{n}{b})+O(n^c).$$ What is the condition on $a,b$ that guarantees $T(n)=O(n^c)$?

With substitution I get $$T(n)=T(\tfrac{n}{a}) + T(\tfrac{n}{b})+O(n^c)\le (\tfrac{n}{a})^c + (\tfrac{n}{b})^c + n^c = n^c ((\tfrac{1}{a})^c + (\tfrac{1}{b})^c + 1)$$ I need $(\frac{1}{a})^c + (\frac{1}{b})^c + 1$ to be less than one if I want to show that it is $\le n^c$. So $\frac{1}{a^c} + \frac{1}{b^c} \le 0$. But I have trouble with that and I don't know if my idea of showing this is right.

# Answer
Suppose that $$ T(n) = T(n/a) + T(n/b) + n^c. $$ Let's try to prove by induction that $T(n) \leq Mn^C$: $$ T(n) \leq M(n/a)^c + M(n/b)^c + n^c = \left((a^{-c} + b^{-c})M + 1 \right) n^C. $$ Therefore we need $(a^{-c} + b^{-c})M + 1 \leq M$, which we can satisfy as long as $a^{-c} + b^{-c} \< 1$.

When $a^{-c} + b^{-c} = 1$, the answer is likely $T(n) = \Theta(n^c\log n)$.
> 1 votes

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Which of the following is a more appropriate complexity for this reccursive function?
Given the following recurrence relation:

\begin{gather\*} h(A) = \begin{cases} 0,\qquad \qquad \text{ }\text{ }\text{ }A=0\\ 1+h(A-1),\text{ }\text{ }A\text{ is odd} \\ 1+h(\frac{A}{2}),\qquad \text{otherwise} \end{cases} \end{gather\*}

which of the following choices best describes its complexity?

A) $h(A)\in\theta(\log\_2A)$

B) $h(A)\in\Omega(\log\_2A),\text{ }h(A)\in\mathcal{O}(A)$

The book that I'm reading has selected choice $A$, however I feel like $B$ should be the answer. We know that the complexity is at minimum $\log\_2A$ (best case when it's a power of $2$), but it could be higher than that and have a few more steps depending on what $A$ is. What am I missing here?

# Answer
You can show that if the binary expansion of $A\>0$ contains $N\_0$ zeroes and $N\_1$ ones then $h(A) = 2N\_1 + N\_0$. Since $N\_0 + N\_1 = \lfloor \log\_2 A \rfloor + 1$, this shows that $h(A) = \Theta(\log A)$.
> 1 votes

---
Tags: time-complexity, asymptotics, recurrence-relation
---


# Question
Title: If possible, use binary search to find an element in sorted array
> Given sorted array $A\[1..n\]$, we want to find an element such that, $A\[i\]=i^2$,Can we use binary search to find such a element?

**My Attempt:** initially, I read this link, but I can't understand the comments for why we can't find that element in $O(\log n)$. Any hint be appreciated.

# Answer
No. Let's define an array $B$ as $B\[i\] = i^2 - 1$. Clearly it has no solution, but it is sorted.

Now I define $A$ to be a copy of $B$, with exactly one element, $A\[k\]$ incremented by one. This array is still easily seen to be sorted, but there's no way to find out which $k$ I used to increment a single element other than scanning the complete array. After all, if you inspect $n - 1$ indices of this array, I could've chosen $k$ as the single index you didn't look at.
> 1 votes

---
Tags: algorithms, search-algorithms, discrete-mathematics, binary-search
---


title: "Batch" partial sorting algorithm

text:
# Question
Title: "Batch" partial sorting algorithm
I'm looking for an existing algorithm that would ensure that the first `k` elements after sorting are the top `k` elements but not necessarily in the right order.

To put it differently, I would like an algorithm that acts like C++ std::partial\_sort but takes advantage of the fact that I don't need the first elements ordered.

If there's no such thing yet, I'm planning on studying again existing algorithms and try to find out which one would be the best candidate to tweak. Any lead would be welcome.

# Answer
> 0 votes
What I was looking for is a selection algorithm that will select the k-th element. As mentioned in comment, running then a simple partition algorithm if needed will then provide the expected result.

The reference seems to be the quick select algorithm while the reference implementation points to introselect as implemented in Numpy's partition function or C++ nth\_element function.

---
Tags: algorithms, sorting
---


# Question
Title: What is uniformity in Boolean circuits exactly?
I have two questions on Kaveh's answer to Definition of uniform boolean circuit :

1. Kaveh mentions that the input is in unary encoding. In the definition it says the input is $1^n$, afaik $1^n$ is a sequence of 1's repeated n times, but unary encoding is a sequence of 1's and ends with 0 there is no power of 1 that gives 0... So how is $1^n$ a unary encoding?
2. Why do we use a unary encoding and not the binary encoding of n? what happens if we use binary instead?

# Answer
> 2 votes
Here is the binary encoding of 5: $$101$$ And here is its unary encoding: $$11111$$ Hopefully the difference is apparent.

Let's see what happens if we switch to binary encoding in the context of the linked question. Given the binary encoding of $n$, we need to produce a circuit, operating on $n$ bits, in logspace, and so in polynomial time. How much time do we have? The binary encoding of $n$ has length roughly $\log n$, so we have time $O(\log^C n)$, which isn't enough to produce a circuit which reads all input bits.

In contrast, if we use unary encoding, then the length of the input is $n$, and so we have time $O(n^C)$, which is more reasonable (in addition, we are only allowed to use $O(\log n)$ space).

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


# Question
Title: Time complexity of min() and max() on a list of constant size?
If you use `min()` or `max()` on a constant sized list, even in a loop, is the time complexity *O(1)*?

# Answer
> 28 votes
That depends what exactly you mean by "constant sized". The time to find the minimum of a list with 917,340 elements is $O(1)$ with a very large constant factor. The time to find the minimum of various lists of different constant sizes is $O(n)$ and likely $\Theta(n)$ where $n$ is the size of each list. Finding the minimum of a list of 917,340 elements takes much longer than finding the minimum of a list of 3 elements.

# Answer
> 14 votes
I found this quote from the Wikipedia article on time complexity helpful:

> The time complexity is generally expressed as a function of the size of the input.

So if the size of the input doesn't vary, for example if every list is of 256 integers, the time complexity will also not vary and the time complexity is therefore `O(1)`. This would be true of any algorithm, such as sorting, searching, etc.

# Answer
> 5 votes
Sure, you could call it O(1) if you want.

So what if you choose to describe it that way? It's still going to iterate over the whole list, so describing it one way or the other doesn't change the real-world Python run time.

It's still something you want to avoid doing repeatedly for the same list, especially if the list isn't tiny. (Especially in a loop that can run many iterations.)

Being O(1) isn't the same thing as *cheap*, especially if you're "cheating" by taking large but fixed sizes as "constants" instead of part of your complexity calculation.

If anything, you've created an example of why complexity-class analysis is not the same thing as performance estimation, especially for a given finite range of problem sizes. If it feels "wrong" to call it O(1), this is why.

# Answer
> 4 votes
**Yes**

In general, if the time complexity of an algorithm is O(f(X)) where X is a characteristic of the input (such as list size), then if that characteristic is bounded by a constant C, the time complexity will be O(f(C)) = O(1).

This is especially useful with certain algorithms that have time complexities that look like e.g. O(N ^ K). This is superexponential, which isn't great, but if you can fix K to be bounded by a small constant, your runtime is polynomial, which is much better! (The downside is that your algorithm will have to refuse certain inputs, but hey those were going to take forever anyway.)

---

This here is the big limitation of complexity analysis: it can only tell you how fast certain functions *grow*, it will not tell you the absolute time taken. An algorithm that will always take a million years no matter the input is still O(1), after all.

To figure out the specific numbers, and if you'll need to cache the results from `min` and `max`, you'll need to measure the actual time your code takes, and decide if it is fast enough for your use case.

# Answer
> 3 votes
# Usually, $\operatorname{O}\left(1\right) .$

Yeah, usually it'll be $\operatorname{O}\left(1\right) ,$ under normal assumptions.

A major exception would be if the list-elements could grow in complexity with input-size. For example, if the list-elements were themselves lists that grew with the input, then even a single comparison between two of the elements could be more than $\operatorname{O}\left(1\right) .$

But if the list-elements are, say, machine-primitives that have constant-time behavior, then, yeah, typically $\operatorname{O}\left(1\right) .$

# Answer
> 2 votes
If the size of the lists as input to the `min()` and `max()` functions always are the same constant $k$, then you can find an upper bound (and lower bound) on the number of operations required to compute `min()` and `max()` that depends only on the constant size $k$ (plus some other constants), which results in a running time of $O(1)$.

Therefore, if the size of the lists always are the same, then the asymptotic time complexity will be $O(1)$. However, do keep in mind that the actual running time still depends on the size of the lists.

# Answer
> 2 votes
Yes, any bounded amount of work is O(1).

*Every* algorithm applied to an input of bounded size takes O(1) time, however, and that is independent of any variables whatsoever, so there is never any reason to mention this as an attribute of any particular algorithm.

In the analysis of algorithms, though, you will often see O(1) used to refer to any bounded amount of work. The recurrence relation for the time taken by binary search, for example, is T(n) = T(n/2) + O(1).

# Answer
> 2 votes
Colloquially we refer to algorithms as $O(1)$ or $O(n\ \log n)$ or such. When you start talking about the Big-O complexity class of an operation over a constant sized object, it becomes important to use it more precisely. Us CS people get too lazy!

Big-O notation is applied to *mathematical functions* not computer algorithms. It explores the bounds on an operation as the independent variables in that function head off towards infinity. We cannot apply it to an algorithm without using extra words. For example, we might define a function $f(n)$ to be "the maximum number of comparisons needed to sort a list of length $n$." This describes a mathematical function, and thus we can plot it, and we can look at its behavior using Big-O complexity analyses.

So in this case, you have an algorithm "determine the maximum value in a list of a given size." But you still need to define your function on that algorithm. I can't say "determine the maximum number of values a list of some pre-specified size as the size of that list grows to infinity" any more than I can say "two plus two equals five for very large values of two."

I *could* pick some arbitrary unimportant variable, and say $f(n)$ is "the number operations does it take to find the maximum of a fixed-size length given that the price of tea in India is $n$". That would be a valid function we could apply Big-O notation to, and we would find that your algorithm's run time is $O(1)$ with respect to the price of tea in India. But we need *something* as an independent variable that can take on values that approach infinity.

To use Big-O meaningfully, you need to identify some function of a variable (or variables) which can approach infinity. Only then is a Big-O analysis meaningful.

# Answer
> -1 votes
My understanding of the notion of time complexity is that it describes the change in the amount of time that an operation takes as the size of a single input to the function changes. The quote that @JoshRumbut gives says pretty much the same thing.

If, as in the case here, one is not talking about how the execution time of an operation changes as the input size changes, then the notion of time complexity does not apply. The time complexity for `min()` or `max()` operations run only on a list of a particular size is not O(?) anything The concept simply doesn't apply here.

What does make sense is to talk about the time complexity of `min()` and `max()` as the size of the input list changes. Since the execution time varies linearly with the size of the input list (either a linked list or an array), the time complexity of `min()` or `max()` on a simple list is `(N)`.

# Answer
> -1 votes
Not really. With a constant size, such as 1,000,000, the time complexity of the `min()` and `max()` aren't O(1).

Consider a nested list whose every element is an m sized list, which then elments are:

> \[0\] * n + \[k\]

where k is a number. The time complexity of comparating two elements is O(m), so the complexity of `min()` and `max()` is O(m).

# Answer
> -2 votes
**The time complexity of the algorithm is still O(N)**

Sure, in a sense the max and min of a constant list is a constant, but no general implementation can know these values without running first.

**The time complexity of the call to the min and max function MAYBE O(1)**

A compiler can recognize that the result of the call is a compile-time constant if the argument is a constant, then precompute these values and place the result directly in the machine code. I doubt that the python interpreter can do this optimization, but I do not know for sure whether it might perform some just-in-time compilation tricks or cache the results. In the end, it is out of your hand.

*EDIT:* I was assuming that constant sized implies that OP does not change the values of the entries at any point. I might need to rephrase this. However, this is my point: If the list ist just constant in size, but not constant in value, I'm allowed to change the last N-1 entry to a value larger than the previous max value. So then the result of max() must change. How can a general algorithm work this out without touching all elements up to the last one?

*If the question is intended to infer the complexity of an algorithm that has M values as input, and is using max and min, then it depends on whether size N is dependent on M. That is not given in the question, thus no conclusive answer can be given.*

# Answer
> -4 votes
It depends if Array/List is sorted or not. The given answer is incorrect and my one was downvoted. Thanks voting bots!

https://stackoverflow.com/questions/35386546/big-o-of-min-and-max-in-python

FROM WIKIPEDIA:

O(1) is applicable

> An algorithm is said to be constant time O(1)... In a similar manner, finding the minimal value in an array sorted in ascending order

O(n) is applicable

> O(n).. finding the minimal value in an unordered array is not a constant time operation as scanning over each element in the array is needed in order to determine the minimal value

You need to check all of the the values to find the minimal one if the list is not sorted. My first idea is that Python does not have a hidden support for caching function return values. I'm not certain if min(value) is considered deterministic in python if you supply a reference instead of an actual list.

Below is an easy way to memoize a function and its return values in Python. If you apply this the complexity of your function can be reduced to O(1)+n

```
def memoize(func):
cache = dict()

def memoized_func(*args):
    if args in cache:
        return cache[args]
    result = func(*args)
    cache[args] = result
    return result

return memoized_func

```

---
Tags: time-complexity, python
---


# Question
Title: Median of medians confusion -- the "approximate" median part
I'm struggling with the median of medians algorithm, and I think it's perhaps more of a semantics thing rather than a technical thing. I've always thought the median of medians algorithm as finding an approximate median $p$ such that $p$ is within $20\\%$ of the true median $M$ in the sorted array.

However, when I look at actual implementations, e.g., in https://brilliant.org/wiki/median-finding-algorithm/, the algorithm they posted returns an exact median, but at each level of the recursion, you may have some approximate median generated from a sublist of medians. And eventually you'll reach a level where the array is $\leq 5$ elements, ending the recursion. At this level, you obtain an exact median of the array you passed in. So I had thought all this time that this exact median computed at the last level is actually your estimate of the median in the original array passed in at the first level of the recursion.

So I had the same confusion as this poster https://stackoverflow.com/questions/52461306/something-i-dont-understand-about-median-of-medians-algorithm and some others.

Now that I understand this algorithm, I am now confused on how the median of medians actually finds an "approximate" median to the original array. In all the implementations I've seen, the median you find using median of medians is exact. So where does the approximate part come in other than approximating the median at each recursion level? Even Wikipedia describes as an algorithm that approximates a median. Yes, it approximates medians at various levels, but the final output is exact.

Or am I operating under a false premise in thinking that Median of Medians finds an approximate median to the ORIGINAL array?

# Answer
> 3 votes
Median-of-medians is a recursive algorithm which solves the more general *selection* problem: given an array $A$ of length $n$ (which we assume, for simplicity, has distinct elements) and an integer $k$, find the $k$'th smallest element (where $1 \leq k \leq n$). It works as follows:

* If $n \leq K$ (where $K$ is some constant), solve the problem by brute force.
* Otherwise, find an approximate median $x$ of $A$ in $O(n)$. By *approximate median*, we mean that $x$ is the $m$'th smallest element in $A$, where $\alpha n \leq m \leq (1-\alpha) n$ for some constant $\alpha \< 1$.
* Use $x$ to split $A$ into elements smaller than $x$, comprising an array $A\_{\<x}$ of length $m-1$, and elements larger than $x$, comprising an array $A\_{\>x}$ of length $n-m$.
* If $m = k$, then output $x$. If $m \> k$ then output the $k$'th smallest element of $A\_{\<x}$. If $m \< k$ then output the $(k-m)$'th smallest element of $A\_{\>x}$.

The running time of the algorithm satisfies the recurrence $T(n) \leq T(\alpha n) + O(n)$, whose solution is $T(n) = O(n)$.

The algorithm finds the exact median, but it does so by repeatedly finding approximate medians.

---
Tags: algorithms
---


# Question
Title: Average case analysis by key comparisons of Max Sort
I'm having trouble approaching this average case analysis in terms of key comparisons.

The pseudo-code is as follows:

```
maxSort(Array) {
    for (int i = Array.length - 1; i > 0; i--) {
        x = i - 1
        max_i = findMaxPos(x) # performs x key comparisons
        swapValues(max_i, i)
    }
}

```

findMaxPos returns position of largest value between index 0 and x of the array. Performs x key comparisons.

I believe the worst case is W(N) = n(n-1)/2 where n is the size of the array.

I am unsure how to contextualize the algorithm in an average case in terms of key comparisons. Should I create a decision tree and show the lower bound for average behavior? Or is there a way to use permutations? Any help is greatly appreciated

Edit: For context, the original question is asking for the number of key comparisons in the worst and average case. While working out the worst case was relatively straight forward I'm unsure how to write some sort of proof or perform analysis to show the average is the same

# Answer
The number of comparisons on an array of length $n$ is $\binom{n}{2}$, regardless of the contents of the array. Therefore all of the following are $\binom{n}{2}$: the worst-case number of comparisons, the best-case number of comparisons, and the average-case number of comparisons, with respect to any input distribution.
> 1 votes

---
Tags: algorithms, algorithm-analysis, sorting, average-case
---


# Question
Title: Information-theoretic lower bound for succinct string dictionary of the Unicode Name property
## Background

The literature on succinct data structures refers often to the “information-theoretic lower bound” of encoding data, i.e., the minimum number of bits needed to store the data – a concept related to information-theory entropy. For instance, the definition of a succinct data structure is one that takes up $Z + o(Z)$ bits of space, where $Z$ is the “information-theoretic lower bound” of the data.

However, I am having difficulty figuring out how to actually use this concept for my purposes: creating a succinct string dictionary for Unicode Standard’s Name property. The best general definition that I can find is from Grossi and Ottaviano (2013), who define it as $\lceil \log\_2 || \rceil$, where $$ is the domain from which the data were originally drawn. They give the information-theoretic lower bound of a bitvector — having length $n$ and containing $m$ one-bits — as $\lceil \log\_2 { \choose } \rceil$, which is equivalent to any subset (made of $$ items) drawn from a universe set (made of $$ possibilities).

Now, the Unicode Standard’s Name property injectively associates a unique immutable name (made of capital English alphanumeric characters, hyphens, and spaces: a repertoire of $38$ characters) with code points (integers ranging between $0$ and $\mathrm{10FFFF}$, in hexadecimal). For instance, the value of the code point $20$ (in hexadecimal) is `SPACE`, and the value of the code point $\mathrm{E01EF}$ is `VARIATION SELECTOR-256`. Name values never start or end with spaces, and they never start with numbers or hyphens. Not all code points have Name values. At the time of this writing, the longest name is `ARABIC LIGATURE UIGHUR KIRGHIZ YEH WITH HAMZA ABOVE WITH ALEF MAKSURA ISOLATED FORM` ($83$ characters long), and the shortest name is `OX` (two characters).

The Name property is defined by the text file `UnicodeData.txt` (along with several other rules that generate names for certain characters such as Hangul syllables, which will be ignored here). `UnicodeData.txt` is (as of March 2021) a highly repetitive 32297-line text file that looks like this:

```
0000;<control>;Cc;0;BN;;;;;N;NULL;;;;
0001;<control>;Cc;0;BN;;;;;N;START OF HEADING;;;;
0002;<control>;Cc;0;BN;;;;;N;START OF TEXT;;;;
0003;<control>;Cc;0;BN;;;;;N;END OF TEXT;;;;
0004;<control>;Cc;0;BN;;;;;N;END OF TRANSMISSION;;;;
0005;<control>;Cc;0;BN;;;;;N;ENQUIRY;;;;
0006;<control>;Cc;0;BN;;;;;N;ACKNOWLEDGE;;;;
0007;<control>;Cc;0;BN;;;;;N;BELL;;;;
0008;<control>;Cc;0;BN;;;;;N;BACKSPACE;;;;

```

…and then this:

```
001E;<control>;Cc;0;B;;;;;N;INFORMATION SEPARATOR TWO;;;;
001F;<control>;Cc;0;S;;;;;N;INFORMATION SEPARATOR ONE;;;;
0020;SPACE;Zs;0;WS;;;;;N;;;;;
0021;EXCLAMATION MARK;Po;0;ON;;;;;N;;;;;
0022;QUOTATION MARK;Po;0;ON;;;;;N;;;;;
0023;NUMBER SIGN;Po;0;ET;;;;;N;;;;;
0024;DOLLAR SIGN;Sc;0;ET;;;;;N;;;;;

```

…and then this:

```
004C;LATIN CAPITAL LETTER L;Lu;0;L;;;;;N;;;;006C;
004D;LATIN CAPITAL LETTER M;Lu;0;L;;;;;N;;;;006D;
004E;LATIN CAPITAL LETTER N;Lu;0;L;;;;;N;;;;006E;
004F;LATIN CAPITAL LETTER O;Lu;0;L;;;;;N;;;;006F;
0050;LATIN CAPITAL LETTER P;Lu;0;L;;;;;N;;;;0070;
0051;LATIN CAPITAL LETTER Q;Lu;0;L;;;;;N;;;;0071;

```

…and then later this:

```
090D;DEVANAGARI LETTER CANDRA E;Lo;0;L;;;;;N;;;;;
090E;DEVANAGARI LETTER SHORT E;Lo;0;L;;;;;N;;;;;
090F;DEVANAGARI LETTER E;Lo;0;L;;;;;N;;;;;
0910;DEVANAGARI LETTER AI;Lo;0;L;;;;;N;;;;;
0911;DEVANAGARI LETTER CANDRA O;Lo;0;L;;;;;N;;;;;
0912;DEVANAGARI LETTER SHORT O;Lo;0;L;;;;;N;;;;;

```

…until getting to the end:

```
E01EC;VARIATION SELECTOR-253;Mn;0;NSM;;;;;N;;;;;
E01ED;VARIATION SELECTOR-254;Mn;0;NSM;;;;;N;;;;;
E01EE;VARIATION SELECTOR-255;Mn;0;NSM;;;;;N;;;;;
E01EF;VARIATION SELECTOR-256;Mn;0;NSM;;;;;N;;;;;
F0000;<Plane 15 Private Use, First>;Co;0;L;;;;;N;;;;;
FFFFD;<Plane 15 Private Use, Last>;Co;0;L;;;;;N;;;;;
100000;<Plane 16 Private Use, First>;Co;0;L;;;;;N;;;;;
10FFFD;<Plane 16 Private Use, Last>;Co;0;L;;;;;N;;;;;

```

Specifically, each line denotes the data of a code point, in fields separated by semicolons: the first field contains the code point itself in hexadecimal, and the second field contains the Name property. If a line’s second field starts with a `<`, or if the field is blank, then there is no Name value for that code point. The other fields may be ignored for the purposes of the Name property.

## Questions

I want to determine the information-theoretic lower bound of the Name property. My eventual goal is to create a succinct data structure that supports bidirectional remote-access lookup of the Name property, between code points and their names.

My questions are:

1. Does the Unicode Name property have *two* information-theoretic lower bounds (one for looking up Name values → code points and one for looking up code points → Name values)?
2. What is the information-theoretic lower bound(s) for looking up Name values → code points and for looking up code points → Name values?
3. Does the information-theoretic lower bound(s) change if Huffman coding or other kinds of data compression is applied to the Name values?

My current best guess is that the information-theoretic lower bound for the Unicode Name property (in both directions) is $\lceil \log\_2 { \choose }\rceil \approx 1.4 \cdot 10^7 \approx 1.8 MB$, where $$ is the number of strings between $2$ and $83$ characters long from a $38$-character alphabet $(38^2 + 38^3 + … + 38^{83} \approx 1.4 \cdot 10^{131})$ and $$ is the number of Name values defined in `UnicodeData.txt` (a little less than its number of lines, which is 32297). But I’m almost certain that this is not correct—this is about as large as the entire size of `UnicodeData.txt`, in uncompressed UTF-8 encoding, and which contains much extraneous non-Name-related data.

# Answer
> 3 votes
The "information-theoretic lower bound" that you mention here is correct if you are encoding an element of a set, all of whose elements should be considered equiprobable. That doesn't really apply to this problem.

It's true that you could encode each character name as though it was a random element of the set of strings of length between 2 and 38 over the alphabet `ABC...XYZ0123456789-` . But an encoding that assigns the same number of bits to every member of that set will use the vast majority of its coding space on strings like `FKCYE 7BAYBM1UIDHF3K3LN9P07IGWEMNTJH31MX2JJ-S3W LGKA0WFU-MHR67E5HD7CUMHWYEX1UW4EO9T`, and only a tiny fraction on strings like `LATIN CAPITAL LETTER A`. You can do much better by assigning shorter bit sequences to "more probable" strings using a more sophisticated model that looks for the presence of words like `LETTER`, and not just length and alphabet.

An information-theoretic lower bound that is closer to what you're looking for is Kolmogorov entropy. The Kolmogorov entropy of a string is the shortest program (in some agreed-upon language) that outputs that string. You want a program that produces different outputs for different inputs, but that only requires a minor change to the definition. Unfortunately it's practically impossible to determine the Kolmogorov entropy of a string of any significant length. Also, Kolmogorov entropy doesn't say anything about the efficiency of the program; for long strings the shortest program is likely to be extremely slow.

---

My recommendation is to compress the concatenation of all of the strings with something like zlib or liblzma to get a target size, which will probably be in the 100K-200K range. This is not really a valid theoretical "bound" but it's probably a good approximation to how much you can reasonably compress your strings in practice.

If there is a decent compression library (like zlib) that you can use without needing to count its code size, then you might have success in compressing the strings in small groups, or compressing each string separately with a prebuilt dictionary containing common strings like `LETTER` . If not, you could use a Huffman code with each code mapping to some common string or single character. Picking a good set of strings is a black art, and I don't know much about it.

---
Tags: algorithms, information-theory, lower-bounds, exact-string-matching, succinct-data-structures
---


# Question
Title: Resources for implementing dependent type theory
I want to implement Martin Löf's intuitionistic type theory in a functional language such as Haskell, preferably also implementing a lexer/parser for the language. How should I start approaching it? Are there any good papers/blog posts/github repo examples that might be useful? Thanks!

# Answer
> 5 votes
This paper is my go-to for implementing dependent types. It starts from the basics, uses bidirectional types, and has accompanying code in Haskell.

If you're at all interested in type inference, this paper is great, and also has accompanying Haskell code.

David Christiansen has a tutorial on dependent type checking with bidirectional types, with a Haskell and Racket. More generally, I've heard great things about his book The Little Typer, though I haven't had a chance to read it myself.

I've heard great things about smaltt by András Kovács, particularly for it being an efficient implementation.

---
Tags: programming-languages, type-theory, semantics, dependent-types
---


# Question
Title: Given a Turing Machine $M$, if I know $L(M)$ is finite, can I solve the halting problem?
Say I'm given an oracle that tells me whether or not $L(M)$, the set of words accepted by a Turing Machine $M$, is finite.

By leveraging this oracle, can I solve the halting problem? That is, on an arbitrary input $\<M, x\>$, can I tell if M is going to halt on $x$ or will it loop forever?

My intuition says no because I don't see a way to leverage the oracle. For example, even with a stronger oracle that tells me if $x \in L(M)$, I still don't know, for inputs $x \notin L(M)$, how $M$ is going to behave. It could either reject (and halt), or loop forever.

Hence, I can't seem to solve the problem even with a stronger oracle that computes $L(M)$ explicitly in case it's finite. So, I believe merely knowing $L(M)$ is finite or not doesn't lead to a solution for the halting problem.

Is my reasoning correct, or am I overlooking something here?

# Answer
Yes, with such a powerful oracle, the halting problem can be solved.

To be clearer, given an arbitrary Turing machine, the oracle will tell the set of words accepted by that Turing machine is finite or not.

Suppose we are given a Turing machine $M$ and an input $x$. Let us construct Turing machine $M'$ such that on all inputs, $M'$ will simulate $M$ running with input $x$. Furthermore, when the simulation of $M$ halts (because $M$ halts on $x$), $M'$ will accept, regardless of whether $M$ accepts or rejects.

Note that $M'$ either always accepts or always runs forever. Now let us apply the oracle to $M'$.

* If the oracle says $L(M')$ is not finite, it implies $M'$ always accepts. That means $M$ halts on $x$.
* If the oracle says $L(M')$ is finite, it implies $M'$ always runs forever. That means $M$ on $x$ runs forever.

So, we have solved the halting problem on $(M,x)$, thanks to the oracle.

---

Here is a similar question, which might be the question intended by the OP as well.

Suppose (without any oracle) we are given an arbitrary Turing machine $M$ that accepts only finitely many words and an arbitrary word $x$, can we decide whether $M$ will halt on $x$?

The answer is no.

Otherwise, we can solve the original halting problem in the following way, which is known to be impossible.

For a pair of Turing machine and input $(M,x)$, we construct Turing machine $M'$, which checks if its input is $x$. If yes, it will run as $M$; otherwise, it will loop forever. Since $M'$ accepts at most 1 word, our assumption says that we can decide whether $M'$ on $x$ will halt or not. But that is exactly the same as whether $M$ halts on $x$ or not.
> 6 votes

---
Tags: turing-machines, undecidability, halting-problem
---


# Question
Title: Why is tabulated hashing 3-wise independent but not 4-wise independent?
Tabulated hashing uses tables of random numbers to compute hash values. Suppose $|\mathcal{U}| = 2^w \times 2^w$ and $m = 2^l$, so that the items being hashed are pairs $(x,y)$ where $x$ and $y$ are $w$-bit strings (or $2w$-bit strings broken in half), and hash values are $l$-bit strings.

Let $A\[0 \cdots 2^w-1\]$ and $B\[0 \cdots 2^w-1\]$ be arrays of $l$-bit strings. $A$ and $B$ can be though of as $2^w \times l$ dimensional array of bits.

Define the hash function $h\_{A, B} : \mathcal{U} \to \[m\]$ by setting $h\_{A, B}(x, y) = A\[x\] \oplus B\[y\]$, where $\oplus$ denotes bit-wise exclusive-or.

Let $\mathcal{H}'$ denote the set of all possible functions $h\_{A, B}$.

Can someone explain why is $\mathcal{H}'$ 3-wise independent and not 4-wise independent?

# Answer
For any $h = h\_{A,B}$ and $x,x',y,y' \in \\{0,1\\}^w$, $$ h(x,y) \oplus h(x',y) \oplus h(x,y') \oplus h(x',y') = 0. $$
> 3 votes

# Answer
To be clear, you're asking why the following holds for $k=3$ but not for $k=4$:

$$ \forall (x\_1,y\_1),...,(x\_k,y\_k)\in\\{0,1\\}^{2w}, z\_1,...,z\_k\in\\{0,1\\}^m, s.t. (x\_i,y\_i)\neq (x\_j,y\_j):\\ \Pr\limits\_{A,B}\left\[\bigwedge\limits\_{i=1}^k A(x\_i)\oplus B(y\_i)=z\_i\right\]=m^{-k} $$

Where $A,B$ are independent and uniformly distributed over $(\\{0,1\\}^l)^{\\{0,1\\}^w}$ and $m=2^l$.

Applying the law of total probability:

$$ \Pr\limits\_{A,B}\left\[\bigwedge\limits\_{i=1}^k A(x\_i)\oplus B(y\_i)=z\_i\right\]=\sum\limits\_{b\_1,...,b\_k\in\\{0,1\\}^l}\Pr\limits\_{A,B}\left\[\bigwedge\limits\_{i=1}^k A(x\_i)=z\_i\oplus b\_i\Big| \bigwedge\limits\_{i=1}^k B(y\_i)=b\_i\right\]\cdot\Pr\left\[\bigwedge\limits\_{i=1}^k B(y\_i)=b\_i\right\] $$

Now let us denote by $\alpha,\beta$ the number of unique $x\_i$'s,$y\_i$'s correspondingly, i.e. $\alpha = |\\{x\_1,...,x\_k\\}|$, and $\beta=|\\{y\_1,...,y\_k\\}|$. Consider the number of non zero summands. Note that if $y\_i=y\_j$, then $b\_i=b\_j$ or the righthand expression in the above sum is zero. Similarly, if $x\_i=x\_j$ then $z\_i\oplus b\_i=z\_j\oplus b\_j$ or the lefthand expression becomes zero. For any "good" sequence of $b\_i$'s (i.e. one which is consistent with repetitions in the $x\_i$'s or $y\_i$'s), we have $\Pr\limits\_{A,B}\left\[\bigwedge\limits\_{i=1}^k A(x\_i)=z\_i\oplus b\_i\Big| \bigwedge\limits\_{i=1}^k B(y\_i)=b\_i\right\]=m^{-\alpha}$ (as $A,B$ are independent) and $\Pr\left\[\bigwedge\limits\_{i=1}^k B(y\_i)=b\_i\right\]=m^{-\beta}$. It thus remains to compute the number of sequences $b\_1,...,b\_k\in\\{0,1\\}^l$ such that $x\_i=x\_j$ implies $b\_i=b\_j\oplus z\_j\oplus z\_i$ and $y\_i=y\_j$ implies $b\_i=b\_j$ (the number of degrees of freedom in the above sum). Denote the number of such sequences by $C=C((x\_1,y\_1),...,(x\_n,y\_n))$ (unfortunately it is not determined by $k,\alpha,\beta$ alone). $C$ is the number of equivalence classes in the relation $b\_i\sim b\_j$ (to be read as $b\_i$ determines $b\_j$) which is the transitive closure of $\\{(b\_i,b\_j)| x\_i=x\_j \lor y\_i=y\_j\\}$. We conclude now that:

$$ \Pr\limits\_{A,B}\left\[\bigwedge\limits\_{i=1}^k A(x\_i)\oplus B(y\_i)=z\_i\right\]=\frac{m^C}{m^{\alpha+\beta}} $$

For $k=3$ you can manually check that the only options (up to renaming $\alpha,\beta$) are: $(\alpha = 1, \beta =3, C=1)$, $(\alpha = 2, \beta =2, C=1)$, $(\alpha = 2, \beta=3, C=2)$, $(\alpha = 3, \beta=3, C=3)$ and in each case the above probability is $m^{-3}$. For $k=4$ you can get $(\alpha=2,\beta=2, C=1)$ which sets the above probability to $m^{-3}$ (instead of $m^{-4}$). I don't know why I wrote this lengthy answer to this simple problem, but I did and there is no going back.
> 1 votes

---
Tags: algorithms, randomized-algorithms, probabilistic-algorithms, hashing
---


# Question
Title: What's the time complexity of this function?
Consider the below function:

Considering that `print(a)` and `swap(a, b)` are of complexity $\theta(1)$, what is the time complexity of the above code?

The answer that comes to my mind is $\theta((n-k)!)$ or $\mathcal{O}(n!)$.

However in the book that I'm reading it says it's of order $\theta(n!)$. What am I missing here?

# Answer
> 1 votes
Denote the time complexity of $f$ on inputs $a,k,n$ by $T(k,n)$ (the time complexity doesn't depend on $a$ in your model). The time complexity satisfies the recurrence $$ T(k,n) = (n-k+1)T(k+1,n) + \Theta(n-k+1). $$ with base case $T(n,n) = \Theta(1)$. Define $$ S(k,n) = \frac{T(k,n)}{(n-k+1)!}. $$ Then $S(n,n) = \Theta(1)$ and for $k \< n$, $$ S(k,n) = S(k+1,n) + \Theta\left(\frac{1}{(n-k)!}\right). $$ It follows that $$ S(k,n) = \Theta\left(\frac{1}{(n-k)!} + \cdots + \frac{1}{1!} + 1\right) = \Theta(1), $$ and so $T(k,n) = \Theta((n-k+1)!)$.

If you take $T(n) = \max\_{1 \leq k \leq n} T(k,n)$, then indeed $T(n) = \Theta(n!)$.

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


# Question
Title: If we say L ⊂ {a, b, c}* then is L an infinite language?
I wonder if we say L ⊂ {a, b, c}\* then is L an infinite language? I think Kleene star makes me think L is an infinite language.

# Answer
$L$ is not *necessarily* an infinite language. $\\{a,b,c\\}^\*$ is an infinite language, but you've written $L\subset\\{a,b,c\\}^\*$, and infinite sets can (and do) have finite subsets. Consider $L=\\{a\\}$, then $L\subset\\{a,b,c\\}^\*$ but $\lvert L\rvert=1\<\infty$
> 3 votes

---
Tags: formal-languages
---


# Question
Title: How do I represent this regular expression in regular grammar?
**Question:** Is the regular expression and regular grammar equivalent? I've look on some examples of regular grammar however I don't think I fully understand how to convert regular expression to its equivalent grammar. So I am also asking for some help or tips to convert regular expression to regular grammar.

***Key**

() -\> empty string\*

**Regular Expression** :
a\* (ba (cf\* (g (f + j)\* b f\*)\* e)\* a)\*

**Regular Grammar**:

S-\> aS| ()

F-\> f F| ()

Q-\> fQ | jQ | ()

G -\> gQB|()

C-\> cFGE| ()

E-\> eC

M -\> baCA|()

A -\> aM

LM = {L1 | L1= SM }

# Answer
> 0 votes
They are equivalent in the sense that every language that can be represented with a regular expression, can be represented with a regular grammar; and vice versa.

Also, you can convert any regular grammar to a regular expression that generates the same language, and vice versa.

---
Tags: formal-grammars
---


# Question
Title: Sort an array that contain two sorted array in $O(n)$
> Given an array $A\[1..n\]$. $A$ is mixed of two sorted arrays $B$ and $C$ of equal sizes, such that $B$ is in the ascending order and $C$ is in the descending order.
>
> Consider the following example: $B=\[2,4,6,8\]$ and $C=\[9,7,5,1\]$. As a result $A=\[2,9,7,4,6,5,8,1\]$. Interestingly, The instructor said: $A$ can be sorted in $O(n)$. Anyone can give me a hint?

**My attempt:**

I tried to partition the array $A$ into sorted arrays $B$ and $C$, but I could not do it because my approach encountered counterexamples.

# Answer
> 0 votes
Let $a$ is the first element of $A$. Let $A$ is composed of array $B = (b\_{1},\dotsc,b\_{n})$ and array $C = (c\_{1},\dotsc,c\_{n})$. Now, we will partition $A$ into arrays: $B'$ and $C'$ in the increasing and decreasing orders respectively. Following is the process:

1. Let $p$ be a pointer. Initially, $p$ is pointing to $a$. Let $b$ be the element in $A$ next to $a$.
2. There are two possibilities:

**Case 1:** $a\<b$. Then, one of them must be an element of $B$. In this case, if $a$ is greater than the last element of $B'$, add $a$ to $B'$. Move the pointer to $b$ and go to step $1$.

Otherwise, add $a$ to $C'$ and $b$ to $B'$. Move the pointer to the element next to $b$ and go to step $1$.

**Case 2:** $a\>b$. Then, one of them must be an element of $C$. In this case, if $a$ is smaller than the last element of $C'$, add $a$ to $C'$. And, move the pointer to $b$ and go to step $1$.

Otherwise, add $a$ to $B'$ and $b$ to $C'$. Move the pointer to the element next to $b$ and go to step $1$.

The above process produces the array $B'$ in increasing order and $C'$ in decreasing order. However, note that these arrays might not be of the same size.

**Correctness:** Proof by induction.

*Base Step:* $A$ is composed of $B$ and $C$. $B'$ and $C'$ are empty right now. In Step $2$, Case 1, we add $a$ to $B'$. If it is indeed an element of $B$ then we are good. If not, then $b \equiv b\_{1}$ and we can assume that $A$ is composed of a new array $B' = (a,b\_{1},\dotsc,b\_{n})$ having elements in the increasing order, and array $C' = C \setminus a$ having elements in the decreasing order. Therefore, adding $a$ to $B'$ is correct.

Similarly, we can prove the correctness of Step $2$, Case $2$. And, the correctness of the further steps follows from the induction step.

---

After obtaining $B'$ and $C'$, you can merge them using merge sort like step in $O(n)$ time.

# Answer
> -1 votes
Here is the natural intuitive way to sort the array. The idea is to keep track of *two* inserting positions.

0. (Data structure) A node contains a value, a pointer to its previous node, which can be null, and a pointer to its next node, which can be null.
1. Initialize a two-way linked list $L$ with three nodes, the head, a node whose value is the first element of $A$ and the tail. Initialize two pointer $p\_1$ and $p\_2$, both of which point to the unique node in $L$. It will always be true that $L$ is sorted by its values and $p\_1$ is before or the same as $p\_2$.
2. Iterate over the remaining element of $A$ in order. Suppose the next element is $a$.

* If $a \lt p\_1.val$, search $L$ element by element backwards starting from $p\_1$ until a node with value that is not bigger than $a$ is found or the head of $L$ is reached. Insert a node with value $a$ just after that node. Update $p\_1$ to point to the inserted node.
    * If $p1.val \le a\lt p\_2.val$, search $L$ element by element backwards starting from $p\_2$ until a node with value not bigger than $a$ is found. Insert a node with value $a$ just before that node. Update $p\_1$ to point to the inserted node.
    * Otherwise, $a\ge p\_2.val$. Search $L$ element by element forwards starting from $p\_2$ until a node with value not smaller than $a$ is found or the tail of is reached. Insert a node with value $a$ just before that node. Update $p\_2$ to point to the inserted node.

I will leave you to figure out why this is a linear algorithm.

---
Tags: algorithms, data-structures, sorting
---


# Question
Title: How a 10GB network can copy 1TB data in 2 hours?
In the slides of a university lecture, the following phrase got my attention.

> Assuming 10GB network, it takes 2 hours to copy 1TB.

My calculation was as follows.

> 10GB network = 10 gigabits per second network = 10 x 10^9 bits per second ------\> (1)
> 1TB = 10^3 x 10^9 x 8 bits --------------\> (2)
>
> Then the time to copy 1TB data = (2) / (1) = 8 x (10^12) / (10^10) = 800s = 13.33 minutes

I'm not getting 2 hours as the result of the above calculation, seems like I have got something wrong. Can someone please educate me on this? Thanks in advance.

# Answer
If you have hard drives capable of reading /writing 140 Megabytes per second, then it takes about 2 hours with a 10 Gbit network to copy one terabyte. 140 MB per second sounds reasonable. A 1 Gbit network wouldn’t take much longer, but then we’d need to know all the overheads in much more detail for precise answers.
> 1 votes

# Answer
You have just done the calculation with the raw data to be transferred and not taken into account of the overhead of transferring data using networking protocols across any particular network. Almost no networking technology transfers data without an overhead because there is the need for addressing the data, routing the data, dealing with the reliability of the network and so forth.

If we assume a layered packet-switching protocol network, such as the internet, we have many layers, each with its own overhead. Each overhead adds more bytes to the data to be transferred.

`Physical Layer Overhead
`Datalink Layer Overhead
`Network Layer Overhead (IP)
`Transport Layer Overhead (TCP)
`Application Layer Overhead
`The file
`The data```````

Getting a large amount of data from one place to another reliabily on a packet-switching network has quite a large overhead.
> 0 votes

---
Tags: computer-networks
---


# Question
Title: How does a computer direct the processing of information
So I'm reading Introduction to computing systems:From bits and gates to C and beyond, and the author states that a CPU is the mechanism that

> ...directs the processing of information. Which is figuring out what task should get carried out next

My question is: what exactly does he mean when he says that a processor "figures out" the next task that the computer has to carry out? Do we have a model for this from a software perspective?

The way that I currently understand this statement is that by "figuring out", he's referring to the Control Unit, from the Von Neumann model of a stored program computer, but I know there's different computer architectures out there. The author implying that the a computer is essentially a CPU in the same paragraph just adds to my confusion.

> We have used the word computer many times in the preceding paragraphs, and although we did not say so explicitly, we used it to mean a mechanism that does two things: It directs the processing of information and it performs the actual processing of information. It does both of these things in response to a computer program. When we say "directing the processing of information," we mean figuring out which task should get carried out next. When we say "performing the actual processing," we mean doing the actual additions, multiplications, and so forth that are necessary to get the job done. A more precise term for this mechanism is a central processing unit (CPU), or simply a processor.

# Answer
Given that this is an introduction, I wouldn't get too concerned about the wording. It's normal to describe things in general terms, and then go into specifics later.

In a typical computer system, everything ultimately happens because some program running in the CPU made it happen. Even with external events such as interrupts (e.g. someone typed on a keyboard, or a network packet arrived), it is software's responsibility to decide what that means.

Of course, the *central* processing unit isn't necessarily the only processing unit that you have to think about. Modern peripherals (e.g. DMA controllers, network adapters, USB hubs, monitors) tend to be quite "smart", and are often fully-realised computers in their own right.

For now, understand that the central processing unit is the programmable processing unit that a) directs the behaviour of the system as a whole, and b) is where general-purpose computation happens. This picture can be modified (e.g. to account for coprocessors) as you learn more.
> 2 votes

---
Tags: terminology, computer-architecture, education
---


title: Transition Function in MDP

text:
# Question
Title: Transition Function in MDP
I got a question about who and how sets the transation function values in markov decision processes?

I mean when some says that an agent, in real world grid, is going to step up by %80 and left/right by %10 each. How did he know that? Do we have to determine the transition probability for each step or agents have to? Simply, it should be non-deterministic process, so how could someone tell the probability of that transition?

It should be %25 for each direction!!

# Answer
> I mean when some says that an agent, in real world grid, is going to step up by %80 and left/right by %10 each. How did he know that?

There are a couple of scenarios that could lead to an agent stepping up with probability 0.8 and left/right with probability 0.1/0.1. The simplest case, and the one you would likely encounter first is that the agent takes an action determined by the agent's policy but the environment dynamics do not map that *state-action pair* deterministically to a next state, but to a *distribution* over possible next states. Then taking the same action in the same state multiple times will not always result in the same transition. The agent may *choose* to go up, but the environment dynamics assign a small probability that if the agent moves up while in the current state the agent may end up moving left or right instead. The dynamics are a feature of the environment, they are independent of the agent, for example they may be observed probabilities in a video game which was developed by other people than the ones develop the RL algorithm to play it.

Another scenario that could explain the probabilities you asked about is the agent could learn a *stochastic* policy, meaning instead of using a deterministic policy $$\pi:S\to A$$ The agent uses a stochastic policy $$\pi:S\to prob(A)$$ which maps states to *probability distributions* over actions. In this case, even if the environment is deterministic the agent may *choose* to move up with probability 0.8 and left or right with probability 0.1 each.

> It should be %25 for each direction!!

This could happen if the environment dynamics did not allow the agent to make a meaningful choice at that state, or the agent's policy assigned each action an equal probability at that state. RL agent's are often explicitly programmed to behave highly randomly in the beginning, maybe even following a uniform random policy, which would assign a probability of .25 for each direction in each state. The amount of random actions the agent takes is then annealed over time as more information is obtained about the environment and the estimate of the value function is refined.
> 1 votes

---
Tags: algorithms, artificial-intelligence, probability-theory, reinforcement-learning, markov-chains
---


# Question
Title: How/why is switch made from equation to inequality for certificate of optimality for dual problem in linear programming?
I am reading Chapter 7 Linear Programming in *Algorithms* by Dasgupta et al.

I don't get how they switch from an equation to an inequality specifically the part highlighted in red/pink regarding the multiplier $y\_1 + y\_3 ≥ 1$ instead of $y\_1 + y\_3 = 1$

# Answer
> 0 votes
If the required conditions are met then you have

$$ x\_1 + 6x\_2 \leq (y\_1+y\_3)x\_1 + (y\_2+y\_3)x\_2 = y\_1 x\_1 + y\_2 x\_2 + y\_3(x\_1 + x\_2) \leq 200y\_1 + 300y\_2 + 400y\_3$$

By looking at the leftmost and rightmost expressions you get the inequality you want.

---
Tags: linear-programming
---


# Question
Title: Consensus algorithm for imperfect annotators
I'll pose the question in the abstract first and then describe concretely what I'm trying to do.

Suppose I have a set of 1000 000 multiple-choice questions and 10 oracles that can answer the questions. But the oracles are imperfect and don't always answer correctly. Some oracles answer more accurately than others. We don't know which ones are better beforehand though. All answer correctly with probability greater than 60% and less than 100%.

Suppose each oracle answers 100 questions. One in every 10 questions, however, is not a new question but a (random) question that a different oracle has already answered. Which lets you check whether they each got the same answer or not.

Now my question is this, suppose I want to rank the oracles at the end in order of most reliable to least reliable, what's the best metric? Naively, we could just ask, which oracle had the highest proportion of co-coinciding answers out of all the questions they answered that were also answered by another oracle. But this ignores that fact that if an oracle's answer disagrees with a different oracle, it could be the different oracle that was wrong. So I think there needs to be a way to scale the penalty based on the rating of the oracle that disagreed.

Is there an algorithm for this sort of ranking? The two that came to my mind are the Buchholz system, and page rank. Because they both consider secondary comparisons, not just direct comparisons. But I'm not sure how I could apply them.

Concrete context: I have lots of annotators annotating data. We get to send some of the data to multiple annotators, but not all of it. I'm looking for a way to identify annotators who perform poorly so that I can either remove their annotations or reduce the weight of their annotations.

# Answer
Technically speaking, you can't. If you flip all of the oracle outputs, then it maintains the same level of agreement but reverses the ranking.

But this is probably a trivial case that's unimportant in practice. Suppose we can assume that every oracle has accuracy that's at least 50%. Then one approach would be to take all questions that are rated by at least three oracles, take the majority vote among all oracles that rated it, and then measure agreement with that majority. I *think* that should give a correct ordering of the oracles, given enough data (i.e., in the limit, as the number of data points goes to infinity, it should converge to the correct ordering).

In practice you could consider using a more sophisticated model that captures both differences in the accuracy of each oracle and differences in the difficulty of each question. I'm not sure whether this will lead to a major difference in outcomes significantly, but there is tons of work in the research literature you could read about to see what methods have been studied. Here are some example papers:

and probably many more - I'm not expert on this topic, so I have no idea whether these are the most important or useful papers, so I suggest doing a literature search of your own.
> 1 votes

---
Tags: algorithms
---


# Question
Title: My professor claims that inserting the same key into a hash table again will lead to a collision … – Is he really right?
My whole life I thought

> a collision is a situation that occurs when two *distinct* pieces of data have the *same* hash value.

Everything looks a little bit different now: A few days ago we had to analyse common collision resolution strategies to handle the event that at least two keys being hashed to the same slot of an ordinary hash table. As mentioned above, to my knowledge (as well as my intuition) when inserting the very same key $k$ – that is already assigned to a slot of a hash table $T$ – again, nothing (special) happens and $T$ remains unchanged.

I wonder now, if i misunderstood this basic concept, since my professor claims, that inserting the key $k$ into a hash table $T$ again will lead to a collision anyway and we have to analyse some collision resolution strategies in this case too …

Many thanks in advance for your help and clarification!

# Answer
> 1 votes
I suppose one could define the word however you like, but I've always understood it to mean the same thing you are talking about. Here I'm assuming if you try to insert a key the second time, no change is made, as it is already present. If inserting the key caused a second copy to be inserted somewhere, then I think it's more ambiguous and in any formal analysis it would be best to define precisely what you mean by a collision and state whether you consider that a collision, to avoid confusion.

# Answer
> 1 votes
What do you mean by "collision", and what does your professor mean?

If you try to insert a key into a hash table, the usual case should be that there is no key with the same hash in the table yet. In that case, no collision, and you insert the key. If there is a key with the same hash already there, *I* would say that either the same key is already there and I'd say "no collision", or it is a different key that has the same hash by bad luck, and I'd call that "a collision". Your professor *might* use the term "collision" for both cases.

PS. Quite often when you have a hash table with k slots, we use hash(key) modulo k to pick a slot, so until we change the number of slots, hash(key) modulo k is effectively the hash function that we are using, and we could call it a collision if two keys want to be stored in the same slot.

---
Tags: data-structures, hash, hash-tables
---


title: Greedy algorithm for maintaining drugs

text:
# Question
Title: Greedy algorithm for maintaining drugs
> Given $n$ drugs such that each drug $d\_i$ should maintain in interval $\[c\_i,h\_i\]$.We want to minimize number of containers to maintain medicines in compatible interval.

**My answer is as follows:**

I use following greedy algorithm:

in each iteration, for remaining drugs, find an interval that have maximum number of compatible drugs, and remove that drugs, and add to container.

any one can help to find an counter example or proving above idea?

# Answer
> 0 votes
Here is a counterexample.

There are 6 drugs with intervals $$\[1, 5\],\ \[2,8\],\ \[3,8\]$$ and $$\[6, 11\], \ \[6,12\],\ \[9, 13\].$$

We can use containers of volume 4 to cover the first 3 drugs and containers of volume 10 to cover the last 3 drugs. So it is enough to use 2 kinds of containers.

If we use the greedy algorithm, we would first cover $$\[2,8\],\ \[3,8\],\ \[6, 11\], \ \[6,12\]$$ using, for example, containers of volume 7. And then the remaining two intervals $$\[1,5\],\ \[9,13\]$$ that are disjoint will need additional two containers of different volumes to cover.

---
Tags: algorithms, dynamic-programming, discrete-mathematics, greedy-algorithms
---


# Question
Title: Proving that Turing decidable languages are closed under reversal
I need to prove that Turing decidable languages are closed under reversal. I have no idea on how I would prove this. Any suggestions or clues?

# Answer
> 2 votes
Let $L$ be a decidable language and let $M$ be a decider for $L$. Since $M$ *decides* $L$, $M$ always halts and accepts if its input is in $L$ and rejects if its input is not in $L$.

We know that string reversal can be performed by a Turing machine. Let's construct a Turing machine to *decide* if a word is in $L^r=\\{w=w\_0w\_1...w\_n \mid w^r=w\_nw\_{n-1}...w\_0\in L\\}$.

Let $M'$ = "On input $w$
$\quad$reverse the string $w$ to obtain $w^r$
$\quad$run $M$ on $w^r$
$\quad$if $M$ accepts, $ACCEPT$
$\quad$otherwise, $REJECT$ "

Then $M'$ accepts $w$ if and only if $M$ accepts $w$. Since $M$ is a decider, both machines always halt. Then $M'$ decides $L^r$.

# Answer
> 1 votes
Suppose that you have a Turing machine $M$ that accepts a language $L$.

Construct a new Turing machine which, on input $x$, reverses its input and then passes control to $M$. The new Turing machine accepts the reverse of $L$.

---
Tags: turing-machines
---


# Question
Title: Doubt in understanding the time complexities of algorithms to recognize regular expressions
I was going through the text *Compilers: Principles, Techniques and Tools* by *Ullman et. al* first edition where I came across the following table.

The authors justify the table as follows:

> 1. Given a regular expression $r$ and an input string $x$, we now have two methods for determining whether $x$ is in $L(r)$. One approach is to use *Thompson's Construction* to construct an $NFA$ $N$ from $r$. This construction can be done in $O(|r|)$ time, where $|r|$ is the length of $r$. $N$ has at most twice as many states as $|r|$, and at most two transitions from each state, so a transition table for $N$ can be stored in $O(|r|)$ space. We can then use Algorithm 3.4 to determine whether $N$ accepts $x$ in $O(|r| \times |x|)$ time. Thus, using this approach, we can determine whether $x$ is in $L(r)$ in total time proportional to the length of $r$ times the length of $x$.
> 2. (a) A second approach is to construct a $DFA$ from the regular expression $r$ by applying Thompson's construction to $r$ and then the subset construction, Algorithm 3.2, to the resulting $NFA$.
>
> (b) Implementing the transition function with a transition table, we can use Algorithm 3.1 to simulate the $DFA$ on ***input x in time proportional to the length of $x$, independent of the number of states in the $DFA$.***

---

Dependencies:

*Algorithm 3.4*

*Algorithm 3.2*

*Algorithm 3.1*

---

**Doubt:** ***The point where I am having the doubt is that why are the authors only considering the time complexity of just the algorithm 3.1 and not the time of rest of the work done in the $2(a)$ and $2(b)$. Since the worse case space complexity of the DFA is exponential won't creation of the same involve exponential time as well?***

# Answer
The authors are describing the time complexity to determine whether the input string $x$ is in $L(r)$ in the table and not including construction time, that is they list the per-string cost of *using* the DFA or NFA, and not the one-time *construction* cost to build it. In many cases the construction will be done once, and used to recognize strings many times, so it may be worthwhile to sacrifice some time upfront to gain more efficient string recognition afterwards.

You are right to consider the construction cost though. If the automaton will be constructed and used only once, or a small number of times, then the savings in string recognition efficiency may not justify the higher construction time costs.
> 3 votes

---
Tags: algorithms, time-complexity, regular-languages, finite-automata, regular-expressions
---


# Question
Title: Check two balanced binary search trees that sub set of each other
> Given two balanced binary search trees $T\_1,T\_2$. We want to check, are $T\_1\subseteq T\_1$ or not. $T\_1$ have $n\_1$ nodes, and $T\_2$ have $n\_2$ nodes.
>
> Instructor say it can be done in $O(n\_1+n\_2)$ time complexity with $O(\log n\_1+\log n\_2)$ space.

**My idea:**

I use in order traverse on two trees , and compare first node in order traverse $T\_1$ with first node in in order traverse $T\_2$, and etc. if all nodes in $T\_1$ present in $T\_2$ then we say $T\_1\subseteq T\_2$, but i can't prove my space complexity followed from mentioned complexity. Any one can help to guarantee my space complexity be $O(\log n\_1+\log n\_2)$.

# Answer
> 0 votes
When you try to traverse a tree, you start at the root, and you will have to remember all the nodes that you were visiting, to be able to find the next node. If your tree is balanced, then it contains only O (log n) nested notes, so your space requirement for two trees is only O(log n) + O(log m). Unbalanced trees could be nested up to n levels deep, so you could need up to O(n) + O(m) space to traverse both trees.

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