How to solve the bin packing problem with conflicts?

I have found the following resources that should be useful.
A first line of work has been on the domain of approximation algorithms and focused on achieving results for particular classes of the conflict graph:

[1] Jansen, Klaus. "An approximation scheme for bin packing with conflicts." Journal of combinatorial optimization 3.4 (1999): 363-377.
[2] Epstein, Leah, and Asaf Levin. "On bin packing with conflicts." SIAM Journal on Optimization 19.3 (2008): 1270-1298.

In [1], the author proposes an asymptotic approximation scheme for the bin
packing problem with conflicts restricted to $d$-inductive graphs with constant
$d$. This graph class contains trees, grid graphs, planar graphs and
graphs with constant treewidth. The algorithm's number of bins within a factor of
$1 + \varepsilon$ of optimal, having runtime polynomial both in $n$ and $1/\varepsilon$. This is an algorithmic theory paper with no experimental results are provided.
In [2], the authors study both online and offline variants of BPC, again, only on specific graph classes, e.g. perfect graphs, interval graphs and bipartite graphs. They improve on previous approximation ratio by Jahnsen and Öhring for perfect graphs. As an example of the results, they create a 2.5-approximation algorithm for the perfect graph case. Again a theoretical work where no numerical examples are shown.
A second line of work is concerned with implementation and heuristics (I am including branch-and-bound algorithms on this category even though they follow a different paradigm) and includes the following publications:

[3] Muritiba, Albert E. Fernandes, et al. "Algorithms for the bin packing problem with conflicts." Informs Journal on computing 22.3 (2010): 401-415.
[4] Sadykov, Ruslan, and François Vanderbeck. "Bin packing with conflicts: a generic branch-and-price algorithm." INFORMS Journal on Computing 25.2 (2013): 244-255.

In [3], the authors present new methods for finding upper and lower bounds for the BPC optimal solution, and a couple algorithmic approaches for the BPC:

Evolutionary Algorithms and Tabu search
Branch and price (that is, branch and bound combined with a column generation scheme) using a set covering formulation.

They show benchmark results consistently improving previous methods from the literature. They also left the benchmark instances and computational results available online, which could be useful to OP or other interested people. At this link you can find conference presentation slides related to this work. They used CPLEX, which is  a commercial solver for optimization.
Finally [4], which is available at one of the authors' ResearchGate profile here. As in [3], the authors propose a branch-and-price algorithm for this problem using a set covering formulation, but the methods' details are different. They tested the approach on several instances, creating a specific variant for the case where the conflict graph $G$ is an interval graph, while also developing an approach for the general case. They tested their algorithm on both kinds of scenarios, and experimental results show their approach outperformed previous algorithms in several instances, both in terms of execution time and of achieving optimality. The work was implemented using BaPCod, a branch-and-price framework developed in C++ by a group at INRIA.

As a summary:

Having graph coloring as a particular case, it's hard to approximate the BPC. Good results have been attained using heuristic methods and branch and price with set covering formulations.
So, you could try starting with the simplest steps of the method presented by Fernandes-Muritiba et al- that is, lower and upper bounds and Evolutionary Algorithms and see if they fulfill your needs in terms of solution quality and execution time. There are several frameworks for implementing evolutionary algorithms, e.g. DEAP in Python.
If you'd rather have a general approximation guarantee, and if the conflict graph instances you work with fall within the categories of their studies, evaluate implementing algorithms from the first line of work.
I'd leave using branch and price approaches for later, especially in case of a tight development timeframe or if you don't have access to an optimization solver license.


Permuting integer vectors $x$ and $y$ which add to integer vector $z$

Your problem is equivalent to numerical 3-dimensional matching and is NP-complete.
It is listed under code SP16 in Computers and Intractability; A Guide to the Theory of NP-Completeness by Garey and Johnson.


The approach you used is called dynamic programming.

In dynamic programming, a series of decisions are made in order to maximize some function, where the options available at any given time depend on the decision we have made before. You may want to check a tutorial on TopCoder or some course material at your hand.

You have started to figure out the recurrence relation, the hallmark of dynamic programming. However, it looks like you made an off-by-one error.

You can imitate the pseudocode in that tutorial. Or many other pseudocode such as those in the Introduction to algorithm by Corman et al.

Here is my pseudocode for this problem, where you can find the correct recurrence relation. I assume $n\ge4$; otherwise the only choice is to use
company $A$ always.

Let $OPT$ be an array of size $n$.
$OPT[0]=0$, $OPT[1]=s_1r$, $OPT[2]=(s_1+s_2)r$, $OPT[3]=(s_1+s_2+s_3)r$
For $i$ = 4 to $n$,  $OPT[i] = \min(OPT[i-1] + s_ir, OPT[i-4] + 4c)$
Output $OPT[n]$


Intersection/Union of recursively enumerable languages that aren't decidable?

Correct. We can have $L_1\cap L_2=\emptyset\in R$. A good answer would give an example of such a pair $L_1$, $L_2$ so you should figure that out on your own.
Correct but for the wrong reason. If $L_1$ and its complement are both $RE$, then both are recursive and the question says that neither is recursive.  You should prove this yourself, as you'll need it for the next part.

Hint for this proof: show how to use machines that accept $L_1$ and $\overline{L_1}$ to give a machine that decides $L_1$.)
Hint for the question: take a recursives language $K_1$ and $K_2$ and set $L_1=K_1 \cup \text{something}$ and $L_2=K_2\cup\text{something else}$ in a way that gives $L_1\cup L_2=K_1\cup K_2$.

Correct. We know that $L_1\in RE$. Use $L_1\cap L_2\in R$ and $L_1\cup L_2\in R$ to show that $\overline{L_1}\in RE$. By the extra proof I suggested you do in the previous part, that means that $L_1\in R$, contradicting the requirement that $L_1\in RE\setminus R$.


if $\delta(q, a) = q$ for all symbols $a$, show that $\delta^* (q, w) = q$ is true for all strings $w$

By popular request, here is what the proof could look like:

  By induction over the length of $w$.  Assume $\delta(q,a)=q$ for all
  $a$. Take any $w$. There are two cases:

  If $|w|=0$ then $w=\epsilon$ (the empty word). Now the definition of $\delta^*$ has "$\delta^*(q,\epsilon)=q$" without any assumption
  on $\delta$ or $q$. We thus have $\delta^*(q,w)=q$ in this first case.
  If $|w|>0$ then $w$ is some $w'a$ and $|w'|<|w|$. Now $\delta^*(q,w)=\delta^*(q,w'a)=\delta(\delta^*(q,w'),a)$ by definition
  of $\delta^*$. Since $|w'|<|w|$ we have $\delta^*(q,w')=q$ by
  induction hypothesis. Finally $\delta^*(q,w)=\delta(q,a)$, which is
  $q$ by the assumption. We have proved the required conclusion in this
  second case too.

  All cases have been covered. The proof is complete.

  Note that the two cases can be considered in any order we like. And
  that we do not use that $|w'|=|w|-1$, just that $|w'|<|w|$.

