Understanding definition of epsilon closure and finite automata states

Your textbook is being very formal, probably since it aims at using set equations later on. However, $\epsilon$-closure is a very simple concept. The $\epsilon$-closure of a set $M$ of states is the collection of states that can be reached from a state in $M$ by taking any number of $\epsilon$-transitions (possibly zero).

The textbook uses a different (but equivalent) definition: it defines the $\epsilon$-closure of $M$ to be the smallest set of states that contains $M$ and that for every state $s$ that it contains, contains all states reachable from $s$ by a single $\epsilon$-transition.

Regarding the second quote, there is some context missing. Here is one possible context which would make sense. For an NFA without $\epsilon$-transitions, we define $\delta(q,a)$ to be the set of states that can be reached from $q$ by taking a transition labeled $a$. When we have $\epsilon$-transitions, there are several different possible definitions of the transition function. One possibility is to define $\delta(q,a)$ to be the set of states that can be reached from $q$ by taking a transition labeled $a$ and then an arbitrary number of transitions labeled $\epsilon$ (possibly none).


Counting substrings that belong to a regular language

You can do it in $O(|x|\cdot |M|)$ with dynamic programming.
Let $q_0$ be the starting state, $\delta$ the transition function of $M$, and $a(q) \to \{0, 1\}$ a boolean function indicating whether $q$ is an accepting state in $M$.
Let $A[i, q]$ be the number of non-empty prefixes of $x_ix_{i+1}\ldots x_n$ accepted by $M$ if we start in state $q$. We can directly compute $A[n, q] = a(\delta(q, x_n))$. Then, going backwards row by row, we can fill the table using $A[i,q] = a(\delta(q, x_{i})) + A[i+1, \delta(q, x_{i})]$.
Finally, you sum $a(q_0) +\sum_{i=1}^nA[i, q_0]$ as your answer, as this is the sum over all non-empty prefixes of all non-empty suffixes, plus one if the empty string is accepted, thus all substrings.


If you know one block of plaintext (which in many situations is a reasonable assumption), you can break the second cryptosystem but not the first one (assuming your cipher is secure!). I'll let you figure out how.

You can extend this attack to the case in which one block of plaintext has small entropy, which is an even more realistic assumption.


You can probably use this to simulate register machines and, if you can do that, the system is Turing complete.

The setup is as follows.

The machine has a sequence of names registers, each of which holds a non-negative integer.
Program instructions are labelled with non-negative integers and execution starts with, say, instruction $0$;
The three possible instructions are:

halt;
increment register $R$ and goto instruction $I$ (where $R$ and $I$ are integer constants);
if register $R$ is zero, goto instruction $I$; else, decrement $R$ and goto instruction $J$ ($R$, $I$ and $J$ are constants).

For example, the following program adds the contents of registers $0$ and $1$ and halts with the sum in register $0$:

0. if R1=0, goto 2 else decrement R1 and goto 1
1. increment R0 and goto 0
2. HALT

My recollection from computation theory classes 20+ years ago is that you can simulate a Turing machine using a register machine with two registers (and certainly with some fixed number of registers). Proving this is long and tedious because you have to code up the tape and all manipulations of it as arithmetic operations and, heck, you even have to code up arithmetic operations such as addition, multiplication and exponentiation. Oh, and you'll probably have to be more careful than I was with my addition routine, because you'll probably want to do arithmetic on two values without destroying them both, which requires copying them to extra registers and then copying back.

You can simulate a two-register machine (i.e., a register machine with two registers) with $n$ instructions with your system as follows.  Use two array cells to store the register values, and then probably one array value for each instruction, such that $A[i]=1$ if instruction $i-2$ is the next to be executed and $A[i]=0$, otherwise. Then executing the system with $A=[x,y,1,0,\dots,0]$ should simulate the register machine running with input $x$ in the first register and $y$ in the second.  If there are $n$ instructions in the program, ASTs will look like this:

$$A[i]=(A[2]*v_0) + (A[3]*v_1) + ... + (A[n+2]*v_n)\,,$$

where $v_j$ is the value that should be stored in $A[i]$ if instruction $j$ is executed.

Note that all of this assumes that the array elements can hold unboundedly large numbers. If not, your system only has a finite number of states so cannot be Turing-complete. The simulation I have in mind only uses non-negative integer values in the arrays.


What does the phrase "Simple For Loops" mean in computability theory?

The Wikipedia statement is informal and quite ambiguous. For example, let $A(n,n)$ be the Ackermann function, and consider the following program, where $n$ is the input:

x ← 0
for i from 1 to A(n,n):
    x ← x + 1
return x

This function is not primitive recursive, although there is a bound on the number of iterations which is known ahead of time.

A better explanation is the LOOP programming languages. Every loop in LOOP runs $x_i$ times, where $x_i$ is a variable, and the number of iterations is the value of $x_i$ before the loop is run. For example:

  LOOP x DO
      x ← x + 1
  END

is a problem that doubles $x$, and

  z ← 0
  LOOP x DO
      z ← z + 1
  END
  LOOP y DO
      z ← z + 1
  END

is a problem that assigns $x + y$ to $z$.

A function can be computed in LOOP (using a reasonable input/output convention) iff it is primitive recursive. So if you only allow loops in which the number of iterations is the value of some variable just before the loop, then the resulting function will be primitive recursive, and furthermore, every primitive recursive function can be computed only using such loops.


What is difference between Hidden Markov Model and Non-deterministic Finite-State Machine?

Deterministic Finite State Machines have at most one trace for a given input. Nondeterministic Finite State Machines may have many traces for a given input. A Hidden Markov Model in some sense fits "in between" these extremes as the traces are probabilistic. With a Hidden Markov Model we do not have complete freedom to choose which trace to follow as we are governed by probabilities. A Hidden Markov Model is essentially a transducer-style Finite State Machine having outputs & transitions governed by a random process; the outputs generated at states are per a random variable model of what happens at that state, e.g., "if the weather is cloudy then 20% it will turn rainy / 80% it will turn sunny".


Indexing Edge Permutations for the Rubik's Cube

The Lehmer code is easily adapted. Instead of using $\binom{n}{k} = \frac{n!}{k! (n-k)!}$, which counts unordered subsets, use $\frac{n!}{(n-k)!}$, which counts ordered subsets.

In Python:

from functools import reduce
from operator import mul

def falling_factorial(n, k):
    return reduce(mul, range(n-k+1, n+1), 1)

def lexicographic_rank(n, perm):
    if len(perm) == 0:
        return 0

    a = perm[0]
    return a * falling_factorial(n - 1, len(perm) - 1) + \
        lexicographic_rank(n - 1, [i if i < a else i - 1 for i in perm[1:]])

Online demo


What simple arguments and insights can I observe that running both BFS and DFS can be achieved in O(|V| + |E|)?

Intuitively, what a time upper bound of $O(|V| + |E|)$ means is that you spend $O(1)$ time per each vertex and each edge. Taking as an example DFS, there is one recursive call per edge, and the procedure itself runs once per vertex. You can turn this into a full-fledged argument that proves the upper bound.

An upper bound of $O(|V| + |E|)$ is optimal for most graph problems – those that potentially require examining all vertices and all edges. What such an upper bound tells you is that your problem can be solved in the minimal possible time; an $O(|V| + |E|)$ algorithm is an asymptotically optimal algorithm.


Yes, your method is fine and, yes, there's a fairly trivial way to complete your proof attempt: it's easy to arrange that $L^*=\Sigma^*$, which is in P.


What is the fastest algorithm for multiplication of two n-digit numbers?

As of now Fürer's algorithm by Martin Fürer has a time complexity of $n \log(n)2^{Θ(log*(n))}$ which uses Fourier transforms over complex numbers. His algorithm is actually based on Schönhage and Strassen's algorithm which has a time complexity of $Θ(n\log(n)\log(\log(n)))$

Other algorithms which are faster than Grade School Multiplication algorithm are Karatsuba multiplication which has a time complexity of $O(n^{\log_{2}3})$ ≈ $O(n^{1.585})$ and Toom 3 algorithm which has a time complexity of $Θ(n^{1.465})$

Note that these are the fast algorithms. Finding fastest algorithm for multiplication is an open problem in Computer Science.

References :

Fürer's algorithm
FFT based multiplication of large numbers
Fast Fourier transform
Toom–Cook multiplication
Schönhage–Strassen algorithm
Karatsuba algorithm


The mistake is in what you're attempting to split. The pumping lemma says if $L$ is a regular language, there exists a number $m$ (the pumping length) such that every string $x \in L$ can be be split into three parts, $x=pqr$ such that:

$|pq| \leq m$
$|q| \geq 1$
$pq^{i}r \in L$ for all $i \in \mathbb{N}$

So it's the strings in the language that can be split and pumped, not the language.

So for the language you give, which is regular, you should be able to take any string, split it and pump it. One problem with doing this in practice is that the pumping length $m$ is not typically known, however we can take a larger example here and we don't have to worry.

Consider the string $y = a^{2m+3}b^{4}$, then we know that $pq = a^k$ for some $k \in [1,m]$, and in particular $p = a^{k_{1}}$ with $k_{1} \in [0,m-1]$, $q = a^{k_{2}}$ with $k_{2} \in [1,m]$ and $k_{1}+k_{2}=k$. Then $r = a^{2m+3-k}b^{4}$. As $k \leq m$, this string is in the language $A$ (it fits the definition in the second part).

Now we get to the pumping part; as $A$ is regular, assuming that we've split things correctly, we should be able to pump $y$. If we pump down, we get $a^{2m+3-k_{2}}b^{4}$, which is still in $A$ (again, $k_{2} \leq k \leq m$). If we pump up $n$ times, we get $a^{2m+3+nk_{2}}b^{4}$, which still fits the definition and is in $A$.

Then as $A$ is regular, we should be able to do this for every string in the language, but there's no real reason we would want to as it doesn't tell us anything - there are non-regular languages which can still be pumped (e.g. see the wikipedia article). What we use the pumping lemma for is showing that languages are not regular by showing that the language we suspect is not regular contains at least one string that cannot be broken up and pumped in any way.


What does it mean for a grammar to be LR(0)?

A bottom-up parsing technique, used for parsing most context-free grammars is LR(k): L indicates that the input is parsed from left to right, R indicates that in the parsing process a rightmost derivation is produced; the number k indicates how many lookahead symbols are used.
An LR parsing scheme consists of: input, output, stack, a parsing program and a parsing table divided into two parts (actions (shift, reduce) and goto).
The idea is that the parsing program reads characters from an input buffer one at a time and uses the stack to store strings of the form s0X1s1X2s2...smXm where s0 is the initial state, the only one present at the beginning of the computation on the stack, while sm is the state at the top of the stack. Each Xi is a grammatical symbol while each si is a symbol that identifies a state. Each state describes the information contained in the stack before it; the combination of the state at the top of the stack and the current input symbol is used to index the parsing table and to determine the parser's shift-reduce decisions.
Given a grammar, to prove that this is LR(0) builds the DFA of viable prefixes.
The first prefix is always S' -> .S because we consider the grammar increased. Then follow the rules to build the LR(0) parsing table.
A grammar is LR(0) if each position in the parsing table LR(0) contains at most one element.
Furthermore, the LR(0) languages all enjoy the prefix property. So if a language does not have this property, we can immediately say that it is not LR(0).
If the grammar is ambiguous then it cannot be LR(k) for any k.


