title: Untyped vs Unityped

text:
# Question
Title: Untyped vs Unityped
1. From https://en.wikipedia.org/wiki/Programming\_language#Type\_system

> **Typed versus untyped languages**
>
> **A language is typed** if the specification of every operation defines types of data to which the operation is applicable, with the implication that it is not applicable to other types.\[47\] For example, the data represented by "this text between the quotes" is a string, and in many programming languages dividing a number by a string has no meaning and will be rejected by the compilers. The invalid operation may be detected when the program is compiled ("static" type checking) and will be rejected by the compiler with a compilation error message, or it may be detected when the program is run ("dynamic" type checking), resulting in a run-time exception. Many languages allow a function called an exception handler to be written to handle this exception and, for example, always return "-1" as the result.
>
> A special case of typed languages are **the single-type languages**. These are often scripting or markup languages, such as REXX or SGML, and have only one data type—most commonly character strings which are used for both symbolic and numeric data.
>
> In contrast, **an untyped language**, such as most assembly languages, allows any operation to be performed on any data, which are generally considered to be sequences of bits of various lengths.\[47\] High-level languages which are untyped include BCPL, Tcl, and some varieties of Forth.
>
> In practice, while few languages are considered typed from the point of view of type theory (verifying or rejecting all operations), most modern languages offer a degree of typing.\[47\] Many production languages provide means to bypass or subvert the type system, trading type-safety for finer control over the program's execution (see casting).

As far as I can understand the above quote, is the differences between unityped and untyped languages that

* for an untyped language, there is no concept of type, and any operation can apply to any value,
    * for an unityped language, all the values belong to exactly one type, and an operation can apply to either all the values or none of the values?
2. If my understanding is correct, how can we understand the following quote which suggests to drop untyped in favor of unityped:

From https://stackoverflow.com/questions/964910/is-javascript-an-untyped-language#comment49716735\_9159863

> it would be nice if the PLT community dropped "**untyped**" in favor of "**unityped**". The definition of "untyped" meaning "just bits" actually makes sense. To use "untyped" to describe a language whose formal specification uses the word "type" and says that it has seven types (Undefined, Null, Number, String, Boolean, Symbol, and Object) is really confusing. Most people do not want to distinguish this notion of type from the PLT def.

Thanks.

# Answer
You can understand this comment as not making much sense: he is proposing calling Javascript **uni**typed precisely because its specification says it has **seven** types. He also says "I was glad to see that this answer referenced Harper's blog post" but that post is about why "type" should be used in PLT sense (static types only): i.e. why the two senses have to be distinguished and JS specification uses the term "incorrectly" (not in the way PLT does).

EDIT: on further thought, he doesn't actually say JS should be called "unityped". That is, maybe he proposes converting PLT to the definitions in Wikipedia:

1. PLT people currently call JS "untyped" in the sense "not statically typed".
2. Because "most people do not want...", PLT definition of "type" should be changed to cover both static and dynamic types.
3. Languages which have 1 type should be called "unityped" instead.
4. JS has 7 types according to its specification, so it's neither "untyped" nor "unityped" (but it is "statically unityped").
> 4 votes

---
Tags: programming-languages
---


title: Is the given language DCFL?

text:
# Question
Title: Is the given language DCFL?
$a^ib^jc^k | (i = j)$ then k is even?

I can write it as $a^ib^ic^k$ where k is even

OR

$a^ib^jc^k where (i != j)$

Both are DCFL and union of DCFL may be DCFL, but I think because of OR operator it gives a sense of parallelism and hence NCFL.

I haven't tried to make a DPDA for it, because in exam I might not be have much time to draw.

I don't think it is DCFL.

**Theoretically, is this approach right ?**

# Answer
> 1 votes
You can construct a DPDA for your language as follows. When reading $a$s, the machine pushes $A$s onto the stack. When reading $b$s, the machine pops them, noting to itself if there are more $b$s than $a$s. When it reads the first $c$, it can use the top-of-stack to tell if the number of $a$ was equal to the number of $b$s; if so, it transfers control to a DFA for $(cc)^\*$, and otherwise it transfers control to a DFA for $c^\*$.

---
Tags: context-free, finite-automata, nondeterminism
---


# Question
Title: "Equivalent device" for testing for NP and coNP?
I'm trying to understand some aspects of the $P=^?NP$ and $NP=^?coNP$ problems.

I am engineer and not mathematician nor computer scientist so I do not completely understand what a turing machine is.

I'm currently thinking about a variant of the "subset sum problem" known to be in $NP$ and suspected to be not in $coNP$. However I'm thinking of a modified variant of the problem.

It is easy to prove that a computer based on a "real" CPU can prove the answer "yes, a subset exists" (when the subset is known) in less than $(n+a)^2$ operations (while $a$ depends on the type of CPU used) when the original set contains $n$ elements.

From my understanding of $NP$ this implies that the problem belongs to $NP$. My first question is if this understanding is correct.

(I write "belongs to $NP$" and not "$\in NP$" because I know I mix up terms like "problem", "formal language", ...)

I suspect the minimum number of operations (on the real CPU) to prove the answer "no, no matching subset exists" to be more than $\frac{2^n}b$ (while $b$ depends on the type of CPU used).

So my second question is if this would mean that the problem does not belong to $coNP$.

As far as I know that there are differences between Turing Machines and CPU-based computers:

* A Turing Machine has unlimited memory while a computer has limited memory
* A Turing Machine can't generate true (undeterministic) random numbers while on a computer you may use the noise of the microphone input...
* ...

So I'm not sure if "cannot be calculated by a computer in polynomal time" implies "cannot be calculated by a Turing Machine in polynomal time".

-- Edit --

Having read the answers I think I have to say something about the background of the question:

I think I had already understood what P, NP or coNP is before asking the question but I was not 100% sure because I was not sure about the differences between a Turing Machine and a computer.

I have an idea how it **could** be possible to prove the impossibility to build a digital computer that can solve a certain problem in less than $a^nb$ steps while $n$ is the number of inputs and $a$ and $b$ depends on the computer and the problem.

I was just wondering if such a proof was sufficient to prove $P \neq NP$ if it could be done for a problem that is known to be in NP.

Having read your answers I think that such a proof would be sufficient. Thanks.