As you can see, the above proof uses the same arguments as in your solution, and at the same places. It is slightly more rigorous on the quantifications ("take any $w$" is a "$\forall w$" and "$w$ is some $w'a$" is a "$\exists w'\exists a:w=w'a$") and their nesting ($w'$ and $a$ depend on $w$).

It is the kind of proof I'd love to get from a bright student beginning automata theory. But it is too pedantic and pedestrian for experts who, in their own papers, will usually just state the conclusion as obvious from the assumption. They may even not state the conclusion at all and use it anyway.


Can we prove that $1 + 2 + \dots + n = \frac{n(n+1)}{2}$ using a computer program?

In order with the explicit questions:

Yes
Yes
No

To answer the question I think you're attempting to ask, we can prove many things using type checking, but not everything. What does this have to do with programs? That's what the Curry-Howard correspondence tells us. The Curry-Howard correspondence is a relationship between logic and computational models. The informal version is "proofs and programs and programs are proofs". While the specifics are far too much to detail here, the rough idea is that a function (read program) that takes an input of type $A$ and produces an output of type $B$ is a proof that $A \rightarrow B$ (and yes the funtion type arrow maps to the logical implication arrow).

Why can't we do everything? The good old halting problem. Some things we just can't check. Even worse, in practice, we're often limited to things we already know we can check, i.e. programs that are of a subclass that we know always halt.

Just to give a more complicated example, I've written a proof/program for $1+\ldots n = \frac{n\cdot(n+1)}{2}$ in Coq. Coq is a bit different to Haskell, but the idea should be fairly apparent. In this case, Coq has the advantage that it's explicitly built for theorem proving, so we can get a "proof-like" version and a "program-like" version. The proof can only complete if all the types match correctly - i.e. if we can specify a way to get from the input type to the output type, in the normal type checking sense. To avoid using division, I've rephrased the lemma.

The proof-like version:

Fixpoint sum (n : nat) : nat :=
match n with
| 0 => 0
| S n' => n + sum n'
end.

Lemma sum_closed_form (n : nat) : 2 * sum n = n * (n + 1).
Proof.
  induction n.
  reflexivity.
  assert (Step: sum (S n) = S n + sum n).
    reflexivity.
  rewrite Step.
  rewrite mult_plus_distr_l.
  rewrite IHn.
  assert (Id : S n = n + 1).
    omega.
  rewrite Id.
  repeat rewrite mult_plus_distr_l.
  repeat rewrite mult_plus_distr_r.
  omega.
Qed.

So apart from the individual steps being black boxes, it's fairly clear that this looks a lot like a normal proof - it is in fact an induction, and all the mystery black boxes are in fact just other proofs that allow us to take some input type to another. One of the key steps in understanding how this works is to look closely at statement of the lemma: Lemma sum_closed_form (n : nat) : 2 * sum n = n * (n + 1).

Notice that it looks a bit like a function declaration, it takes a parameter of type nat, and produces an output of type 2 * sum n = n * (n + 1). That is in fact what it is, so in this form we can see the proof bit, and get an idea of the function bit - i.e. the proof is in fact a program. More explicitly, it is this program:

sum_closed_form =
fun n : nat =>
nat_ind (fun n0 : nat => 2 * sum n0 = n0 * (n0 + 1)) eq_refl
(fun (n0 : nat) (IHn : 2 * sum n0 = n0 * (n0 + 1)) =>
(fun Step : sum (S n0) = S n0 + sum n0 =>
eq_ind_r (fun n1 : nat => 2 * n1 = S n0 * (S n0 + 1))
(eq_ind_r (fun n1 : nat => n1 = S n0 * (S n0 + 1))
(eq_ind_r (fun n1 : nat => 2 * S n0 + n1 = S n0 * (S n0 + 1))
((fun Id : S n0 = n0 + 1 => eq_ind_r
(fun n1 : nat => 2 * n1 + n0 * (n0 + 1) = n1 * (n1 + 1))
(eq_ind_r (fun n1 : nat =>
n1 + n0 * (n0 + 1) = (n0 + 1) * (n0 + 1 + 1))
(eq_ind_r (fun n1 : nat =>
2 * n0 + 2 * 1 + n1 = (n0 + 1) * (n0 + 1 + 1))
(eq_ind_r (fun n1 : nat =>
2 * n0 + 2 * 1 + (n0 * n0 + n0 * 1) = n1)
(eq_ind_r (fun n1 : nat =>
2 * n0 + 2 * 1 + (n0 * n0 + n0 * 1) = n1 + (n0 + 1) * 1)
(eq_ind_r (fun n1 : nat =>
2 * n0 + 2 * 1 + (n0 * n0 + n0 * 1) = n1 + (n0 + 1) * 1 + (n0 + 1) * 1)
(eq_ind_r (fun n1 : nat =>
2 * n0 + 2 * 1 + (n0 * n0 + n0 * 1) = n0 * n0 + 1 * n0 + n1 + n1)
(Decidable.dec_not_not
(2 * n0 + 2 * 1 + (n0 * n0 + n0 * 1) = n0 * n0 + 1 * n0 + (n0 * 1 + 1 * 1) +
(n0 * 1 + 1 * 1))
(dec_eq_nat (2 * n0 + 2 * 1 + (n0 * n0 + n0 * 1))
(n0 * n0 + 1 * n0 + (n0 * 1 + 1 * 1) + (n0 * 1 + 1 * 1)))
(fun H : 2 * n0 + 2 * 1 + (n0 * n0 + n0 * 1) <> n0 * n0 + 1 * n0 +
(n0 * 1 + 1 * 1) + (n0 * 1 + 1 * 1) =>
(fun (P : Z -> Prop) (H0 : P (Z.of_nat 2 * Z.of_nat (sum n0))%Z) =>
eq_ind_r P H0 (Nat2Z.inj_mul 2 (sum n0)))
(fun x : Z => x = Z.of_nat (n0 * (n0 + 1)) -> False)
((fun (P : Z -> Prop)
(H0 : P (Z.of_nat n0 * Z.of_nat (n0 + 1))%Z) =>
eq_ind_r P H0 (Nat2Z.inj_mul n0 (n0 + 1)))
(fun x : Z => (2 * Z.of_nat (sum n0))%Z = x -> False)
((fun (P : Z -> Prop) (H0 : P (Z.of_nat n0 + Z.of_nat 1)%Z) =>
eq_ind_r P H0 (Nat2Z.inj_add n0 1))
(fun x : Z => (2 * Z.of_nat (sum n0))%Z =
(Z.of_nat n0 * x)%Z -> False)
(fun _ :  (2 * Z.of_nat (..))%Z =
(Z.of_nat n0 * (.. + 1))%Z =>
(fun  (P : Z -> Prop) (H0 : P (..)%Z) =>
eq_ind_r P H0 (Nat2Z.inj_add (..) (..)))
(fun x : Z => Z.of_nat (..) = x -> False)
((fun (P : ..) (H0 : ..) => eq_ind_r P H0 (..))
(fun x : Z => .. = ..%Z -> False)
(fun _ : .. => (..) (..) (..) (..)))
(inj_eq  (sum (S n0)) (S n0 + sum n0) Step))))
(inj_eq (2 * sum n0)
(n0 * (n0 + 1)) IHn)))
(mult_plus_distr_r n0 1 1))
(mult_plus_distr_r n0 1 n0))
(mult_plus_distr_l (n0 + 1) n0 1))
(mult_plus_distr_l (n0 + 1) (n0 + 1) 1))
(mult_plus_distr_l n0 n0 1))
(mult_plus_distr_l 2 n0 1)) Id)
(Decidable.dec_not_not (S n0 = n0 + 1)
(dec_eq_nat (S n0) (n0 + 1))
(fun H : S n0 <> n0 + 1 =>
(fun (P : Z -> Prop)
(H0 : P (Z.of_nat 2 * Z.of_nat (sum n0))%Z) =>
eq_ind_r P H0 (Nat2Z.inj_mul 2 (sum n0)))
(fun x : Z => x = Z.of_nat (n0 * (n0 + 1)) -> False)
((fun (P : Z -> Prop)
(H0 : P (Z.of_nat n0 * Z.of_nat (n0 + 1))%Z) =>
eq_ind_r P H0 (Nat2Z.inj_mul n0 (n0 + 1)))
(fun x : Z => (2 * Z.of_nat (sum n0))%Z = x -> False)
((fun (P : Z -> Prop)
(H0 : P (Z.of_nat n0 + Z.of_nat 1)%Z) =>
eq_ind_r P H0 (Nat2Z.inj_add n0 1))
(fun x : Z => (2 * Z.of_nat (sum n0))%Z = (Z.of_nat n0 * x)%Z -> False)
(fun _ : (2 * Z.of_nat (sum n0))%Z =
(Z.of_nat n0 * (Z.of_nat n0 + 1))%Z =>
(fun (P : Z -> Prop) (H0 : P (Z.of_nat (S n0) + Z.of_nat (sum n0))%Z) =>
eq_ind_r P H0 (Nat2Z.inj_add (S n0) (sum n0)))
(fun x : Z => Z.of_nat (sum (S n0)) = x -> False)
((fun (P : Z -> Prop) (H0 : P (Z.succ (Z.of_nat n0))) =>
eq_ind_r P H0 (Nat2Z.inj_succ n0))
(fun x : Z => Z.of_nat (sum (S n0)) = (x + Z.of_nat (sum n0))%Z -> False)
(fun _ : Z.of_nat (sum (S n0)) =
(Z.succ (Z.of_nat n0) + Z.of_nat (sum n0))%Z =>
(fun (P : Z -> Prop) (H0 : P (Z.succ (Z.of_nat n0))) =>
eq_ind_r P H0 (Nat2Z.inj_succ n0))
(fun x : Z => Zne x (Z.of_nat (n0 + 1)) -> False)
((fun (P : Z -> Prop) (H0 : P (Z.of_nat n0 + Z.of_nat 1)%Z) =>
eq_ind_r P H0 (Nat2Z.inj_add n0 1))
(fun x : Z => Zne (Z.succ (Z.of_nat n0)) x -> False)
(fun H0 : Zne (Z.succ (Z.of_nat n0))
(Z.of_nat n0 + 1) => ex_ind (fun (Zvar29 : Z)
(Omega75 : Z.of_nat n0 = Zvar29 /\ (0 <= Zvar29 * 1 + 0)%Z) =>
and_ind (fun (Omega66 : Z.of_nat n0 = Zvar29)
(_ : (0 <= Zvar29 * 1 + 0)%Z) =>
ex_ind (fun (Zvar30 : Z) (Omega74 : .. /\ ..%Z) =>
and_ind (.. => ..) Omega74) (intro_Z (sum (..)))) Omega75)
(intro_Z n0))) (inj_neq (S n0) (n0 + 1) H)))
(inj_eq (sum (S n0)) (S n0 + sum n0) Step))))
(inj_eq (2 * sum n0) (n0 * (n0 + 1)) IHn)))) IHn)
(mult_plus_distr_l 2 (S n0) (sum n0))) Step) eq_refl) n
: forall n : nat, 2 * sum n = n * (n + 1)

To give a shorter example, the associativity of addition can be proved like so:

Lemma add_assoc (n m p : nat) : n + (m + p) = (n + m) + p.
Proof.
  induction n.
  reflexivity.
  simpl. rewrite IHn.
  reflexivity.
Qed.

The associated function is:

add_assoc =
fun n m p : nat =>
nat_ind (fun n0 : nat => n0 + (m + p) = n0 + m + p) eq_refl
  (fun (n0 : nat) (IHn : n0 + (m + p) = n0 + m + p) =>
   eq_ind_r (fun n1 : nat => S n1 = S (n0 + m + p)) eq_refl IHn) n
     : forall n m p : nat, n + (m + p) = n + m + p


What is $R_\min$ in this formulat for optimal buffer size?

$R_{min}$ is the "Writing Rate in Application Buffer" (from router in your example).

This formula makes sense for different conditions like $R_{app}=R_{min}$. In this case the buffer size should be infinite (very large buffer) and it is intuitively correct. $R_{app} >R_{min}$ makes the size negative which shows that buffering does not help while the reading data is very faster than buffering data in user side.


How is this algorithm in these two complexities?

The $O(\cdot)$ notation only gives an upper bound on the complexity. An algorithm has running time $O(n^2)$ if its running time can be bounded by $cn^2$ for some $c$. If it has running time $n$, say, then it's certainly bounded by $cn^2$ and so $O(n^2)$, though that's not the optimal bound.

A complement to $O(\cdot)$ is $\Theta(\cdot)$. An algorithm has running time $\Theta(n^2)$ if its (worst-case) running time is between $c_1n^2$ and $c_2n^2$ for some $0<c_1\leq c_2$. If an algorithm is $\Theta(n\log n)$ then it is not $\Theta(n^2)$ (though still $O(n^2)$). In fact, even if all you know is that it is $O(n\log n)$, then that rules out $\Theta(n^2)$.

Summarizing, $\Theta$ is "exact" complexity (up to constant multiples), and $O$ is just an upper bound. There is also $\Omega$ which is for lower bounds, for example an algorithm is $\Omega(n^2)$ if its (worst-case) running time is at least $cn^2$ for some $c > 0$.


Finding path with specific length in weighted graph

Your problem is NP-complete by a reduction from Hamiltonian $st$-path, even with unweighted arcs. Thus, you should not expect a polynomial-time algorithm. I'll sketch a reduction below.

Let $G$ be an instance of Hamiltonian $st$-path with all $m$ arcs having weight 1. Let $G'$ be a graph obtained from $G$ by adding a long directed path of length $C$ starting from $t$ ending at (say) $t'$. Now, if there's an Hamiltonian path from $s$ to $t$, there is also a path from $s$ to $t'$ of length $m$ plus $C$. On the other hand, if there's a path of length $m+C$ from $s$ to $t'$ in $G'$, you can chop off the long path from $t$ to $t'$ to obtain a Hamiltonian $st$-path in $G$.


Satisfiability with relational operators instead of boolean variables

Congratulations, you have invented Satisfiability Modulo Theories, also known as SMT. This is a large field of research, and deals with exactly the problem of satisfiability with not just boolean variables, but predicates over some existing logical theories, such as linear integer arithmetic, uninterpreted functions, arrays, etc.

The basic idea is that you alternate between calling a SAT solver and a theory solver. You take your relational formula, and replace every relational statement with a boolean variable, then get a solution from a SAT solver. This gives you a True or False value for each relational statement. You then plug those into your theory solver, which determines if there's a solution that is consistent with the truth value for each relational proposition.

If the solution is valid, then you are done. If it is not valid, then you add the negation of the assignment (or a reduced form) to your original boolean problem, since you know it can't hold, and you repeat until you either the theory solver succeeds or the SAT solver fails.

SMT research doesn't care a ton about theoretical complexity, since everything is NP-hard in the best case, and possibly much worse, depending on your theory. Instead, modern SMT solvers are heavily optimized with heuristics and prunings that allow them to be reasonably fast for common cases.

The two most common SMT solvers are Z3 and CVC4, but I have no clue if either work in JavaScript. Writing an inefficient SMT solver yourself is not too hard, especially if you can use an off-the-shelf SAT solver.


Understanding the one-writer, many-readers problem?

First,I would suggest (in the future as well) to write the pseudocode yourself (the commands for the readers/writers), It will be cleaner and easier to read than the image. Also, i would suggest briefly explaining the semantics of your operations (wait/signal/up, since you used all three in the code).

To your answer, readers not being able to read simultaneously does not mean starvation, although simultaneous reading ability is an additional requirement, at least in the classical formulation of the problem (moreover, readers can read simultaneously in this protocol). Starvation means that there exists a process stuck waiting while other processes share the resource (if one reader $r_1$ has to wait until $r_2$ is done, then he might read after $r_2$, who eventually will be done reading, so $r_1$ is not stuck).

This protocol (as  it seems to me) is the same as the one described here (under First readers-writers problem). It is easy to see (as mentioned in the link) that writers can be starved here. Suppose $r_1,r_2$ are reading at the same time, so the count is $2$. Imagine a scenario where whenever $r_1,r_2$ read together, the first to finish (and decrements the counter to $1$) immediately requests reading again (so the counter is back to $2$). This way the counter will never reach $0$ and the writer will be starved (stuck waiting).


Does P=NP imply polynomial solutions to #P?

Your confusion is that the class #P only asks you to count the solutions, not to enumerate them, and you only need $n$ bits to write down the number $2^n$. This means that to express the number of satisfying assignments to a formula of $n$ variables, you need $n$ bits, because there are at most $2^n$ solutions (i.e. in the case of a tautology). Another example: the number of isomorphisms between two graphs is at most $n!$, which requires $\log(n!)\approx n\cdot \log(n)$ bits to write down. All these number of bits are polynomial in the size of the input

#P can be solved in polynomial time if and only if P=PP. This is a stronger statement than P=NP, because P=PP implies P=NP (and hence, it is less likely). If P=NP, then all #P problems can be approximated to within a constant factor by a deterministic algorithm.


A complete graph is a graph with every possible edge; a clique is a graph or subgraph with every possible edge. That is, one might say that a graph "contains a clique" but it's much less common to say that it "contains a complete graph".


Algorithm/data structure to quickly check if an integer is a member of any [lower, upper] interval

Here's my thought process on this problem:

If you only care about "in or out", you can reduce the list of intervals so that no intervals overlap, and the intervals are in sorted order.

Sorting by leftmost point takes $O(n \log n)$, then replacing any overlapping pairs with their union takes $O(n)$. But you've said you don't care how long this part takes.

For a given point and a given interval, you can determine whether the point is "outside to the left", "inside", or "outside to the right" in $O(1)$.

This assumption only works as long as you have a fixed word length, but that's generally true for all practical purposes.
Let's change the terms: "outside to the left" is "less than", "inside" is "equal to", and "outside to the right" is "greater than".

Now you can use standard binary search!

Since each comparison is $O(1)$, the total time is $O(\log n)$.

And voilà, each check takes only logarithmic time! Setting up the list in the first place takes $O(n \log n)$, and adding a new interval to the list later takes $O(n)$ in the worst case.


Intuition behind eigenvalues of an adjacency matrix

(Disclaimer: This answer is about eigenvalues of graphs in general, not the second eigenvalue in particular. I hope it is helpful nevertheless.)

An interesting way of thinking about the eigenvalues of a graph $G = (V, E)$ is by taking the vector space $\mathbb{R}^n$ where $n = |V|$ and identifying each vector with a function $f\colon V \to \mathbb{R}$ (i.e., a vertex labeling). An eigenvector of the adjacency matrix, then, is an element of $f \in \mathbb{R}^n$ such that there is $\lambda \in \mathbb{R}$ (i.e., an eigenvalue) with $A f = \lambda f$, $A$ being the adjacency matrix of $G$. Note that $A f$ is the vector associated with the map which sends every vertex $v \in V$ to $\sum_{u \in N(v)} f(u)$, $N(v)$ being the set of neighbors (i.e., vertices adjacent to) $u$. Hence, in this setting, the eigenvector property of $f$ corresponds to the property that summing over the function values (under $f$) of the neighbors of a vertex yields the same result as multiplying the function value of the vertex with the constant $\lambda$.


3-Col using each colour exactly $|V|/3$ times

No, the problem is still NP-complete.  Suppose you want to know if $G$ is 3-colourable (with no limits on how many vertices can be each colour). Just make a new graph $G^+$ by adding $2|V(G)|$ new vertices with no edges between them, so $|V(G^+)|=3|V(G)|$. If $G$ has a 3-colouring then you can get a "balanced" 3-colouring of $G^+$ by setting the colours of the new vertices appropriately; if $G$ has no 3-colouring, then $G^+$ also has no 3-colouring, so it has no balanced 3-colouring, either.


How do we define the term "computation" across models of computation?

Definition 5.12 is a standard way of defining a "computable function".  I see that you wish it was defined generically, but things are not as you wish they were; computability is typically defined with respect to a single model of computation.
That said, if you have any other Turing-complete notion of computation, then it is easy to prove that you can replace "Turing machine" with "machine in that model of computation" and you'll get an equivalent notion: in other words, there will be a Turing machine that computes $f$ iff there is a machine in that model of computation that computes $f$.  So the concept is indeed quite generic, even if the definition is not articulated that way.
See also https://en.wikipedia.org/wiki/Computable_function#Definition.
The exact semantics of C are messy and hard to formalize, and there appears to be some debate about whether C is Turing-complete, so C code is typically not a good way to prove that a function is computable or to reason about whether a function is computable.


sentiment analysis by sentence similarity

I expect that measuring the similarity of two sentences probably isn't a useful way to do sentiment analysis.  There are better methods for sentiment analysis, so rather than adopting the artificial constraint that it must work by measuring the similarity of two sentences, it's better to use standard methods (I expect they will perform better).


Average number of comparisons for a successful search of a prime number in a binary search tree

This is a very simple question, I will explain steps-by-steps:
First, you need to count total elements and total comparisons in your tree
Second, you need to know that for each element in the tree, it takes $\frac{total \ comparisons}{total \ elements}$ average comparisons to search for an element in the tree.
Third, if the problem gives you a probability to search for an element, you need to multiply it by each element.
Now back to your question:

Total elements = $10$, total comparisons = $1 \cdot 1 + 2 \cdot 2 + 3\cdot 3 + 2 \cdot 4 + 2\cdot 5 = 33$ (this is calculated by taking the total nodes at each level and multiply it by the level, you need to draw the tree to understand).
The tree has $5$ odd elements and $5$ even elements, you need to do now is to take the probability and multiply it by each element, which in your case is $\frac{1}{10} \cdot 5 + \frac{1}{25} \cdot 5 = \frac{1}{2} + \frac{1}{5} = \frac{7}{10}$.
Now your expected value is: $E(x) = \frac{33}{\frac{7}{10} \cdot 10} = \frac{33}{7}$, which is also the solution for your problem.


Min weighted edge cover - is the greedy algorithm sub-optimal?

Here is a counterexample to your proposed algorithm:

The optimal solution consists of 3 edges and costs 3+1+1=5, but the min-cost maximum-cardinality matching, which consists of 2 edges and costs 3+3=6, will be chosen by the first step of your algorithm and immediately returned, as it is already a solution. (The only other maximum-cardinality matching costs 1+6=7.)


Linear programming: reduce a contstraint that includes minimun

Solve two linear programs.  The first has the constraints
$$
A \mathbf x = \mathbf b,\quad x_1 = x_2 \le x_3.
$$
The second has the constraints
$$
A \mathbf x = \mathbf b,\quad x_1 = x_3 \le x_2.
$$
Choose whichever solution gives you a smaller value for $\mathbf c' \mathbf x$.

This works for your particular situation.  It doesn't scale to a case where you have a large number of $\min$ constraints.


The connection is that if a you can represent the structure underlying your optimisation problem as matroid, you can use the canonical greedy algorithm to optimise the sum of any positive weight function. If your optimisation goal fits this paradigm, you can solve your problem with the greedy approach.

Example

Consider the minimum spanning tree problem with positive edge weights¹. We will show that there is a matroid corresponding to that problem, implying that it can be solved greedily, that is by the canonical greedy algorithm on said matroid.

Let $G = (V,E,c)$ be an undirected graph with $c : E \to \mathbb{R}_+$ the edge-cost function. Then, $(E,I)$ with

$\qquad \displaystyle I = \{F \subseteq E \mid (V|_F, F) \text{ is a forest}\}$²

is a matroid. Thus, we can find the element of $I$ maximising the sum of edge weights $c'(e) = (\max_{e \in E}c(e)) - c(e)$. This happens to be a minimum spanning tree. Note that the canonical greedy algorithm is called Kruskal's algorithm in this context for historical reasons.

Proofs

To show: $(E,I)$ is a matroid. We have to verify three properties:

$\emptyset \in I$ -- the empty graph is a forest.
If $F \in I$, every subset of $F$ is in $I$ -- given an arbitrary forest, removing edges can not introduce cycles. Therefore, every subgraph of a forest is a forest.
For every $F_1,F_2 \in I$, $|F_1| > |F_2|$ implies that there is $e \in F_1 \setminus F_2$ so that $F_2 \cup \{e\} \in I$ -- consider an arbitrary forest $F_1$ and a smaller one $F_2$. Assume there is no such $e$. That means that all edges in $F_1$ lie in cuts induced by edges in $F_2$³. As there are only $|F_2|$ such cuts, at least one pair of edges in $F_1$ shares a cut; this contradicts that $F_1$ is a forest.

To show: any element $F^*$ with maximum weight in $I$ is a minimum spanning tree of $G$. First of all, it is clear $F^*$ has maximum weight according to $c'$, so by definition of $c'$, it also has minimum weight according to $c$. Now all we have to show is that it is a spanning tree: if it was not, it would not be maximal in the sense that we could still add edges (with positive weight), contradicting maximum weight.

We can deal with negative edge weights by adding the minimum weight plus one to all weights.
A forest is a disjoint union of trees.
A graph contains a cycle if and only if there is a cut with more than one edge.


Is intersection used in regular expression?

Regular expressions over an alphabet $\Sigma$, and their denotations (denoted by $L[r]$), are defined as follows:

$\emptyset$ is a regular expression, and $L[\emptyset] = \emptyset$ (empty language).
$\epsilon$ is a regular expression, and $L[\epsilon] = \{\epsilon\}$ (the empty word).
For each $\sigma \in \Sigma$, $\sigma$ is a regular expression, and $L[\sigma] = \{\sigma\}$ (single letter).
If $r_1,r_2$ are regular expressions over $\Sigma$ then so is $r_1r_2$, and $L[r_1r_2] = L[r_1]L[r_2]$ (concatenation).
If $r_1,r_2$ are regular expressions over $\Sigma$ then so is $r_1+r_2$, and $L[r_1+r_2] = L[r_1] \cup L[r_2]$ (union).
If $r$ is a regular expression over $\Sigma$ then so is $r^*$, and $L[r^*] = L[r]^*$ (iteration).

The definition of concatenation of languages is
$$
L_1L_2 = \{w_1w_2 : w_1 \in L_1, w_2 \in L_2\}.
$$
The definition of iteration is
$$
L^* = \bigcup_{n=0}^\infty L^n, \text{ where } L^0 = \{\epsilon\} \text{ and } L^{n+1} = L^nL.
$$

As you can see, union is built into regular expressions, whereas intersection isn't. However, the set of regular languages (which is the set of languages of the form $L[r]$) is closed under intersection, and so given any two regular expressions $r_1,r_2$, we can find a regular expression $r$ such that $L[r] = L[r_1] \cap L[r_2]$.

It turns out that sometimes $r$ will be much larger than $r_1,r_2$, see for example
Gelade and Neven, Succinctness of the Complement and Intersection of Regular Expressions, Theorem 17(2). A similar phenomenon is exhibited by complementation, see for example Theorem 12(2) in the aforementioned paper. For this reason, sometimes extended or generalized regular expressions are considered, in which operations such as intersection and complementation are allowed. While this does not increase the expressivity of regular expressions – every language expressible using an extended regular expression can also be expressed as a standard regular expression – it does increase their economy (i.e., length or size).


To use any formula, you need to think about what it means. You can't just blindly apply formulas.

$C(n) = aC(n/b) + c$ (and, yes, I've changed the constants) means that the cost of running the algorithm on an input of size $n$ is $a$ times the cost of running it on an input of size $n/b$, plus some constant overhead $c$.  A typical case of that would be an algorithm that chops its input into $b$ equally sized parts and makes recursive calls on $a$ of those parts. Normally, you'd have $a=b$ (e.g., split the input into three and recurse on each part), which is why the formula you quoted has just two constants.  But you could imagine some sort of average-case analysis where you split into some number of parts and, on average, only need to look at half of them.


How to show that a non-empty $L$ is recognizable iff there exists a total computable function whose range equals $L$

Hints:

If $L$ is recognized by some Turing machine $T$, then consider a Turing machine that on input $(x,n)$, runs $T$ on $x$ for $n$ steps and outputs $x$ if $T$ halts within $n$ steps.
If $L$ is enumerated by some Turing machine $T$, then given $x$, accept it if it appears in the list generated by $T$.


What does "finding an optimal action" for a bandit mean?

In the bandit setting, to each arm is associated an unknown reward distribution. The optimization goal is to find a policy (a series of level pulls) which yields the maximum sum of rewards.

"Finding an optimal action" thus refers to the process of discovering the arm which gives you the most reward.


How to solve $T(n)\leq n^2+n\left[T(n-m)+T(m-1)\right]$?

On the one hand, we have
$$
\begin{align*}
T(n) &\geq n^2 + nT(n-1) \\ &\geq n^2 + n(n-1)^2 + n(n-1) T(n-2) \\ &\geq n^2 + n(n-1)^2 + n(n-1)(n-2)^2 + n(n-1)(n-2)T(n-3)
\end{align*}
$$
and so on. Assuming, for simplicity, a base case of $T(0) = 0$, this gives
$$
\begin{align*}
T(n) &\geq n^2 + n(n-1)^2 + n(n-1)(n-2)^2 + \cdots + n(n-1)\cdots (1)^2 \\ &=
n! \left(\frac{n}{(n-1)!} + \frac{n-1}{(n-2)!} + \cdots + \frac{1}{0!} \right) \\ &=
n! \left(n + \frac{1}{(n-1)!} + \frac{1}{(n-2)!} + \cdots + \frac{1}{1!}\right) \\ &=
n! \left(n + e - 1 \right) - O(1).
\end{align*}
$$
This should also work as an upper bound. To prove this rigorously, choose an upper bound $S(n)$ for which you can prove $S(n) \leq n^2 + n(S(n-1) + S(0))$ as well as that $S(n)$ is convex. Convexity will ensure that the values of $m$ maximizing the sum $S(n-m) + S(m-1)$ are $m=1$ and $m=n$.


Why does coNP⊆NP∖P imply that the polynomial hierarchy collapses?

I believe the claim is more commonly written as $coNP \subseteq NP/poly$, but that of course does not immediately answer your question.

The fact that this implies that the polynomial hierarchy collapses is shown in Theorem 2 here:

Chee-Keng Yap. Some consequences of non-uniform conditions on uniform
classes. Theoretical Computer Science, 26:287–300, 1983. doi:10.1016/
0304-3975(83 ) 90020-8

If I understand correctly, $coNP \subseteq NP/poly$ is shown to be equivalent to $coNP/poly = NP/poly$ (unnamed corollary on page 292), and this would then imply $\Pi_3 = \Sigma_3$ (Theorem 2), implying collapse of the further hierarchy. For an actual proof, if you have access to the paper, I'll refer you there, I am not familiar enough with it to attempt an explanation now.

On an unrelated note, I believe the paper you are citing to be incorrect (but that would probably warrant a separate question?)


Proving that the reversal of a language reversal is that language

Well, we don't really need induction here.

We want to prove that for any language $L$ holds the statement

$$\left( L^R \right)^R = L.$$

(1) Let $s \in \left( L^R \right)^R$.
Then there exists a (unique) string $t \in L^R$, such that $s = t^R$.
The situation is analogous with $t$: there exists a (unique) string $u \in L$ such that $t = u^R$.
From that we get $s = t^R = \left( u^R \right)^R = u$, so $s \in L$.

(2) Let $s \in L$. Observe that $s^R \in L^R$ and $\left( s^R \right)^R \in \left( L^R \right)^R$, again using the fact that $s = \left( s^R \right)^R$ we get that $s \in \left( L^R \right)^R$.

From (1) and (2) follows the statement of the theorem.


Which of the following statements are true for the given special cases of the Traveling Salesman Problem?

Statement 1 is false (assuming P $\neq$ NP) because any instance $G$ of the NP-complete Hamiltonian Cycle problem can be reduced to an instance of the TSP in which every edge cost is either 1 or 2.

Why? Define a TSP instance on a complete graph $K_n$, with edge cost 1 whenever the corresponding edge is also in the original graph $G$, and edge cost 2 otherwise. Now a TSP tour of cost $\le n$ exists in the complete graph if and only if $G$ has an Hamiltonian cycle.


Can two free variables in lambda calculus have different values?

$y$ is free in the term you have given, so it is indeed the same variable.

You would not have the same variable in case $y$ was bound by the lambda. That would be the case, for example, if the term were to be $(\lambda y.xy)y$; then the rightmost $y$ would be free, but the one in $xy$ would be bound by lambda and, hence, a different variable.


These are basically two different perspectives or two different ways of viewing the running time.  Both are valid (neither is incorrect), but $O(b^d)$ is arguably more useful in the settings that typically arise in AI.

In the algorithms community and CS theory community, folks there tend to like to count the running time as a function of the number of vertices and edges in the graph.  Why?  In that context, worst-case running time is what makes most sense; also, in the problems that are typically considered in that community, in the worst case we need to examine the entire graph, so you typically can't hope to do better than $O(|V|+|E|)$.

In the AI community, folks tend to count the running time differently.  They often consider a specific kind of graph: a tree with branching factor $b$.  Also, in the situations that arise there, the graph is often infinite or very large.  Typically we try hard to avoid examining all of the graph -- that's often one of the major goals of the algorithms.  Thus, counting complexity in terms of $|V|$ and $|E|$ doesn't make sense: $|V|$ may be infinite, and in any case, we don't plan on examining all of the graph, so all that matters is the number of vertices we actually visit, not the number that may exist elsewhere but that we don't care about.

So, for the situations that often arise in the AI community, it's often more meaningful to measure the running time in terms of the branching factor of the tree ($b$) and the depth of the goal node ($d$).  Typically, once we find the goal node, the algorithm stops.    In such a tree, if we examine every vertex at depth $\le d$ before we find the goal node, we'll end up visiting $O(b^d)$ vertices before we stop.  Thus, if you like, you could think of this as visiting a subset of the graph with $|V|=O(b^d)$ (where now $V$ includes only the vertices we visit) and $|E|=O(b^d)$ ($E$ includes only the edges we look at), and you could think of an $O(b^d)$-time algorithm as one whose running time is $O(|V|+|E|)$... though this is a bit of an abuse of the $|V|,|E|$ notation.   Anyway, hopefully you can see why $O(b^d)$ is more informative than $O(|V|+|E|)$ in this context.


What you ask is impossible, assuming you don't really mean sets (as sets are orderless), but ordered tuples. Consider $j=2$, then you effectively have $k$-length binary strings. And those require $\Omega(k)$ storage.


Algorithm for finding largest subset with equal number of even and odd elements

Here's an easy linear time solution which uses $O(n)$ space. You could probably bring this down to $O(1)$ space using the techniques you mentioned.

First compute
$$ D_i = \# \text{even integers among $a_1,\ldots,a_i$} - \# \text{odd integers among $a_1,\ldots,a_i$}. $$
You can do this in $O(n)$.

Second, for each $\Delta \in \{-n,\ldots,n\}$, compute $a_\Delta = \min \{ i : D_i = \Delta \}$ and $b_\Delta = \max \{ i : D_i = \Delta \}$ (possibly these are undefined). You can do this in $O(n)$.

Finally, compute $\max_\Delta b_\Delta - a_\Delta$ for all $\Delta$ for which these indices exist. This also takes $O(n)$.


Why sum of two binary numbers cannot be determined in $NC^0$ but in $AC^0$?

In an $\mathsf{NC^0}$ circuit, every output bit depends on a bounded number of input bits. But the $k$th bit of the output (counting from the LSB) depends on the first $k$th bits of each input.

To see that $\mathsf{AC^0}$ circuits can compute addition, we need to produce such a circuit. Hopefully you have seen such circuits, and otherwise perhaps you can construct them on your own. Give it a shot.


Is there a name for the "tree" aproach to listing things?

Your technique is known as exhaustive search (with some pruning). It consists of trying all possibilities. In many cases, the way to implement exhaustive search is using a search tree. There are several possible optimizations:

Tree pruning algorithms like A* avoid going through paths which are known to be suboptimal.
Greedy algorithms, when they apply, are able to make the correct choice at each step without going over all possibilities.
Dynamic programming corresponds, morally, to exploring a DAG instead of a tree, thus reducing the number of vertices explored. (The actual details are rather different.)


Help with understanding Simulated Annealing algorithm

The variable $T$ is not a timer but the temperature. It starts very high, making it more likely that transitions are taken, and then slowly cools. It's called annealing due to the metallurgical technique of the same name.

Simulated annealing handles one problematic aspect of the hill climbing algorithm, namely that it can get stuck at a local optimum which is not a global optimum. Instead of getting stuck, simulated annealing offers a way out: if the proposed change only marginally deteriorates the objective function, then with some reasonable probability with make it anyway. This way we can escape local optima.

As the process proceeds, we increase the threshold of making unfavorable changes by decreasing the temperature; when the temperature is zero, simulated annealing is the same as hill climbing (and when the temperature is infinite, it is the same as a random walk). The idea is that at first we need to escape local optima more vigorously, but eventually we settle at a good solution which does not require as much tinkering with (except for hill climbing).

You mention that hill climbing always chooses the best neighbor, but this is only one version of the algorithm, and not necessarily the best one. In other versions we choose an improving neighbor in some other fashion. I don't have much intuition which approach is better, though you are right that choosing the best neighbor sounds like a reasonable heuristic.


Finite automaton whose alphabet is $\mathbb{N}$

In the standard definition of a finite automaton (say a DFA or an NFA), the alphabet is a non-empty finite set (perhaps the empty set is allowed by some definitions). The reason we insist that the alphabet be finite is that otherwise the description of the automaton would potentially not be finite.
For example, in one common definition of DFAs, the transition function is a function from $Q \times \Sigma$ to $Q$, where $Q$ is the set of states. If $\Sigma$ is infinite, then describing the transition function would require us to list infinitely many values of the transition function.
Some definitions of DFA allow the transition function to be partial, and in that case, we could have an automaton with a finite description even when the alphabet is infinite; and the same always holds for NFAs. However, in such cases all words accepted by the automaton belong to $\Delta^*$ for some finite $\Delta$, and so the effective alphabet is finite.

While the usual definition requires $\Sigma$ to be finite, the definitions of DFA and NFA still make sense even for infinite alphabets. However, if you keep the set of states finite, then you can find a partition of the alphabet into finitely many subsets $\{\Sigma_\sigma : \sigma \in \Delta\}$ so that the language accepted by the automaton behaves as a language over $\Delta$, in the sense that whether a word is accepted or not depends only on which partitions $\Sigma_\sigma$ its letters belong to (that is, it is obtained from a language over $\Delta$ by applying the inverse of the homomorphism mapping all letters in $\Sigma_\sigma$ to $\sigma$).
Allowing infinitely many states doesn't really change the picture: if the set of states is allowed to have the same cardinality as the alphabet, then all languages are regular, and otherwise the "effective alphabet" has the same cardinality as the set of states (as in the case considered above), and all languages over that alphabet can be accepted.
This shows that even from a theoretical perspective, the most interesting case is that of finitely many states and ("without loss of generality") finite alphabet.


Given two formulae E[G F p] (which is CTL*) and EG EF p ( which is a CTL) with a Model prove that they are not equivalent

Consider a system with 3 states, $s_1,s_2,s_3$ and the following transitions:
$s_1\to s_1$, $s_1\to s_2$, $s_2\to s_3$ and $s_3\to s_3$.

The state $s_2$ is labelled $p$.

Clearly $E[GF p]$ doesn't hold, since every path from $s_1$ has at most one $p$.

However, there exists a path, namely $s_1^\omega$, such that in every state along this path, i.e. in $s_1$, there exists a path that eventually sees $p$, so $E G EF p$ does hold.


What is a lay explanation for universal search?

Think of it like this.  You have a problem, with input $x$ and you know how to verify a solution if you ever found one (like the inverse of a matrix or whatever you'd like to imagine).

Now, take your favourite programming language (say Python), and create every single Python program consisting of at most 10 characters!  Then you run all those programs with your input for 10 seconds each, each on input $x$.  If none of them give you the answer, you go all the way to 11.  Run each program of at most 11 characters (including the ones you already tried, of course) for 11 seconds each, on input $x$.  If none of them give you the correct answer, you continue to 12 and so on.

More formally, in iteration $i$, you run all programs of length at most $i$ (finitely many, but of course exponential in $i$), each for $i$ seconds (or steps).

There is a program, say $P$ that gives the correct output in $s$ seconds.  When you have come to iteration $i = \max\{|P|, s\}$, this program will be run for at least $s$ seconds, and you will output both $P$ and the solution.


How do we determine how much time a multi-tape DTM saves over a one-tape DTM?

As this is homework, I'll go for the gentle hint approach. Firstly, it's a bit odd to talk about a TM using an algorithm - a TM is an algorithm, so my interpretation of the question is:

Given a multitape TM, you want to produce a single tape TM that does the same job (i.e. has the same language), and you want to know how much slower the single tape version is (in the worst case).

To put it another, hint laden way, how much slower is it to simulate a multitape machine with a single tape machine?

There's a rather important result regarding this (i.e. there's a way to do it that guarantees an upper bound on the slowdown factor), a little searching should get you that at least.


Color a graph using k colors, k>4, with the most equal distribution of colors

You are perhaps looking for an equitable coloring, which is a proper coloring where the size of any two color classes differ by at most one. Finding an equitable 3-coloring is NP-complete for planar graphs.


complexity of dividing set of number with constraints

The difficulty of your problem heavily depends on "constraint".
For example if $n=3k$, $\text{size}=[\underbrace{3,3,3,...}_{k\text{ times}}]$, and the constraint is that the sum of the numbers each group must be equal, then your problem is strongly NP-hard since it is exactly $3$-partition.
The same problem with groups of size $2$ is polynomial.
Notice that both problems are in $\mathsf{NP}$ and that being in $\mathsf{NP}$ does not mean that the complexity to solve it is exponential.


HashTable open-addressing is used for main array or buckets

Open addressing is a method for handling collisions. Another method is chaining, in which we have lists at our table indices, like you say.

In other words, open addressing means that all elements are stored inside a single table. In particular, to resolve a collision, the probing sequence finds a free slot in our table.


Need help understanding regular expressions

There are three standard regular expression operators: concatenation, alternation, and Kleene closure. (Note that we're talking about regular expressions in the formal mathematical sense, not the random collections of hacks which comprise typical regex libraries.)

These can be thought of as operators on (possibly infinite sets); alternation is set union, and concatenation of two sets is the Cartesian product; in this sense,
alternation and concatenation correspond to addition and multiplication. Alternation is generally written as $+$ (although $\mid$ is also common, because of its use in regexes) while concatenation is generally written without an explicit operator symbol, much the same as mulitiplication.

Kleene closure is a unary operator which produces the arbitrary application of any number of concatenation operations on the same set; in effect, an arbitrarily long concatenation of elements of the set. (It includes 0 concatenations, which is always the empty string.) Kleene closure is always written as a postfix $^*$.

As with algebra, there is a standard operator precedence; Kleene closure binds the most tightly, followed by concatenation, followed by alternation. If you need different binding, you can use parentheses. So $ab^*+cd^*$ should be read as $(a(b^*))+(c(d^*))$, much as you would read the algebraic expression $ab^2+cd^2$

So the expression you ask about:

$$0(0+1)^∗+(0+1)^∗0$$

is the union of two subexpressions: $0(0+1)^∗$ and $(0+1)^∗0$. The first of these is any binary string starting with $0$ and the second is any binary string ending with $0$, so the union is any binary string which starts or ends with $0$; in other words, any binary string which doesn't both start and end with $1$.


Can a language recognized by a NFA be recognized by a push down or Turing machine?

A language is recognized by an NFA iff it is regular. It is recognized by a push-down automaton iff it is context-free. It is recognized by a Turing machine iff it is computable. Every regular language is context-free. Every context-free language is computable.

Even without knowing these facts, it is not difficult to simulate an NFA by a push-down automaton and a DFA by a Turing machine.


Is this lower bound proof for the comparison-based sorting problem correct?

No, I don't think it's a reasonable proof.  This makes claims without justification.  For instance, the second bullet says that the only way to put an element into its final position is (the algorithm must know something..).  How do you know that is correct?  How would you prove that?  What does it even mean for an algorithm to know something?  Why does knowing that cost at least $\Omega(\lg i)$ comparisons?  All of that seems a bit unclear to me, so I don't find it a persuasive proof.


This problem is known as the “minimum common string partition problem.”  (More precisely, the answer in the minimum common string partition problem equals the answer in your problem plus 1.)  Unfortunately, it is NP-hard, even with the restriction that each letter occurs at most twice in each of the input strings, as is proved by Goldstein, Kilman, and Zheng [GKZ05].  This means that no polynomial-time algorithm exists unless P=NP.  (Of course, if each letter occurs at most once, then the problem is trivial because there is only one anagramming.)

On the positive side, the same authors [GKZ05] give a polynomial-time 1.1037-approximation algorithm under the same restriction.  (A “1.1037-approximation algorithm” means an algorithm which may not output the correct answer A but is guaranteed to output a value B such that A ≤ B ≤ 1.1037A.)  They also give a linear-time 4-approximation algorithm under the weaker restriction that each letter occurs at most three times in each of the input strings.

[GKZ05] Avraham Goldstein, Petr Kolman, and Jie Zheng.  Minimum common string partition problem: Hardness and approximations.  Electronic Journal of Combinatorics, 12, article R50, 2005.  http://www.combinatorics.org/ojs/index.php/eljc/article/view/v12i1r50


Is 3-colouring NP-hard for 5-colourable graphs?

Yes, and this holds even for structured graphs. Indeed, every planar graph is 5-colorable (in fact even 4-colorable by the Four color theorem), but it is NP-complete to decide if a planar graph can be colored in 3 colors.


Find the smallest binary digit multiple of given number

No idea where you got that 9 from, in the last line of the question.

Having said that, You have to know that "concatenating" numbers is equivalent to multiplying the first number by a power of 10, followed by adding the second number. E.g. 42|7 = (42*10)+7.

Now obviously 42 is divisible by 6, but therefore so is 420. Furthermore, 42 mod 5 = 2, therefore 420 mod 5 = 20 mod 5. "42 is divisible by 6" in fact means "42 mod 6 = 0"


Consider the set of all possible pairs $ \langle M, w \rangle$, where $M$ is a Turing machine and $w$ is some string on a fixed alphabet. Also note that some $M$ may halt on input $w$, and some may not.

Basically, the Halting problem asks to create a Turing machine that takes a pair $ \langle M, w \rangle$ as input, and eventually halts with answer "YES" if $M(w)$ halts, and "NO" if $M(w)$ does not halt.

If you are familiar with programming you could interpret this problem as following. The Halting problem asks you to write a C++ program which reads another target program together with its input written in C/C++, and always stops and prints "YES" if the target program eventually stops on the input,  and prints "NO" otherwise. Note that your program must work for any finite size of target program and any finite size of input.

As for its history, this is one of famous David Hilbert's 23 questions posed in 1900 at the Second International Congress of Mathematicians in Paris, and later in 1936 was solved by Alan Turing to show that such algorithm deciding on all possible pairs $ \langle M, w \rangle$  cannot exist.

This Wikipedia article provides a formal definition of the problem and sketch of proof.


The downside of your algorithm is that you need to allocate enough space to hold pointers to all the elements in the list. This requires knowing the length of the list (which would need traversing it once to count) and you may not have enough memory to get a contiguous space for it.

A variation of classic merge sort will work a lot better for linked lists:

Have a array of $\lceil \log_2 n \rceil$ linked lists initially empty. (or just fix to size 64 because when are you ever going to need to sort anywhere near $2^{64}$ elements).

For each element in the original list you extract it into a single element list and do the following:

for the first list in the array if a list is already there merge the list into that list and remove the list from the array and repeat for the next list in the array.

otherwise move on to the next element in the original list.

Once you've done the last element of the list you merge the lists in the array starting from the lowest index.

This is the algorithm used for linked lists in the linux kernel. And has a few handy features:

no allocations needed, no recursion, so no chance of an out of memory situation.
you only walk the original list once.
the merge passes except the final ones are all with lists of equal length. This means there are few unbalanced passes which would have more traversing of the longer list than actually merging the two lists together in.


How can a Turing machine write the description of the n-th Turing machine?

The question is probably assuming that there is some arbitrary but agreed-upon convention that specifies how to write a Turing machine description with the symbols of some alphabet. Since all Turing machines have by definition a finite description, all valid outputs will be finite strings.

The exercise itself is an ordinary combinatorics problem.


What does the halting problem mean for a Babbage machine?

No. The undecidability of the halting problem for a particular model of computation means that there's no algorithm that takes as input a description of an arbitrary machine $M$ in that model and an input $x$ and determines whether $M$ halts when run with input $x$.

As a consequence, there's no algorithm that takes as input a description of a machine and determines whether that machine computes logarithms. However, that doesn't mean that you can't prove that a specific machine computes logarithms. Indeed, people do this all the time, as exemplified by Knuth's famous quote, “Beware of bugs in the above code; I have only proved it correct, not tried it” (emphasis mine). Proving the code correct requires proving that it terminates and computes the thing it's supposed to compute.


String edit distance between strings x, y, with restrictions on 'intermediary' strings

I think your approach has merit, but you want to limit the amount of searches on $V$.

Model $V$ as a graph and connect all nodes whose strings have Hamming distance one. Then you connect $x$ and $y$ with all nodes at Hamming distance one, respectively.

Now the problem is just finding a shortest path from $x$ to $y$.


Finding Second large element from a set of 4 element

It is known that the exact number of comparisons needed to find the second largest element out of $n$ elements is exactly
$$
n-2+\lceil \log_2 n \rceil.
$$
See for example Jeff Erickson's notes. In our case, this gives $4-2 + \lceil 2 \rceil = 4$ comparisons.

Here is a matching algorithm for $4$ elements. Let the elements be $a,b,c,d$, which we assume to be distinct for simplicity.

Compare $a$ and $b$. Without loss of generality, $a > b$.
Compare $c$ and $d$. Without loss of generality, $c > d$.
Compare $a$ and $c$. Without loss of generality, $a > c$.
Compare $b$ and $c$, and return the maximum.

More generally, if $n$ is a power of $2$, here is how to find the second largest element in $n-2+\log_2 n$ comparisons. First you form a "tournament" by comparing the elements in pairs, then comparing the winners in pairs, and so on, until you find the maximum. This takes $n-1$ comparisons. Then you find the maximum among all $\log_2 n$ elements which "lost" to the maximum, using $\log_2 n - 1$ comparisons.

If $n$ is not a power of $2$ then you add dummy elements with value $-\infty$ to pad the list to the closest power of $2$, and proceed as before. The first phase will take only $n-1$ comparisons (since comparisons with dummy elements need not be performed), and the second will take $\lceil \log_2^n \rceil - 1$ in the worst case (depending on the number of dummy elements which "lost" to the maximal element).


If these computations appear in a paper for me to review, I would like to ask the author to rewrite.

  $$\exp(-x^2/2)\leq \exp\left(-K_1\log n^{c+1/2\,}\right), \text{ where } K_1>0$$

This is wrong. The direction of inequality should be switched. For example, let $n\to\infty$ and $x$ be constant 1, the left hand side remains a constant while the right hand side goes to 0. This error means "Computation 2" is wrong from the start.

  The last quantity $n^{-O(1)}$ represents the set of polynomially-bounded functions.

Instead of $n^{-O(1)}\,$, $n^{O(1)}$ represents asymptotically the set of polynomially-bounded functions.


Is there any use case for the bottom type as a function parameter type?

One of the defining properties of the $\bot$ or empty type is that there exists a function $\bot \to A$ for every type $A$. In fact, there exists a unique such function. It is therefore, fairly reasonable for this function to be provided as part of the standard library. Often it is called something like absurd. (In systems with subtyping, this might be handled simply by having $\bot$ be a subtype of every type. Then the implicit conversion is absurd. Another related approach is to define $\bot$ as $\forall \alpha.\alpha$ which can simply be instantiated to any type.)

You definitely want to have such a function or an equivalent because it is what allows you to make use of functions that produce $\bot$. For example, let's say I'm given a sum type $E+A$. I do a case analysis on it and in the $E$ case I'm going to throw an exception using $\mathtt{throw}:E\to\bot$. In the $A$ case, I'll use $f:A\to B$. Overall, I want a value of type $B$ so I need to do something to turn a $\bot$ into a $B$. That's what absurd would let me do.

That said, there's not a whole lot of reason to define your own functions of $\bot\to A$. By definition, they would necessarily be instances of absurd. Still, you might do it if absurd isn't provided by the standard library, or you wanted a type specialized version to assist type checking/inference. You can, however, easily produce functions that will end up instantiated to a type like $\bot\to A$.

Even though there isn't much a reason to write such a function, it should generally still be allowed. One reason is that it simplifies code generation tools/macros.


In a single cycle datapath, do 'decode' and 'operand fetch' occur simultaneously?

Figured it out. The control unit and register file are accessed one after the other. So the total delay would be 160ps.


One approach could be to use least-squares fitting.

Your problem is: given functions $f_1,\dots,f_N$ and $f$, we want to find constants $\alpha_1,\dots,\alpha_N$ such that

$$f(x) \approx \sum_i \alpha_i f_i(x).$$

Here

$$f(x) = e^{\frac{-\|x-c\|^2}{2\sigma^2}}$$

and

$$f_i(x) = e^{\frac{-\|x-c_i\|^2}{2\sigma^2}}.$$

To make this problem well-defined, we need to make precise the notion of approximation.  One plausible notion is the $L_2$ error of the approximation, i.e., the error is

$$E = \int \big( f(x) - \sum_i \alpha_i f_i(x) \big)^2 \; dx.$$

This is tricky to compute, but we can approximate $E$ by picking values $x_1,\dots,x_m$ and then calculating

$$\hat{E} = \sum_j \big( f(x_j) - \sum_i \alpha_i f_i(x_j) \big)^2.$$

If the $x_j$'s are chosen appropriately (e.g., evenly spaced over the range you care about; or randomly chosen according to the distribution of $x$-values you're likely to evaluate the approximation at), and if $m$ is large enough, then $\hat{E}$ should be a good approximation to $E$.

So, the problem becomes: given functions $f_1,\dots,f_N$ and $f$ and values $x_1,\dots,x_m$, we want to find constants $\alpha_1,\dots,\alpha_N$ that minimize the error $\hat{E}$.

This turns out to be exactly a multiple linear regression problem.  We try to find a fit

$$z = \alpha_1 y_1 + \dots + \alpha_N y_N$$

where $y_i = f_i(x)$ and $z = f(x)$.  We can evaluate the $f_i$'s and $f$ at any input $x$ of our choice.  When we evaluate at $x_j$, we obtain a single input $(y_1,\dots,y_N)$ and a single output $z$; in this way, we obtain $m$ matching input-output pairs.  You can now use a standard library to solve this multiple linear regression problem and find $\alpha_1,\dots,\alpha_N$.

All that remains is to choose $m$ and $x_1,\dots,x_m$.  I would suggest that you try to figure out what values you'll evaluate the approximation on, and choose the $x_j$'s randomly from the distribution (it might be a uniform distribution over some range, or something else), or choose the $x_j$'s to be evenly spaced over some range.  The larger $m$ is, the better the approximation will be, but the longer the algorithm will take, so experiment with some different values of $m$ and see what the tradeoff is.  My guess is you'll want $m$ to be a small constant multiple of $N$ (say $m=2N$), but you can see what you get.

Since you said $N$ is small (8--16), this should be very fast.

An optimization: Since you're going to repeat this many times with the same values for $c_1,\dots,c_N$ (i.e., $f_1,\dots,f_N$) but a different value of $c$ each time, you can also speed things up.  If the matrix is $X$ and the vector is $y$, the solution is $(X^\top X)^{-1} X^\top y$, where $X$ depends only on the $c_i$'s but not on $c$.  Thus, you can precompute the matrix $(X^\top X)^{-1} X^\top$ (once), then for each instance of the problem you want to solve, you just have to do a matrix multiplication -- no need to solve a new linear system.

Lastly, one optional refinement you could also try: use multiple linear regression to choose $\alpha_i$'s, then follow that up with gradient descent to fine-tune the $\alpha_i$'s and improve the quality of the approximation.  Often if you choose a good starting point that is close to optimal, gradient descent will converge faster.  Thus you can use the solution from multiple linear regression as the starting point for the gradient descent optimization routine.


Probability of Attaining the/a Global Optimum

No, you can't infer that.  You seem to be assuming that the optimization process tries one element of the search space, chosen uniformly at random, and hopes that it got lucky.  But that's not how real optimization algorithms work.  They try multiple solutions, and they're not chosen uniformly at random; they're typically chosen in some way that we hope is more likely to hit a good solution.
In general, you cannot conclude anything about the probability of hitting the optimum after some amount of optimization, without further information.  The probability might be much larger than $N/|S|$ (e.g., if the optimization problem is easy or the optimization algorithm is effective on this kind of problem).
In the kinds of optimization problems we typically use a computer to solve, often you can't just "plot it out" as often we're working with a multidimensional search space.


How does the equation for min heap array indexing work?

Start indexing at $1$, then everything will be fine.

Want to start at $0$? That is no problem, but one has to adjust the formula's. Children of $x$ can be found at $2x+1$ and $2x+2$.


Problems Implementing Closures in Non-functional Settings

May I direct you to the Funarg problem wikipedia page? At least this is how the compiler people used to reference the closure implementing problem.

  So a closure is essentially a (anonymous?) function value which can use variables outside of its own scope. In my experience, this means it can access variables that are in scope at its definition point.

While this definition makes sense, it does not help describe the problem of implementing first-class functions in a traditional runtime-stack based language. When it comes to implementation issues, first class functions can be roughly divided into two classes:

Local variables in the functions are never used after the function returns.
Local variables can be used after the function returns.

The first case (downwards funargs) is not that hard to implement and can be found on even the older procedural languages, like Algol, C and Pascal. C kind of skirts the issue, since it does not allow nested functions but Algol and Pascal do the necessary bookkeeping to allow inner functions to reference the stack variables of the outer function.

The second case (upwards funargs), on the other hand, requires activation records to be saved outside the stack, in the heap. This means that it is very easy to leak memory resources unless the language runtime includes a garbage collector. While almost everything is garbage collected today, requiring one is still a significant design decision and was even more so some time ago.

As for the particular example of Java, if I remember correctly, the main issue was not actually being able to implement closures, but how to introduce them to the language in a way that was not redundant with existing features (like anonymous inner classes) and that did not clash with existing features (like checked exceptions - a problem that is not trivia l to solve and that most people don't think of at first).

I can also think of other things that make first class functions less trivial to implement, such as deciding what to do with "magical" variables such as this, self or super and how to interact with existing control flow operators, such as break and return (do we want to allow for non-local returns or not?). But in the end, the recent popularity of first-class functions seems to indicate that languages that don't have them mostly do so for historical reasons or due to some significant design decision early on.


How to show all false outputs in a circuit?

First you can write down the truth table of your circuit, in this case it will be entirely composed of $0$s.
Then you will build up a Boolean expression in the form you prefer (if you have no limitations) which reproduces the behavior (relation input/output) observed in the truth table.

Note that every operator of your boolean expression correspond to a logic gate:

$\land$ = AND

$\lor$ = OR

$\neg$ = NOT

$\oplus$ = XOR


Algorithm to distribute elements evenly among a population

Traditionally, this kind of problem is described as a fractional factorial design problem. However, your problem also can be elegantly solved via a probabilistic / statistical method that exploits the power of low discrepancy sequences.

For additional context, this method can be applied to very similar questions as yours, such as:

Random but even distribution of AB vs BA
How to shuffle coloured balls

Low Discrepancy Sequences

Low discrepancy sequences, (often described as quasirandom sequences) are numbers that generally appear random, but have an underlying structure to them that makes them more evenly distributed and so have less 'gaps' and 'clumping'.

There are many ways to construct low discrepancy sequences, and they can be generalised to arbitrarily high dimensions, too. For example, below is a picture of the first 100 terms of five different low discrepancy sequences in two dimensional and how they compare to simple random sampling. Note that all of them are substantially more evenly distributed than the conventional uniform random sampling.

Further details can be found at the Wikipedia article: "Halton Sequence".

Equidistributed Allocation

A post I wrote, "The unreasonable effectiveness of quasirandom sequences" , describes how to easily create an efficient extensible $d$-dimensional low discrepancy sequences. (For this particular case, we need a $d=3$ dimensional sequence.)

Define an $n$ x $3$ dimensional array, where each of the $n=200$ rows represents a different trial, and each of the components of each 3-vector defines which type of variety to use for each of the $d=3$ categories.

For $d=3$, there is one magical number involved which is $ \phi_3 = 1.2207440846... $ (see the article if you are interested in what is so special about this number).

Now simply define for all integer $n$, a 3-dimensional vector $\pmb{t}_n$ such that:
$$ \mathbf{t}_n = \pmb{s} + n \pmb{\alpha}  \; (\textrm{mod} \; 1),  \quad n=1,2,3,... $$
$$ \textrm{where} \quad \pmb{\alpha} =(\frac{1}{\phi_3}, \frac{1}{\phi_3^2},\frac{1}{\phi_3^3}).$$

In nearly all instances, the choice of initial seed $\pmb{s} $ does not change the key characteristics, and so for reasons of obvious simplicity, $\pmb{s} =\pmb{0}$ is the usual choice. (I have included it in this definition, because if you wish to create another sampling distribution, all you need to do is re-run the code but with a different starting seed!)

Specifically for $d=3$; with $\phi_3 = 1.2207440846$ and $\pmb{s}= (0.5,0.5,0.5) $,  the first 5 terms of this sequence are:

(0.319173, 0.171044, 0.0497005)
(0.138345, 0.842087, 0.599401)
(0.957518, 0.513131, 0.149101)
(0.77669, 0.184174, 0.698802)
(0.595863, 0.855218, 0.248502)
...

Now consider the first component $x_n$ of each vector $t_n$, to represent the first category ("Maize"). (ie  $x_1 = 0.319173$). If

$ 0 \leq x < 1/7$, then select Maize, option A
$ 1/7 \leq x < 2/7$, then select Maize, option B
$ 2/7 \leq x < 3/7$, then select Maize, option C
...
$  6/7 \leq x < 1$, then select Maize, option G

Similarly, consider the second component $y_n$ of each vector $t_n$, to represent the second category ("Fertilizer"). If

$ 0 \leq x < 1/4$, then select Fertilizer, option A
$ 1/4 \leq x < 2/4$, then select Fertilizer, option B
$ 2/4 \leq x < 3/4$, then select Fertilizer, option C
$  3/4 \leq x < 1$, then select Fertilizer, option G

Summary

The beautiful result of this low discrepancy method is that, for any $n$, the number of varieties allocated in each category will not differ by more than 1.

Said another way, the number of samples for every variety and every category, will never be more than 1 away to the ideal equal allocation method.

Code

Python code to create the low discrepancy sequences is

# Use Newton-Rhapson-Method
def gamma(d):
    x=1.0000
    for i in range(20):
        x = x-(pow(x,d+1)-x-1)/((d+1)*pow(x,d)-1)
    return x

d=3
n=200

g = gamma(d)
alpha = np.zeros(d)
s=0.5  # initial seed.

for j in range(d):
    alpha[j] = pow(1/g,j+1) %1
z = np.zeros((n, d))
for i in range(n):
    z = (s + alpha*(i+1)) %1

print(s)
print(z)

Hope that helps!


Why a TM with infinite states can decide the halting problem?

If you are allowed infinite states and transition functions, then even a DFA could solve the halting problem (and in fact, any language). In this case, the DFA/TM can basically have a state for each possible pair of TM + word. If a certain state represents a pair where the TM halts on the word it would be an accepting state.

Notice that I don't give a constructive algorithm of how to build this TM/DFA, but it could easily be seen that such a TM theoretically exists and therefore decides the halting problem.

EDIT - more detail regarding the last point: by definition, a language is regular if there exists some DFA accepting it, even if we don't know how to build that DFA. If we allow infinite states, than all languages will be regular. The infinite-state-DFA I described above may seem confusing because we have no idea how to construct it, and in particular, how to choose which states are accepting and which aren't. However, it definitely still exists!

Another way to think about it is that the states of the DFA can be computed/built in "compile-time" and therefore we don't need to figure out whether a TM stops on a word in "run time". We determine what is accepting and what isn't before we even get any input, and when we do get an input, we will definitely halt on it because of the nature of DFAs. We don't need to simulate a TM on an input during the DFAs run!

Lastly, I want to emphasize that the confusion regarding DFAs which we have no algorithm to construct is valid even using the standard, finite-state model of DFAs. If we denote the halting problem by $H_{TM}$, then for all $n$, the language $H_n:=H_{TM}\cap \{0,1\}^n$ is a finite language and therefore regular! However, it can be proved that there is no general algorithm that takes $n$ as an input constructs a DFA for $H_n$, since otherwise we could decide the halting problem.


Standard OCR software already incorporates this idea: it has a corpus of words, along with their frequency of occurrence, and uses this to correct  errors.

How does it work?  OCR doesn't just output a letter at each position; it actually produces a probability distribution on letters.  For example, its output might be something like: I'm 99% sure the first letter is a 'h'; I'm 60% sure the second letter is a 'u', but there's is a 20% chance it is a 'o', and a 15% chance it is an 'a', and so on.  This lets you consider many possibilities for what the word might be, and combine the probabilities from the OCR with the frequency of occurrence of that possibility in English text to come up with an educated guess about what the actual word is.

For instance, if the OCR says "5% chance this is 'hurze", 2% chance this is 'horse'", and you know that 'horse' occurs 100x more often than 'hurze' in English language, you should guess that the corresponding word is probably 'horse', not 'hurze'.

As Yuval Filmus says, another approach is to look for a dictionary word that is within edit distance 1 or 2 of the raw output from the OCR.

If your OCR software is any good, it might already be doing this sort of correction.  Sometimes you can give the OCR software a custom dictionary of words that tend to appear in your documents, to help it do this sort of correction.


You seem to be right. But as Raphael says, be careful.

Statement 1. Note that the $L_2$ is defined using the enumerating algorithm $\cal E$ for $L_1$, not by $L_1$ itself. To decide whether $u\#v \in L_2$, decide whether both $u,v$ in $L$, and if confirmed run the enumerator $\cal E$ and see whether $u$ is output before $v$. As we know both strings are in $L_1$ this will terminate.

Statement 2. If $L_1$ is finite, it is recursive, so we assume $L_1$ is infinite. Run $\cal E$ and wait for first word $w_1$. Now a decider for $L_2$ can be turned into one for $L_1$ as follows. To test $u\in L_1$ first check whether $u=w_1$, and then check $w_1\#u \in L_2$. This is then equivalent to $u\in L_1$ as we do not have to worry about the $i<j$ requirement, which is now true by construction.

I am not even certain we need to know $w_1$ by running $\cal E$: we only want to verify there exists a decider, not whether one can be effectively constructed. That seems impossible.

(edit) Just to note that Raphael has posted a more explicit "implementation" of these suggestions, which avoids possible ambiguities.


Distributed algorithm can be executed in a single process

From Wiki:

  Distributed algorithms are a sub-type of parallel algorithm, typically executed concurrently, with separate parts of the algorithm being run simultaneously on independent processors, and having limited information about what the other parts of the algorithm are doing.

It is inherent type of algorithm to be run independently with no requirement that processors are in the same machine. Think of it as the type of workload being cut into independent pieces.

From Wiki:

  A distributed system is a network that consists of autonomous computers that are connected using a distribution middleware. They help in sharing different resources and capabilities to provide users with a single and integrated coherent network.

So the algorithm is distributed, but the system you have described is not. This is just algorithm with different purpose run in less distributed environment with potential to be sub-optimal in such setting.

Another example: you can run sorting network (say bitonic sort) in one thread, it doesn't make it serial algorithm, but overhead is costly in such case.


Find a regular language that is "infinitely between" two other regular languages

Because regular languages are closed under complement and intersection, $L_2 - L_1$ is regular. Because it's also infinite, it contains words of arbitrarily large lengths.

Therefore, by the pumping lemma, there exist some words $x$, $y$, and $z$ such that the concatenation $x y^k z$ is in $L_2 - L_1$ for all $k \geq 0$.

Now consider the language $L'$ consisting of all words of the form $x y^{2k} z$ - that is, words where the $y$ is repeated an even number of times. Clearly, $L'$ is regular and infinite, and so is $L_2 - L_1 - L'$, since it contains all strings $x y^k z$ where $k$ is odd. Therefore, setting $L_3 = L_1 \cup L'$ satisfies the problem.


What does "refuting random 3CNF" formulas mean?

A random 3CNF with $n$ variables and $m$ clauses is obtained by picking $m$ clauses uniformly at random among the $8\binom{n}{3}$ different clauses. It is known that there exists a constant $C$ such that when $m = Cn$, a random 3CNF is unsatisfiable with high probability; it is strongly suspected that there exists a best such constant $C$, which is known experimentally to be about $4.2$.

It seems, therefore, that if I give you a random 3CNF with $n$ variables and $100n$ clauses, it should be easy to prove that it's unsatisfiable (unless you're very unlucky). However, the best such algorithm, due to Feige and Ofek, only works for $m = \Omega(n^{1.5})$. The best non-deterministic algorithm, due to Feige, Kim and Ofek, only works for $m = \Omega(n^{1.4})$.

One can state many conjectures of the form "refuting random 3CNF formulas is hard". The weakest would state that for every $C > 0$, there is no polynomial time algorithm that, given a formula, answers either unsatisfiable or don't know, and (i) answers unsatisfiable with high probability when given a random 3CNF with $n$ variables and $Cn$ clauses, (ii) answers unsatisfiable only for unsatisfiable formulas.

Stronger conjectures would work for $n^{1+\epsilon}$ clauses for some $\epsilon > 0$, and for non-deterministic polynomial time algorithms.


Given a set of irregular polygons finding a set of vertices (one on each polygon) such that distance between points is maximized

I don't know whether this problem is in P.  Given the similarity to facility location problems, it smells like it might be NP-hard.  However, I can suggest some candidate algorithms.  They break down into two categories: algorithms to get the exact optimal solution, and heuristics to get a pretty-good solution that hopefully will be an approximation to the optimal (but no guarantees).

Exact algorithms

One approach is to convert to a decision problem, and then an algorithm for independent set.  The decision problem is:

Given sets $S_1,\dots,S_k$ of points and a distance $d$, is there a way to choose one point from each set so that no two points are at distance $\le d$ from each other?

(Each $S_i$ represents the set of points in a single polygon.)
Binary search over $d$ lets you convert any algorithm for the decision problem into an algorithm for your optimization problem.

Now form a graph $G=(V,E)$ where $V=S_1 \cup \dots \cup S_k$, and where you have an edge between every pair of points that are at distance $\le d$ from each other.  You are looking for an independent set $v_1,\dots,v_k$ such that $v_i \in S_i$ for all $i$.  There are many approaches for solving such a problem.

For instance, you can express it as a SAT instance, and feed the result into a SAT solver.  You'll have one boolean variable $v$ for each $v \in V$; if $v$ is set to true, then that means you've included $v$ in your set.  Now you have a bunch of clauses of the form $(\neg v \lor \neg w)$ for each pair $(v,w) \in E$, asserting that you don't pick any pair of vertices at distance $\le d$, as well as a clause for each set $S_i$ asserting that you pick exactly one element of $S_i$.

Or, you could express it as an integer linear programming instance, and feed the result into an ILP solver.  You'll have one zero-one variable $v$ for each $v \in V$; add an inequality $v+w \le 1$ for each pair $(v,w) \in E$, along with an equality $x_1+x_2+\dots + x_j = 1$ where $S_1=\{x_1,\dots,x_j\}$ (and similarly for each $S_i$).

Or you could apply an approximation algorithm for independent set, such as the greedy algorithm based on selecting the minimum degree vertex at each step.

The graph $G$ is a geometric intersection graph, so you might be able to use algorithmic ideas customized for that kind of graph.  You'd have to investigate them  for yourself and see if they can be applied to your problem.

Heuristics

One heuristic is to use the Farthest Point First heuristic from clustering.  You pick a point arbitrarily, then pick the point that is furthest from it, then pick a third point that is furthest from these two (maximizes the minimum-pairwise-distance), and repeat.

You'll need to adjust it to your setting, to make sure you don't pick two points from the same polygon.  There are multiple ways to do that, but one simple one is: if you've already picked some subset of points, then discard any remaining ones that are from the same polygon as one of those, and only consider what's left as a candidate for your next point.


Heaps and Heapsort - Find the 7'th biggest value in a min heap by $O(1)$

O(1) means: You need to do this with a fixed number of operations. Basically, write code without a loop. That's not difficult. It's a lot of code, but a fixed amount of code.

Look at your heap as if it was a binary tree. You want the 7th largest item in your tree. That's the sixth largest of the subtrees L and R. If the item at L is smaller than the item at R, it's the fifth largest item in the subtrees L, RL and RR, otherwise the fifth largest item in the subtrees R, LL and LR. And so on..


Minimal Spanning Tree vs Minimum Spanning Tree

A minimum weight edge is an edge whose weight is minimal among all edges. There can be more than one minimum weight edge. All minimum weight edges have the same weight.
Similarly, a minimum spanning tree is a spanning tree whose weight is minimal among all spanning trees. There can be more than one minimum spanning tree. All minimum spanning trees have the same weight.
In some cases, there is a distinction between minimum and minimal. For example, a minimum vertex cover is a vertex cover whose weight is minimal among all vertex covers. In contrast, a minimal vertex cover is a vertex cover, any proper subset of which isn't a vertex cover. Finding a minimal vertex cover is easy – start with the set of all vertices, and repeatedly remove a vertex as long as it is possible to do so while maintaining the property of covering all edges. In contrast, finding a minimum vertex cover is expected to be hard (the corresponding decision problem is NP-hard).
The same property of being minimal doesn't make much sense for edges and spanning trees. When people say minimal edge or minimal spanning tree, they probably mean minimum (weight) edge and minimum spanning tree.


Turing machine that does not halt on any input

To use reduction, you would need to show that the halting problem reduces $T$, not the other way around.

The reduction* in this case is a standard one. You want to know if $M$ halts on input $w$ but all you have is this lousy T-shirt a procedure that tells you if a machine loops on every input. So you construct a machine $M'$ such that does the same thing on every input, so that whether or not $M'\in T$ tells you whether or not $M$ halts on input $w$.

* Well, strictly a reduction: if there's one, there are infinitely many.


Why is the subset of palindromes of a regular language context-free?

Hint: The intersection of a context-free language with a regular language is still context-free.


Applications in Computer Sciences of Partition Functions

there is a connection between partition functions and counting possible edge and vertex colorings in graphs, but its very abstract. see eg Graph parameters and invariants of the orthogonal group, Regts
there are applications of partition functions to simulating Ising models for Spin glasses in physics. spin glasses have been shown to have deep connections to NP complete phase transitions.


Concluding $SPACE(n^2) \neq SPACE(n^7)$ from universal turing machine running time

I assume with ${\sf SPACE}$ you mean ${\sf DSpace}$. As usual for these types of hierarchy question you can use a diagonalization argument.

So build a machine $D$ that takes its input $w$ and then executes $M_u(\langle  w ,w \rangle)$. While executing $M_u$ it checks also how much space is used and how many steps the machine $M_u$ has done. Then the result of $D$ is the following:

if $D$ used more than $n^2$ space than reject,
if $D$ does more than $2^{cn^2}$ steps then accept (in this case the simulation detected a cycle if $\langle w \rangle$ would be a $n^2$ space bounded TM),
if none of the above occurred, then accept if $M_u$ rejected, and reject if $M_u$ accepted.

You can say that $D(w)$ anti-simulates the machine $M_u(\langle w ,w \rangle)$, if $\langle w \rangle$ is in ${\sf DSpace}(n^2)$. Clearly, $\langle D\rangle$ is in ${\sf DSpace}(n^7)$. However, it cannot be in ${\sf DSpace}(n^2)$. If it would be then you get a contradiction at $D(\langle D \rangle)$.


Trying to prove semidecidability of an undecidable language

We know that the halting problem is semidecidable, but the non-halting problem is not semidecidable (since otherwise the halting problem would be decidable). Hence one way to show that a language is not semidecidable is by reduction from the non-halting problem.

Let $\langle M,x \rangle$ be an input the the non-halting problem. We construct a new Turing machine $M'$ which on inputs $1,2,3,4,5$ halts, on input $6$ simulates $M$ on $x$, and on all other inputs never halts. Then $M' \in S$ iff $M$ doesn't halt on $x$.

We can also construct another Turing machine $M''$ which on inputs $1,2,3,4$ halts, on input $5$ simulates $M$ on $x$, and on all other inputs never halts. Then $M'' \notin S$ iff $M$ doesn't halt on $x$.

These reductions show that neither $S$ nor its complement are semidecidable.


What is my error in reasoning about the complexity class $n^{o(1)}$

$n^{o(1)}$ converge to 1 (after all, $n^0=1$ )

You can't take the limit of one part without taking the limit of the other part, that doesn't give any useful information. If you take the limit of both parts, you get $\infty^0$, which is an indeterminate form.

It's easier to reason about exponentials with a constant base.
$$n^{o(1)} = e^{o(1) \cdot \ln(n)}$$
This way you can see that what matters is how fast the $o(1)$ function converges to $0$ relative to a logarithm.


Show that the OR of n variables cannot be expressed as a polynomial over Fp of degree less than n

Let $AND:\{0,1\}^n\mapsto\{0,1\}$ be a polynomial in $GF(q), q\geq 2$.
Notice that the polynomial can't have a constant term (the constant term is zero), because
$AND(0,...,0) = 0$.
Meaning we can write the polynomial as:
$$AND(x_1,...,x_n) = \sum_{S\subseteq[1,n], S\neq \emptyset}a_S\prod_{j\in S}x_j$$
We now claim that every non-zero summand in $AND$ contains $x_i$.
Suppose that there are a set of summands not containing $x_i$. Choose the smallest (by amount of different parameters contained) of them. Notice that this  term is uniquely identified by a set $U \subset [1,n]\backslash\{i\}$. Now set $x_u = 1, u\in U$ and $x_v = 0, v\notin U$ and that there is no proper subsets of $U$ whose associated term is non-zero, because $|U|$ was chosen to be minimal.
$$AND(x_1,...,x_n) = a_U$$
This implies $a_U = 0$, because $i\notin U \land x_i = 0$. Repeat for all other summands (in increasing order by size). Thus all non-zero terms contain $x_i$. This applies to all $i\in[1,n]$, hence the degree of $AND$ is $n$.
We can denote $OR$ as $OR(x_1,...,x_n) = 1-AND(1-x_1,...,1-x_n)$ and likewise $AND(x_1,...,x_n) = 1-OR(1-x_1,...,1-x_n)$ by De Morgan's Law. Thus $AND$ and $OR$ must have the same degree.


A pragmatic answer: Use the Miller-Rabin test with 50 iterations.  The probability that a composite number will be wrongly declared prime by this test is at most $2^{-100}$ (see, e.g., here).  This is smaller than the chance of a cosmic ray causing a bitflip error that causes your program to output an erroneous result.  So, if you're not worried about cosmic rays, you shouldn't be worried about probabilistic algorithms.

An alternative: use any probabilistic algorithm to rule out composite numbers.  If the probabilistic algorithm claims the number is prime, use a deterministic primality test, or use a test that produces a primality certificate.  There are many such algorithms, and you can study the literature and find one which leads the best tradeoff between complexity of implementation vs speed on numbers of the size you care about.


Gaussian elimination requires $O(n^3)$ operations, not $O(n^2)$.

In general, matrix inversion has the same exponent as matrix multiplication (any matrix multiplication algorithm faster than $O(n^3)$ gives a matrix inversion algorithm faster than $O(n^3)$), see for example P.Burgisser, M.Clausen, M.A.Shokrollahi "Algebraic complexity theory", Chapter 16 "Problems related to matrix multiplication".


Divide N sticks among M boys as homogeneously as possible (ignoring order)

Give some of the boys $\lfloor N/M \rfloor$ sticks (i.e., divide and round down), and some of them $\lceil N/M \rceil$ sticks (divide and round up).  Once you fix those two numbers, that uniquely determines how many boys get $\lfloor N/M \rfloor$ sticks and how many get $\lceil N/M \rceil$ sticks -- do some simple arithmetic, try a few examples, use the fact that $\lceil N/M \rceil = \lfloor N/M \rfloor + 1$ if $M$ doesn't evenly divide into $N$, and you'll work out the general formula.


Why every finite language is polynomial?

Suppose that the longest word in the language has length $m$. The Turing machine reads the first $m+1$ symbols on the input tape. Based on that, it can decide whether the input belongs to the language or not. This Turing machine runs in constant time.


Algorithm Selection for Classification problem

I don't think existing state-of-the-art technology will be adequate to solve this task effectively.  The current state of knowledge in NLP and AI probably isn't good enough to build something that will work well in practice.    Instead, I think you'll need to use humans.  Perhaps you can hire someone and train them -- that will probably be both cheaper and more effective than anything feasible with AI today.

(It seems impractical to obtain the large training sets typically needed for deep learning.  Also, your task requires deep understanding of spoken text at a semantic level, which is currently hard.  Finally, your task requires domain knowledge about the kinds of application tasks that clients are likely to ask about.)


Guided Backpropagation in Deep Neural Networks

Guided backpropagation from the model output to the input of the first ReLU indeed results in non-negative values (as the gradient from ReLU output wrt. ReLU input is set to zero if it is negative). From the input of the first ReLU the gradient wrt. the input pixels can however become negative. Input images are mostly scaled to the range [-1,1] (e.g. by division by 127.5 and subtraction of 1 for Keras' pretrained models - that means roughly achieving zero mean and unit variance). If a negative input (pixel that is darker than the mean) contributes positively - via negative weights - to the output of the first convolutional layer the gradient for that pixel is negative. As negative gradients are only set to zero in guided backprop when passing through a ReLU and there is no ReLU between the input of the first ReLU and the overall input, guided backprop can result in negative values.


NP contains decision problems. Problems with a yes or no answer. Finding $x$ such that $g(x) = y$ for some given pseudo-random generator $g$ and output $y$ isn't a decision problem. It's a function problem.
You can turn this into decision problem by asking whether the $i$'th bit of $x$ is 1 instead. Then you can still find $x$ by just asking this question once for every bit.
Now this problem of deciding on the $i$'th bit is trivially in NP. Speaking informally, every problem that has efficiently verifiable proofs is in NP. $x$ is just such a proof. You can quickly check it's $i$'th bit. And you can quickly check that $g(x) = y$.


What is the minimal pumping length of this string $(01)^*$

The pumping length of a regular language $L$ is the minimal $p$ such that every word $w \in L$ of length at least $p$ can be split as $w = xyz$ such that (i) $|xy| \leq p$, (ii) $y \neq \epsilon$, (iii) $xy^iz \in L$ for every $i \geq 0$. The pumping length of $(01)^*$ using this definition is $2$. Anybody claiming that the pumping length is $1$ is either wrong or has a different definition in mind (the notion of pumping length isn't completely standard, and my definition is not the only possible one).

In order to show that the pumping length cannot be $1$, you need to show that there exists some word $w \in L$ of length at least $1$ such that for every splitting $w = xyz$ in which $|xy| \leq 1$ and $y \neq \epsilon$ there exists $i$ such that $xy^iz \notin L$. In particular, you don't get to pick the decomposition. You need to show that no decomposition works. In this case, we can take the word $w = 01 \in L$. Since all words in $L$ have even length, if $w = xyz$ and $xz \in L$ then necessarily $y$ has even length. However, this is impossible since on the one hand $|y| \leq |xy| \leq 1$, and on the other hand $y \neq \epsilon$.


Time complexity of pairs in array double loop

The time complexity of an algorithm depends on the model of computation. Algorithms are usually analyzed in the RAM machine, in which basic operations on machine words (such as assignment, arithmetic and comparison) cost $O(1)$. A machine word has length $O(\log n)$, where $n$ is the size of the input.
In your case, the size of the input is at least $n$ (defined to be the length of array), and so count fits in a single machine word. Each of the basic operations in the algorithm cost $O(1)$, and so the overall time complexity is $\Theta(n^2)$, since the algorithm executes this many basic operations.


Sorting in sub-quadratic time and logspace simultaneously

The following paper proves that any comparison-based sorting algorithm must satisfy $TS = \Omega(n^2)$, where $T$ is the running time and $S$ is the amount of read-write space used.

Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, Martin Tompa.  A Time-Space Tradeoff for Sorting on Non-Oblivious Machines.  Journal of Computer and System Sciences, vol 22 pp.351--364, 1981.

In particular, if $S = O(\log n)$, then $T = \Omega(n^2/\log n)$, i.e., if you have only logarithmic space, then the running time has to be nearly quadratic.