Reading elements of a countable set with Turing machine

By definition, a set $S$ is recursively enumerable if there is a Turing machine that enumerates it.


A grammar is a set of production rules for symbol sequences.

But you knew that already. If you edit the question to make it more specific, we can offer more specific answers.


"3 tier database architecture" is a bit of misnomer, as database by itself doesn't have extra tiers. So what are the 3 tiers? From outter-most to inner most, they are:

presentation,

application processing,

data management.

https://example.net is literally 1-tier since it doesn't have application processing and data management, it just presents a text permitting you to use that domain name in documentations.
FTP would be a 2-tier protocol since it doesn't have application processing.


How to prove the existence of the spectral expander with the given parameteres?

There are also expanders with the following parameters: $(3, 2, 1/2)$ — complete graph on 3 vertices and $(8,8, 0)$ — complete graph on 8 vertices with the loop in each vertex. So we have the following tensor product:
$$
(1944, 144, 0.5) = (9^2, 9, 1/3) \otimes (3, 2, 1/2) \otimes (8,8, 0)
$$


How to approach analysis of randomized algorithm

Let $P$ be the distribution of $i^*$, which you can calculate explicitly:
$$
\begin{align*}
p_i := \Pr[P=i] &= \left(1-\frac{i-1}{n}\right)^k - \left(1-\frac{i}{n}\right)^k.
\end{align*}
$$
This is the probability that all samples are at least $i$ minus the probability that they are all at least $i+1$.

The counter $C(i)$ has binomial distribution $\mathrm{Bin}(M,p_i)$, which will be concentrated around $Mp_i$. In contrast, $\frac{1}{n} \sum_{j=1}^n C(j) = \frac{M}{n}$. Therefore you can only expect $C(i)$ to be close to $\frac{1}{n} \sum_{j=1}^n C(j)$ if $p_i \approx \frac{1}{n}$. Even when $p_i \approx \frac{1}{n}$, the concentration of $C(i)$ is not so good – the standard deviation is $\sqrt{Mp_i(1-p_i)} \approx \sqrt{M/n}$, so the probability that $C(i)$ is very close to $M/n$ is probably quite small.


How does make/scons manage dependency graph and figure out which file need to be recompiled?

I do not how SCons works in details so I will focus on Make. I am not sure anyone really knows what is the algorithm Make uses because it is so complicated and error-prone, it is loosely described in the manual . But at the high-level, Make takes as input rules as described in the manual of form $$target: dependencies$$
Furthermore, when running make one has to specify one or more targets to build (if you give no target, it builds "default"): make target1 target2 ...
This essentially describes a graph and a set of nodes to be built.
In terms of graph, one could say that Make performs a depth-first search1 from those to-be-built nodes, but this hides many details like PHONY/FORCE rules, intermediate files, secondary-expansions, the fact that a file can actually be built twice, parallel make and more features. Make considers dependency loops to be an error and will break them arbitrarily (and display a warning).

In fact, one could say that Make performs two different (but related) functions: building the dependency graph and rebuilding everything according to the graph. The difference between Make and other tools is that other tools mostly take as input a complete description of the graph. On the other hand, Make provides a whole range of tool to dynamically create the graph. This creates a lot of confusion because you can literally have a 5 lines Makefile that will generate a graph with thousands of nodes and runs all kinds of tools to figure out the dependencies. SCons, CMake and friends will usually let other tools do this work for them and focus on just rebuilding everything. Also Make's approach makes it somewhat inefficient because just building the graph may involve running some tools, and not just reading the Makefiles.

1The order in which Make builds file is completely unspecified, except for the fact that it is a topological order (and even that is not entirely true because Make may actually build some targets more than once)


How to eliminate for/if/while from algorithms when it's possible

For/if/while are the main blocks that will check for a condition. Since a recursive function will keep recurring until a condition is met, you will at least need an if statement to tell the function when to return. Otherwise, you will essentially be stuck in an infinite loop.


Computer years, like man hours, are a measure of work. A computer year is the work one computer (of some agreed-upon speed...) performs in a year. 365 computers working in parallel for a day also perform one computer year of work.


This is sometimes called "0-1 normalization" or "feature scaling".

http://en.wikipedia.org/wiki/Feature_scaling

http://en.wikipedia.org/wiki/Normalization_(statistics)

The entire function f() is a Piecewise function, which consists of 3 domains, defined separately for

v <= min
v is between min and max, and
v >= max.

The primary function is the normalization function when v is between min and max.  The other two functions just limit the range or codomain of the function.

Piecewise functions are used often in mathematics to make the whole function continuous over a larger domain or to handle special cases like divide by zero, which the original poster might want to handle when min == max.

And what does the function do?
Creates a function f(x) where f(min) returns 0.0, f(max) returns 1.0, and f(v) rescales the input v from 0.0 to 1.0 linearly. Anything less than min maps to 0.0; anything more than max maps to 1.0.

One application of this is to calculate the percentile of a data samples (but from 0.0 to 1.0 vice 0 to 100).


What is the average height of a binary tree?

There is no reason to believe that both definitions describe the same measure. You can write $\operatorname{avh}_1$ recursively, too:

$\qquad \displaystyle \operatorname{avh}_1(N(l,r)) = \frac{\operatorname{lv}(l)(\operatorname{avh_1}(l) + 1) + \operatorname{lv}(r)(\operatorname{avh_1}(r) + 1)}{\operatorname{lv}(l) + \operatorname{lv}(r)}$

with $\operatorname{avh}_1(l) = 0$ for leaves $l$. If you don't believe that this is the same, unfold the definition of $\operatorname{avh}_1$ on the right hand side, or perform an induction proof.

Now we see that $\operatorname{avh}_1$ works quite differently from $\operatorname{avh}_2$. While $\operatorname{avh}_2$ weighs the recursive heights of a nodes children equally (adding and dividing by two), $\operatorname{avh}_1$ weighs them according to the number of leaves they contain. So they are the same (modulo the anchor) for leaf-balanced trees, that is balanced in the sense that sibling trees have equally many leaves. If you simplify the recursive form of $\operatorname{avh}_1$ with $\operatorname{lv}(l) = \operatorname{lv}(r)$ this is immediately apparent. On unbalanced trees, however, they are different.

Your calculations are indeed correct (given your definition); note that the example tree is not leaf-balanced.


Linear time algorithm to sort points of a simple polygon

You ask:

  the very first step is sorting the vertices of such polygon.
  Apparently this very step can be done in $O(n)$

but the book says

  We now analyze the running time of the algorithm. Constructing the priority queue QQ takes linear time...

Constructing a priority queue does not take as much time as sorting. Priority queues can be constructed in linear time. The most famous algorithm for doing this is called "heapify".


Hint: For a formula $\varphi$, let $\#(\varphi)$ be the number of satisfying assignments of $\varphi$. Come up with a polytime transformation $T$ so that $\#(T(\varphi)) = \#(\varphi) + 2$.


Giving a regular grammar for the language

That's fairly easy. Just take a non-terminal X and add the rule $X\to aY$ where $a$ is the label on the arrow from $X$ to $Y$ if $X$ is not final; if it's final add a rule like: $X\to \epsilon$ as well. Do that for every non-terminal and you get a right-regular grammar.

Here is a right-regular grammar for the given automaton:

$A \to 1 A$

$A \to 0 B$

$B \to 1 A$

$B \to 0 C$

$C \to 0 C$

$C \to 1 C$

$C \to \epsilon$


You can compute the pairwise GCDs of the factors. You have to divide out the GCDs from the factors to avoid finding the same GCD factor twice:

a[1...m] = [given factors of A]
b[1...n] = [given factors of B]
g = 1
for i from 1 to m do
    c = a[i]
    for j from 1 to n do
        d = gcd(c, b[j])
        g = g * d
        c = a[i] / d
        b[j] = b[j] / d
return g

Unfortunately, I don't think that this is not notably faster than the computation of the GCD of the two numbers A and B.


Question about idempotent and Dominance Laws in Boolean Algebra

The principle of substitution states that if $\varphi$ is a valid (fully parenthesized) formula in variables $x_1,\ldots,x_n$ and $e_1,\ldots,e_n$ are arbitrary expressions, then if we substitute $e_i$ for $x_i$ in $\varphi$ (you have to substitute all occurrences of $x_i$ by $e_i$) we still get a valid formula. You can apply this principle to your examples.

Perhaps the principle will become easier to understand if we take an example from algebra. Consider the identity $(x+y)(x-y) = x^2-y^2$. If we substitute $2a$ for $x$ and $1+a$ for $y$ then we get $((2a)+(1+a))((2a)-(1+a)) = (2a)^2-(1+a)^2$, which is still valid. The same happens in your case.


Is it possible to simulate a fair coin with a finite number of tossing of a biased one?

No, it's not possible.  Suppose the bias of the coin is $1/3$, and suppose you could guarantee termination.  Then there would be some $n$ such that this always terminates after $n$ coin flips.  Let $S$ denote the set of flip-sequences that causes your algorithm to output 0 (so that $\overline{S}$ is the set of flip-sequences that causes your algorithm to output 1).  The probability of your algorithm outputting 0 is equal to the probability of getting a flip-sequence in $S$, which is a sum of the form

$$\sum_{x \in S} {a_x \over 3^n}$$

where each $a_x$ is an integer.  Thus the probability of outputting 0 has the form $b/3^n$ where $b$ is an integer.  We want this to be $1/2$, for your algorithm to produce an unbiased bit of output.  However since $3^n$ is odd, there is no integer $b$ such that $b/3^n = 1/2$.  Therefore, no such algorithm can exist.


Is maximum edge-weighted triangle-free graph NP-hard?

The problem is $NP$-complete even in the unweighted case (e.g.: all edge weights are equal to $1$). Instead of looking for a maximum edge-induced, triangle-free subgraph we may equivalently consider the minimum number of edges to delete from the original graph in order to leave a triangle-free graph. This problem (and other, related problems) are demonstrated to be $NP$-complete in [1]:

If $\pi $ is a property on graphs or digraphs, the edge-deletion problem can be stated as follows: find the minimum number of edges whose deletion results in a subgraph (or subdigraph) satisfying property $\pi $. Several well-studied graph problems can be formulated as edge-deletion problems.
In this paper we show that the edge-deletion problem is NP-complete for the following properties: (1) without cycles of specified length l, or of any length $ \leqq l$, (2) connected and degree-constrained, (3) outerplanar, (4) transitive digraph, (5) line-invertible, (6) bipartite, (7) transitively orientable. For problems (5), (6), (7) we determine the best possible bounds on the node-degrees for which the problems remain NP-complete.

Yannakakis, Mihalis. "Edge-deletion problems." SIAM Journal on Computing 10.2 (1981): 297-309.


The throughput of the ALOHA protocol if the Binomial distribution was used

I don't think it makes sense to use the binomial distribution.

