In Coq, what does it mean to have an inductive type where the right-hand side of ":" is Prop? I'm new to Coq, and my (rather limited) understanding is that inductive types are like algebraic datatypes in Haskell, so there is a constructor data T = A a with some arguments, and the result A a is a T: specifically a T, so I understand stuff like this:

Inductive List := Nil : List | Cons : nat -> List -> List.

where you apply a constructor and get a List, which defines what Lists (as opposed to something else) are.

So how exactly does it work that I can define an inductive type like this:

Inductive Person := Name : nat -> Person.
Inductive Knight : Person -> Prop := Knight_ : ∀(A:Person), Knight A.
Inductive Knave : Person -> Prop := Knave_ : ∀A, Knave A.

where the inductive type has Prop (or Person -> Prop?) on the right-hand side of it? This is supposed to represent "A is a knight" and "A is a knave" in knights-and-knaves puzzles. I think this is a way to encode the idea, but this is a little confusing, and I couldn't find an explanation of this. Some places in fact introduce inductive types as being similar to Haskell's data, but that's clearly not all of it.

Inductive types are similar to Haskell's data, but they are more general.

An inductive definition in Set describes a way to build a piece of data from smaller pieces. For example, the following definition defines a type called prod which allows taking two pieces of data and bundling them together.

Inductive prod (A B : Set) : Set :=  pair : A -> B -> prod A B.

(This definition exists in the standard library — with Type rather than Set, but I won't get into that distinction in my answer.) In English, given two data types A and B, and given a value a of type A and a value b of type B, I can build the value pair a b which has the type prod A B. (In the standard library, there's syntactic sugar for this: (a, b) : A * B.) And this is the only way to build a value of the type prod A B: given a value of this type, I can extract the two values that make it up (the primitive syntax for that is pattern matching, both in Haskell and in Coq).

You could take the same definition, but with A and B in Prop, and construct a type in Prop.

Inductive pprod (A B : Prop) : Prop :=  ppair : A -> B -> pprod A B.

What does this mean? Let's go through the English explanation above, applying the Curry-Howard correspondence: types become propositions, and values become proofs. So, given two propositions A and B, and given a proof a of the proposition A and a proof b of the proposition B, I can build a proof ppair a b which has the type pprod A B. And this is the only way to build a proof of pprod A B.

To build a proof of pprod A B, I need a proof of A and a proof of B. In other words, pprod A B is true if A and B are both true. There's a name for that: it's the conjunction of the two propositions — pprod A B is “A and B”.

Well, in the standard library, there's syntactic sugar for this: pprod is called and — the definition is

Inductive and (A B : Prop) : Prop :=  conj : A -> B -> and A B.

and there's syntactic sugar for and A B which is A /\ B.

This is pretty typical of how Coq works. In Coq, to say that something is true is to hold a proof of it. Coq implements a constructive logic, and makes that logic apparent. Every time you prove something, Coq builds the proof object and verifies that it's well-formed. It's rare to write down constructions in Prop, you'd usually let a tactic do it for you, but the objects always exist under the hood. (End a proof with Defined. instead of Qed. and run Print mytheorem to see the proof object for mytheorem. It can get big, but it's sometimes instructive to look at that for small proofs.)

I think it's instructive to look at how basic logical operators such as and, or, not and exists are defined (forall is a primitive concept). They're in the Logic library. It might not all make sense at first read, so revisit it again after you've practiced a bit.

To say that “P is true” in Coq, you build a proof of X. To show that “(A and B) is true”, you build a proof of (A and B), and you do this by building a proof of A and a proof of B. Likewise, to show that “(A or B) is true”, you build a proof of (A or B) by either building a proof of A or a proof of B (your choice, and if the proof depends on some variable, then you can pick a different side to prove depending on the value of that variable). This illustrates the relationship between constructivity and intuitionistic logic: the only way to prove A \/ B (syntactic sugar for or A B) is to either prove A or prove B, and this goes even when B is not A. If you can't manage to prove A and you can't manage to prove not A either, then you can't prove A \/ not A. The law of excluded middle does not hold. (It can be added as an axiom, but at a cost — you lose some of the advantage of constructivity.)

I don't think your definitions of Knight and Knave are particularly useful. You can prove Knight p and Knave p for any person p. The point of defining things in Prop is that they're not always true. Parametrized types in Set are often non-empty for every value of the parameters, but parametrized types in Prop are usually empty for some parameters — the parameters that make the proposition false.


Type inference with overloading I am working on a type system supporting overloading. I have a rough idea of how type inference is usually implemented in such a scenario, but I am wondering how - after type inference is completed - the correct implementation of an overloaded operator can be chosen. Or, in other words, how the inferred type can be passed back down the syntax tree to the operator.

For a small example, consider the expression (x + y) + 1 where x :: N | S, y :: a, + :: (N -> N -> N) | (S -> S -> S), 1 :: N. :: stands for type of, and a | b stands for type a or type b.

The way, I assume, type inference would now work, is to traverse the syntax tree, and for each node return a type constraint:

(x + y) + 1 => ((N & (N[a=N] | S[a=S])), (N & N) -> N) | ((S & (N[a=N] | S[a=S])), (S & N) -> S) => N[a=N]
  1         => N
  +         => (N -> N -> N) | (S -> S -> S)
  x + y     => ((N & (N | S)), (N & a) -> N) | ((S & (N | S)), (S & a) -> S) => N[a=N] | S[a=S]
    x       => N | S
    y       => a
    +       => (N -> N -> N) | (S -> S -> S)

a & b in this example stands for unifying the types a and b, [a=T, b=U] is a set of equality constraints for type variables.

As expected the return type of the given expression is inferred as N[a=N], that is N where the type variable a is expected to be N.

Therefore, of the two provided implementations for the + operator (N -> N -> N, S -> S -> S), N -> N -> N should be used. In the given example, the resulting type is inferred, but not the type of the overloaded operator. My question is if there is a common pattern that is used to inform the + node in the syntax tree of the used implementation.

You could organize type inference as follows.

Suppose your input syntax has type Input. Define output syntax Output to be like Input but with explicit type annotations on all variables. The type inference would have type

infer : Input -> List (Output * Type)