(Needless to say that I am *not* able to carry the proof I'm thinking of for any problem.)

# Answer
I will not directly answer your questions, as this would result in explaining the definitions of $\mathsf{NP}$ and $\mathsf{coNP}$, which has been done before. However, using the following hint combined with the definition of the complexity classes indirectly answers your questions.

---

A modern computer with unlimited memory is equivalent to the concept of a register machine, which in turn is turing equivalent. Thus everything that can be computed on a modern computer with infinite memory can also be computed by a turing machine and vice-versa.

> A Turing Machine can't generate true (undeterministic) random numbers while on a computer you may use the noise of the microphone input...

A microphone, or any other hardware-based true random number generator, is an *input* of the computer. That means the values delivered by it are not computed by the computer itself. Note that you can also model random input by a two-tape turing machine, where one tape contains the random numbers.
> 2 votes

# Answer
P, NP, co-NP are all about "decision problems", that is problems where the answer is either "yes" or "no".

P is the set of problems that I can solve in polynomial time if the answer is "yes", and co-P is the set of problems that I can solve in polynomial time if the answer is "no". P and co-P are the same: If I can solve problems where the answer is "yes" in polynomial time, then I can solve problems where the answer is "no" also in polynomial time: I just try to prove that the answer is "yes", and if I fail for long enough time, then I know the answer must be "no" (because if it was "yes", I would have found the answer).

NP can be described in different ways. It is the set of problems where for every instance where the answer is "yes", there is a proof for that that can be checked in polynomial time. Alternatively, you can solve the problem in polynomial time if you have an unfailing ability to make lucky guesses. And co-NP is almost the same, except that it works when the answer is "no".

But here the situation is different. Take your problem: If I give you two subsets of equal size, you can easily check that a set can be split into two sets of equal size. But if there are no two sets of equal size - it seems very hard to prove that they don't exist. And I can't come up with the slightest idea what would help you to prove that the answer is no (quite obvious, because I would be really, really famous if I could).

On a lower level, the problem whether a number is composite. It's easy to prove if the answer is yes: I just give you a prime factor, and that's it. There is no obvious way to prove that the answer is "no" - but it turned out quite incredibly that there is indeed for every prime a short proof that it is prime that can be tested quite quickly; that required some deep mathematics. So "composite" is both in NP and in co-NP. There is a suspicion that the intersection of NP and co-NP is less than NP, and in fact a way to check primality or compositeness in polynomial time was found. (Unfortunately that method can prove that a number is composite, but it cannot find factors).
> 1 votes

# Answer
Complexity theory is based on analyzing the asymptotic running time of algorithms. In order to talk about asymptotics, the input length should be unbounded. However, real CPUs can only handle inputs of bounded length. So you cannot do complexity theory with real CPUs.

In more details, in complexity theory we only care about the order of growth of the running time; so running times of $n$ and $1000n$ are the same for us. Everything that can be computed at all on a real CPU can be computed in some finite time, so all problems computable on a real CPU have complexity $O(1)$.

One way out of this mess is to consider an idealized version of a real CPU which can handle arbitrary inputs. Such an ideal version would probably be very similar to a RAM machine, and these are known to be polynomial equivalent to Turing machines. Without getting into details, this means that you can define classes like $P,NP,coNP$ using a RAM machine instead of a Turing machine, and you'll get exactly the same class.

You mention that real CPUs have access to randomness. While randomness is considered in complexity theory, the complexity classes $P,NP,coNP$ assume machines with no access to randomness (deterministic machines), so you'll have to disallow this. If you really care about randomness, you should probably look into the complexity classes $BPP,AM,coAM$, which are one possible list of analogues of $P,NP,coNP$. (For AM, see this.)

Finally, you mention that you suspect that the minimum number of operations needed to certify a negative instance in the worst case scales like $2^n$. If the suspicion were true, then it would indeed follows that subset sum is not in $coNP$. Unfortunately, nobody knows how to prove this.
> 0 votes

---
Tags: complexity-theory
---


# Question
Title: What concept is for a name referring to different types at different points in execution?
In programming language theory, which concept means that a name can refer to values of different types at different points of execution of a program,

* dynamic typing,
* implicit i.e. inferred typing, defined as opposed to explicit i.e. manifest typing,
* something else?

Let me explain the above question.

1. My question comes from reading following two sources.

* From Wikipedia https://en.wikipedia.org/wiki/Programming\_language#Static\_versus\_dynamic\_typing

    > **Statically typed languages can be either manifestly typed or type-inferred.** In the first case, the programmer must explicitly write types at certain textual positions (for example, at variable declarations). In the second case, the compiler infers the types of expressions and declarations based on context. Most mainstream statically typed languages, such as C++, C# and Java, are manifestly typed. Complete type inference has traditionally been associated with less mainstream languages, such as Haskell and ML. However, many manifestly typed languages support partial type inference; for example, Java and C# both infer types in certain limited cases.\[48\] Additionally, some programming languages allow for some types to be automatically converted to other types; for example, an int can be used where the program expects a float.
    >
    > **Dynamic typing, also called latent typing, determines the type-safety of operations at run time**; in other words, types are associated with run-time values rather than textual expressions.\[47\] **As with type-inferred languages, dynamically typed languages do not require the programmer to write explicit type annotations on expressions**. Among other things, **this may permit a single variable to refer to values of different types at different points in the program execution**. However, type errors cannot be automatically detected until a piece of code is actually executed, potentially making debugging more difficult. Lisp, Smalltalk, Perl, Python, JavaScript, and Ruby are dynamically typed.

    In "this may permit a single variable to refer to values of different types at different points in the program execution", is it correct that "this" means implicit typing?

    So does it imply that it is implicit typing instead of dynamic typing which "may permit a single variable to refer to values of different types at different points in the program execution"?
    * From https://pythonconquerstheuniverse.wordpress.com/2009/10/03/static-vs-dynamic-typing-of-programming-languages/

    > **In a dynamically typed language**, every variable name is (unless it is null) bound only to an object.
    >
    > Names are bound to objects at execution time by means of assignment statements, and it is possible to **bind a name to objects of different types during the execution of the program**.

    Does it imply that it is dynamic typing which "may permit a single variable to refer to values of different types at different points in the program execution"?
2. In order to answer the above questions, some counterexameples may help. Specifically,

* Can you give an example when a programming language is dynamic typing, but a name is not allowed to refer to values of different types at different points of execution of a program?
    * Can you give an example when a programming language is implicit typing, but a name is not allowed to refer to values of different types at different points of execution of a program?

# Answer
> 3 votes
A couple of things would fit the bill: polymorphism and dynamic typing.

## Polymorphism

Say you have a polymorphic function, `first`:

```
first : (A, B) -> A
first (a, b) = a

```

At runtime, the variables `a` and `b` may refer to values of different types on different invocations. e.g. `first (1, 'a')` and `first ("Fred", 42)`. Polymorphic means many forms/types.

## Dynamic typing

Dynamically typed languages also have variables that refer to values of different types at runtime. This happens for functions like `first` above but also in other situations like:

```
$ python
>>> a = "hi"
>>> a = 42

```

## Type Inference

You also mentioned "implicit" or inferred typing for statically typed languages. Type inference happens at compile time. If the type inference process decides that a variable is of a monomorphic type (like Int), then that variable will always refer to a value of type Int. Monomorphic simply means a single form/type. The type inferencer can also decide that a function has polymorphic arguments, then it will be as `first` above. I hope you can see that type inference is a red herring when it comes to the main thrust of your question.

---
Tags: programming-languages, typing
---


# Question
Title: Is {a^i b^j c^k | i≤j or (k=j≤i)} context sensitive?
$$L = \\{a^i b^j c^k \mid i \le j \text{ or } (j \le i \text{ and } j = k)\\}$$

I think the given language is CSL as i can break this language like this

$$L = \\{a^i b^j c^k \mid i \le j \text{ and } j = k\\} \cup \\{a^i b^j c^k \mid j \le i \text{ and } j = k\\} \cup \\{a^i b^j c^k \mid i \le j \text{ and } j \le i \text{ and } j = k\\}$$

Last language i,j are independent, hence DCFL.

When we take union of these languages, we get CSL.

**Is my approach right?**

# Answer
There are two possible interpretations of the condition on $i,j,k$:

1. $(i \leq j \lor j \leq i) \land j = k$. This condition is equivalent to just $j = k$, and so the language in question is $\\{ a^i b^j c^j : i,j \geq 0 \\}$, which is a prototypical context-free language.
2. $i \leq j \lor (j \leq i \land j = k)$. A linear-bounded automaton can decide this language (exercise), so it is context-sensitive. On the other hand, using the pumping lemma you can show that it is not context-free (exercise).

I would guess that the second interpretation is the one that was intended.
> 3 votes

# Answer
It is CFL. Number of a & b are irrelevant. What matters is number of b should be equal to number of c which can be achieved by PDA.
> 0 votes

---
Tags: formal-languages, context-sensitive
---


title: What is a predicate transformer?

text:
# Question
Title: What is a predicate transformer?
I'm reading *Programming - The derivation of algorithms*, and I want to understand the purpose of a **predicate transformer**. This is the excerpt (p. 14-15):

> A more precise way in which constructs may be introduced is as follows. For each construct $S$ one defines a **predicate transformer**, denoted $wp.S$, which is a function from predicates to predicates. For construct $S$ and predicate $Q$, $wp.S.Q$ is interpreted as the weakest predicate $P$ for which $\\{P\\}\\,S\\,\\{Q\\}$ holds. It is called the **weakest precondition** of $S$ with respect to $Q$. The relation between the expressions $\\{P\\}\\,S\\,\\{Q\\}$ and $wp.S.Q$ is given by
>
> $$ \\{P\\}\\,S\\,\\{Q\\}$ \text{ is equivalent to } \[P \implies wp.S.Q\]$$

Explain me the concept predicate transformer. What is its purpose?

# Answer
The predicate transformer is just a formalization of the idea that you can produce a precondition given a program and its postcondition.

For example, given a program `sqrt` with the postcondition that `sqrt(x) = y` and `y*y = x`, what are some valid preconditions?

* x \> 10
* x \> 20
* x \> 1

Some invalid preconditions would be

* x \< 0
* x \> -10

One predicate `P1` is weaker than another predicate `P2` if `P2 => P1`, but it is not true that `P1 => P2`. For example, `x > 1` is weaker than `x > 10` because `x > 10` implies `x > 1` as well, but `x > 1` does *not* imply `x > 10`; `x == 3` would be a counterexample.

Given all possible preconditions for our square-root program, one must be the weakest of them all; we denote that with the function `wp.S.Q` (which you could also write in the more familiar notation `wp(S, Q)`). In this case, `wp.S.Q = {x >=0 }`. You can prove that if `x` satisfies any precondition `P`, then it must satisfy `x >= 0`, and that if it does not satisfy `x >= 0`, it cannot satisfy any other precondition `P`.

The idea of a weakest precondition is useful because it allows a program to work with as many values as possible. Using a precondition of `x >= 20` isn't useful because it doesn't allow us to compute the square root of 4.

Note that just because `wp.S.Q` is *defined*, that doesn't mean we have to provide an algorithm to actually compute its value. Doing so would provide a constructive proof of its existence, but non-constructive proofs could be found as well.
> 9 votes

---
Tags: semantics, hoare-logic, denotational-semantics
---


title: Why is $O(t(n)b^{t(n)}) = 2^{O(t(n))}$?

text:
# Question
Title: Why is $O(t(n)b^{t(n)}) = 2^{O(t(n))}$?
I'm not sure how to get from the left hand side to the right. It appears in Sipser's Introduction to the Theory of Computing, in a proof of showing that a $t(n)$ time nondeterministic single-tape Turing machine has an equivalent $2^{O(t(n))}$ time deterministic single-tape Turing machine.

# Answer
> 4 votes
Note that for every number $x$ it holds that $x=2^{\log x}$. Using this, we can do the following:

$t(n)b^{t(n)}=2^{\log t(n)}b^{t(n)}=2^{\log t(n)}({2^{\log b}})^{t(n)}=2^{\log t(n)}2^{t(n)\log b}=2^{\log t(n)+t(n)\log b}$. Now, assuming $t$ is non-decreasing, we have that $\log t(n)=O(t(n))$, so ${\log t(n)+t(n)\log b}=O(t(n))$, and we're done.

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


# Question
Title: Given an algorithm, do worst case time complexity "class" vary with array and linked list?
My intuition says that I can make a sorting algorithm(may be a strange, not an useful), such that with array it have different worst case time complexity class and linked list(assuming time complexity of operation performed in linked list are same as conventionally used) with different complexity class.
But what about the sorting algorithms which are conventionally used(may be the algorithms in CLRS)?
I am assuming the implementation done on RAM model and by class I mean the set $\theta(f)$ with f as worst case running time of the algorithm

# Answer
> 1 votes
Note that complexity classes are classes of *problems*, not classes of *algorithms*. Specifically, complexity classes are classes of problems that can be solved within particular resource bounds *by some algorithm*. So, for example, sorting is in polynomial time because there is at least one algorithm that sorts with this resource bound. (In fact, you probably know many algorithms that do this.)

When it comes to comparing different algorithms for solving the same problem, yes, they may have different resource usage. The fact that you have random access to the elements of an array but not to a linked list means that you can probably design more efficient algorithms based on arrays compared to those based on linked lists. And note that, by using different data structures, they are different algorithms: they involve different computational steps.

Note also that all of this is dependent on your model of computation. For example, if you're solving computational problems using Turing machines, then arrays and linked lists are essentially the same thing, because we can only access the array by moving the tape head sequentially through the elements. Typically, though, when analyzing actual algorithms, we use models of computation, such as the random access Turing machine, that correspond more closely to actual computers.

---
Tags: time-complexity, sorting, arrays, linked-lists
---


# Question
Title: machine learning classification with financial instrument/time series data
I am new to machine learning and have started brainstorming some model ideas that involve financial instrument/time series data. I was thinking it might be useful to use a classification algorithm to predict if an instrument was in fact up or down y% (TRUE/FALSE) after n days, based on i.e. a combination of technical indicator states for each learning example.

That said, in researching the idea I came upon an article that stated training examples in time series data are not independent of each other:

*"Time series data has a natural temporal ordering - this differs from typical data mining/machine learning applications where each data point is an independent example of the concept to be learned, and the ordering of data points within a data set does not matter"*

My question is as follows: is the above true only if we are trying to predict the continuous value of an asset n days into the future? As far as my idea outlined in the first paragraph is concerned, would this then still be valid considering I am not (apparently) taking into account the specific relationship

# Answer
Consider that:

* a "sliding window" approach can be used with any *standard* regression / classification algorithm. E.g. given the following time series

```
Time High Low Open Close Volume
  1   H1   L1  O1   C1     V1
  2   H2   L2  O2   C2     V2
  ...
  i   Hi   Li  Oi   Ci     Vi

```

you can feed the ML algorithm with these examples:

```
  O0, H1, L1, O1, C1, V1, H2, L2, O2, C2, V2, H3, L3, O3, C3, V3
  O1, H2, L2, O2, C2, V2, H3, L3, O3, C3, V3, H4, V4, O4, C4, V4
  O2, H3, L3, O3, C3, V3, H4, V4, O4, C4, V4, H5, V5, O5, C5, V5
  ...

```

(the first value is the target)

The size of the window (`s`) is an important limitation: the algorithm cannot correlate "candles" that lie more than `s` timesteps apart.

On the other end, with a large `s`, all examples appear to be sparse and dissimilar in many ways (see Curse of dimensionality).

You may use other features (e.g. averages, multiple timeframes, Japanese candlestick patterns...) but not without a good knowledge of the specific domain.
* ML has tools that, in theory, can deal with timeseries. E.g. Recurrent neural networks can take advantage of their internal memory to process arbitrary sequences of inputs and exhibit dynamic temporal behavior. See Which machine learning algorithms can be used for time series forecasts? for references.
> 3 votes

---
Tags: machine-learning, classification, time-series-analysis
---


title: decidability of artificial intelligence

text:
# Question
Title: decidability of artificial intelligence
Not sure whether this is the correct place to post the question. some of my terms might not accurate.

currently AI is used for classification, inference, and so forth, is AI problem decidable? for example, given a dataset, prior/constraints and neural network, whether it can recognize a pattern (properly accuracy greater than some lower bound) is decidable? I understood the decidable problem is searching in a finite space. In terms of Machine learning techniques, the parameter space is finite, can I say it is decidable?

Also, Many problem solved by machine learning is quite different with traditional problem which has an algorithm, but machine learning problem doesn't have an algorithm format. And therefore, it is undecidable

Finally, for many proved math theorem, let's say the bound in some constrained problems (ex: Shannon limit in communication). Can I say such problem (constrained problem exists bound) is decidable, since people could find an algorithm (or math formula) to define limits.

# Answer
> 2 votes
For a problem to be approachable using what we presently call "AI methods", it has to be, *at least theoretically*, also solvable using "regular" methods (writing a set of instructions that solves it, line by line). Thus, decidable.

AI systems may create effective algorithms whose operation no human can understand. Also, by using AI methods we may find solutions to new problems, by accident, or discover that problems are decidable. These things do not contradict the affirmative above.

An algorithm *exists* that solves the problem.

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


# Question
Title: I do not understand why finding the minimum of elements take O(n) time
I know that sorting the array take O(logn) time. But why finding the minimum of elements take O(n) time, which is more expensive? If I sort the array, I simply output the first element and this would be my minimum.

# Answer
Sorting the array using comparison-based method takes $\Omega(n \log n)$. So sorting is obviously more expensive than finding minimum in $\mathcal O(n)$.

In fact finding minimum or sorting takes $\Omega(n)$ to at least read the whole array. For finding minimum it is actually $\Theta(n)$.

If it were true that sorting takes $\mathcal O(\log n)$ then you would be right to use sorting instead.
> 4 votes

# Answer
I think there is no possible way a sorting algorithm can be less than O(n). Best performance we generally get is O(nlogn).

Also, In case of finding the minimum in an array It should be O(n) at least, unless you have more data about the numbers in array. Because you need to go through all the numbers in array at least.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Complexity classes pertaining to listing all solutions?
I was reading a question over at Stack Overflow asking whether it was **NP**-hard to list all simple cycles in a graph containing a particular node and it occurred to me that I couldn't think of any existing complexity class that was well-suited for talking about problems of the form "list all solutions to this problem." The class **NP** in some sense consists of problems that ask whether at least one solution exists, the class **FNP** asks to produce a single solution, and the class **#P** asks to count how many solutions there are, yet none of these deal with the complexity of exhaustively enumerating all possible solutions.

Is there a complexity class for describing problems that are of the form "given a polynomial-time computable predicate $P(x, y)$ and a string $x$, enumerate all $y$ for which $P(x, y)$ is true subject to \[insert some appropriate complexity restrictions\]?" I understand that it might be tricky to pin down the restrictions given that the number of solutions might be exponentially larger than the size of the input $x$, though that doesn't seem insurmountable.

# Answer
The concept you are looking for is called **enumeration complexity**, which is the study of the computational complexity of enumerating (listing) all the solutions to a problem (or the members of a language/set). Enumeration algorithms can be modeled as a two step process:a *precomputation* step and an enumeration phase with *delay*. Both of these steps have their own time and space complexities (perhaps entropy, too). In the general spirit of complexity, there are often trade offs between these to consider.

The **precomputation step** performs some work that is necessary before the first solution is enumerated. This might involve finding the solution itself or initializing some large data structure that will reduce the overall delay between each solution.

The **delay** is the resource cost associated with the computation necessary in between arbitrary enumerated solutions. In other words, the delay is a measure of the space and time needed to produce the $i+1^{th}$ solution after the $i^{th}$ one. Problems whose solutions that take $O(1)$ time for each enumeration are said to have constant delay. A requirement of $O(poly(n))$ time is said to have polynomial delay.

For the enumeration problem you specifically mentioned in your question, you should look into the class $ENUM\_{NP}$ and its related siblings in section 2.1 of "Enumeration: Algorithms and Complexity" by Johannes Schmidt (Linked at the bottom).

---

**Why do we care about precomputation time and delay?**

Delay is very key to understanding the true intricacies of enumeration problems. Enumerating the elements of $\Sigma^\*$ (up to size $n$) and $\\{ \vec{x} : \phi(\vec{x}) \\}$ where $\phi(\vec{x})$ is a Boolean formula (i.e. SAT) both take exponential time. However, enumerating through $\Sigma\*$ only requires constant delay since you can just go through the elements in some order. For all we know, the delay for enumerating solutions to a 3SAT instance could be exponential. Our job as complexity theorists is to capture why the latter problem is fundamentally harder (more complex) than the former one. Delay does a pretty good job at showcasing this difference.

Likewise, we also need to know how much precomputation is done. We can reduce the delay for any enumeration problem to constant time and space by precomputing all solutions and storing them in a list to be enumerated at a later time. The challenge is to find the best balance between the two resources.

The order in which you enumerate the elements can also influence the complexity. Requiring results to be returned in a specified sorted order might require us to perform additional computation in both steps. Though situations where any order suffices (as long as each enumerated element is unique) are certainly studied, too.

As far as I know, these classes do not typically have concise labels (akin to $P$ and $NP$). We cannot feasibly expect to be able to do this since enumeration complexity classes are juggling around 3 or more resources (precomputation/total time, space, delay, and entropy). There are simply too many combinations of resource bounds to hand out special names. This does not make these classes any less interesting and also does not stop researchers from trying anyways.

---

**Resources**

This survey (really an attempt at formalization) should help you get started. It also proves some basic hierarchy theorems.

**Enumeration: Algorithms and Complexity** (Johannes Schmidt, 2009)

https://www.thi.uni-hannover.de/fileadmin/forschung/arbeiten/schmidt-da.pdf

For an enumeration of results in enumeration complexity, check out this compilation curated by Kunihiro Wasa. Since it is categorized by problem type, you can easily find a number of papers dedicated to enumerating graph cycles. It should be simple to modify the algorithms involved to only consider cycles with a given node.

http://www-ikn.ist.hokudai.ac.jp/~wasa/enumeration\_complexity.html
> 11 votes

---
Tags: complexity-theory, reference-request, complexity-classes, enumeration
---


# Question
Title: Is type inference done by an interpreter static or dynamic?
Type inference can be done by a compiler, and in such cases, type inference is static.

Type inference can also be done by an interpreter. An interpreter does the jobs of both compilation and execution. So is type inference done by an interpreter static or dynamic?

This question is an example that motivated my question Does "static" or "dynamic" imply a compiler or interpreter implementation of a programming language? at a more general level.

# Answer
Typically , type inference in interpreted languages happens after parsing (because type inference works on ASTs) but before interpretation (= execution). Both compilers and interpreters have a phase distinction between type inference, and the execution. The former happens strictly before the latter.

---

BTW, it's wrong to say that an "interpreter does the jobs of both compilation and execution". An interpreter does *not* do compilation.

* A **compiler** is a meta-program that takes as input a program and outputs another program (the executable). It is this output that is executed.
* An **interpreter** is a meta-program that takes as input a program and executes it.

Maybe the following picture clarifies the issue.
> 4 votes

---
Tags: typing
---


# Question
Title: Can a shortest-path tree be a also maximum spanning tree?
If we were to find the shortest-path tree rooted at some vertex in a weighted graph G, is it possible that the resulting tree is also a maximum-weight spanning tree of G? Please give an example!

I tried every combination I could come up with using connected graphs with cycles on them (so that there is more than one possible path) and used Dijkstra's algorithm. No luck!

# Answer
> 2 votes
Let A-B-C be connected graph with edges like shown (AB and BC) the shortest path (the only possible) from A to C is through B. To include all vertices in the maximum spanning tree all vertices are needed, so this is small example (the smaller, A-B is also valid).

Maximum spanning tree have maximal weights, but may be not unique for given graph. The shortest path tree (which I assume is the weighted one) have path weights but also is not guaranteed to be unique.

From the definitions finding graph with cycles will be harder - taking minimal example, a full graph with vertices D, E, F and distances |DE| = 3, |EF| = 2, |DF| = 3, the shortest path from E to F is 2, but the maximal spanning tree will not contain this edge.
The two structures may overlap when there are no cycles or weights are equal, otherwise they will get opposite edges when possible.

---
Tags: graphs, trees, shortest-path, spanning-trees
---


# Question
Title: Framework or tools to generate theorem prover/solver/reasoner for new logic
I have new logic which has syntax and semantics in usual natural languages and I have to create theorem prover/solver/reasoner for this logic. Is there framework or tool set that can generate such prover from the formal definition of grammar and semantics? I have heard about Isabelle/HOL, is this right set of tools. Is such generation a common path to proceed. Are the metalogical framework, prover compilers suitable for any kind of new logic?

Of course, I can create parser and encode all the algorithms by myself from scratch but this is not the common practice, I guess?

# Answer
There are many related ways you can mechanise your logic.

* **Deep embedding** into one of the well-developed provers such as Isabelle/HOL, Coq or Agda. This is (almost) always possible, but makes using the embedded logic awkward.
* **Shallow embedding** into one of the well-developed provers such as Isabelle/HOL, Coq or Agda. This is only possible when the embedded and embedding logics are sufficiently similar, but when it works it tends to work well.
* **Embedding into Isabelle**. Note that Isabelle is a meta-tool for embedding logics, and Isabelle/HOL is but an implementation of HOL using the Isabelle tool. This is probably a lot of work, and moreover, most of the proof automation available for Isabelle/HOL is targetxing the logic HOL, so is unlikely to work for your specific logics.
* **Roll your own**. It's quite easy to build a proof checker, should be just a few lines of code, especially if you take the LCF approach. More advanced tools are rather difficult, a modern SAT solver is probably \> 10k LOC and that's for propositional logic, which is the simplest logic.
* **Logical frameworks**. Some $\lambda$-calculi have been built particularly to enable the embedding of logics. Most well-known might be the Edinburgh Logical Framework and Pure Type Systems. Some mechanismation of those is available, but whether that is usable for you I don't know.
> 10 votes

---
Tags: logic, sat-solvers, automated-theorem-proving, reasoning, smt-solvers
---


# Question
Title: Show that $T(n) = 2T(\lfloor n/2\rfloor) + n$ is $\Omega(n\log n)$ using substitution
I have to solve this using the **substitution method**.

**Floor** functions **cannot be skipped**.

---

IH: Assume that $T(k) \geq ck\log(k) $ for all $k \leq n$, where c is a constant.

IS: Must prove $T(k) \geq ck\log(k) $

Proof:

\begin{align\*} T(n) &= 2T(\left \lfloor{k/2}\right \rfloor ) + k\\ &\geq 2 c\left \lfloor{k/2}\right \rfloor\log(\left \lfloor{k/2}\right \rfloor) +k \end{align\*}

We now have two cases: $k$ is even and $k$ is odd. It is easy to prove this case when $k$ is even, **however I run into trouble when $k$ is odd.**

When k is odd, $\lfloor k/2\rfloor = (k-1)/2$, which gives

\begin{align\*} T(n)&\geq 2 c\tfrac{k-1}2\log(\tfrac{k-1}2) +k\\ &= c(k-1)\big(\log(k-1)-1\big) +k \qquad\qquad\text{(Since $\log2 = 1$)}\\ &= c\big(k\log (k-1) - k -\log(k-1) + 1\big) +k\\ &= ck\log (k-1) - ck -c\log(k-1) + c +k\\ &= ck\log k + ck\log\big(1-\tfrac{1}k\big) - ck -c\log(k-1) + c +k\\,, \end{align\*} where the last equality is because $\log(a-b) = \log\big(a\big(1-\tfrac{b}a\big)\big)$.

And here is where I am stuck. I have gotten the $ck\log k$, but cannot find the $c$ that will let me finish the problem.

Any help would be appreciated.

# Answer
One way to go around the difficulties is as follows.

First, you prove that $T(n) = \Omega(n \log n)$ when $n = 2^k$.

Second, you prove that $T(n)$ is monotone (given monotone base cases).

Third, you finish the proof as follows. Let $m \leq n \< 2m$, where $m = 2^k$. Then $$ T(n) \geq T(m) = \Omega(m \log m) = \Omega(n \log n). $$ Details left to you.
> 2 votes

---
Tags: recurrence-relation, induction, divide-and-conquer
---


title: Order of various functions

text:
# Question
Title: Order of various functions
I am to arrange the following 30 functions in terms of increasing order
**( all the lg (log) are to the base 2.<br>log\* represents iterated logarithm.)**

Here's my answer (*the functions on the same level are of the same order)*:

1 ,
lglg\*n

```
lg*n,      lg*(lgn)

```

,

,

,

,

I am not sure where to insert (logn)!. I know (logn)! = o((logn)^logn) and logn = o((logn)!), *isn't it*. But where exactly would it fit. Can anyone help me with that. Also I would really appreciate if someone could verify that my arrangement is right or not.

Thank you.

EDIT : I MEANT TO ASK THE POINT OF INSERTION OF (LOGN)! IN THE ABOVE LIST SORTED IN TERMS OF INCREASING ORDER. Simple.

# Answer
> 2 votes
Stirling's formula asserts that $$ n! = \Theta(\sqrt{n}(n/e)^n). $$ Thus $$ (\log n)! = \Theta(\sqrt{\log n}((\log n)/e)^{\log n}). $$

---
Tags: asymptotics
---


title: Sort Algorithm running in O(n)

text:
# Question
Title: Sort Algorithm running in O(n)
An array A holds n integers, and all integers in A belong to the set {0,1,2}. Describe an O(n) sorting algorithm for putting A in sorted order. Your algorithm may not make use of auxiliary storage such as arrays or hash tables. More precisely, the only additional space used, beyond the given array is O(1). Give an argument to explain why your algorithm runs in O(n) time.

*This is a self-answered question, but other answers are certainly desired.*

# Answer
> 4 votes
My answer was the following:

```
 Algorithm Sort(A, n)
   Input: an array A of n integers, the element of A belong to the set {0,1,2}
   Output: A is sorted
   int zero ← 0, one ← 0
    for i = 0 to n-1
    // we count the number of occurrences of each element in the array
    switch(A[i])
      case 0:
        zero ← zero + 1
      case 1:
        one ← one + 1
    // 2 would be be n - ( zero + one)
    // now we populate the array
    for i = 0 to n – 1{
      if i < zero then A[i]  = 0
      else if i < zero + 1 then A[i] = 1
      else A[i] = 2

```

The algorithm traverses the array twice, so its execution time is at least 2n. I was thinking of a way to get rid of the second for loop, but I doubt it can be avoided, unless the input array is already sorted or it contains element of the same type. In any case 2n is O(n).

# Answer
> 3 votes
This is the Dutch National Flag Problem. It has been examined in depth due to its use in Quicksort, and methods are given in the literature about that algorithm. Sedgewick gives a method in his paper on Multikey Quicksort due to the need for ternary partitioning in radix-based sort.

James R. Bitner, “An Asymptotically Optimal Algorithm for the Dutch National Flag Problem,” SIAM J. Comput., 11(2), 243–262 found lower bounds on swaps and how to get arbitrarily close to them (i.e. how to tune the constant on O(n) as a function of working space).

---
Tags: algorithms, sorting
---


# Question
Title: What is the $\mathcal O$ of subtraction-based GCD algorithm?
Subtraction-based algorithm for finding the greatest common divisor works like this:

For two integers a and b (a \> 0, b \> 0),
if a \> b, then gcd(a, b) = gcd(a-b, b)
else if b \> a, then gcd(a, b) = gcd(a, b-a). else if a = b gcd(a, b) = a

What is the $\mathcal O$ of this algorithm?

# Answer
Suppose that $a,b$ are the two input numbers. At each step of the algorithm, the sum $a+b$ decreases, since (assuming $a \> b$), the new numbers are $a'=a-b,b'=b$, and $a'+b'=a \< a+b$ (since we stop when $b=0$). Thus the algorithm terminates in at most $a+b$ steps. This is almost tight: if $b = 1$, then the algorithm terminates in $a$ steps.

Summarizing, on inputs $a,b$, the number of steps (or arithmetic operations) is at most $a+b$, and could be as bad as $a$. In terms of the *length* $n$ of the input (number of bits needed to represent it), the number of operations is at most $O(2^n)$ (since $a,b \leq 2^n$), and could be as bad as $\Omega(2^n)$ (when $a = 2^n,b=1$). Thus the *worst-case* running time (as measured by number of steps) is $\Theta(2^n)$, where $n$ is the input length.
> 4 votes

# Answer
For subtraction-based GCD algorithm (with checking for 0 value and signs of numbers to make it work) the complexity is $\mathcal O(n)$ which is easily seen by using gcd(n, 1) which takes $n$ steps. This steps depend on the *actual value* not like in standard case the *length of the input*, so algorithm is in fact exponential.

Avoiding corner cases the worst case occurs when two numbers are coprime. The property of gcd is that $gcd(ma, mb) = m\*gcd(a, b)$. When the numbers are coprime, meaning that in the factorization of a and b there are no common primes, which yields irreducible pair, so algorithm must continue to the only common divisor: 1.
> 1 votes

# Answer
gcd (n, 1) requires n-1 steps. The algorithm is therefore exponential in the size of the inputs.
> 1 votes

# Answer
Try calculating gcd (1, 0) using that "algorithm". It doesn't seem to be an algorithm, because it never finishes. Fix your question. Also, please think about the problem more carefully before asking.
> -2 votes

---
Tags: algorithms, asymptotics
---


# Question
Title: Understanding state table for turing machine
I'm having trouble understanding state tables for turing machines where the state table shown in the above image is supposed to show the change from the top turing machine to the bottom such that an extra 1 was added at index 5. I don't see how when S0 reads 1 (at start, index 1) and shifts the head right it then reads 0 and then writes 1, as when it shifts right shouldn't the head be at index 2 and read 1? And if the head was at index 2 then the finish at S2 would be at index 2 as well (since it shifts left and then right again)?

# Answer
> 2 votes
They're the same Turing Machine, to be specific - the top diagram is a representation of the tape before the TM has run, and the bottom diagram is after.

There's no key regarding how to read the state transitions but I'm assuming `>>` means shift right one cell, `<<` means shift left one cell and `1` means stay put.

You are right that the first move would be to index 2, using the first rule. But this rule applies three more times still, so the head ends up at index 5, where it encounters 0 and enters state S1 via the second rule - at the same time writing 1 at index 5.

The head then shifts back all the way to index 0 (one cell at a time) using the third rule, at which point the fourth rule is used (read 0, switch to S2, shift right). So it moves right to index 1 and then stops, as S2 is the final state.

---
Tags: turing-machines
---


# Question
Title: What is a "name/variable of base type" in applied $\pi$-calculus?
I'm studying the articleVerifying privacy-type properties of electronic voting protocols which uses Applied $\pi$-calculus to formalize voting protocols and verifies some privacy-related properties.

In certain parts of the paper they define some transformations over processes which are defined inductively. For example:

> **Definition** (**Process** $P^{ch}$) Let $P$ be a plain process and $ch$ a channel name. We define $P^{ch}$ as follows:
>
> * $0^{ch} \equiv 0$
> * $(P|Q)^{ch} \equiv P^{ch} \equiv Q^{ch}$
> * $(\nu n.P)^{ch} \equiv \nu n.out(ch, n).P^{ch}$ when $n$ is name of base type
> * $(\nu n.P)^{ch} \equiv \nu n.P^{ch}$ otherwise
> * $\ldots$

The idea is that they want to model a voter, which is a process, that wants to provide information about how he voted to the attacker (think: guy $X$ buys the vote of $Y$ and wants a "receipt" to be sure that $Y$ voted how he wanted). What I don't understand exactly is when is that $n$ a "name of base type"?

I've read the article *Mobile Values, New Names, and Secure Communication* where Applied $\pi$-calculus was first defined but here they just say that they assume that terms have some kind of type-system behind the scenes and the only thing they say is that the type system must include the type $\texttt{Channel}\langle \tau\rangle$ for every type $\tau$.

So, does the condition "when $n$ is name of base type" simply means "$n$ is not the name of a channel"? This would make sense, because in formalizing these protocols it is assumed that there exists some private channels between voter and authorities that the attacker can not eavesdrop due to physical limitations (they represent the voting booth).

# Answer
“Base type” is a type that isn't built from other types. Types built from other types include data structures (e.g. lists, arrays, pairs, …), functions, etc. In the context of the pi-calculus, base types exclude channel types.

Some typical example of base types in practice are integers, booleans, floating point, etc. From a theoretical point of view, a base type is one that is a base case in the type grammar, and more generally this implies that there's no type equation that relates this type with “interesting” constructed types. For example, a value of a base type is not a channel or anything that contains a channel.

“$n$ is name of base type” here means that $n$ is a channel that transports opaque values, as opposed to a channel that can transport a channel name. So $(\nu n.P)^{ch} \equiv \nu n.\mathsf{out}(ch, n).P^{ch}$ holds only when the output operation isn't extruding any of the channels in $P$.
> 3 votes

---
Tags: type-theory, communication-protocols, pi-calculus
---


# Question
Title: How do neural networks create results like its inputs?
I understand basic neural networks (input layer, hidden layers, output layer) and gradient descent learning. However I keep hearing about news talking about neural networks painting and making jazz music. That is puzzling me.

As I understand a neural network, you feed it the input data (i.e. a picture, music, ...) and it gives you some kind of classification on the result. But by reading those results it looks as if they were using the neural network to generate new results based on a training dataset. Because of that, I'm thinking the kind of neural networks they're referring to is essentially different from the ones I've studied, so I'd like to ask:

* What are the differences between classic neural networks and the ones used to run these experiments? What makes them fundamentally different so that they are able to generate results similar to its input?
* Do these results (generating results with a NN) have anything to do with deep learning? Or is deep learning just a better learning technique?

# Answer
These are known as Autoencoders. As you said, these neural networks are trained to produce output that is similar to the input, rather than output a classification of some kind.

Internally, they do not differ much from other neural net designs. Simply, the expected output is the input (or a slight variant of the input), rather than a classification.

One difference however is often the level of depth. Networks designed to replicate sequences, like writing jazz music, need to remember a sequence throughout training and prediction. This is where deep learning succeeds better than other methods.

This paper briefly discusses one type of an auto-encoding network and how it's used to produce music. I think you will find the design is very similar to a traditional neural network.
> 6 votes

---
Tags: artificial-intelligence, neural-networks
---


# Question
Title: How does a recurrent connection in a neural network work?
I am reading a very interesting paper on genetic algorithms which define neural networks. I am familiar with how a feedforward neural network operates, but then I came across this:

Where node #4 goes back to connect to #5. I was wondering how this is handled? Does the state of node 4 get kept from the last timestep and applied to node 5 when it is time to calculate its activation?

# Answer
When a recurrent network is calculated you can imagine the network is 'unrolled' out through time.

When visualized this way, you can see activation and loss can be calculated using the same method as a typical network.

So to clarify using the example you provided. Yes, the input to node #5 is the output from node #1, node #2, and the previous time steps node #4.

It is important to note; Typically the input and output to RNN's are expected to be time dependent. That is, for each time step *t* there is input *t* and output *t*. This makes RNN especially good at things like evaluating sequences. Although it is possible to keep the input and output equal throughout time.
> 2 votes

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


# Question
Title: Non-primitive recursiveness in real world nonmathematical software?
Is there a real world nonmathematical example of computer software that isn't primitive recursive?

I'm not interested in examples that are somehow closely related to theory of computation or logic (like automated theorem proving, model checking, compiler design etc.), or examples that aren't primitive recursive in a trivial way (i.e. having unbounded loops that could have been bounded).

The example doesn't have to be an actually existing piece of code (although it would be great if it is).

# Answer
> 1 votes
Many useful pieces of software have "unbounded" loops that can't be trivially bounded. Any program with a user interface that waits for input, for example. You'd probably also be surprised by the number of software that contains an interpreter of some sorts: your browser, your PDF reader, the software on your printer...

---
Tags: computability, primitive-recursion
---


# Question
Title: Complexity of algorithm to find number of elements > element index i in an array
The question is:

Given an array of size N, arr, create another array whose index i = number of elements in sub-array(arr, i+1, N-1) that are greater than arr\[i\].

Eg. if input array is, 5 3 9 8 2 6 output array is 3 3 0 0 1 0

O(N^2) is simple just two for loops.

I think a O(N\*logN) is possible by starting from last element and adding each element to a height-balanced BST with a size element.

Any thoughts on if we can do O(N)?

# Answer
***TL;DR***: There is a simple algorithm that runs in time $O(n \log n)$ and finds the inversion vector of a given array. Furthermore, there is a time lower bound of $ \Omega (n \log n) $ for any comparison-based algorithm for this problem, based on a reduction to the sorting problem. I have never read the paper Yuval Filmus referenced to in his answer, but from a brief reading it seems that the operations that the data structure permits are not exactly what you need in order to implement an algorithm for computing the inversion vector.

---

***The lower bound***:

*Edit: As D.W. mentioned, the $ Ω(nlogn) $ lower bound only holds for comparison-based algorithms. There exist sorting algorithms whose running time is $o(nlogn)$, by going outside the comparison-based model.*

Suppose by negativity that there exists an algorithm $\mathcal A$ that, given an array of elements $X$ and its length $n$, returns their inversion vector $Y$ in time $o (n\log n)$. Given the assumed algorithm $\mathcal A$, we present a sorting algorithm.

*Sorting algorithm*:

Input: an array $X$ and its length $n$. In order to simplify the proof, we assume that all of the elements in $X$ are unique, i.e. that no element appears more than once in $X$.

Output: an array that consists of the elements in $X$, in a sorted order.

1. Compute $Y\_1 = \mathcal A (X,n)$. Intuitively, $Y\_1 \[i\]$ contains the number of elements in $X$ that are larger than $X\[i\]$ and "to its right".
2. Generate the array $R = reverse(X)$, i.e. $R\[i\] = X\[n-i\]$ for every $i \in \[n\]$.
3. Compute $Y\_2 = \mathcal A (R,n)$. Intuitively, $Y\_1 \[i\]$ contains the number of elements in $R$ that are larger than $R\[i\]$ and "to its right", i.e. the number of elements in $X$ that are larger than $X\[n-i\]$ and "to its left".
4. Generate a new array $I$ that satisfies: $I\[i\] = Y\_1 \[i\] + Y\_2 \[n-i\] + 1$ for every $i\in \[n\]$. Intuitively, $I\[i\]$ is the number of elements that are greater than or equal to $X\[i\]$ in $X$, i.e. the position in which we should put $X\[i\]$ in the output array.
5. Generate the output array: $O\[I\[i\]\] = X\[i\]$ for every $i\in \[n\]$.

The correctness of the algorithm is immediate. As to its complexity, steps 2,4 and 5 take $O(n)$, and steps 1 and 3 take $o(n \log n)$. We were therefore able to sort an array in time $o(n\log n)$, which contradicts the known lower bound of $\Omega(n\log n)$ for sorting.

---

***An algorithm that runs in time $O(n\log n)$***:

1. Create an empty balanced binary search tree, e.g. an *AVL* tree or a *red-black* tree. Each node in the tree will hold additional information of the number of elements in its subtree. This data can be easily maintained in insertions and deletions.
2. Go over the input array from right to left, and for each element $X\[i\]$:
    * Insert $X\[i\]$ to the tree. While doing so, use the additional information in the nodes in order to compute the number of elements in the tree that are larger than $X\[i\]$, and save the result in $O\[i\]$.
    * Finally, update the additional information along the insertion path in the tree and re-balance the tree.
3. Output the array $O$.

The correctness of the algorithm follows from the fact that we insert the elements to the tree from the rightmost element in the array to the leftmost element in the array. Therefore, when inserting the element in the $i$'th position to the tree, the elements that are currently in the tree are all of the elements to its right, and hence the computation in step 2 returns the number of elements in the array that are larger than the $i$'th element and to its right, as desired.

As for the complexity of the algorithm, since the height of the tree is $O(\log n)$, the algorithm runs in time $O(n \log n)$.

Hope that helps :)
> 6 votes

