Algorithm for determining if there is exactly one Eulerian path Given a directed graph such that at least an Eulerian path exists, how to determine efficiently if there is exactly one Eulerian path?

Of course if there is an Eulerian circuit then there is more than one Eulerian path, so we will assume that no Eulerian circuit exists.
In other words, just to fix some notation, we assume that for all nodes $\text{indegree}=\text{outdegree}$ except for two nodes $r$ (starting point) and $s$ (ending point) for which the following holds:
$$\text{outdegree}(r) = \text{indegree}(r)+1$$
and
$$\text{indegree}(s) = \text{outdegree}(s)+1.$$

An observation. If there is a node with $\text{outdegree} \geq 3$ then there are at least two distinct Eulerian paths. Is this condition only sufficient or maybe even necessary?

Do you know an algorithm for finding Eulerian paths?
Fleury's algorithm begins at one of the endpoints and draws out the eulerian path one edge at a time, then imagine removing that edge from the graph. The only trick to the algorithm is that it never chooses an edge that will disconnect the graph. Only with that condition, it is guaranteed to never get stuck in tracing out an eulerian path.
So, as long as that choice of edge is unique at every step, the eulerian path will be unique. If ever there are two choices that can be made which are valid (i.e. they each would not disconnect the graph) then you have multiple eulerian paths.


Connected Components - Linear Decision Trees What does connected components mean in the context of non-graphs? Graphs have vertices and the vertices are connected by edges. Hence, you can build a spanning tree (for example) by systematically joining connected components (where connected components refer to connected subgraphs).