That is, given some input e, it returns a list of possible answers. Each answer is a pair (e', t) where e' is e with variables annotated by types, and t is the inferred type of e.

You can view this as all happenning in the nondeterminism monad. Whenever you need to infer the type of a variable x, you look up its possible types S | T | ... and branch on each one of them. This way you do not have to "pass back" any information to sub-expressions. Instead, each sub-expressions already comes annotated, in all possible ways.


operate infinite times over a regular language Let $T:Σ^*\to Σ^*$ be an operation such that $T(L)$ is regular for all regular languages $L \in Σ^*$.

Is it possible to prove $T^∞(L)$ is regular?

$T^∞(L)=\bigcup_{i=1}^{\infty}{T^{i}\left(L\right)}$

Colleague Apass Jack already warned about the dangers of infinity, and he also indicated a very simple example that shows that a very simple iteration leads to a non-regular language. Case closed, but I like to add an observation: iterating simple local substitutions lead to Turing power, not just non-regularity.

The single steps of a Turing machine van be encoded, and performed with a regular operation. The instruction "on reading $a$ in state $q$, write $b$, move left and change to state $p$" is coded as rule $aq \mapsto pb$ and is extended to longer strings containing a single state as $\alpha aq \beta \mapsto \alpha pb\beta $. This operation can be extended to sets of instructions, and will map a regular language into a regular language. However,iterating them will actually generated Turing machine computations!

(I have an answer somewhere with this observation, but cannot find it.)


Is there a CPU architecture which allows early register access? In Intel's x86 architecture, imul (integer multiply) usually has latency of a few clock cycles.  Those CPUs are very smart in filling the time (e.g., pipelining or out-of-order execution), but do any commercial CPUs simply let the program access the intermediate unfinished result?

To be realistic, one clock cycle after imul, the output register probably has not changed at all.  So, in this case, my question becomes: Is there any commercial CPU which would allow you to read that register in the following clock cycle though it still gives the old contents?

If the compiler plans for these latencies, it seems that this architecture might be useful.  It basically passes the burden of pipelining from the CPU to the compiler.  I'm sure this approach has a name, but I am just a curious beginner.

You are describing pipeline forwarding for data hazards. Here is a wikipedia article about it:
https://en.wikipedia.org/wiki/Operand_forwarding

This is a common feature of in-order processors (such as MIPS32). Since they are not operating out-of-order, the data hazard detection logic detects that the result will not be available during the clock cycle immediately after the instruction executes. The pipeline scheduling logic could either stall the pipeline or forward the result from the arithmetic unit (e.g., the multiplier) directly into where the next instruction would expect the result (e.g., one of the inputs to the ALU for example).

The compiler isn't required to be aware of this feature, however, in some scenarios it can optimize for these types of architecture features.

I won't say it is impossible or even say it isn't performed, but doing this in an out-of-order processor is much harder because the instruction window is tracking dependencies of each instruction via register indices. The control logic for the instruction window is significantly more complex if it is allowed to detect all possible data hazards opportunistically.


How can I tell who is a truth teller and who is a liar? This is a problem that I was given for my data structures and algorithms class. I am not sure how to tackle this problem. Can I get some assistance?

  At Hogwarts a new shipment of $n$ goblins has arrived.  To be of any use, a goblin must be completely truthful (never lies).  Unfortunately, not all of the $n$ goblins in the shipment are truth tellers.  Only some are truth-tellers, and some are deceivers.  It is your task to design an algorithm to separate the truth-teller goblins from the deceiver goblins.  To do this, you have one tool available:  You may combine any two goblins and have them state whether the other goblin is a truth-teller or a deceiver.  A truth-teller will always say correctly what the other goblin is, but a deceiver may lie (but also may sometimes tell the truth to REALLY confuse you).  For any two goblins that you test, the following can be concluded from the goblin responses:

  $$
\begin{array}{ccc}
\text{Goblin A says} &
\text{Goblin B says} &
\text{Conclusion} \\\hline
\text{B is a truth-teller} &
\text{A is a truth-teller} &
\text{both are truth-tellers or both are deceivers} \\
\text{B is a truth-teller} &
\text{A is a deceiver} &
\text{at least one is a deceiver} \\
\text{B is a deceiver} &
\text{A is a truth-teller} &
\text{at least one is a deceiver} \\
\text{B is a deceiver} &
\text{A is a deceiver} &
\text{at least one is a deceiver}
\end{array}
$$

  Show that if more than $n/2$ goblins are deceivers, it is impossible to determine which goblins are the truth-tellers using only the pairwise testing strategy.
  Consider the problem of identifying $1$ truth-teller goblin.  Show that if we assume that more than $n/2$ of the goblins are truth-tellers, then the problem of finding a single truth-teller from $n$ goblins can be reduced to a problem of about half the size using $n/2$ goblin comparisons.
  Use a recurrence equation to show that if more than half of the goblins are truth-tellers, then the truth-tellers can all be identified within $O(n)$ goblin comparisons.

Here are some hints to get you started. Admittedly, this question isn't that easy.

Part (a): Suppose that there are exactly $n/2$ truth-tellers and $n/2$ deceivers. Show that the deceivers have a strategy in which what a goblin A says about a goblin B depends only on whether they both have the same nature. Draw the conclusions.

Part (b): Pair the goblins up. Show that for some pairwise responses, it is safe to get rid of both goblins. Explain why it is useful to have a majority of truth-tellers.

Part (c): This part should be clear enough.


Are their problems that we can not even approximate efficiently? Most hard problems can either be solved efficiently in average time, or an approximation can be efficiently found. Are there any natural problems for which this is not the case? In particular, is there a natural problem that can not be solved in polynomial time in the average case, even if we only demand an approximation?

Are there any natural problems for which this is not the case?

Consider the scheduling jobs with deadlines on a single machine problem. I cannot say anything about its average time but this problem has no $\rho$-approximation unless $P=NP$.

Suppose that there are $n$ jobs to be scheduled on a single machine, where the machine
processes at most one job at a time. Suppose also each job $J_i$ has

release time $r_i  \geq 0$
deadline (due time) $d_i$

Define the delay by $D_i = t_i - d_i$ if the job $J_i$ finishes at $t_i$. So, we are interested in the minimization of the maximum delay, i.e.,

$$\text{minimize: } \max\{D_i\}, i=1,\dots,n$$

Now assume we have $\rho$-approximation algorithm for this problem. This means that our algorithm would find a solution which is not more than $\rho OPT$ (where $OPT$ is the optimal value). If for any problem instance with the optimal value equal to $0$ our approximation algorithm would find the solution at most $\rho 0 = 0$ in (polynomial time) and this would imply $P=NP$.


Looking for a book that derives and constructs a model checking application I am teaching myself program verification and am currently learning proof assistants. I have the book Handbook of Practical Logic and Automated Reasoning which gives the proofs necessary for the understanding of such a system, but more importantly for me it also gives an implementation of the necessary algorithms as OCAML source.

I know that some of the tools listed in Wikipedia: Model Checking tools and YAHODA: Verifications Tools Database are open source, but I also prefer it when the theory, proofs, algorithms and source code are presented at the same time reinforcing each other, and in a progression building up to a final application.

Is there such a book for model checking?

EDIT

I may have found what I am looking for in Mathematical Logic for Computer Science with Prolog source. As I don't have the book, does anyone know if this book fits the requirement?

John Harrison's book is an exception in going all the way from theory to practice and making all the source code available. I think you will find it difficult to find an equivalent book for model checking, but there are a few that achieve a close approximation.

Principles of Model Checking by Baier and Katoen contains a lot of examples and pretty detailed algorithmic description.
The SPIN Model Checker by Gerard Holzmann is a very different treatment from the author of one of the earliest model checkers. He has maintained the tool for about thirty years and has a "programmatic" approach.

A better bet may be to follow the course notes and lab assignments of some courses available online. At least you will find the theory, practice and examples, even though they are not organised in a book.

Edmund Clarke's course in CMU has a reading list which includes tutorials for a few different model checkers.
Joost-Pieter Katoen's software verification course and the followup on Practical Model Checking and Advanced Model Checking cover a lot of ground.

Finally, this is not entirely what you asked for, but since you have been studying logic and now model checking, you will invariably run into references to abstract interpretation, which is the basis of static program analysis and is intimately connected to model checking (though this connection is not always explicit in the model checking literature).

Patrick Cousot's MIT Course is a tour de force covering everything from lattice theoretic foundations to the complete implementation of a static analyzer for a simple language. His course material includes all the code and exercises.


Proving a specific language is regular In my computability class we were given a practice final to go over and I'm really struggling with one of the questions on it.

Prove the following statement:
If $L_1$ is a regular language, then so is
$L_2 = \{ uv |$ $u$ is in $L_1$ or $v$ is in $L_1 \}$.

You can't use the pumping lemma for regular languages (I think), so how would you go about this? I'm inclined to believe that it's false because if $u$ is in $L_1$, what if $v$ is non-regular? Then it would be impossible to write a regular expression for it. The question is out of 5 marks though and that doesn't seem like enough of an answer for it.

You can use the pumping lemma to show that a language is not regular. Here, you're trying to prove that if $L_1$ is regular then $L_2$ is regular. The pumping lemma can't be used to prove this implication. It could be used to prove the contraposite (i.e. you might be able to prove that if $L_2$ is not regular, then $L_1$ is not regular by the pumping lemma). However, even assuming this can work (I haven't checked), it would be a lot more complicated than necessary for this result.

You write “what if $v$ is non-regular?” But this doesn't make sense: the concept of regularity applies to a language, not a word. For a given $u$, what language does $v$ have to belong to, in order for $uv$ to be in $L_2$?

If that's not enough of a hint, try reasoning with regular expressions. If $L_1$ is regular, then there is a regular expression that characterizes it. How can you use this regular expression to characterize $L_2$?


Algorithm for blending/merging shapes together like liquid This is a basic example of how 2 circles would come together:

A more complex example would be an arbitrarily shaped polygon like a country on earth, merging with another one or a circle. All of the edges would have to somehow attach to the circle as you move the circle around, so it feels like it's adhering together like liquid.

Wondering if there are standard equations for doing this, or how it is done.

The Povray raytracer has an object like this, the blob. You find its code with some explanations at https://github.com/POV-Ray/povray/blob/master/source/core/shape/blob.cpp .


How to show whether $n2^n = 2^{O(n)}$? show whether $n2^n = 2^{O(n)}$ is true or not.

In my opinion, it's false because O(n) can be n and thus the equality will be wrong, because $n2^n$ grows much faster than $2^n$

One way, if you want to prove that $n2^n \in 2^{\mathcal{O}(n)}$, is to show that there exists a $c \in \mathbb{R}$ such that $n2^n \le 2^{cn}$ for all $n$ greater than some $n_0 \in \mathbb{N}$.

Correspondingly, if you want to show the contrary, then you have to show that such a $c$ does not exist. However, we will see that the statement is true.

Choose $c = 2$, i.e., we ask whether $n2^n \le^? 2^{2n} = 4^n$ for all $n > n_0$. We know that $n \le 2^n$ for all $n \in \mathbb{N}$. Therefore, it also holds that $n2^n \le 2^n\cdot 2^n = 2^{2n}$. Hence, we have an upper bound for the function $n2^n$ by choosing $c = 2$. In this case, we can set $n_0 = 1$, for instance.


Recurrence equation calculation I have a recurrece equation

Changed notations:
$\qquad\displaystyle G(W) = \max \{ G(W - s_i) + v_i \mid 0 \leq i \leq n, w_i \leq W \}$,

I am not sure if I understand $\ w_i $ correctly.

On each iteration my $ w_i \leq W $ . So my $ w_i $ will be previous $ W-s_i $ since G takes one argument?

Here is pseudocode for computing your function:

  Parameters:

  Integer $n$
  Arrays $W,V,S$ of length $n$

  function G(w):

  If $w = 0$, return $0$
  Let $\mathrm{max} \gets -\infty$
  For $i$ from $1$ to $n$:

  If $W[i] \leq w$:

  Let $x \gets G(w-S[i])+V[i]$

  If $x > \mathrm{max}$, let $\mathrm{max} \gets x$

  Return $\mathrm{max}$

I used the notation $W[i],V[i],S[i]$ rather than $w_i,v_i,s_i$.


Dubins TSP NP-hardness proof detail In Le Ny et al.'s paper On the Dubins Traveling Salesman Problem (https://tinyurl.com/y59f7d8x) the authors prove, among other works, that the Dubins Traveling Salesman Problem (DTSP) is NP-hard. I will give here the basics of the proof, after which I will ask my question regarding this proof.

The authors reduce Exact Cover to DTSP, by adapting Papadimitriou's reduction from Exact Cover to Euclidean TSP (ETSP). This is done by first noting how Papadimitriou's proof makes it so Exact Cover has a solution if and only if the optimal ETSP tour has length no more than some $L$. Le Ny et al. note however that if Exact Cover admits no solution, then the optimal ETSP tour has length at least $L + \delta$, not just $L$, for some defined $\delta$. Next, they note that the optimal DTSP tour length has the following relation with an optimal ETSP tour length : $DTSP \leq ETSP + Cn$, for some $C$ (proven by Savla et al.). Le Ny et al. then go on to construct Papadimitriou's ETSP instance from a given Exact Cover instance, in which they then multiply all distances by $2Cn/\delta$.
They then prove that Exact Cover has a solution if the optimal DTSP tour has length no more than $2CnL/\delta + Cn$, whereas Exact Cover has no solution if the optimal DTSP tour has length at least $2CnL/\delta + 2Cn$.

My question now is, why is it necessary to multiply all distances by $2Cn/\delta$ ?
It would seem to me that not multiplying the distances by anything would still result in Exact Cover having a solution if the optimal DTSP tour has length no more than $L + Cn$, and Exact Cover having no solution if the optimal DTSP tour has length at least $L + \delta + Cn$. What am I missing here?

Not multiplying by $2Cn/\delta$, does not result in

  ... Exact Cover having no solution if the optimal DTSP tour has length at least $L+\delta+Cn$.

It in fact would result in a length at least $L+\delta$. This length is not always greater than $L+ Cn$, hence the need to multiply all distances by $2Cn/\delta$, after which one obtains the authors' result : $2CnL/\delta+2Cn$.


How optimal is Lempel-Ziv at reaching the Shannon limit? I find this a bit difficult to describe, but I am interested in the following idea :

The LZ algorithm factors (verb) an input stream into adjacent factors, these are by definition the maximal prefixes of the piece of text that occur in the previous text (or equivalently the previous concatenation of LZ factors).

I know and believe that in the long term (given infinite input and infinite window) this coding scheme can achieve the Shannon limit, that it will find all repeat patterns that exist.

However in any given finite text (but with an unbounded window) how optimal is this?

Do the choice of factors earlier in the input have potential detrimental effects later on? For instance, could LZ converge to a choice of factors that omits certain larger factors, or factor-choices that would result in a better cover of the input (i.e. a choice of factors that  cover more of the text?).

Or is the optimality of LZ only constrained by the window limit, and the finite nature of a text? Please provide some kind of hand waving or intuitive proof.

If you apply the LZ77 algorithm twice, it doesn't find any new repeat patterns the second time. You can show that if there were any repeat pattern present after the LZ77 algorithm has been applied. this would have arisen from a repeat pattern in the original data which LZ77 would have found.

The DEFLATE algorithm follows LZ77 with Huffman coding, and does better for finite strings than LZ77 alone. So LZ77 can be improved upon for finite strings fairly easily, just not by using another iteration of LZ77.

However, the Huffman algorithm doesn't use repeat patterns. If you're asking the question of whether, for finite strings, the LZ77 algorithm does as well as any other algorithm based solely on finding repeat patters, I don't know if anybody has looked at this. The problem isn't quite well-defined as stated, but somebody might be able to prove some interesting theorems about this.


Sum weighted nodes between nodes in a DAG efficiently Suppose we have a directed acyclic graph $G=(V,E)$, such that all vertices have a addible weight, e.g. there is a function $weight: V \to \mathbb{R} $. Moreover two vertices $v,w \in V$ are given and we write $G_{v,w}$ for the subgraph of $G$ that consists of all vertices and path between $v$ and $w$, both included.

The task is to compute the sum of the weight $weight(u)$ of all vertices $u \in G_{v,w}$.
In addition if $v'$ and $w'$ are two vertices, with $G_{v,w}\subset G_{v',w'}$, then the computation on $G_{v,w}$ should not be repeated (kind of divide and conquer, but on subgraphs) to compute the weight of $G_{v',w'}$.

Is that possible?

A vertex $z$ is "between $v$ and $w$" in $G$ (that is there is a path in $G$ from $v$ to $w$ that traverses $z$) if and only if both the following conditions are true: 1) there is a path from $v$ to $z$ in $G$; and 2) there is a path from $w$ to $z$ in $\overline{G}$, where  $\overline{G}$ is the graph obtained from $G$ by reversing its edges.