# Answer
Your problem is very related to that of computing the number of inversions in a permutation, or (equivalently) the Kendall tau distance between two permutations; this is the sum of your vector. In fact, your vector (with a very superficial change in the definition) is known as the *inversion vector*.

There is a classical data structure of Dietz that can be used to compute the inversion vector in time $O(n\log n/\log\log n)$; the $O(n\log n)$ solution you mention is the baseline here. Fredman and Saks proved a matching lower bound showing that the time complexity of Dietz's data structure is optimal. Computing the insertion vector can however be done faster: Chan and Pătraşcu give an $O(n\sqrt{\log n})$ algorithm (see under "Offline dynamic ranking and selection").
> 8 votes

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


# Question
Title: When a trained RNN is tested, is the number of time-steps same for every input?
I am a beginner in deep learning so bear with me. If I want to unfold the RNN in order to represent the relation of output to the input as a non-recursive functions I would have to know the number of time steps it takes for the RNN to make a prediction, correct? Hence it is important for me to know if the number of time steps is the same for every test input.

Will the number of time steps for an RNN which is unchanged in any way always stay the same?

# Answer
> When a trained RNN is tested, is the number of time-steps same for every input?

Typically, yes. If an input is too short, it can be padded. If an input is too long, it can encoded in some way to reduce length. A good discussion of these methods can be found here.

