# Question
Title: Approximating the runtime of a practice problem
I'm studying for an algorithms exam and came upon the problem :

```
    for (i = 0; i < n * n; i++) {
        i++;
        for (j = 0; j < (log(n) * log(n) * log(n)); j++) {
            j++;
        }
    }

```

I figure that line 1 costs $ c\_1(n^2) $, line 2 costs $ c\_2(n^2 - 1) $, line 3 costs $ \sum\_{j=0}^{n^2} \log(j)^3 $, and line 4 costs $\sum\_{j=0}^{n^2} \log(j)^3 - 1 $. Am I on the right track? If so, what do the summations get simplified to?

# Answer
> -1 votes
Those lines with the increments matters for the final complexity function, but do not take them in count as it will only make things messy. The function can be simplified as follow:

The outer for runs $\frac{n^2}{2}$ times, and for each of it's iterations it runs $\frac{log^3{n}}{2}$ times.

We can call the complexity function $T(n) = \frac{n^2}{2} * log^3{n}$ which leads to $O(n^2 log^3{n})$.

# Answer
> -1 votes
(Original question started with for (i = 0; i = n\*n; ...) ) The runtime is zero if n = 0, and the algorithm runs forever otherwise.

I suspect strongly that the algorithm that you wrote in your question is not what you wanted to ask about. aajjbb's answer probably answers what you *intended* to ask.

(i = n * n in the for loop is most likely not what you wanted. Using i++ and j++ twice is most likely not what you wanted either. If you change i = n * n to i \< n * n then a good compiler may notice that the statements inside the inner loop are idempotent and reduce the runtime massively. )

---
Tags: algorithm-analysis, runtime-analysis, loops
---


# Question
Title: Possible solutions how to find all points (given by lat, long) that are within a radius from main point
let's say that I have:

* **M - Main point** \- given by coordinates (lat, long)
* **C - Collection of points** \- also given by coordinates (lat, long)
* **R - Radius** \- maximum search distance

I'm trying to find all points that are within a radius from main point (neighbors). `algorithm(main_point, collection_of_points, radius) --> neighbors`

Obvious solution is to calculate distances and select those points, where distance is equal or smaller than R, but I believe there are better options with better performance.

Do you know any possible solutions? I'm open for every idea (not only the best one).

## EDIT:

I should add that I'm looking for solution where points are strongly dynamic (every point is mobile phone or car). I'd like to update point when it's neccessary (it has been moved) so frequency of updates depends on amount of connected devices (so as queries). Let's say that server will get update request every 5 second and query request every 20 second.

---

## Visualisation

# Answer
> 2 votes
You can speed up your search by using a datastructure like a kd-tree or an r-tree. The basic idea is to divide your space into boxes and store the mapping from points to boxes (and back) in a way that allows for quick lookup times. Then you don't have to calculate the distances to *all* points to see which are too far away, you can restrict your search to points in the same (or adjacent) boxes.

But note that the naive approach is actually pretty good in this case, even if it's asymptotically not optimal. CPUs are really good at summing squares and it's trivial to throw more cores at the problem if you need more speed. So unless you're dealing with *many* points, it will be hard to beat.

# Answer
> 1 votes
Depending on your practical situation, once you have examined all the points you might not just determine if they are within the radius, but how long it would at least take for them to either leave or enter the radius. Then you only re-examine a point after that time interval has gone by, and classify it again.

For example, if the radius is 1km, and a car is 2km away, you might figure out that it would take 41 seconds to enter the radius (while not exceeding the speed limit excessively), so if you check every five seconds, you check that car after 45 seconds.

# Answer
> -2 votes
https://en.wikipedia.org/wiki/Spatial\_database#Spatial\_index

This link describes most popular ways to index spacial data.

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


# Question
Title: Algorithms for logical synthesis of multiple output bits?
Karnaugh maps and the Quine–McCluskey algorithm can be good choices for coming up with fairly minimal logical expressions that match the requirements of a truth table.

What if I have a situation where I have $M$ input bits and $N$ output bits though?

A naive way to deal with it would be to solve each output bit independently and come up with $N$ logical expressions. The problem with that is that in circuitry or in CPU implementations, you can do multibit operations which can potentially handle a more optimal logical expression which takes into account several, if not all, of the bits at once.

Are there any algorithms to come up with a fairly minimal logical expression when you have $M$ input bits mapping to $N$ output bits?

# Answer
> 4 votes
as you realize, while universal, Quine-Mcclusky is only a "bitwise" construction method (single bit output) that does not recognize/ exploit common subpatterns for multibit outputs. multibit function construction optimization is a very broad area handled by EE type papers/ applications/ algorithms, there are very many published. the general topic is "logic synthesis". there is also a very broad array of software built for this purpose both commercial and public domain. here is an example of a relatively recent survey of algorithms and also a technique of using known/ previously computed circuits in a library-like context. this paper is useful here in that it refs many of the top systems in use and gives a consolodated view that you seem to be asking for in particular.

---
Tags: algorithms, optimization, logic, digital-circuits
---


title: Can I mix LL and LR parsing?

text:
# Question
Title: Can I mix LL and LR parsing?
I want to go RD parsing with Shunting Yard for expression (for the sake of easier operator precedences and less left-recusion), is that considered no-good because nobody did that before?

# Answer
> 1 votes
Using recursive descent in combination with an operator precedence variant for expressions is a very common approach. You might also want to search for Pratt parsing.

An older, now uncommon technique which combines LL and LR parsing is "left-corner" (LC) parsing, which should also be easy to search for.

In practice, the existence of easy-to-use and efficient LR parser generators makes all of these less powerful techniques much less useful. LC parsing was pretty well obsoleted as a technique with the discovery of the LALR algirithm.

---
Tags: algorithms, reference-request, parsers, lr-k, ll-k
---


title: Complexity of sorting $A+A$

text:
# Question
Title: Complexity of sorting $A+A$
Is there a proof for the **lower bound** of the problem to create a **sorted list of sums** for a given list of integers with length n.

In this \[thread\]\[1\] people discuss solving this problem by sorting the list of integers first and then creating the sums. However none of the solutions seems to be faster than $O(n^2 \log n)$, which is the runtime of just creating all sums and then sorting them.

How would you proof that this is the best you can get or is there a better algorithm to solve the problem.

# Answer
This answer assumes that your question is about computing the sorted order of $\\{ x\_i + x\_j : 1 \leq i,j \leq n \\}$ given a list $x\_1,\ldots,x\_n$.

This problem is a special case of $X+Y$ sorting. According to Wikipedia, no algorithm whose complexity is better than $O(n^2\log n)$ is known for this problem. The decision tree complexity, however, is only $O(n^2)$. (That is, there is an algorithm which asks at most $O(n^2)$ decisions and outputs the sorted $X+Y$; deciding which question to ask could be difficult.)

Your version (with $X=Y$) is no easier than the general case. Indeed, suppose that $X,Y$ are integer arrays. Let $Z = \\{ 4x+1 : x \in X \\} \cup \\{ 4y+2 : y \in Y \\}$. Given the sorted version of $Z+Z$, it is easy to extract $X+Y$ by taking all elements of the form $4m+3$ and extracting $m$.

The $X+Y$ problem is 3SUM-hard. However, this doesn't shed much light on the problem since 3SUM itself can be solved in $O(n^2)$ (and even faster), while the $X+Y$ problem plainly requires $\Omega(n^2)$.
> 7 votes

---
Tags: time-complexity, sorting, lower-bounds
---


title: One-time-pad possible solutions

text:
# Question
Title: One-time-pad possible solutions
I am having a very difficult time trying to understand what exactly this question is asking.

> How many valid English plaintexts are there for the ciphertext message CJU using a length-3, one-time pad of cyclic shifts, (i, j, k)?

If the encrypted question message is CJU and the one time pad is i, j, k would there not be exactly 1 solution? We are given the one time pad i, j, k so we can derive the plaintext simply by some alagebra

`(x + 9) % 26 = 3`

`(y + 10) % 26 = 10`

`(z + 11) % 26 = 21`

Where x, y, and z are the plaintext letters T, Z, J?

I feel like this is a trick question that I am not understanding

# Answer
$(i,j,k)$ is not a specific OPT. It's three variable names that you can use to talk about the key. The question is just asking, "Given all possible three-character OTPs, how many valid English plaintexts are there for the ciphertext CJU?"

In other words, how many different values are there for the triple $(i,j,k)$ such that "CJU" decrypts to an actual English word.
> 2 votes

---
Tags: cryptography, encryption
---


# Question
Title: Data flow equations to determine value dependencies
I need to define the data-flow analysis equations to determine the value dependencies of an statement.

For example:

```
a = 9
b = a + 7
c = b * 2

```

the value of `c` depends on the value of `a`.

I'm sure this is a well known problem in data flow analysis, can any one point to the equations solving this? Static Single Assignment (SSA) form can be used.

# Answer
> 2 votes
Well, it seems that this can be reduced to the Reaching Definition problem, who's equations are:

$REACH\_{in}(S) = \bigcup\_{p \in pred(S)} REACH\_{out}(p)$

$REACH\_{out}(S) = GEN(S) \cup (REACH\_{in}(S) - KILL(S))$

$GEN\[d: y \rightarrow f(x\_1, .., x\_n)\] = {d}$

$KILL\[d: y \rightarrow f(x\_1, .., x\_n)\] =DEFS(y) - {d}$

---
Tags: programming-languages, static-analysis, data-flow-analysis
---


# Question
Title: Why is the video game Braid Turing-complete?
It's written in wikipedia https://en.wikipedia.org/wiki/Turing\_completeness#Games that the video game Braid is Turing-complete.

I've played Braid before but I can hardly reconcile it with Turing completeness. In what sense is it Turing-complete?

# Answer
> 1 votes
Because Braid can simulate a variant of Rush Hour, which is at least PSPACE-hard.

Additionally, Braid itself is undecidable because it can simulate a counter machine which is equivalent to a Turing machine, and thus determining if any general Braid level is solvable is similar to solving the halting problem, which is undecidable.

---
Tags: computability, turing-completeness, computer-games
---


title: NP with a parallelism model?

text:
# Question
Title: NP with a parallelism model?
Can we think of NP using a parallelism model instead of using a "checking relation" without loss of generality?

From what I understand from the problem statement given by Stephen Cook,