Using any standard visit algorithm you can compute the set $A$ of vertices reachable from $v$ in $G$ and the set $B$ of vertices reachable from $w$ in $\overline{G}$.

Then you can compute $C = A \cap B$ and find the desired quantity as $\sum_{z \in C} \text{weight}(z)$. Each of the above steps can be performed in linear time.


Complexity of iterative exponentiation I've watched multiple videos and read articles about recursion but I'm still confused. I've got this problem here but I'm unsure how to answer it:

  The following function calculates $x^n$ recursively. How many multiplications does the function make to calculate exp_rec(2, 64)?

def exp_rec(x, n):
    if n==1:
       return x
    else:
        p = exp_rec(n, x-1)
        return x*p

Could someone help explain?

You are unsure how to answer the question.

When you are unsure: I method that does usually not work is trying to think about the problem very hard and waiting for inspiration. It doesn't come.

A method that works quite well is using pen and paper and trying it out. And you'll find that f (2, 64) calls f (64, 1) which doesn't make any further calls.

Now try f (10, 64) -> f (64, 9) -> f (9, 63) -> ... -> f (3, 57) -> f (57, 2) -> f (2, 56) -> f (56, 1). It should be easy to figure out the exact number of multiplications.

But then you need to check for the cases where the recursion doesn't end, and that is when we miss the test "n = 1" altogether because n < 1. If n < 1 then we call f (n, x-1). If x-1 < 1 as well then the recursion never ends. So that is the case when n < 1 and x ≤ 1.

PS. This function does not calculate x^n.


Is there a generic word for "thread or process"? I'm writing about a problem that could be caused by race conditions between multiple threads, or OS-level processes on the same machine or different machines, or VM-level processes like the Erlang VM has.

In this context, the fact of parallel execution is the important part; the language or memory-sharing model is irrelevant.

Is there a generic word that means "thread or process"? "Concurrent unit of execution" is the best attempt I have so far, but it sounds awkward to me.

A process is a context with one or more threads of execution (concurrent with other threads of execution, either in the same process, or perhaps in other processes), and with its own address space (and usually other resources such as open file descriptors, IPC mechanisms, etc.).  More subtle details and implications are described here

So, if address space (and other such resources) isn't relevant to your discussion (and it's probably not given your description), then I would say that the word thread is sufficient to describe the entities involved in your discussion.  Historically task has also been used to describe a thread, and indeed it was perhaps the first word used to describe this concept (see this).