The point of using the Poisson distribution is that network nodes are assumed to want to transmit with an exponential distribution at some rate. This is a reasonable model for objects that randomly emit stuff – for example radioactive decays follow this distribution.  Given a bunch of things emitting stuff at intervals sampled from the exponential distribution, the number of emissions in some time interval is given by a Poisson distribution.  In other words, the Poisson distribution arises naturally from a model of the individual nodes. A particular property of the Poisson distribution is that it has infinite support: it assigns a probability to the event that you have a million transmission attempts within ten time slots.  Another feature of using exponential distributions is that it allows one to model the back-off time after a collision.

In contrast, using a binomial distribution doesn't come from any natural model of the individual nodes' behaviour. It only allows you to model "were there at least $n$ transmissions attempts during this time slot?" for some $n$ of your choosing. It doesn't seem able to deal with back-off and it doesn't seem able to deal with multiple collisions within a single time slot.


What is a counterexample for Lamport's distributed mutual exclusion algorithm with non-FIFO message queues?

Looks like this modification is correct. Proof is similar to proof of Lamport algorithm and follows.

Consider two processes $P_i$ and $P_k$ who entered critical sections at moments $e$ and $f$, correspondingly, requested them at moments $e'$ and $f'$, and exited at moments $e''$ and $f''$.

At moment $e$ process $P_i$ have received a confirmation from $P_k$. Suppose it was sent by $P_k$ at moment $g \to e$.

Case 1: $g < f'$. In that case, process $P_k$ has both itself and $P_i$ in queue, and $P_k$'s ticket is greater than $P_i$'s (because we use logical clock as tickets). So process $P_k$ cannot enter the critical section until it receives a release from $P_i$, and we have a correct mutual exclusion.

Case 2: $f' < f < f'' < g$. In that case, $f'' \to g \to e$, and we have a correct mutual correct mutual exclusion.

Case 3: $f' < f < g < f''$. That case is impossible as $P_k$ have sent a confirmation while in critical section.

Case 4: $f' < g < f < f''$. In that case, process $P_k$ should've received a confirmation from process $P_i$ by $f$. Suppose it was sent by $P_i$ at moment $h$. If $h > e$, then $h > e''$ and we have a correct mutual exclusion ($e''
\to h \to f$). Otherwise, $h < e$, so process $P_i$ learns about $P_k$'s wish before entering the critical section. Similarly, as $g < f$, $P_k$ learns about $P_i$'s wish before entering the critical section. But only one of them has lower priority, hence, their critical sections happen in order.


This explanatory part can be skipped :

Non-terminal in a Context-Free Grammar can be interpreted as standing
for the set of strings they generate (this is actually one standard
interpretation of CF grammars as string set equations).

For example $A \rightarrow C \mid D \mid a$ may be read as a set
equation $A = C \cup D \cup \{a\}$ where $A$, $C$ and $D$ now stand
for sets of strings and {a} for a singleton set containing the
string "$a$".

Algebraic properties of concatenation and set union on strings and
string sets can be used to transform grammars. In particular, you can
use factorization in ways that are similar to what you do in
arithmetics to make formulae simpler to compute.

Typically, if $A$, $B$ and $C$ are string sets (possibly reduced to a
simgleton, i.e. a single string), then $(A \cup B)C = AC \cup BC$,
i.e. concatenation is distributive for set union, like product is for
sum.

How to do it

So, when you transform a CF grammar, you can first reduce the size
with factorization. For that, you may replace some non-terminals by the
right-hand-side of their defining rule, or introduce new non-terminals
when convenient.

$A \rightarrow C \mid D \mid a$
$C \rightarrow c \mid A d$
$D \rightarrow A e \mid f$

can be rewritten as

$A \rightarrow X \mid a$
$X \rightarrow AY \mid Z$
$Y \rightarrow d\mid e$
$Z \rightarrow c\mid f$

There are various ways of using this, but you should be able to use it
to do away with the complexity of your grammar.

I deliberately did not make it as simple as I could have. My purpose
is only to give you an idea of what can be done.

The correctness of transformations can also be proved directly on
derivations, without having to consider interpretations on string sets
as I did above.

Complete solution

Here is a suggested answer. Hoping to simplify presentation, I used
extended context-free notation that allows for regular expressions on
the right-hand side (RHS) of rule. It does not change the practical uses and
properties of CF grammars. You can do it as well by introducing new
non-terminals. This was not really necessary here, but I found it
convenient while doing the transformations. In retrospect, it would be simpler without it.

With this convention the rule $X\rightarrow Y\mid Z$ is equivalent to
$X\rightarrow Y+Z$.  Essentially the operators ¨$+$" and ¨$\mid$" have
the same role.

Starting with your grammar, I first eliminate some non-terminals by
replacing them by the corresponding RHS. I do that in the rule for $B$,
and it gives:

$A\rightarrow B \mid a$
$B\rightarrow (b+c+f+g+i+k+l+n) \mid A(d+e+j+m) \mid Bh$

Then, substituting $A$ by the RHS of its rule:
$A\rightarrow B \mid a$
$B\rightarrow (b+c+f+g+i+k+l+n) \mid (B+a)(d+e+j+m) \mid Bh$

and simplifying

$A\rightarrow B \mid a$
$B\rightarrow (b+c+f+g+i+k+l+n) \mid a(d+e+j+m) \mid B(h+d+e+j+m)$

And going back tu usual CF notation:

$A\rightarrow B \mid a$
$B\rightarrow BX \mid Y$
$X\rightarrow h \mid U$
$U\rightarrow d\mid e\mid j\mid m$
$Y\rightarrow aU \mid V$
$V\rightarrow b\mid c\mid f\mid g\mid i\mid k\mid l\mid n$

Now you only have to remove the left recursion from the $B$ rule in
the usual way, replacing it by:

$B\rightarrow Y \mid YH$
$H\rightarrow X \mid XH$

and you are set.


Expected weight of euclidean minimum spanning tree on a unit square

The following is based on J. Michael Steele's paper proving the rigorous bound.

The pigeonhole principle shows that out of any $n$ points in $[0,1]^d$, there are two at distance at most $O(n^{1/d})$, say at most $c_d n^{1/d}$; the idea is to divide $[0,1]^d$ into small enough boxes, and find a box containing two points. Construct a spanning tree by repeatedly adding an edge corresponding to the two closest points and throwing out one of them. This spanning tree has cost at most
$$
c_d (n^{1/d} + (n-1)^{1/d} + \cdots + 2^{1/d}) \leq c_d \int_2^{n+1} x^{1/d} \, dx = O(n^{(d-1)/d}).
$$

For the lower bound, a similar argument dividing $[0,1]^d$ into small boxes shows that for any $\epsilon > 0$, with probability $1-\epsilon$ there are only $\epsilon n$ many edges whose weight is $O_\epsilon(n^{1/d})$, and so with constant probability any spanning tree has cost $\Omega_\epsilon(n^{(d-1)/d})$. With more work, it follows that the expected weight of a minimum spanning tree is $\Omega(n^{(d-1)/d})$.


When an algorithm says Summation this, and Integral that, what does it mean in coding terms?

You are probably looking at a rather mathematical sketch of an algorithm. There are two general roads to implement non-trivial mathematical expressions such as series, integrals, and differential equations.

If you want exact, potentially symbolic results you have to simplify "complex" expressions into closed forms on paper, and/or employ computer algebra.
If you are satisfied with numerical, potentially approximate solutions, you want to employ numerical algorithms, including error estimations.


Deciding whether a given language is regular

Hint: Consider how many words are in $L$. The answer will then be immediate.


Why can we drop the superscripts in the Floyd Warshall algorithm?

Basically in iteration k no entry $d_{ij}$ can change if $i=k$ or $j=k$. Since you update the entries in $D$ by considering $d_{ik}$ and $d_{kj}$ you can do all these updates in-place.

However there is an even simpler argument if you only want to show that the algorithm requires $O(n^2)$ space. At every iteration $k$ the values in $D^k$ only depend on the previous matrix $D^{k-1}$. Therefore it is enough to store the matrix $D^{k-1}$ of the previous iteration, use it to fill the next matrix $D^k$ and then you can safely discard $D^{k-1}$. So you only ever need to keep two matrices in memory and arrive at $O(n^2)$ space. Of course no sensible implementation would actually do this but it is enough to show the space bounds.


Using pumping lemma to prove irregularity of regular language - what is my error?

The pumping lemma gives you a pumping length $n$ and $\alpha, \beta, \gamma$ under the conditions specified in it so that $\alpha \beta^k \gamma \in L$ for all $k \ge 0$. You do not get to choose $\alpha, \beta, \gamma$ as you please. Also, the pumping lemma works for all words of length at least $n$, not simply an arbitrary word $\sigma$.

The trick when using the pumping lemma, then, is picking a word longer than the pumping length and such that any decomposition into $\alpha, \beta, \gamma$ (obeying the conditions specified in the lemma) can be used to derive the contradiction that you need.


Verifying connectivity of a graph in O(n^2)

You can do one graph traversal to find all the connected components of your graph.

Then add an edge from each connected component to the next : the graph is fully connected and you did only one traversal, that's $O(n^2)$


Is this classic puzzle book game NP-complete?

Sorry for answering an old post.

I´ve been thinking about it and i think that the problem with a fixed alphabet is NP-complete as well.

I´m going to reduce positive 1-in-3 SAT to this word problem

Yesterday i was having trouble coming with ideas for solving the problem. I had trouble making each variable different until i looked again at the question and i realized that you allowed having squares with planted symbols. This simplified the reduction a lot. My other idea was to have words of different length for each different variable.

THE REDUCTION

Now i´m going to describe the gadgets we are gonna use:

Variable gadget

We label each variable with a different numerical index and we will have a different number for each variable. We pick the biggest index and we represent the number in binary, we will call this binary chain $n$.

Then we create two different vertical words for each variable. All words will have a length of $3 + |n|$ (Only if we allow duplicate words in the list of words), where $|n|$ is the length of the binary chain $n$.

For instance, let the biggest index be the number $4$. When we transform this number in binary we obtain the chain $100$ in binary, this chain has a length of three. So each variable word will have a length of $6$ in this example.

Now we create two different words for each variable. One word will have the symbol $3$ at the beginning, then the symbol $2$ below, then a binary chain that represents the index of the variable and we pad with zeroes the chain so that it has the same length that chain $n$ and finally the symbol $3$ at the end. Of course the symbols can be changed.

The other word is almost the same but it will have the symbol $4$ instead of the symbol $3$.

For instance, let the biggest index be the number $4$. We will have the following two words for the variable with index $1$:

$320013$ and $420014$

As we see we have padded the binary reperesentation of the number $1$ with zeroes so that it has a length of $|n|$

We have to copy these words many times, we will need one copy of each word for each occurence of a variable in the SAT instance. This will create duplicates in the list of words. We can get rid of the duplicates by adding another binary chain to the binary chain that uniquely identifies the variable. This new chain will uniquely identify each ocurrence of a variable.

To do that, we simply assign each ocurrence of the variable another binary chain and we olace that chain at the end of the binary representation of the variable.

To create this new binary chain first we have to create a different index for each variable, we call the biggest number in each index $n_i$ where $i$ is an identifier for each variable.  After that, we transform the number $n_i$ into a binary chain and then we count the length of the chain, we call this number $|n_i|$. Then, for each index, we create a different binary number for each ocurrence of the variable. We pad the number with zeroes until the length of the binary chain becomes $|n_i|$ so that all the words that belong to each ocurrence of the variable have the same length.