The reason I said typically is because an RNN is producing an output after each time step *t*. That is for each time step *t* there is an input *t* and output *t*. In classification tasks, we usually only want the last output. But in generative tasks we would want the output at each time *t*. It is certainly possible for the length to differ between inputs.

So like most things in machine learning the answer is, *it depends*.
> 1 votes

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


title: Prove that if f ∉ ω(g) →f∈O(g)

text:
# Question
Title: Prove that if f ∉ ω(g) →f∈O(g)
I am trying to prove the statement in the title. I have a hard time proving it is true. The way I go about it is by using the definition of $\omega$:

$c\times g(n) \< f(n)$; So that if $f \notin \omega(g)$, then $\mathrm{NOT} (c\times g(n)\<f(n))$ means that $c\times g(n) \geq f(n)$. And that by definition is Big-Oh.

Is this a correct way of proving the statement in the title?

Thanks, Lukasz

Remarks:

The definition of $\omega$ is that $f(n)$: for all constants $c \> 0$, there exists a constant $n\_0\>0$ ...

So, the negation of that would be: There exists $c\times g(n) \geq f(n)$, correct? Can you think of an example that would disprove the statement?

Note to the comments:

I think I understand what you are saying. Since the definition states that "for all $c\>0$, there exists a constant $n$ ..." The negation of that is: "There exists a constant $c\>0$, for which this is not true..."