(Note of course there's a difference between concurrent threads and parallel threads -- concurrent threads may be executed in parallel, but it is not necessary for operations to occur in parallel for them to suffer from the issues related to concurrency.)


What is the worst-case big-O time complexity for this code? I had a quiz in my class and didn't do so well on it. I'm looking to find out if someone can explain to me what I did wrong here - our professor is overwhelmed with office hours as we moved online so I thought I'd post here.

def functionC(L):
    for i in range(len(L)):
        if L[i] == i:
            v = L.pop(i)
            L.insert(i, 2*v)
    return

I supplied the following answer:

  The above function is O(n) because the for-loop grows with the size of
  L. The pop and insert functions are both constant time.

the word time is crossed out, but there is no other explanation as to why I received 6/10 for the question. What did I get wrong in this and why?

Here is an image of the question and my answer to prove the quiz has already been graded and handed back.

You need to be aware that the complexity of insert and pop can be $O(n)$ in python ($n = \text{length($L$)}$). Hence, the time complexity can be $O(n^2)$.


Are all finite languages context-free? As far as I know, finite languages have a finite number of strings or words, while context-free languages are generated by context-free grammars. I don't know which aspect should I know that they are correlated with. All I know is that finite languages are regular, and regular languages are context-free. How should I know this?

The language consisting of the words $w_1,w_2,\ldots,w_n$ is generated by the context-free grammar
$$
S \to w_1 \mid w_2 \mid \cdots \mid w_n.
$$


What would show a human mind is/is not reducible to a Turing machine? In computer science it is often assumed that a human mind can be reduced to a Turing machine.  This is the assumption that underlies the field of artificial intelligence.

However, it is an assumption, one that has neither been proven or disproven.

Is there any kind of test within our current capabilities where we can prove/disprove this assumption?

If not, is there any evidence that would suggest one way or another?

Here is a similar question I asked awhile back on theoretical computer science:

https://cstheory.stackexchange.com/questions/3170/human-intelligence-and-algorithms

To answer your question:

  Is there any kind of test within our current capabilities where we can prove/disprove this assumption?

The Turing test was conceived as a way to test a particular special case of this assumption: it gives us a way to test whether a particular AI system is successful at behaving indistinguishably from a human.  Thus, this would give a plausible way to prove the assumption -- if we could come up with an AI system that is good enough to pass the Turing test.  Unfortunately, that's something we haven't been able to do, yet.


Interactions between predictive analytics, ML, and case-based and rules-based reasoning For my studies on economy, I work on prediction of judicial decisions. I don't really understand the interactions between several concepts:

predictive analytics
machine learning
case-based reasoning
rules-based reasoning

At the moment, I understand that predictive analytics is an area of statistics that deals with extracting information from data and using it to predict a outcome, like a judicial decision. In predictive analytics there are 2 kinds of tools: econometric tools like MCO regression and machine learning tools like neural networks.

Among ML tools, we can distinguish between 2 approaches: rules-based reasoning and case-based reasoning. Given a given legal problem, with the rules approach, the algorithm learns the rules that led to these data, deduce a linear model and then we can confront the problem to the model to deduce the solution given by a court. With cases approach, the algorithm brings the given problem closer to similar cases found in the data, and deduces a solution given by a court.

Is it correct?

Are different kind of ML tools like K-NN or neural network only used for one type of reasoning? or they can be used for both?

Personally, I'm not that enamored of the "rules-based reasoning vs case-based reasoning" categorizatin; I'm not sure it is a particularly useful mindset for modern machine learning.  For instance, deep learning is one of the most effective ML methods used today in several domains, yet it doesn't seem to fall into either of those categories.  That's just my opinion; perhaps others might find it useful.

Rather than trying to find this kind of high-level generalization about how ML works, I think it might be more useful to study some specific ML techniques: linear regression, k-nearest neighbors, SVM, random forest, deep learning, etc.


Is this the correct "standard form" of nonlinear programming (optimization) problem and if it is why it's in this form? Rather a simple question I guess, though makes me wonder. The standard form I've found in the book (and on wiki) is something like this:

$\min f(x)$

s.t.

$h_i(x) = 0$

$g_i(x) \le 0$

Is this considered a "standard form" for nonlinear optimization problems? And if it is why it's defined like this? Why it has to be exactly the min of the function and why constraints have to be either equal or less than 0 or equal to 0? I couldn't find any answer why it is as it is actually. Is there some important thing why it couldn't be max actually for example?

There is no "standard form" that you must use. You don't have to write an optimization problem in that way. This is a useful representation in a number of ways; it is very general; and it facilitates some kinds of analysis (e.g., KKT conditions).  But there are no police forcing you to express your optimization problem in this way; you can use whatever you find most useful.

Note that every optimization problem can be expressed in this way, as $h(x)=0$ can express arbitrary constraints on $x$ and $f(x)$ can express an objective function.  So, it is nice from this perspective.


Inconsistent state of a lock I'm reading The Art of Multiprocessor programming and trying to understand their concept of inconsistent locks. Specifically, on page 37, the definition 2.8.1 of an inconsistent lock is not clear to me, as well as Lemma 2.8.1.

Definition 2.8.1. A Lock object state s is inconsistent in any global state where some thread is in the critical section, but the lock state is compatible with a global state in which no thread is in the critical section or is trying to enter.
Lemma 2.8.1 No deadlock-free Lock implementation can enter an inconsistent state.
Proof:
Suppose the Lock object is in an inconsistent state s, where no thread is in the critical section or trying to enter. If thread B tries to enter the critical section, it must eventually succeed, because the implementation is deadlock-free.
Suppose the Lock object is in an inconsistent state s, where A is in the critical section. If thread B tries to enter the critical section, it must block until A leaves.
We have a contradiction, because B cannot determine whether A is in the critical section.

What I don't understand:

Does being inconsistent just mean that if a thread is in a critical section, there's no way other threads can know about it?
What's the contradiction in a lemma proof? Say thread A is in a critical section, and the lock is in an inconsistent state. What stops another thread from overwriting the lock's state and acquiring it?

"inconsistent" here means basically the internal implementation is not reflecting the reality of thread activation and lock availability. aka "defective". ie its not functioning correctly as a thread lock. eg the lock may indicate "active" but no thread has acquired the lock or the lock indicates "inactive" but some thread acquired a lock.
the contradiction is that according to "deadlock free", a lock will eventually be acquired by at least some thread that requests it. but if its in an inconsistent state then some thread is running but the lock indicates that nothing is locked. but then any new thread cannot succeed in obtaining the lock (without running at the same time as A).

note a wrinkle/subtlety from an online ref[1] that closely matches the book exposition (same authors):

  Note that a program can still deadlock even if each of the locks it
  uses satisﬁes the no-deadlock property. For example, consider threads A and
  B that share locks 0 and 1. First, A acquires 0 and B acquires 1. Next,
  A tries to acquire 1 and B tries to acquire 0. The threads will deadlock
  because each one waits for the other to release its lock

[1] Multiprocessor Synchronization and Concurrent
Data Structures Maurice Herlihy / Nir Shavit


Semi-local Levenshtein distance If you have a long string of length $n$ and a shorter string of length $m$, what is a suitable recurrence to let you compute all $n-m+1$ Levevenshtein distances between the shorter string and all substrings of the longer string of length $m$?

Can it in fact be done in $O(nm)$ time?

If you want the minimum number of single-character changes (insert, delete, substitute) that transforms the shorter string $S$ into some length-$m$ substring of $T$, then this can be done in $O(nm)$ time.

The standard algorithm for computing the edit distance between two strings runs in $O(nm)$ time.  It uses dynamic programming to build up a matrix $d[\cdot,\cdot]$ where $d[i,j]$ denotes the minimum number of single-character changes that transform $S[0\ldots i]$ to $T[0 \ldots j]$.

You can use a simple variation of this algorithm to build up a matrix $d'[\cdot,\cdot]$ where $d'[i,j]$ denotes the minimum number of single-character changes that transform $S[0\ldots i]$ to some suffix of $T[0 \ldots j]$ (i.e., to some string $T[k \ldots j]$ for some $k\le j$).  The running time remains $O(nm)$.  This is sometimes known under the name fuzzy string search.

This gives you a single distance, which represents the smallest number of single-character changes needed to transform $S$ into a length-$m$ substring of $T$.  (If you wanted to get all $n-m+1$ edit distances from $S$ to each length-$m$ substring of $T$, I don't know whether that can be done in $O(nm)$ time.)


Why the restriction on the length of the proof in a $(r,q)$-verifier in PCP is inconsequential? In the textbook by Arora-Barak, they define PCP verifier as

While in the definition they put a restriction of $q2^r$on the length of the proof, later, they say that it is inconsequential as the machine can look on at most this number of locations with nonzero probability over all $2^r$ choices for its random string.

The formal version of "the limitation on the proof length is inconsequential" is the following:

If $L$ has a $(r(n),q(n))$ PCP verifier, then it also has an $(r(n),q(n))$ verifier with proof length bounded by $q(n)2^{r(n)}$.

The above holds since as you mentioned, the verifier can ask $2^{r(n)}q(n)$ different queries on a length $n$ input ($q(n)$ queries for each possible outcome of the verifier coins). Let $f_x$ be an embedding (one to one mapping) of the possible verifier queries on input $x$ in the set $\{1,2,...,q(|x|)2^{r(|x|)}\}$. Let $V'$ be the verifier who acts like $V$, with the sole difference that when $V$ asks for index $i$, $V'$ requests $f_x(i)$. It is easy to see that $V'$ is a verifier for $L$ with the same properties, and bounded length proofs.


What is the advantage of Day-Stout-Warren algorithm for balancing BST? While reading about Day–Stout–Warren algorithm for balancing BST which takes any BST and transforms it into a balanced BST in O(n) time.

In my opinion I can achieve absolutely the same with these simple steps:

convert BST into array using inorder traversal. This will give me an array in increasing order and can be completed in O(n)
create a binary search tree by selecting the middle element in array in O(1), put it as a root, and recursively do the same for a right part of an array (putting the value as a root for a right subtree) and the same for the left part. This will also run in O(n)

So in my opinion I can achive absolutely the same in O(n). What is the advantage of DSW algorithm in comparison to this one?

The Wikipedia article states:

  The algorithm [...] is in-place.

You algorithm requires at least twice as much space. This is a significant drawback on huge data sets.

A further possible advantage (I did not check) lies in the constant factors of the runtime function. Intuitively, you always construct a perfectly balanced BST so you may well do (lots) more work than DSW, even if you are still linear. Again, even a factor of magnitude $< 10$ is significant on huge data sets.

In my opinion, this question is more interesting: why use simple BST + DSW instead of using balanced BSTs in the first place? (The answer is hinted at in the article, too.)


How to identify object(s) in image when given a list of all images? I see a lot of articles and topics about OpenCV and machine learning in regards to identifying general things (like cats, or alphanumeric characters) but I am wondering if something more specific is easier/detailed somewhere.

Basically, if I have a folder of 20 images, how would I identify those images contained with another image?  Like for a game, where you have to find all the hidden items in an image but are given a list of the items to find.

To make this even easier, let's just pick one image to find within another and also assume this image to search in won't even change the original image at all (no skewing or rotating), just put it (non-overlapping) somewhere zero or many times.  If done correctly, I would imagine the results would be an array of rectangles that contain each instance of the image.  Just looking for any assistance in learning how to write a program that can do this, even if its just articles/books regarding the technique.  Thank you

Think of images as matrices (2D arrays) of numbers that indicate brightness. If you are looking for an exact match of an image in another, you are looking for comparing 2D integer arrays, which could be done with a double for loop that is done for each possible match location (so it is a 4 deep for loop acutaly).

A more interesting related problem is searching an image with no exact match, but with some kind of similarity instead. For that task you should read into template matching algorithms.


Finding first/last intersection in a set of lines I am given $n$ lines, in the form $y=ax+b$, where

there are no two lines with the same $a$
no three lines intersect in the same point
no vertical lines

I need to find in time $O(n\log n)$ an $x'$ such that for any $x>x'$ there are no line intersections with that $x$ value.

For example consider the lines on the image above, the thick blue line is $x=0$, and the red line is $x=x'$.

Is that possible? Any hints or ideas on how to solve this?

Notice that you want to maximize

$$x' = - {\frac{b_j - b_i}{a_j - a_i}}$$

over all possible pairs of indices $i,j$. If you interpret the lines as points in the plane, so that the line $y=ax+b$ corresponds to the point $(a,b)$, then the above expression corresponds exactly to the negative slope, so you want to look for the minimum slope that occurs between any two points in the set.  You can prove that this slope always occurs between two points that are adjacent after sorting by $b$.  Similarly, to minimize $x'$, it suffices to consider only points that are adjacent after sorting by $a$.

This yields a $O(n \lg n)$ time algorithm for your problem.

Also, here's a somewhat less efficient solution.  It doesn't achieve $O(n \log n)$ runtime (the running time also depends on coordinate magnitude and required precision), but it may be what you're looking for.

Label the lines. Let  $\mathrm{sortedPermutation}(x) = (\mathrm{label}_1, \mathrm{label}_2, ..., \mathrm{label}_n)$ be a function of $x$ that returns the permutation of labels which corresponds to the sorted order of $y$ values at point $x$. Notice that $\mathrm{sortedPermutation}$ becomes constant after $x'$ (the lines never change order again). Let's call this final permutation $P_{\mathrm{final}}$. We've never seen $P_{\mathrm{final}}$ for any $x < x'$. If we had, it means some lines swapped order more than once and, well, lines tend not to do that. $P_{\mathrm{final}}$ is easy to compute in $O(n \log n)$ time.

You can now use $\mathrm{sortedPermutation}()$ to evaluate candidates for $x'$ and decide if they're too small or too big compared to the real value, and use binary search to find $x'$.


Brzozowski's algorithm for DFA minimization Brzozowski's DFA minimization algorithm builds a minimal DFA for DFA $G$ by:

reversing all the edges in $G$, making the initial state an accept state, and the accept states initial, to get an NFA $N'$ for the reverse language,
using powerset construction to get $G'$ for the reverse language,
reversing the edges (and initial-accept swap) in $G'$ to get an NFA $N$ for the original language, and
doing powerset construction to get $G_{\min}$.

Of course, since some DFA's have an exponential large reverse DFA, this algorithm runs in exponential time in worst case in terms of the size of the input, so lets keep track of the size of the reverse DFA.

If $N$ is the size of the input DFA, $n$ is the size of the minimal DFA, and $m$ the size of the minimal reverse DFA, then what is the run time of Brzozowski's algorithm in terms of $N$,$n$, and $m$?

In particular, under what relationship between $n$ and $m$ does Brzozowski's algorithm outperform Hopcroft's or Moore's algorithms?

I have heard that on typical examples in practice/application, Brzozowski's algorithm outperforms the others. Informally, what are these typical examples like?

Most of the below is from Parsing Theory by Sippu and Soisalon-Soininen.

Let $Q$ be the set of states of the DFA. Let $T$ be the input alphabet. Let $|M|=O(|T| \cdot |Q|)$ be the size of the machine. Exercise 3.40 gives a $O(|T|\cdot|Q|^2)$ algorithm for state minimization. As Wikipedia describes, Hopcroft's algorithm has a running time of $O(|T| \cdot |Q| \cdot \log|T|)$ and Moore's algorithm has a running time of $O(|T|^2 \cdot |Q|)$.

Theorem 3.30 states that the subset construction can be done in $O(2^{|T|+\log|T|+\log|Q|})$ yielding an automaton of size $O(2^{|T|+\log|Q|})$ (actually, if the resulting automaton has $|T'|$ states, the running time is $(|T'| + |T|\cdot|M|) \cdot |Q|$). The two reversals and the second determinisation are therefore inconsequential in the running time, so the asymptotic running time of Brzozowski's algorithm is the same as that of the subset construction.

This means that in the worst case, Brzozowski's algorithm is exponentially slower than the other three algorithms. Note that the worst case really does occur: the classic example of the NFA for the language $(a|b)^*a^k$ has $k+1$ states and its corresponding minimal DFA has $O(2^k)$ states, while the reverse of the NFA is deterministic, so running Brzozowski's algorithm on this reversed NFA triggers the worst-case behavior.

However, if the subset construction yields an automata of size $|T'|=O(|T|)$, then its running time is also $O(|T|^2 \cdot |Q|^2)$, which is often the case on real-life inputs. Furthermore, if proper care is taken when computing the closure of a state, then this can be done much faster in most cases (that is, cases where the closure is small), saving a factor $|T|$ in practice (for essentially the same reason that transitive closures can be computed quite quickly on real-world examples). Furthermore, if the input and intermediate automatons are sparse, which means that states have few transitions, then a factor $|Q|$ is saved, which gives a $O(|T| \cdot |Q|)$ running time on 'good' inputs.

Unfortunately, I'm not familiar enough with Hopcroft's or Moore's algorithms to give an analysis of their running times in typical cases. Wikipedia talks about a $O(|T| \log \log |T|)$ running time in some cases, which would make the three algorithms comparable.


Algorithm to create n arrays with maximum difference Let's suppose I want to generate n equal sized boolean arrays with maximum "difference". - "Difference" in this case is defined as that the arrays share as low as possible fields with one another. (an example of share: array1 = {1,0,0,0) and array2 = {1,1,1,1} -> array1 and array2 share 1 field (array1[0] / array2[0])

Just for example: n would equal 2 and the size of the field would be 6
-> the optimum solution would be the arrays [0,0,0,0,0,0],[1,1,1,1,1,1] because they share no fields and so are very "different" from one another
Another example: n was equal to 4 and the size of the array would be 4
-> a solution would be [0,0,0,0], [1,1,1,1], [1,1,0,0], [0,0,1,1] - the arrays share 1.33 fields per array by average

Has anybody an idea of an algorithm or solution strategy that could solve this problem (generate n of these arrays) perfectly (or very good - so that they are as different as possible) (in a realistic runtime)? Thanks very much in advance :D

This problem is posed and solved in Ahlswede and Katona, Contributions to the geometry of Hamming spaces, page 10. If the number of vectors $N$ is even, the best solution is to choose $N/2$ pairs of a vector and its complement (obtained by switching 0s and 1s). If $N$ is odd then choose $N/2$ such pairs and add an arbitrary vector.

Curiously enough, if you want to minimize the average distance, then the answer is still unknown, though it is suspected to be a Hamming ball.


explaining $\lambda$-calculus/functional programming to someone used to Turing machines/procedural programming? I have the following background:

I have experience with object-oriented programming languages
I find Turing machines and the concept of a "procedure" very intuitive.

Yet I'm interested to understand the idea behind the abstract $\lambda$-calculus, and its application in the form of functional programming.

When I read about either $\lambda$-calculus or functional programming, these explanations tend to either:

make reference to practical benefits that seem generally beneficial to me, but don't give me a fundamental-principled understanding. E.g. that functional programming languages are more modular and less error-prone because there are no state-dependencies.
or assume an already existing intuitive familiarity with either $\lambda$-calculus or the practicalities of functional programming. (Essentially these explanations suffer from the curse of knowledge: the authors cannot place themselves in the shoes of someone who doesn't have their intuition yet).

So I am looking for a general, principled, theoretical understanding of the conceptual and formal difference between (1) $\lambda$-calculus and Turing machines, and between (2) functional programming and procedural programming.

I'd like to second both Derek Elkins' and Chi's comments. You can do Functional Programming in most languages, but it requires the discipline to adhere to the functional principles. It's probably harder to learn FP in a language like Javascript\Python because you'll have to fight against the urge to do things the old way you already know.

In a Functional Programming Language (i.e. purely functional) you'll have to do stuff THE FUNCTIONAL WAY, without taking corners. Also, doing practical stuff means you'll have to learn some theory as well.

  make reference to practical benefits that seem generally beneficial to me, but don't give me a fundamental-principled understanding. E.g. that functional programming languages are more modular and less error-prone because there are no state-dependencies.

Something I really like about functional languages (and is kinda contained in what you said about error-proneness) is they often have some pretty amazing Type Systems.

Let's look at a "Hello World" in C:

#include <stdio.h>

int main(){
    printf("Hello World\n");
    return 0;
}

The function main takes no arguments and returns an Int, but there's no way I would know that it is actually doing IO inside it's body, unless I look at the functions body.

I can even change it and only get a warning.

#include <stdio.h>

char* main(){
    printf("Hello World\n");
    return 0;
}

hello.c:3:7: warning: return type of ‘main’ is not ‘int’ [-Wmain]
 char* main(){

The same code in Haskell,

module Main where

main :: IO ()
main = do
  putStrLn "hello world"

The function putStrLn has type Str -> IO(), to put it simply, it takes a String and returns some IO() stuff. Main also returns IO().

If I try to change the main's type to main :: String I would get the following error:

module Main where

main :: String
main = do
  putStrLn "hello world"

hello/src/Main.hs:4:1: error:

    • Couldn't match type ‘[Char]’ with ‘IO t0’
      Expected type: IO t0
        Actual type: String
    • In the expression: main
      When checking the type of the IO action ‘main’
  |
4 | main = do
  | ^

hello/src/Main.hs:5:3: error:
    • Couldn't match type ‘IO ()’ with ‘[Char]’
      Expected type: String
        Actual type: IO ()
    • In a stmt of a 'do' block: putStrLn "hello world"
      In the expression: do putStrLn "hello world"
      In an equation for ‘main’: main = do putStrLn "hello world"
  |
5 |   putStrLn "hello world"
  |   ^^^^^^^^^^^^^^^^^^^^^^

That is, Haskell is telling me that putStrLn will return some IO(), so main is expected to do the same, since it returns putStrLn. Actually it wasn't even required to give main a type, since Haskell has a pretty powerful Type System based on Hindley–Milner Type Inference.

This was a really trivial example, but it is often the case that most Runtime Errors in many languages will be caught as Compilation Errors in pure functional languages. Some languages, like Coq, are so strong that you can prove theorems with it!

  or assume an already existing intuitive familiarity with either $\lambda$-calculus or the practicalities of functional programming. (Essentially these explanations suffer from the curse of knowledge: the authors cannot place themselves in the shoes of someone who doesn't have their intuition yet).

This is actually a problem with Haskell (Survey 2017)

  Most people want the Haskell community to be bigger. To that end, many
  people want the community to be less divisive (for example Stack
  versus Cabal) or less elitist (for example putting down other
  languages). Also more beginner and intermediate documentation and
  tutorials would help.

Some pure Functional languages you might want to give a try:

Haskell
Elm
Coq

Here are some references I've been using through the years to get some familiarity with FP and it's theory.

Some references on the $\lambda$-Calculus:

Books

Lambda-Calculus and Combinators: I've only read the first 3 chapters, but it's a pretty solid introduction to the theory of $\lambda$-calculus.

Lecture Notes

Lambda-Calculus and Types: Lecture notes from a Oxford class with the same name.
Lecture Notes on the Lambda Calculus: Lecture notes from the University of Ottawa.
Introduction to Functional Programming: Lecture notes from a Cambridge course.

Quick Talks

Adam McCullough - Greek Classics: Lambda Calculus For Beginners
Steven Syrek - Lambda Calculus For People Who Can't Be Bothered to Learn It - part 1 of 2
Steven Syrek - Lambda Calculus For People Who Can't Be Bothered to Learn It - part 2 of 2

Lectures

Dana Scott - Theory and Models of Lambda Calculus Untyped and Typed : A five lecture series by Dana Scott.

Some theory about Functional Programming:

Books

The Algebra of Programming
Purely Functional Data Structures
Type Theory and Functional Programming
Software Foundations: A free course on Coq, Functional Programming, Logic and Program Correctness.

Implementation of Functional Programming Languages

Design Concepts in Programming Languages
Implementing functional languages: a tutorial

Lecture Notes

Foundations of Functional Programming


Local Search Optimization Algorithms in Applied Settings -- How best to explain to applied researchers? I realize this may be an opinion-based question, but relevant nonetheless in my opinion.
Context:
I have a local search optimization algorithm, A.
I designed A to address a specific biological question.
A returns many local optima and often gets stuck near said optima.
My target audience (biologists) don't understand this. They want a single plausible answer (the global optimum) or at least many plausible answers (local optima) with low variability. The reason for this is that biologists will need to incur high cost and large effort to reach their end goal. They feel uneasy that A returns many plausible solutions.
Specifics:
The problem faced by the biologists revolves around sampling. Specifically, they would like to know, given current sampling levels, how much more sampling is required to estimate genetic diversity within species.
Unfortunately, there is no means of comparison with other algorithms because this problem hasn't been thought about in a computational light before. Biologists just sample randomly in the field. Crude estimates of necessary sample sizes range from 5-10 individuals, but sometimes only 1-2 can be reasonably collected (due to say, species rarity and/or project budget).
Algorithm A suggests sample sizes 1-2 orders of magnitude larger than the crude estimate, but the variability is large.
For instance, A might suggest anywhere from 200-250 individuals should be sampled to capture 95% of existing genetic variation for a given species.
All plausible sample sizes returned by A are close to the required 95% cutoff, yet the variation in the estimates themselves is quite large.
The makes the biologists uncomfortable because it suggests that A is not very good.
One way I try to frame things is with the analogy of climbing a mountain or hill. We want to get to the top (the global optimum), but there are a lot of obstacles (local optima) in the form of ridges and valleys in the way.
Putting this into a more CS-centric context:
The Travelling Salesman Problem (TSP) is an NP hard problem of great theoretical interest. For this reason, TSP is often solved via local search (e.g., simulated annealing (SA) or genetic algorithms (GA)). Since both SA and GA are stochastic, they will return different routes each time the algorithm is run.
Clearly, the shortest route is targeted. If many local routes are possible, why use local search in the first place?
I realize the answer to the about question is "to get a 'good enough' solution in a finite amount of computation time". However, this doesn't fit well with applied researchers.
Put another way:
In the case of TSP, why would an airport rely on a local search algorithm to find the optimal path if this could mean wasted money and resources?
My question: How can we justify the use of local search algorithms with the same kind of behaviour as A to researchers in very applied fields who otherwise lack math/stats/computer science knowledge?

The question is a bit unclear, but just to add my two cents:

Simulated Annealing and Genetic Algorithms are not classified as ”local” optimization algorithms. They have been designed to overcome the limitations of local searches so they are usually put in the “global” optimization basket.
The fact that they are stochastic doesn’t mean that their results are not reproducible. Standard implementations of SA and GA allow you to specify a random seed, so the optimizations are perfectly reproducible.

So you have many local optima from your algorithm. Do the “better” local optima tell you anything more than the worse ones? What is the actual, physical meaning of your optima? Is there any way you could compare your algorithm with other, established optimization procedures to assess the quality of your implementation? How many parameters (optimization variables) does your model have? Is your objective function expensive to evaluate or quick? We haven’t seen your model so it’s difficult to suggest anything about possible arguments to convince your colleagues.
That said, having an objective function full of local optima is nothing new, very many real life applications are like that. However, in almost all cases we strive for better and better optima all the time (I.e. lower objective functions in minimizations, higher for maximizations) and when we have to account for many optima (for example, for forecasting a matched model) we usually have a good, physical explanation for what we are doing.
I have to admit that your case is a bit unusual, as having orders of magnitude different optima is unheard of (at least for me). But since you haven’t provided a model nor benchmarked your algorithm against others I am afraid these is the best suggestions I can come up with.


Checking if the graph provided by a distance matrix is a tree I came across this problem in an online judge: We are given a distance matrix consisting of $N$ rows and columns. The $i$th line of $j$th row is the distance between node $i$ and $j$ (not necessarily neighbors). The task is to find out if there exists a tree satisfying the given distance matrix or not. The only constraint is $1 \le N \le 2000$ and the time limit is 1 second.

Some sample test cases for clarity:

Input:
N = 3
0 2 7
2 0 9
7 9 0
Output:
True

Input:
N = 3
0 1 1
1 0 1
1 1 0
Output:
False

I couldn't find an answer that is feasible for implementing in a short period of time (this is kind of important for me as I participate in competitions sometimes). An idea came to my mind is that to take the distance matrix as it was an adjacency matrix and compute MST, and then run Dijkstra's SSSP from each vertex through this MST and generate a new distance matrix and finally compare if the initial distance matrix and the matrix we found are identical. I know that this solution is not efficient nor logical (and also I'm not sure if this would work correctly) and that's why I'm posting here for an answer. I can tell that the solution involves DSU (Disjoint Set Union) and DFS from the problem tags but it just didn't come to my mind.

We can assume all weights are positive. Otherwise we can merge all pairs of nodes with distance $0$ to get an equivalent new distance matrix (a rigorous proof would be a little verbose here so I omit it).

We can process all distances from small to large. For a distance $d$ between node $u$ and node $v$, check if $u$ and $v$ are connected (initially there is no edge thus every pair of nodes is not connected). If they are not connected, add an edge with weight $d$ between them. Finally we will get a tree and we can check whether this tree satisfies the distance matrix.

To efficiently determine whether two nodes are connected, we can maintain a disjoint-set data structure where each disjoint set represents a connected component. With this data structure, we can build the tree in $O(N^2)$. In addition, computing all-pair distances in a tree takes $O(N^2)$ time, so the total running time is $O(N^2)$, which is sufficient for the constraints.

Correctness of the Algorithm

If the algorithm reports "yes", then we indeed build a tree satisfying the distance matrix.

On the other hand, if there is a tree $T$ satisfying the distance matrix, we claim that our algorithm will build $T$ finally. We prove this claim by mathematical induction. Suppose our algorithm processes the distances of pairs $(u_1,v_1),(u_2,v_2),\ldots$ in order. Denote by $D(u,v)$ the distance between $u$ and $v$ in the distance matrix.

Our algorithm always adds the edge $(u_1,v_1)$ with weight $D(u_1,v_1)$, while there is always an edge $(u_1,v_1)$ with weight $D(u_1,v_1)$ in $T$.
Assume our algorithm agrees with $T$ for pairs $(u_1,v_1),\ldots,(u_{n-1},v_{n-1})$.

If there is an edge $(u_n,v_n)$ in $T$ (it must have weight $D(u_n,v_n)$), then $u_n$ and $v_n$ are not connected through edges $(u_1,v_1),\ldots,(u_{n-1},v_{n-1})$, which means our algorithm will add this edge by inductive assumption.

Otherwise, there is a path connecting $u_n$ and $v_n$ with length $D(u_n,v_n)$ in $T$. All of the edges in this path must have weights less than $D(u_n,v_n)$, thus are already added by our algorithm (again, by inductive assumption) when processing $(u_n,v_n)$. This means when our algorithm processes $(u_n,v_n)$, $u_n$ and $v_n$ are already connected, thus our algorithm will not add the edge $(u_n,v_n)$.

Now we have proved our algorithm indeed builds $T$, thus will report "yes".


Algorithms for procedural generated mazes For the purposes of this question, a maze is a spanning tree on a square grid (although the type of grid isn't super important).

There are many Maze generation algorithms, but they only work on a finite grid.

What if instead you are working on an infinite grid? But you only need to know finite of the grid at a time (the application I have in mind is a character wandering around in a grid). What are some algorithms I could use?

In particular, it would be best if the algorithm wasn't biased by which parts of the maze you choose to evaluate first.

One algorithm I thought of was a modification of randomized Kruskal's algorithm. Basically, to calculate a part of the grid, you add the walls to the list, and then eliminate walls until the part of the grid you want to reveal, along with the parts of the maze already revealed, are all in the same set. This might have bias though depending on which parts you evaluate first.

If you have to create the maze:

Without boundaries
Generated uniformly
Generated from a seed

It is unfortunately impossible without risking an endless loop, but most times it is good enough to create a really large maze.
Daedalus has lots of features and implements all the algorithms on this page.
To generate a really big maze in Daedalus, start the program -> press File -> run script -> Worlds largest maze -> click Ok -> press i.
From Daedalus features: (beware the rabbit hole)

World's Largest Maze: This script has the option to use different algorithms to generate the parts of the Maze being viewed, which are nested cell fractal, binary tree, recursive division, unicursal Labyrinth, classical Labyrinth, and Hilbert curve Labyrinth.
Mazes created here are enormous, and measure at least a billion passages on each side. Visiting one cell per second, it would take over 31 years just to walk from one side of the Maze to the opposite side, and that’s assuming no walls are in your way. Wall following to actually solve the Maze will take on average 31 billion years

Wall following a maze this large on a regular computer, would take over 100 years. Exceeding the lifetime of a person, I would say this is "big enough".

Nested Fractal: This creates a fractal Maze, which is composed of smaller Mazes connected together. Each cell of an outer Maze contains an inner Maze nested inside of it, where this Maze nesting process can be repeated multiple times.
Consider a 10^9 by 10^9 passage Maze, or a 10x10 Maze nested with 9 levels total. If we want at least a 100x100 section around us, we only need to create the 100x100 passage submaze at the lowest level, and the seven 10x10 Mazes it's nested within, to know exactly where the walls lie within a 100x100 section.  To ensure the Maze remains consistent and never changes as you move around, have a formula to determine a random number seed for each coordinate at each nesting level.

The nested fractal maze has an obvious texture, where you can see the maze is split up into "blocks"

This is the closest i have come to an infinite maze, and it should be possible to extend this by adding randomization to the edges of the lowest level to break the "blocky" texture.
From Daedalus features:

Binary Tree: The algorithm creates Mazes with the special property that each cell has a passage that leads either up or left, but never both or neither. This creates a biased texture, where one can always easily travel diagonally up and to the left without hitting barriers or having to make choices. Moving down and to the right is when the Maze becomes a challenge, so the Maze is hard to solve but easy to solve backwards. The Maze forms a binary tree, with the upper left corner the root, where each node or cell has one or two children, and one unique parent which is the cell above or to the left of it.

Recursive Division: The algorithm creates a Maze by adding walls, where the area within the Maze is divided by a randomly positioned horizontal or vertical wall with a passage opening within it. Each subarea is then recursively divided with more walls until all areas are filled.

Every time we subdivide, we only have to subdivide the part of the maze we are in.

The images are from World's Largest Maze in Daedalus, (the subjectively best) open-source maze generation program, written in C++, and it even has its own scripting language. If you want a more detailed explanation of the algorithms, you can also check out the source code. The images above are colored based on the distance you have to walk to another cell. Black cells can't be reached without exiting the viewport.


Lower bound for number of nonterminals in a CFG Let's say we have a context-free grammar for the language $a\mbox{*}b\mbox{*}c\mbox{*}$.  Is there a way to determine a lower bound for the number of nonterminals in this grammar?  I'm pretty sure you need at least 2, but I haven't been able to prove it.

You need at least two non-terminals here. For suppose not. A rule of the form $S \to \alpha$ cannot include two copies of $S$, since otherwise it would generate a word of the form $\cdots b \cdots a \cdots$ (since $S$ generates $b,a$). A rule of the form $S \to x S y$ (where $x,y$ are words) cannot mention the letter $b$ for similar reasons. The only rules mentioning $b$ are thus of the form $S \to w$ (where $w$ is a word). It follows that every word generated by the grammar has a bounded number of $b$s (since at most one rule of the form $S \to w$ can be applied when generating a given word), so it doesn't generate all of $a^*b^*c^*$.

In contrast, you can generate the language using two non-terminals: $S \to aS|Sc|B$, $B \to Bb|\epsilon$. Therefore the minimum number of non-terminals needed to generate this language is two.


Direct NP-Complete proofs I'm just starting to learn about NP-completeness. While I understand that reducibility plays a key role in this, I'm astonished how few problems I've been able to find who's proof that they are NP-Complete is not based on reduction to an existing NP-Complete problem.

While I understand these proofs are perfectly valid, you loose insight into what makes a particular problem difficult if you have to trace logic through 3, 4, 5+ reductions.

Since NP-Complete is, by definition, an equivalence class, I should be able to start with any of them; however I can only seem to find is this general strategy.

Are there any other problems with direct proofs that they are NP-Complete other than Circuit-SAT and SAT?

At risk of sounding like I'm avoiding the question, I claim that every reduction is a direct proof of NP-completeness, just avoiding a lot of tedious, unnecessary work.

First, let me talk a little about the proof of the Cook-Levin theorem (SAT np-completeness).

At a very high level, the cook-levin theorem proof does this:

Assume R is some problem in NP. Then, by definition, there is a nondeterministic TM $T$ that runs in $p(n)$ time and decides $R$, for $p(n)$ a polynomial.

Then, it is sufficient to show that for any $x$, we can construct in polytime a boolean formula $B$ such that $B$ is satisfiable if and only if $T$ accepts $x$ (within $p(|x|)$ steps, by assumption of $T$).

Finally, by taking the formal definition of a nondeterministic turing machine and translating it into the language of a SAT instance, we construct a formula that is true only if $T$ accepts $x$ within $p(|x|)$ steps. This is a tedious and difficult process, which you can read about here http://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem#Proof

Anyways, the point of this explanation is the last paragraph: notably, that the only nontrivial part of this proof is taking the parts of a NTM and putting it in the language of a SAT instance. But, this is essentially what a reduction is!

For example, when you write a reduction from SAT to 3-coloring, what you are showing is that a SAT instance can be translated into a 3-coloring instance -- and this gives you a direct proof of np-completeness, because we already have a translation from a p(n) time NTM into a SAT instance.

So, cook-levin tells us how to make boolean formulas from an NTM, and a 3-coloring reduction tells us how to make vertices and edges from boolean formulas. Put these together, and you get a direct translation from an NTM into vertices and edges, which is exactly what you're looking for. It just happens to be tedious to deal with all the annoying little pieces of the NTM formalism, so no one likes to deal with that. It's much easier to do a reduction from SAT than a 'reduction' from NTM.


How to solve if we have $3^{(n-2)/2}$ in recurrence relation? In a question i found the recurrence relation $a_n=a_{n-2}+3^{(n-2)/2}$  then i should solve this relation with using generating factor but $3^{(n-2)/2}$ makes difficult to solve . Is there a solution for such a relations ?  Or is my answer  wrong ?


What is the meaning and significance of a Turing machine taking a description of itself as input? Currently I'm reading about the Halting problem. $H(\langle M,w\rangle)$ is a machine which will solve the Halting problem, and then using machine $H$ one creates a new machine $D$ and we run $H$ on input $\langle M, \langle M\rangle\rangle$.

My question is: What is the significance of giving a description of Turing machine as input as in $\langle M,\langle M\rangle\rangle$?

What is the logical reason behind giving the description of a Turing machine as input to $D$?

We can then think of the machine description $\langle M \rangle$ as the source code of $M$. If we do this, then the Halting Problem is really concerned with the decision problem

Given the source code of a program and an input string, will the program halt if fed the string as input?

There are many programs that take program code as input. A compiler is a well-known example; a specialized text editor is another.

If the Halting Problem were decidable, there would be a predictor program that could correctly predict the behaviour of any given program, given its source code. We could then modify the predictor program such that it would always behave differently from the program that it was analyzing. But then we could of course feed this modified predictor program its own source code and predict how it would react. And the conclusion would be that its behaviour would be different from its own behaviour -- and this is of course a contradiction.


Recursion Davis' Staircase understanding I'm going through a hackerrank challenge on recursion https://www.hackerrank.com/challenges/ctci-recursive-staircase

and I'm having difficulty understanding how the solution below solves the problem. Here's the tree (the recursion calls) like you would with the fibonacci problem but I don't see the insight

With N = 3 the possible choices are

3
1,1,1
2,1
1,2

But I don't see these states represented in the tree, I guess I'm not following the logic which makes it hard for me to solve recursive problems

func f(int n){
   if (n < 0) /* base case */
    return 0;
   if (n == 0) /* base case */
    return 1;

   return f(n-1) + f(n-2) + f(n-3)
}

Your base case seems to be wrong.
Suppose we want to climb $n$ stairs, we want to compute $F(n)$. There are three possibilities which can be defined recursively:
1) First cover 1 stair, then there are $F(n-1)$ ways to continue.
2) First cover 2 stairs, then there are $F(n-2)$ ways to continue.
3) First cover 3 stairs, then there are $F(n-3)$ ways to continue.

So we need to add these three options
$$F(n) = F(n-1) + F(n-2) + F(n-3)$$
where base case is

$$F(1) = 1, F(2)=2, F(3) = 4$$

UPDATE (on Charles, and quicksort comments):

How to derive base cases

$F(1)$ means we have only one stair and thus there is only one way to climb it. So, $F(1)=1$.

For $F(2)$ we have two stairs and there are only two ways to climb it: First stair, and then the second, or directly jump on the second stair. So, $F(2) = 2$.

Similarly for $F(3)$. We may move to the first stair, then to the second, and then to the third one. We may also jump to the second and then to the third, or alternatively step on the first and then jump to the third. And finally we could directly jump to the third stair. In total, four possibilities, $F(3) = 4$.

The following is the pseudocode:

 Count(N)
   if N == 1 return 1
   if N == 2 return 2
   if N == 3 return 4
   return Count(N-1) + Count(N-2) + Count(N-3)
 end

As for the above tree, you don't need to "unravel" for the case $N=3$ since it is the base case which is handled in a single if-statement. However, for $N=5$ the recursion tree would look like as the following:

                      ( 5 )
                     /  |  \
                    /   |   \
                   /    |    \
                  /     |     \
                (4)    (3)    (2)
               / | \    |      |
              /  |  \   4      2
            (3) (2) (1)
             |   |   |
             4   2   1

Note that the above method of counting is the most terrible way since you always solve the same subproblems (overlapping subproblems) many times which leads to the exponential time. You could rewrite the algorithm which solves iteratively without using recursion as following

Count(n)
  if n == 1 return 1
  if n == 2 return 2
  if n == 3 return 4

  x1 = 1
  x2 = 2
  x3 = 4
  i = 4

  while i <= n
    sum = x1 + x2 + x3
    x1 = x2
    x2 = x3
    x3 = sum
    i+=1
  end

  return sum
end

Finally (as quicksort noted in his/her comment), you could solve the above recurrence relation and find the closed form formula which gives you $O(1)$ solution (without need to compute the entire sequence up to $N$).


Prove that this family of hash function is $3$-wise independent, but not $4$-wise independent Consider the hash function mapping $w$-bit keys to hash values in
  $\{0,...,m-1\}$. Suppose $w=cr$. Interpret a $w$-bit key $x$ as a
  vector $(x_1,...,x_c)$ of $c$ $r$-bit keys.

  Consider the hash family:

  $$H = \{h_{T_1,...,T_c}:T_i \in \{0,...,m-1\}^{2^r}\}$$

  where

  $$h_{T_1,...,T_c}(x) = \sum\limits_{1\le i \le c}T_i[x_i]\mod m$$

  Prove that $H$ is $3$-wise independent, but not $4$-wise independent.

  $H$ is $k$-wise independent if for inputs $x_1,...,x_k$ and output
  $v_1,...,v_k$, $\Pr[h(x_1) = v_1 \wedge ... \wedge h(x_k)=v_k] =
 \frac{1}{m^k}$

So I can certainly see why $H$ is $1$-wise and $2$-wise independent if we're choosing inputs to the hash function that must be different from each other. However, I'm having a lot of trouble seeing why the family is not $4$-wise independent, which I think lends greatly to my difficulty in proving that the family is $3$-wise independent.

So for the family to not be $4$-wise independent, if we have inputs $x_1,...,x_4$ and outputs $v_1,...,v_4$, $\Pr[h(x_1)=v_1\wedge...\wedge h(x_4)=v_4]\not = \frac{1}{m^4}$. I am trying to think of a counterexample where this will not be the case, but it seems like we need, for example, $x_4$ to be constructed in such a way that $v_4$ can be attained by some combination of $v_1,v_2,v_3$. However, all of $x_1,...,x_4$ are $w$-bit keys, so even if $x_4$ had bits taken from each of $x_1,x_2,x_3$, the output $v_4$ would still be some random sum corresponding to the $c$ $r$-bit blocks accessing each $T_i$.

Is there something I'm missing here? Perhaps it's not possible for $v_4$ to be some combination of $v_1,...,v_3$, but how else would we show that $H$ is not $4$-wise independent?

Hint for refuting 4-wise independence: Suppose for simplicity that $c = 2$, pick some $\alpha \neq \beta$ of length $r$, and consider the four inputs $(\alpha,\alpha),(\alpha,\beta),(\beta,\alpha),(\beta,\beta)$.

Hint for proving 3-wise independence: Let the three inputs be $x,y,z$. If there is some coordinate $i$ such that $x_i,y_i,z_i$ are all different then we are done. Otherwise, without loss of generality there are coordinates $i,j$ such that $x_i = y_i \neq z_i$ and $x_j = z_j \neq y_j$, and we are again done.


If $j − 1 < \log k < j$. Why is $j = O(\log k)$? If $j \in Z^+$ and $k \in R^+$ and $j − 1 < \log k < j$. Why is $j = O(\log k)$? (All log's are in base 2)
I know I have to find constants where $j <= c \cdot \log k$ but I need some help with it.

You solved your own question. Quite literally the bounds you gave (with $c=1$ or $c=2$) should suffice


Sub-exponential time algorithm to compute playoff chances There are 10 teams, Team A through Team J, playing in a triple round robin pool (each team plays thrice against each other team, for a total of a 27 games per team). After the round robin pool, the top 4 teams (with the highest number of wins) make playoffs (with some tie-breaking procedure that can be done in polynomial time).
After some number of games, we are given the records for each team (including all head-to-head records). Assuming the remaining $g$ games have outcomes which are coin flips, we want to calculate the percentage chance each team makes playoffs.

Here's a brute-force solution. There are $g$ remaining games, so we can consider $2^g$ binary sequences where a 0 in each position means the team earlier in the alphabet wins, and a 1 means the team later in the alphabet wins. For each sequence, we can compute which teams make playoffs. Then, the percentage chance of making playoffs can be computed as the number of sequences in which a given team makes playoffs divided by $2^g$.
This obviously has exponential time complexity (in $g$). Is there a better algorithm to solve this problem - perhaps a polynomial time algorithm using dynamic programming? Is there some way to prove we can do no better than exponential time? Is it possible to show this problem is NP-hard?

One simplification that can be made (which unfortunately does not reduce the complexity) is that we can compute, in polynomial time, teams which are guaranteed to make or guaranteed to not make playoffs. All games between teams in either set will not affect the probabilities for teams in the middle. As $g \to 0$, this gives a substantial practical boost to the algorithm.

Note that 10 teams playing triple round robin are arbitrary and this problem can be generalized to $N$ teams playing a $k$-round robin. Specifically for the brute-force algorithm, it is exponential in $g$ which may not be related to $N$ or $k$. A sub-exponential algorithm should ideally be not exponential in any of $\{N, k, g\}$.

A pragmatic solution is to use Monte Carlo: do one million random simulations, and for each team, count in how many simulations it made it to the top 5.  This should give you a good approximation of these probabilities, even though the number is not exact.
If you want the exact probabilities, I think there is a complex solution that has polynomial asymptotic running time.  I don't know whether it will be useful in practice.  We'll enumerate all possibilities for the set of teams that make the top-4 and the 5th team, and for each such combination, compute the exact probability obtaining such an outcome.  Asymptotically, if there are $n$ teams, this will involve enumerating $O(n^5)$ combinations, and I'll show below how to compute each of these probabilities in polynomial time, which yields a polynomial-time algorithm -- albeit one that might still be to slow to implement in practice.
Here's how to compute the probability of a particular combination of outcomes, namely, that a specified 4 teams make the top-4 (in some order) and one more specified team is #5.
For each game yet to be played, we can introduce a zero-or-one variable $x_i$ that records who wins.  We can write down a set of linear inequalities that characterize the conditions under which the desired outcome occurs.  The total number of wins of each team is a sum of some of these variables, and we want each of the top-4 teams to have at least as many wins as the #5 team, and every other team to have fewer wins than the #5 team, so we obtain inequalities comparing sums of these variables.  Also for each $x_i$ we have the inequality $0 \le x_i \le 1$. This gives us a linear program, or in other words, a convex polytope.  Now the question is to count the number of integer solutions to this linear program, or equivalently, the number of lattice points inside this convex polytope.  There are known polynomial-time algorithms for this problem; see Finding all solutions to an integer linear programming (ILP) problem.
However, I suspect this fancy algorithm might be non-trivial to code up and might not be very useful in practice, even though it is polynomial time in theory, because of the large polynomials involved.

If you care about the asymptotic running time, I think there might be an improvement to the latter algorithm.  For each team, enumerate all candidates for $t$, the number of wins of the #5-ranked team.  Introduce zero-or-one variables $y_i$, where $y_i=1$ means that team $i$ was in the top 5.  If we are counting solutions where team $j$ is in the top-5, force $y_j=1$.  We obtain an expression $e_i$ for number of wins of team $i$, where $e_i$ is linear in the unknowns $x_i$.  We can then add the inequalities
$$y_i t \le e_i \le t-1 + (3n-2-t) y_i$$
$$y_1 + \dots + y_n = 5$$
and count the number of solutions to this system.


How to predict the length and offset of the sequence in and array? I have an input string similar to ABCDEFGHIJK from which a series of sequences has been generated into an array as following:

00: 'ABCD'
01: 'BCDE'
02: 'CDEF'
03: 'DEFG'
04: 'EFGH'
05: 'FGHI'
06: 'GHIJ'
07: 'HIJK'
08: 'ABC'
09: 'BCD'
10: 'CDE'
11: 'DEF'
12: 'EFG'
13: 'FGH'
14: 'GHI'
15: 'HIJ'
16: 'IJK'
17: 'AB'
18: 'BC'
19: 'CD'
20: 'DE'
21: 'EF'
22: 'FG'
23: 'GH'
24: 'HI'
25: 'IJ'
26: 'JK'
27: 'A'
28: 'B'
29: 'C'
30: 'D'
31: 'E'
32: 'F'
33: 'G'
34: 'H'
35: 'I'
36: 'J'
37: 'K'

The sequences in the array above has been generated by following these steps:

Set length to 4
Set offset to 0
Pick a sequence of length long characters from "ABCDEFGHIJK" (Input string)
Put the sequence at the bottom of output array
Increase offset by 1
If offset + length <= 11 (Input string's length) then goto 3
Decrease length by 1
If length >= 1 then goto 2
Exit

By looking at the output array, sequences in the array have a length which starts at 4 and gradually goes down to 1, and also an offset which is where in the input string the sequence has begun.

What I'm trying to achieve is to "predict" both the length and the offset of a sequence at a given index in the output array, only having the input string's length and index in the output array.

I'm preferably looking for a formula, however an algorithm which doesn't involve simulating the output array will work as well.

Let $n$ be the length of the string, and $k$ be the maximum length of the substring. Thus the first $n-k+1$ positions correspond to length $k$, the next $n-k+2$ to length $k-1$, and so on. Denote by $i_\ell$ the index at which substrings of length $k-\ell$ begin. We have
$$
i_\ell = \sum_{t=k-\ell+1}^k (n-t+1) = \frac{[(n-k+1)+(n-k+\ell)]\ell}{2} = \frac{\ell^2}{2} + \ell\left(n-k+\frac{1}{2}\right).
$$
Given $i_\ell$, we can solve for $\ell$:
$$
\ell = \sqrt{(n-k+1/2)^2+2i_\ell}-(n-k+1/2).
$$
Monotonicity shows that for arbitrary $i$, the floor of this expression still gives the correct value of $\ell$. This suggests the following algorithm:

Let $i$ be the input index.
Calculate $\ell = \lfloor \sqrt{(n-k+1/2)^2+2i}-(n-k+1/2) \rfloor$.
Calculate $i_\ell = \ell^2/2 + \ell(n-k+1/2)$.
Output length=$k-\ell$ and offset=$i-i_\ell$.

For example, let's take $i = 10$ in your case (where $n = 11$ and $k = 4$). Then $\ell = \lfloor \sqrt{7.5^2+20}-7.5 \rfloor = \lfloor 1.23\ldots \rfloor = 1$ and $i_\ell = 1^2/2 + 1\cdot 7.5 = 8$. Hence the length is $4-1=3$ and the offset is $10-8=2$.


NP Problem and reduction I've read that "Every problem in NP can be reduced to every NP-complete problem".
I want to know why the term "Every" is important.If we have one problem in NP that is reduced to one NP complete problem then what will be the problem.

Since NP-Complete problems can be reduced to each other, If we can reduce a problem to a specific NP-Complete problem. It means that we can reduce it to any NP-Complete problem.
The reason is All problems in NP-Complete can be reduced to SAT and SAT to 3-SAT and 3-SAT to CLIQUE and so forth. So reducing to a problem in NP-Complete means reducing to all problems in NP-Complete.


Context-free grammar for binary words I am supposed to create CFG for this languague:

$L= \{w : w \in \{a, b\}^*, |w_b| = 3k, k \geq 0 \}$

where $|w_b|$ is count of terminals $b$ in $w$.

For example:

aa - OK, no 'b'

abb - wrong, only 2 'b'

aaabbb - OK, 3 times 'b'

aababbb - wrong, 4 times 'b'

abbbbbaaa - wrong, 5 times 'b'

abababbbaaab - OK, 6 times 'b'

and so on...

I can't come up with any solution. Any advice?

My goal is to design context-free grammar, not automaton or regular expression (i don't know how to design automatons or RE yet).

What about CFG

G = {{S,A}, {a,b}, R, S}

where R rules are:

1] S -> S A b A b A b A S
2] S -> A
3] S -> ε
4] A -> a A
5] A -> ε

Explanation:

rule 2] is for cases when there are no 'b' symbols in w