This will get rid of duplicates inside the variable words.

For instance, suppose that variable $x_2$ appears three times in the SAT instance.
We create the following words:

$32010013$ $42010014$, $32010103$ $42010104$ and $32010113$ $42010114$

Clause gadget

For each clause gadget, we will create three new horizontal words, each clause word will have  a length of $6$ squares (Only if we allow duplicate words in the list of words). These are the words that we will create for each clause:

$535354$, $535453$ and $545353$

We have a different clause word for each possible way of satisfyng the clause, the symbol $4$ represents a literal set to true and the symbol $3$ represents a literal set to false. The number $5$ is used to indicate that it is a clause word.

There will be repeated words in the list of words, we can get rid of the repetitions by using the procedure that we used to uniquely identify the variable words.
That is, we create a different binary chain for each clause and we append each chain to the clause words corresopnding to each clause.
To do that we create a new index for the clauses and we pick the biggest number of the index, we will call this number $m$. We represent $m$ as a binary chain and we call the length of this binary chain as $|m|$. Now, we create a different binary number for each clause, starting with the number 1, and we pad the number  with zeroes to make a binary chain that has a length of $|m|$. We append each binary chain to the clause words that belong to the clause.

Now, let´s see a picture of a clause gadget in the board:

This example represents the clause $(x_2 \lor x_3 \lor x_4)$ and the 1 in 3 instance being reduced is $(x_1 \lor x_2 \lor x_3) \land (x_2 \lor x_3 \lor x_4) $

As we see, there are written squares. The vertical columns have written symbols to indicate which literals are inside the clause. The end and the beginning of the column are blank squares. This lets the player choose the value of the variable.
The marked symbols in the horizontal row force the player to put a clause word in that row. Because all clause words have only a  single symbol $4$ that means that only one of the literals that is inside the clause gadget can be set to "true".

If we don´t allow duplicates inside the list of words we will have to modify the image.

The clause row in the image will become: $5b5b5b10$ and the literal columns will be, from left to right:

$b201010b$, $b201110b$ and $b21001b$

Where the symbol $b$ means blank square

See an example:

Variable consistency gadget

This is a gadget that ensures that the player can only asign the same value for all literal columns of a variable.

We will have a new gadget for each variable

We will create two new words for each gadget.

The length of the word will depend on the number of ocurrences of a variable. The length of a word will be $2 * k$ where $k$ is the number of ocurrences of a variable. So if variable $x_2$ appears two times in the sat instance, the words will have a length of four.
One of the two words is formed by repeating the chain $63$ $k$ times, where k is the number of occurrences of the variable. The other word is formed by repeating
the chain $64$ $k$ times, where k is the number of occurrences of the variable in the SAT instance being reduced.

For instance if a variable $x_2$ has two ocurrences, the words that belong to the corresponding variable assignment gadget will be:

$6363$ and $6464$

If we want to avoid repeated words, notice that each consistency gadget belongs to a different variable. So we can append the binary chain that identifies each variable to the two words that we created for this gadget.

Now let´s see an example picture of this gadget:

This gadget is for the variable $x_2$ and the 1 in 3 instance being reduced is $(x_1 \lor x_2 \lor x_3) \land (x_2 \lor x_3 \lor x_4) $.

As we see, there are two horizontal rows, the symbols written inside the rows make sure that we can only place words containing those symbols, those words are the words that we created for this gadget. In one of the rows, we see that there are two columns coming into it, because of the symbols that are placed in the columns we make sure we can only place variable words. Because the only words we can only place on the variable consistency row have only the symbol $3$ or only the symbol $4$ in them, we force the player to place all variable words with that symbol inside the gadget. This means that the only variable words that are available to be placed inside the clause gadgets have only the symbol $3$ or only the symbol $4$. We can place the remaining word of this gagdet in the other row

If we don´t allow duplicates in the list of words, the words inside the example picture will be:

For the rows:

$6b6b010$ and $6b6b010$

For the columns:

$b201001b$ and $b201010b$

Where the symbol $b$ means blank square

See an example:

Clause dump gadget

This is a gadget created to place the unused clause words. To do that, we have only to place two rows for each clause word in an empty part of the board. These rows are not connected to any other row or column.

With this we finish the reduction, as we claimed we only need 6 symbols for the reduction.

Example

If the previous explanation was confusing, here is an example picture of an instance of positive 1 in 3 SAT that has been reduced to this word problem:

If we disallow repeated words:

The instance that has been reduced is:

$(x_1 \lor x_2 \lor x_3) \land (x_2 \lor x_3 \lor x_4) $


Complex/Hybrid data structures- do people ever combine structures like graphs and hash tables together?

I am convinced that in many practical cases such hybrid data structures are key to effectiveness, so I like your question pretty much!
There are many examples, and I would like to detail one that makes a true difference both in practice and in theory.
First, a bit of context. There are two main data structures for representing graphs: adjacency lists, where we have the list of neighbors for each vertex; and adjacency matrices, where we have a double-entry array in which cell $i,j$ tells if there is an edge between vertices $i$ and $j$.
Let us consider a graph $G$ with $n$ vertices and $m$ edges. In practice, $m$ is generally much lower than its maximal value $\frac{n\cdot (n-1)}{2} \sim n^2$. This makes adjacency lists appealing, because they need only $O(m)$ space, whereas adjacency matrices need $O(n^2)$ space. However, one cannot query edge existence in constant time in an adjacency list representation, whereas one can do this in an adjacency matrix. This is why the two approaches coexist in the wide world of graph algorithms, with some relying on adjacency lists, and some on adjacency matrices.
In some cases, though, it is possible to take advantage of the best of the two worlds. This is particularly true when one considers large graphs with heterogeneous degrees. The degree of a vertex is its number of neighbors. Heterogeneous degrees mean that there are vertices with only few neighbors, as well as some with many many neighbors. In practice, there are often many nodes with low degree, as well as few nodes with very high degree (and some nodes with intermediate degrees). This leads to the following idea: represent low degree neighborhoods by adjacency lists, and then parsing them is fast (as they are small); and represent each high degree neighborhors by an array of size $n$. If one carefully chooses which degrees are considered small and which are considered large, then it is possible to have a compact graph representation that allows very fast edge existence queries.
I used this approach in triangle listing/counting algorithms (triangles are sets of three vertices all linked together):
Theory and Practice of Triangle Problems in Very Large (Sparse (Power-Law)) Graphs
In this case, one may formally show that the algorithmic complexity depends on the way vertices are divided into low and high degrees. The practical benefit is huge too.


Prove that there is a sequence of k minimum spaning trees between two distinct minimum spanning trees that each one is different in only 1 edge

This is a generalization of the Uniqueness property of minimum spanning trees, and the proof is almost the same:

Note there is at least one edge that belongs to exactly one of $T$ and $T'$. Among such edges, let $e_1$ be the one with least weight. Without loss of generality, assume $e_1 \in T$.
As $T'$ is an MST, $e_1\cup T'$ must contain a cycle $C$ with $e_1$.
As a tree, $T$ contains no cycles, therefore $C$ must have an edge $e_2\notin T$.
Since $e_1$ was chosen as the lowest-weight edge among those belonging to exactly one of $T$ and $T'$, the weight of $e_2$ must be no less than the weight of $e_1$.
As $e_1$ and $e_2$ are part of the cycle $C$, replacing $e_2$ with $e_1$ in $T'$ therefore yields a spanning tree $T''$ with no larger weight, thus also a minimum spanning tree. Since $e_1\in T$ and $e_2\notin T$, $T''$ is more "closer" to $T$ than $T'$.
Repeat the processes above for $T$ and $T''$. Finally you will get a sequence of mimimum spanning trees between $T$ and $T'$.


The idea is that if a DFA having $n$ states isn't universal (doesn't accept $\Sigma^*$) then there must be some word of length at most $n$ which it doesn't accept. The proof is similar to the proof of the pumping lemma: take any word not accepted by the DFA, and trace its route through the DFA. You can always shorten it to a word which ends up in the same state, and additionally all states encountered are distinct. Since there are only $n$ distinct states, this finished up the proof.

An NFA having $n$ states is equivalent, via the powerset construction, to a DFA having $2^n$ states. Therefore if it is not universal then it rejects some word of length at most $2^n$. The non-deterministic algorithm you describe guesses such a word and verifies that it is indeed rejected by the NFA. Since NPSPACE=PSPACE, we can convert this into a deterministic algorithm (in fact, one using space $O(n^2)$).


What does instantiating existential variables with out of scope variable imply?

When you do an existential introduction, you are saying there is some term $t$, which is represented by the unification variable ?x, such that $P(t)\to Q$. You then try to apply $P(t)$ to $H : (\forall x.P(x)) \to Q$. It tries to generalize P ?x, because if it can show that $P(c)$ for a fresh constant $c$ (represented by x in the Coq output), then $\forall x.P(x)$ would follow. It attempts to unify that fresh constant, x, with the unification variable ?x, but this is disallowed. From a logical perspective, ?x represents a term $t$ and that term is, by definition freshness, distinct from the fresh $c$ (i.e. x) which is just to say $c$ wasn't in scope when we introduced $t$, so $t$ can't have depended on it.

As a simpler scenario, we can't prove $\exists x.\forall y.x = y$ by using existential introduction with $y$. $y$ isn't in scope at that point.


Class C can have _______ 1s with the remaining bits 0s

Check again your count of how many 1's are in the binary representation of 255.  Beyond that, there's nothing wrong with your reasoning.  The answer "25" is wrong.

Some examples are available in Wikipedia: https://en.wikipedia.org/wiki/Subnetwork


Why is the blank symbol not considered part of the input alphabet of a Turing machine?

The main reason is that it allows the machine to detect the end of its input: it's (the character before) the first blank. If you allowed blanks in the input, the machine could never know whether it might find more input by scanning farther to the right. Of course, you could solve that by having a special "end of input" character but then you have to insist that that can't appear in the input, so you've just shifted the problem one level deeper.

It also makes the initial conditions much easier to specify: the input is the non-blank section of the initial tape, which must be finite and contiguous. And if you want a blank character to be a part of the input alphabet, you can always add an extra character (call it "space" or something) and have the machine behave however you want when it sees it.


I suggest you try to run your algorithm on a few small arrays and see if it works.
Merge sort can be implemented in-place, and the same is true in your case.
Consider the recursive version of merge sort. Apart from calling itself recursively, the only other operation is merge. See if you can make a sequential list of all calls made to merge (with their parameters).


Having trouble proving a language is NP-complete

Here is a more technical answer.  The "trick" is to put all the
work in the reduction function.

Assume $NP = P$, $L \in P$ and let $x_0, x_1$ be two instances, such
that $x_1 \in L$ and $x_0 \not\in L$.  We have to show that some
$NP$-complete problem $Q$ is poly-time reducible to $L$.  By
assumption, there is an algorithm $M$ deciding $Q$ in polynomial
time.

Define a function
$$
f(x) =
\begin{cases}
  x_1 & \mbox{if $M(x) = 1$} \\
  x_0 & \mbox{else}
\end{cases}\mbox{ ,}
$$
for all instances $x$ of $Q$.  Then clearly $f \in FP$ and $x \in Q
\Leftrightarrow f(x) \in L$.


Rigorous proof against pseudo random function