However, for any $c\>0$ there is a constant $n$ big enough that will make the statement true. Am I wrong?

# Answer
> 9 votes
The claim is not true (unless you add some "nice" conditions on the functions).

Take, for example, the functions $g(n)=n$, and consider the following function $f$: on the even numbers, we'll take $f(n)=n^2$, and on the odd numbers, take $f(n)=n$.

Since $n\notin \omega(n)$, then the assumption holds (that is, $f(n)\notin \omega(g(n))$), but since since $n^2\notin O(n)$, we also have that $f(n)\notin O(g(n))$.

# Answer
> 1 votes
The key to understand why that statement is false (without conditions on f and g) is to think that if $g$ is not a lower bound for $f$, it does not mean is an upper bound. It could be the case that neither $f$ is a bound for $g$, nor $g$ is a bound for $f$. An example for this is a function $f$ that is, informally, half in $O(g)$ (for even values) and half in $\omega(g)$ (for odd values), so $f$ is neither $O(g)$ nor $\omega(g)$. Details left to you.

Anyway, let's follow the definition and try not to mess things up with the existentials and universals.

$f \in \omega(g) \iff \forall c \> 0.\ \exists n\_0.\ \forall n ≥ n\_0.\ cg(n) \< f(n) \quad $

On the other hand,

$f \in O(g) \iff \exists c \> 0.\ \exists n\_0.\ \forall n ≥ n\_0. f(n) ≤ cg(n) \quad $