rule 3] is for case of empty string

rule 4] is for adding 'a' symbols between 'b', e.g. baaaabab, babaab

rule 5] is for cases, when there are multiple 'b' next to each other, e.g. abbbaaa

Is this CFG ok?

Hint: A string with exactly one $a$ would look like this:
$$
(any\ number\ of b's)\,a\,(any\ number\ of b's)
$$
and a grammar to generate the language of these strings is $S\rightarrow AaA,\ \  A\rightarrow aA\mid \epsilon$.

Generalize.


$\omega$-string avoiding a set of substrings Given a set of strings $S$ over $\{a,b\}$. How to determine whether there is an infinite sequence consisting of ${a, b}$ (i.e., a $\omega$-string), which doesn't have any string in $S$ as a substring?
The total length of all substrings in $S$ is at most $20000$.

If every $\omega$-string contains a substring in $S$, then we say that $S$ is unavoidable or a universal hitting set (UHS). There is a classical algorithm for detecting whether a set of substrings is unavoidable, described for example in Lothaire's Algebraic combinatorics on words, Section 1.6.
Construct a graph $G$ as follows. The vertices are all prefixes of strings in $S$. For every prefix $p$ and symbol $\sigma$, we connect $p$ to the longest suffix of $p\sigma$ appearing in the graph. The set $S$ is unavoidable iff every cycle in $G$ passes through a vertex corresponding to a word in $S$.
To see this, suppose first that every cycle in $G$ passes through a vertex corresponding to a word in $S$. Consider some $\omega$-word $w$. Starting at the vertex $\epsilon$, "read" the symbols of $w$ one by one. Eventually you will hit a cycle (since $G$ is finite). By assumption, this cycle contains a vertex $v$ in $S$, and so $w$ contains $v$. In the other direction, tracing an $S$-less cycle (replacing each edge by the symbol $\sigma$ used to create it) results in a periodic $\omega$-word which avoids $S$.