How to approach it? It's always the same answer - go back to the definitions.

the definition of PRF, talks about a family of functions $\{f_k\}$. The key $k$ just selects one specific function out of this big family.

Next, for $\{f_k\}$ to be a PRF family,the definition requires that any PPT algorithm $A$ will not be able to distinguish a member of the that family, from a really-random function (that is, a function sample randomly from all-the-possible-functions).

Since all the functions in your family have a very specific structure, you can easily built an algorithm $A$ that will always answer '1' if it's input function has the structure $f_k(x)=k\oplus x$, or otherwise, it  outputs '0' (I let you complete the details). This $A$ is a distinguisher for that family-- for functions from this family it always answers 1, and for a random-function, it will answer '0' most of the times (say, it will answer '0' for at least half of those functions). Since such a distinguisher exists, the given family of functions is not pseudo-random.


How can I prove that $T(n)=\sqrt{n}T(\sqrt{n})+n$ grows as $\Theta(n\log \log{n})$?

You can use repeated substitution:
$$
\begin{align*}
T(n) &= n + \sqrt{n}T(\sqrt{n}) \\ &=
n + n + n^{3/4} T(n^{1/4}) \\ &=
n + n + n + n^{7/8} T(n^{1/8}) \\ &= \cdots
\end{align*}
$$
You reach the base case after after $\ell$ iterations when $n^{1/2^\ell} = 2$ (say), whose solution is $\ell = \log_2\log_2 n$. Assuming for simplicity that $T(2) = 0$, we get $T(n) = n\log_2 \log_2 n$.


Are problems in NP decidable in polynomial time by NDTMs, or just recognisable?

The decision problems studied in computational complexity theory are all decidable. One cannot define the worst-case time complexity for Turing machines that may fail to halt.


I will try to help you with this, even if incomplete.

Generally speaking (I don't know if you already know this or not), the camera matrix $K$ tells you how the pinhole camera projects each point in a 3D world, with some coordinates $(X,Y,Z)$ into an image-plane point, with coordinates $(x,y)$. A good reference is Wikipedia. Looking at the diagrams provided there, the 3D point has coordinates labelled $(X_1,X_2,X_3)$, which can be the same ones as our $(X,Y,Z)$ here, and the projected 2D point has coordinates $(y_1,y_2)$, which map to our $(x,y)$ here.

Let's delve into specific cases:

In the case the 3D point is $(0,0,Z)$, the point will be mapped to $(x_0,y_0)$, as the equation you provided shows. Why: in this case, the 3D point is along the line that is perpendicular to the image plane and which goes through the principal point of the camera, regardless of distance $Z$ to the camera.
For some fixed $(X,Y)$ in the 3D world, let's increase $Z$ endlessly. What happens is that, the bigger the distance $Z$ to the camera, the nearer to the camera's principal point $(x_0,y_0)$ the projected point will be. As an example, imagine a road photographed by a camera, such as this one. See how the 3D points that form the surface of the road converge to the principal point of the camera when their distance to the camera increases. This relates to the fact "parallel lines intersect themselves at infinity".

Now that we presented some specific cases, let's go a little backward in terms of why this matrix makes sense in the first place. It has to do with simple trigonometry around similar triangles. Please look at the Wikipedia article where it shows the similar triangles diagram and the corresponding mathematical formulation; you'll see the resemblance with $f\frac{X}{Z}$ and $f\frac{Y}{Z}$ elements you provided.

Now, you provided a camera matrix with high skew ($s=1$). In a pinhole camera model, you should have $s=0$, which means no skew at all, and so kill that $\frac{Y}{Z}$ parcel you have at your first entry, which only confuses you further. Skew in a camera is typically due to digitization effects and is very close to zero, not $s=1$ as you provided.

For further knowledge about this topic, I highly recommend the book Computer Vision: Algorithms and Applications
by Richard Szeliski available freely as PDF at the same link.

I just came across this good article that also thoroughly explores the pinhole camera model. It includes an interactive applet at its bottom.

I hope this helped you get a first understanding of how those entries make any sense.


Estimating (c-1) from approximation of c

No. An FPRAS for a function $f$ must return an answer between $(1-\epsilon)f(x)$ and $(1+\epsilon)f(x)$ say 75% of the time. Therefore, if $f(x)=0$, an FPRAS for $f$ must return exactly zero, at least 75% of the time: an FPRAS must be able to reliably distinguish zero from non-zero. It does not, however, have to reliably distinguish $y$ from not-$y$ for any $y\neq 0$.

In more detail, suppose we have an FPRAS for a function $f(x)$ and we want to produce an FPRAS for $f(x)-1$.  If $f(x)=1$ for some $x$, the FPRAS will give an answer in the range $1\pm\epsilon$, 75% of the time. Just subtracting $1$ from the result of the FPRAS gives an answer within the range $\pm\epsilon$, 75% of the time but an FPRAS for $f(x)-1$ would have to give exactly zero, 75% of the time.


Reducing Independent Set to a problem to prove that it is NP complete

Hint: try to reduce each vertex to a customer and each edge to an available food.


Check if knapsack problem instance is unsolvable

This is a complex set of constraints.  The standard way to solve this kind of problem is using integer linear programming (ILP).  Solving ILP instances is NP-hard -- so there is unlikely to be any polynomial-time algorithm -- but in practice, on real-world scheduling problems, solvers can often find a solution in a reasonable amount of time.  For your parameters (10 employees, 75 tasks, a few dozen time slots), I would expect that ILP might be very effective.  This kind of approach is widely used in operations research for scheduling.

So, use an ILP solver.  You can even set a time limit, and then it will return either "solution found", "no solution exists", or "time exceeded".  That will meet your requirement of identifying some instances that are unsolvable, efficiently.


Cost of computational representation in PAC-learning definition

I found a satisfactory answer in chapter 1.2.2 of "An Introduction to Computational Learning Theory" by Michael J. Kearns and Umesh V. Vazirani.

Basically they consider for each natural number $n$ a concept class $\mathcal{C}_n$ over $\mathcal{X}_n$ (where $\mathcal{X}_n$ is either $\{0,1\}^n$ or $\mathbb{R}^n$), and let $\mathcal{C} = \bigcup_{n \geq 1} \mathcal{C}_n$ and $\mathcal{X} = \bigcup_{n \geq 1} \mathcal{X}_n$. So it is indeed necessary to look at all concept classes at once in order to make sense of the parameters $n$ and $\mathrm{size}(c)$ in the polynomial that gives a lower bound of the required sample size.

In the cases $\mathcal{X}_n = \{0,1\}^n$ or $\mathbb{R}^n$ it is also clear that the cost of computational representation is in $\mathcal{O}(n)$.

All this makes sense in any setting that works for arbitrary $n$, e.g. learning axis-aligned rectangles (or $n$-dimensional boxes) can (in a natural way) be generalized to $\mathbb{R}^n$ and the universal concept class $U_n$ is obviously another example.


How to prove that these two languages are regular, or not regular?

Hints:

One of the two languages is not regular. It is the one that forces you
to count beyond 10 to decide whether some strings are in the language.
Regular languages are not very good at counting without bound.

However, the use of the pumping lemma to prove it requires that you start from a
string in the language where $n$ is as close to $m$ as permitted by
the definition of the language, and that you pump out rather than in,
i.e. remove the only $w$ of the $xwy$ decomposition of the string,
rather than inserting more copies of $w$.

Alternatively, you can prove that the reverse of the language is not
regular, if you know about closure properties.


Find a threshold such that one function is always bigger than the other

As you suspected, the threshold is indeed 3.

Here is one approach to prove that for all numbers $y \ge 3$, $c(y,y) > d(y)$.

Step 0, show that $c(\cdot, \cdot)$ is strictly increasing with respect to each variable when the second variable is not 0.
Step 1, show that $c(1,n) \gt n^2$ for all $n\ge0$.
Step 2, show that $c(2,n) \gt 2^n$ for all $n\ge0$.
Step 3, show that $c(3,n)\gt d(n)$ for all $n\ge0$.
Step 4, show that $c(y,y) \gt d(y)\text{ if }y\ge3$.

Exercise. Show that $c(3,y) > \underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{2y+2 \text{ copies of }2}$ for all $y\ge0$.


A sufficient and necessary condition about regularity of a language

Here are some necessary and sufficient conditions for a language to be regular.

Theorem. Let $L\subseteq\Sigma^*$. The following conditions are equivalent:

$L$ is generated by a regular expression (i.e., the definition of regular language).
$L$ is recognized by a nondeterministic finite automaton (Kleene).
$L$ is recognized by a nondeterministic finite automaton without $\varepsilon$-transitions.
$L$ is recognized by a deterministic finite automaton (Scott and Rabin).
$L$ is generated by a grammar $(N,\Sigma,P,S)$, where $N$ is a finite subset of $\Sigma^*$ (Frazier and Page).
$L$ is generated by a left (resp. right) regular context-free grammar.
The index of the Nerode relation $\equiv_L$ is finite (Anil Nerode, Linear automaton transformations, 1958). This is widely (and incorrectly) known as the Myhill-Nerode theorem. $\equiv_L$ is the relation used to build the minimal DFA of a regular language.
The index of the Myhill relation $\sim_L$ is finite (John Myhill, Finite Automata and the Representation of Events, 1957). $\sim_L$ is the relation used to build the syntactic monoid of an arbitrary language.
The syntactic monoid of $L$ is finite (consequence of Myhill's result). We note here that the syntactic monoid, apart from being defined by using relation $\sim_L$, can be defined as a minimal monoid (in size) that recognizes $L$ as a preimage of a homomorphism.
$L$ can be recognized by a read-only Turing Machine (trivial).
$L$ can be defined by a formula in Monadic second-order logic over strings (Büchi).

If a language does not satisfy the conditions of the pumping lemma for regular languages, then it is not regular. This means pumping lemma is a sufficient condition for the non-regularity of a language.

In summary, statements 1, 2 and 3 are false, while statement 4 is true, as you mentioned.


Operating System: replace the process's memory space with a new program

A process memory space   is :

and when you call fork with a process, the entire address space of that process gets copied, and we allocate some part of the memory to it, and when we call exec after doing fork, it replaces that copy (the child) with a new program.
(note that we usually call exec only with the child, we do this in our code using the fact that the child will return 0 to the fork value and the parent will return the process id of that child, so we use the if command and use exec if its the child)

so to answer your question, we basically replace the address space of the child that was created, with another program.


Why do we need so many transistors in a chip, and how are they managed?

This is a huge question. To fully answer it would take far more space than you'd want to read (not to mention that I suspect that there's a limit on the length of any SE answer), but I'll try to give you an idea of what goes on in the CPU.

First, a transistor (when used in a CPU) is essentially a switch, like a light switch except that you don't have to turn it on or off manually. Rather, it is controlled by an electrical current. The most important thing to understand is that modern computers are two-state devices: the only thing that really matters is whether a wire has a current or not.

One then begins the process of chip design by, for example, deciding how an integer (or other data) will be represented. For integers, say, the chip designers generally decide to them by ganging wires together in a logical unit, so with a collection of four wires it would be possible to represent 16 possible patterns: $\mathtt{0000}, \mathtt{0001}, \dots \mathtt{1111}$, where a pattern like $\mathtt{1101}$ would represent a voltage in wires 1, 2, and 4, and no voltage in wire 3 and this collection might be interpreted as the number 13. In this example, we'd have what's known a a 4-bit chip. A modern computer would have either 32 or 64 wires treated as a unit.

It happens that with a suitably-connected collection of switches (aka transistors), one can do things like add two numbers, compare two numbers for equality, decide whether a number is zero or not, and so on. Often, all of these operations are often done at once, simultaneously, and the relevant one is chosen by the current instruction, which determines which of the various results to use, and where that result will be sent. All of this traffic control is also controlled by switches, depending on what the current instruction is (in the program being executed). In addition, things like memory and registers which store information can also be implemented by these switches.

To get a feel for the number of transistors used, an adder circuit in a $n$-bit computer might require about, say, $20n$ transistors, an $n$-bit register might require $50n$ transistors, and the traffic control circuitry to sent the results to the right place might require several hundred more for each bit. It's not hard to imagine that with a lot of functionality and a wide data path (the number of wires ganged together) a modern CPU could easily take millions of transistors.

As to why "more [transistors] means faster", the answer is "not necessarily", but in general, doubling the width of the data path, say from 32 bits to 64, gives you the ability to manipulate larger numbers in a single instruction at the cost of requiring more transistors.

Finally, the registers don't really "manage everything". A register is simply a very fast storage unit, capable of storing and retrieving information far faster than, say RAM memory. For that reason, things like the current instruction are often stored in a special register (called the instruction register), simply because access to its bits is very fast. The current instruction actually "manages everything", and it's stored in a register for speed.

This is a very abbreviated explanation---I've left out a ton of detail and glossed over a lot of technical matters, but I hope it at least gives you a sense of what goes on in a modern computer. [entering duck-and-cover mode in expectation of howls of complaints from computer engineers]


Please, let me contribute to this question with some observations. Most of them refer to the reply by Shaull.

First, and foremost, I found that the answer provided to the question pointed to by Shaull is a little bit strange. The property of monotonicity is defined there in a strange way and indeed, I posted a question ---note I am not saying that's wrong but just strange to me and not very common and frankly speaking, I am a little bit suspicious that it might be wrong.

In the original question I see various questions so let's go by steps.

First, consistency is usually defined as follows [Pearl, 1984]: a heuristic $h(n)$ is consistent if and only if $h(n) \leq c(n,n') + h(n')$ for every pair of nodes $n$ and $n'$ in the state space, where $c(n,n')$ stands for the cost of the shortest path joining $n$ and $n'$. I think it is clear that admissibility (i.e., $h(n) < h^*(n)$ where $h^*(n)$ is the true optimal cost of node $n$) is immediately implied from consistency if $h(t)=0$ where $t$ is the goal node. For this and other definitions see "Common Misconceptions Concerning Heuristic Search".