> The notation NP stands for “nondeterministic polynomial time”, since originally NP was defined in terms of nondeterministic machines (that is, machines that have more than one possible move from a given configuration). However, now it is customary to give an equivalent definition using the notion of a checking relation, which is simply a binary relation R ⊆ Σ ∗ × Σ ∗ 1 for some finite alphabets Σ and Σ1. We associate with each such relation R a language LR over Σ ∪ Σ1 ∪ {#} defined by LR = {w#y | R(w, y)} where the symbol # is not in Σ. We say that R is polynomial-time iff LR ∈ P. Now we define the class NP of languages by the condition that a language L over Σ is in NP iff there is k ∈ N and a polynomial-time checking relation R such that for all w ∈ Σ ∗ ,w ∈ L ⇐⇒ ∃y(|y| ≤ |w| k and R(w, y)), where |w| and |y| denote the lengths of w and y, respectively.

it appears that the definition of NP given here can be derived from the definition of non-deterministic Turing machines. From this lecture document from the University of Illinois:

> Formally, a nondeterministic Turing machine has all the components of a standard deterministic Turing machine—a finite tape alphabet Γ that contains the input alphabet Σ and a blank symbol ; a finite set Q of internal states with special start, accept, and reject states; and a transition function δ. However, the transition function now has the signature δ: Q × Γ → 2 Q×Γ×{−1,+1} . That is, for each state p and tape symbol a, the output δ(p, a) of the transition function is a set of triples of the form (q, b,∆) ∈ Q × Γ × {−1,+1}. Whenever the machine finds itself in state p reading symbol a, the machine chooses an arbitrary triple (q, b,∆) ∈ δ(p, a), and then changes its state to q, writes b to the tape, and moves the head by ∆. If the set δ(p, a) is empty, the machine moves to the reject state and halts. The set of all possible transition sequences of a nondeterministic Turing machine N on a given input string w define a rooted tree, called a computation tree. The initial configuration (start, w, 0) is the root of the computation tree, and the children of any configuration (q, x, i) are the configurations that can be reached from (q, x, i) in one transition. In particular, any configuration whose state is accept or reject is a leaf. For deterministic Turing machines, this computation tree is just a single path, since there is at most one valid transition from every configuration.

This mentions the notion of a computation tree:

Thus, suppose I were to have a machine that was able to compute all of the non-deterministic branches in parallel such that the bounded running time is $O(poly(n))$. Is this an equivalent of a Turing machine such that a language that is accepted by this machine is within $NP$?

In a sense, we can also see that if a deterministic machine were to choose the "right" branch by chance that it's somewhat equivalent to the notion of an oracle. This seems like it's similar to the "checking relation" in the sense that we need only compute one branch's result in order to determine acceptance of the answer or rejection. Is this intuition right?

And, in addition, can the deterministic machine can simulate the computation of the non-deterministic machine in $O(2^n)$ time?

**Edit:** If we make the addition that one of the paths are guaranteed to accept, then is the machine now equivalent to NP?

# Answer
Your description of NP is still missing the accept criterion. For example you might decide to accept the input exactly in case all computation paths accept. This would give you the class coNP instead of NP. Or you might decide to accept the input exactly in case half of the computation paths accept. But for NP, the accept criterion is that there exists at least one computation path which accepts. Other than that, your parallelism model of NP is perfectly fine. And yes, the deterministic machine can simulate the computation of the non-deterministic machine in $O(2^n)$ time!
> 4 votes

---
Tags: complexity-theory, time-complexity, computation-models, np, parallel-computing
---


# Question
Title: Why does the state remain unchanged in the small-step operational semantics of a while loop?
Usually I see that in the structural operational semantics representation for the while loop, the program state don't change:

$(while \\\> B \\\> do \\\>S, \sigma) \rightarrow (if \\\>B \\\> then \\\>S; (while \\\> B \\\> do \\\>S) \\\> else \\\> SKIP, \sigma)$

For me, this not intuitive, if the state don't change (i.e. the status of the memory stays the same) then $B$ will continue to stay true and the program will never terminate.

Can anyone please explain why the state don't change in this rule?

# Answer
> 10 votes
In programming language semantics, the notion of program state is not a vague philosophical notion, but a very precise mathematical one. A *state* $s$ in this small-step operational semantics is a partial function

$$ s : \mathbf{Var} \hookrightarrow \mathbb{Z} $$

that records the values of the variables. So if $s\\, x = v$, then variable $x$ has value $v$. The state is necessarily a partial function, since it only makes sense to record the values of variables that actually occur.

The unfolding axiom

$$ \langle \texttt{while}\\; b\\; \texttt{do}\\; S,s \rangle \Rightarrow \langle \texttt{if}\\; b\\; \texttt{then}\\; S; \texttt{while}\\; b\\; \texttt{do}\\; S \\; \texttt{else skip},s \rangle$$

is simply telling us that we unfold a while-loop into a conditional statement, one of whose branches contains the loop. No variables will change their value because of this, and for this reason the state does not change.

# Answer
> 10 votes
The state can change in subsequent reduction steps because on the right hand side of

$$ \langle while\ B\ do\ S, \sigma \rangle \quad\rightarrow\quad \langle if\ B\ then\ ( {\color{red}{S}};\ while\ B\ do\ S )\ else\ skip, \sigma\rangle $$

the $while$-loop is guarded (preceeded) by $S$. The computation of $S$ may change the state so that the condition $B$ can evaluate to $\mathsf{false}$.

# Answer
> 9 votes
The state $\sigma$ does not change when we consider $B$ to decide whether to perform one iteration of the loop, but it can *change later* when we run the body $S$. And so, the next time we consider $B$, there can be a change of $\sigma$.

---
Tags: formal-languages, programming-languages, formal-methods, operational-semantics
---


# Question
Title: Karger's algorithm: why does every vertex have degree at least the number of edges crossing a min cut?
I'm currently watching a video on the analysis of Krager's Algorithm, and I am confused about something.

The analysis goes as follows:

Fix a min cut $(A,B)$.

Let $k$ = # of edges crossing $(A,B)$ , these edges will be called $F$

Let $S\_{i}$ be the event that an edge of $F$ is contracted in iteration $i$.

For the first iteration, $\Pr \[S\_i\] = \frac{\text{# of crossing edges}}{\text{# of edges}}=\frac{k}{m}$,

where $k$ is the number of crossing edges, and $m$ is the total number of edges.

Here's where I get confused:

**Observation**: The degree of each vertex is at least k

**Reason**: Each vertex v defines a cut $\left( \\{v\\}, V - \\{v\\} \right)$

I don't really understand. The reason given for his observation doesn't make much sense to me. Why would the degree of each vertex be *at least* the number of edges crossing our min cut (A,B)?

# Answer
> 5 votes
You pretty much have the answer in front of you.

For any vertex $v$, the cut $\left(\left\\{v\right\\},V\setminus\left\\{v\right\\}\right)$ has $\text{deg}(v)$ crossing edges.

If there exists a vertex $v$ with degree $\<k$, then its corresponding cut has less than $k$ crossing edges, contradicting the minimality of $(A,B)$.

---
Tags: algorithm-analysis, randomized-algorithms, minimum-cuts
---


# Question
Title: What is the optimal way to cut B chocolate bars to share equally between N people?
What is the optimal way to cut B chocolate bars to share equally between N people?

Here is an example of different cuts for B = 5 chocolate bars and N = 6 people.

Strategy 1: cut each chocolate bar in 6 equal parts and, then, give 5 parts for each person. Number of cuts: 5 x 5 = 25.

Strategy 2: cut 3 bars in 2 equal parts and cut 2 parts in 3 equal parts and, then, give 1/2 bar and 1/3 bar for each person. Number of cuts: 3 x 1 + 2 x 2 = 7.

What is the optimal solution for the general problem?

Thanks, Humberto.

# Answer
If optimal means having less cuts, can do this:

```
1. Line the chocolate bar up.
   [bar 0][bar 1][bar 2]

2. Treat that as a big bar.
   [big bar            ]

3. Divide the big bar equally.

```

Only about N cuts needed (if B \< N)

If B \> N, just give everyone equal number of bars. Then divide the remaining bars with the above algorithm.

Or 1 cut:

```
[bar 0]
  [bar 1]
    [bar 2]

cut vertically once.

```

I am sure there might be easier way to line it up... if optimal means that we don't need to use a ruler to measure the chocolates in real life.
> 1 votes

# Answer
Considering the minimum common multiple of N and B: mcm, it is the worse case for the given N and B. (You will find no N+B where the optimal cut is worse than its MCM)

> e.g. B=5, N=6 -\> mcm = 30

The value of mcm can be factorized into prime numbers (factors). Each of the mcm little chunks could be grouped using those values and minimize the number of cuts.

Each factor can be used or not depending of your custom rules, in this case, allowing only chunks of equal size for all N persons.

Example of algorithm:

```
orderFactorsDecreasing(factors)
remainingB = B
foreach (f in factors)
{
    while ( acceptChunkGrouping( f ) ) // yes, can be flattened easily.
    {
        distributeToEachPerson( f*B/mcm )
        remainingB -= N *  (f*B/mcm )
    }
}

```

> Following your example of B=5, N=6, mcm=30: factorization of 30 is: (1), 2, 3, 5, 6:
>
> * Chunks of 6\*(1/6) -\> rejected as there are no N x (1/6) chunks available.
> * Chunks of 5\*(1/6) -\> rejected as there are no N x (5/6) chunks available.
> * Chunks of 3\*(1/6) -\> Allowing N x (3/6) -\> remaining 2 bars.
> * Chunks of 2\*(1/6) -\> Allowing N x (2/6) -\> remaining 0 bars.
> * chunks of 1\*(1/6) -\> rejected as there are no N x (1/6) chunks available.

To force each person having chunks of the same size, the test could be:

```
var chunksPerBar = floor(1 / (factor*B/mcm))
if (chunksPerBar*remainingB >= N) then acceptTheFactor
else rejectTheFactor

```

> An other example:
>
> * B=26, N=4;
> * mcm = 52;
> * factors: 13, 2, (2), 1
>     + 13 is rejected.
>     + 2 is accepted, giving 6 full bars to each N persons.
>     + 1 is accepted, giving 0.5 bars to each N persons.
> * Each person get 6 full bars + 1/2 bar.
> -1 votes

---
Tags: algorithms, optimization
---


# Question
Title: Why does computer have branch and jump instructions
I could guess why computers have arithmetic operations like add, sub, and mult instructions. It is to compute numbers, but I don't get why branch and jump instructions exist. I am asking what theory or purpose for implementing branch and jump instructions is there? I've tried to get rid of branch and jump instructions and what effect it will cause on the computation, but I could not get the result.

# Answer
> 1 votes
A very short example.

Let's say you need to write a program that get three variables:
`a` is an integer.
`b` is an integer.
`op` is an operand (can be only `+` or `*`).

Lets say you know how to calculate `a+b` and also `a*b`.
You also know how to process what `op` is (`+` or `*`).
All that is left is to perform the relevant calculation.

How do you suggest doing this without a `jump` or `branch`?

# Answer
> 9 votes
Theoretically speaking you do not need any branch and jump instructions. This is so because you can encode them into artihmetic. For instance, instead of writing

```
if p:
   x = a
else:
   x = b

```

you can write (assuming that $0$ stands for "false" and $1$ for "true"):

```
x = p * a + (1 - p) * b

```

Gödel was the first to have realized that when he proved his incompleteness theorem, namely that arithmetic sufficies for all of programming, *theoretically speaking*. So in this sense you are correct.

**Supplemental:** we do need some sort of iteration or recursion, as was noted in the comments. By "arithmetic" here I mean general recursive functions which have recursion built in. There is a form of "conditional" in recursion, namely the distinction between zero and a successor.

*However*, it is *impractical* to insist that arithmetic is somehow the most important thing. There are *many* different ways to do computation. For instance, we do not even need any arithmetic or recursion, we could use just pure $\lambda$-calculus, which is a pure theory of functions, without *any* numbers, booleans, or any other form of data (they can all be built up). Which paticular form of computation should be used actually depends on many factors: What does the hardware support? What makes programming most maintainable? How do we make programs efficient? And so on. The actual programming languages and CPUs that we know today are the result of many years of experience. It's turned out that it's better to have conditional branching than not.

# Answer
> 2 votes
There are many, many different ways to perform computations, but any general-purpose computer has some form of conditional execution, and some way to repeat a computation with different data.

We have invented many models of computation, and it turns out that all the ones we think of as sufficiently powerful are equivalent. A sufficiently powerful model of computation is said to be Turing complete. There are of course models of computation that aren't Turing complete, but they feel restricted: you can't do as much with them. Pretty much all programming languages are Turing complete if you ignore the fact that computers have finite memory (and reasoning about computers with large but finite memory is so hard that we normally approximate the memory as infinite).

A computer that doesn't have any way to compute conditionally or to repeat a computation can effectively perform only the particular sequence of instructions that it was programmed to do. That lets you define some simple operations, but not much. If there's conditional execution but no repetition, then the program can behave differently depending on the data, but there is effectively a finite number of different behaviors. If there's repetition but no conditional execution, then a program either always terminates or never terminates, there's no way for a program to terminate or not depending on the data. To write all possible programs, both conditional execution and repetition are necessary.

In practice, to write most interesting programs, both conditional execution and repetition are necessary. Exactly what programs you can write without them depends on what basic operations you allow, but it won't be much. For example, if you only have the basic four operations on integers (`+`, `-`, `*`, `/`) then something as simple as primality testing can't be done without repetition (e.g. to *repeat* trial division) and branching (to exit the program once the answer has been found).

Conditional execution and repetition aren't enough to be Turing complete: you also need some way to use an unbounded amount of memory. But that's a story for another time.

In low-level imperative programming, conditional jumps are the usual way to implement conditional execution and repetition (you repeat by jumping to an earlier point in the program). In a higher-level imperative program, repetition is expressed via looping.

In other models of computation, conditionals and repetition may be derived from other primitive functionality in a non-obvious way. For example, one of the most important models of computation, the lambda calculus, does not have a conditional feature or a repetition feature per se. Lambda calculus has just one computation rule, called beta reduction: “if you apply the function that maps $x$ to $M$ to the argument $N$, then the result is $M$ in which $x$ has been replaced by $N$”. It indirectly permits repetition because there can be many occurrences of $x$, and so $N$ is repeated. It indirectly permits conditional execution because the lambda calculus doesn't distinguish between data and code, and the argument of a function can be treated as a function and executed, resulting in behavior that depends on the argument. So conditionals, repetition and unbounded memory (like repetition, arising from the repetition of the argument in the substitution) are all present.

In fact, conditional branching and unbounded memory are all you need to make a Turing complete model of computation. A suitably-chosen one-instruction set machine is Turing complete. Many such instructions involve a subtraction in addition to the conditional branching, because it's convenient, but arithmetic is not actually necessary, it's just convenient to access memory. Turing machines, another very important model of computation, doesn't include anything like arithmetic, just conditional branching (inside the finite automaton, conditional because it depends on the value read from the tape) and the tape for memory. Likewise the lambda calculus doesn't have anything like arithmetic in its rule, but you can build arithmetic above the lambda calculus.

---
Tags: algorithms, turing-machines, computation-models
---


# Question
Title: Decidability of Equality of Radical Expressions
Consider terms built from elements of $\mathbb Q$ and the operations $+,\times,-,/$, and $\sqrt\[n\]{\\,\cdot\\,}$ for each natural number $n$. Given the promise that two terms are well-formed -- that is, there is no division by zero, and no even roots of negative numbers -- is there an algorithm which decides when the two terms are equal?

A related question was posted here, but it is more general (as it allows arbitrary exponentiation, rather than just by rational numbers).

# Answer
1. Algebraic numbers are solutions of polynomials with rational coefficients.
2. $+,\times,-,/$ of algebraic numbers result in algebraic numbers because algebraic numbers form a field (). This means nested radicals are algebraic numbers too ().
3. Nested radicals can be denested by algorithm (,).
4. Each algebraic number of degree $n$ can be uniquely represented as a $n$ by $n$ matrix of integers under a suitable basis (for example, $\[1,x, (x^2+1)/2\]$). This representation allows symbolic evaluation of $+,\times,-,/$ by matrix addition, multiplication, and inverse (p.159 of ,,).
5. Two terms are equal if their unique representations are identical.
> 3 votes

# Answer
Yes.  By the real-number analogue of the Tseytin transformation, that
reduces to the existential theory of the reals, which is in PSPACE by

page 291 and the bottom of page 290 from this paper
and
the answers to this question

.
For all real numbers $x$, $\sqrt{x^2}$ and $x$ are both well-formed and    $\sqrt{x^2} = x$  if and only if  $0\leq x$  ,    so testing *inequality* reduces to your problem.        I'm not aware of any better upper bound for testing inequalities of sums-of-square-roots than this paper, which puts it in the counting hierarchy.
> 3 votes

---
Tags: computability, undecidability, number-theory, equality
---


# Question
Title: Are the words "expression" and "term" interchangeable in programming language theory?
When describing the syntax of a given programming language the words "expression" and "term" are often used to seemingly describe the same things. Are these words interchangeable in the context of programming languages?

# Answer
The two words *expression* and *term* have largely the same sets of possible meaning, but in a specific presentation, they may not be synonyms.

In rewriting theory, a *term* is something that conforms to a certain syntax, and for which a notion of computation (rewriting) is defined. In programming language theory, *term* can mean specifically one of the two aspects. And so can *expression*. Which means which depends on the author, and not all authors use both words in this way.

* One possible meaning of the word is “something that can be computed”. In this sense, if the computation terminates, you end up with a *value*.
* Another possible meaning of the word is “something that conforms to a certain syntax”. There is often a computation mechanism defined over this syntax, but not always.

In the theory of a programming language, there are often multiple syntactic objects: the core language, types, kinds, objects, classes, modules, interfaces, … Something like `function x : int => x + 1` may be a *core term* which contains the *type term* `int`, or a *core expression* which contains the *type expression* `int`. It's common but not universal to use one of the two nouns to mean “core” (and “core” is my choice of terminology), e.g. “`function x : int => x + 1` is an expression” or “`function x : int => x + 1` is a term”. Different authors use different words; communities of a specific language tend to align on terminology, but that isn't systematic.

For example, in the world of ML, “expression” with no qualifier is normally reserved for the core language, and there are additionally “module expressions” in the module language, as well as “type expressions” and “signature expressions”. A “term” can be anything conforming to one of the syntactic forms, although many authors (e.g. the SML definition) don't use “term” at all.

But in Coq, a “term” is the most important syntactic form. Due to the nature of the language, the syntax of types is the same as terms. The Coq manual uses “expression” to designate any family of syntactic form.

If you're reading a text on programming languages, the meaning of the words should be explained or (in less formal texts) clear from context. If you're writing a text, try to use the terminology that's common in your community, and always make sure that the definitions you use are clear.
> 11 votes

# Answer
These terms do not have any universal meaning in computer science theory. They are popular choices for the names of productions in particular grammars, but they only have meaning within the context of a specific grammar. By convention "expression" is often used for the top-level construct in a grammar (so that in some sense "everything is an expression"), while "term" is used for a much more specific construct, often an operand to an addition or subtraction operator. The word "term" may be used with other meanings in other contexts, for example it has a particular meaning in some flavours of BNF.
> 6 votes

# Answer
In predicate logic, you can have both function symbols and relation symbols. The terms in this context are the *valid* combinations of variables, constants and function symbols. The valid combinations of terms, relation symbols and equality are called atomic formulas, the valid combinations of atomic formulas, logical operators and logical quantifiers are called formulas.

In programming languages like C or C++, things like typedefs or function definitions and declarations are probably not expressions. Control structures like `for`, `if`, and `while` are probably not expressions either (because they don't need to be terminated by a semicolon, and because they don't have a type). The language specifies exactly what counts as an expression, and I guess that an expression (in C/C++) always has a type.
> 2 votes

---
Tags: terminology, programming-languages, functional-programming
---


# Question
Title: Why does counting sort copy the input elements?
When I was reading about counting sort in *Introduction to Algorithms* for the first time, I stopped reading after the step where they calculate the number of each element in the input array. It's the first thing we do after allocating an auxiliary array.

I was sure the algorithm would look like this:

```
public static int[] countingSort2(int[] input, int k) {
    // 0 <= input[i] < k
    int[] result = new int[input.length];
    int[] auxiliary = new int[k];

    for (int j = 0; j < input.length; j++) {
        auxiliary[input[j]] = auxiliary[input[j]] + 1;
    }

    int resultIndex = 0;
    for (int i = 0; i < auxiliary.length; i++) {
        if (auxiliary[i] != 0) {
            for (int m = 0; m < auxiliary[i]; m++) {
                result[resultIndex++] = i;
            }
        }
    }
    return result;
}

```

But of course, the canonical implementation is different:

```
public static int[] countingSort(int[] a, int k) {
    int c[] = new int[k];
    for (int i = 0; i < a.length; i++)
        c[a[i]]++;

    for (int i = 1; i < k; i++)
        c[i] += c[i - 1];

    int b[] = new int[a.length];
    for (int i = a.length - 1; i >= 0; i--)
        b[--c[a[i]]] = a[i];

    return b;
}

```

I wonder why they needed to fill the auxiliary array *again* and then put elements of the input array to the output array.

# Answer
They do not *need* to do it this way, but they might have found it more elegant.

Their idea is not:

> Put every element `j` in `0..k-1` into `b` exactly `c[j]` times.

But rather:

> Use the counts to compute the position of every `a[i]` in `b`.

That is what the second loop is for: it subsequently computs the offsets for the block of elements `i` in `b`.
(The should use `j` here to avoid confusing, but well.)

As KWillets notes, the latter idea lends itself¹ better to sorting more complex data, say objects, by an integer key; then you would need to copy the references in proper order. Note how it is even stable!

On the other hand, if you do not need resp. make use of this, I expect the first idea to be much more efficient in practice: observe how the second implementation makes non-sequential accesses to arrays `b` *and* `c` which may cause a lot more cache misses than the alternative.

---

1. The given implementation can only sort integer arrays, of course.
> 2 votes

---
Tags: algorithms, sorting, algorithm-design
---


# Question
Title: Single Source Shortest Paths using Product Construction
I am trying to solve a bounded SSSP problem as follows:

> Given a connected weighted graph with non-negative edges (might have cycles), find the shortest path from a vertex s to a vertex t with **at most** k edges.

I have done some research on this problem. All proposed solutions point to using Bellman-Ford's algorithm by modifying its outer loop to perform k iterations. This will yield a worst case time complexity of O(VE).

I wish to know if it is possible to solve this in O(k * (V+E)LogV) or better using Dijkstra's algorithm?

I have seen this post that discusses the same problem. Dijkstra's algorithm to compute shortest paths using k edges?

However, I don't know how to prove the correctness of the solution that uses product construction.

Could someone please advise me?

# Answer
The product construction means that you don't just store the shortest distance to a given node, but store the shortest distance to reach a node on a shortest path with $k$ nodes. You certainly don't need to explicitly construct the edges of the product graph. But since the algorithm will produce $k\cdot|V|$ shortest distances of this form, it seems as if you must at least construct an array of this size to hold those distances. However, this is not exactly true, because only the distances different from $\infty$ must be stored.

So you could either generate the nodes of the product graph on the fly and store them in a map (i.e. something like a red black tree), or first determine the reachable part of the product graph by a suitable algorithm. If you only care about the complexity and not about the practical efficiency, then the solution with the map is simpler and still good enough. That map can then also be used for Dijkstra's algorithm itself to determine the next node on which the algorithm continues.

The disadvantage compared to Bellman-Ford's algorithm is that you can't reuse the memory from the previous iteration for the current iteration, because Dijkstra's algorithm will not produce all distance $j-1$ paths before producing distance $j$ paths. But maybe it is possible to modify Dijkstra's algorithm to do exactly this, and this might indeed yield the most efficient algorithm for your problem.
> 1 votes

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


# Question
Title: Proof that PDA's with different definitions have same expressive power
Let $P$ be a ***push down automaton*** $(Q,\Sigma,\Gamma,\delta,q\_s,F)$, where

* $Q$ is the set of states,
* $\Sigma$ is the input alphabet
* $\Gamma$ is the stack alphabet
* $\delta$ is the transition function with signature $Q\times(\Sigma\cup\\{\epsilon\\})\times(\Gamma\cup\\{\epsilon\\})\to\mathcal{P}(Q\times(\Gamma\cup\\{\epsilon\\}))$
* $q\_s$ is the initial state
* $F$ is the set of acceptable states.

We suppose that at every transition at 1 symbol of the input string is read, 1 symbol of the stack is popped, 1 symbol is pushed and we can change our state. A general (informal) definition of the acceptance of a string is: we accept the string when we end in an acceptable state with an empty string (whatever the stack contains).

However, there are ***other possible definitions*** of the acceptance of a string by $P$. Some possibilities:

* The string is accepted when both the string and stack are empty (even when the current state would not be an acceptable state).
* The string is accepted when both the string and stack are empty and we are in an acceptable state.

One could also change the definition of the PDA as follows:

* One can push more than 1 symbol to the stack in 1 transition.

My question is, how can 1 (both formally and informally) proof that ***the power of the PDA does not change by using another definition?*** Alternatively, one could say that the languages determined by the different PDA's are the same.

# Answer
You prove it the same way you prove that any two models of computation are equivalent: you show that, for every machine of type A, the language accepted by that machine is accepted by some machine of type B, and vice-versa. Sometimes, this is trivial, for example if A is just a restricted version of B (e.g., proving that every language accepted by a DFA is accepted by an NFA). In other cases, it involves simulating the features or acceptance criteria of A using B (e.g., proving that every language accepted by an NFA is accepted by a DFA by using the subset construction).

If you're looking for details of how to prove all the equivalences mentioned in your question, then I think your question is too broad. You should be able to find some of them in any good textbook that covers PDAs, and you'll probably find the rest as exercises because the specific proofs probably use the same general principles.
> 4 votes

---
Tags: automata, proof-techniques, pushdown-automata, simulation
---


# Question
Title: How many range are completely inside a given range
I have a list of ranges *ai , bi*. And I have many queries in the form of a range *c, d*, which asks how many ranges ( ai, bi ) are completely inside *c, d*.

c \<= ai & bi \<= d

There are so many of these queries. So I want to know if there is an algorithm that answer each query in a time complexity that is better than *O(n)*.

My first attempt was to use two sorted list. One with respect to the end point of ranges and the other with respect to the start point of ranges. This way I can find how many ranges start after *c*, and how many ranges end before *d*. But I couldn't find a way to calculate their union. So this attempt was unsuccessful.

My second idea was to use Interval Tree. Interval Tree can help you find whether any ranges overlap with a certain range. I couldn't come up with a modification so that it gives me what I want instead of just overlaps. My best attempt had time complexity of *O(n)* for each query. For example if the ranges were are all equal my query would take *O(n)* but this wasn't the only example and there were a lot of other cases that the result of each query would take *O(n)*.

So now I am wondering whether there is a data structure or an algorithm that helps me do these queries in sub-linear time?

# Answer
I've given an answer to the question with the similar idea here. I'll recall the most important parts of the data structure in this answer. It looks similar to the solution with wavelet trees by Jouni but, I think, is easier to code (arguable).

Here is the data structure which is sometimes called Merge Sort Tree. It is basically a segment tree where each node stores a sorted subarray. This structure requires $O(n \log n)$ memory (because there are $\log n$ layers and each of them requires storing $n$ numbers). It is built in $O(n \log n)$ as well: you just go bottom-up and for each inner vertex merge sorted lists of its children.

Here is an example. Say `1 5 2 6 8 4 7 1` be an original array.

```
|1 1 2 4 5 6 7 8|
|1 2 5 6|1 4 7 8|
|1 5|2 6|4 8|1 7|
|1|5|2|6|8|4|7|1|

```

This structure can answer queries of form "how many numbers $\leq x$ are there in range $\[l, r\]$" in $O(\log^2 n)$ time: just make a reqular query to a segment tree (traversing $O(\log n)$ nodes) and make a binary search to know how many numbers $\leq x$ are there in that node (additional $O(\log n)$ from here).

This can be speed up to $O(\log n)$ using Fractional Cascading technique, which basically allows you to do the binary search not in each node but only in the root. However it is complex enough to be described in the post.

The original problem is reduced to this one exactly the way Jouni explained: having your segments sorted by left endpoint, you create the array of left endpoints $A$ and a Merge Sort Tree of right endpoints $B$. Use the binary search on $A$ to find the range, $\[l, r\]$, of indexes of left endpoints lying in $\[c, d\]$ and make a query "how many numbers $\leq d$ are there in range $\[l, r\]$ in array $B$".
> 8 votes

# Answer
There are probably existing data structures for this problem, but I am not familiar with them. Instead, I will just create something with the tools I am familiar with.

Assume that the ranges are stored in arrays $A$ and $B$ so that $A\[i\] = a\_i$ and $B\[i\] = b\_i$ and that the ranges are sorted by their starting points. Given a query range $\[c, d\]$, we can binary search array $A$ to find the interval $A\[sp, ep\]$ of ranges starting in $\[c, d\]$.

To solve the counting version of the problem, we store array $B$ as a wavelet tree. We can then report the number of endpoints $b\_i \le d$ in interval $B\[sp, ep\]$ in $O(\log n)$ time.

If we also want to list the ranges contained in $\[c, d\]$, we can do that in $O(\log n)$ time per range by using the wavelet tree. We can get the time down to $O(1)$ / range with a range minimum query data structure over array $B$. We find the smallest value $b\_i$ in $B\[sp, ep\]$, check whether $b\_i \le d$, and then continue recursively to $B\[sp, i-1\]$ and $B\[i+1, ep\]$.

The solution based on wavelet trees assumes that the endpoints are integers. If they are not, we can simply map them into integers by binary searching the sorted array of endpoints.

**Example.** We have seven ranges: $\[2, 6\]$, $\[3, 4\]$, $\[3, 5\]$, $\[4, 8\]$, $\[5, 6\]$, $\[6, 7\]$, and $\[8, 9\]$. The arrays are therefore $A = (2, 3, 3, 4, 5, 6, 8)$ and $B = (6, 4, 5, 8, 6, 7, 9)$.

Assume that the query range is $\[c, d\] = \[3, 6\]$, which contains three ranges: $\[3, 4\]$, $\[3, 5\]$, and $\[5, 6\]$. By binary searching array $A$, we find that the starting points of the ranges starting in $\[3, 6\]$ are in the interval $A\[2, 6\] = (3, 3, 4, 5, 6)$. The corresponding interval of endpoints is $B\[2, 6\] = (4, 5, 8, 6, 7)$.

The root of the wavelet tree partitions array $B$ into "small" and "large" values and stores the partitioning as a bitvector. Its left and right subtrees are wavelet trees for the subsequences of "small" and "large" values, respectively. If we consider values $\le 5$ "small", the bitvector at the root is $V = (1, 0, 0, 1, 1, 1, 1)$, and the "small" and "large" subsequences are $S = (4, 5)$ and $L = (6, 8, 6, 7, 9)$, respectively.

Bitvector $V$ supports $rank(i, b)$ ("how many $b$s are there in prefix $V\[1, i\]$") queries in constant time.

We want to count the number of values $\le 6$ in $B\[2, 6\]$. As $6$ is a "large" value, we first determine the number of "small" values in the interval as

$rank(6, 0) - rank(2 - 1, 0) = 2 - 0 = 2$.

Then we determine the number of "large" values $\le 6$ in $B\[2, 6\]$ recursively by going into the right subtree. Interval $B\[2, 6\]$ in the root corresponds to interval

$L\[rank(2 - 1, 1) + 1, rank(6, 1)\] = L\[2, 4\] = (8, 6, 7)$

in the right subtree, and the number of values $\le 6$ in $L\[2, 4\]$ is also the number of "large" values $\le 6$ in $B\[2, 6\]$. The recursion eventually stops, reporting one such value. Hence the number of values $\le 6$ in $B\[2, 6\]$ is $2 + 1 = 3$.
> 4 votes

# Answer
You could simply use a multidimensional index, such as an R-Tree or R\*tree, which can be used to perform inclusion queries for rectangles or cubes. In your case, you would simply use a 1-dimensional version of these trees.
> 0 votes

---
Tags: algorithms, data-structures, intervals
---


# Question
Title: Are LR(k) languages and DCFLs equivalent?
In the familiar book of *Theory of Computation* by *M. Sipser*, the author proved that for *endmarked* context-free languages, the set of languages having a LR(k) grammar for a predefined $k \in \mathbb{N}$ (denoted as LR(k) languages) *is* the set of deterministic context-free languages (denoted as DCFL).

My question is also about the relation of those two sets, but in the broader field of all context-free languages. Specifically, *are LR(k) languages and DCFLs equivalent?* And, in which book can I find a proof?

For now, I just have some surrounding facts as followed. Also in the book, the author proved that LR(0) languages *strictly* belong to DCFLs, and LR(k) languages belong to DCFLs for all $k \in \mathbb{N} \setminus \\{0\\}$. In addition, it's obvious that LR(a) languages belong to LR(b) languages for all $0 \le a \< b$. Recently, I've got an unchecked fact from here: LR(1) languages and DCFLs are equivalent.

# Answer
> 8 votes
According to Wikipedia:

* For every fixed $k \geq 1$: A language has an LR($k$) grammar iff it is DCFL.
* A language has an LR(0) grammar iff it is DCFL and has the prefix property (no word is a prefix of another word).

The first property is proved in Knuth's original paper, in Section V on page 628.

---
Tags: formal-languages, context-free, lr-k
---


# Question
Title: Are Huffman trees and optimal binary search trees for solving the same problems?
**Huffman trees** are used in a specific application - Huffman coding - for finding the minimum-expected-length binary-coding for a set of strings, with respect to a probability distribution over the string set.

**Optimal binary search trees** (as defined in CLRS's Introduction to Algorithms) are used for finding the optimal binary search tree for a set of elements, so that the expected look-up time is minimized, with respect to a probability distribution over the set.

Noticing how similar they are to each other, I have some questions

1. Is it correct that the applications of **Huffman trees** are not limited to Huffman coding?

What kinds of problems can **Huffman trees** be used to solve?

Can **Huffman trees** be used for solving the same problems that **optimal binary search trees** can?

Can **optimal BSTs** be used for solving the same problems that **Huffman trees** can?
2. One difference I notice between Huffman trees and optimal binary search trees is that

* In **Huffman trees**, all the elements are stored in the leaves, so that a successful search always end up in a leaf.
    * In **optimal binary search trees**, not all the elements are stored in the leaves, and a successful search may end up in an internal node.

So if Huffman trees and optimal BSTs can both solve a problem, then is the Huffman tree always higher than an optimal BST, and thus will the Huffman tree take longer on average to look up an element?

Thanks.

# Answer
Both Huffman trees and optimal binary decision trees can be though of as mechanisms for playing the (probabilistic) 20 questions game optimally. In the 20 questions game you are given a set of items $X$ and a probability distribution $\pi$ over $X$, and then you are presented an unknown item $x \sim \pi$. Your task is to discover $x$ using the least expected number of questions. The difference lies in which questions are allowed:

1. In the case of Huffman trees, you can ask any Yes/No questions of your choice.
2. In the case of BSTs, you can ask a 3-way question of the form "$x \< t$, $x = t$, or $x \> t$?".

Neither Huffman trees nor binary search trees are described in this way usually. Instead:

1. Huffman trees can be viewed as a way of *coding* elements drawn from $\pi$ in a prefix-free way (no codeword is the prefix of another). The code of an element consists of the path that takes you from the root to the appropriate leaf ($0$ for taking a No edge, $1$ for taking a Yes edge).
2. Binary search trees allow searching $x$ inside a list $y\_1,\ldots,y\_n$. The answer is either $y\_i$ (this corresponds to items stored in internal nodes), or $y\_i \< x \< y\_{i+1}$ (this corresponds to items stored in leaves; this includes the cases $x \< y\_1$ and $y\_n \< x$).

This should answer most of your questions.
> 6 votes

---
Tags: data-structures, search-trees, huffman-coding
---


# Question
Title: Prove or disprove the bound given the recurrence relation
Given the following recurrence relation,

$T(n) = 2 T(\frac{n}{2}) + f(n)$,

where $f(n) = \Omega(n^2)$, I'm asked to prove or disprove that $T(n) = O(f(n))$.

If I'm allowed to restrict my discussion within the special cases in which that $n = 2^k$ for positive integer $k$, how can I prove or disprove the proposed bound, $T(n) = O(f(n))$?

As a side information, if $f(n) = \Theta(n^2)$, then we can show that $T(n) = \Theta(f(n))$ by the Master Theorem. But how should I handle the subtlety of this case with big-Omega and big-O?

Thanks for the help.

# Answer
Your recurrence relation is covered by case 3 of the master theorem:

> If
>
> * $T(n)=aT(\frac{n}{b})+f(n)$ where $a\geq 1$ and $b\>1$
> * $f(n)\in\Omega(n^c)$ where $c\>\log\_b a$
> * $af(\frac{n}{b}) \leq k f(n)$ for some constant $k\<1$ and sufficiently large $n$
>
> then $T(n)\in \Theta(f(n))$

Note that $T(n)\in \Theta(f(n))$ means that both $T(n)\in O(f(n))$ and $f(n)\in O(T(n))$. So $T(n)\in O(f(n))$ follows from $T(n)\in \Theta(f(n))$.

In your case, you have $a=b=2$ and $f(n)\in\Omega(n^2)$ where $2 \>\log\_2 2 = 1$. The only problem is that you cannot guarantee $2f(\frac{n}{2})\leq kf(n)$ for some constant $k\<1$ and sufficiently large $n$.

So you can disprove $T(n)=O(f(n))$ by a counterexample like $f(n)=n^2+\exp(n)\cos^2(\frac{\pi}{2}\log\_2 n)$. Not really a great example for a nice exercise, but OK.
> 1 votes

# Answer
Although we only know $f(n) = \Omega(n^2)$, let's consider this: if it turns out that $f(n)$ is actually $\Theta(n^{\alpha})$ for some $\alpha \> 2$, then from the analysis similar to that of the Master Theorem (e.g. by recurrence tree) we can show that

$T(n) = \Theta(n) + g(n)$,

where

$g(n) = \displaystyle{\sum\_{j=0}^{N-1}} \\; 2^j \\; f\left(\frac{n}{2^j}\right) \\ \quad\\;\\; = \Theta\left( \displaystyle{\sum\_{j=0}^{N-1}} \\; 2^j \\; \frac{n^{\alpha}}{2^{\alpha j}} \right) = \Theta(n^{\alpha}).$

(One can show that this is true for all $\alpha \> 1$.) Then we have

$T(n) = \Theta(n) + \Theta(n^{\alpha}) = \Theta(n^{\alpha})$,

since in our case $\alpha \> 2$. And therefore we do have $T(n) = O(f(n))$.

My point is: for $f(n) = \Omega(n^2)$, the recurrence procedure is actually dominated by $f(n)$ during splitting/merging.
> 0 votes

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


# Question
Title: Problems with the proof of Huffman Optimality in Cover's book
There is a some question that arise from the proof of Lemma 5.8.1 of Cover's book on information theory that confuse me.

First question is why he assumes that we can "Consider an optimal code $C\_m$. Is he assuming that we are encoding a finite number of words so that $\sum p\_i l\_i$ must have a minimum value? Here I give you the relevant snapshot.

Second, there is an observation made on this notes that was also done in my class before proving the theory of optimality of huffman codes, that is,

> observe that earlier results allow us to restrict our attention to instantaneously decodeable codes

I don't really understand why this observation is necessary.

# Answer
To answer your first question, the index $i$ goes over the range $1,\ldots,m$. The assumption is that there are finitely many symbols. While some theoretical papers consider encodings of countably infinite domains (such as universal codes), usually the set of symbols is assumed to be finite.

To answer your second question, the claim is that a Huffman code has minimum redundancy among the class of *uniquely decodable codes*. The proof of Theorem 10 in your notes, however, only directly proves that a Huffman code has minimum redundancy among the class of *instantaneously decodable codes*. It does so when it takes an optimal encoding for $p\_1,\ldots,p\_{n-2},p\_{n-1}+p\_n$ and produces an optimal encoding for $p\_1,\ldots,p\_n$ by adding a disambiguating bit to the codeword corresponding to $p\_{n-1}+p\_n$; it's not clear how to carry out a similar construction for an arbitrary uniquely decodable code.
> 1 votes

---
Tags: information-theory, coding-theory
---


title: Does CPU without register exist?

text:
# Question
Title: Does CPU without register exist?
Is existence of registers in CPU an obligation, Or we just do it for performance?

Can we theoretically and practically have computer architectures that don't use registers? If yes, please name computer architecture and computer models that doesn't have register.

Update: Do stack machines use register? If yes, is it possible to have stack machines without registers?

# Answer
> 5 votes
Theoretically, the answer to your question is a resounding "yes". A Turing Machine, the very first definition of computability in terms of machine models, has no registers. Neither do stack machines (operations always act on the top elements of the stack). Register machines, of course, do.

Practically, the answer is "it depends on your definition of a CPU". At the very least you'll need a program counter, as Yuval pointed out

# Answer
> 8 votes
Every CPU has, at the very least, some internal registers: a *program counter*, a register storing *flags*, and in some architectures, an *accumulator* (though the latter isn't strictly required).

As you mention, registers are important for speed reasons. CPUs are designed with efficiency in mind. There are no drawbacks to having (external) registers, so I conjecture that all CPUs have them.

---
Tags: computer-architecture, cpu
---


# Question
Title: Truth and lie in infomation theory: negative amount of information
How does information theory deal with truth?

Does disinformation or lie have negative amount of bits of information?

# Answer
> 4 votes
> How does information theory deal with truth?

It doesn't. It deals with messages drawn from probability distributions, not with knowledge.

> Does disinformation or lie have negative amount of bits of information?

No, because that's not what information theory is about.

# Answer
> 3 votes
Suppose we have the following deck of cards

$$\\{\mbox{Ace}, 2, 3, 4, 5, 6, 7, 8\\}$$

I shuffle the deck, pick a card, but do not show it to you. You are totally ignorant as to what card I picked. Hence, you model your ignorance using a uniform probability mass function over the deck. Computing the Shannon entropy, your ignorance can be measured: $3$ bits.

Suppose I send you the following message:

> The card I picked is greater than $4$.

Your probability mass function is now uniform over $\\{5, 6, 7, 8\\}$, whose Shannon entropy is $2$ bits. By halving the set of "suspects", you gained $1$ bit of information from my message.

Suppose now that I send you the following message next:

> The card I picked is a prime number.

Since $6$ and $8$ are not prime, the set of "suspects" is halved again. Your probability mass function is now uniform over $\\{5,7\\}$, whose Shannon entropy is $1$ bit. You gained another bit of information from my 2nd message.

Suppose I now send you a 3rd message:

> Just kidding! The card I picked is **not** a prime number.

Your probability mass function is again uniform over $\\{5, 6, 7, 8\\}$. Your ignorance is again $2$ bits. In other words, you lost one bit of information when you received my 3rd message.

Perhaps you lost all trust in me. In that case, your probability mass function is back to the uniform distribution over the whole deck of cards, which corresponds to $3$ bits of ignorance.

Whenever a message makes you more "confused", whenever it widens the support of the uniform probability mass function you use to model your ignorance... well, then that message carries a negative information gain, which is another way of saying that it leads to information loss, i.e., to increased uncertainty.

---
Tags: information-theory
---


# Question
Title: An algorithm to find the maximum profitable assignment
Given a set of workers $w\_1,...,w\_m$ and and a set of tasks $t\_1,...,t\_n$, and a $m\times n$ matrix $P$ s.t. $P(i,j)$ is the profit of assigning worker $i$ to task $j$. One worker can only be assigned to one task, and one task can only have one worker. We want to find the maximum profit of all possible assignments.

Does anyone knows an algorithm or approach that can efficiently solve this problem and help provide a name or reference? Thank you.

# Answer
> 3 votes
Your problem is known as the assignment problem.

---
Tags: algorithms, optimization, assignment-problem
---


# Question
Title: 1's complement addition of outer carry to the result
Let's take for example this addition: **3 + (-1)**.

* 1 in binary is 001, and to obtain it's 1's complement counterpart we flip the bits. So it is: **110**.
* 3 in binary is 011.

> 011 + 110 = **1**001
>
> That first 1 which is in bold has to be added to the number formed by the last 3 bits as follows:
>
> 001 + **1** = 010 (*2* in decimal).

Why do we do the last step, adding that outer carry? Which is the logic behind?

# Answer
Computers represent numbers (and other things) imperfectly, sometimes for convenience, sometimes because there is no alternative. Complement arithmetic is easier to implement than sign-magnitude, but has a few quirks.

We just live with them, there's nothing special here.

In two's complement, the "extra one" is also there, but it is added during the change of sign, and because there is only one representation for zero, the system is a bit more elegant.

Try to picture a base complemented number as representing *what's missing* in the number to reach $b^k$ ($b$ is the base, $k$ is the number of significant digits). The apparent "extra one" is due to the fact that what is counted here are the steps to reach the implicit "zero" in $b^k$.

For instance, in ten's complement, with $k=3$:

$-5 = 995=10^3\color{red}{-5}$

In nine's complement, $999$ **is** zero, so the extra one is not necessary in this case. It becomes necessary, though, when the operation causes overflow due to change of sign:

$-5 = 994$

$-5+6 = 994+006 =\color{red}{1}000\color{blue}{+1} = 001$
> 0 votes

# Answer
**I only understand two's complement**

Let's take two 3 bits numbers, X and Y

Complementing the bits is like calculating 111-X

(it is obvious as $\overline {b} = 1-b$, $\sum\_{i=0}^n 2^i\*(1-b\_i) = \sum\_{i=0}^n 2^i - \sum\_{i=0}^n 2^i\*b\_i$...)

The addition becomes 111-X+Y

If you add 1 you get 1000-X+Y. The leftmost carry is discarded.
> 0 votes

---
Tags: arithmetic
---


title: Lambda Calculus Type Inference

text:
# Question
Title: Lambda Calculus Type Inference
I'm currently trying to learn how to infer most general types on lambda calculus, and due to the lack of information on the subject I could find on Google I'm forced to attempt what I think is logical and ask here if it's correct, it's most likely not, so please correct me!

Here's a couple exercises I've got, the idea is to reduce the redex and infer the most general type:

1. $(λf.λg.λx.g\space x(f\space x)) (λy.y)$
2. $λz.λx.((λy.λw.y w)x z)$

After I reduce them:

1. $λg.λx.(g x) x$
2. $λz.λx.x z$

And my attempt to infer the most general type:

1. Since $g \space x$ is applied to $x$ I assumed $g$ must be $g :: a\rightarrow (a \rightarrow b)$ while $x :: a$ Then $(λg.λx.(g\space x)\space x)$ must be of type $(a\rightarrow (a\rightarrow b))\rightarrow (a\rightarrow b)$
2. Since $x$ is applied to $z$, let's say $z :: a$ and $x :: a\rightarrow b$, therefor the function is $a\rightarrow (a\rightarrow b)\rightarrow b$

# Answer
> 4 votes
Let me assume that you are asking about basic type inference for $\lambda$-calculus with parametric polymorphism a la Hindley-Milner (it's not entirely clear from your question). I would recommend the Types and Programming Languages textbook by Benjamin Pierce as a general reference for this sort of thing. In there you can look up *parametric polymorphism* and *Hindley-Milner type inference*. These are the buzzwords you should be Googling. And when you do, it should be easy to find many resources.

P.S. You should not reduce before type inference. You should just do type inference on the original terms.

*Supplemental:* to find out whether you're correct, and since you're going to do Haskell in your course, why not ask Haskell about the types?

```
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Prelude> :t \g -> \x -> (g x) x
\g -> \x -> (g x) x :: (t1 -> t1 -> t) -> t1 -> t
Prelude> :t \z -> \x -> x z
\z -> \x -> x z :: t1 -> (t1 -> t) -> t

```

Yup, you were correct.

# Answer
> 0 votes
There are many different type systems. Before you do type inference, you need to decide in which type system you'll be working. Some of the common type systems for the lambda calculus are simply typed lambda calculus, Hindley-Milner, System F, LF, intersection types

Most type systems don't have decidable type inference, or most general types. If you're doing type inference and looking for a most general type, then you're probably working in Hindley-Milner, which is the basis of the type systems of languages such as ML and Haskell.

To find the type(s) of a term, you need to look at that term, not at what that term becomes after reduction. There is no intrinsic reason why there would be any relation between the types of a term and the types of the terms that it reduces to, but it's common to study combinations of type systems and notions of reductions that work well together. The property “working well together” is called *type preservation* or *subject reduction*, and it says that if $M$ reduces to $N$ and $M$ has the type $T$ then $N$ also has the type $T$, i.e. reduction of a term preserves its types. All the usual type systems for the lambda calculus are preserved by beta reduction. But the reduced term may have more types than the original.

Hindley-Milner type inference is fairly simple (the hard bits are to make it give good error messages and to make it fast, and especially extending it to do all kinds of neat stuff without making it incomprehensible and slow). You can to it from top to bottom. Maintain a list of type variables; some will get refined during the type inference process, and the ones that remain at the end are the ones that make the term polymorphic.

* Start by giving the whole term a type variable $a\_0$.
* When you have an application $M\\,N$ and you want it to be of type $T$, take a new type variable $a\_i$ and match the type of $M$ with $a\_i \to T$ and the type of $N$ with $a\_i$.
* When you have a lambda abstraction $\lambda x.M$, and you want it to be of a certain type:
    + If the desired type is of the form $T\_1 \to T\_2$, then match the type of $M$ with $T\_2$ under the assumption that $x$ has the type $T\_2$.
    + If the desired type is a variable $a$, then take two new type variables $a\_1$ and $a\_2$, replace $a$ by $a\_1 \to a\_2$ everywhere, and match the type of $M$ with $a\_2$ under the assumption that $x$ has the type $a\_1$.
    + If the desired type has some other form (which doesn't happen if the type language is restricted to functions and variables) then the term cannot be well-typed because you're trying to apply something that isn't a function.
* When you have a term variable, match the type that you assumed for it with the type you want it to be.

The “matching” operation between the type of a term and a type given by the context is called unification. The association of term variables to the assumed type for each of them in a subexpression is called a *context* or *environment*.

I'm not going to go through the procedure in detail for your examples. The types you gave for the two terms $\lambda g. \lambda x. g \\, x \\,x$ and $\lambda z. \lambda x. x \\, z$ are correct. The original terms happen to have the same types in this case, but in general they could have fewer types, for example they could be ill-typed (e.g. $(\lambda x. \lambda y. y) \\, M$ with $M$ ill-typed, reducing to $\lambda y.y$ which is well-typed).

---
Tags: lambda-calculus, functional-programming, typing, type-inference
---


# Question
Title: What kind of formal semantics can describe HTML and CSS?
What kind of formal semantics can describe HTML and CSS? Are there endeavours to do this. HTML/CSS layouts are espcially complex, so formalization can be of help.

# Answer
> 5 votes
I think the paper "Automated Reasoning for Web Page Layout" might be interesting to you. This paper defines CSS semantics in order to verify the layout formally. Look at section 3 of the paper for details. This would be one of the ways to express the CSS semantics, although this is a bit different from other semantics for programming languages.

---
Tags: semantics
---


# Question
Title: How long will selection sort and merge sort take to sort a certain number of items?
I am dealing with a sample exam question that I cannot understand which is as follows:

> Selection sort takes one millisecond to sort 1000 items (worst-case time) on a particular computer. Estimate the amount of time it would take to sort 100,000 items. If Mergesort took 1 second for 100 items and 15 seconds for 1000 items, how long would you expect it to take for 1,000,000?

Now, I know that selection sort has worst-case upper bound of $O(n^2)$. So as size of input $n$ increases, $f(n)$ increases in a quadratic manner. So I understand the concept of it but I don't understand how to use it to solve for how much time it would take for 100,000 items (100 times the original input). How would I solve it?

# Answer
> 1 votes
They want you to apply rule of three under ridiculous assumptions.

> If an O(n²) algorithm takes 1ms for 1000 elements, then from 1ms = c * 1000² and the ansatz Xms = c * 100000² we get that X = 10000.

In essence, they want you to assume that the running time function *equals* $cn^2$, in which case you could compute the constant $c$ from the given information.

The problem is that

* $O(\\\_)$ is only an upper bound and does not tell you anything about the true behaviour of the described function,
* there are unknown lower-order terms hidden in that $O(\\\_)$ (and also $\Theta(n^2)$, if you had that) and
* asymptotics tell us *nothing* for any finite $n$.
* They also ignore that the algorithms take different amounts of time for different inputs *of the same size* and
* that "time" is a famously fickly cost measure as it depends a lot on effects like caching and process scheduling.

Therefore, the problem is senseless.

---
Tags: algorithm-analysis, runtime-analysis, sorting, landau-notation
---


# Question
Title: Which of these simple data structures is most efficient when implementing a Dequeue?
A deque is a double ended queue of course. So if I can either use 2 stacks, or 2 queues, or 1 stack and 1 queue, which two would I use to have the fastest implementation? Can we derive the complexity for InsertLeft, InsertRight, and RemoveLeft, and RemoveRight?

I was thinking of using 2 stacks. Call 1 stack 'left' and the other 'right'. All operations are now order O(1) because if InsertLeft inserts items at stack called 'left' and InsertRight inserts in stack called 'right'. Both stacks maintain the front and the end of the sequence respectively. Am I correct?

# Answer
We need to clearly separate interface interfaces (abstract data types) from implementation. You talk about implementing a deque, an ADT, in terms of a stack or queue, but those are themselves ADTs. We need to be talking about concrete implementations.

So here's the answer (drumroll please): *use a doubly-linked list*. All the operations you mentioned are now $O(1)$.
> 2 votes

---
Tags: algorithms, algorithm-analysis, data-structures
---


# Question
Title: What is the time complexity (upper bound) for this simple recursive function?
So I have function that I have written to return the maximum value between index i and index x of a given array using recursion as follows:

```
FindMax( A, i, j )
    if (i == j):
        return A[i]
    else:
        k = (i + j) / 2
    return max( FindMax(A, i, k), FindMax(A, k+1, j) )

```

What is the correct way to go about calculating the big O asymptotic time complexity of this algorithm? I would appreciate if someone could document a general way to calculate the correct complexity even if it is a different recursive function. I have spent a lot of time watching videos and reading up on the web but sadly I come up with different complexities after each.

# Answer
Let's say the time of FindMax is $T(n)$ where $n$ is the size of array A. Notice, that FindMax access only the part of array between $i$ and $j$. Look at the pseudocode step by step. The first if is just comparison, so it's O(1). IF comparison is true, returning is O(1) (exit recursion step). The else step is doing again some arithmetic things which is O(1) and then calling three functions: max with time O(1), FindMax with time $T(n/2)$ and again FindMax. The time is the half, because again those function are "working" on the half of the original array. This gives the recursion $T(n) = O(1) + 2T(n/2)$. Using the master's theorem we get $T(n) = O(n)$ see here. Another proof without using the theorem mentioned above is by induction, pretty straightforward for this relation.
> 2 votes

---
Tags: algorithm-analysis, asymptotics, runtime-analysis, recursion
---


# Question
Title: How to rank these functions in increasing order of complexity [Algorithms]?
I have the following functions:

1. What is the correct order of these functions in increasing complexity?
2. I could always start entering values in these functions and check the corresponding output to notice the rate of increase. But is there a better, faster way of ranking these functions in order of increasing complexity? For example are there rules of thumb I could use to quickly sort these in order of increasing complexity? (Like I know generally exponential functions are more complex than log functions)

# Answer
I solved it after understanding asymptotic notation and the complexity of some common functions. Here's the order from least expensive to most expensive:

> log log n, log n ~ ln n, (log n)^2, sqrt(n), n, n log n, n^(1+x), n^2, n^3, n-n^3+7n^5, 2^(n-1) ~ 2^n, e^n, n!
> 2 votes

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: Can we count the number of times a particular state in a DFA is running in a loop?
If in a particular DFA , we are looping in a state for n symbols.... Is there any way to keep track of this 'n'?

# Answer
First of all, let me mention that the definition of DFA is final. The definition specifies *everything* that counts as a DFA. If you modify the model, it is no longer a DFA. However, your question makes sense if we interpret it as trying to change the model while keeping the class of languages accepted by the model.

There are several ways to interpret counting. If you could keep track of the number of loops through a state and then still remember it when you exit the state, then (depending on your exact rules) you could accept the language $a^n b^n$. So any mechanism that allows this is ruled out.

Another interpretation is that the state keeps a loop counter $C$, and it can base its decisions on the value of $C$ (that is, allow the transition function to depend on the auxiliary information $C$). This is also too powerful – you can accept every unary language (i.e., a language over $\\{0\\}$) using this mechanism.

What if we just allow the state to remember *some* information about $L$? Say that we partition $\mathbb{N}$ (the natural numbers) into finitely many sets $S\_1,\ldots,S\_d$, and we want to allow our transitions to depend also on which class $C$ lies in (here it doesn't really matter whether we are counting how many times we were at a state *overall*, or *in the current run*).

Let's do the case $d=2$ first. We can think of this as defining a unary language $L$ (which we identify with a subset of $\mathbb{N}$), and allowing transitions to depend on whether $C \in L$ or not. In this case, the resulting automaton model (for some *fixed* $L$) remains equivalent to DFAs precisely if $L$ is regular (exercise).

The general case is similar, and left to the interested reader.
> 1 votes

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


# Question
Title: Proving an algorithm exists to find independent set from a graph given an oracle
This is the problem that I have been given:

Consider the Independent-Set problem, in which the input is an undirected graph $G = (V,E)$ and a parameter $k$, and the goal is to determine if $G$ has an independent set of size $k$. Suppose we have an oracle $O$ for solving this decision version of independent set (think of it as a library function that takes input a graph $G$ and $k$ and answers YES/NO). Prove that there exists an algorithm that can find an independent set of size $k$, if one exists, using a polynomial number of calls to the oracle $O$, and possibly a polynomial amount of computation of its own.

My first question is: Is there any way to prove that an algorithm exists without just giving a specific algorithm?

I'm sort of taking a crash course in computer science, so this is not my strongest subject. Any hints as to what direction to take this would be appreciated!

# Answer
> 1 votes
Here's a hint.

Try running the decision problem subroutine on the original graph $G = (V, E)$. If the answer is NO, clearly you have your answer. If the answer is YES, pick some arbitrary vertex $v \in V$ and remove it from $G$ to produce a new graph $G'$. Now run the decision problem subroutine on $G'$. If the answer is still YES, what did you learn? (This is the "easy" case.) If the answer is now NO, what did you learn? (This case needs a bit more thinking, but not too much.) How many times might you need to repeat this procedure?

# Answer
> 1 votes
If the problem has the property that the decision version can be converted to the search version, it is self reducibility. You can show that all NP-complete problems are self reducible. The idea is to build the instance with the prefix of the verifier for NP-complete problem, and solve it based on the decision version. This is kinda well-known several lines proof.

I am not aware of any other methods to show the fact you asked for.

---
Tags: algorithms, graphs
---


# Question
Title: What is the complexity of timing a turing machine?
I can't find the standard name for this problem, so lets call it TIMING, it takes as input a Turing machine $F$ with its input $i$, and a number of steps $n$. It returns yes if $F(i)$ halts in less than $n$ steps, otherwise it returns no. What is the time complexity of this problem in terms of $n$, is it $n\log n$ as it is similar to a universal Turing machine, or does the counting each step mean it takes longer.

# Answer
> 0 votes
Let S (F, i, n) = the number of steps that F (i) takes until it halts, if it halts in n or fewer steps, and n if F (i) doesn't halt in n steps. Then you can simulate the Turning machine and get the result in O (S (F, i, n)) steps.

If this were important to you, then you could examine a few Turing machines, and see if you can detect patterns in their operation. For example, you might detect a pattern that indicates the Turing machine is trying to add two numbers x and y, and you might be able to analyse how many steps this will take and what state the Turing machine is afterwards; if you do this then you might often get a result in substantially fewer than c * N steps.

Or in your simulation, you might detect that the Turing machine enters the exact same state that it entered before; in that case it won't ever halt.

---
Tags: complexity-theory, turing-machines, halting-problem
---


# Question
Title: Practical communication example for a data rate scenario
Having difficulty with the following question.

I can answer parts I and II but having trouble finding a practical example.

Question:

> Compute the maximum data rate of the following communication links;
>
> I) 4000Hz bandwidth and a signal to noise ratio(SNR) of 20dB;
>
> II) noiseless channel of 2.4GHz bandwidth with 64 signalling levels;
>
> **Provide a practical communication example for each scenario.**

Any help would be greatly appreciated.

# Answer
> 0 votes
4kHz bandwidth and 20dB SNR is telephone communication.
2.4GHz with 64 signaling levels is WiFi with 64QAM if I understood correctly. In that case bitrate is 6 * baud.

---
Tags: computer-networks
---


# Question
Title: Automatic Downcasting by Inferring the Type
In java, you must explicitly cast in order to downcast a variable

```
public class Fruit{}  // parent class
public class Apple extends Fruit{}  // child class

public static void main(String args[]) {
    // An implicit upcast
    Fruit parent = new Apple();
    // An explicit downcast to Apple
    Apple child = (Apple)parent;
}

```

Is there any reason for this requirement, aside from the fact that java doesn't do any type inference?

Are there any "gotchas" with implementing automatic downcasting in a new language?

For instance:

```
Apple child = parent; // no cast required

```

# Answer
Upcasts always succeed.

Downcasts can result in a runtime error, when the object runtime type is not a subtype of the type used in the cast.

Since the second is a dangerous operation, most typed programming languages require the programmer to explicitly ask for it. Essentially, the programmer is telling the compiler "trust me, I know better -- this will be OK at runtime".

When type systems are concerned, upcasts put the burden of the proof on the compiler (which has to check it statically), downcasts put the burden of the proof on the programmer (which has to think hard about it).

One could argue that a properly designed programming language would forbid downcasts completely, or provide safe casts alternatives, e.g. returning an optional type `Option<T>`. Many widespread languages, though, chose the simpler and more pragmatic approach of simply returning `T` and raising an error otherwise.

In your specific example, the compiler could have been designed to deduce that `parent` is actually an `Apple` through a simple static analysis, and allow the implicit cast. However, in general the problem is undecidable, so we can't expect the compiler to perform too much magic.
> 24 votes

# Answer
Usually downcasting is what you do when the statically known knowledge the compiler has about the type of something is less specific than what you know (or at least hope).

In situations like your example, the object was created as an `Apple` and then that knowledge was thrown away by storing the refernce in a variable of type `Fruit`. Then you want to use the same refernce as an `Apple` again.

Since the information was only thrown away "locally", sure, the compiler could maintain the knowledge that `parent` is really an `Apple`, even though its declared type is `Fruit`.

But usually nobody does that. If you want to create an `Apple` and use it as an `Apple`, you store it in an `Apple` variable, not a `Fruit` one.

When you have a `Fruit` and want to use it as an `Apple` it usually means you obtained the `Fruit` through some means that *generally* could return any kind of `Fruit`, but in this case you know it was an `Apple`. Almost always you haven't just constructed it, you've been passed it by some other code.

An obvious example is if I have a `parseFruit` function that can turn strings like "apple", "orange", "lemon", etc, into the appropriate subclass; *generally* all we (and the compiler) can know about this function is that it returns some kind of `Fruit`, but if I call `parseFruit("apple")` then **I** know that's going to call an `Apple` and might want to use `Apple` methods, so I could downcast.

Again a sufficiently smart compiler *could* figure that out here by inlining the source code for `parseFruit`, since I'm calling it with a constant (unless it's in another module and we have separate compilation, like in Java). But you should easily be able to see how more complicated examples involving dynamic information could become more difficult (or even impossible!) for the compiler to verify.

In realistic code downcasts *usually* occur where the compiler couldn't verify that the downcast is safe using generic methods, and not in such simple cases as immediately following an upcast throwing away the same type information we're trying to get back by downcasting.
> 3 votes

# Answer
It's a matter of where do you want to draw the line. You can design a language that will detect validity of implicit downcast:

```
public static void main(String args[]) {
    // An implicit upcast
    Fruit parent = new Apple();
    // An implicit downcast to Apple
    Apple child = parent;
}

```

Now, let's extract a method:

```
public static void main(String args[]) {
    // An implicit upcast
    Fruit parent = new Apple();
    eat(parent);
}
public static void eat(Fruit parent) {
    // An implicit downcast to Apple
    Apple child = parent;
}

```

We're still good. Static analysis is much harder but still possible.

But the problem pops up the very second somebody adds:

```
public static void causeTrouble() {
    // An implicit upcast
    Fruit trouble = new Orange();
    eat(trouble);
}

```

Now, where do you want to raise the error? This creates a dilemma, one can say that the problem is in `Apple child = parent;`, but this can be rebutted by "But it worked before". From the other hand, adding `eat(trouble);` caused the problem", but the whole point of polymorphism is to allow exactly that.

In this case, you can do some of the programmer's job, but you can't do it all the way. **The further you take it before giving up, the harder it will be to explain what went wrong.** So, it's better to halt as soon as possible, according to the principle of reporting errors early.

BTW, in Java the downcast you've described is not actually a downcast. This is a general cast, which can cast apples to oranges just as well. So, technically speaking @chi's idea is here already, there are no downcasts in Java, only "everycasts". It would make sense to design a specialized downcast operator which will throw compilation error when it's result type can't be found downstream from it's argument type. It would be a good idea to make "everycast" much more difficult to use in order to discourage programmers from using it without a very good reason. C++'s `XXXXX_cast<type>(argument)` syntax comes to mind.
> 3 votes

---
Tags: object-oriented, type-inference, language-design
---


# Question
Title: Where I can I find Pre Trained CNN Datasets for Facial Emotion Recognition?
I am working on a project that involves recognising emotion from images. There are two parts in the project: One where I will generate features from images using API's and then classify the emotion and the other part is where I will first use a CNN on a dataset and then take some layer of features and then give it to SVM to classify.

So, I need a dataset of images as well as pre-trained CNN on that dataset also. I have searched quite a lot on google and I am not able to find any. In some cases, I found a pre-trained CNN dataset but could not find the original dataset of images on which CNN was trained.

# Answer
You are probably interested in IAPS, and want to read Analysis of Physiological Signals for Emotion Recognition Based on Support Vector Machine.

But to be honest this classification is doomed in advance, not only pictures are stripped of below threshold of effector activisation but also you do not get baseline as point of reference.

If you are really interested then start from reading everything that Ekman or Sejnowski wrote and feed your NN with only relevant parts, otherwise the most of the data feeded is noise.
> 2 votes

---
Tags: machine-learning, neural-networks, image-processing, pattern-recognition, data-sets
---


# Question
Title: When is it useful to split critical edges?
Some compilers have utility functions that split critical edges in the control flow graph. I assume that this is not done as an optimization in itself, but rather to simplify other analyses and transformations. In what cases would splitting critical edges be useful?

# Answer
> 5 votes
An easy google search shows in Muchnick, *Advanced Compiler Design & Implementation*, Section 13.3 *Partial-Redundancy Elimination*, pp 407-408:

> A key point in the algorithm is that it can be much more effective if the critical edges in the flowgraph have been split before the flow analysis is performed.

So the notion is useful to increase the efficiency of certain flow analyses in redudancy elimination, which aims to find portions of code with common sub-expressions and hoist them out into a single computation, which is facilitated in the absence of critical edges.

---
Tags: compilers, program-optimization, data-flow-analysis
---


# Question
Title: Calculate Complexity, loop incremented by log(k)
I'm preparing for an exam, and I ran across the following algorithm:

```
for(int j = 1 to n) {
    k=2
    while (k < n) {
        sum+= a[k] * b[k]
        k+= log(k)
    }
}

```

I'm trying to work on finding the complexity of the algorithm. Here's what I have so far.

The outside loop obviously runs in n steps. The inside loop gets incremented by log(k), so it should run faster than n as log(n) when n \>= 2 is greater than 1. Overall, it looks like the overall complexity is a little faster O(n^2), but by how much? I guess the question boils down to: **How do I find the complexity of the inner loop when it is incremented by a function of k?** What is the final complexity in this case? I'm assuming O(n^2) is technically correct since it will still be an upper bound, but is there a more accurate answer here?

# Answer
Let's ignore the outer loop, and concentrate only on the inner one. Since $\log m \approx \log (2m)$ for $m \geq 2$, we see that the number of times it takes $k$ to double is proportional to $k/\log k$. Therefore the number of iteration it takes to get from $2$ to $n$ (assuming for simplicity that $n$ is a power of $2$) is roughly $$ \frac{2}{\log 2} + \frac{4}{\log 4} + \frac{8}{\log 8} + \cdots + \frac{n}{\log n} \approx \frac{n}{\log n}, $$ since the numbers increase exponentially. Therefore the inner loop runs in time $O(n/\log n)$.

You can make this reasoning rigorous with enough effort.
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis, loops
---


# Question
Title: Characterize the Equivalence Classes of a Language
Given a language $A = \\{a^nb^n : n \>= 0\\}$, how would one go about characterizing the equivalence classes of this language, in order to apply Myhill-Nerode to show it is not regular? The idea and meaning of "characterizing equivalence classes" is what I am struggling with.

# Answer
> 3 votes
The notion of equivalence is that of *indistinguishability*. Given a language $L \subseteq \Sigma^{\ast}$, we say that strings $x$ and $y$ are indistinguishable wrt. $L$, written $x \\, I\_L \\, y$, if we have that for every $z \in \Sigma^{\ast}$ that $xz \in L \iff yz \in L$.

The Myhill-Nerode theorem tells us that a language $L$ is a regular language iff the set of equivalence classes of $I\_L$ is finite.

To show that $L = \\{ w \in \\{ a,b\\}^{\ast} \mid \exists n \geq 0. w = a^n b^n \\}$ is not regular, we simply have to show that the set of equivalence classes of $I\_L$ is infinite.

So consider a string $w \in \\{ a,b\\}^{\ast}$. The set of all strings $w$ not of the form $a^i b^j$ where $i \geq j$ forms an equivalence class, since for *no* $z$ we have that $w\_1 z \in L$ if $w$ is not of the form $a^i b^j$.

Moreover, every string of the form $a^i b^j$ where $i \geq j$ can only be indistinguishable from itself. So every such string forms an equivalence class containing only this single string.

Consequently, $I\_L$ has infinitely many equivalence classes.

---
Tags: formal-languages, automata, finite-automata
---


# Question
Title: Proof of non-regularity, based on the Kolmogorov complexity
In class our professor showed us 3 methods for proving non-regularity:

1. Myhill–Nerode theorem
2. Pumping Lemma for regular languages
3. Proof of non-regularity, based on the Kolmogorov complexity

Now the first two, Myhill-Nerode theorem and Pumping lemma, I understood well and I was also able to do the exercises to the first two methods. But I did not understand the third one. The Definition of the third method is as follows:

> Let $\ L \subseteq (\Sigma\_{bool})^\* $ be a regular language. Let $\ L\_x=\\{ y \in (\Sigma\_{bool})^\* | xy\in L \\} $ for every$\ x \in (\Sigma\_{bool})^\*$. Then there exists a constant $\ c$, such that for all $\ x,y \in (\Sigma\_{bool})^\* $
>
> $\ K(y) \leq \lceil log\_2(n+1)\rceil+c $
>
> if $\ y $ is the n-th word in the language $\ L\_x $.

Now I do not understand how to use this theorem to prove that a language is not regular, I don't really get the concept. We used the kolmogorov complexity before for determining the length of the shortest computer program of an object. How does one prove non-regularity with this theorem? And what is the thought behind it?

Thanks a lot!

# Answer
> 9 votes
To my knowledge, this is not one of the "classical" approaches used to characterize regular languages.

This approach is discussed in "A New Approach to Formal Language Theory by Kolmogorov Complexity", by Ming Li and Paul M.B. Vitanyi (see section 3.1).

They give several examples where one can use the statement you mentioned instead of using the pumping lemma. For example, proving non-regularity of $L$ where

$L=\left\\{1^p|\text{p is prime}\right\\}$.

Given some $x\in\Sigma^\*$, $L\_x=\left\\{y| \hspace{1mm} xy=1^p \land \text{p is prime}\right\\}$. Let us choose $x=1^{p'}$ where $p'$ is the $k$'th prime. Let $y\_1$ be the first word in $L\_x$. Obviously, $y\_1=1^{p-p'}$ where $p$ is the $k+1$ prime. According to the statement you mentioned, $K(y\_1)\le c$ ($n=1$), for some constant $c$ depending only on $L$ (see paper).

Since this holds for all $x$, we can bound the Kolmogorov complexity of all elements in $S=\left\\{y\_1^x| x=1^p \text{ for prime $p$ } \land \text{$y\_1^x$ is the first string in $L\_x$}\right\\}$ by the same constant $c$. However, we saw that $S$ actually consists of differences between consecutive primes, i.e. $S=\left\\{1^{p\_{k+1}-p\_k} | k\ge 1\right\\}$ where $p\_k$ is the $k$'th prime. Since we know $S$ cannot have bounded Kolmogorov complexity (prime differences get arbitrarily large), this means $L$ cannot be regular.

# Answer
> 4 votes
Another very easy example is the following: use Kolmogorov complexity to prove that $L\_{ww} = \\{ww \mid w \in \\{0,1\\}^\* \\}$ is not regular.

I give you a *very informal* proof hoping that it can help you better understand the role of Kolmogorov complexity.

The key idea is the following: a finite automata $D$ (that recognizes a regular language $L\_D$) has a finite amount of "memory"; so running on an input string $x = yz$ when it has "processed" the first part of the input $y$ the membership of $x$ in $L\_D$ depends only upon its current state and the second part of the input $z$.

Now suppose that $L\_{ww}$ is regular; then there is a DFA $D\_{ww}$ that recognizes it.

Let $y$ be an incompressible string of length $|y| = n \gg |D|$

For all inputs $x=y z$, at the end of the first part $y$, the DFA $D\_{ww}$ will clearly be on the same state $q\_i$, and by hypothesis it will accept only if the remaining part $z$ is such that $x = y z$ can be split in two equal halves (i.e. $yz = ww$); for example

```
 Let y = 10110
       y   z
 x = 10110 0  >> rejected
 x = 10110 1  >> accepted  (w=101, |y|>|z|)
 x = 10110 00 >> rejected
 x = 10110 01 >> rejected
 ....
 x = 10110 10110 >> accepted  (w=10110,  |y|=|z| !!!)
 ....
 x = 10110 1101101 >> accepted (w=101101, |z|<|y|

```

But it is important to notice that there is only one string $z$ of length $|y|$ that is accepted ($z = y$).

So given the description of $D\_{ww}$, the state $q\_i$ at the end of $y$, and the length $|y|$ we can simulate the behaviour of $D\_{ww}$ on all the $2^{|y|}$ strings and see which of them it accepts ... but it accepts exactly $z=y$.

So with a program of size $\ell = |D\_{ww}| + \log{i} + \log y + c $

($|D\_{ww}|$ space is needed to store the description of $D\_{ww}$, $\log i$ space to store $q\_i$, $\log y$ space to store the length of $y$, $c$ space is needed for the instructions that simulates the DFA)

we can "reconstruct" the string $y$; but for large enough $y$ we have $\ell \< |y|$ which is a contradiction because $y$ is incompressible.

---
Tags: formal-languages, regular-languages, proof-techniques, kolmogorov-complexity
---