A non-mechanical way to get an infinite decidable subset of a Turing-recognizable language? There's a famous theorem that every infinite Turing-recognizable language has an infinite decidable subset. The standard proof of this result works by constructing an enumerator for the Turing-recognizable language, then including the first enumerated string in the decidable language, then the first string that comes after it lexicographically, then the first string that comes after that lexicographically, etc. Since this set is enumerated by a Turing machine in lexicographically increasing order, it's decidable.

This construction works, but it doesn't seem to give a very "natural" example of an infinite decidable subset. In particular, the only way I can think of to describe the subset is to point at a specific enumerator for the language, define a recurrence relation from it, and then define the language from that recurrence relation.

Is there an alternative construction that produces an infinite decidable set from an infinite Turing-recognizable language that is less dependent on the particulars of how a specific enumerator runs?

Let $\Sigma$ be an alphabet, let $\mathcal{R}$ be the collection of all recognizable subsets (languages) of $\Sigma^{*}$ and let $\mathcal{D}$ be the collection of all decidable subsets of $\Sigma^{*}$.

Say that $n \in \mathbb{N}$ is a code for $L \in \mathcal{R}$ if the Turing machine encoded by the number $n$ (via some Gödel encoding of Turing machines) recognizes $L$. Let us write $L_n$ for the set that is recognized by the $n$-th Turing machine.