So far, no need to say "Suppose I have a admissible and consistent heuristic". It just suffices saying "Suppose I have a consistent heuristic".

Now, regarding your first question. If you have a consistent heuristic, there is no need to reopen nodes or, equivalently, everytime a node $n$ is expanded by A$^*$, the path discovered to it is necessarily optimal.

Proof: Let us assume this is not true and after expanding node $n$ through a path $\pi\langle s, n_1, n_2, \ldots, n_k, n\rangle$ there was another path $\pi'\langle s, n'_1, n'_2, \ldots, n'_l, n\rangle$ such that $g_{\pi}(n) > g_{\pi'}(n)$. Note that $f(n)=g(n)+h(n)$ so that from our assumption $f_{\pi}(n) > f_{\pi'}(n)$ since $h(n)$ takes the same value in spite of the path followed to node $n$. But this is impossible, since $n$ was expanded as a successor or the path $\pi$ so that $f_{\pi}(n) \leq f_{\pi'}(n)$. Of course, you might say that the error was committed somewhere along the path $\pi'$ because a node $n'_i$ had such a large value of $h(n'_i)$ that it was delayed in the OPEN list, but this is impossible by definition of consistency.

From here it should be obvious that the condition:

if current = goal return reconstruct_path(came_from, goal)

works smoothly since once the goal is about to be expanded it is guaranteed that the path discovered to it is optimal.

Regarding your second question, the reason of your post, Shaull already answered in the footnotes of his reply: if the heuristic function is consistent then nodes are never reopened and your condition:

if neighbor in closedset continue

is enough. However, in practice, it is just simply substituted by a different condition: when expanding a node, their children are only added to OPEN if it was never expanded (not in closedset) and also, it is not already in OPEN (not in openset). With the appropriate structures for managing the open and closed list this can be done very fastly. This trick make it unnecessary to use that statement.

But again, bear in mind what Shaull says, the pseudocode you show in your post is intended to work also with inconsistent heuristic functions. What you are asking for are, indeed, simplifications that result from the assumption of consistency.

Hope this helps,

[Pearl, 1984] Judea Pearl. Heuristics. Addison-Wesley. 1984


Do "compiler" and "assembler" correspond to frontend and backend phases of a compiler?

Some compilers translate source code to assembler code in one or more phases, then use an assembler which will produce bit patterns of the instructions needed, and store them in a file that the linker understands.

Many compilers don’t do this. Producing code in assembler (human readable) form takes time. Parsing the human readable form, which is the first thing the assembler has to do, takes time again. Substantial time, actually. By generating the output directly that the linker needs, substantial time can be saved.

So usually there is no assembler involved.

And please note that (1) all these charts are just examples of how you could. The UCSD Pascal compiler had one single phase for compiling. And (2) gcc is more than a compiler. There is no iron rule how a compiler has to be organized. It's just a program, and the developers of that program figure out a good way to make the software work.

PS. Do “compiler” and “assembler” in Figure 1.5 and in the GCC figure respectively correspond to frontend and backend phases of a compiler in Figure 1.6? Absolutely not. The whole Figure 1.6 is just a more detailed view of the "Compiler" box in Figure 1.5.


Is there a way to convert a program into a Boolean formula?

Disclaimer: I'm not sure how useful any of this is for getting this done practically since you have a program, not a Turing Machine.

The Cook-Levin Theorem essentially states that you can translate the execution of a Turing Machine into a boolean formula that is polynomial in the length of the TM's execution such that the formula is satisfiable iff the TM accepts the input.

In your case 'accepts' means 'returns true'. One could model this in a TM by transitioning to an accepting state instead of returning true.

The linked Wiki article gives a good exposition of the proof but the gist if it is that you have variables that describe the input to the machine, the sequence of states the machine takes during an execution, the position of the head during an execution, and a bunch of conjunctions that force satisfying assignment of the variables to describe a successful execution of the TM on the input.


Language of TMs that accept some x in less than 50 steps. Is it in co-RE?

Maybe that will help ?

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-045j-automata-computability-and-complexity-spring-2011/lecture-notes/MIT6_045JS11_lec09.pdf

Page 42
Credits : Nancy Lynch MIT

Applications of Rice’s Theorem

• Example 3: Another property that isn’t a language property and is decidable

{ M |M is a TM that runs for at most 37 steps on input 01 }

– Not a language property, not a property of a machine’s structure.

– Rice doesn’t apply.

– Obviously decidable, since, given the TM description, we can just simulate it for 37 steps.


How does this proof show that sequences of $O(1)$ polynomially bounded Kolmogorov complexity are NOT the polynomial computable ones?

Wow, that was sooooo long ago. Something like the early nineties...

The point is, for that T, at the time of writing, the construction proper was assumed to be well-established in the background knowledge of any potential reader. Thus, we did not give details. Essentially, what you do is a Cantor-like proof as in the non-numerability of the reals: for each i, run the i-th DTIME(f) machine on a string of s(i) zeros, and add that string to T if and only if the simulated machine rejects it. (Colloquially that string was often called "the cookie".) Then g is to be any time-constructible function that allows for this process to be completed - for this we will need it considerably larger than f. There is a slight circularity in that the process depends on s, which depends on g, which is defined as sufficient time to run the process. But it is easy to upper bound this time and select a sensible g.

Hope this helps! (And hope this works. It is my first time writing anything into stackexchange.)


If you want diagrammatic material on data structures like binary search trees etc. then Introduction to Algorithms by C.L.R.S. (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein) should do the job.


One approach would be to use SIFT (or SURF, or other similar methods) to align one object to the other to account for scaling and rotation, and then compute a pixelwise distance based on the aligned images.

The right algorithm to use for alignment will depend upon the nature of the 2D images.  If they are natural-color photographs taken using a camera, SIFT, SURF, etc. might work well.  If they are black-and-white geometric shapes like shown in the question, you might do better to use image moments (e.g., Hu moments) or some other approach.


Time complexity of $T(n) = nT(n-1) + n^2$

We can compute the limit explicitly:
$$
1 + \sum_{n=0}^\infty \frac{n+1}{n!} = 1 + \sum_{n=0}^\infty \frac{1}{n!} + \sum_{n=1}^\infty \frac{1}{(n-1)!} = 2e + 1.
$$


Given 3 disjoint Turing-recognizable languages prove that one of them is decidable

Let's call MA, MB and MC the Turing machines that recognize A, B and C, respectively. The 3-TM T (a Turing machine with 3 tapes) that decides A can be described as follows:

T: input x.

Copy x on 2nd and 3rd tapes.
T executes one step of MA on tape 1. If MA accepts x, T accepts x.
T executes one step of MB on tape 2. If MB accepts x, T rejects x.
T executes one step of MC on tape 3. If MC accepts x, T rejects x.

T halts for every string x in A U B U C, so T halts for every input in Σ*. Moreover, L(T) = A. So T is a TM that decides A, and A is Turing-decidable.


Notice that if you allow once jumping without paying the weight cost, then the shortest path is exactly what you need.

Create 2 copies of $G: G_1,G_2$. For every edge $e=(v,u)\in G$ also add an edge $(v_1,u_2)$ between the node $v$ of $G_1$ and $u$ of $G_2$. Make those edge's weight to $0$.

Now, find a shortest path between $s_1$ and $t_2$ (using Djikstra)


Proving the undecidability of a language knowing the language of polynomials evaluating to 0 is undecidable

Yes like you say, you have to show that an algorithm that solves $E$ can be used to solve $D$.

A practical approach is to give a polynomial $p_E$ for every polynomial $p$ such that $p$ evaluates to $0$ iff $p_E$ evaluates to a prime number.


Data structure optimized for merging maps on partitions

I can't say that I have a fully satisfactory answer to my question. But I spent a bit of time implementing and writing about a data-structure to solve my needs here. I call the data structure a partition map. It is really just an association lists of list of integer intervals and values. The former have nicer properties, resting on top of fairly straight-forward interval comparison logic.


Does there exist a problem for which no existing solution can be parallelized on a Turing machine?

The question is not precisely defined, so it's not really amenable to a precise technical answer at this stage.  But a common view/hypothesis/expectation is that there exist problems that are inherently sequential, in the sense that they cannot be substantially sped up on a parallel computer, no matter how many parallel processors you have.  A weak version of this view is implied by the conjecture that $NC \ne P$ (see https://en.wikipedia.org/wiki/NC_%28complexity%29), which is conjectured but not known to hold.  In particular, P-complete problems are good candidates for problems that don't benefit much from parallelization.  There are stronger versions of this view; for instance, in cryptography, timelock puzzles utilize functions that are believed to be inherently sequential: a parallel processor cannot speed them up very much.