Previous discussion on this topic reveals that each connected component of a linear decision tree on some function F represents a particular region bounded by a set of half-planes and hyperplanes. For linear decision trees applied to the element uniqueness problem, we have 2 possible type of connected components (correct me if I'm wrong) - YES and NO components.

Apparently there is only 1 NO component, and at least n! YES components when for linear decision trees applied to the element uniqueness problem on a set of "n" distinct items. I can understand the number of YES components (simply permute all items), but I'm not sure why there's only 1 NO component.

Connected components are a concept of topology. Under the usual topology on $\mathbb{R}^n$, we say that two points $x,y \in S$ belong to the same connected component if there is a path from $x$ to $y$ which is entirely in $S$ (this is known as path-connectedness). This defines an equivalence relation on $S$, and a connected component of $S$ is an equivalence class of this relation. This generalizes the graphical definition which is more familiar to this audience.


Is there a way to theoretically compare hash functions? Say I am given two hash functions f1 and f2 is there anyway that I can prove one hash function will produce fewer collisions than another one? That is say for some domain assuming all values in the domain are equally likely to be chosen can I show that f1 will on average perform better than f2?

Looking up how to determine if one hash is better than the other lead me to some interesting articles of how to compare cannabis but I couldn't find much else.

One measure to compare two hash function is the expected value of collision in the hash function. Now, based on the expected value, if a hash function has a lower collision in the expected sense could be a better hash function here. This expectation can be estimated by a random sample with a proper size from the specified domain.

Moreover, hash functions are compared base on their time complexity too, which is not your case here.


How CompCert "proves" different things in its codebase In order to understand examples of formal proofs, I am interested in how CompCert applies "proof" techniques. Specifically, I am wondering what a particular example is of something CompCert "proves" in their GitHub repo, so I can get a grasp of how proofs are applied in practice (to something that is somewhat familiar, compiler technology). I have had some minimal experience with Coq so I should be able to follow along. I also have some experience with x86, so perhaps something in the x86 folder would be a good example. Or perhaps something directly to do with the C language (such as Clight), or with memory.

In x86/Asm.v, they have several Inductive definitions, which I think is a proof in itself. For example:

Inductive ireg: Type :=
  | RAX | RBX | RCX | RDX | RSI | RDI | RBP | RSP
  | R8  | R9  | R10 | R11 | R12 | R13 | R14 | R15.

Inductive instruction: Type :=
  ...

Then they have some Definition definitions:

Definition code := list instruction.

Definition is_label (lbl: label) (instr: instruction) : bool :=
  match instr with
  | Plabel lbl' => if peq lbl lbl' then true else false
  | _ => false
  end.

Wondering if this is also a "proof" of some sort since (I think) it is some sort of type.

They also have Lemma definitions, where the explicit proofs are:

Lemma is_label_correct:
  forall lbl instr,
  if is_label lbl instr then instr = Plabel lbl else instr  Plabel lbl.
Proof.
  intros.  destruct instr; simpl; try discriminate.
  case (peq lbl l); intro; congruence.
Qed.

I understand about Coq tactics, but haven't actually written any proofs myself so don't have applied knowledge.

So here we have Inductive is used in a Definition which is used in a Lemma. And then it looks like that lemma is used by other lemmas:

Lemma transl_code_label:
  forall lbl f c ep tc,
  transl_code f c ep = OK tc ->
  match Mach.find_label lbl c with
  | None => find_label lbl tc = None
  | Some c' => exists tc', find_label lbl tc = Some tc' /\ transl_code f c' false = OK tc'
  end.
Proof.
  induction c; simpl; intros.
  inv H. auto.
  monadInv H. rewrite (transl_instr_label' lbl _ _ _ _ _ EQ0).
  generalize (Mach.is_label_correct lbl a).
  destruct (Mach.is_label lbl a); intros.
  subst a. simpl in EQ. exists x; auto.
  eapply IHc; eauto.
Qed.

In this question I am wondering what a proof consists of in CompCert, given some example like the above. I would like to be able to know what I need to write a proof for my own software, by first knowing what CompCert is actually "proving", and how they are "proving it". It seems that there are types (Inductive and Definition), and then proofs (Lemma and Proof). Not sure if the Inductive/Definition things are proofs in and of themselves. Proofs traditionally are essentially just derivation trees of applying rules, but I'm not exactly sure if that is what is happening here. It seems the Coq tactics are just creating a derivation tree, correct me if I'm wrong. Then the lemma/proof is just a derivation tree (a bunch of rules applied) down to the "axioms" (definitions and inductive types). The fact that there could be an electronics error isn't accounted for (I don't think), so the proof is really of a "pure" system in some sense. So practical proofs are applied to pure systems that make some assumptions about the environment.

In the end, I'm wondering, the kind of "proof system" CompCert is. What is making it a good system of formal proofs. Knowing that, I would be able to apply "proofs" to stuff outside of CompCert but in other programming contexts. Also wondering if there is some sort of "specification" that CompCert is formally verified against, or if it is just the "model" (as in the model in model checking vs. specification).

I am not very sure what you are asking, and I am also not sure that you have the background to understand CompCert. It seems that you are still confused by some basic concepts in Coq.

I would suggest you start with Software Foundations. Most of your questions would be answered there.

But, basically:

Definition and Fixpoint are like OCaml's let and let rec, respectively. They are used to define values and functions (and, of course, propositions).
Inductive is like  type in OCaml, or datatype in SML. They are used to define algebraic data types (or "inference rules").
Prop is the sort of propositions, so Definition and Inductive that return Props are defining propositions (i.e., "proof rules"). The Definition and Inductives are not themselves proofs.
Lemma, Theorem, Corollary, etc...are used for proofs.
Coq is based on the Curry-Howard correspondence: a proof of the proposition $A \rightarrow B$ is a function that takes something of type $A$ and produces something of type $B$, a proof by induction corresponds to a recursive function, etc. A proof of $A = B$ is obtained by transforming both sides and applying the only constructor of the type $=$, which is Refl of x * x (not Coq syntax, but you should get it). So, all proofs by tactic actually expand into programs!
In other words, Coq tactics are just another style of programming. You can use Definition and/or Fixpoint to write proofs, or use Proof to write programs. Of course, you should not do so; but you can.
CompCert is indeed proved against a formal specification. Which one? The official C programming language specification! Of course, you can't really prove anything against the text of the specification, so they encoded the specification in Coq using Definitions and Inductives.

In Software Foundations, there are examples of verifying a few toy interpreters and some toy programs, as well as more serious examples of verifying algorithms like red-black tree insertions and graph coloring. It does a pretty good job of explaining what and how to prove when you are writing programs in Coq. I would suggest that you start from there.


What are the differences and relations between a type constructor and a type operator? What are the definitions of a type constructor and a type operator?
What are their differences and relations?
I think a type operator is a function whose parameters are n types and return is a type. A type constructor also means the same thing.
I use them exchangeably. But some reply used type constructor when my question (I forgot where) used type operator.
In Types and Programming Languages by Pierce, the index says

  type constructors, see type operators

Ch 29 says informally that

  these type-level functions, collectively called type operators, more formally.

Is it correct that type operators/constructors are used only and exactly to create algebraic types, and algebraic types are created only and exactly by type operators/constructors?

Is Ref in Ref T a type operator/constructor? Is Ref T an algebraic type?

Thanks.

These sorts of terms in type theory are not always used completely consistently. However, type operators are generally type-level functions: that is, they take as arguments some number of types and return a single type. Type constructors are a specific kind of type operator for which the return type is free in the sense that it is a new type on its arguments.

Generally speaking, if you have a type operator $T: \star \to \star$ and for any type $A : \star$, you have a type $T(A) : \star$, which is not prima facie equal to anything else, then it is called a type constructor.

For example, $\times$, $+$ and $\to$ are all type constructors. Type-level application is not, because the application of $(\lambda X . X + X)\ Y$ is reducible to $Y$, i.e. the application of the type operator is equal to some other type.

In your example, $\mathrm{Ref} : \star \to \star$ would be considered a type constructor. If by "algebraic type" you mean "algebraic data type", then $\mathrm{Ref}(T)$ is not an algebraic data type, because it's part of the type system rather than formed as a composite type out of products and sums.


Algorthm: Given a set of points, width around line, find line to capture maximum points I want to know if there is an algorithm for this problem.

I have a list of points given as (x,y) values and a given distance. I want to draw a line through the set of data points so that the size of the set of points that is within the given distance from the line is maximized. That is, this line

Does an algorithm for this problem exist?

If your notion of distance is "vertical distance", similar to how residuals are computed during ordinary linear regression, this problem can be solved with linear programming.

Let $y=ax+b$ be the equation of the desired line; here $a,b$ are unknowns.  Suppose we are given a list of points $(x_i,y_i)$.  The vertical distance from $(x_i,v_i)$ to the line $y=ax+b$ is

$$|ax_i+b-y_i|.$$

Suppose we want this distance to be at most $d$, where $d$ is given.  In other words, we want

$$|ax_i+b-y_i| \le d.$$

This is equivalent to

$$y_i-d \le ax_i+b \le y_i+d,$$

which gives two linear inequalities.  (Recall that $x_i,y_i,d$ are known, and $a,b$ are unknown.)  Given $k$ points, you get $2k$ linear inequalities.  Now you can use linear programming to find $a,b$ that satisfy all of these linear inequalities.

You can even find the minimal value of $d$ such that such a line exists.  Simply treat $d$ as an additional unknown, and minimize $d$ subject to the $2k$ linear inequalities above.


CISC and RISC - synchronous and asynchronous I have two opposing ideas. I think that all the instructions in a RISC take the same time what makes me believe RISC is associated with synchronous.

At the same time i think that CISC should be synchronous and RISC should be asynchronous.

Can you tell me if RISC is associated with asynchronous and CISC is associated with synchronous? Why?

I think that all the instructions in a RISC take the same time what
  makes me believe RISC is associated with synchronous.

It's not true that all instructions in a RISC CPU take the same time. Even in the classic RISC pipeline, the pipeline will stall in some circumstances. Pipeline interlocks and control hazards are the ones that Hennessy and Patterson go into some detail about, but they also mentioned data cache misses.

Even if you ignore those complications, it's unrealistic to design a general-purpose CPU where every instruction takes the same time these days. Programmers want floating point, and SIMD operations, and so on.

  Can you tell me if RISC is associated with asynchronous and CISC is
  associated with synchronous?

On, that's easy: They're not.

Truly asynchronous CPUs are rare, for a few reasons. One of them is that you can't (currently) prototype asynchronous logic on a FPGA, and it's much harder to express in Verilog or VHDL than synchronous logic.

Having said that, it is easier to implement a RISC pipeline in asynchronous logic than a CISC pipeline (e.g. Sproull's Counterflow Pipeline). However, event his is a bit misleading because the boundary between RISC and CISC is quite fuzzy these days. Most modern CISC CPUs use RISC cores internally, and dynamically translate the CISC instruction stream into RISC code. The main reason for this is that the same features which make RISC attractive (e.g. fixed-size instructions which can be buffered) are also the ones which make superscalar execution work.

So to the extent that asynchronous logic works, modern CISC CPUs can benefit almost as much as RISC CPUs can.


One rational interval function and one irrational, will they ever collide? This question may be a little mathy or hardware-y, so I may have to ask elsewhere.

I've recently learned that if a is a positive rational number and b is a positive irrational number, there exists no common multiple between the two.

A common design consideration in threaded or embedded systems is concurrency control, when two functions or threads share resources.

So if function A runs every sqrt(2) seconds, and function B runs every 1 second, they will never run at the same time.

Is it somehow possible to use very accurate measured numbers, to make this possible? Or is it possible using exact/symbolic programs/tools? Or is it not possible at all in machine/computer computational formats?!

Could you make a theoretical device that could measure an irrational number of seconds? Maybe, but that would be impossibly hard. In the real world the computers clock, which runs the scheduler, is made out of a vibrating piece of quartz creating the ticks. This is vibrating at a few billion times per second. You will never get resolution of time between the vibrations so it provides us with an implicit limit on how accurately we can measure time.


Under what kind of oracles are $P$ and $NP$ equivalent? How strong have the oracles needed to be for these two classes to be proven equivalent with respect to them?

For instance: is $P^H$ = $NP^H$ (ie. is $P$ equipped with an oracle to solve the halting problem equivalent to $NP$ equipped with an oracle to solve the halting problem)?

From Theodore Baker, John Gill, and Robert Solovay. Relativization of the P=?NP problem. Siam Journal of Computing, 4:432-442, 1975 [219] we know $NP^A =P^A$ for their oracle A (which is a decision algorithm for a PSPACE complete problem).

If the oracle can perform an infinite amount of computation and return back the result in one step are these classes equal with respect to an oracle of this type? How about weaker ones? What is the weakest oracle we know of where $P$ and $NP$ are equal with respect to it?

An answer I'm looking for is something like: $P^O$=$NP^O$ with respect to an oracle O and any oracle more powerful than it.

It's not about strength: the Baker-Gill-Solovay nonrelativization result relativizes (hehehe), in the sense that

for every $A$ there is a $B\ge_p A$ such that $\mathsf{P}^B\not=\mathsf{NP}^B$, and

for every $A$ there is a $B\ge_p A$ such that $\mathsf{P}^B=\mathsf{NP}^B$.

What matters more - or at least, what matters more in a way we can understand - is the genericity/randomness properties of the oracle. Specifically, the set of oracles with respect to which $\mathsf{P}\not=\mathsf{NP}$ has full measure, which is to say that $\mathsf{P}^A\not=\mathsf{NP}^A$ whenever $A$ is "sufficiently random." If I recall correctly, the same is true for genericity: the set of oracles with respect to which $\mathsf{P}\not=\mathsf{NP}$ is comeager, which is to say that $\mathsf{P}^A\not=\mathsf{NP}^A$ whenever $A$ is "sufficiently generic." Both of these notions can be made precise. For a concrete example, Chaitin's constant and its relativizations are sufficiently random to separate $\mathsf{P}$ and $\mathsf{NP}$.

So what about the halting problem specifically? Well, the exact structure of the halting problem is rather dependent on the way we choose to enumerate Turing machines, and we can in fact whip up an "appropriate" enumeration whose associated halting problem goes whichever way we desire. So I suspect that it's hard to say anything here.

This leaves open the question of how weak we can make an oracle with respect to which we have $\mathsf{P}=\mathsf{NP}$ (or $\mathsf{P}\not=\mathsf{NP}$ for that matter). The Baker-Gill-Solovay argument gives us the non-highness result that for any non-polytime-computable $A$ we can find $B,C$ to which $A$ is not polytime-reduciblesuch that $\mathsf{P}^B=\mathsf{NP}^B$ and $\mathsf{P}^C\not=\mathsf{NP}^C$. (Incidentally, note that "high" and "low" are technical terms which I'm misusing here. I'm rude like that.)

Now the above isn't as satisfying as one might hope since the $\le_p$-degrees are rather "spread out." We might hope for some results "closer to home." For example, in an earlier edit I suggested examining the behavior of minimal degrees with respect to polynomial-time $m$-reducibility, where "minimal" means "nonzero but not strictly above any nonzero degree" (while this clashes with the standard order-theoretic meaning, it is standard in computability theory). I just realized that this is vacuous: there are no minimal polynomial-time degrees, with respect to either $m$- or $T$-reductions, at all! This was proved by Homer, following a result of Ladner.
Just to wrap up this coda, Homer subsequently observed (and this was followed up by Ambos-Spies) that things are less trivial with respect to so-called honest reductions; honesty is a bit technical, but the basic idea is to rule out situations where disproportionately much of the information about a set is concentrated in a small region of the oracle computing it. It turns out that there is a tentative connection between minimal degrees with respect to honest polynomial reductions and the $\mathsf{P=NP}$-problem. To my understanding this turned out to be a red herring, but it's still very neat!


Arthur-Merlin protocol I recently learned about the Arthur-Merlin protocol, and we defined the complexity classes $AM,MA$.
We have also seen that there exists a theorem stating that $AMAMAM...AM=AM$, however we have not formally defined $AMAMAMAM...AM$.
We did give a brief definition for it as a protocol, but i would like to see a formal definition without protocols, just like $AM$ and $MA$ (and $MAM$)
A definition for $AMA$ should suffice for me, just to get the hang of how it should look.
Thanks!

$AMA$ is basically a 3-round interactive proof system where the verifier (Arthur) is only allowed to send randomness to the prover (Merlin).
I haven't seen such an explicit definition yet, but I think we can formulate it as follows.
The first round of AM[3] starts with Merlin sending a message $m_1$ to Arthur. In the second round, Arthur sends randomness $r$ to Merlin, which is followed by the final third round in which Merlin sends a message $m_2$. Arthur then decides to accept/reject using deterministic polynomial-time verifier $V$.
I think we can define the class as follows.
Definition: $L ∈ AMA$ if there exists a poly-time deterministic algorithm $V$ such that:

If $x \in L \;(|x| = n)$ then $\exists P. Pr_{r \in \{0,1\}^{p(n)}} \left( V(x, m_1, r, m_2) = 1 \right) \ge 2/3$ where $\; m_1 = P(x),\;
m_2 = P(x, r)$
If $x \notin L \;(|x| = n)$ then $\forall P. Pr_{r \in \{0,1\}^{p(n)}} \left( V(x, m_1, r, m_2) = 1 \right) \le 1/3$ where $\; m_1 = P(x),\;
m_2 = P(x, r)$

Note the prover $P$ is a function $P: \{0,1\}^* \rightarrow \{0,1\}^{q(n)}$, where $q(n)$ is a polynomial.
See: Computational Complxity by Arora-Barak's section 8.1.


Is there a reversible transform that reduces the number of distinct values? The idea is to take a sequence like $\langle 1,2,3,4 \rangle$ and reduce it to something like $\langle 1,2,2,3 \rangle$, or something similar. The key point is that there are fewer distinct values $\{1,2,3\}$ vs $\{1,2,3,4\}$. In the case that the number of distinct values cannot be reduced, i.e. $\langle 0,0,0,0 \rangle$, it would output the same value $\langle 0,0,0,0 \rangle$. An algorithm that doesn't always decrease the number of distinct values is ok, as long as it doesn't increase the number of distinct values, or as long as it does so only rarely. The output sequence length can be less than or equal to the input sequence length, and the input sequence is bounded by $[0,255]$, but the output sequence need not be, though they should be integers in the range $(-\infty,+\infty)$. Another restriction on the input, if it helps at all, is that it's a restricted growth string. A property of restricted growth strings that might be useful is that the first $0$ in the sequence always comes before the first $1$, the first $1$ before the first $2$, and so on. So a valid sequence might look something like $\langle 0,0,1,0,2,1,1,0,2 \rangle$.

As an example, consider this simple algorithm. First, construct a "dictionary" from the input sequence consisting of all distinct values in the input. So, for the input sequence $\langle 1,2,2,3 \rangle$, the dictionary would be $\langle 1,2,3 \rangle$. It then iterates over the input, doing two things: replacing the input value with its position in the dictionary, and rotating the dictionary left by one. For most inputs, this will do little to reduce the number of distinct values, but for the input sequence $\langle 1,2,3,4 \rangle$, it will output $\langle 0,0,0,0 \rangle$. This can be inverted by applying a similar algorithm. Starting with the same dictionary, iterate over the output, successively replacing the values in the output with the value in the dictionary at that output value's index (that is, if $D$ is our dictionary and $i$ is a value in our output sequence, replace that value with $D_i$) and then rotate the dictionary to the left by one.

There are many reversible transformations that take a list of (let's say) non-negative integers and output a single integer. Here are two examples:
$$
2^{a_1} \cdot 3^{a_2} \cdot 5^{a_3} \cdot 7^{a_4} \cdot 11^{a_5} \cdots \\
\langle a_1, \langle a_2, \langle a_3, \ldots, \langle a_{n-1}, a_n \rangle \cdots \rangle, \quad \langle a,b \rangle = \binom{a+b+1}{2} + a.
$$


Reduce ATM to the language of TM encodings concatenated by a string where the TM accepts both the string and its reverse Prove that the language $LM =\{\langle M,x\rangle\mid \ M \text{ accepts }x\text{ and rev}(x) \}$, where $\mathrm{rev}(x)$ is the reverse of the string $x$, is undecidable with a reduction from $A_{\mathrm{TM}}$. Note that the empty string belongs to $LM$.

Hint
Forget the similarity between $LM$ and $A_{\mathrm{TM}}$, and for an input $\langle M,x\rangle$ of the reduction, try to build a new TM $N$ such that $M$ accepts $x$ if and only if $N$ accepts $0$, i.e. $\langle N,0\rangle\in LM$.
Complete answer

 Given $\langle M,x\rangle$, build a TM $N_{M,x}$ that on any input always simulates $M$ on $x$. Therefore if $M$ accepts $x$, $N_{M,x}$ accepts everything, otherwise $N_{M,x}$ rejects anything. Now we can see $M$ accepts $x$ if and only if $N_{M,x}$ accepts $0$, i.e. $\langle N_{M,x},0\rangle\in LM$. All above completes the reduction.


Subtree with minimum sum of nodes' costs Let's consider a tree with root $r$ ( not necessary binary) and to each node $i$ we associate a cost $\sigma(i)$ that can be negative, positive or zero. We want to select the set of nodes that minimize $\sum_i \sigma(i)$. Of course, the problem until now is easy :

If there are only non-negative costs the solution is the empty set.
If there are some non-positive costs, we select them all.

But, there is an additional constraint that states: "if a node $\sigma(i)$ is selected, its predecessor to the root is also selected.  Thus we are looking for the set of nodes that grow upward to the root and that minimize that sum, or equivalently, we are looking at a subtree of root $r$ that minimize that sum.

My question is how to design an algorithm that solves this problem and how to prove its correctness and compute its complexity?

(I have a hint that states that we could do some bottom-up traversal, of the tree but I don't know how to use this information)

Any help will be appreciated.
Thanks

For a node $i$ with children $j_1,\ldots,j_d$, let us denote the best solution for the subtree rooted at $i$ by $\tau(i)$; you're interested in $\tau(r)$, where $r$ is the root. The function $\tau$ satisfies the recurrence
$$
\tau(i) = \min(0,  \sigma(i) + \tau(j_1) + \cdots + \tau(j_d)).
$$
Indeed, there are two cases to consider. Either we take no vertex, in which the answer is 0. Otherwise, we must take $i$ itself (by the constraint), and then we should take the best solutions for the subtrees rooted at all children of $i$.

Like all such recurrences on trees, this one can be evaluated in linear time in many ways.


Is a Turing Machine that only takes strings of the form $0^*$ Turing Complete? You have a Turing machine that only processes input on the form $0^*$. If it is given an input without 0's, it will simply halt without accepting or do anything else. Is it Turing Complete?

The set $0^*$ is countably infinite, since you can make the bijective function $f(x) : 0^* → \mathbb{N} $:

$f(x) = length(x)$

Where $length(x)$ is the length of the string (so you treat them as Peano Numbers).

I understand that the set of all programs (the programs that a Turing machine can run) are countable, and that the set of a Turing machines are also countable. But, can the set of string that the Turing machine can process (with no guarantees of halting) only be countably infinite (as in this case), or does it have to be uncountable?

My understanding of undecidable problems with regards to Turing machines is that they arise because there are languages that have a cardinality strictly greater than the natural numbers, e.g. $B^*$, where $B = \{0,1\}$, which has a cardinality equal to the real numbers. It seems to me that, although you can encode any integer with the language $0^*$, you can't encode an arbitrary language. The problem is: how can you encode recursively enumerable languages when all you have is unary notation? If this is indeed impossible (though I have a feeling it is possible; I can't see how the representation of numbers should be a fundamental hindrance), then it turns out that this particular Turing machine is not Turing Complete (or maybe you would say that it is not really a Turing machine).

It looks like Turing machines remain Turing-complete when the alphabet is restricted to have one symbol, $0$. First, preprocess your input by replacing every $0$ with $0\square$, where $\square$ is the blank symbol. Now, you can simulate a 2-symbol alphabet by using $0\square$ to represent zero and $\square0$ to represent one.

  My understanding of undecidable problems with regards to Turing machines is that they arise because there are languages that have a cardinality strictly greater than the natural numbers

This is incorrect. A language is, by definition, a set of finite strings and there are only countably many finite strings over any finite alphabet (proof: you get a bijection with the natural numbers by treating each string as a number written in base-$k$, where $k$ is the size of the alphabet). However, there are uncountably many different languages and that observation along with the countability of the set of Turing machines lets you deduce that there must be some undecidable langauges.

  It seems to me that, although you can encode any integer with the language 0∗, you can't encode an arbitrary language.

This is also incorrect. You can encode any natural number $n$ with the single string $0^n$ and, therefore, you can code any set of natural numbers with a unary language, i.e., a subset of $0^*$.  And you can code any set of natural numbers as a language. You can also code any language over an alphabet of size $k>1$ by using the base-$k$ trick I described above.


How does a transition function behave in a FSM when an input is not recognized (i.e. the input is not contained in the alphabet)? In Sipser's Introduction to the Theory of Computation, the provided proof for the union operation being closed for regular languages has a step for the transition function that I find a bit lacking.
Assuming that $M_1=(Q_1, \Sigma, \delta_1, q_1, F_1)$ and $M_2=(Q_2, \Sigma, \delta_2, q_2, F_2)$  are two different FSMs for languages $L_1$ and $L_2$. With $M=(Q, \Sigma, \delta, q_0, F)$ being the FSM for $L = L_1 \cup L_2$ (the regular languages for the FSMs).  The step for the constructed transition function, $\delta$, states that for each $(r_1,r_2) \in Q$ and each $a \in \Sigma$, let $\delta((r_1,r_2),a)=(\delta_1(r_1,a),\delta_2(r_2,a))$. This is working with the assumption that the input alphabet, $\Sigma$, is the same for $M_1$ and $M_2$.
I am confused on how $\delta((r_1,r_2),a)=(\delta_1(r_1,a),\delta_2(r_2,a))$ behaves for a combined alphabet $\Sigma = \Sigma_1 \cup \Sigma_2$, specifically if $a \in \Sigma_1$ and $a \notin \Sigma_2$? What would the output of $\delta_2(r_2,a)$ be and how would this transition work in the FSMs $M_2$ and $M$?

In my copy of the book, third edition, this is Theorem 1.25. From its proof, I quote:

The theorem remains true if they have different alphabets, $\Sigma_1$
and $\Sigma_2$. We would then modify the proof to let $\Sigma = \Sigma_1\cup \Sigma_2$.

What is suggested here is that in advance we assume the two alphabets to be equal, i.e., before we start the product construction. So we have to transform the original automaton $M_1$ with alphabet $\Sigma_1$ into an equivalent automaton $M_1'$ with alphabet $\Sigma_1\cup \Sigma_2$ accepting the same language. As you observe automata here are deterministic, i.e., have a transition function $\delta:Q\times \Sigma\to Q$.
The easiest way for the construction of $M_1'$ is extending the transition function for letters outside $\Sigma_1$. Any such letter should lead to not accepted computations. This can be done by adding a new garbage (or failure state) where all letters from $\Sigma_2\setminus \Sigma_1$ are mapped to.


Time complexity of 8-queen, by placeing one by one without attack I am new to artificial intelligence. I have been trying to analyse the time complexity of 8-queen, by placing one by one without attack.

One approach to achieve goal state is to "add a queen to any square in the leftmost empty column such that it is not attacked by any other queen". And this approach will have a state space of 2057 (also wondering: How to compute this?)

What is the time complexity if I am using Depth First search algorithm (which I think is the most suitable one)? How about the space complexity?

I am puzzled because the brunching of the search tree is reducing greatly when goes deep. $O(8^8)$ looks too much for time complexity, even for worst case.

Let's tackle your questions one by one:

State space: I have no idea where you got this number from. The state space is ostensibly $\binom{64}{8} \approx 2^{48}/8! \approx 2^{32}$.
Your approach: What backtracking is involved here? Your algorithm as stated could either succeed or not, but it will do so very fast.
Time complexity: It is in general difficult to estimate the time it takes a backtracking algorithm to find a solution. You can try to estimate the total time it takes to go over the entire space in various ways, for example you can estimate the branching factor at each step.
Space complexity: Backtracking algorithms have very small space complexity. You're basically keeping track of one partial solution.
The estimate $O(8^8)$: Actually $8^8 = 2^{24}$ is very small. You can probably go over this search space in under a second on a modern computer.


EXTRACT MIN algorithm for Young tableau This are two sections from a task I got.

  The Young tableau is defined as a matrix of m rows on n columns so that
  the bars in each row are sorted in ascending order Left to right and
  the elements in each column are sorted in ascending order from top to
  bottom. Some of the elements in the Young tableau may be $\infty$ we
  will refer to these elements as non-existent elements . Therefore, the
  Young tableau can be used to hold finite numbers.

  Write an algorithm for EXTRACT-MIN on a non-empty Young tableau of m at n in time running  $O(n+m)$
  Show how to insert a new element into a non-complete Young tableau v at the size of m at n in time running  $O(m+n)$

That's what I tried:

When I remove the element at the $(1,1)$ I need to move every element in the table 1 step left (and if the col is 1 so move one row up and put it on the last col) so I can solve it on $O(n*m)$. I think that $O(m+n)$ actually measn $O(max(m,n))$

Regarding the second clause I was thinking to compare the element to insert with the element in the first col in every row until until we get to bigger one and then and then check on this row where to insert it. But again let's say that I want to insert element which will be the min on the new table, so I need to push all the elements one stop left and it takes $O(m*n)$

Hint: For EXTRACT-MIN, instead of thinking in terms of shifting rows/columns, try to replace the element at $(1,1)$ by $+\infty$. Now you just want to swap $+\infty$ with one of his neighbour until you get the invariant of a Young tableau. How can you decide where to move it?


How is the right, root, left order traversal called in a binary search tree? In a Binary Search Tree you have the following orders for traversal:

Left, Root, Right is called Inorder (or ascending order).

Root, Left, Right is called Preorder.

Left, Right, Root is called PostOrder.

But how is Right, Root, Left (or descending order) called?

As per wikipedia (Tree Traversal), it is called Out-order traversal

Though, you could also find reference to reverse in-order traversal, which means the same.


Why does the app I downloaded say that 1 in binary is 00110001? I've just started learning binary so mind me if I'm bad at this. I think that the binary for 1 ought to be just "1" but, when I key it in to an app I downloaded, the answer has extra 0s and 11s in it. Why?

The app you have converts strings in the ASCII character set to their binary representation.  This representation assigns eight bits for each character in the string. For example, the word "cat" is composed of characters number 99, 97 and 116, which is 01100011 01100001 01110100.

What your app is doing is converting the string "1" into its binary ASCII representation. "1" is character number 49 in ASCII, which is 00110001, and it's pure coincidence that this ends in a 1.

You're completely correct that, as a number, 1 in decimal is 1 in binary.


Is a language that sits between two regular languages also regular? Suppose that L0, L1, L2 are languages over the same alphabet and that

L0 ⊆ L1 ⊆ L2.

Is it true that if L0 and L2 are regular, then L1 must be regular as well?

By regular = the set of words accepted by a finite automaton.

Suppose

L0 = { $a^{\textrm{n}}$ | n = 2}

L2 = { $a^{\textrm{n}}$ | n => 0}

how can i find a set for L1 that is NOT Regular when there are no parameters or syntax on what the machine accepts or not?

I'm thinking

L1 = { $a^{\textrm{n}}$ | n = prime number }

but I'm not sure how to start proving it

Any time you're asked questions like "Is a subset of a regular language always regular?" or "Is a superset of a regular language always regular?", you have the best chance if you pick the biggest possible language to take subsets of, and the smallest possible language to take supersets of. Thankfully, the biggest possible and smallest possible languages are both regular.


Decidability of language L = { n : ∃x∈N, n = 3x+2 } I've recently came across this language and I don't know if my hint for proving its class is correct or not.

$$L = \{ n : \exists x \in N, \,n=3x+2 \} $$$n$ is in binary format.

I think $L$ is decidable and as proof I was considering using a canonical enumerator of $\{0,1\}^*$.

For each word $x$ printed by the enumerator, my algorithm would compute $3x+2$ and halt if the result was equal or greater to the provided input.
If equal, then accept, if greater, then reject.

I would like someone to confirm if I'm correct, pointing me in the right direction if I'm not.

Yes, your approach is correct.

The description of your algorithm would be clearer if it also mentions the following.

The algorithm rejects the empty word immediately.
That canonical enumerator of $\{0,1\}^∗$ enumerates all positive integers in increasing order.
If $3x+2$ is smaller than the input then the result will be ignored and the enumerator will keep going.

Another algorithm that decides the language would be subtracting 3 from the input number and checking the result repeatedly. If the result is 2, it accepts. If the result is negative, it rejects. It also rejects the the empty word immediately.


baz_num_elts exercise from Software Foundations I'm at the following exercise in Software Foundations:

(** **** Exercise: 2 stars (baz_num_elts) *)
(** Consider the following inductive definition: *)

Inductive baz : Type :=
   | x : baz -> baz
   | y : baz -> bool -> baz.

(** How _many_ elements does the type [baz] have?
(* FILL IN HERE *)
[] *)

All of the answers I've seen on the Internet say that the answer is 2, and that the elements are x and y. If that's the case, then it's not clear to me what is meant by elements. There are certainly two constructors, but it's impossible to actually create a value of type baz.

It's impossible to create a value of type baz because x has type baz -> baz. y has type baz -> bool -> baz. In order to get a value of type baz we need to pass a value of type baz to either x or y. We can't get a value of type baz without already having a value of type baz.

So far I've been interpreting elements to mean values. So (cons nat 1 nil) and (cons nat 1 (cons nat 2 nil)) would both be elements of type list nat and there would be an infinite number of elements of type list nat. There would be two elements of type bool, which are true and false. Under this interpretation, I would argue that there are zero elements of type baz.

Am I correct, or can someone explain what I'm misunderstanding?

I agree with you. There's a bijection between baz and False.

Definition injective : forall {t1 t2}, (t1 -> t2) -> Prop := fun t1 t2 f1 => forall x1 x2, f1 x1 = f1 x2 -> x1 = x2.

Definition surjective : forall {t1 t2}, (t1 -> t2) -> Prop := fun t1 t2 f1 => forall x1, exists x2, f1 x2 = x1.

Definition bijective : forall {t1 t2}, (t1 -> t2) -> Prop := fun t1 t2 f1 => injective f1 /\ surjective f1.

Inductive baz : Type :=
   | x : baz -> baz
   | y : baz -> bool -> baz.

Theorem baz_False : baz -> False. Proof. induction 1; firstorder. Qed.

Goal exists f1 : baz -> False, bijective f1.
Proof.
exists baz_False. unfold bijective, injective, surjective. firstorder.
assert (H2 := baz_False x1). firstorder.
assert (H2 := x1). firstorder.
Qed.


How can you modify a SUBSET-SUM instance so evaluating a set outputs either 0 or 1? An SUBSET-SUM instance is a list of $n$ integers $\{ a_1, a_2,... a_n\}$. To evaluate a subset is to output the sum of a subset.
However, I want to know, is it possible to create a new instance $T$, the same size as the original set $S$, that any subset in $S$ that evaluates to $W$, the corresponding subset in $T$ (the numbers taken from the same positions) evaluates to $0$? All other subsets in $T$ should evaluate to $1$.
Bonus: Give a list of other NP-complete problems (other than 3SAT, where you evaluate a formula that either outputs $0$ or $1$ depending on the set of binary variables being passed into it), where evaluating an analogous instance outputs $0$ if it satisfies some objective related to the problem and $1$ otherwise.

However, I want to know, is it possible to create a new instance T, the same size as the original set S, that any subset in S that evaluates to W, the corresponding subset in T (the numbers taken from the same positions) evaluates to 0? All other subsets in T should evaluate to 1.

No, this is impossible. Consider $S=\{1,2,3\}$ and $W=3$. Our set $T$ should be $\{a,b,c\}$ such that $a+b=0, c=0$ and $a+b+c=1$.


Is there a way a proving a language regular/non-regular that works for every possible language? In my theory of computing class, we've been talking about how to prove languages regular and non-regular. I've heard of methods like the pumping lemma and Kolmogorov complexity to prove languages non-regular, while proving languages regular revolves around building a DFA, or using the Myhill-Nerode theorem. All of these approaches fail for some language. Is there some approach that will work for all regular/non-regular languages?

No, there isn't. It is undecidable, even for context-free languages. It is decidable for deterministic context-free languages.

References are easy to find with Google; for instance,

Undecidable Problems for Context-free Grammars, by Hendrik Jan Hoogeboom
Deciding whether a context-free language is regular [closed], on the Theoretical Computer Science Stack Exchange, in which user babou lists

A regularity test for pushdown machines,  R.E. Stearns, Information and Control, 1967 (full text by clicking on the page)
Regularity and Related Problems for Deterministic Pushdown Automata, Leslie G. Valiant, JACM 1975


Is there a discipline studying the prioritizing of repeated tasks? Sorting algorithms have a huge literature behind them, and the algorithm I'm planning has some similarities to the topic, but I couldn't even find the correct search terms to know whether a field exists which studies such algorithms.
Imagine the following problem: there is a serial communication channel of a very low throughput, and you have to communicate with a number of devices through it. If all devices had the same priority, the solution would be obvious:
A B C D A B C D A B C D A ...

(In case of 4 devices, where "A" means "communicate with device A")
However, it can happen that some devices have a lower priority, and our goal is to improve the latency of high-priority devices, that is, the time between two consecutive communications with the same device should be small.
For example, we have devices A, B, C, and D with a high priority, and devices e, f, g and h, with a lower priority.
The naive solution would be to process the lower priority devices only every second turn, or every third turn, etc. Let's call this the "skipping factor".
Example: higher-case letters are twice as important:
A B e C D f A B g C D h A B e C D f A B g C D h ...

Example: higher-case letters are three times as important:
A B C e D A B f C D A g B C D h A B C D e ...

However, this solution quickly breaks down if the number of elements in the different priority categories differ greatly.
Take the example of "capital letters are twice as important", but with 8 capital letters and 2 lower case letters:
A B i C D j E F i G H j A B i ...

Here, the lower-case letters occur more often, even though that's opposite to our goal.
A solution would be to multiply the skipping factor by the ratio of the cardinalities of the priority groups. In the above example, the ratio is 8/2 = 4, we multiply it with the skipping factor of two, and we get 8, so after every 8 capital letter there can come a lower case one.
The problem
The above examples were by far not exhaustive. Even the latest solution in the above example breaks down easily if there are more than two priority groups, and especially if the priority of the elements can change over time. This last constraint can be a very difficult one, as even "smarter" algorithms where every element has its own "timeout" counter ticking down can be fooled by cases where an element changes priority back and forth so that it never gets executed. The complexity also grows because we have to crawl through the lists of elements of every priority level on each occasion we select a new element to be sent.
The question
I have many different ways in my mind to solve this problem, but I'm afraid of trying to re-invent the wheel, and arriving to a suboptimal solution. I'm therefore looking for a field of study which works with problems such as the one listed above. Does it have a name? Does it have a literature? I tried searching some terminology I guessed relevant for the topic, but I couldn't find anything.

By far the simplest solution is probabilistic. Let's suppose you have $k$ classes, and their relative importance is $c_1,\ldots,c_k$. Let's also suppose that there are $N_i$ objects in class $i$. You want the frequency of appearances of each symbol in class $i$ to be proportional to $c_i$.

Let $P = \sum_i c_i N_i$ and $p_i = c_i N_i/P$. At each step, choose class $i$ with probability $p_i$, and output a random element from the class. The probability that a specific element from class $i$ appears is $p_i/N_i = c_i/P \propto c_i$.

To increase fairness among class $i$, instead of outputting a random element, you can keep a counter for each class (counting modulo $N_i$), incremented any time the class is chosen, and output the corresponding element from the class.

A similar approach should work for fairness across classes, but here it's not as straightforward so I'll leave it to you.


Is my formal definition of programming language correct? I found this formal definition of a programming language in the 1973 paper Formal definition of programming languages by Terrence Pratt.

  PL is a formal language endowed with two structures: a translator and
  an abstract machine.

  Translator defines a mapping from program strings, as defined by BNF
  grammar, into a representation of programs as hierarchies of directed
  graphs.

  Abstract machine is a mathematical model of computation.

Is it an appropriate and full definition? Do you have another?

It is certainly not a full definition; one might reasonably expect a "real" programming language to have not merely an abstract mathematical model defining the language's semantics, but also a concrete implementation of a compiler or an interpreter which runs on an actual computer. Then again, one might reasonably not expect this. Is lambda calculus, for example, a programming language? Wikipedia doesn't define it as one, but if somebody else does then I can't say they are wrong.

There are many aspects of what makes a language a "programming language"; reasonable people might disagree on whether a certain aspect (say, Turing completeness) is strictly necessary for something to count as a true programming language. It is unlikely that any list of such aspects would ever be agreed by all computer scientists, or even just the academic computer science community, to be both correct and complete.

The concept of a "programming language" is not in the same category as mathematical concepts such as "group". It is possible for a formal definition of a group to be correct or incorrect, but a formal definition of a programming language can merely be useful or not useful (or, more useful or less useful) relative to the use at hand. Presumably, the definition you quoted was useful for the author of the paper you found it in.


What is the complexity of multiplying a matrix by a scalar? I would like to know the complexity of multiplying a matrix of $n\times m$ size by a scalar $\alpha$?

In fact, I have a directed graph $G=(V,E)$ represented by an incidence matrix $M$. I would like to calculate the transpose of this graph, i.e., inverse the directions of the edges. I think that if I multiply $M$ by $-1$ I will get the transposed graph. Am I right?

If I am right, what is the complexity of multiplying a matrix by a scalar?
If I am not, where is my mistake and what is the complexity of multiplying a matrix by a scalar anyway?

I think the complexity is $\Theta(n\cdot m)$.

Thanks.

In general, if you have an $n\times m$ matrix $A=(a_{i,j})$ with $1\le i\le n$ and $1\le j\le m$ then there will be $nm$ entries in the array. To multiply $A$ by a scalar $c$ you multiply each element by c, which (assuming multiplication can be done in constant time) will take $nm$ multiplications. That's not the way to go, though, if $A$ is the adjacency matrix of a directed graph.

For your peoblem, if $A$ is the adjacency matrix of a digraph $G$ on $n$ vertices, then $A$ will be an $n\times n$ matrix $(a_{i, j})$ with $a_{i,j}=1$ when there is a directed edge $e=(i, j)$ from vertex $i$ to vertex $j$ and $a_{i,j}=0$ otherwise. You correctly note that the reversed graph $G'$ will have an adjacency matrix $B=(b_{i,j})$ which is the transpose of $A$, so we'll have $b_{i, j} = a_{j, i}$, since $G'$ will have an edge from vertex $v_i$ to vertex $v_j$ if and only if $G$ has an edge from $v_j$ to $v_i$. To get the transpose of $A$, then, we'll swap $a_{i, j}\leftrightarrow a_{j, i}$ entries of $A$. There will be $n(n-1)/2$ swaps needed, since we swap every element above the main diagonal with its corresponding entry below the main diagonal.

Note that multiplying $A$ by $-1$ won't work, since the entries of an adjacency matrix must be only $1$ or $0$.


How to calculate the depth of sorting networks? I have trouble understanding how to calculate the depth of a sorting network on $n$ inputs.

For example, in case of selection sort, we have:

$\qquad \displaystyle D(n)=D(n-1)+2\\\qquad D(2)=1$

which leads to

$\qquad \displaystyle D(n)=2n-3=\Theta(n)$

I have confirmed that the depth of selection sort is equal to $2n-3$ by hand, but I can't understand how the recurrence $D(n)=D(n-1)+2$ is derived.

For selection/bubble sorting network algorithms, the main tricky point is that "some operations are overlapped" or in other words because of pipeling! (it is shown in figure below)
You can find more information in these lecture notes by Rolf Karlsson.

This is the reason why the time complexity is linear!


Why is $3^n = 2^{O(n)}$ true? $3^n = 2^{O(n)}$ is apparently true. I thought that it was false though because $3^n$ grows faster than any exponential function with a base of 2.

How is $3^n = 2^{O(n)}$ true?

With some algebra (and changing the constant in the $O(n)$), we can actually change the bases.

$$3^n = (2^{\log_2 3})^n = 2^{n\log_2 3}$$

Since $\log_2 3$ is a constant, $n\log_2 3 = O(n)$.  So $3^n = 2^{O(n)}$.

I'm not sure what you mean by "$3^n$ grows faster than any exponential function with a base of 2."   $2^n = o(3^n)$ of course but it seems you mean something more general.  My guess is that your statement applies to something like $O(3^n)$, where you multiply the base by a constant, as opposed to $2^{O(n)}$ where you multiply the number in the exponent by a constant.


Binary Search Tree Traversals I have a clue as to how this code/traversals work but I'm still confused.

For example, in the first traversal (Preorder), it prints 31, 12, 25 but then it backtracks all the way to 68? How does it know to do this? My professor referenced a stack but I am still a bit confused.

As for the other codes, I don't know how to backtrack on them at all. I understand the first one quite a bit but for the next 2, not so much.

The rules for traversing a tree are, to visit all nodes of a tree you do this:

Preorder: (1) visit the root node, then (2) visit all the nodes in the left subtree of the root, then (3) visit all the nodes in the right subtree of the root. In steps (2) and (3), use the same rule as above.
Inorder: (1) visit all the nodes in the left subtree, (2) visit the root node, (3) visit all the nodes in the right subtree.
Postorder: (1) visit all the nodes in the left subtree, (2) visit all the nodes in the right subtree, (3) visit the root.

For example, to do an inorder traversal of your tree,

Visit the nodes, $(12, 25)$, in the left subtree.
Visit the root, $31$.
Visit the node in the right subtree, $(68,50,72,39,56,42,53,60)$

In step (1) we use the same rule: visit the left subtree of 12 (nothing there), then the root, 12, then the right subtree $(25)$. So now you've done task (1), having visited the nodes $12, 25$ in that order.

In step (2) we visit $(31)$, so now we've visited $12,25, 31$.

In step (3) we need to visit the nodes in the right subtree, using the rule Left-Root-Right, as we did before. It turns out that we'll visit the right subtree's nodes in order 39,42,50,53,56,60,72.

Doing this traversal by hand is complicated and prone to error. While computers are easily able to use these recursive rules, humans aren't so good at this. Fortunately, there's a three-step technique that's easy for people to apply.

Draw an upward-pointing triangle around each node in your tree.
"Shrink-wrap" the whole tree by drawing a closed circuit around the whole tree, making your circuit follow the tree as closely as possible, like this:

Starting at the root node, trace the circuit counter-clockwise, listing a node as visited when: for a preorder traversal, you encounter the node for the first time (that is, when you travel along the left side of the node's triangle); for an inorder traversal, mark the node as visited when you encounter the node for the second time (that is, when you travel around the base of the node's triangle); for a postorder traversal, mark the node as visited when you encounter it for the last time (when you travel along the right side of the node's triangle).

Try it for your tree and each of the three traversals and you'll see what happens.


How strong is an oracle that avoid don't-halt Consider such an oracle:

  Given a turing machine[1], return the halting state it falls on, or arbitary result(but don't stuck in) if the TM doesn't halt.

How strong is a TM with the oracle?
Can the oracle exist(or does the question always have an answer) if change [1] into a TM with the oracle?

Some results I get:

It's as strong as a TM with oracle that compare running time of two programs, or arbitary returned value if both don't halt.
If the oracle returns integer the TM returns(may need to define a way it outputs integer), or arbitary integer if it doesn't halt, we can solve the halting problem by getting the runtime and check. However, currently I can't output from the oracle a string of any finite length if the length can be arbitary long, promising it's finite.

(Moved to here)

EDIT: I made a deeply silly mistake in my previous answer. Below what I've done is answered the question, then explained how two variations of the question - which I originally conflated with the actual question - yield a very different answer.

An oracle of the type you describe computes the halting problem (and conversely every oracle computing the halting problem computes an oracle of your type).

Suppose $x$ computes the halting problem. Without loss of generality, we may take $x$ to literally be the halting problem. Then we can compute an $f$ as desired by simply taking an input $e$, asking $x$ whether $T_e(e)$ halts, and (i) if the answer is no, halt and output $0$ and (ii) if the answer is yes, run $T_e$ until it halts and output the result.
Conversely, suppose $f$ has the desired property. There is a total computable function $h$ such that for all $e$ if $T_e(e)$ halts, then $T_{h(e)}(h(e))$ halts and gives the runtime of $T_e(e)$. Now to tell whether $T_e(e)$ halts we simply run $T_e(e)$ for $f(h(e))$-many steps.

Now there are a couple natural variations to the above notion:

What if we demand inequality instead of equality?
What if we restrict attention to machines with binary output?

Both of these variations prevent the argument above from working, the former by preventing us from representing runtimes as outputs and the latter by preventing us from coding literally anything into the output.

It turns out that these notions yield a much weaker complexity class: namely the PA degrees. The original definition was that something is of PA degree if it computes a complete consistent extension of Peano arithmetic (which by Godel must be non-computable), but there are many equivalent definitions. Generally the simplest to work with is:

  A degree ${\bf a}$ is PA iff whenever $X$ is an infinite computable binary tree, ${\bf a}$ computes an infinite path through $X$.

PA degrees can be quite weak, computability-theoretically. While no PA degree is computable, they don't have to compute the halting problem: there are PA degrees incomparable with the halting problem, and there are PA degrees strictly weaker than the halting problem (where strength here is measured by Turing reducibility).

Re: relativization, the answer is no: the proof of the incomputability of all PA degrees relativizes, so no oracle is PA over itself.


The meaning and relevance of the locution ''no terminating implementation'' in type theory In the context of a discussion of Haskell https://stackoverflow.com/questions/62509788/the-intuition-behind-the-definition-of-the-co-reader-monad, I was told that

There is no terminating implementation for the polymorphic type $(e \to a) \to a$

and that we couldn't have a function of type $((e \to a) \to a) \to e$ or a function of type $(r \to x) \to x$, for these would not be ''implementable''.
These types are well formed in the STLC, in the sense that we can construct them using the rules of type-formation. And I don't see why we can't form lambda terms of this shape, such as $\lambda c_{((a \to t) \to t)}. \, b_a$, or $\lambda p_{e \to a}.\,b_a$.
What is therefore the problem? Specifically, what is a ''terminating implementation'' in the context of the STLC? I believe this relates to the fact that $(e \to \bot) \to \bot$ is not constructively equivalent to $e$, but I would appreciate if someone could spell this out for me.

You can always inhabit a type by a free variable: the type $\tau$ is inhabited by the free variable $x_\tau$. When people speak about "implementation" of a type they mean a closed term, i.e., one without free variables. The examples you gave contain free variables, namely $b_a$.
In pure simply-typed $\lambda$-calculus all terms are "terminating" in the sense that the calculus is strongly normalizing, so whatever reductions you take they will always lead to the (unique) normal form.
In $\lambda$-calculus extended with recursive definitions (such as Haskell) we can inhabit every type $\tau$ with a closed term, for instance in Haskell the type t is inhabited by a defined as
a :: t
a = a

Once we have recursive definitions, it is easy to write closed terms that do not terminate (or do not have a normal form).


What are the limitations of RNNs? For a school project, I'm planning to compare Spiking Neural Networks (SNNs) and Deep Learning recurrent neural networks, such as Long Short Term Memory (LSTMs) networks in learning a time-series. I would like to show some case where SNNs surpass LSTMs. Consequently, what are the limitations of LSTMs? Are they robust to noise? Do they require a lot of training data?

I finally finished the project. Given really short signals and a really small training set, SNNs (I used Echo State Machines and a neural form of SVM) vastly out-performed Deep Learning recurrent neural networks. However, this may be mostly because I'm really bad at training Deep Learning networks.

Specifically, SNNs performed better at classification of various signals I created. Given the following signals:

The various approaches had the following accuracy, where RC = Echo State Machine, FC-SVM = Frequency Component SVM and vRNN = Vanilla Deep Learning Recurrent Neural Network:

SNNs were also more robust to noise:

For more information, including how I desperately tried to improve the Deep Learning classification approach performance, check out my repository and the report I wrote which is where all the figures came from.

Update:
After spending some time away from this project, I think one of the reasons that RNNs do horribly at this project is that they're bad at dealing with really long signals. Had I chunked the signals together with some sort of smoothing as preprocessing, they probably would have performed better.


Is there an abstract machine that can capture power consumption? When reporting algorithmic complexity of an algorithm, one assumes the underlying computations are performed on some abstract machine (e.g. RAM) that approximates a modern CPU. Such models allow us to report time and space complexity of algorithms. Now, with the spread out of GPGPUs, one wonders whether there are well known models where one can take into account power consumption as well.

GPUs are well known to consume considerable amount of power and certain instructions fall into different categories of power consumption based on their complexity and location on the sophisticated chip. Hence instructions, from an energy of view, are not of unit (or even fixed) cost. A trivial extension would be assigning weights to operation cost, but I'm looking for a powerful model where an operation/instruction might cost non-constant units of energy, e.g. polynomial amount (or even more complex e.g.: function of time elapsed since start of the algorithm; or taking into account probability of failure of cooling system, which will heat up the chips, and slow down the clock frequency etc.)

Are there such models where non-trivial costs and faults can be incorporated?

There isn't an established model yet, but this is an area of active research right now. One of the experts on the algorithms side of things is Kirk Pruhs. His papers have more information, and you can also browse this presentation.


Why ⊢ for affirmative predicates and ⊨ for ¬negations? I read a book which says that in Predicate Calculus, syntactic theorem proving is identical (complete and sound) with semantic entailment and this is very useful because it is easier to prove positive witnesses in natural deduction whereas when you seem to fail you better switch to semantic account to demonstrate a counter-example.

Particularly Logic in computer science says

  to show that Γ  ⊢ψ is valid, we need to provide a proof of ψ from Γ.
  Yet, how can we show that ψ is not a consequence of Γ? Intuitively,
  this is harder; how can you possibly show that there is no proof of
  something? You would have to consider every ‘candidate’ proof and show
  it is not one. Thus, proof theory gives a ‘positive’ characterisation
  of the logic; it provides convincing evidence for assertions like ‘Γ
  ⊢ ψ is valid,’ but it is not very useful for establishing evidence
  for assertions of the form ‘Γ ⊢ φ is not valid.’

  Semantics, on the other hand, works in the opposite way. To show
  that ψ is not a consequence of Γ is the ‘easy’ bit: find a model in
  which all φ_i are true, but ψ isn’t. Showing that ψ is a consequence
  of Γ, on the other hand, is harder in principle. For propositional
  logic, you need to show that every valuation (an assignment of truth
  values to all atoms involved) that makes all φ_i true also makes ψ
  true. If there is a small number of valuations, this is not so bad.
  However, when we look at predicate logic, we will find that there are
  infinitely many valuations, called 'models' from hereon, to consider.
  Thus, in semantics we have a ‘negative’ characterisation of the logic.
  We find establishing assertions of the form ‘Γ ⊭ ψ’ (ψ is not a
  semantic entailment of all formulas in Γ) easier than establishing ‘Γ
  ⊨ ψ’(ψ is a semantic entailment of Γ), for in the former case we need
  only talk about one model, whereas in the latter we potentially have
  to talk about infinitely many. All this goes to show that it is
  important to study both proof theory and semantics. For example, if
  you are trying to show that ψ is not a consequence of Γ and you have a
  hard time doing that, you might want to change your strategy for a
  while by trying to prove the validity of Γ ⊢ ψ. If you find a proof,
  you know for sure that ψ is a consequence of Γ. If you can’t find a
  proof, then your attempts at proving it often provide insights which
  lead you to the construction of a counter example. The fact that proof
  theory and semantics for predicate logic are equivalent is amazing,
  but it does not stop them having separate roles in logic, each
  meriting close study.

I was sure that we can prove the opposite by proving ⊢ ¬ψ and wondered why do we need the entailment. Now I see that validity of the opposite has nothing to do with validity of affirmative statement. Thanks. What we need is the satisfaction of the ¬ψ, which says that there is a counterexample. We do not need the validity of ¬ψ. But why semantics instead of proof? Do you say that semantics is in patrimony of satisfaction whereas proof theory is dedicated to validity?

I have mistakenly thought that not being able to prove ψ means that ψ is absurd and, thus, you can prove ¬ψ. But, this seems not to be the case.

The answer is really in the first paragraph of the quoted text, so what I'm about to attempt is really a rephrasing of that.

Remember that $\Gamma \vdash \psi$ means that there exists a formal proof of $\psi$ (in the system from $\Gamma$ blah blah blah). That is, there's some way, starting from the axioms, to syntactically manipulate the symbols according to the rules of the system to end up with $\psi$.

On the other hand, $\Gamma \models \psi$ is a statement about the semantics  of the system, i.e. the interpretation of what the symbols `mean', so $\Gamma \models \psi$ when there's no interpretation that renders all of $\Gamma$ true and $\psi$ false.

So, back to the question. When we want to show that $\Gamma \vdash \psi$ is valid, a formal proof is very nice, because it has no dependence on the meaning (semantics) of the symbols, it is simply a consequence of the rules of the system. On the other hand, if we suspect $\Gamma \vdash \psi$ is not valid, it's very hard to give a formal proof - you would have to show that every possible route to a formal proof doesn't work, i.e. that no matter what potentially-very-convoluted order you apply the rules of the system in, starting from the members of $\Gamma$, you can't get to $\psi$. Just to reiterate, you would effectively have to consider every possible proof, and show that it didn't work.

Semantic entailment kind of works the other way around. To show that $\Gamma \models \psi$ is not valid, `all' we need to find is some interpretation such that everything in $\Gamma$ is true, but $\psi$ is false - i.e. we just have to find that one counterexample. Showing that $\Gamma \models \psi$ is valid is the part that requires lots of cases - we have to show that $\psi$ holds for every interpretation for which everything in $\Gamma$ also holds.


Why is the clique problem NP-complete? Possible Duplicate:
  Is the k-clique problem NP-complete?

I've been lately reading about the clique problem, specifically, the variety of the clique problem of deciding whether a given graph $G$ with $n$ nodes has a clique of at least size $k$.

Why is this problem $NP$-complete? Could one solve this problem in polynomial time by trying out each possible group of $k$ nodes in the graph and checking if this group is a clique?

Wouldn't this algorithm run in time $O(\binom{n}{k})$ or $O(\frac{n!}{(n-k)!k!})$ or $O(n^2)$?

The 3-clique problem is, given a graph, does it have a clique of size 3? This is solvable in polynomial time. Likewise, for any fixed $k$, the $k$-clique problem (given a graph, is there a clique of size $k$) is solvable in polynomial time.

But in the clique problem, we are given both the graph and $k$ and asked if there is a clique larger than size $k$. This problem is NP-Complete. For example, let's suppose someone sets $k = \frac{n}{2}$. Then the running time you give is definitely exponential.

This should make intuitive sense -- in the $k$-clique problem, if I fix $k$ to be, say 1000, ($k$ being a constant with respect to $n$.) then as graphs get really really large (like trillions of nodes), I still only have to check every set of 1000 nodes. But in the clique problem, as the graph gets really gigantic, the sets I have to check might get gigantic too.

(Edit. To finish answering the question, clique is NP-hard because for example 3SAT can be reduced to it in polynomial time, and clique is in NP. However, $k$-Clique (for any given $k$) is not NP-hard).


Does the product of two functions equal the product of their Big-O's? let's say $f(n) = O(g(n))$ and $l(n) = O(m(n))$

is it always true that $f(n) \cdot l(n) = O(g(n)) \cdot O(m(n))$ ?

By definition, $f(n) \leq c_1 \cdot g(n)$ and $l(n) \leq c_2 \cdot m(n)$, for some $c_1$ and $n \geq n_0$, and for some $c_2$ and $n \geq n_0'$ respectively. Suppose we set $n_0^* = \max (n_0, n_0')$, then both inequalities are satisfied for $n \geq n_0^*$. Then obviously $f(n) \cdot l(n) \leq c_1 \cdot g(n) \cdot c_2 \cdot m(n)$ for $n \geq n_0^*$. So indeed the claim holds. We can go take one additional step, however. Note that we can replace $c_1 \cdot c_2$ by a new constant, and thus we conclude that $f(n) \cdot l(n) = O(g(n) \cdot m(n))$.


What is known about coRL and RL? Wondering about any known relations between $\mathsf{RL}$ complexity class (one sided error with logarithmic space) and its complementary class, $\mathsf{coRL}$.

Are they the same class?

What are $\mathsf{coRL}$'s relation to $\mathsf{NL}$, $\mathsf{P}$?

By definition, $ \mathsf{RL} $ is a subset of $ \mathsf{NL} $, and so $ \mathsf{coRL} $ is a subset of $ \mathsf{coNL} $.

Since $ \mathsf{NL} = \mathsf{coNL} $, $ \mathsf{coRL} $ is also subset of $ \mathsf{NL} $.

Moreover, $ \mathsf{NL} \subseteq \mathsf{P} $.

Please also note that although it is widely believed to be true, whether $ \mathsf{RL} \subseteq \mathsf{L} $ is still an open problem, and so is whether $ \mathsf{coRL} \subseteq \mathsf{L} $. (The obviuos relation is $ \mathsf{L} \subseteq \mathsf{RL} \cap \mathsf{coRL} $.)


Pushdown automaton from given code for parsing a while statement I was preparing for my exam and have some questions that can possibly come on the test.
There is a task to make pushdown automata from a given code:

void compile_while() {
  // while ( expression )
  if (symbol == SYM_WHILE) {
    get_symbol();

    if (symbol == SYM_LPARENTHESIS) {
      get_symbol();

      compile_expression();

      if (symbol == SYM_RPARENTHESIS) {
        get_symbol();

        // zero or more statements: { statement }
        if (symbol == SYM_LBRACE) {
          get_symbol();

          while (is_not_rbrace_or_eof())
            compile_statement();

          if (symbol == SYM_RBRACE)
            get_symbol();
          else {
            syntax_error_symbol();

            exit(EXITCODE_PARSERERROR);
          }
        } else
          // only one statement without {}
          compile_statement();
      } else
        syntax_error_symbol();
    } else
      syntax_error_symbol();
  } else
    syntax_error_symbol();
}

First of all, I don't understand why we need to construct PDA for it because we can do it without stack too and second, I don't understand how the pushdown automata for it would look like.

Can someone help me to understand this task and show me how the PDA for it looks like?

What you write is a snippet out of a recursive descent parser, one way of writing a program that parses a context free language. It is modelled on a PDA, specifically a LL(1) one. The stack is implicit in the recursive calls your parser does. Recursive descent is popular as it easy to write by hand (some tricks are needed to handle ambiguous constructs, like nested if ... then ... else and expressions, which naturally are represented by left-recursive grammars, but they are well-known) and requires no theory. More powerful parsing methods (like LALR or canonical LR) are too complex to do by hand for realistic grammars (in LL(1)/recursive descent, you can work one production at a time, other methods require considering a much larger part of the grammar). If you look at a typical (LA)LR parser generator's output (ask e.g. for --report=all for bison or -rfor byacc to get a text description, or -g for any of them to get a graphical depiction of the PDA).

Tl;dr: Undestanding PDAs and their relation to the grammar is
useful, but not essential to use the technology.


Minimizing Turing machine-like automaton with no final states I have a deterministic finite automaton which behaves mostly like a Turing machine, with following difference (relevant to this question):

The tape is initially finite.
The automaton can insert and delete cells from the tape.
Actions are associated with states rather than with transitions (this includes head shift and tape manipulation).
The automaton has no accepting/final state. The computation is only terminated when the machine exits the tape. The final state of the tape is the machine's output.

I know most of the states in the machine are redudant (equivalent to other states). However the good old DFA minimization algorithm won't work here, because it starts its work on the final states (which I don't have).

The algorithm should be efficiently computable (the machines in question have hundreds of thousands to millions of states).

Is this possible in the general case? Every algorithm I make up fails in some cases.

What exactly is the difference between your machine and a TM? (apart from not having accepting states, which is quite meaningless since you have an output)

It sounds like this is a very powerful model, and its halting problem will be undecidable, let alone minimization.

EDIT: Minimizing TMs is undecidable (actually, not in $RE\cup coRE$). It is easy to reduce the universality problem to it: given a TM, if you could minimize it, then the minimal TM will consist of a single, accepting state iff its language is $\Sigma^*$.


How do I count the exact number of executed commands for a MIPS program? I want to know what the best way is to count the number of executed commands for a given MIPS program. Let's say we're given a simple for loop that counts from $0$ to $100$. For this I would write the following MIPS code:

li $s1, 0
li $t0, 100

for_loop:
    addi $s1, $s1, 1
    beq $s1, $t0, exit
    j for_loop

exit:

Since I have $2$ li's before the loop, that would be $+2$ commands and then within the for_loop, the 99 loops pass for addi, beq and j which makes it $99⋅3$ and then $2$ for addi and beq. That makes it a total of $301$ executed commands. Is my answer correct? If not then what is the correct procedure to count the number of executed commands and if in the future I come across a more complex example, then how should I deal with it?

There are two ways: You use a simulator and count the actual number of instructions (or do it manually), which of course only works for fixed input like your case here. Or you use mathematics to calculate the number of instructions, just as you did.

In general, mathematical analysis ranges from easy to hard to impossible for humans, so there is no general method.

Sometimes you’re lucky to get a result like “about 2.25 n^2”, or “$\Theta (n^2)$ or similar. How do you deal with it? You do your best.


House painting problem where the house row is split and converged back I am trying to solve a house painting problem: There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs1 is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

This can be solved with dynamic programming (see solution in link house painting). I am trying to solve a very similar problem, but my house row is splitting somewhere in the middle and converging (but sometimes it doesn't), as shown in the picture attached:

Above you can see the problems that I am facing... Can I solve those problems with dynamic programming ? Is there any other solution for those problems ?

The problem you described can be solved in polynomial time using dynamic programming whenever the topology of the input houses is a tree (a path is just an even easier special case).

Unless $P=NP$, the problem is not solvable in polynomial time when the input instance is a general graph, since the $k$-coloring problem can be easily reduced to your problem.

However, in your particular case you are in luck since your input instances can always be decomposed in any of the following ways:

into $2$ paths by deleting two vertices.
into $2$ trees by deleting one vertex.

You can then guess the the color(s) of the deleted house(s) and update the cost matrix of their neighbors so that if a house $u$ is adjacent to a deleted house $v$ and $v$ is colored with color $c$, the cost of coloring $u$ with $c$ will be $+\infty$ (effectively ensuring that no optimal solution will color $u$ with $c$).

If $k$ is the number of colors, $n$ is the number of houses, and you delete $2$ vertices, solving your problem will take time $O(k^2 \cdot n k) = O(n k^3)$.

If you delete a single house and solve the problem on the resulting tree, you can reduce the time complexity to $O(k \cdot nk) = O(n k^2)$.

To solve the problem on trees in time $O(n k)$, root the input tree $T$ in an arbitrary vertex $r$ and let $C(u,c)$ be the cost of coloring vertex $u$ with color $c = \{1, \dots, k\}$.

Define $OPT[u,c]$ as the minimum cost needed to color the subtree of $T$ rooted in $u$ with the additional constraint that vertex $u$ must have a color different from $c$.

Then, if $u$ is a leaf of $T$, you have $OPT[u,c] = \min_{c' \in \{1, \dots, k\} \setminus c} C(u,c')$.
Otherwise, if $u$ is an internal vertex of $T$, let $v_1, \dots, v_h$ be its children. You have $OPT[u, c] = \min_{c' \in \{1, \dots, k\} \setminus c} \left( C(u, c') + \sum_{i=1}^h OPT[v_i, c'] \right)$.

The optimal solution is $\min\{ OPT[r, 1], OPT[r, 2] \}$ (since if $r$ is not colored with color $1$ in an optimal coloring then $OPT[r, 1]$ is exactly the minimum cost to color $T$, while if $r$ is colored with color $1$ then it is not colored with color $2$ and $OPT[r, 2]$ must be the minimum cost needed to color $T$).

A similar argument shows that, for each fixed vertex $u$, all supbroblems $OPT[u, c]$ can be solved in an overall time of $O(k)$ (there are only two interesting values of $c$). The time complexity follows.


Why is binary search called binary search? I heard several possible explanations, so I would like some trustable reference.

Update 05.19:
I'm interested in the question because one of mine students wrote in his thesis that the name comes from the below explanation (1). Until now I thought/heard that it comes from explanation (2). I would feel bad both for letting the wrong thing in his thesis, as well as telling him to remove it if it might be right.

(1) Consider the search for an integer in the interval $[0,2^{n-1}]$.
We can find it using $n$ questions by asking in step $i$ the $i^{th}$ binary digit of the number.

(2) If we have a search space with $2^n$ elements, we can find an unknown element by questions that repeatedly split the remaining part of the space in two.

And yes, I know that (2) can give the same algorithm as (1) but that's not the point here.
(2) can be also applied for more general problems.

I tried to look up the Mauchly reference cited by Knuth but my library seems to have misplaced their copy.

In the meantime, consider the following early-ish citations for "binary search":

Halpern, Mark. "Variable-width tables with binary-search facility." Communications of the ACM 1.2 (1958): 1-4.

  The family of subroutines described in this report was designed to create, search and maintain tables which are to contain entries of different lengths, and yet be amenable to search by partition, or “binary” search.

Nagler, H. "An estimation of the relative efficiency of two internal sorting methods." Communications of the ACM 3.11 (1960): 618-620.

  This report concerns the IBM 705, models I and II. It is a study of the machine time required by two internal sorting methods, the conventional two-way merge, and a form of the binary search, which is due to D. Mordy, of the IBM Corporation.

Petersen, T. L. RE-ENTRY VEHICLE SYNTHESIS PROGRAM. No. STL/TR-60-0000-09103 (pdf link). TRW SPACE TECHNOLOGY LABS LOS ANGELES CA, 1960.

  The value of ${V_0}^*$ for which $g({V_0}^*) = 0$ must now be found. It is easily seen that $g(0) = K_3 - 1$ and $g(K_1) = -1$, so that the required value of  ${V_0}^*$ lies between 0 and $K_1$ if $K_3>1$. A binary search is conducted for the root of $g({V_0}^*)$; the ${V_0}^*$ selected is that for which the absolute value of the difference between consecutive values of ${V_0}^*$ is less than $0.01$.

I'll note how the first 1958 citation uses quotation marks around "binary" but by the third citation in 1960, a binary search is mentioned without any further description or explanation. The allusion to "search by partition" would tend to suggest that explanation 2) is closer, but further verification is required.


prove upper bound of the recurrence $ T(n) =T(n-\sqrt{n})+1 $ i want to prove  upper bound of the following recurrence $ T(n) =T(n-\sqrt{n})+1 $ is $ O(\sqrt{n})$.

Define a sequence by $n_0 = n$, $n_{i+1} = n_i - \sqrt{n_i}$. Let $\ell$ be the maximal index such that $n_\ell \geq n/2$. For $i \leq \ell$ we have $\sqrt{n_i} \geq \sqrt{n/2}$, and so $n/2 \leq n_\ell \leq n - \ell \sqrt{n/2}$. It follows that $\ell \leq \sqrt{n/2}$.
Let $\ell_t$ be the maximal index such that $n_{\ell_t} \geq n/2^t$; so $\ell_0 = 0$ and $\ell_1 = \ell$. The preceding paragraph shows that $\ell_{t+1} - \ell_t \leq \sqrt{n_{\ell_t}/2}$. Since $n_{\ell_t+1} < n/2^t$, it follows that $n_{\ell_t} - \sqrt{n_{\ell_t}} < n/2^t$. If $t \leq \log_2 n$ then $n_{\ell_t} \geq 1$, and so $(\sqrt{n_{\ell_t}}-1)^2 = n_{\ell_t} - 2\sqrt{n_{\ell_t}} + 1 \leq n_{\ell_t} - \sqrt{n_{\ell_t}} < n/2^t$, and so $\sqrt{n_{\ell_t}} < \sqrt{n/2^t} + 1$. Therefore if $n_{\ell_t} \geq 1$ then $\ell_{t+1} - \ell_t \leq \sqrt{n/2^{t+1}} + 1/2$. It follows that if $t \leq \log_2 n$ then
$$
\ell_{t+1} \leq \sqrt{n/2} + \cdots + \sqrt{n/2^{t+1}} + t/2 = O(\sqrt{n} + t).
$$
Choosing $t = \lfloor \log_2 n \rfloor$, we get that the maximal index $s$ such that $n_s \geq 1$ is at most $\ell_{t+1} = O(\sqrt{n} + \log n) = O(\sqrt{n})$.
This shows that assuming an initial condition of the form $T(n) = O(1)$ for $n \leq 1$, you can bound $T(n) = O(\sqrt{n})$; a matching lower bound is obvious (at each step, the value of the parameter decreases by at most $\sqrt{n}$).
Using similar ideas, you can show that if you replace $\sqrt{n}$ by its floor or ceiling, then the resulting recurrence still grows like $\Theta(\sqrt{n})$.
What is the constant factor in the asymptotics of $T(n)$? If we define $\tau(s) = n_s$ and think of $\tau$ as continuous, then $\tau' = -\sqrt{\tau}$, and so $\tau(s) = (c-s)^2/4$. Since $\tau(0) = n$, we find that $c = 2\sqrt{n}$, and so $\tau(s) = (2\sqrt{n}-s)^2/4$. Therefore $\tau(s) = 0$ for $s = 2\sqrt{n}$, and so we expect $T(n) \sim 2\sqrt{n}$. This is indeed borne out by experiments, which suggest that $T(n) = 2\sqrt{n} - \Theta(\log n)$.


Switching between user-level and kernel-level threads After reading difference between user-level threads and kernel-level threads ,now I am in doubt of context switching.Context switching is managed by OS when switching between processes/threads but google didn't clarify me when i asked it that in which case more number of switching will take place for these cases :

1). User-level thread switched to another user-level

2).kernel-level thread switched to another kernel-level

3). User-level thread switched to kernel-level

Anyone please make it clear

Exceptional Control Flow

There is a process called exceptional control flow to deal with the problem of switching between kernel code and user code. Switching between user mode programs actually need the kernel code being executed between.

Context Switching

When a user mode program times out, an external timer triggers an interrupt. Then the operating system kernel takes back the control, save all registers used by the program. Then schedule another program to run.

Exceptions and Interrupts

There are some kinds of exceptional interrupts from outside, for instance user hit Ctrl-C or when you try to open a file (syscall), it will switch to kernel code. When the file is opened for you, the program will come back running. Another example is on modern virtual memory systems, if a memory requested is currently in a disk, not on memory, the system will interrupt the program by a page fault. Then the computer continue to run kernel code to fetch that portion of memory and come back to the program.


Practical applications of the palindromic substring problem? The longest palindromic substring problem is certainly an interesting intellectual exercise, and seems to be popular in coding interviews in industry. As an interesting puzzle, its popularity for interviews is not too hard to understand--it's not too hard to find an $O(N^2)$ solution, and if someone manages to come up with a linear time solution, they're probably either a genius or at least well-read, which is arguably as valuable.

Given the apparent frivolity of the problem, however, it seems like a surprising amount of effort has gone in to analyzing it. There are at least three published linear-time solutions (by Manacher, Jeuring, and Gusfield). But, is it actually useful for anything? Are there other problems in which finding a palindromic substring is a necessary step? And in the absence of a direct application, did any of the known solutions to this problem reveal new techniques that have been applicable elsewhere?

Lots of string-related algorithms have applications in the field of bioinformatics. Motivations for finding palindromic substrings in bioinformatics include

Finding secondary structures in RNA folding 1
Predicting DNA breakage during gene conversion 2
Finding/analyzing clustered regularly interspaced short palindromic repeats (CRISPRs) 3

These three motivations are presented in an article here and there are most likely many more.


What is a search problem? I'm looking for a formal and broad definition.

Intuitively, I would say that a problem where various checks have to be done is a search problem. Is this the only criteria? How can we know that a problem requires multiple checks?

Alternatively, I also think intuitively of problems with multiple paths as a search problem. In this case, only a single check might be necessary but multiple comparisons are needed in order to know which path is the best to follow.

A problem is a search problem if there's an algorithmic way to verify the answer.  In particular, let $V$ be any algorithm that takes two inputs and always terminates.  Then the following is a search problem:

Input: $x$
Goal: find and output any $y$ such that $V(x,y)=1$, or report that no such $y$ exists

Every search problem can be written in this form.  In particular, you can take the above as the definition of a search problem: a problem is a search problem if there exists an always-terminating algorithm $V$ that has the above form.


Algorithm to enclose a 2D-gridbased-room efficient I have the problem that I have a grid-based room which has 1 or more exits and I want to "secure" the room with minimal effort.

Here a little Example:

In this example black squares are not passable, white ones are and the ones with the arrows are the exits that should not be able to be reached.

I wan't to enclose the yellow square by converting white squares into black ones. I want to use as few conversions as possible.

Two ideas I found until now:

1 The fastest algorithm in my opinion would be to just convert all squares around the exits but it would not be the most efficient algorithm since in this example it would cost 9 conversions (13 if diagonal movement is possible) but its possible to enclose the yellow block with only 3 (5) conversions.

2 I found the Flood fill Algorithm, which would enable me to check if the area around the yellow square is enclosed but I can't think of a (cpu-)efficient method to try out possible conversions until I find the solution with the least conversions needed.

The Method should be able to enclose more then one targets, since otherwise an optimal solution would be often to just enclose the yellow block with 9 conversions around him. Therefore I added to my picture the green block, so the algorithm should be able to enclose all targets.

If you don't have an idea how to solve it but a hint where I could look into to find a possible solution I would be happy to hear it!

Thanks,
Niko

This is a graph cut problem.

Build a graph with one vertex per square.  Add an edge between each pair of adjacent vertices (i.e., where you can go from one to the other in a single step).  Add an extra "source" vertex $s$, and an edge from $s$ to each starting point (yellow/green block).  Add an extra "sink" vertex $t$, and an edge from each exit to $t$.

Now your mission is to find a minimum vertex cut that separates $s$ from $t$, i.e., a subset $S$ of vertices such that every path from $s$ to $t$ traverses at least one vertex of $S$.  There are standard algorithms for the minimum vertex cut problem, which you can find by searching the literature.

See also https://en.wikipedia.org/wiki/Vertex_separator and https://cstheory.stackexchange.com/q/2877/5038 and https://cstheory.stackexchange.com/q/29464/5038.

You'll need to add the extra constraint that the subset $S$ cannot include $s$ nor $t$, but I expect it should be easy to incorporate this constraint into standard algorithms for vertex cut.


Are there any known W[3] or W[3]-hard problems? We are currently working on a variant of domination parameter and we have shown that it is in W[3] with regard to parameterized complexity. To show it is W[3]-complete, we must show the problem is W[3] hard i.e, reduce an already known W[3] hard problem to ours. But unlike W[1] and W[2], where many famous problems are proved those classes, surprisingly we have not come across a single problem that is W[3] hard and not even in just W[3]. Of course there is the general W[t] case which we can go for, but any result for W[3] in particular would help a lot.

There are a few examples in the answer to Natural complete problems in higher levels of the W-hierarchy. In particular, the W[3]-complete problem $p$-HYPERGRAPH-(NON)-DOMINATING-SET may be useful for your proof.
Given that the linked question is now almost 6 years old, you'd perhaps expect some more examples to pop up by now. However, I couldn't find anything concrete in a quick literature search. The closest thing I could find was  Separating sets of strings by finding matching patterns is almost always hard (2017) by Lancia et al., where they conjecture that the problem they call PATTERN IDENTIFICATION is W[3]-complete for a particular parameter, but this conjecture is probably not very useful for your proof. I do note that I'm not an expert in this field, so there may be some more recent results out there I simply wasn't able to find.