# Question
Title: How does this allow list operations to be applied to lists with elements of any type?
In *Types and Programming Languages* by Pierce, Chapter 11 is simple extensions of the simply typed lambda calculus with any simple base types. Section 11.12 introduces Lists.

How does the section allow list operations to be applied to lists with elements of any type? Specifically, my confusions are:

* Does Section 11.12 introduce lists and list operations by making use of some kind of polymorphism, or type inference? (The book doesn't introduce type inference till Chapter 22 and parametric polymorphism till Chapter 23.)

Does "*When we ﬁrst introduced lists in §11.12, we used “custom” **inference rules** to allow the operations to be applied to lists with elements of any type*" in Section 23.4 mean that Section 11.12 makes use of type inference to achieve similar behavior of "polymorphism"?
* Does "*For every type `T`, the type `List T` describes ﬁnite-length lists whose elements are drawn from `T`*" in Section 11.12 mean

+ that `List T` is a single literal type name for all possible specific typess for `T`, or
    + that `List T` should be instantiated differently for different specific types for `T`, e.g. `List Boolean`, `List Nat`?
* Is `[T]` part of the the names of the list operators, e.g. `nil[T]`, `cons[T]`, `isnil[T]`?

Should `[T]` in `nil[T]` be instantiated differently for different specific types for `T`, e.g. `nil[Boolean]`, `nil[Nat]`?
* Does Section 23.4 use the same type `List T` as in Section 11.12? Where is `List T` defined?
* I think lists are not simple types but recursive types (not introduced till Chapter 20), so why does Section 11.12 cover lists?

Thanks.

> **11 Simple Extensions**
>
> **11.12 Lists**
>
> The typing features we have seen can be classiﬁed into base types like Bool and Unit, and type constructors like → and × that build new types from old ones. Another useful type constructor is List. **For every type `T`, the type `List T` describes ﬁnite-length lists whose elements are drawn from `T`.**
>
> Figure 11-13 summarizes the syntax, semantics, and typing rules for lists. Except for syntactic diﬀerences (List T instead of T list, etc.) and **the explicit type annotations on all the syntactic forms in our presentation**, these lists are essentially identical to those found in ML and other functional languages. The empty list (with elements of type `T`) is written `nil[T]`. The list formed by adding a new element `t1` (of type `T`) to the front of a list `t2` is written `cons[T] t1 t2` . The head and tail of a list t are written `head[T] t` and `tail[T] t`. The boolean predicate `isnil[T] t` yields true iﬀ t is empty.

and

> **23 Universal Types**
>
> **23.4 Examples**
>
> **Polymorphic Lists**
>
> As an example of straightforward polymorphic programming, suppose our programming language is equipped with a type constructor List and term constructors for the usual list manipulation primitives, with the following types.
>
> ```
> ñ nil : ∀X. List X
> cons : ∀X. X → List X → List X
> isnil : ∀X. List X → Bool
> head : ∀X. List X → X
> tail : ∀X. List X → List X
>
> ```
>
> When we ﬁrst introduced lists in §11.12, we used **“custom” inference rules** to allow the operations to be applied to lists with elements of any type. Here, we can **give the operations polymorphic types** expressing exactly the same constraints

# Answer
Most importantly, Section 11.12 does not introduce *polymorphic* lists, but introduces *monomorphic* lists annotated by a type of its elements.

For example, Fig. 11-13 introduces a new term `cons[T] t t`. Here `[T]` is a type annotation, which indicates a type of elements of the list. Note that `T` is a metavariable ranged over types, not an object-level type variable or a type-level abstraction. In other words, it is different statements that "For every type `T`, the type `List T` has property P" and "the type of polymorphic lists `∀X. List X` has property P". See Section 3.1 for details of metavariables.

I think most of your questions are answered in short by the above explanation. The followings are more detailed answers.

### Q1

* Does Section 11.12 introduce lists and list operations by making use of some kind of polymorphism, or type inference?

Neither. It introduces monomorphic lists annotated by an element type (No need of type *inference*).

### Q2

* What does *"For every type `T`, the type List T describes ﬁnite-length lists whose elements are drawn from `T`"* in Section 11.12 mean?

`T` is a metavariable. For instance, it implies a type `List Bool` describes finite-length lists whose elements are drawn from `Bool`.

### Q3

* Is `[T]` part of the the names of the list operators, e.g. `nil[T]`, `cons[T]`, `isnil[T]`?

`T` is a metavariable. It may give you an intuition to try typing some actual program which contains lists.

### Q4

* Does Section 23.4 use the same type `List T` as in Section 11.12?

Yes/No. Both sections try to define the type `List T` as "a type of lists whose elements are drawn from `T`", but they define `List T` individually: `List T` of Section 11.12 is defined in Figure 11-13, and `List T` of Section 23.4 is defined informally in sentences.

> ... suppose our programming language is equipped with a type constructor `List` and term constructors for the usual list manipulation primitives, with the following types. ...

As written in the book, the notation of `List T` is the same, but list-related primitives are defined differently.

### Q5

* I think lists are not simple types but recursive types (not introduced till Chapter 20), so why does Section 11.12 cover lists?

Chapter 20 describes a type system to handle general recursive types, rather than a specific recursive type (e.g. `List T`). Actually the beginning of Chapter 20 takes `List T` as an example of recursive types.
> 1 votes

---
Tags: programming-languages, type-theory, polymorphisms
---


# Question
Title: Find first occurence of multiple tokens using C++
I am using C++03. I have a stream of chars and I need to find the first token from a group of tokens. That is, I need to find the lowest indexed match. Specifically, the stream is just an char array, and the tokens of interest are listed below. The start of a token can occur anywhere in the stream (and not necessarily at position 0).

* ssh-{rsa|dsa|ed25519}
* ecdsa-sha2-{nistp256|nistp521}
* ---- BEGIN SSH2 PUBLIC KEY ----
* -----BEGIN RSA PRIVATE KEY-----
* -----BEGIN DSA PRIVATE KEY-----
* -----BEGIN EC PRIVATE KEY----- (ecdsa)
* -----BEGIN OPENSSH PRIVATE KEY----- (ed25519)

The OpenSSH folks were not very forward thinking, and it is making the lexer/parser more complicated than it should be.

There are some suggestions for the problem like at Pass multiple strings to the string::find function on Stack Overflow. It provides a match for a string, but it may not be the lowest index for a match.

I think my non-STL alternative is to examine each char byte-by-byte. That takes O(n). If the char is one of `s`, `e`, or `-`, then look for the longer token, like `ssh-rsa`. The full token compare takes O(m) and it may happen s times, so the operation is O(s\*m).

I kind of feel like O(n+s*m) can be improved upon similar to the way Boyer-Moore improves a single string search. My question is, is there an algorithm that runs in better time than O(n+s*m)?

# Answer
> 1 votes
You can turn that search into a DFA,and you can then pass the input through the DFA until an accepting state is reached (or the end of the string is encountered).

Each pattern is turned into an NFA by adding a start state which self-loops on any input and transitions to the next state on a match of the first character. Each subsequent state transitions only on the corresponding match. The last state is accepting.

These NFAs are then combined into a single NFA by merging the start states, after which the consolidated NFA is turned into a DFA using subset construction.

Assuming the DFA is stored in a datastructure which allows O(1) transitions, the scan can be performed in $O(k)$ where $k$ is the index of the last character in the earliest match.

Note that this is not a general algorithm. It actually produces the index of the match which ends first, not the one which starts first. In the case where no pattern matches a substring of any other pattern, however, these are the same match so there is no problem.

Also, in the worst case the subset construction takes exponential time, although this is ameliorated by the fact that no pattern use repetition operators. In your particular problem, though, the DFA only needs to be constructed once when the program is compiled and the runtime is going to be $O(n)$.

# Answer
> 0 votes
The shortest string you accept is seven letters, so you *must* examine at least one out of every 7 letters. That’s the minimum. So you need to examine at least n/7 letters in the worst case. Which is O(n).

And if the length of the longest string S is k, we can show that in the worst case you need to examine all letters when n is a multiple of k: Create a string consisting of copies of S, except when you have examined k-1 of the letters of one copy, and examine the last remaining letter, that letter is modified. So it takes n steps in the worst case.

---
Tags: c++, string-matching
---


# Question
Title: What is the minimal degree $d$ required for a B tree with $44*10^6 $ keys so that it's height is less than or equal to $5$
> What is the minimal degree $d$ required so a B - tree with $44\*10^6$ keys will have a height $h$, such that $h\leq 5$

My attempt was to build the tallest tree possible with minimum degree $d$ and $n = 44,000,000$ keys and then solve for $d$. That would mean any other tree with a minimal degree $d'$ such that $d'\geq d$ and $n$ keys will be shorter than the one I built:

at depth 0 , we have the root and that's $1$ node

at depth 1, we got exactly $2$ nodes

at depth 2, since we're going for the tallest tree each node will have a minimal number of keys so $d-1$ keys each, that means $d$ children each so a total of $2d$ nodes.

at depth 3, following the same reasoning , $2d^2$ nodes.
...

at depth $h$, there are $2d^{h-1}$ nodes

total number of keys is :

$n = 1+ (d-1)\sum\_{k=0}^{h-1} {2d^k} = 1 + (d-1) \frac{2(d^h-1)}{d-1} = 2d^h-1 = 44\*10^6 $

so:

$2d^5-1=44,000,000 $

$d= 29.4 $

$d\geq 30$

is that even correct ?

# Answer
Having degree $d$ tree has $1$, $d$, $d^2$, $d^3$, $d^4$ nodes per level. So, we must have that:

$$1+d+d^2+d^3+d^4 \ge 44\ 000\ 000$$

Let's consider just $d^4 = 44\ 000\ 000$. This has solution $d\approx 81.4$ but real $d$ must be bigger because we threw away some summands. So, we need to try $82$:

$$1+82+82^2+82^3+82^4=45\ 770\ 351$$

And let as check $81$ just to be sure:

$1+81+81^2+81^3+81^4 = 43\ 584\ 805 \< 44\ 000\ 000$

So, the answer is 82.

---

Ups, you are asking about B-tree, so having branching factor $d$ we have at most $2d-1$ keys inside a node. Then we have different equation:

$$(2d-1) + d(2d-1) + d^2(2d-1) + d^3(2d-1) + d^4(2d-1) \ge 44\ 000\ 000$$ $$2d + 2d^2 + 2d^3 + 2d^4 + 2d^5 - (1 + d + d^2 + d^3 + d^4) \ge 44\ 000\ 000$$ $$d + d^2 + d^3 +d^4 + 2d^5 - 1 \ge 44\ 000\ 000$$ Let's solve $2d^5 = 44\ 000\ 000$, $d \approx 29.4$, so we need to try both $29$ and $30$: $$29+29^2+29^3+29^4+2\*29^5 = 41\ 754\ 838$$ So, we have to choose $30$, but lets check: $$30+30^2+30^3+30^4+2\*30^5 = 49\ 437\ 930$$
> 1 votes

---
Tags: search-trees, b-tree
---


# Question
Title: Exact meaning of $2^{\mathcal{O}(f(n))}$
In Sipser's Introduction to the Theory of Computation he uses the notation $2^{\mathcal{O}(f(n))}$ to denote some asymptotic running time.

For example he says that the running time of a single-tape deterministic turing machine simulating a multi-tape non-deterministic turing machine is

$\mathcal{O}(t(n)b^{t(n)})=2^{\mathcal{O}(t(n))}$ where $b$ is the maximal number of options in the transtition function.

I was wondering if someone can clarify the exact definition of this for me:

My assumption is that if $g(n)=2^{\mathcal{O}(f(n))}$ then there exists $N \in \mathbb{Z}$ and $c \in \mathbb{R}$ s.t.

$g(n) \leq 2^{cf(n)}=(2^{f(n)})^c$ for all $n\>N$.

Thank you

# Answer
> 3 votes
The class $O(f(n))$ consists of all functions $\phi$ such that for some $N,c \> 0$, we have $\phi(n) \leq Cf(n)$ for all $n \geq N$.

The class $2^{O(f(n))}$ is simply $$ 2^{O(f(n))} = \\{ 2^{\phi(n)} : \phi(n) = O(f(n)) \\}, $$ which is essentially what you wrote.

---

A different way of looking at this is that $O(f(n))$ stands for some function $\phi(n)$ such that $\phi(n) \leq Cf(n)$ for all large enough $n$.

Given this point of view, $2^{O(f(n))}$ simply stands for some function of the form $2^{\phi(n)}$, where $\phi(n) = O(f(n))$.

---
Tags: complexity-theory, asymptotics, notation, big-o-notation
---


# Question
Title: Are type abstraction values and universal types not for non functions, but only for functions?
In *Types and Programming Languages* by Pierce, *Chapter 23 Universal Types* has a summary of System F in the following figure, in particular, "type abstraction values" and their types "universal types".

In all the examples I have seen so far in the chapter, in particular *Section 23.4 Examples*, (not sure if I miss any example):

* all the type abstraction values are parametrically polymorphic functions, by allowing the types of their arguments to have any type, and
* all the universal types, i.e. the types of type abstraction values, are types of parametrically polymorphic functions.

Are type abstraction values and their universal types not for non functions, but only for functions?

More specifically, in any type abstraction value, say $\lambda X.t$, must $t$ have a function type, not a non-function type?

In *Section 23.4 Examples*, values of base types and of recursive types are type abstraction values, because their definitions in the section are functions by Church encodings.

Thanks.

# Answer
> 2 votes
**Short Answer:** In `λX₁. λX₂. ... λXₙ. t` it doesn't matter if `t` is not a function, but if so, it may not be an interesting example for introduction.

**Long Answer:**

First of all, technically speaking, the type system defined in Figure 23-1 does NOT have any base types such as `Bool` or `Nat`. A type of `t` in `λX. t` is either a type variable `X`, a function type `T → T`, or a universal type `∀X. T`.

Section 23.4, however, takes `Nat` as an example. So let's consider an extended type system by adding some base types and its values, terms, typing rules, etc. like Section 11.1 does.

Then we can consider, for example, a term `λX. 42`. This is a well-typed term. Proof:

\\\[ \cfrac{}{ \cfrac{\mathrm{X} ⊢ \mathrm{42} : \mathrm{Nat}}{ ∅ ⊢ \mathrm{λ X. 42} : \mathrm{∀ X. Nat} }} \\\]

This term, however, is not very interesting; polymorphism doesn't play any important role here.

Also, we can consider a type `∀X. X`. But there is no term of type `∀X. X` (i.e. there is no inhabitant of `∀X. X`). This can be proved through the Curry-Howard correspondence. But this example may not be suitable for introduction of System F.

Section 23.7 writes a bit more interesting example. If we extend the type system by adding errors, we can consider a term `λX. error`. This term doesn't throw an error during an evaluation because of the type-abstraction. This observation gives an idea of a new type erasure method, described in Section 23.7.

---
Tags: programming-languages, type-theory, types-and-programming-languages, polymorphisms
---


# Question
Title: BosonSampling: $\# P \subseteq FBPP^{{NP}^{\mathcal{O}}}$ implies $P^{\#P}\subseteq BPP^{{NP}^{\mathcal{O}}}$
I am a complexity beginner, actually a quantum physicist.

In their famous BosonSampling paper, Aaronson and Arkhipov show amongst other things a polynomial time machine solving the problem of BosonSampling exactly, would result in the collapse of the Polynomial Hierarchy.

If you are not familiar with BosonSampling or any quantum physics at all, do not bother, it won't be necessary for this question: I am interested in one particular aspect of the argument, that I do not understand because of my lack of background: It seems to have to do with the relation of function/search problems and corresponding(?) decision problems.

Specifically, on page 33, in the **the proof of Theorem 1**, they show that a #$P$-hard problem is also contained $FBPP^{{NP}^{\mathcal{O}}}$ where $\mathcal{O}$ is an oracle to some problem called BosonSampling. From there, they immediately seem to get that $$P^{\\#P}\subseteq BPP^{{NP}^{\mathcal{O}}}$$

My question is: How? I understand that there is a difference between counting/function problem complexity classes like $\\#P$ or $FBPP$ and classes for decision problems. But how to relate the results? In particular, why is it $P^{\\#P}$ on the left?

# Answer
I'm not an expert, and I have one blank space in my answer, hope someone might fill it in.

> $FBPP$ is the class of search problems $R = (B\_x)\_{x\in\\{0,1\\}^\*}$ for which there exists a probabilistic polynomial-time algorithm $A$ that, given $\langle x, 0^ {1/\varepsilon}\rangle$ as input, produces an output $y$ such that $Pr \[y \in B\_x\] ≥ 1 − \varepsilon$, where the probability is over $A$’s internal randomness.

Suppose that $L$ is a $\\# P-$hard problem, and $L \in FBPP^{NP^{\mathcal{O}}}$. Then, $$P^{\\# P} \subseteq P^{L} \subseteq P^{FBPP^{NP^{\mathcal{O}}}} \subseteq BPP^{NP^{\mathcal{O}}}$$

The second inclusion is clear. The first inclusion: suppose $L\_1 \in P^{\\# P}$. It means that there exists some polynomial algorithm $\mathcal{A}$ which makes queries to some functions $f\_1, f\_2, \ldots$ from $\\#P$. By the definition of $\\#P-$hard problems, $f\_i \in FP^{L}$, where $FP$ is the class of polynomially computed functions $f:\\{0,1\\}^\*\rightarrow \\{0,1\\}^\*$. It means that every $\mathcal{A}$'s query to $f\_1, f\_2, \ldots$ can be replaced by a polynomial program with (at most polynomial) number of queries to $L$, or simply speaking $\mathcal{A}$ is equivalent to some polynomial program $\mathcal{B}$ with queries to $L$. We've shown $$P^{\\#P} \subseteq P^{FP^{L}} = P^L$$ We see that $P^{FP}$ can be replaced by $P$.

The third inclusion: again, the same trick: here $P^{FBPP}$ turns to $BPP$. Suppose $L\_2 \in P^{FBPP^{NP^{\mathcal{O}}}}$ and $\mathcal{A}$ is the corresponding algorithm for $L\_2$. $\mathcal{A}$ makes at most $p(n)$ queries to the probabilistic polynomial programs $A\_1, A\_2, \ldots$ which solve some search problems. $\mathcal{A}$ uses randomness, but always gives the right answer. One can supposedly make $A\_1, A\_2\ldots $ a part of $\mathcal{A}$; the resulting probabilistic polynomial algorithm $B$ with queries to $NP^{\mathcal{O}}$ never errs and belongs to $BPP^{NP^{\mathcal{O}}}$.

The only doubt that I have here is that there might be a polynomial number of queries to different functions $FBPP$, and $\mathcal{B}$ is supposed to know all the algorithms for them. It is widely known that if $\mathcal{C}$ is a complexity class with a complete problem $\mathcal{L}$, then $A^{\mathcal{L}} = A^{C}$ for class $P$. However, $BPP$ doesn't have complete problems, and I'm not sure about $FBPP$.
> 2 votes

---
Tags: complexity-theory, decision-problem, quantum-computing
---


title: What does "prime" mean in this context?

text:
# Question
Title: What does "prime" mean in this context?
In a lecture video the instructor introduced the quadratic probing method for hash tables. The formula he gave was the following:

$h(k,i) = (h'(k) + c\_1 + c\_2i^2)$ $\\% M$

where $h'$ was h "prime". So, what I am supposed to conclude for $h'(k)$ to be? Is it any different from the value I get by computing $h(k)$

# Answer
> 2 votes
$h'(k)$ is the value returned by the original unmodified hash function when applied to the element $k$. If the $h(k)$ slot is not free then $h(k,i)$ for $i=0,1,2,\dots$ gives a sequence of modified hash values which can be tried in turn until a free slot is found.

---
Tags: terminology, hash, hash-tables
---


title: Keeping track of best algorithms

text:
# Question
Title: Keeping track of best algorithms
Is there a site that keeps track of the "current best algorithms", e.g., for certain combinatorial optimization problems?

In the latter there exists a range of classic problems such as MIN st-CUT or MAX FLOW, for which the best algorithms seem to be somewhat hidden in the literature.

# Answer
"Best algorithm" is a fuzzy term. The algorithm which is best for some particular case can very well be absolutely worst for another, similar problem. Problems differ in details (and not-so-details), in size, in available resources, sometimes an exact solution is essential, other times a rough approximation is good enough. And there are literally thousands of algorithms, with new ones added each day.
> 1 votes

---
Tags: algorithms, reference-request
---


# Question
Title: Louvain algorithm: self-loop weight is double?
In the 2nd phase of the Louvain algorithm, self-loops are given by the sum of all the intra-community weights. I'm wondering from their own figure, why all of the self-loops seem to have `2w` weights, rather than `w`. Note in the blue community for instance: 2 intra-community edges, self loop has weight 4.

# Answer
Every edge has the same weight, which it contributes to each endpoint. When both endpoints are in the same cluster, the edge counts twice towards that cluster. Then they are in different clusters, the edge counts once towards each of the two clusters. So each edge has the same overall contribution.
> 1 votes

# Answer
It seems they calculate the total intra-community weight by considering the intra-community weight leaving every single node in the community, and then summing these. This sums all intra-community edges double.
> 0 votes

---
Tags: graphs
---


# Question
Title: Like transitive reduction, but removing vertices rather than edges?
Suppose I have a directed graph $G = (V, E)$ *(or, which is the same, a relation on the set $V$ as defined by the adjacency matrix)* that may contain three vertices $x, y, z$, such that $xy, xz, yz \in E$ — that is to say, the relation restricted to $x, y, z$ is transitive, there is a triangle. Let us call this situation a *"local transitivity"*. My goal is to obtain all the subgraphs of $G$ induced by cutting middle vertices from local transitivities until none remain, which I dub *"resolution"*.

There may be multiple solutions. For instance, consider a graph given by this relation:

```
  a b c d
a □ ■ ■ □
b □ □ ■ ■
c □ □ □ ■
d □ □ □ □

```

*(It looks like a square with one diagonal.)*

There are two ways it can be resolved:

```
  a b d        a c d
a □ ■ □      a □ ■ □
b □ □ ■      c □ □ ■
d □ □ □      d □ □ □

```

One way I can compute the resolutions of a graph is by giving a *"non-deterministic"* function $f :G \rightarrow \\{G\\}$ that removes any single local transitivity. Repeatedly applying $f$ to any graph, I will eventually converge to a set of induced subgraphs completely devoid of local transitivities.

One way to define $f$ is by considering all the triples of distinct vertices and checking them for local transitivity. From each matching triple, the middle vertex is extracted, and any of these vertices is cut. But there is about $|V|^3$ such triples.

Is there a better way? Is there prior art that I may study?

**P.S.** Answering to questions from the comments:

1. > Is "local transitivity" the same as a triangle? Or could it (for instance) involve more than 3 vertices?

In the case I have in mind, it is specifically triangles that I need to remove. But I can see how a generalization may be offered where, given two paths $p\_1, p\_2: a \dots b$ such that $|p\_1| \leq n$ and $|p\_2| \leq m$ *(counting edges)*, we can remove the longer. My specific problem is then the special case with $n = 1, m = 2$.
2. > In your example, I think there are more than two ways it can be resolved. For example, you could remove vertex a (from the abc triangle) ...

I was thinking that it is only allowed to remove a midpoint from a triangle, so that *"initial"* and *"terminal"* vertices cannot be removed, and therefore the length of the shortest path is preserved.
3. > What's your question? Is your question "can I enumerate all triangles faster than $O(|V|^3)$ time?" Is your question "how efficiently can I find all possible triangle-free subgraphs?"

This and that too. Primarily, I need the triangle-free induced subgraphs. Enumerating triangles is only a means to this end, but it may be a useful technique for other algorithms, elsewhere, so would be good to know.

# Answer
There's a $O(n^\omega)$-time algorithm that outputs a count, for each vertex, of the number of triangles that include that vertex. Here $O(n^\omega)$ is the running time for matrix multiplication. See, e.g., Number of triangles in an undirected graph, Is it a valid graph canonical form?, https://cstheory.stackexchange.com/q/9972/5038. This may or may not be faster in practice.

To enumerate a list of all such triangles can take $\Theta(n^3)$ time in the worst case, for instance, in the case where you have a complete graph on $n$ vertices, as then you have $\Theta(n^3)$ triangles in the graph, so just outputting them takes $\Theta(n^3)$ time.
> 1 votes

---
Tags: algorithms, graphs, functional-programming, nondeterminism, transitivity
---


# Question
Title: Differences and relationships between randomized and nondeterministic algorithms?
What differences and relationships are between randomized algorithms and nondeterministic algorithms?

From Wikipedia

> A **randomized algorithm** is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits. Formally, the algorithm's performance will be a random variable determined by the random bits; thus either the running time, or the output (or both) are random variables.
>
> A **nondeterministic algorithm** is an algorithm that can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave differently from run to run. A **concurrent algorithm** can perform differently on different runs due to a race condition. A **probabilistic algorithm**'s behaviors depends on a random number generator. An algorithm that solves a problem in nondeterministic polynomial time can run in polynomial time or exponential time depending on the choices it makes during execution.

Are randomized algorithms and probabilistic algorithms the same concept?

If yes, are randomized algorithms just a kind of nondeterministic algorithms?

# Answer
> 26 votes
Non-deterministic algorithms are very different from probabilistic algorithms.

Probabilistic algorithms are ones using coin tosses, and working "most of the time". As an example, randomized variants of quicksort work in time $\Theta(n\log n)$ in expectation (and with high probability), but if you're unlucky, could take as much as $\Theta(n^2)$. Probabilistic algorithms are practical, and are used for example by your computer when generating RSA keys (to test that the two factors of your secret key are prime). Probabilistic algorithm which don't use any coin tosses are sometimes called "deterministic".

Non-deterministic algorithms are ones which "need a hint" but are always correct: they cannot be fooled by being given the wrong hint. As an example, here is a non-deterministic algorithm that factors an integer $n$: guess a factorization of $n$, and verify that all the factors are prime (there is a "fast-in-theory" deterministic algorithm for doing that). This algorithm is very fast, and rejects false hints. Most people think that randomized algorithms can't factor integers that quickly. Clearly this model of computation isn't realistic.

Why do we care about non-deterministic algorithms? There is a class of problems, known as NP, which consists of *decision problems* which have efficient non-deterministic algorithms. Most people think that the hardest problems in that class, the so-called NP-complete problems, do not have efficient deterministic (or even randomized) algorithms; this is known as the P vs NP question. Since many natural problems are NP-complete, it is interesting to know whether in fact they are not solvable efficiently, in the worst case (oftentimes, the instances which arise in practice are in fact solvable in reasonable time).

# Answer
> 15 votes
An algorithm specifies a method to get from a given input to a desired output that has a certain relation with the input. We say that this algorithm is deterministic if at any point, it is specified exactly and unambiguously what the next step in the algorithm is that must be performed as part of that method, potentially dependent on the input or the partial data computed so far, but always uniquely identified.

Nondeterminism means that some part of the algorithm is left under or even unspecified. For example, "int i = an even number between 0 and n" is underspecified. This means there is no unique behavior that is specified at this point.

For this distinction to be useful, you need the (usual) concept of 'correctness' for (deterministic) algorithms, which informally is that "the algorithm always computes what I want it to compute". It then becomes interesting to think about what correctness would mean for nondeterministic algorithms, which must take into account the choices possible in underspecified instructions.

There are two ways of defining correctness for nondeterminism. The first one is rather simple and less interesting, for which correctness means "the algorithm always computes what I want it to compute, for all sequences of choices I am allowed to make". This sometimes occurs if an author of a bit of pseudocode is too lazy to pick a number and says "pick any even number between 0 and n", when "pick 0" would have made the algorithm deterministic. Essentially, by replacing all nondeterminism by the result of some choice you can make the algorithm deterministic.

This is also the 'nondeterminism' referred to in your second paragraph. This is also the nondeterminism in parallel algorithms: in these algorithms you are not quite sure what execution precisely looks like, but you know that it will always work out, no matter what happens exactly (otherwise your parallel algorithm would be incorrect).

The interesting definition of correctness for nondeterministic algorithm is "the algorithm always computes what I want it to compute, for **some** sequence of choices I am allowed to make". This means that there may be choices that are wrong, in the sense that they make the algorithm produce the wrong answer or even go in an infinite loop. In the example "pick any even number between 0 and n", perhaps 4 and 16 are right choices, but all other numbers are wrong, and these numbers may vary depending on the input, the partial results and the choices made so far.

When used in computer science, nondeterminism is usually limited to nondeterministically choosing either a 0 or a 1. However, if you pick many such bits nondeterministically, you can generate long nondeterministic numbers or other objects, as well as make nondeterministic choices, so this hardly (if ever) limits its applicability - if applicability is limited, nondeterminism was too powerful in the first place.

Nondeterminism is a tool that is exactly as powerful as a certificate-based deterministic algorithm, that is, an algorithm that checks a property given an instance and a certificate for that property. You can simply nondeterministically guess the certificate for one direction, and you can give a certificate that contains all the 'right' answers for the nondeterministic guesses of 0 and 1 of your program for the other direction.

If we throw running time into the mix, then things become even more interesting. The running time of a nondeterministic algorithm is usually taken to be the minimum over all (right) choices. However, other choices may lead to a dramatically worse running time (which can be asymptotically worse or even arbitrarily worse than the minimum), or even an infinite loop. This is why we take the minimum: we do not care about these weird cases.

Now we get to randomized algorithms. Randomized algorithms are like nondeterministic algorithms, but instead of 'allowing' the choice between 0 and 1 at certain points, this choice is determined by a random coin toss at the time that the choice has to be made (which may differ from run to run, or when the same choice has to be made again later on during the execution of the algorithm). This means that the result is 0 or 1 with equal probability. Correctness now becomes either "the algorithm nearly always computes what I want it to compute" or "the algorithm always computes what I want it to compute" (just the deterministic version). In the second case the time the algorithm needs to compute its answer is usually 'nearly always fast', contrasting with a deterministic 'always fast'.

Contrasting the three: deterministic algorithms exactly specify the answer to the choice, nondeterminism leaves it completely open, but tells you a 'right' answer exists, and randomization leaves the answer up to chance. Note that you can just guess the right coin tosses, which gives rise to a hierarchy between these three: nondeterminism is as powerful as randomization, which in turn is as powerful as determinism, or, with respect to polynomial time, $P \subseteq ZPP \subseteq NP$. In this setting, no proofs are known whether any is strictly more powerful than another.

# Answer
> 14 votes
In short: non-determinism means to have multiple, equally valid choices of how to continue a computation. Randomisation means to use an external source of (random) bits to guide computation.

---

In order to understand nondeterminism, I suggest you look at finite automata (FA). For a *deterministic* FA (DFA), the transition function is, well, a function. Given the current state and the next input symbol, the next state is uniquely defined.

A non-deterministic automaton (NFA), on the other hand, has a transition *relation*: given the current state and the next input symbol, there are multiple possible next states! For example, consider this automaton for the language $(ab)^\*(ac)^\*$:

\[source\]

The automaton *guesses* which $a$ marks the border between $(ab)^\*$ and $(ac)^\*$; a deterministic automaton would have to postpone its decision until after having read the symbol after each $a$.

The key point here is that acceptance is defined as "accept if *there is* an accepting run" for NFA. This existence criterion can be interpreted as "always guessing right", even though there is no actual guessing.

Note that there are no probabilities here, anywhere. If you were to translate nondeterminism into programming languages, you would have statements that can cause jumps to different other statements *given the same state*. Such a thing does not exist, except maybe in esoteric programming languages designed to skrew your mind.

---

Randomisation is quite different. If we break it down, the automaton/program does not have multiple choices for continuing execution. Once the random bit(s) are drawn, the next statement is uniquely defined:

```
if ( rand() > 5 )
  do_stuff();
else
  do_other_stuff();

```

In terms of finite automata, consider this:

\[source\]

Now every word has a probability, and the automaton defines a probability distribution over $\\{a,b,c\\}^\*$ (differences between $1$ and the sum of outgoing edges is the probability of terminating; words that can not be accepted have probability $0$).

We can view this as a deterministic automaton, given the sequence of random decisions (which models practice quite well, as we usually use no real random sources); this can be modelled as a DFA over $\Sigma \times \Pi$ where $\Pi$ is a sufficiently large alphabet used by the random source.

---

One final note: we can see that nondeterminism is a purely theoretical concept, it can not be implemented! So why do we use it?

1. It often allows for smaller representations. You might know that there are NFA for which the smallest DFA is exponentially as large¹. Using the smaller ones is just a matter of simplifying automaton design and technical proofs.
2. Translation between models is often more straight-forward if nondeterminism is allowed in the target model. Consider, for instance, converting regular expressions to DFA: the usual (and simple) way is to translate it to an NFA and determinise this one. I am not aware of a direct construction.
3. This may be an academic concern, but it is interesting that nondeterminism can increase the power of a device. This is not the case for finite automata and Turing machines, arguable the most popular machine models devices, but for example deterministic pushdown-automata, Büchi automata and top-down tree automata can accept strictly less languages than their non-deterministic siblings².

---

1. See this question on cstheory.SE for an example.
2. See here, here and here (Proposition 1.6.2), respectively.

# Answer
> 14 votes
You should be aware that there are two different definitions of nondeterminism being thrown around here.

1. As wikipedia defines it, pretty much "not determinism", that is, any algorithm that doesn't always have the same behavior on the same inputs. Randomized algorithms are a special case of "not deterministic" algorithms, because they fit the definition as I just gave it.
2. Nondeterministic models of computation (like nondeterministic turing machines) are theoretical models of computation. They may have multiple possible paths of execution and they "accept" if any of those paths accept. You should note they aren't real. There is no way to physically run an algorithm that is nondeterministic in this sense, although you can simulate it with a randomized or deterministic one.

In CS, nondeterminism usually means (2), so Wikipedia's definition you gave (which is (1)) is misleading. Most of the answers given so far explain (2), not (1).

# Answer
> 1 votes
Revisiting this due to some related research I am doing, the disagreement between myself and some of the others who answered, can be assimilated into a holistic understanding in which we were all correct. But IMO the adopted computer science terminology “bounded nondeterminism” is an incorrect oxymoron (which was my point before).

They key point is to distinguish between bounded and unbounded nondeterminism.\[1\]

Nondeterministic Turing machines (aka “NTMs”) have *bounded* nondeterminism in that each state transition has a *bounded* number of possibilities, i.e. the number of programs (aka “configurations”) is finite. The tape remains unbounded, so the proof of termination remains undecidable. But for any given input that halts, the output is deterministic and bounded in time― i.e. for any input the result is deterministic or doesn’t terminate. Also NTMs execute all possible configurations in parallel, so they execute exponentially faster than emulation of NTMs on deterministic Turing machines (aka “DTMs”).\[2\]

There really isn’t any nondeterministic relationship between inputs and outcomes in NTMs because the outcome is always the same for any input or initial state, which is evident because they they can be emulated by DTMs without any added randomness.\[2\] Undecidable is not the antithesis of deterministic, because not halting is also a deterministic result. Deterministic machines always have the same outcome for a given input, even when that outcome is to not halt. The localized nondeterminism of NTMs is in each state transition of the executing algorithm. It is undecidable a priori which path of the tree might terminate providing the output state. But undecidability is not nondeterminism. Thus the term “bounded nondeterminism” is intended to describe the localized indeterminacy within the state machine but not the relationship of inputs to results, hence the concept of “bounded”. I still think the term “bounded nondeterminism” is an oxymoron and it could have been more accurately described as a “parallelized state transition” Turing machine.

Whereas, for any given input or initial state, *unbounded* nondeterminism (aka “indeterminism”) has an unbounded number of possible states. Unbounded nondeterminism involves not just the number of possible configurations of programs, but some unbounded external state which is not part of the input or initial state, such as unbounded delays. And thus outcomes can vary on repeated executions for the same input or initial condition; thus is not a deterministic relationship between inputs and outcomes.\[3\]

Randomized and probabilistic algorithms employ some nondeterminism, i.e. random selection of possible configurations possibly bounded in number of configurations, but they don’t execute all the possible configurations as NTMs do. Thus they are not deterministic unless the randomness is deterministic (e.g. PRNG) and the initial state of the entropy for the randomness is considered to be part of the input.

\[1\] https://en.wikipedia.org/w/index.php?title=Unbounded\_nondeterminism&oldid=710628370#Nondeterministic\_automata

\[2\] https://en.wikipedia.org/w/index.php?title=Non-deterministic\_Turing\_machine&oldid=754212081#Equivalence\_with\_DTMs

\[3\] Hewitt, Meijer and Szyperski: The Actor Model (everything you wanted to know...). Jump to the 17:44 minute mark.

# Answer
> 0 votes
Apart from all the answers which explain the difference, I have an example which may help you get the thing they want to say.
Consider a coin toss, you either get a **H** or a **T**. If the coin toss is random, it is highly likely that out of 1000 coin tosses, 500 would be **H** and it is quite unlikely that 999 out of them would be **H**. But if the coin toss is non-deterministic, we can't say that getting 999 **H** would be highly unlikely.

---
Tags: algorithms, terminology, computation-models, nondeterminism, randomness
---


# Question
Title: The time complexity for finding the kth smallest number in a min-heap
Suppose that $k \< \sqrt n$, what is the time complexity to find the $k\_{th}$ smallest number in a min-heap?

I thought that we can remove the root element for k times and each time we apply heapify? So it should be $O(k \log n)$ but the answer is $O (k \log k)$. What did I do wrong?

# Answer
> 3 votes
There is an $O(k)$ algorithm \[1\].

\[1\] Frederickson, G. N. (1993). An optimal algorithm for selection in a min-heap. *Information and Computation, 104*(2), 197-214.

# Answer
> 2 votes
Here is an $O(k\log k)$ algorithm at this SO answer, slightly improved.

```
Create toVisit, a collection of nodes that contains the nodes which we will traverse next. This is initially just the root node.
Let counter c = 1.
While c < k:
    Remove the smallest node from toVisit
    Insert that node's children in the given min-heap to toVisit
Return the smallest node from to toVisit

```

The `toVisit` can be implemented in a min-heap or balanced BST/B+ tree or skip list in which the insertion and removal of the smallest node takes $O(\log m)$ time, where $m$ the number of nodes. Assuming the degree of original min-heap is $O(1)$, there were at most $O(k)$ elements in `toVisit` since there have been at most $k$ insertions.

---
Tags: algorithm-analysis, data-structures, runtime-analysis, heaps
---


# Question
Title: Which algorithm to detect errors in 32bit data with 8bit parity
I want to transmit a 32bit message in eight groups of 5bit each. This leaves me with 8bits to use for error checking.

Overall, a group is likely transmitted without error, but when there is an error transmitting a group, there are probably multiple bits wrong.

If I use one parity bit per group, I have a 50% chance to detect a wrong group. But I don't need to know which group of a message is wrong, I want to check the entire message.

I want 100% chance of detecting if one group of the message is incorrect, regardless of how many bits are flipped in that group. If possible, I also want to be able to check wheather two neighboring groups have been switched.

Which algorithm should I use for error checking / How should I code the data?

# Answer
> 2 votes
Think of your message as seven 5-bit numbers $x\_2,\ldots,x\_8 \in \\{0,\ldots,30\\}$. This gives you $7\log\_2 31 \approx 34.68$ message bits. Calculate $x\_1 = -\sum\_{i=2}^8 ix\_i \bmod{31}$, so that $$ \sum\_{i=1}^8 ix\_i \equiv 0 \pmod{31}. $$

It is easy to check that every single symbol error is detected, since $31$ is prime.

Now suppose that $x\_i$ and $x\_j$ are switched, but the equation above still holds. Then $ix\_i + jx\_j \equiv ix\_j + jx\_i$, and so $(i-j)(x\_i - x\_j) \equiv 0$, implying that either $i = j$ or $x\_i = x\_j$.

---
Tags: algorithms, coding-theory
---


# Question
Title: How does a computer compute negative(-) and positive(+) Infinity?
If we divide (1.0/0.0) we will get +Infinity and if we divide (-1.0/0.0) we will get -Infinity.

How does a computer calculate this value internally?

# Answer
> 2 votes
The simple answer is that a computer that follows a floating point standard such as IEEE 754 does not really *compute* +/- infinity at all. Instead it treats it as an exception - a special case. Whenever the processor detects an attempt to divide a non-zero floating point number by zero, it sets the result to a special value that is then interpreted as +/-infinity, where the sign depends on the sign of the original number.

In IEEE 754 I believe the special values of +/- infinity are represented internally as a floating point number with a sign bit, an exponent set to all $1$s, and a significand set to all $0$s. This is a value that cannot result from normal (non-exceptional) floating point operations.

# Answer
> 1 votes
Technically speaking, not all computers evaluate `1.0 / 0.0` to `+Inf`. But most of recent computers follows a specification named IEEE 754, which especially defines the division on floating-point numbers `1.0 / 0.0` is `+Inf`.

> Division by zero: an operation on finite operands gives an exact infinite result, e.g., 1/0 or log(0). By default, returns ±infinity.

Also note that an evaluation of a division on integers `1 / 0` often throws "Division By Zero" error in many programming languages.

# Answer
> 0 votes
Division is a rather complex operation.

If the computer is implementing IEEE 754 arithmetic then most likely it categorises its inputs as NaN (not a number), Infinity, Normalised numbers, denormalise numbers, and zeroes. That is done by looking at the exponent and mantissa. The rules are:

1. Largest possible exponent with zero mantissa is Infinity.
2. Largest possible exponent with nonzero mantissa is NaN.
3. Smallest possible exponent with zero mantissa is zero.
4. Smallest possible exponent with nonzero mantissa is denormalised.
5. Everything else is normalised.

Denormalised numbers are made normalised. Then if the operands are not both normalised, the hardware has defined values for the 15 other combinations. If both operands are normalised, the division is performed, and the result can be overflow, normalised, denormalised, or so small it is rounded to zero.

# Answer
> 0 votes
It just checks if the denominator is zero and, if so, does whatever it needs to do, such as returning a value representing infinity, an error, or whatever else is required in the context.

---
Tags: arithmetic, floating-point, number-formats
---


# Question
Title: Can't find a mistake in reduction from RE language to a non-RE language
In the book Introduction to Automata Theory there is a question 9.3.4 that asks if a question "whether a language L(M) is infinite" is RE or non-RE? I've seen the answer, that its non-RE, however I tried a reduction from a Universal Turing machine language(which is RE) and it also seemed to work. Since a language can't be both RE and non- RE, there is a mistake and I can't figure out where. Please help!

My reduction from Lu (univeral TM) to Lm (infinite language TM): The input to Lu is (M,w). Build a new TM M' with an input x as follows, let it simulate a string w on M and if it accepts, then M' goes to states where it accepts a language 0^n, n\>1, and accept its input x. If M rejects w or doesn't halt, then M' never accepts its input x. Then take the description of this machine M' and feed it into Lm. Therefore, if M accepts w, M' accepts an infinite language and Lm accepts it. If M doesnt accept w, then M' only accepts ∅ language, which is finite, hence Lm rejects.

# Answer
Your reduction actually shows that $L\_m$ is not co-RE. Indeed, if $L\_m$ were co-RE, then your reduction shows that $L\_u$ is also co-RE. However, $L\_u$ is known to be RE but not recursive, hence cannot be co-RE.

Similarly, you can show that $L\_m$ is not RE, by reduction from the *complement* of the halting problem: given an instance $(M,w)$ of $L\_u$, create a new machine $M'$ which on input $n$ simulates $M$ on $w$ for $n$ steps. If $M$ halts, $M'$ gets into an infinite loop, and otherwise it halts. You can check that $M$ halts on $w$ iff $L(M')$ is finite.

The language $L\_m$, usually known as INF, is actually one of the canonical examples of $\Pi\_2$-complete languages, making it harder than the halting problem.

---

Your title suggests that you believe that RE languages cannot be reduced to non-RE languages. But in fact, every recursive language can be reduced to every non-RE language. I'll let you work this out.
> 1 votes

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


title: Difference between UCB1 and UCT

text:
# Question
Title: Difference between UCB1 and UCT
In Bandit Based Monte-Carlo Planning by Levente Kocsis and Csaba Szepesvári (2006) they propose the UCT algorithm which is derived from the UCB1 algorithm.

UCB1 algorithm:
$$X\_j + \sqrt{\frac{2\ln n}{n\_j}}$$

where $X\_j$ is the average reward for machine $j$, $n\_j$ is number of times $j$ has been played and $n$ is the entire number of games played.

In comparison, UCT is $$\frac{W\_i}{n\_i} + c \sqrt{\frac{\ln N\_i}{n\_i}}$$ where $\frac{W\_i}{n\_i}$ is win:lose ratio (the same as $X\_j$),
$c$ is temperature parameter, which is often set to $\sqrt{2}$ (so they just put it in front...)
and $\frac{N\_i}{n\_i}$ is number of total games played for parent Node / number of games played for the corresponding node, which is the same as $\frac{n}{n\_j}$.

So what's new here?

# Answer
As the authors state in the introduction to their paper, UCT is an application of UCB1 for a specific problem:

> The main idea in this paper it to apply a particular bandit algorithm, UCB1 (UCB stands for Upper Confidence Bounds), for rollout-based Monte-Carlo planning. The new algorithm, called UCT (UCB applied to trees) described in Section 2 is called UCT.

It's not the algorithm but the particular application which is new.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Strongly connected components in a directed graph
Let $G$ be an arbitrary directed graph. Does $G$ always have the same strongly connected components on $G$ as on $G^\*$? Here, $G^\*$ is the inverted graph of $G$ (i.e., $(u,v)\in E \rightarrow (v,u) \in E^\*$).

I'm thinking yes because otherwise the algorithm of Kosaraju would not work at all? But do not have another explanation for this.

# Answer
Two vertices $x,y$ lie in the same strongly connected component if there is a directed path from $x$ to $y$ and a directed path from $y$ to $x$.

There is a directed path from $x$ to $y$ in $G$ iff there is one from $y$ to $x$ in $G^\*$. This easily implies that $G$ and $G^\*$ have the same strongly connected components.
> 2 votes

---
Tags: graphs
---


# Question
Title: Is properly quantified 3SAT complete for PSPACE and all PH levels?
I know 3SAT is NP-complete and QSAT is PSPACE-complete. However, is it true that

$$\exists X\_1 \forall X\_2 \cdots Q\_k X\_k \colon \varphi(X\_1, \ldots, X\_k)$$

is complete for $\Sigma\_k$, the existential side of level $k$ of the polynomial hierarchy if each clause in $\varphi$ has at most 3 literals (or some other constant size bound)? Similarly for

$$\forall X\_1 \exists X\_2 \cdots Q\_k X\_k \colon \varphi(X\_1, \ldots, X\_k)$$

in relation to $\Pi\_k$, and the quantified version with unbounded alternation in relation to PSPACE, once again with each clause of $\varphi$ having at most 3 literals (or some other constant number)?

# Answer
> 3 votes
QSAT with only 2 literals per clause was shown to be in P back in 1979.

Since the $\Sigma\_k$ and $\Pi\_k$ versions of QSAT can be reduced to equisatisfiable problems with 3 literals per clause using only a slight modification the method used to transform a SAT instance to 3SAT (i.e. putting all the new variables in the innermost existential group), those limited problems continue to be complete for their levels of the polynomial hierarchy.

---
Tags: complexity-theory, satisfiability
---


# Question
Title: Why are ADT packages opened immediately after they are built, while existential objects opened as late as possible?
Section 24.2 in *Types and Programming Languages* by Pierce defines ADTs in existential types:

> **A conventional abstract data type (or ADT)** consists of (1) a type name A, (2) a concrete representation type T, (3) implementations of some operations for creating, querying, and manipulating values of type T, and (4) an abstraction boundary enclosing the representation and operations. Inside this boundary, elements of the type are viewed concretely (with type T). Outside, they are viewed abstractly, with type A. Values of type A may be passed around, stored in data structures, etc., but not directly examined or changed—the only operations allowed on A are those provided by the ADT. ... We ﬁrst create an existential package containing the internals of the ADT:
>
> ```
> counterADT =
> {*Nat,
> {new = 1,
> get = λi:Nat. i,
> inc = λi:Nat. succ(i)}}
> as {∃Counter,
> {new: Counter,
> get: Counter→Nat,
> inc: Counter→Counter}};
>
> > counterADT : {∃Counter,
> {new:Counter,get:Counter→Nat,inc:Counter→Counter}}
>
> ```
>
> We can open it for example
>
> ```
> let {Counter,counter} = counterADT in
> counter.get (counter.inc counter.new);
> > 2 : Nat
>
> ```

and then defines existential objects in existential types:

> **A counter object** comprises two basic components: a number (its internal state), and a pair of methods, get and inc, that can be used to manipulate the state. We also need to ensure that the only way that the state can be queried or updated is by using one of these two methods. This can be accomplished by wrapping the state and methods in an existential package, abstracting the type of the state. For example, a counter object holding the value 5 might be written
>
> ```
> c = {*Nat,
> {state = 5,
> methods = {get = λx:Nat. x,
> inc = λx:Nat. succ(x)}}}
> as Counter;
>
> ```
>
> where:
>
> ```
> Counter = {∃X, {state:X, methods: {get:X→Nat, inc:X→X}}};
>
> ```
>
> We opens it for example:
>
> ```
> let {X,body} = c in body.methods.get(body.state);
> > 5 : Nat
>
> ```

and compare ADTs and existential objects:

> **when programming with ADTs**, packages are opened immediately after they are built; on the other hand, **when packages are used to model objects** they are kept closed as long as possible—until the moment when they must be opened so that one of the methods can be applied to the internal state.

* What does "*when programming with ADTs, packages are opened immediately after they are built; on the other hand, when packages are used to model objects they are kept closed as long as possible*" mean?

They are both opened in the binding parts of the `let` terms, which can be anywhere (not immediately) after they are built. So their timings seem to be the same to me.
* What are the differences in the definitions of ADT and of existential objects in terms of existential types, which lead to the timing difference of their opening?

Thanks.

# Answer
You can see an instance of the claimed property in the two definitions of `add3`.

---

In the ADT style, `add3` is defined as:

```
let { Counter, counter } = counterADT in
let add3 = λ (c : Counter). counter.inc (counter.inc (counter.inc c)) in
counter.get (add3 counter.new);

```

As you see, in order to call about `inc`, one must already have opened the existential package. You cannot write the `inc3` function in the "ambient scope", as `Counter` is not an ambient type, but a type encapsulated in the `counterADT` package.

You could repackage everything after the first call to `inc`, and re-open the package before the next call, but that would be somewhat pointless.

---

In the object style, `add3` is defined as:

```
add3 = λ (c : Counter). sendinc (sendinc (sendinc c)))

```

Here, the client code does not open the existential package themselves. Instead, each call to `sendinc` will open the package when it needs to run `inc`, and will repackage the output. The client could just do the same, but that is not the intent of this style (they would be breaking the abstraction).

---

So, the confusion might be that you understood the sentence as "the packages are open at a given time", as opposed to "a programmer would be expected to open the package at a given time".

---

The difference in timing comes from the way we want to use these two mechanisms.

The ADT mechanism is one where we have a single representation, that we wish to hide, while giving some actions to perform on that representation. Because there is a single representation, it is perfectly acceptable to unpackage it once and for all.

The object mechanism is one where we want to potentially allow multiple representations that all share some actions to perform on them. Because we want to allow multiple representations, each package should be responsible for knowing how to perform the abstract action on its concrete representation. If we were to unpackage the existential type early, we would locally be restricted to a given representation.

This becomes very interesting when thinking about binary operations over the packaged type: in the ADT style, the two operands are guaranteed to share the same representation, whereas in the object style, each operand could have its own concrete representation and its own way of implementing the binary operation.

http://www.cs.utexas.edu/~wcook/Drafts/2009/essay.pdf

^ This paper, "On Understanding Data Abstraction, Revisited", by William R. Cook gives a lengthy explanation of the difference in power between these two approaches, and is, in my opinion, an excellent read.
> 3 votes

---
Tags: programming-languages, type-theory, polymorphisms
---


# Question
Title: Recurrence relation (not solvable by the master theorem)
Consider the following recursion: $\begin{cases} T(n) = 2T(\frac{n}{2}) + \frac{n}{\log n} &n \> 1 \\ O(1) &n = 1 \end{cases}$.

The master theorem doesn't work, as the exponent of $\log n$ is negative. So I tried unfolding the relation and finally got the equation: $T(n) = n\[1 + \frac{1}{\log(\frac{n}{2})} + \frac{1}{\log(\frac{n}{4})} + ... + \frac{1}{\log(2)}\]$.

I do not know how to simplify (inequalities to use???) from here. A trivial method would be to assume that all reciprocal of the log terms are $\< \frac{1}{\log(2)}$, and since there are $\log n$ terms, the summation of all the reciprocal-log terms is $\< \frac{\log n }{\log(2)} = \log\_2 n$, which gives $T(n) = O(n \log n)$. However this is a very poor approximation, as by the master theorem we can check that the time complexity for the recursive relation $T(n) = 2T(\frac{n}{2}) + n$ is $O(n \log n)$. Can someone find a tighter correct upper bound?

# Answer
> 1 votes
Wikipedia has a slight extension of the master theorem which covers your case: case 2b here. For the recurrence $T(n)=aT(n/b)+f(n)$ where $f(n)=\Theta(n^{\log\_b a}/\log n)$, it gives $T(n)=n^{\log\_b a}\log\log n$.

---
Tags: time-complexity
---


# Question
Title: How does the computer know whether an address contains an instruction to be executed, or data to be used in an instruction?
The question is already stated in the title.

# Answer
> 4 votes
In current architectures, the CPU does not need to distinguish. Whatever is pointed by the program counter register will be interpreted as an instruction and executed. Everything else can be manipulated as "data". For example, you can have a program modify its own code (in fact, some computer viruses do this, with the aim of avoiding detection).

# Answer
> 3 votes
A full answer to this question depends on the underlying computer architecture, as well as on layers of protection that the operating system may add on top of the basic architecture.

In the Harvard architecture instructions and read/write data are held in physically separate memory stores accessed by separate data pathways (buses). It is physically impossible to load a value from the data memory into the instruction register and it is physically impossible for a program to modify its own instructions. Values in the instruction memory may be copied into data registers and then treated as data, but the processor will know this from context e.g. when it sees an opcode "load the next word into Register A", the processor will assume the value in the next address in the instruction memory is a data value to be copied into Register A.

In the more flexible von Neumann architecture (which is adopted by most modern computers) instructions and data are held in the same memory and the processor does not see any difference between them. The processor assumes that whatever memory address its program counter points to at the start of an instruction cycle holds an instruction, and it will load that value into its instruction register and will try to execute it as if it were an instruction.

The danger with the von Neumann architecture is that the processor may treat data that was not intended to be executed as instructions, with unpredictable results. Or it may treat its own instructions as data and change them - this is known as self-modifying code, and is usually avoided because it is difficult to understand, test and maintain.

The solution to this danger is to re-introduce a distinction between data and instructions into the von Neumann architecture by using a no-execute bit, which can be implemented at a hardware level or in the operating system software.

# Answer
> 3 votes
It doesn't. The CPU executes instructions beginning at the program's start address. After each instruction, the CPU either jumps to the address specified by that instruction or, if it's not a jump, moves on to the next instruction in memory. The start address is known to contain executable code because the program was just loaded there. The correctness of the program's logic ensures that each subsequent memory location from which instructions are retrieved actually contains an instruction. However, an error in the program (or memory corruption) could cause the CPU to start fetching "instructions" from memory that is supposed to be interpreted as data, leading to unpredictable behaviour – usually crashing the program.

# Answer
> 2 votes
The computer doesn't know, just as it has no idea whether the information at a certain memory cell should be interpreted as a character, integer or floating point number.

When executing code, the CPU reads the code byte by byte. Each instruction is composed of an *opcode* followed by relevant information, such as constants (*immediates*) and addresses. In principle, however, you could jump in the middle of such a code, so the same byte could be use both as an opcode and as data (though in practice this never ever happens).

# Answer
> 0 votes
Adding to other answers: Modern CPU's can mark memory regions as "do not execute" or "do not modify", and the operating system will instruct them to do so. So if you start a program, the operating system should know which part of memory is instructions, and which is data. It will then mark the data as "do not execute" (because you really don't want the CPU to try to execute data as if it were code) and it will mark the instructions as "do not modify" (because you really don't want the CPU to modify the instructions it's executing).

The CPU will obey this. If it is given an instruction that tells it to run code inside a "do not execute" region, it will refuse to do so, and your program will crash (because that is considered safer than trying to execute random data as if they were code), and if it it given an instruction that tells it to modify data in a "do not modify" region, it will also refuse to do so.

Still, the CPU does NOT know whether the "do not execute" region contained code or not, only that it isn't allowed to execute it.

(Many years ago self modifying code was considered really cool and clever. Today, with gazillions of hackers trying to break into a computer system, that ability is considered Dangerous with a capital D).

---
Tags: computer-architecture
---


# Question
Title: 'simple' algorithm that can predict disk usage or 'time to be full'
Let say I have time series of disk usage of last 30 days.. Given this information and with the assumption that the disk usage 'pattern' isn't changing dramatically over time, what would be a naive/**simple** algorithm to predict when is disk going to be full?

# Answer
> 1 votes
I'd try fitting a linear model (i.e., assume new data arrives at a constant rate) or an exponential one (i.e., new data is proportional to what is already there), and see which one is better.

# Answer
> 0 votes
In addition to the linear model, take your historical data and figure out the variance of memory usage. Because you don't want to know the point of time where the average disk usage exceeds the available space, but the point of time when peak usage exceeds available space.

Say you have 4,000 GB, usage goes up and down by 500 GB every day, but tends to go up on average 100 GB a month, and the average usage today is 1,000 GB, then you will likely run out of disk space when average usage is 3,500 GB (and then you have a sudden peak needing 500 GB more).

You also need to make a difference between "storage used" and "storage required". The OS can cache data that might be required again in the future, but these caches might be optional and could be automatically removed if space is tight. So you might have 1,000 GB of such data that *uses* space but is not really absolutely required. When your disk space is full, this space can and will be released.

You should also take into account how speed is affected when your disk is full. For spinning hard drives, reading or writing the last tracks on the drive takes more as twice as much time than the first tracks. For SSD drives, it can be worse. An 80% full SSD drive may drop write performance considerably (there are SSD drives where this doesn't happen - they tend to be more expensive, and that may be because the drive that was sold as "100 GB with no performance drop when full" is in reality "150 GB but we won't let you fill it more than 2/3rds").

---
Tags: algorithms
---


title: Decidability of decision problems

text:
# Question
Title: Decidability of decision problems
Can somebody give intuition how to answer those questions? From one side I can say that most of them are undecidable because we can reduce the halting problem to them (or halting problem can appear because we don't know about given TM anything so it can behave unpredictably, can simply loop on any input), but on another hand in question 2. we don't know much about machine, however I can hardcore all words into my TM as far as given language is finite. Also, for question 1. I'm able to create TM which checks if the output of M is even-length (I would classify this problem as semi-decidable).

**What type of the following decision problems are: decidable, partly decidable, or even undecidable:**

1. Does the language of the given machine M contain only even-length words?
2. Does the given M machine accept a finite language size of which is less than 2019?
3. We say that language A is prefixless if no word belonging to A is a prefix of any other word from A. For example, language A = {0, 10, 110, 1110, ...} is prefixless, while language B = {0, 1, 00, 11, 000, 111, ...} does not have this property (for example, because 0 is the prefix 00). Consider the following language (decision problem): L = {⟨M⟩ | L (M) is prefixless}.
4. Is the given recursive function a surjection?
5. Is the given recursive function an injection?
6. Does the machine M stop at bb?
7. Does the machine M accept the empty language?

# Answer
> 0 votes
A good rule of thumb is to use Church's thesis: can *you personally* solve the problem? While this is of course informal, in practice it works very well after you develop a bit of experience with Turing machines. (That said, ultimately the theorem you'll learn and use here is **Rice's theorem**.)

By way of example, let's first consider the following two sets:

* Those Turing machines which halt (on input $0$) in at most $42$ steps.
* Those Turing machines which halt (on input $0$) and output $42$.

It should be fairly easy to see that we can informally compute the former: given a Turing machine, just run it on input $0$ for $42$ steps and see what happens. The latter, though, is harder: if I'm presented with a candidate Turing machine, *if I know it halts* I can run it until it halts and check whether the output is $42$, but in the absence of that information I seem to be stuck since I don't see a way around the infinite search involved in "wait until it halts, if it ever does."

---

So now let's look at a couple candidates on your list.

* (1): in principle, we'd need to check *each possible input* to be confident that a Turing machine has the desired property: a single counterexample tells is it doesn't, but we don't know where such a counterexample might be and so as we go along checking all possible strings we'll never be fully confident that there isn't a counterexample (= a string of odd length which is accepted) which we just haven't found yet.
* (2): Here, there are only finitely many things we need to check, namely all those strings of length $\<2019$. However, think about what's involved in checking a single candidate: the only a priori way to tell that a Turing machine *doesn't* accept a string is to run it forever, and "at the end of forever" you'll know that it in fact doesn't accept that string, but that's clearly bonkers. So there's still an infinite search involved, and this appears undecidable.

---

Now how do we make further distinctions between the undecidable sets - in particular, between semidecidable (more commonly, *computably enumerable*) and not-even-semidecidable?

Again, Church's thesis is the key: is it the case that, in order to be certain that something *is* in our set, we need to see some finite amount of information? If so, then it's computably enumerable. Otherwise, it's not - and in particular, if it's *falsified by a counterexample* (instead of *verified by a witness*) its *complement* is computably enumerable. So our Church's thesis analysis of (1) and (2) says that **each is not even computably enumerable**.

---
Tags: turing-machines, undecidability, decision-problem, semi-decidability, rice-theorem
---


title: Minimum index Array Product

text:
# Question
Title: Minimum index Array Product
Given an array A(1 indexed based) of positive integers.For each element A\[i\] find the minimum index (say idx) such that the product of all the elements from index 1 to idx is divisible by A\[i\].where(1\<=idx\<=i).

constraints are: the number of elements of the array 1\<=n\<=10^5 and

1\<=A\[i\]\<=10^5.

For example let A\[\]={2,4,6,8}

The output should be {1,2,3,2}

I could only think of O(n^2) solution but that gives a T.L.E.

I also looked up to the code of successfully accepted solution but could not understand the logic.I only understood that it is first calculating the smallest prime factor using seive and then calculating the prime factors of each A\[i\] using its smallest prime factor.However I am not able to understand the later part of the solution.

Here is the code of one of the accepted solution.

int main() {

```
ll n,arr[500001],minP[500001];
cin>>n;
for(int i=0;i<n;i++){
    cin>>arr[i];
}
for(int i=2;i<=500000;i++){
    minP[i]=i;
}
for(ll i=2;i*i<=500000;i++){
    if(minP[i]==i){
        for(ll j=i*i;j<=500000;j+=i){
            minP[j]=min(minP[j],i);
        }
    }
}
vector<ll> v[500001];
for(int i=0;i<n;i++){
    ll temp = arr[i],mx=0;
    while(temp>1){
        v[minP[temp]].push_back(i);
        temp/=minP[temp];
    }
    temp = arr[i];
    while(temp>1){
        ll x=minP[temp],cnt=0;
        while(temp%x==0){
            temp/=x;
            cnt++;
        }
        mx=max(mx,v[x][cnt-1]);
    }
    cout<<mx+1<<" ";
}

```

}

Also,Suggest me some relevant material to understand the underlying concept used above.

Here I have tried to implement the solution using binary search can anybody point the error as I am still getting the wrong answer upon submission.

```
 void Bsearch(int low,int high,int key,long long product[])
    {

    int ans;
    int mid;
    long long midVal;
    while (low <= high)
    {
    mid = low + (high - low + 1) / 2;
    midVal = product[mid];

    if (midVal% key!=0)
    {
        low = mid + 1;
    }
    else if (midVal%key==0)
    {
        ans=mid;
        high=mid-1;
    }
}
     cout<<ans+1<<" ";
}
  int main()
  {
int n;
cin>>n;
int arr[n];
long long product[n];
int i;
for(i=0;i<n;i++)
cin>>arr[i];
product[0]=arr[0];
for(i=1;i<n;i++)
product[i]=product[i-1]*arr[i];//prefix product array
for(i=0;i<n;i++)
{
    int temp=arr[i];
    Bsearch(0,n-1,temp,product);//Using binary search to find the minimum
                                  index.
}
}

```

# Answer
> 1 votes
Here's a simple $O(n \log n)$ solution if multiplication and the modulus operator is always assumed to be $O(1)$ (which is a big assumption -- see the note at the end).

Create a new array, $B$, in which the first element is $A\[1\]$ and every future element at index $i \in 2..n$ is $A\[i\] * B\[i-1\]$. This gives you an array of all "partial products".

This array is nondecreasing, and $B\[j\]$'s factors are a superset or $B\[i\]$'s factors whenever $i \< j$. Therefore, for any $A\[i\]$ (or even for every integer $k$), you can use binary search to find the smallest index $i$ for which $k$ divides $A\[1\] * A\[2\] ... * A\[i\]$. This takes $O(\log n)$ time per lookup, or $O(n \ log n)$ in total for all of $A$.

--

Regarding the initial assumption. As it turns out, assuming arithmetic operations can be done in constant time gives you a bit more power than what most people consider reasonable. For example, one can factor arbitrary integers in polynomial time under this assumption, by constructing pathologically large multiplications/divisions that let them "carpool" many different operations into one. Do you know which cost model we are operating under?

# Answer
> 0 votes
Pseudocode:

For 2 ≤ n ≤ 500,000 calculate minP \[i\] = smallest prime factor of n.

For each prime p, record the indices of every array element arr \[i\] that has p as a prime factor, recording an index multiple times if arr \[i\] has p^2, p^3 as a factor. (The code does this in a different order, iterating through the array elements first instead of the primes).

For each array element arr \[i\], and each prime factor p of arr \[i\]: Find which prime power p^k divides arr \[i\]. Consult the table created earlier to find at which point earlier array elements had the same number of prime factors p. And the largest of these values is the result we want.

Of course this doesn't run in O(n) where n is the number of array elements, but O ("total number of prime factors of all array elements"). There's also the minor problem that none of the arr\[i\] can have a prime factor \> 500,000.

Material for the underlying concepts... A book about basic arithmetic? I don't think anything that the ancient greeks didn't know is required here.

# Answer
> 0 votes
Task 1: Create a data structure which given an integer N, can give you all primes from $p ≤ N^{1/2}$ in constant time each. This is quite easy: Given N, we calculate $M = N^{1/2}$, rounded down to the nearest integer. We keep an array of consecutive primes, starting with p = 2. If the highest of these primes is less than or equal to M, then we add primes until the array contains a prime greater than M. We then can just iterate through that array, until a prime greater than M is found.

Task 2: Create a data structure which given an integer N, produces the smallest prime factor of N: To do this, we create a hash table which maps integers N to their smallest prime factors. Given N, we look it up in the hash table, and return the result if N is present. Otherwise, we divide N by all prime numbers $p ≤ N^{1/2}$ until a divisor is found; if a divisor is found then we enter (N, divisor) into the hash table and return the divisor, otherwise N is prime and we enter (N, N) into the hash table.

Task 3: Have an algorithm that given an inteer N, determines all prime factors of N: We do this by looking up the smallest prime factor of N and dividing N by that factor, until N = 1.

Task 4: For each prime factor p contained in the array, have an array storing the first index i such that the product of a\[0\] to a\[i\] is divisible by $p^k$, for k = 1, 2, 3 etc. We do this by taking N = a\[0\], a\[1\] etc., determining all prime factors p, and adding i to the array for the prime p. (Note that if we have an upper limit for the size of array elements, we can determine the maximum possible power of any prime factor - for example, any 64 bit integer cannot have a factor $p^k$ with k \> 63).

Task 5: For each array element, calculate all prime factors and their power, say $p^k$. Given the array of Task 4, find the smallest i such that the product a\[0\] to a\[i\] is divisible by $p^k$. The largest of these indexes is the result.

I think the worst case would be an array of n large different primes. If the primes are ≤ M, then determining this takes $M^{1/2} / log M$ steps, for total execution time of $O (n * M^{1/2} / log M)$.

---
Tags: algorithms
---


# Question
Title: Give a Context Free Language, is the complement of this language always recursive(REC)?
I have seen some people make an argument that given the fact that Context Free Languages are proper subset of REC which is closed under complementation thus complement of a CFL must be in REC. I cannot wrap my head around this argument.

What I know about a CFL(say L) is that the complement of this CFL(say L') need not necessarily be a CFL. This creates fair bit of skepticism about nature of such a complement in my head and makes me feel that there is a possibility this complement L' could fly off anywhere in Chomsky Hierarchy as long as it is not a CFL. Why would it be restricted to REC?

In my head, I find myself coming up with arguments like following: "Every CFL is in RE and complement of an RE need not necessarily be RE and thus need not necessarily be REC! Thus there could be CFLs whose complements are not in REC. " or "Complement of a CFL may fall under RE and there are RE languages which are NOT REC. Thus there is a possibility that a certain complement may not be in REC"

Thread like : What is complement of Context-free languages? did not answer my question.

# Answer
We have $\text{CFL} \subset \text{R} \subset \text{RE}$. As you have mentioned, $\text{RE}$ is not closed under complementation, but $\text{R}$ is. Hence, the complement of a CFL is also in $\text{R}$ (though not necessarily another CFL).
> 5 votes

# Answer
The problem with the Chomsky Hierarchy is that it says nothing at all about the class of recursive languages. Honestly, that's the most important class of all, since it corresponds to the things that computers can do, at least in principle.

The key point here is that every context-free language is recursive: you can simulate a PDA (even a nondeterministic one) on a computer (formally, a Turing machine). If you can do something on a computer, you can also do that thing and then negate the answer, so recursive languages are closed under complementation. So the complement of a CFL is still some kind of recursive language.

You're right that the complement of an RE language isn't necessarily RE. But a CFL isn't just *any* RE language: it's a very, very special kind of RE language and its complement is still RE and, furthermore, recursive.
> 2 votes

# Answer
Putting similar arguments as above answers in a slightly different way :

All context free languages can be decidable by a Halting Turing Machine. (Those would be a piece of cake for the Machine). Now even if we complement such a language, Halting TM can still decide whether it is accepted or not.

The Complement of CFL still lies under the power of Halting TM, hence cannot go beyond the RE boundary in Chomsky Hierarchy.
> 0 votes

---
Tags: turing-machines, context-free
---


# Question
Title: Selecting a polygon within an array of complex polygons
I have an array of polygons which are arrays of points. There are no gaps and none of them overlap like a Voronoi diagram.

Unlike a Voronoi diagram I cannot simply find the nearest centroid to select a polygon, this returns the correct polygon most of the time but sometimes the point lies within a neighboring polygon.

The developer tools in my chrome browser seem to be able to do it with the selection tool but I have no idea how it is doing it.

# Answer
> 2 votes
I would use a winding number algorithm. There are a few, but the fastest goes like this:Imagine a line from your point along the positive x-axis. Now, for every edge of your polygon, determine if it crosses this line. if it crosses the line from below to above, then increment the winding number (which is initially zero), if it crosses going from above to below then decrement. If the winding number is zero, then the point lies outside of the polygon, otherwise it lies inside.

You probably don't want to test every polygon every time the point moves, so I would pre-compute a bounding box or sphere for every polygon. I would then only test winding numbers against those polygons whose bounding shapes collide with the point in question.

Hope this helped. Good luck!

---
Tags: polygons
---


# Question
Title: How to schedule events optimally given when the events are available?
Suppose I had a dictionary that contains events and the corresponding periods they are occurring. For example:

$$ \begin{align} \textrm{Event 1} &\rightarrow \textrm{\[1, 2, 3\]} \\ \textrm{Event 2} &\rightarrow \textrm{\[2, 4\]} \\ \textrm{Event 3} &\rightarrow \textrm{\[4\]} \\ \textrm{Event 4} &\rightarrow \textrm{\[2, 3\]} \end{align} $$

How would I go about generating a schedule so that the events are scheduled optimally? For the example above, one possible optimal schedule would be:

$$ \begin{align} \textrm{Period 1} &\rightarrow \textrm{Event 1} \\ \textrm{Period 2} &\rightarrow \textrm{Event 2} \\ \textrm{Period 3} &\rightarrow \textrm{Event 4} \\ \textrm{Period 4} &\rightarrow \textrm{Event 3} \\ \end{align} $$

Is there any way to do this in better than checking every permutation? This seems like the reverse of the graph-coloring problem for scheduling, so is there any way to construct a graph to encapsulate this relationship and maybe find a shortest path? Can someone point me in the right direction on how to approach this?

# Answer
I assume that by "optimally" you mean using the least number of periods. Thirst thing is that you can renumerate the dictionary such that there are no gaps in available periods, so:

$$ \text{Event 1} \rightarrow\ \[1, 2, 10\]\\ \text{Event 2} \rightarrow\ \[3, 5, 11, 12\]\\ $$

becomes

$$ \text{Event 1} \rightarrow\ \[1, 2, 5\]\\ \text{Event 2} \rightarrow\ \[3, 4, 6, 7\]\\ $$

So now the largest number on the right side is not greater then the sum of sizes of lists on the right side. Assume that, there are $n$ events and sum of sizes of lists on the right side is $m$. Now to check if there is a solution, which uses only first $i$ periods we can reduce the lists to the numbers smaller or equal to $i$, so for $i=4$ this example will change to: $$ \text{Event 1} \rightarrow\ \[1, 2\]\\ \text{Event 2} \rightarrow\ \[3, 4\]\\ $$ Now to check if there is a solution for given $i$ we can create bipartite graph with events on one side, periods on the other side and edges between event $e$ and period $p$ if $e$ is available during $p$. If there is matching of size equal to $n$ in this graph then we can schedule events using only first $i$ periods. If we find smallest $i$ with such property then we have a solution to our original problem. It's easy to see that if there is such matching for $i$ then there is also for $i+1$, so we can use binary search to find smallest $i$. This solution will work in time $O(m\sqrt{n+m}\log{m})$ where $O(m\sqrt{n+m})$ comes from finding matching and $O(\log{m})$ comes from binary search.
> 1 votes

---
Tags: algorithms, scheduling
---


# Question
Title: Longest path in a directed acyclic graph with constraints
Given a directed weighted acyclic graph *G=(V,D,W)* and a subset of edges *D'* of *D*. The problem is to find the longest path in *G* that passes by exactly one edge of *D'*.

What is the complexity of this problem?

# Answer
> 3 votes
You can solve this problem in time $O(|V|+|E|)$ by using dynamic programming. Thirst you order nodes in topological order. Let $v\_i$ be the $i$-th node in topological order. Let $E\_i$ be the set of edges ending in $v\_i$.

If $|E\_i\setminus D'| = 0$ then: $$ d\[v\_i\]\[0\] = 0 $$

otherwise: $$ d\[v\_i\]\[0\] = 1 + \max\_{(v\_j, v\_i) \in E\_i}(d\[v\_j\]\[0\]\_{(v\_j, v\_i) \not\in D'})\\ $$

If $|E\_i| = 0$ then: $$d\[v\_i\]\[1\] = -\infty$$ otherwise: $$d\[v\_i\]\[1\] = 1 + \max\_{(v\_j, v\_i) \in E\_i}(d\[v\_j\]\[0\]\_{(v\_j, v\_i) \in D'}, d\[v\_j\]\[1\]\_{(v\_j, v\_i) \not\in D'}) $$

It's easy to see that $d\[v\_i\]\[0\]$ is equal to length of longest path ending in $v\_i$ without edges from $D'$ and $d\[v\_i\]\[1\]$ is equal to length of longest path ending in $v\_i$ with exactly one edge from from $D'$. After that you need to find largest of $d\[v\_i\]\[1\]$. You can also store the id of the node for which we found the maximal value during dynamic programming to recreate the path.

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


# Question
Title: Why is heap insert O(logN) instead O(n) when you use an array?
I am studying about the arrays vs heap for make a priority queue

For check the heap implementation I am reviewing this code: Heap

, but I have the following question.

Heap is based on array, and for creating an array you need O(n), for inserting into a heap you need O(logN), so if you have a unordered list of task and you want to create a heap, you need O(NLogN).

If you use an array, you need O(n), to create the array, and O(NlogN) to sort the array, so you need O(NLogN).

So if you need implement some similar to this:

```
function priorityQueue(listOfTask l)

```

There isn't a diference betwen use an Array or an Heap right? So, why I should use a heap instead an array for solve this function?

Thanks

# Answer
> 4 votes
Given your link, you seem to be interested in data structures supporting the following operations:

* Create(*m*): create a new instance with room for *m* elements.
* Size(): return the number of elements currently stored in the instance.
* Insert(*k*): insert an element with priority *k*.
* ExtractMax(): return the maximal priority currently stored, and remove it.

Since Size() is easy to implement in constant time as part of the other operations, I will not discuss it below.

Here are three sample implementations:

Unsorted array:

* Create() simply allocates memory.
* Insert() simply inserts the element at position *i*+1, where *i* is the current number of elements.
* ExtractMax() goes over the entire array, finding the maximum; and then "compacts" the array by moving all elements to the right of the maximum one entry to the left.

Sorted array: (your implementation)

* Create() simply allocates memory.
* Insert() first scans the array to find the proper location for the element, then moves all elements to the right of the intended location one entry to the right, and finally stores the element.
* ExtractMax() returns and removes the *i*th element, where *i* is the number of elements currently in the instance.

Binary heap:

* Create() simply allocates memory.
* Insert() and ExtractMax() are described on Wikipedia.

Binary heaps are implemented using "partially sorted" arrays. That is, the order of elements in the array is not arbitrary, but it is also not completely determined. Rather, we are only guaranteed that A\[i\] ≥ A\[2i\],A\[2i+1\]. This freedom allows us to trade-off the running time of the two operations Insert() and ExtractMax().

In all of these implementations, Create() is roughly the same, so to compare the various implementations it suffices to consider the two operations Insert() and ExtractMax():

$$ \begin{array}{c|c|c} \text{Implementation} & \text{Insert()} & \text{ExtractMax()} \\\hline \text{Unsorted array} & O(1) & O(n) \\ \text{Sorted array} & O(n) & O(1) \\ \text{Binary heap} & O(\log n) & O(\log n) \end{array} $$

Here $n$ is the number of elements currently in the array.

If you perform many Insert() and ExtractMax() operations, a binary heap is likely to be more efficient.

Another operation which you mentioned is

* Initialize(*A*): add to an empty instance the elements in *A*

You can add support to this operation to all different implementations mentioned above:

* Unsorted array: simply copy *A* to the array. Running time: $O(|A|)$.
* Sorted array: copy *A* and sort the resulting array. Running time: $O(|A|\log|A|)$.
* Binary heap: run Insert() for each element of *A*. Running time: $O(|A|\log|A|)$.

Considering this operation doesn't strengthen the case of your implementation.

# Answer
> 1 votes
Keeping a heap is more efficient than keeping a sorted array, when you need to keep adding items to the priority queue. In case you don't need to add to it, you don't need a queue in the first place, just an array sorted by priority.

Insertion to heap-based priority queue is *O(logN)*, while insertion to sorted array is *O(N)* (binary search for position is *O(logN)*, but inserting there is *O(N)* ).

As you can see here, almost all data structures are about trade-offs. Converting an array to heap (and keeping it heap) you gain something (*O(logN)* priority queue action) but also lose something (ability to iterate contents in order, binary search). In contrast, if you used an unsorted array, you'd gain *O(1)* insertion (because you can just append), but almost everything else would be *O(N)*, which is excellent if you have handful of items, but becomes bad if you have dozens, impossible if you have thousands.

# Answer
> 1 votes
A priority queue does something entirely different than sorting an array.

The important operations for a priority queue are: 1. Add an item to the queue. 2. Tell us the smallest item in the queue and remove it from the queue. Both these operations run in O(log n).

Now use a sorted array. Operation 2 is fast if we sorted in descending order. But operation 1 isn’t: Adding a random value to a sorted array and keeping the array sorted requires moving n/2 array elements on average.

You could sort an array in O(n log n) by adding all items to a priority queue, then removing the smallest item n times. Fast sorting algorithms process the array as a whole, they don’t try to keep part of the array sorted (straight insertion or binary insertion do; they ar not fast). Quicksort moves items very roughly into the right place at each step. Note that a priority queue only performs a rough ordering of the items as well. That’s what makes both Quicksort and a priority queue fast: They don’t ask for the data to be sorted at all times.

---
Tags: data-structures, arrays, heaps, big-o-notation
---


# Question
Title: Maximizing total value given bound on total cost
I have a list of pairs with values and costs:

```
    | value | cost |
    11, 1000
    7, 700
    7, 700
    6, 700
    2, 400
    2, 500
    1, 600

```

The list is ordered by value/cost decreasingly. The task is, given a budget X find the maximum value you can get while keeping the total cost within the budget. In the sample example, if X=1400, the maximum value would be 14.

What algorithm would be the most efficient to find this value?

# Answer
Your problem is KNAPSACK, one of the classic NP-complete problems. Wikipedia contains a wealth of information about the problem, include exact and approximation algorithms.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Expressing partial decidability using existential quantification
**def.** A predicate M(x,y) is *partially decidable* if the function f given by " f(x,y) = 1(if M(x,y) holds), f(x,y) = undefined(otherwise) " is computable.

**Thm.** If M(x,y) is partially decidable, then so is the predicate ∃yM(x,y).

proof. Take a decidable predicate R(x,y,z) such that M(x,y) iff ∃zR(x,y,z). Then...

---

I can not imagine the R(x,y,z)... Please explain the way of thinking.

( Page115, Computability by Nigel Cutland)

# Answer
The predicate $R(x,y,z)$ states that "$M$ accepts the input $x,y$ within $z$ steps". It is computable since we can simulate a given machine on a given input for a bounded number of steps.
> 1 votes

---
Tags: computability
---


title: Are these 2 equivalent?

text:
# Question
Title: Are these 2 equivalent?
Is **∀x∀y∀z\[φ(x,y)∧p(y,z)-\>p(x,z)\]** equivalent to **∀x∀y∀z\[φ(x,y)∧p(x,z)-\>p(y,z)\]** ?

The only thing I can think of is that this question can be answered if we show that `p->q` is equals (↔) το `q->p`, but that's not true because `p->q ↔ ¬p->¬q`, hence `p->q` is not equals to `q->p`. However, I do not know if my logic is correct and if it can be accepted as an answer.

I also think that the (first) **∀x∀y∀z\[φ(x,y)∧** part is irrelevant and that i have to focus only to the last part.

# Answer
It does hold that $$ \forall x \forall y \forall z \\, \[p(y,z) \to p(x,z)\] \quad \longleftrightarrow \quad \forall x \forall y \forall z \\, \[p(x,z) \to p(y,z)\], $$ since $\forall x \forall y$ is the same thing as $\forall y \forall x$. So your logic is incorrect.

Similarly, if $\varphi$ is promised to be symmetric then the equivalence holds, for similar reasons.

A simple example where the equivalence doesn't hold is $\varphi(x,y) = x$, $p(x,y) = x$.

In this case the first statement is $$ \forall x \forall y \forall z \\, \[x \land y \to x\], $$ whereas the second statement is $$ \forall x \forall y \forall z \\, \[x \land x \to y\]. $$ (This assumes that the statements are interpreted as $(\varphi \land p) \to p$ rather than $\varphi \land (p \to p)$.)
> 3 votes

---
Tags: logic, discrete-mathematics, propositional-logic
---


# Question
Title: Algorithm to count the number of subsets of size k with sum of all its elements minimum possible
An array is given eg:-1 2 2 2 and we need to count the number of subsets for it of size k which has the sum of elements minimum possible

here the subsets of size k=3 are:- 122 122 122 222

we see that there are 3 subsets having the minimum sum

I did this in bruteforce approach..first I stored the subsets of size k in a vector and then found the sum for each of the subsets and stored them in another vector and then counted the frequency of the minimum element

how to optimize it?

# Answer
> 3 votes
Suppose that you arrange the array in non-decreasing order. It's not hard to check that the minimum sum is obtained by taking the first $k$ elements.

Suppose that the distinct values found in the array are $a\_1 \< a\_2 \< \cdots$, where $a\_i$ appears $n\_i$ times. There is an index $d$ such that $n\_1 + \cdots + n\_{d-1} \< k$ but $n\_1 + \cdots + n\_d \geq k$. Thus every $k$-subset of minimum sum contains all elements of values $a\_1,\ldots,a\_{d-1}$, and any $k-(n\_1+\cdots+n\_{d-1})$ elements of value $a\_d$. You take it from here.

# Answer
> 0 votes
There are 3 minimum subsets, which happens to be the same number as the *largest number in the sum*. Can you play around with this insight to see if you can find out how to solve it?

For example, if the minimum sum contains both (e.g.) the numbers 5 and 7, then realize that *all* 5ers have to be included in every minimum sum!

---
Tags: combinatorics
---


# Question
Title: What is a range of an attribute in data mining?
In my data mining course, we are working with a data set. I have to identity the ranges of each attribute. I am given the set of data for all 150 points and i am given the visualization (charts) of all attributes. However I do not know how to use that set of data or the charts to find the ranges of each attribute. I do not know what is meant by range either.

I'm working on the data set for Iris plants and I have three classes of the flower.

# Answer
> 0 votes
The range of the attribute is the interval where the values of the attribute varies. For Real numbers, is the closed interval \[min,max\].

For example, for an attribute $A$ with values $\\{0.1, 0.5 , 1 , 10 , 100\\}$ the range is the interval $\[0.1,100\]$

The concept is also valid for Integers, however there are no widely know notation to describe that. Ways of describing it would be:

$i = 1,...,10$

or

$(i \in \mathbb{Z}) \wedge (i \in \[0,10\])$

---
Tags: data-mining, data-sets
---


# Question
Title: What are some research papers or techniques that deals with fitting clothes on a human?
Given an image of a dress (from different angles), what could be ways to fit it on a human image (again multiple angles corresponding to dress)? Any link to research papers or tutorial regarding this?

# Answer
I would expect most of the works use Generative Adversarial Networks (GANs) for this because they are powerful generative models capable of learning the complex underlying probability distribution.

In this amazing work the authors used a Conditional GAN, in which they can generate an image conditioned on semantic segmentation map. In your case, you might want to condition on two images, one of a dress and the other of a human. https://github.com/NVIDIA/pix2pixHD

You might also want to look at the ICCV 2019 workshop on fashion.
> 1 votes

---
Tags: machine-learning, reference-request, image-processing, computer-vision
---