How would I go about determining popularity and relevance among articles and use it to improve my search algorithm

It seems to me like 'relevance' is a qualitative abstraction. Thus you need to define your own heuristic for your service which defines what relevance is.

I think it would be best to look for solutions in third party applications such as elasticsearch instead of implementing your own.


Is it possible to prove closure of decidable languages under union and intersection, using enumerators?

Given a decidable language $L$ consider the following enumerator:

EnumL
 loop on strings x over 0 and 1 in canonical/lexicographic order
   if x in L then print x
 end
end

This procedure enumerates/emits all strings in $L$ in lexicographic order. So you can decide if $x \in L$ by running EnumL until it prints the first string of length $|x| + 1$. If it does print $x$ until that time then it means $x \in L$, otherwise $x \notin L$. Thus, using both enumerators EnumA and EnumB you can decide $x \in A\cup B$ and $x \in A\cap B$. In other words, if one of EnumA or EnumB eventually emits $x$ then $x \in A\cup B$, and if both EnumA and EnumB emit $x$ then $x \in A\cap B$.


Create a schedule from overlapping events

One idea would be to construct an additional list of so-called 'changes'. So for your data it would look like this:

Time   Change
0      Background Start
12     Background End
2      Event A Start
3      Event A End
4      Event B Start
...

Then sort by 'Time' O(n log n)

Time   Change
0      Background Start
2      Event A Start
3      Event A End
4      Event B Start
6      Event C Start
...

Construct an empty balanced binary search tree T. Loop over the changes in order, when a change is an 'event start' add that event to T, when the change is an 'event end' remove it from T. At each change determine the highest priority event and do that until the next change (If it is not different than your last event, in which case just keep doing it).

Each of the tree operations is log n, and are done n times so this is all O(n log n). Most languages have some sort of balanced tree that could be used. You could encode the event changes as integers which represent the priority, positive meaning add this event, negative meaning remove this event. This works with non-integer times.


Optimization problem in a social network

The optimization version can be solved with logarithmic overhead by binary searching on the range $[0,\dots, n]$ of the possible values of $k$, where $n$ is the number of nodes of the input graph.

The search version of the problem can be solved with a polynomial overhead by first solving the optimization problem to obtain the maximum number $m$ of people than can be reached by $k$ observers and then:

guessing an observer $v$ in the input graph $G$,
computing the set $R$ of vertices than can be reached by $v$, and
checking whether $k-1$ observers are enough to reach $m-|R|$ people: if this is the case, then the problem is equivalent to the one of selecting $k-1$ observers in $G-R$, and the whole procedure can be repeated. Otherwise, try with a different vertex $v$.

Solving an instance of your problem when $k=0$ is trivial.

At most $n$ attempts are necessary to guess the right vertex, and the whole procedure is repeated most $k$ times, i.e., the decision problem needs to be solved at most $O(\log n + nk) = O(nk)$ times.


By definition, for any oracle for a language $A$, $(coNP)^{A}=\{L \mid \overline{L} \in NP^{A}\}$. Using this definition and definition of co-class we have

$$L \in co(NP^{NP})\iff \overline{L}\in NP^{NP} \iff L \in (coNP)^{NP}$$

You can also use $coNP$ instead of $NP$ as oracle (as Yuval commented), since if we can decide $x \in L$ using an oracle for a language $A$ we can decide $x \in L$ using another oracle for $\overline{A}$ as well, because $x \in A \iff x \notin \overline{A}$.


First note that $s \le \frac{n(n-1)}2$, equality need not necessarily hold.

Your observations are all correct:

The addition (and the head of the inner loop) is executed $O(s)$ times.
The head of the outer loop  is executed $O(n)$ times.
Neither $s\in O(n)$ nor $n \in O(s)$ holds for all possible inputs.

In this situation, there are multiple ways to give a bound that holds for all inputs:

You can use the fact that $s \in O(n^2)$ and give $O(n^2)$ as a bound for the algorithm,
you can say that the runtime is in $O(\max\{n,s\})$, or
you can say that the runtime is in $O(n+s)$.

Note that the latter two statements are acually equivalent (i.e. $O(\max\{n,s\})$ and $O(n+s)$ describe the same set of functions).


Cannot understand reductions from the halting problem and its complement

The machine $M'$ ignores its input, and just simulates $M$ running on $x$. Hence:

If $M$ halts on $x$ then $M'$ halts on all inputs.
If $M$ doesn't halt on $x$ then $M'$ doesn't halt on any input.

The notation $\tau(\langle M,x \rangle) = M'$ is the definition of a reduction $\tau$ from $\overline{HP}$ to $L_5$. The input to the reduction is an instance of the halting problem, which is a pair consisting of a Turing machine $M$ and an output $x$, and the output is the Turing machine $M'$ described above.


Hint: $L$ is regular. Draw a DFA accepting $L$, and modify it to a full-fledged Turing machine whose operation is essentially equivalent to that of the DFA.


How would a DFA be designed to accept a language defined as the string comprised of every other character in each string in another language?

This is a closure property. For language $L\subseteq \Sigma^*$, define the language $even(L) = \{ x_2x_4\dots x_{2n} \mid x_1x_2x_3\dots x_{2n-1}x_{2n} \in L, x_i\in\Sigma\}$. Now for regular $L$ the language $even(L)$ is again regular. This is a special case of closure of the regular languages under finite state transductions.

In case of this specific property an automaton $M_1$ for $even(L)$ when $M$ for $L$ is given, can be found as follows. For every pair of consecutive transitions $(p,a,q)(q,b,r)$ for $M$ introduce the transition $(p,b,r)$ in $M_1$.

Additionally one needs a somewhat formal argument that this will in fact work.

Alternatively, this closure property can be deduced from known closure properties: (inverse) morphisms and intersection with regular languages.
Make a copy of $\Sigma$: $\bar\Sigma=\{\bar a \mid a\in \Sigma\}$.
Define the morphisms $g,h:(\Sigma\cup\bar\Sigma)^*\to \Sigma^*$ where $g$ removes the bar (but keeping the letters), and $h$ removes letters from $\bar\Sigma$. $R$ is the regular language $(\bar\Sigma\Sigma)^*$
Then $even(L)$ is the composition $h(g^{-1}(L) \cap R) $.


There is no initial state, so there's no automaton. I suppose $1$ is the initial state.
From state 4 you can still read several times the symbol $*$ and accept the comment. For example, the coment /*hello*/ is being accepted, but the comment /*hello**/ is not. So you need $\delta(4,*)=4$.
Also, you need more transitions for the automaton to be a DFA. Remember that a DFA has a defined transition for all symbols from all states.

For example, you need transitions from $4$ with other symbols ($\delta(4,x)=3$ for $x\in\Sigma\smallsetminus\{*,/\}$).
The same goes for $1$ and $2$, but I leave that as an exercise ;-)


Location Selection Algorithm in Solar Engineering

The problem looks messy, so there probably isn't a clean algorithm to
produce a globally optimal solution.  Instead, I suggest you use some
combination of heuristics to try to find a nearly-optimal solution
in a reasonable amount of time, perhaps by iteratively making small
incremental improvements.

Any candidate solution is comprised of three elements:

Location of the hubs.
Assignment of each heliostat to a hub.
Routing of the harnesses.

One way to make an incremental improvement is to repeatedly fix two
of these three and optimize the other (holding the other two fixed),
and rotate through which one you change.  You seem to have a reasonable
strategy to obtain an initial candidate solution, and you could iterate from
there.  I'll sketch in more detail each of these three optimizations,
which you could rotate through repeatedly until you cannot make any
further improvement:

Harness optimization. Hold the location of the hubs and the
assignment of which hub each heliostat is associated with fixed
(to be the same as in the current candidate solution).  The goal
is optimize the routing of the harness wiring.  For
candidate algorithms for that, see the other question.  My
suspicion is that this step is the one where there are the greatest
opportunities for improving your solution, and where it's worth
devoting the most effort to.

Hub location optimization. Hold the heliostat-to-hub assignments
and harness routing fixed.  Pick a single hub and the heliostats
associated with it.  Then it's easy to fine-tune the location
of the hub to minimize overall cost, under the assumption that you
don't change the topology/routing of the harnesses.

In particular, each
harness contributes one edge from the hub $r$ to the heliostats
$h_1,h_2,\dots,h_{12}$ it is immediately connected to.  Now we want
to find a location for $r$ that minimizes the sum of distances
$d(r,h_1)+\dots + d(r,h_{12})$.  This is a sum-of-squares problem
so it can be solved through standard sum-of-squares optimization,
or simply by solving it with gradient descent; since we're in only
2 dimensions I would expect any method to converge rapidly.
You can do this separately for each hub.

It would also be possible to try a random perturbation to the
location of the hub, re-apply harness optimization, see whether
this reduced the overall cost, and if so accept that change to the
hub location.  This might be more expensive than it is worth.

Heliostat assignment to hubs. Hold the location of hubs fixed,
and assume we're not going to make radical changes to the harness
topology.  We can try to fine-tune the assignment of heliostats to
hubs in a number of ways.

One approach is to pick a heliostat $h$ that is currently assigned to
hub $r_1$ but is relatively close to another heliostat that's wired
to a different hub $r_2$, try swapping which hub it is associated
with, and see if this leads to any reduction in cost.  To determine
whether it leads to a reduction in cost you could re-run
harness optimization from scratch in both cases (which might be slow).
Or, as a fast heuristic, you could remove $h$ from its current harness,
find the nearest heliostat $h'$ that's currently connected to $r_2$,
attach $h$ to $h'$ (splicing it into the harness for $h'$), and see
whether this reduces the cost.

Another approach would be to do a more ambitious optimization.
Pick a pair of hubs $r_1,r_2$ and the set of heliostats currently
connected to either of them.  Now try to apply joint harness optimization
to that set of heliostats and those two hubs simultaneously,
simultaneously optimizing the routing of the heliostats and also
which hub each heliostat is connected.  The methods in that other
question can be generalized to solve this problem.  When finding the
solution we may find that one or two heliostats switch which hub they
are connected to.  Now repeat this for every pair of adjacent hubs.
However, my guess is that heliostat assignment might not yield many
gains (compared to the naive method of assigning each heliostat to
the hub it is closest to), so it might not be worth implementing these
more sophisticated methods for heliostat assignment.

Overall algorithm. In summary, we start from some initial
solution (e.g., selected using the method described in the question)
and then repeatedly rotate through the following three operations:

Harness optimization: fine-tune the routing of the harnesses.
Hub location optimization: fine-tune the location of the hubs.
Heliostat re-assignment: fune-tune the assignment of heliostats to hubs.

There is no guarantee that this will lead to a global optimum, i.e.,
the absolute lowest cost possible.  This could get stuck in a local
minimum.  There are various methods for dealing with that (e.g., applying
random perturbations; re-starting from multiple randomly chosen initial
solutions), which you could experiment with as well.

Hopefully this will help you find a solution that is "good enough",
or at least, get you started on some methods to try.  Good luck!


Why is the precision of floating point numbers worse for smaller numbers?

The potential error is the same in absolute terms for the same exponent.