So if we have that $f \notin \omega(g)$ then

$f \notin \omega(g) \iff \exists c \> 0.\ \forall n\_0.\ \exists n \> n\_0.\ \neg (cg(n) \< f(n)) \iff $

$\hspace{15.5ex} \exists c \> 0.\ \forall n\_0.\ \exists n \> n\_0.\ f(n) \leq cg(n)$

In conclusion, applying the negation to the definition you get something which is not what you need. We manage to get a $c$, and maybe we can pick a $n\_0$ as being the minimum one, but we cannot guarantee that the inequality will hold **forall** $n$s as required.

So, this is not a proof, to proove the statement wrong you need to show that the counter example really works, but maybe this can help you too see why, and how to work with this kind of definitions.

---
Tags: asymptotics, proof-techniques
---


title: What does Harper mean by "class"?

text:
# Question
Title: What does Harper mean by "class"?
I've been teaching myself type theory on and off over the past couple years. I've reach large sections of Pierce's *Types and Programming Languages* and Harper's *Practical Foundations for Programming Languages*, but there are still sections I need to either read for the first time or really understand.

In Harper's section on *classes*, this is his introduction:

> It frequently arises that the values of atype are partitioned into a variety of classes, each classifying data with distinct internal structure. A good example is provided by the type of points in the plane, which may be classified according to whether they are represented in cartesian or polar form. Both are represented by a pair of real numbers, but in the cartesian case these are the x and y coordinates of the point, whereas in the polar case these are its distance, r, from the origin and its angle, θ, with the polar axis. A classified value is said to be an object, or instance, of its class. The class determines the type of the classified data, which is called the instance type of the class. The classified data itself is called the instance data of the object.

As far as I can tell, this does not align closely with objects as they are commonly understood in programming languages today. When I think of classes, I think primarily of *encapsulation* and *inheritance*, not of classifying different representations of a value.

Am I right in believing this is not the same definition of classes that is commonly used? Is this definition common in the academic community? Are there any programming languages where these kinds of classes are used?

## Update

Since this question seems to have attracted some recent activity, I'll update with my current understanding.

We start with the general, abstract notion of a two-dimensional table. Each cell in the table specifies a function acting on a specified type. Thus, the rows are "classes" and the columns "methods" with dynamic dispatch.

If we take the row-oriented view, then we have the standard notion of a class in mainstream OOP languages: a record of functions acting on a specified type of data. If we instead take the less commonly considered column-oriented view, we have a function that uses case analysis on the type of its first argument. The fundamental take-away is that neither the row or column-oriented view is more natural; we must understand classified values as a two-dimensional table.

It does turn out that we need need sum types to implement this realization, but that is only one aspect. We also need product types, and then to view these product and sum types in the right light.

# Answer
The term *class* here has absolutely nothing to do with OOP classes. Rather, a class determines which possibility in a C `union` an object takes.

For example, one definition of a binary tree is: a binary tree is either a leaf or a pair of binary trees. Leaves form one (boring) class, pairs of binary trees form another.

Mathematical terminology often uses words which have other meanings in common usage. You should get used to that.
> 2 votes

# Answer
This is a very generic, informal definition of the concept of classes which is commonly implemented in programming languages. I can't think of a programming language that uses the term “class” in a different sense, except where “class” is used in its everyday meaning where it is a synonym of “category”, “type”, “sort”, etc. You may not recognize it because this is only a small part of the class systems of the language(s) that you're used to, but that's the core of the concept.

Would you recognize a car engine if it was sitting there outside of a car? You don't need to have any idea what a car engine looks like to drive a car, but a book about building cars definitely needs to describe engines in detail. Engines don't look at all like a car (no wheels, no windows, …) but they are a core part of a care nonetheless.

An *object* consists of some data — the values of the instance fields — together with a class indication. A *class* is the type of all the objects with a given class indication, i.e. a class is a way to categorize objects. The intent of the class is to reflect the semantics of the instance fields. I don't have the book at hand, but I expect it to mention *methods* soon after, which are functions attached to an object or to the class (depending on whether they are virtual or static methods, to use common OOP terminology).

The definition is very generic and covers, for example, type classes as well as the class systems with dynamic dispatch that you're probably more familiar with.

Encapsulation and inheritance are common properties of object-oriented languages, but they are not inherent properties of classes: they are constructions that can be expressed in a language of classes. Encapsulation is done by allowing different classes to expose the same interface, typically either with a class-implements-interface as in Java or with a multiple inheritance system where a class implements only its ancestors as in C++. Inheritance is a mechanism whereby classes are defined from other classes by specifying the differences between the parent class and the derived class.
> 2 votes

---
Tags: terminology, programming-languages, type-theory, object-oriented
---


title: Asymptotic analysis of statements

text:
# Question
Title: Asymptotic analysis of statements
I was wondering if you could double check on the following statements being true, false or non-conclusive (as in in some cases true, but false in others). Here they are:

1) $F(n) = \log (n^n)$ implies $F(n) = \Theta(\log n)$.

Answer: It is a tough one? It is confusing because of $n^n$. My assumption would be to have it as non-conclusive. It is because for some cases, where $n$ is even a bit large, $\log$ will greatly decrease $F(n)$'s value. For abysmally large numbers, it will be significant, i.e. $n = 10000000$. Maybe I am wrong?

2) $F(n) = n \log n + n^2$ implies $F(n) = \Omega(n \log n)$.

Answer: True. We drop $n \log n$ (since it is not significant) and indeed $n^2$ will grow asymptotically faster (it is slower) than $n \log n$.

3) $F(n) = n!$ implies that $F(n) = O(2^n)$.

Answer: False. $n!$ grows faster than $2^n$. Therefore it would be $\Omega(2^n)$ not $O(2^n)$.

# Answer
> 1 votes
The function $\log(n^n) = n\log n$ grows much faster than $\log n$, so we can conclusively say that $\log(n^n) = \omega(\log n)$. It even grows much faster than $n$, so $\log(n^n) = \omega(n)$.

You say that whether $\log(n^n) = \Theta(\log n)$ (where perhaps you mean $\Theta(n)$ instead of $\Theta(\log n)$) is "inconclusive", since for small $n$ there is one behavior, and for large $n$ there is another. *For asymptotic analysis we care* only *about the behavior for large $n$*.

---
Tags: asymptotics
---


# Question
Title: Is SAT-Problem with XOR and AND NP-complete
Is this problem NP-complete?

I have many restrictions like this and want to find a feasible solution:

((a and b) xor (c and d)) = 1

with a,b,c,d are arbitrary literals. It looks similar to XOR-2SAT but has additional ANDs inside the clause.

# Answer
Your question is likely answered by Schaefer's dichotomy theorem. In particular, if an instance of your problem is a conjunction of formulas, each one depending on a bounded number of variables, then according to the theorem your problem is either in P or NP-complete; and moreover there is a simple criterion to decide which case it is.
> 4 votes

---
Tags: np-complete, satisfiability, 2-sat
---


# Question
Title: How to add two numbers in IEE754 half precision format?
i'm trying to understand how to add two numbers in IEE754 half precision format , i haven't found a good reference/tutorial on this , so i've tried to follow the 32 bit floating point addition procedure , but at some point i'm stucked , what i know is:

Half precision (16 bit) IEEE 754 floating point number bit configuration is:

1 bit for sign 5 bit for exponent bit and 10 bit for mantissa.

i have two numbers:

1110001000000001 0000001100001111

so i rewrited them as

1 11000 1000000001 0 00000 1100001111

before adding them i have to convert them in normalized binary scientific notation (i don't know if i'm right):

Convert the exponent of the first number in decimal: 24 Subtract bias (that is 15) so i have: 24-15 = 9 so the exponent is 9

so the mantissa is : 1.000000001 * 2^9

But i don't know how to continue , can someone please explain me the correct process for solving this , or link me a good reference/title of a book for understanding this procedure? i'm searching on Google and trying to understand on different books , but i can't clarify this procedure to myself.

# Answer
> 1 votes
The second number has zero as exponent and has non zero mantissa, so it is a Denormal (aka Subnormals)

```
0 01111 1100001111 = 1.1100001111 * 2**0   = 1.1100001111
0 01110 1100001111 = 1.1100001111 * 2**-1  = 0.11100001111
0 01101 1100001111 = 1.1100001111 * 2**-2  = 0.011100001111
0 01100 1100001111 = 1.1100001111 * 2**-3  = 0.0011100001111
0 01011 1100001111 = 1.1100001111 * 2**-4  = 0.00011100001111
0 01010 1100001111 = 1.1100001111 * 2**-5  = 0.000011100001111
0 01001 1100001111 = 1.1100001111 * 2**-6  = 0.0000011100001111
0 01000 1100001111 = 1.1100001111 * 2**-7  = 0.00000011100001111
0 00111 1100001111 = 1.1100001111 * 2**-8  = 0.000000011100001111
0 00110 1100001111 = 1.1100001111 * 2**-9  = 0.0000000011100001111
0 00101 1100001111 = 1.1100001111 * 2**-10 = 0.00000000011100001111
0 00100 1100001111 = 1.1100001111 * 2**-11 = 0.000000000011100001111
0 00011 1100001111 = 1.1100001111 * 2**-12 = 0.0000000000011100001111
0 00010 1100001111 = 1.1100001111 * 2**-13 = 0.00000000000011100001111
0 00001 1100001111 = 1.1100001111 * 2**-14 = 0.000000000000011100001111
0 00000 1100001111 = 0.1100001111 * 2**-14 = 0.000000000000001100001111

```

Denormals have no leading 1 and use the same exponent as smallest normal numbers.

To perform an addition, you need to align mantissas, then perform an addition or a subtraction (if the signs are opposite, as this is the case here.) :

```
  -1000000001.0
  +         0.000000000000001100001111
 =-1000000000.111111111111110011110001

```

Here the difference between the two numbers is too large and the small number will disappear after rounding, except if you use a special rounding mode (as round towards zero or towards +infinite)

Maybe you have other sample additions that are more interesting.

---

Using two's complement, one can make subtractions out of additions :

```
    -         0.000000000000001100001111
 ! = 1111111111.111111111111110011110000 : Invert all digits
+1 = 1111111111.111111111111110011110001 : plus one.

```

The addition-that-is-a-subtraction becomes :

```
     1000000001.000000000000000000000000
   + 1111111111.111111111111110011110001
= [1]1000000000.111111111111110011110001

```

---
Tags: information-theory, floating-point
---


# Question
Title: In the Gas-Up problem, how is the amount of gas the same up to a cyclic shift regardless of starting city?
I'm working through *Elements of Programming Interviews* as practice for finding a job. I've spent a ridiculous amount of time on Problem 18.7.