Similarly, say that $n$ is a code of $D \in \mathcal{D}$ if the $n$-th Turing machine is the decider for $D$. If $n$ is the code of a decider (not every number is!) then we write $D_n$ for the set it decides.

Consider the statement: "For every infinite $L \in \mathcal{R}$ there is an infinite $D \in \mathcal{D}$ such that $D \subseteq L$."

You are asking whether we can prove the statement by giving an effective procedure which assigns to every $L$ a corresponding $D$ in such a way that $D$ does not depend on the choice of the code of $L$. (Clearly, we can do this inefectively by an application of the axiom of choice.) More precisely, the question seems to be whether there a computable map $f$ such that

if $n$ codes an infinite $L \in \mathcal{R}$ then $f(n)$ codes an infinite $D \in \mathcal{D}$ such that $D \subseteq L$, and
if $L_n = L_m$ then $D_{f(n)} = D_{f(m)}$.

The answer is no, there is no such map: you must appeal to a particular recognizer for $L$ and obtain a $D$ which depends on the recognizer.

To prove that this is really so we appeal to Rice's theorem. Suppose we had such an $f$. There exists $n, m, a \in \mathbb{N}$ such that $a \in D_n$ and $a \not \in D_m$. The subset $S \subseteq \mathcal{R}$ defined by
$$L \in S \iff \exists n \,.\, L = L_n \land a \in D_{f(n)}$$
is a non-trivial decidable subset of $\mathcal{R}$, which violates Rice's theorem.