But since the smaller numbers are about half the size of the larger numbers, the relative error is about twice as high for the smaller numbers.


Need help in understanding these relational algebra queries

Recall the definition of schema: The name of a relation and the set of attributes for a relation is called schema. An example of schema of a Movies relation is:
Movies(title, year, length, genre)

In the question, $r$, $s$ represent relation names; $R$, $S$ represent schema. Thus, we have $R = r(a,b,c)$ and $S = s(c)$. A schema consists of a set of attributes. Notation $R - S$ means the set difference between $R$'s set of attributes and $S$'s set of attributes. Thus, we have $R - S = \{a,b\}$. Now we have $\Pi_{R-S,S}(r) = \Pi_{a,b,c}(r)$.
Back to the question we have, let's work with the following example: suppose $r$ has two tuples: $(1,3,5)$ and $(2,4,8)$ with first value corresponds to $a$, second value corresponds to $b$, and the third value corresponds to $c$. $s$ has two tuples: $(5)$, $(5)$. Note we use bag semantics, which aligns with SQL semantics.
Let's consider option 1 first.
$$
\begin{align*}
\Pi_{R-S}(r) - \Pi_{R-S}(\Pi_{R-S}(r)\times s - \Pi_{R-S,S}(r))
&= \Pi_{a,b}(r) - \Pi_{a,b}(\Pi_{a,b}(r)\times s - \Pi_{a,b,c}(r)) \\
&= \Pi_{a,b}(r) - \Pi_{a,b}(\Pi_{a,b}(r)\times s - r)
\end{align*}
$$
Evaluate $\Pi_{a,b}(r)\times s$ will lead to tuples: $(1,3,5)$, $(1,3,5)$, $(2,4,5)$, $(2,4,5)$. Then, $\Pi_{a,b}(r)\times s - r$ means take out all the tuples that show up in $r$, which leads to $\{(2,4,5),(2,4,5)\}$. Then $\Pi_{a,b}(\Pi_{a,b}(r)\times s - r)$ leads to $\{(2,4),(2,4)\}$. $\Pi_{a,b}(r)$ is $\{(1,3),(2,4)\}$. The set difference between $\{(1,3),(2,4)\}$ and $\{(2,4),(2,4)\}$ is $\{(1,3)\}$, which is the result after evaluating option 1.
Now, let's consider option 2.
$$
\{t | t \in \Pi_{R-S}(r) \land \forall u \in s (\exists v \in r (u = v[S] \land t = v[R-S]))\}
$$
we have the following notation

$v$ is a tuple in $r$
$t \in \Pi_{a,b}(r)$ means that $t$ can be $(1,3)$ or $(2,4)$
$u$ is a tuple in $s$

Let's focus on $\forall u \in s (\exists v \in r (u = v[S] \land t = v[R-S]))$ part. Because it is for every $u$, we have

when $u = (5)$, there is a $v$: $(1,3,5)$ that satisfies the requirement:
$v[S] = v[c] = (5) = u$ and $v[R-S] = v[\{a,b\}] = (1,3) = t$ where $t = (1,3) \in \Pi_{R-S}(r)$. Thus $(1,3)$ belongs to the result set of option 2.
now we look at the second $u = (5)$ in $u$ and by the same analysis above, we see $(1,3)$ belongs to the result set of option 2.

Thus, the result set of option 2 is $\{(1,3),(1,3)\}$.
Let's consider option 3.
$$
\{t | t \in \Pi_{R-S}(r) \land \forall v \in s (\exists u \in r (u = v[S] \land t = v[R-S]))\}
$$
Option 3 has the same set of notation as option 2. Let's focus on $\forall v \in s (\exists u \in r (u = v[S] \land t = v[R-S]))$:

for $v = (1,3,5)$, there is a $u = (5)$ such that the requirement is satisfied:
$v[S] = v[c] = (5) = u$ and $v[R-S] = (1,3) = t$. Thus, $(1,3)$ belongs to the final result set of option 3
for $v = (2,4,8)$, there is no such $u$ satisfies the constraint.

Thus, the final result set of option 3 is $\{(1,3)\}$.
Let's consider option 4. The SQL is evaluated to $\{(1,3),(1,3)\}$.
From the above example, we can see that

option 1 and option 2 are not equivalent
option 2 and option 3 are not equivalent

Now, let's consider another example where $r$ has tuples $\{(1,3,5),(2,4,6)\}$ with the first value corresponds to $a$, the second value corresponds to $b$, and the third value corresponds to $c$. $s$ has tuples $\{(5),(6),(7)$}.
By repeating the same evaluation like we did with the first example, we can see option 1 is evaluated to $\emptyset$ whereas option 3 is evaluated to $\{(1,3),(2,4)\}$. Thus, option 1 and option 3 are not equivalent.
Thus, we show that option 2 and option 4 are equivalent.


Triangulation algorithm for an arbitary amount of points?

In general, without additional information, you can't, due to scale ambiguity; for example, you can't tell the difference between a 1" bird that's 10' away, vs a 2" bird that's 20' away.  See, e.g., Using Headpose Vector and 2D Points to Compute Distances, calculting distance between a person and the object in the image, Is it possible to transfer a point from one camera to another, given n corresponding points?, find the actual size of an object from pixel coordinates.

If you don't have additional information but want to do the best you can, there are some heuristics; see Algorithms to convert 2D videos to 3D ones.

If you know the camera's instrinsic parameters, or the positions of the cameras, or other extra information, this is solvable  Relevant technology:

object detection lets you find the 2D coordinates of an object feature in a 2D image (you can apply this to each 2D image)
algorithms for the correspondence problem let you match these points between multiple 2D images, even without first doing object detection
camera calibration lets you figure out the camera parameters

See also Fundamental and essential matrices, value of intrinsic parameters, How to obtain the camera extrinsic matrix without using chessboard.


Confusing example of a language which may be Context-free or not context-free

The best way to show that a language is context-free is to use one of the equivalent definitions of context-free languages. The two most popular ones are:

A language is context-free if it is generated by a context-free grammar.
A language is context-free if it is accepted by a (non-deterministic) push-down automaton.

The language $\{ a^n b^n : n \geq 0 \}$ is generated by the grammar $S \to aSb | \epsilon$. Let's try to use the same idea for your language: $S \to 0^k S 1 | \epsilon$ (we can implement $0^k$ using context-free rules). The problem is that we can't guarantee that the same $k$ is used in all productions. This leads me to conjecture that the language is not context-free.

How do we show that a language is not context-free? The most popular way is to use the pumping lemma or one of its variants, though this method doesn't always work. Perhaps you should give it a try.


Checking validity of formulas in first-order logic

First of all, from this post

Heuristic: To try to determine whether ϕ is valid: If the answer's not
obvious, look for an interpretation where ϕ is false.

So try to proof by negation. Consider $1:$
Let
\begin{gather*}
\phi\equiv(\exists xP(x)\to Q )\to(\forall x(P(x)\to Q)).
\end{gather*}
Now negate $\phi$ then we have:
\begin{gather*}
\neg\phi\equiv \neg(\neg(\exists xP(x)\to Q )\vee(\forall x(P(x)\to Q)))\equiv (\exists xP(x)\to Q )\wedge \neg(\forall x(P(x)\to Q))\equiv (\forall xP(x)\vee Q )\wedge (\exists x(P(x) \wedge \neg Q))
\end{gather*}
so after elimination of quantifiers:
\begin{gather*}
 \neg P(x)\vee Q
\end{gather*}
\begin{gather*}
P(C_1)
\end{gather*}
\begin{gather*}
\neg Q
\end{gather*}
oblivious that if we use resolution, and resolve each clause we achieve $\bot$.
As a result we can say $1$ is valid.
$2$ is not valid, you can use above method or if we set
\begin{gather*}
Q\equiv \top
\end{gather*}
\begin{gather*}
 P\equiv R\equiv \bot
\end{gather*}
as a result $2$ is $\bot$.
Repeat idea that used in $1$ for $3$:(as you know from logic, $A\leftrightarrow B\equiv (A\to B) \wedge  (B\to A)$) so we have:
\begin{gather*}
 \neg(((\exists x(P(x)\to Q(x)) \to (\forall xP(x)\to \exists xP(x)))
\end{gather*}
\begin{gather*}
\wedge
\end{gather*}
\begin{gather*}
(\forall xP(x)\to \exists xP(x)) \to ((\exists x(P(x)\to Q(x))  ))
\end{gather*}
After applying  negation:
\begin{gather*}
\equiv
\end{gather*}
\begin{gather*}
 (((\exists x(\neg P(x)\vee Q(x)) \wedge (\forall xP(x)\wedge \forall  x\neg P(x)))
\end{gather*}
\begin{gather*}
\vee
\end{gather*}
\begin{gather*}
(\exists x\neg P(x)\vee \exists xP(x)) \wedge  ((\forall x(P(x)\wedge \neg Q(x))  ))
\end{gather*}
Eliminate quantifiers:
\begin{gather*}
 (\neg P(C_1)\vee Q(C_1)) \wedge (P(x)\wedge\neg P(x))
\end{gather*}
\begin{gather*}
\vee
\end{gather*}
\begin{gather*}
(\neg P(C_2)\vee P(C_3)) \wedge  (P(x)\wedge \neg Q(x)  ))
\end{gather*}
As you know
\begin{gather*}
 (\neg P(C_1)\vee Q(C_1)) \wedge (P(x)\wedge\neg P(x))\equiv \bot
\end{gather*}
So we have:
\begin{gather*}
 \bot
\end{gather*}
\begin{gather*}
\vee
\end{gather*}
\begin{gather*}
(\neg P(C_2)\vee P(C_3)) \wedge  (P(x)\wedge \neg Q(x)  ))
\end{gather*}
\begin{gather*}
\equiv
\end{gather*}
\begin{gather*}
(\neg P(C_2)\vee P(C_3)) \wedge  (P(x)\wedge \neg Q(x)  ))
\end{gather*}
As a result above formula can't equal to $\top$ because we can't resolve some clauses to get $\bot$. So $3$ isn't valid.
$4$ remain as exercise, if you follow described approach for other options, you can see $4$ is not valid.


No, that is not the correct statement.

Every graph contains the empty graph as a subgraph, the problem as you define it would return TRUE for all pairs of graphs, which isn't very interesting.

Finding the largest common subgraph of two graphs would be an interesting problem, and it is at least as hard as the actual subgraph isomorphism problem (since $G$ contains a subgraph isomorphic to $H$ if and only if the largest common subgraph is isomorphic to $H$.)


I'm sure this greatly varies according to the application and the specific code in use.

Though not for DRAMs, maybe this will give you some insights:

  For CDs encoding, a (28,24)-Reed Solomon code is used.
  For DVDs, it is a (208,194)-Reed Solomon code.

Symbols are over $GF(2^8)$, that is, 8 bits per symbol.  The notation is $(n,k)$-ReedSolomon for a linear $[n,k,d]$ code ($k$ being the dimension). RS is an MDS code and has $d=n-k+1$.

(I think this was the source, but maybe you can find it online):
Stephan Wicker and Vijay Bhargava (eds.), Reed-Solomon Codes and their Applications, IEEE Press, 1994


Yes, 0^n or $0^n$ denotes the string obtained by concatenating $n$ copies of the symbol $0$.