> In the gas-up problem, $n$ cities are arranged on a circular road. You need to visit all of the $n$ cities and come back to the starting city. A certain amount of gas is available at each city. The total amount of gas is equal to the amount of gas required to go around the road once. Your gas tank has unlimited capacity. Call a city $c$ *ample* if you can begin at $c$ with an empty tank, refill at it, then travel through each of the remaining cities, refilling at each, and return to $c$, without running out of gas at any point. See Figure 18.3 for an example. \[You can see Figure 18.3 on the Google Books result if you search for "Elements of Programming Interviews Problem 18.7.\]
>
> Given an instance of the gas-up problem, how would you efficiently \[i.e. in $\mathcal{O}(n)$ time or better\] compute an ample city, if one exists?

I couldn't figure it out. I read the hint, and I still couldn't figure it out. I gave up, and read the answer in the back of the book. I still couldn't figure it out. I searched Google and this site for a more complete solution, but didn't find one.

This is the part that's getting me:

> On closer inspection, it becomes apparent that the graph of the amount of gas as we perform the traversal is the same up to a cyclic shift regardless of the starting city.

I must not be inspecting closely enough, because this is not apparent to me at all. I tried calculating the remaining gas at each city during a traversal of an example circuit, starting at different cities (and permitting the number to be negative when necessary, as the solution suggests). There does not seem to be any relation between the series of numbers I get when starting at different cities. I understand, if we accept that the amount of gas remaining at each city is the same up to a cyclic shift, how the algorithm the solution gives would solve the problem. I cannot see how this is the case. What am I missing?

# Answer
> 4 votes
Suppose that starting at city $i$, traversing the cities in ascending order, we have $A\_j$ amount of fuel remaining when we arrive at city $j$. If instead we start at city $i+1$ then the amounts $A\_j$ will change by $\[\textrm{gas required to go from $i$ to $i+1$}\]-\[\textrm{gas at city $i$}\]$ for all $j$.

So the problem can be solved by computing the values $A\_j$ starting at city $0$, finding the minimum and then looping over all the cities, updating the minimum value until it becomes non-zero (at which point you've found an ample city).

# Answer
> 6 votes
This is over a year later, but I also found this question really frustrating, but after reading other explanations, I've finally figured it out. So, I want to share with everyone my findings!

In this problem we're guaranteed that the amount of gas is enough to go around the road once. We then have this equality
$Amount\_{gas}$ = $Amount\_{distance}$ $$\sum\_{i=1}^{n} x\_{i} = 0$$ where $x\_{i}$ is the Amount of gas at station i - the cost:
$$G\[i\] - D\[i\]$$

If we reach a point $j$ such that:

$$\sum\_{i=1}^{j} x\_{i} \< 0$$

This must mean $$\sum\_{i=j + 1}^{n} x\_{i} \> 0$$

Why!?!??! Because the problem promises us enough gas to cover the distance! $$\sum\_{i=1}^{j} x\_{i} + \sum\_{i=j + 1}^{n} x\_{i} = 0$$

If we start at point $j + 1$, which is right after we don't have enough gas, the equation becomes $$\sum\_{i=j + 1}^{n} x\_{i} + \sum\_{i=1}^{j} x\_{i} = 0$$

Starting at $j + 1$ means we have $\sum\_{i=j + 1}^{n} x\_{i}$ gas before j, so we won't have a negative number.

This agrees with the solution in EPI because we are in fact doing a vertical shift on our piecewise function $\sum\_{i=1}^{n} G\_{i} - D\_{i} $ The pictoral graph in EPI helps us see that it's not good enough to merely spit out the first j that gives us a negative value. If instead, we find the minimum, we will have more than enough gas before we reach j (first point that gives us negative amount of gas left) and cover subsequent negative gas stations until the aforementioned minimum.

# Answer
> 2 votes
I also had problems solving this task and I came up with an alternative `O(n)` solution, which I find more simple to understand (at least for me).

The idea is to start at some city and try to advance the head to the next city if we have enough fuel. If we can't advance the head, we move the tail. At each step we have to adjust the current fuel we have. This way we move like a caterpillar until we reach our own tail:

```
public static City findGasup(City city) {
    int currentGallons = 0;

    City head = city;
    City tail = city;
    while (true) {
        if (currentGallons + head.gallons >= head.miles / 20) {
            currentGallons += head.gallons;
            currentGallons -= head.miles / 20;

            if (head.next == tail) {
                return tail;
            }

            head = head.next;
        } else {
            currentGallons -= tail.gallons;
            currentGallons += tail.miles / 20;
            if (tail == head) {
                head = head.next;
            }

            tail = tail.next;
        }
    }
}

```

It requires at most 2 passes around the cities and we could also add a condition to terminate after those 2 passes in case there is no ample city.

# Answer
> 1 votes
The problem is not easy, it took me a lot of time to understand and prove the solution.
Model the problem to a sequence of integers: element at i = the remaining of gas after city i = G\[i\] – D\[i\]. In other words, the sum of any subsequence *i to j* is the remaining of gas after traveling from city *i* to city *j*.
We can find A, the minimum-sum subsequence (A = total of elements from beginning to the city *j* at which the sum is minimum), by traversing all the cities once; *the starting city does not matter*. Then the city *j+1* is the *ample city*.
Proof:
From the problem description: total of sequence = A + remaining = 0
When beginning at the city *j+1* right after the minimum city: remaining + S \>= remaining + A = 0
For any city inside remaining: Q \>= 0 because if Q \< 0 then A + Q \< A while A is the minimum
Therefore, sum of any of subsequence when beginning at *j+1* always \>= 0, i.e., never run out of gas.

---
Tags: algorithms
---


# Question
Title: Lower bound of a summation with an exponential
For the following (related to a binary tree complexity question):

$$f(n) = \sum\_{h=0}^{\lg{}n} h2^h$$

Is there any way to express this only in terms of $n$? Or approximate it?

---

Put in another way, I figure at worst for an upper bound, we could guess at it in the following way:

$f(n) = 0 + (1 \cdot 2) + (2 \cdot 2^2) + (3 \cdot 2^3) + ... + (\lg{}n \cdot 2^{\lg{}n})$

This means since we go from $0$ to $\lg{}n$, and the largest above when reduced is $n\lg{}n$, I could write $\mathcal{O}(n\lg^2{}n)$.

Supposedly $f(n)$ reduces to $\Theta(n\lg{}n)$ or better (by better I mean closer to $\Theta(1)$) and I'm struggling to show that... and I don't know if it's possible even. I can't prove it though so I can't claim it's not, reducing the summation if possible would hopefully lead to a quick answer.

# Answer
There is a general formula for this sum: $$ \sum\_{h=0}^m h2^h = \sum\_{h=1}^m \sum\_{k=1}^h 2^h = \sum\_{k=1}^m \sum\_{h=k}^m 2^h = \sum\_{k=1}^m (2^{m+1}-2^k) = m2^{m+1} - (2^{m+1}-2). $$ Overall, we get $$ \sum\_{h=0}^m h2^h = (m-1)2^{m+1} + 2. $$ When $m = \lg n$, this works out to be $2n\lg n - 2n + 2$.
> 8 votes

# Answer
Exponentials grow *very fast* — your very first guess should be that the sum is asymptotically on the order of its final term.

In fact, it's easy to get actual bounds here. It's should be familiar result that $2^m$ is larger than $\sum\_{k=0}^{m-1} 2^h$ (but if not, it's a geometric series), and so $m 2^m$ is larger than $\sum\_{h=0}^{m-1} m 2^h$ which is larger than $\sum\_{h=0}^{m-1} h 2^h$. Thus,

$$ m 2^m \< \sum\_{h=0}^m h 2^h \< 2 m 2^m $$

with $m = \lfloor \lg n \rfloor$, it's now esay to see the sum is $\Theta(n \lg n)$.

If you care about the overall constant, since only the last terms matter and for those $h \sim m$, you should guess $\sum\_{k=0}^m h 2^h \sim m \sum\_{k=0}^m 2^h \sim 2m 2^m$.

We can establish rigorous lower bounds (or a slightly more precise upper bound) similarly. Taking the last $(k+1)$ terms gives

$$\begin{align} \sum\_{h=0}^m h 2^n &\> \sum\_{h=m-k}^m h 2^h \> (m-k) \sum\_{h=m-k}^m 2^h \\\&= (m-k) (2^{m+1} - 2^{m-k}) \\\&= 2m2^m (1 - \frac{k}{m}) (1 - 2^{-(k+1)}) \end{align}$$
> 2 votes

---
Tags: time-complexity, asymptotics, binary-trees
---


# Question
Title: Analyzing the time complexity of nested loops
So I've been given a piece of pseudo code that involves nested loops. The answer to this question is Θ(n^5) but I do not understand why it is so.

What is the time complexity of this code?

```
for  i = 1 to n
   for  j = 1 to n*n
      for  k = 1 to j
         Task

where the time complexity of Task is Θ(1)

```

The most inner loop, for k = 1 to j is Θ(j). Then the middle loop, for j = 1 to n^2 I thought, should produce Θ(n^2) as it loops from j = 1 to n^2 but I've been told it's Θ(n^4). I honestly do not understand how it could be Θ(n^4) when it's iterating from 1 to n^2. Can someone explain how this works in simple terms?

# Answer
You are correct: the middle loop executes $\Theta(n^2)$ inner loops.

What you are told is correct: the runtime of the middle loop is $\Theta(n^4)$.

Your mistake is confusing the two. The inner loop does not run in constant time, so you should not expect the middle loop to complete in $\Theta(n^2)$ time. You can, however, expect the middle loop to complete in

$$ \sum\_{j=1}^{n^2} \Theta(j) = \Theta\left( \sum\_{j=1}^{n^2} j \right) = \Theta(n^4)$$

time. (and with care, you can even make this calculation rigorous!)

You could heuristically guess that enough loop iterations take close enough to maximum time and guess the middle loop would take $n^2 \cdot \Theta(n^2)$ time, although this heuristic can go astray.

However, the heuristic can also be made rigorous -- e.g. by determining $\Theta(n^2)$ of the loop iterations will complete in half of the maximum time, or by determining that the last half of the loop iterations each take $\Theta(n^2)$ time.
> 3 votes

# Answer
Translating `for`-loops into sums is the best way to approach this as the resulting calculations are elementary. We get:

$\qquad\displaystyle\begin{align\*} \\#\mathrm{Task} \quad&= &&\sum\_{i=1}^n \sum\_{j=1}^{n^2} \sum\_{k=1}^j 1 \\ &= && \sum\_{i=1}^n \sum\_{j=1}^{n^2} j \\ &= && \sum\_{i=1}^n \frac{n^2(n^2 + 1)}{2} \\ &= && \frac{n^3(n^2 + 1)}{2}. \end{align\*}$

We use the closed form of the triangular numbers (which you find on any formulary if you have not memorized it). Finally, obtain a $\Theta$-class using standard tools.
> 4 votes

# Answer
For each value of $i$, the number of times that "task" is run is $$ \sum\_{j=1}^{n^2} \sum\_{k=1}^j 1 = \sum\_{j=1}^{n^2} j. $$ The latter sum is at least $$ \sum\_{j=1}^{n^2} j \geq \sum\_{j=n^2/2}^{n^2} n^2/2 \geq (n^2/2)^2 = \Omega(n^4). $$ It is also plainly at most $(n^2)^2 = O(n^4)$.
> 0 votes

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


title: Modal Logic - □ distribution over →

text:
# Question
Title: Modal Logic - □ distribution over →
In the modal logic K does □ distribution over →?

For example, would the following be correct?

□(p → q) ≡ □p → □q

# Answer
> 3 votes
No.

In the modal logic K, the formula □(p → q) implies □p → □q (by the distribution axiom) but it is *not* equivalent to it.

A possible intuition is as follows. Read □(p → q) as: every time it rains, my umbrella is open. Read □p → □q as: if it rains everyday, my umbrella is open everyday. In those worlds in which it rains sometimes but not always, the first formula implies that my umbrella is open on those days, the latter does not since its premise requires rain on all days.

---
Tags: logic, modal-logic
---


# Question
Title: Trying to understand this Quicksort Correctness proof
This proof is a proof by induction, and goes as follows:

P(n) is the assertion that "Quicksort correctly sorts every input array of length n."

Base case: every input array of length 1 is already sorted (P(1) holds)

Inductive step: fix n =\> 2. Fix some input array of length n.

Need to show: if P(k) holds for all k \< n, then P(n) holds as well

He then draws an array A partitioned around some pivot p. So he draws p, and calls the part of the array that is \< p as the 1st part, and the part that is \> p is the second part. The length of part 1 = k1, and the length of part 2 is k2. By the correctness proof of the Partition subroutine (proved earlier), the pivot p winds up in the correct position.

By inductive hypothesis: 1st, 2nd parts get sorted correctly by recursive calls. (Using P(K1),P(k2))

So: after recursive calls, entire array is correctly sorted.

QED

**My confusion**: I have a lot of problem seeing exactly how this proves the correctness of it. So we assume that P(k) does indeed hold for all natural numbers k \< n.

Most of the induction proofs I had seen so far go something like: Prove base case, and show that P(n) =\> P(n+1). They usually also involved some sort of algebraic manipulation. This proof seems very different, and I don't understand how to apply the concept of Induction to it. I can somewhat reason that the correctness of the Partition subroutine is the key. So is the reasoning for its correctness as follows: We know that each recursive call, it will partition the array around a pivot. This pivot will then be in its rightful position. Then each subarray will be further partitioned around a pivot, and that pivot will then be in its rightful position. This goes on and on until you get an subarray of length 1, which is trivially sorted.

But then we're not assuming that P(k) holds for all k \< n....we are actually SHOWING it does (since the Partition subroutine will always place one element in its rightful position.) Are we not assuming that P(k) holds for all k

# Answer
> 14 votes
We are indeed assuming $P(k)$ holds for all $k \< n$. This is a generalization of the "From $P(n-1)$, we prove $P(n)$" style of proof you're familiar with.

The proof you describe is known as the principle of strong mathematical induction and has the form

> Suppose that $P(n)$ is a predicate defined on $n\in \\{1, 2, \dotsc\\}$. If we can show that
>
> 1. $P(1)$ is true, and
> 2. $(\forall k \< n \\;\[P(k)\])\Longrightarrow P(n)$
>
> Then $P(n)$ is true for all integers $n\ge 1$.

In the proof to which you refer, that's exactly what's going on. To use quicksort to sort an array of size $n$, we partition it into three pieces: the first $k$ subarray, the pivot (which will be in its correct place), and the remaining subarray of size $n-k-1$. By the way partition works, every element in the first subarray will be less than or equal to the pivot and every element in the other subarray will be greater than or equal to the pivot, so when we recursively sort the first and last subarrays, we will wind up having sorted the entire array.

We show this is correct by strong induction: since the first subarray has $k\<n$ elements, we can assume by induction that it will be correctly sorted. Since the second subarray has $n-k-1\<n$ elements, we can assume that it will be correctly sorted. Thus, putting all the pieces together, we will wind up having sorted the array.

# Answer
> 7 votes
This proof uses the principle of *complete induction*:

> Suppose that:
>
> * Base case: $P(1)$
> * Step: For every $n \> 1$, if $P(1),\ldots,P(n-1)$ hold (*induction hypothesis*) then $P(n)$ also holds.
>
> Then $P(n)$ holds for all $n \geq 1$.

You can prove this principle using the usual induction principle by considering the property $$ Q(m) \Leftrightarrow P(1) \text{ and } P(2) \text{ and } \cdots \text{ and } P(m) $$ I leave you the details.

---

Now, let's use complete induction to prove that the following version of Quicksort sorts its input correctly:

```
Quicksort(A, n)
    if n = 1 then:
        return
    else:
        let X[1...x] consist of all elements of A[2],...,A[n] which are at most A[1]
        let Y[1...y] consist of all elements of A[2],...,A[n] which are larger than A[1]
        call Quicksort(X, x)
        call Quicksort(Y, y)
        set A to the concatenation of X, A[1], Y

```

Here `A[1],...,A[n]` is the input array, and `n` is its length. The statement that we want to prove is as follows:

> Let $A$ be an array of length $n \geq 1$. Denote the contents of $A$ after calling Quicksort by $B$. Then:
>
> 1. Quicksort terminates on $A$.
> 2. There is a permutation $\pi\_1,\ldots,\pi\_n$ of $1,\ldots,n$ such that $B\[i\] = A\[\pi\_i\]$.
> 3. $B\[1\] \leq B\[2\] \leq \cdots \leq B\[n\]$.

I will only prove the third property, leaving the rest to you. We thus let $P(n)$ be the following statement:

> If $A$ is an array of length $n \geq 1$, and $B$ is its contents after running `Quicksort(A, n)`, then $B\[1\] \leq B\[2\] \leq \cdots \leq B\[n\]$.

The proof is by complete induction on $n$. If $n = 1$ then there is nothing to prove so suppose that $n \> 1$. Let $X,x,Y,y$ be as in the procedure `Quicksort`. Since $x,y \< n$, the induction hypothesis shows that $$ X\[1\] \leq X\[2\] \leq \cdots \leq X\[x\] \\ Y\[1\] \leq Y\[2\] \leq \cdots \leq Y\[y\] $$ Moreover, from the way we formed arrays $X$ and $Y$, it follows that $X\[x\] \leq A\[1\] \< Y\[1\]$. Thus $$ X\[1\] \leq \cdots \leq X\[x\] \leq A\[1\] \< Y\[1\] \leq \cdots \leq Y\[y\]. $$ It follows immediately that $B\[1\] \leq \cdots \leq B\[n\]$. Thus $P(n)$ holds.

# Answer
> 4 votes
The missing part of the argument is *transitivity of '\<'* \- i.e the property that if a \< b and b \< c, then a \< c. The proof that the final array is sorted goes something like this:

Let A\[i\], A\[j\] be elements of the array post-sort, where i \< j. Then A\[i\] \< A\[j\] follows from one of the following placement cases (and there are no other cases):

(a) i and j are in the first partition - A\[i\] \< A\[j\] follows by recursion/induction.

(b) i and j are in the second partition - A\[i\] \< A\[j\] follows by recursion/induction.

(c) i is in the first partition and j is the index of the pivot - A\[i\] \< A\[j\] follows by proof of partition procedure.

(c) i is the index of the pivot and j is in the second partition - A\[i\] \< A\[j\] follows by proof of partition procedure.

**(e) i is in first partition and j is in second partition - then by partition procedure, A\[i\] \< pivot, and pivot \< A\[j\]. So by transitivity, A\[i\] \< A\[j\].**

---
Tags: correctness-proof, induction, quicksort
---


# Question
Title: Deriving the average number of inversions across all permutations
In the answer by Raphael to the question "Is there a system behind the magic of algorithm analysis?", there is an equation:

$$\qquad\displaystyle \mathbb{E}\[C\_{\text{swaps}}\] = \frac{1}{n!} \sum\_{A} \operatorname{inv}(A) \tag{1},$$

where $A$ is an array, $\mathbb{E}\[C\_{\text{swaps}}\]$ is the expected number of swaps it takes to sort a random permutation with Bubblesort, $n$ is the length of $A$, and $\operatorname{inv}(A)$ is the number of inversions of $A$.

Then (1) is equal to the following equation:

$$\qquad\displaystyle \mathbb{E}\[C\_{\text{swaps}}\] = \frac{1}{2} \cdot \binom{n}{2}. \tag{2}$$

But I don't understand how to prove (2) based on (1). Could anyone please give me a proof?

# Answer
You can not go directly from one equation to the other; you need to add a whole proof which is separate from what I explain there. Hence my statement "it has been shown".

A boring proof using induction is here.

For a constructive proof, you can follow the idea from here:

1. Show that the maximum number of inversions is $\binom{n}{2}$.
2. Observe that every permutation and its reverse pair up: their respective sets of inversions are complement to each other, so both together add $\binom{n}{2}$ inversions to the sum.
3. Since this pairing neatly and uniquely covers all permutations, we get that the total number of inversions across all permutations is $\frac{n!}{2} \cdot \binom{n}{2}$.

The claim follows immediately.
> 6 votes

# Answer
For $i \< j$ and a random permutation $A$, let $X\_{ij}$ be the indicator variable for the event $A\[i\] \> A\[j\]$. Clearly $\Pr\[X\_{ij} = 1\] = 1/2$ and so $E\[X\_{ij}\] = 1/2$. The total number of inversions is $\sum\_{i\<j} X\_{ij}$, and so the average number of inversions is $$ E\left\[\sum\_{i\<j} X\_{ij}\right\] = \sum\_{i\<j} E\[X\_{ij}\] = \sum\_{i\<j} \frac{1}{2} = \frac{1}{2} \binom{n}{2}. $$
> 7 votes

---
Tags: combinatorics, permutations
---


# Question
Title: How does the Galil's rule work on Boyer-Moore algorithm?
I would like to know how Boyer-Moore text searching algorithm with Galil's rule works,. I tried to search for but I couldn't understand the information I found, for example this Wikipedia page. And why with this rule we go to a linear time complexity?

# Answer
The algorithm is based on a simple principle. Suppose that we are trying to match a substring of length **n**. We are going to first look at character at index m. If that character is not in the string, we know that the substring we want can't start in characters at indices **1 2....n**

If that character is in our string, we will assume that it is at the last place in our string that it can be. We will then jump back and start trying to match the string from that possible starting place. This piece of information is my first table.

Once I start matching from the beginning of the substring, when I find a mismatch, I can't just start from scratch. I could be partially through a match starting at a different point. For instance if I'm trying to match *anand* in *ananand* successfully match, anan, realize that the following a is not a d, but I've just matched an, and so I should jump back to trying to match my third character in my substring. This, "If I fail after matching x characters, I could be on the y'th character of a match" information is stored in the second table.

Note that when I fail to match the second table knows how far along in a match I might be based on what I just matched. The first table knows how far back I might be based on the character that I just saw which I failed to match. You want to use the more pessimistic of those two pieces of information.
> 1 votes

---
Tags: algorithms, algorithm-analysis, search-algorithms, strings, exact-string-matching
---