Determine what is the best order for running filters on a dataset I'm trying to figure out what is the optimal order for running a sequence of tasks in a pipeline.

Each task filters a percentage of the dataset.

Assuming I got the tasks t1, t2, t3, ..., ti and a dataset. Each task have an execution time per item in the dataset denoted as e1, e2, e3, ..., ei and each task filters a certain percentage of the dataset denoted as f1, f2, f3, ..., fi.

What is the optimal sequence of tasks to achieve the minimum running time ?

I've first tried to examine two tasks - t1 and t2 with their representative execution time and filter percentage - e1, f1 and e2, f2.

I want to find the ordering predicate for getting e1 + f1*e2 < e2 + f2*e1. I'll get the condition e1 / (1 - f1) < e2 / (1 - f2). And I guess that from here I'll need to prove it in induction, but I'm stuck because the equation is some kind of recursion.

You can prove that the optimal ordering is according to ascending order of e(i)/f(i).

Proof:

Let r(i) = 1 - f(i).
The total cost of an ordering is: e(1) + e(2)*r(1) + e(3)*r(2)*r(1) + ... + e(N)*r(N-1)*...*r(1)

Now, assume that there's an optimal ordering that doesn't follow the rule above. It follows that there are two adjacent tasks t(i) and t(i+1) such that e(i)/(1-r(i)) > e(i+1)/(1-r(i+1)) => e(i)*(1-r(i+1)) > e(i+1)*(1-r(i))
swapping these two will change the value of only two expressions in the total cost expression, resulting in a delta of:

e(i) * r(i-1)*...*r(1) + e(i+1)*r(i)*...*r(1) -
e(i+1)*r(i-1)*...*r(1) + e(i)*r(i+1)*r(i-1)*...*r(1) =
r(i-1)*...*r(1)*[e(i) + e(i+1)*r(i) - e(i+1) - e(i)*r(i+1)] =
r(i-1)*...*r(1)*[e(i)*(1-r(i+1)) - e(i+1)*(1-r(i))] > 0

The delta is positive, meaning that the original configuration is more expensive than the outcome of the swap, therefore we have a contradiction.


Theoretical question about Zobrist hashing and chances of collision with slight modification I have a hash table that uses zobrist hashing to calculate the hash for various positions. The hash table is used to look up various transpositions. For some positions I do not want to allow any transpositions, but I still want to store the position in the hash table. So I'm trying to make the position's hash unique by XOR'ing it with the memory address of the object that holds the position structure. Here is some pseudocode:

hash = zobristHash(position);
if (makeItUnique)
    hash := h XOR [memory address of position object]

Is there any reason to suppose that what I'm doing will increase the likelihood of hash collisions?

it may be better to store them in separate hash table. or, if you need them in the same table:

tmp = position
if (makeItUnique)
    tmp := [memory address of position object]
hash = zobristHash(tmp);

It's better than your current code since it will avoid collisions of objects with the same position AND similar memory address (the definition of similarity here depends on how you use the hash value to address the hash table)