Nilsson's sequence score for 8-puzzle problem in A* algorithm I am learning the A* search algorithm on an 8-puzzle problem.

I don't have questions about A*, but I have some for the heuristic score -  Nilsson's sequence score.

Justin Heyes-Jones web pages - A* Algorithm explains A* very clearly. It has a picture for Nilsson's sequence scores.

It explains:

Nilsson's sequence score

  A tile in the center scores 1 (since it should be empty)

  For each tile not in the center, if the tile clockwise to it is not the one that should be clockwise to it then score 2.

  Multiply this sequence by three and finally add the total distance you need to move each tile back to its correct position.

I can't understand the steps above for calculating the scores.

For example, for the start state, what h = 17?

  0 A C

  H B D

  G F E

So, by following the description,

B is in the center, so we have 1

Then for each title not in the center, if the **tile** clockwise to **it** is not the one that should be clockwise to it then score 2. I am not sure what this statement means.

What does the double starred title refer to?

What does the double starred it refer to?

Does the double starred it refer to the center title (B in this example)? Or does it refer to each title not in the center?

Is the next step that we start from A? So C should not be clockwise to A, then we have 2. And then B should be clockwise to A, then we ignore, and so on and so forth?

See if this explanation can help you:

Current pos:   Goal:
*AC            ABC
HBD            H*D
GFE            GFE

How to calculate the score:

Center

B in the center -> 1

Distances (manhattan distance)

A must move LEFT -> 1
B must move UP   -> 1
sum of distances = 2

Successors (clockwise)

current: ACDEFGH*  (skip B because it is in the center)
goal:    ABCDEFGH

the [tile,tile clockwise to it] pairs  are:
[A,C], [C,D], [D,E], [E,F], [F,G], [G,H], [H,*]
([*,A] is not considered)

the "goal" pairs are:
[A,B], [B,C], [C,D], [D,E], [E,F], [F,G], [G,H], [H,A]

There are 2 pairs that do not match the goal pairs:

[A,C], [H,*]

So the final score is: $distances + 3*(center + 2*successors) = 2 + 3 * (1 + 2*2) = 17$


Finding which strings in a set of strings have a certain prefix - can it be smaller than O(number of strings*length of prefix) If I have a set of words and need to return which of them start with a certain prefix, can that complexity be less than O(n*d), where n is the number of words and d is the prefix. I'm asking because of this video: https://www.youtube.com/watch?v=QGVCnjXmrNg (1:20 starts discussing the solution), where it says it can be lowered through using a trie with all of the words, but I think the creation of the trie would take O(n*t) complexity, where t is the average length of the words. Assume that all words will be at least as long as d (any word which has length smaller than d is disregarded immediately in the solution below, but is still considered during the creation of the trie in the video).
My idea for the solution is the simple one: go through each word and check if it starts with the same prefix. If it does, add it to the list of words which start with that prefix, otherwise don't. The reason I think this is the best solution possible in terms of worst-case complexity is as follows: if we skip even one character or one string, we may return the wrong answer. This is the minimum input that is to be considered and in any other case, it is also considered (for example, in the solution that input is considered during the creation of the trie).
Example javascript code:
function solve(prefix, words) {
    //startsWith has worst-case complexity O(d) where d is the length of the prefix
    function startsWith(word, prefix) {
        //this doesn't change worst-case complexity but means that the only disregardable input is disregarded
        if (prefix.length > word.length) return false;

        for (let i = 0; i < prefix.length; i++) {
            if (prefix[i] !== word[i]) {
                return false;
            }
        }

        return true;
    }

    const wordsArray = [];

    //since there are n (n is the length of the words array) and every iteration has worst-case complexity O(d),
    // we have a worst-case complexity of O(n*d)
    for (let i = 0; i < words.length; i++) {
        if (startsWith(words[i], prefix)) {
            wordsArray.push(words[i]);
        }
    }

    return wordsArray;
}

console.log(solve("do", ["dog", "dark", "cat", "door", "dodge"]));

I'm asking that because in the video it was mentioned that it can be faster than O(n*d), but I believe the solution was wrongly analyzed. I, however, am just a hobbyist and feel like it is more likely I'm missing something here.

In the worst case, it has to be $n \cdot d$: You must check $d$ symbols of each of the $n$ strings to confirm they all start with the prefix, if you leave any out it might be different. This is essentially an adversarial argument.
You certainly can speed it up for non-matching strings, like comparing lengths, just check some positions to rule out prefixes. If the strings are random, checking just the first symbol will weed out all but a fraction of the strings (like the program you show does, bailing out early).
If you assume random strings over an alphabet of $m$ symbols, they will agree with the first $k$ symbols of your needle (which you are looking for in the haystack) $1/m^k$ of the times. The number of checks to do for each string will then be on average:
$\begin{align*}
   c
     &= 1 + \sum_{2 \le k \le d} \frac{k}{m^k}
\end{align*}$
(you do $1$ check regardless, then $k$ more checks if $k$ symbols match).
To compute this sum, note that:
$\begin{align*}
  f(z)
    &= \sum_{0 \le k \le d} \frac{z^k}{m^k} \\
    &= \frac{1 - z^{k + 1} / m^{k + 1}}{1 - z / m} \\
    &= \frac{m^{k + 1} - z^{k + 1}}{m^{k + 1} - z m^k}  \\
  f'(z)
    &= \sum_{0 \le k \le d} \frac{k z^{k - 1}}{m^k} \\
  f'(1)
    &= \sum_{0 \le k \le d} \frac{k}{m^k} \\
    &= \frac{m^{d + 1} - (d + 1) m + d}{m^d (m - 1)^2} \\
  c
    &= 1  + f'(1) \\
    &= 1 + \frac{m^{d + 1} - (d + 1) m + d}{m^d (m - 1)^2}
\end{align*}$
Thus the number of symbol comparisons for one string is approximately $(m + 1) / m$, as you'd suspect.


Find all edges of G contained in some MSP I have the following question in a homework:

Let $G = (V,E)$ be an undirected graph, and let
$$A = \{ e \in E \mid \text{ s.t. exists an MSP $T$ containing } e\}.$$

We were asked to find $A$ in $O(m \log n)$ time.

Any suggestions?

We call an edge superheavy if it is the unique heaviest edge in some cycle. This post shows that an edge $e\in A$ if and only if $e$ is not superheavy.

To find all edges that are not superheavy, we can first sort the edges according to their weights from small to large. Then, we remove all edges, re-add them in this order, and track the connected components by a disjoint-set data structure.

Now we can check whether an edge $e$ is superheavy by checking whether it connects two vertices in different connected components in the graph with edges whose weights are less than $w(e)$: If $e$ is superheavy, then the two endpoints of $e$ are connected by a path on which the edges have weights less than $w(e)$, so the two endpoints must lie in the same connected components in the graph with edges whose weights are less than $w(e)$. On the other hand, if $e$ connects two vertices in the same connected components in the graph with edges whose weights are less than $w(e)$, then we can find a path connecting the two endpoints of $e$ on which the edges have weights less than $w(e)$, so $e$ along with this path forms a cycle and  $e$ has the largest weight in this cycle, so $e$ is superheavy.


Was my Huffman coding solution wrong? I finished my exam a moment ago and one of the question was to calculate Huffman coding for given probabilities:

A: 0.15
B: 0.2
C: 0.55
D: 0.1

I encoded them as follows:

A: 110
B: 10
C: 0
D: 111

But my lecturer told me that this results seems odd and gave me just a fraction of points for my solution. I argued that all my encodings have unique prefixes. I also said that all my encodings has same length as his (he compared my solution with his reference solution), thus they have same entropy.

Do I really don't understand Huffman codding? I found the theory behind this algorithm amazing so I would like to know.

Huffman's algorithm is actually an "algorithm scheme", that is, a specification for an entire class of algorithms. Roughly speaking, Huffman's algorithm is any instantiation of the following scheme:

  While there is more than one symbol, choose (in an unspecified way) two leaves of minimum total probability, and merge then (in an unspecified order).

Any particular instantiation will include a tie-breaking rule for choosing the two leaves, and will order them in some specific way.

In your case, there is only one choice for the two leaves, but there are several choices for the order (two at each of the three iterations of the algorithm). Hence your distribution supports 8 different "Huffman codes". It might be that the one you chose is not the canonical one which is produced by the specific implementation you were taught in class. The 8 Huffman codes for your distribution are:
$$
\begin{array}{c|l|l|l|l|l|l|l|l}
A & 110 & 111 & 100 & 101 & 010 & 011 & 000 & 001 \\\hline
B & 10 & 10 & 11 & 11 & 00 & 00 & 01 & 01\\\hline
C & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\\hline
D & 111 & 110 & 101 & 100 & 011 & 010 & 001 & 000\\
\end{array}
$$

An important fact to be aware of is that not while Huffman's algorithm is guaranteed to produce a minimum redundancy code, not all minimum redundancy codes can be produced by Huffman's algorithm. See Gallager's classic paper Variations on a Theme by Huffman.


Can computers lose information? I've heard that computers cannot forget anything, but yesterday my teacher told me that a computer can lose its memory from getting very hot. Is that true that computers can lose information? How and why does this happen? Can the lost information be retrieved back?

It depends on what "memory" you are talking about. Basically, nothing in a computer can contain data forever. Random Access Memory in a computer loses its data after it is no longer powered, a hard drive has a data retention of approximatively 10 years (this may be different now because of SSDs/SSHD/etc, but you get the idea). There are also several cases where a memory becomes amnesic, but knowing that there are many types of technology for memory, it can vary greatly. It is sometimes possible de retrieve lost data, but again, it depends on the technology.


Find the recurrence relation for the following algorithm The question requests to find the recurrence relation of the following algorithm and solve it using the characteristic equation.
\begin{align}
&\text{SORT}(A[0\dots n-1])\colon\\
&\quad \text{if } n = 2 \text{ and } A[0] > A[1] \text{ then} \\
&\quad\quad \text{swap}(A[0],A[1]) \\
&\quad \text{else if } n > 2 \text{ then} \\
&\quad\quad m=\lceil 2n/3 \rceil \\
&\quad\quad \text{SORT}(A[0\dots m-1]) \\
&\quad\quad \text{SORT}(A[n-m\dots n-1]) \\
&\quad\quad \text{SORT}(A[0\dots m-1])
\end{align}
The recurrence equation that I found is $T(n) = 2 \cdot T(2n/3) + T(n/3) + 1$ with base case $T(2) = 5$.
The base case is $T(2) = 5$ because of 2 comparisons in the if statement plus 3 statements in swap() function.
I'm not sure whether what I've tried is correct or not.
All help is appreciated!

Your recurrence relation is almost correct. Here are some small issues with it:

The length of the array $A[n-m\ldots n-1]$ is $m$, not $n-m$.
Your recurrence only holds when $n$ is divisible by 3. The exact length of the arrays in the recursive calls is $m = \lceil 2n/3 \rceil$.
You are not handling arrays of length $1$.
You are trying to count operations, but without a precise model of computation, this is really impossible. There are two common options here: either you count specific operations, for example only comparisons and swaps, or you just give up and replace everything with $O(1)$. Both options are common.

Accordingly, here are some more accurate solutions are:

When counting only comparisons of array elements, the recurrence is $T(1) = 0$, $T(2) = 1$, and $T(n) = 3T(\lceil 2n/3 \rceil)$ for $n \geq 3$.
When counting only swaps, the recurrence is the same as in the first bullet. Note that $T$ is actually an upper bound on the worst-case cost of your procedure.
When counting both comparisons of array elements, the recurrence is the same as in the first bullet, with "$1$" replaced by "$2$".
When counting the running time on a RAM machine (the standard computation model for analyzing algorithms), the recurrence is
$$T(n) = \begin{cases} O(1) & \text{if } n \leq 2, \\ 3T(\lfloor 2n/3 \rfloor) + O(1) & \text{otherwise.} \end{cases}$$

One fine point is that except when counting comparisons, the recurrence $T$ is for an upper bound on the cost. The exact cost depends on the instance, and often we are interested in estimating the worst-case cost as a function of the input length (in this case, $n$). However, the recurrence for $T$ isn't even guaranteed to compute the worst-case cost: it could be too pessimistic. For example, it could be that no input causes all possible swaps to be performed. Nevertheless, $T(n)$ does upper-bound the cost of the procedure on any input of length $n$.


Can top SAT-solvers factor easy numbers? Modern SAT-solvers are very good at solving many real-world examples of SAT instances. However, we know how to generate hard ones: for instance use a reduction from factoring to SAT and give the RSA numbers as input.

This raises the question: what if I take an easy example of factoring. Instead of taking two large primes on $n/2$ bits, what if I take a prime $p$ on $\log n$ bits and a prime q on $n/\log n$ bits, let $N = pq$ and the encode $\mathrm{FACTOR}(N)$ as a SAT instance. $N$ would be an easy number to factor by brute-force search or sieve methods since one of the factors in so small; does a modern SAT-solver with some standard reduction from factoring to SAT also pick up on this structure?

Can top SAT-solvers factor $N = pq$ where $|p| = \log n$ quickly?

There are other much simpler instances which we provably know that the current algorithms cannot solve in sub-exponential time. These algorithms are incapable of counting (almost all of them are improvements of DPLL which correspond to Resolution propositional proof system).
Unfortunately such examples are unsatisfiable instances. The question about finding  natural satisfiable hard instances for these algorithms is an interesting research problem (Russell Impagliazzo mentioned this during the proof complexity workshop last year at Banff). There are satisfiable instances that we provably know the algorithms fail badly if there is any such instance, but they are not very natural (they are based on formulas expressing the soundness of algorithms).
Regarding factoring, if the size of numbers are small (e.g. logarithmic as in your case, i.e. the numbers are given in unary), then theoretically there is no result that says there cannot be solved by current algorithms, and in fact we can write simple polynomial time algorithms that factor these numbers. So whether a particular SAT solver program can solve them might depend on the particular algorithm.


Bellman-Ford parent pointer (?) negative cycle First of all, let me preface by saying that this question is not completly new but the original question hasn't been answered. More important, this is only basic question on understanding the proof itself.

So after some search in the site I found the following question : Bellman-Ford algorthm and negative cycle proof.

The guy is trying to understand how to prove that a cycle in parent pointer is necessarily a negative cycle.

My question is very basic and isn't duplicate, I just couldn't find anything in the document on the related question which answers my question.

What does it mean a cycle in the parent pointer? I mean I could a graph whereas the cycle in the parent pointer isn't a negative cycle... I don't understand why It must be a negative cycle.

See an example of a graph I have in mind :

Now suppose the first node we start with is (a) and suppose the we travling the edges in the following order: ab,bc,cd.

and here we goes, we have a cycle in the parent pointer, and as far as I understand that is (c) becuase it is the parent of (d) and yet the cycle isn't negative cycle.

In the notation here, a vertex $v$ is called a parent pointer of a vertex $u$, if a shortest path to $u$, found so far in the algorithm, has $v$ preceding $u$. So in the graph above, starting at $a$ and moving to $b,c,d$ in that order, the parent pointers are $a,b,c$ respectively for $b,c,d$.

We say there is a loop in parent pointers if we have vertices $v_1,v_2, \ldots ,v_n$ such that $v_i$ is a parent of $v_{i+1}$ and $v_n$ is a parent of $v_1$. Notice that this is not happening in the earlier example. But if we change the weight of edge $(c,a)$ to $-3$, then we have $a$ as parent of $b$, $b$ parent of $c$ and $c$ as parent of $a$, forming a loop in parent pointers, indicating a negative cycle.

Proof for why this finds negative cycles is given in the document referred in that earlier post

Edit:

Suppose we have found a cycle $v_1,v_2,\ldots , v_n$ in parent pointers ($v_i$ is parent of $v_{i+1}$ and $v_n$ is parent of $v_1$). Let $P(v)$ denote the shortest path length obtained to vertex $v$ so far. Then, as $v_i$ is parent of $v_{i+1}$, we get $P(v_{i+1}) = P(v_i) + w(v_i,v_{i+1})$, where $w(u,v)$ is weight of the edge from $u$ to $v$. So $P(v_n) = P(v_1) + \sum_{i=1}^{n-1} {w(v_i,v_{i+1})}$. We have reached $v_n$ so far and now looking at its neighbour $v_1$. And $v_n$ is made parent of $v_1$. Which means the shortest path length to $v_1$ ($P(v_1)$) found so far is bigger than the path coming from $v_n$. That is, $P(v_1) > P(v_n) + w(v_n,v_1)$. Hence,

$$
P(v_1) > P(v_1) + \sum_{i=1}^{n-1} {w(v_i,v_{i+1})}
$$
$$
0 > \sum_{i=1}^{n-1} {w(v_i,v_{i+1})}
$$

So any cycle in parent pointers corresponds to a negative cycle in the graph.

Note that this is only one half of the proof. We still need to show the converse (whenever there is a negative cycle in the graph, we will get a cycle in parent pointers).


How to calculate Kolmogorov Complexity if we have access to an Oracle for the HALT Problem I try to solve the following exercise:

We know that K (x), the complexity of Kolmogorov, is incomputable. Show how
calculate it, if we have an oracle for the membership problem (or for the HALT problem, if it accommodates more).

I have solved it in the following way:

Let (w) be the string to which I compute K (w).

(1). I have a TM 'G', which generates TM descriptions in order of length 'Mi'.

(2). The generated descriptions 'Mi' and (w) are inputs of a TM that has a Oracle for the Membership Problem TMO 'Memb'.

     * If TMO 'Memb' rejects then TM 'G' generates a new description Mi + 1, returns to step (1).
     * If you accept this description Mi and (w), they pass as input to the TM 'R', go to step (3).

(3). TM 'R' runs the description Mi with input (w) and prints the number of steps (t).

(4). Then K(w) would be |< Mi >| + t

It would be necessary to run TM 'R' or I can replace the problem of the Membership with the one of the HALT Problem and this gives me that number of steps that I calculate with TM 'R'?

regards

Here is the idea. Given a string $x$ whose Kolmogorov complexity you want to calculate, go over all programs in non-decreasing order of length. For each program $p$, check using the oracle whether it halts, and if so, check whether it outputs $x$. If it does, the Kolmogorov complexity is the length of $p$. Otherwise, go to the next program. Eventually you will find a program computing $x$. The program you will find is a shortest one since we go over all programs in non-decreasing order of length.


Handling TOCTTOU with system calls What are some of the best practices when implementing system call functionality for handling/avoiding "Time of check to time of use" (TOCTTOU) security issues?

One of the simplest ways to avoid TOCTTOU issues is for your system calls to perform the check at time of use (within the system call) instead of trusting a prior check. If you can gracefully fail a check upon use, the caller can instead rely upon exception handling to avoid a check race or a vulnerability. This methodology will help with both long-running and short-running scenarios.

To further assist with short-running scenarios, you could implement transactions for your security-related system calls. Of course, this would require being architected in early on, and would influence the design of the system call APIs, but it would provide concurrent consistency across the system.


What does it mean that a set of intervals is sorted by the right and left endpoints? While reading a paper (On the k-coloring of intervals), I came upon the following description:
"Input: An integer k, and a set of n intervals sorted by right and left endpoints. The intervals are indexed in order of increasing right endpoint, and it is assumed that all endpoints are positive integers."
What does it mean that they are sorted by "right and left endpoints"? Does it mean that each interval is on the form (left endpoint, right endpoint)?

Yes, you are right. The intervals are of the form (left endpoint, right endpoint).
First, consider the following statement:

The intervals are indexed in order of increasing right endpoint

It means that given a set of intervals $I_{1}, \dotsc, I_{n}$, the $(\textrm{right endpoint of }I_{i})$ $\leq$ $(\textrm{right endpoint of }I_{j})$ for any $i \leq j$ and $i,j \in \{1, \dotsc,n\}$.
Similarly, you can define the sorted order based on the left endpoints. However, the sorted order based on these two criteria could be different.

Now, consider the following statement:

a set of n intervals sorted by right and left endpoints

This statement is a bit unclear since the sorted order by left endpoints could be different from the sorted order by right endpoints. However, in Section 1(Introduction) of their paper, they also mention the following statement: "set of $n$ sorted intervals (the $2n$ endpoints of the intervals are sorted). ". Therefore, the sorting by "right and left endpoint" simply means that you are sorting the set of all $2 \cdot n$ points together, i.e., the set: $\{ \ell_{1}, r_{1}, \dotsc, \ell_{n}, r_{n} \}$ is given in sorted order irrespective of point being a left or right endpoint. Furthermore, using this sorted set you can easily recover the sorting of intervals based on (right endpoint) or (left endpoint) in linear time i.e., $O(n)$. This does not change the running time of their coloring algorithm which is $O(n + k)$.


Difference between stable marriage problem and assignment problem What is the difference between the stable marriage problem and an assignment problem? Both refer to a matching problem in general but what is their specific difference?
I can see clear differences in the implementation but do not see any related to the motivation. Both aim at assigning a man to a female -  both approaches take into account preferences.

The main difference is the optimization goal.

In classical assignement problem, there is a fitness/cost function to maximize/minimize. Each assignement possibility has a weight and you only sum up all these weights to get the best global result. Only the overall result matters even if it means some individual assignements have a very bad fitness/cost.

In the stable marriage problem, it is the opposite. You do not care about the overall optimality. You just want to guarantee that it does not exist a "male" and a "female" that would both be "happier" together rather than with their assigned partner.

The idea behind the word "stable" is that if such a couple exists, they will tend to get together breaking your initial assignement.

An exemple:
two "males" A and B and two "females" C and D

A loves hardly C (weight 10) and not D (weight 1)
B loves a little more C (weight 3) than D (weight 2)
C loves a little more B (weight 3) than A (weight 2)
D loves hardly B (weight 10) and not A (weight 1)

In assignement problem, you clearly put A&C and B&D to get a fitness score of 24. But this is not a stable marriage as B and C would rather like to be together. A&D and B&C is a stable marriage but only has a fitness score of 8.


How is the NP verifier polynomial? If we start with the definition of L being in NP if "there exists a polynomial NTM that decides L" (where polynomial for an NTM means the length of the worst run as a function of the size/length of the input / the maximal tree depth)

There is a proof that L is in NP iff there exists a polynomial TM verifier for L.
Regarding the "L is in NP" -> "there exists a polynomial TM verifier for L" side:
Let N be that NTM
I fail to understand how given (w, R) where R is the encoding for an accepting run of N on w, we can verify this in polynomial time in regards to w (as this is how the time complexity for a Verifier is defined)

We can show R's length is polynomial in w, but how would we verify that it is a valid run for N in polynomial time?
We need to verify every 2 consecutive configurations in R are valid, but since for NTM's the transition function maps to a set of (Q x Gamma x {L,R}) possibilities - I can't figure out how this is possible.

Update:

Let me clarify a little further.
An obviously bad (non polynomial) solution would be to have the verifier initially write the whole encoding on N on its tape, and then "search through it" to see if a transition is valid. But since the encoding of N is certainly not necessarily polynomial in N, this doesn't work.

It seems the answer has to rely on having the "inner workings" of N "embedded" in the verifier therefore avoiding time complexity issue as we are avoiding time complexity issues by having things "embedded" - but I fail to see how that could then be used further.
I see how this opens an avenue of possibility, but can't see it through.
I'm assuming there is some low-level technical grunt work so that the right transitions can be "embedded" straight into the verifier.

You run your NTM, and at any point where it could decide between n > 1 actions, it picks an action k and writes k to a tape.
Now you build a TM. It’s identical to the NTM, except at every point where the NTM made a decision, your TM reads a number k from the NTMs successful run, and takes action #k. That’s it.


Regular expressions and semi-linear sets In proving Parikh's Theorem, my Theory of Computer Science textbook defines a linear set as:

$u_0 + \langle u_1, \dots, u_m \rangle = \{u_0 + a_1u_1 + \dots + a_mu_m \mid a_1, \dots, a_m \in \mathbb{N}\}$ where $u_i$ are vectors of natural numbers.

and a semi-linear set as a union of finitely many linear sets. It goes on to say ''For every semilinear set $S \subset N^k$, it is not hard to construct a regular set $R \subset \Sigma^*$ such that $\psi(R) = S$'' (where $\psi$ is the Parikh map, taking strings over an alphabet $\Sigma$ to vectors where the first entry is the number of the first letter, the second entry is the number of the second letter, etc. So $\psi(\{a, ab, ba, aaa\})) = \{(1), (1, 1), (3)\}$.)

I was trying to think why regular languages would be semi-linear instead of just linear, and it seems like the + (or) operation in regular expressions is to blame. Is this correct: are languages described by regular expressions which use only concatenation and $^*$ linear?

Your claim is correct for a one letter alphabet $\Sigma = \{a\}$. We prove by induction that $\psi(r)$ is linear for every regular expression without addition. When $r = a$, $\psi(r) = 1$. When $r = r_1 r_2$, by the induction hypothesis $\psi(r_1) = u_0 + \sum_i \mathbb{N} u_i$ and $\psi(r_2) = v_0 + \sum_j \mathbb{N} v_j$, and so $\psi(r) = u_0 + v_0 + \sum_i \mathbb{N} u_i + \sum_j \mathbb{N} v_j$. When $r = r_1^*$, $\psi(r)$ is a subset of $\mathbb{N}$ closed under addition. Let $g = \operatorname{gcd}(\psi(r))$. Then $\psi(r)/g$ is a numerical semigroup, and so finitely generated, say $\psi(r)/g = \sum_i \mathbb{N} u_i$. So $\psi(r) = \sum_i \mathbb{N} gu_i$.

This argument doesn't quite work when $|\Sigma| \geq 2$, although there are some notions of GCD for multidimensional vectors, see for example this interesting presentation by Vadim Ponomarenko. Perhaps the argument above can be pushed through, or perhaps a different argument, which uses the fact that $\psi(r_1)$ is linear, exists. It's also possible that the claim is wrong in this case.


Finding a Hamiltonian path in this graph family Given a directed graph $G = (V, E)$, you have been told that a Hamiltonian path $p_0p_1\ldots p_V$ exists with the property that for each edge $p_ip_j$ that is not part of the Hamiltonian path, $i > j$.

Find any Hamiltonian path.

It is not too hard to find an $O(|V||E|)$ solution to this problem: for every vertex with out-degree one, try starting a BFS from this vertex. If ever there is more than one vertex that could be expanded next in the BFS, give up and try another vertex.

I am not necessarily looking for a more efficient solution than this (though that would be nice), but I'm having trouble finding literature on this type of graph (in general, it seems very hard to look up literature on a family of graphs you do not know the name of).

Do you know where I can find out more about this graph family, or other graph families that involve guaranteeing the existence of a Hamiltonian path/cycle with interesting properties?

The class of graphs that contain a Hamiltonian cycle is known as Hamiltonian graphs. Being Hamiltonian doesn't really imply much: a wide range of well-known graph parameters (diameter, treewidth, chromatic number, ...) can still be unbounded. At least partly, this is the reason there aren't many non-trivial subclasses of Hamiltonian graphs known.

As an example, every 2-connected $(P_6,K_{1,3})$-free graph is Hamiltonian (see e.g., [1]). Further, [1] also cites some conjectures which claim that every 2-tough graph is Hamiltonian, or that every 4-connected $K_{1,3}$-free graph is Hamiltonian.

On the algorithmic side, even recognizing Hamiltonian graphs is of course well-known to be NP-complete. That is, recognition means the problem of deciding whether a given graph is Hamiltonian or not. Also, because many structural parameters remain unbounded, many classical problems also remain hard for Hamiltonian graphs (as there is no clear algorithmic foothold to exploit).

You might also enjoy Hypohamiltonian graphs, which are "almost Hamiltonian".

[1] R. Faudree, E. Flandrin, Z. Ryjacek. Claw-free graphs - a survey. Discrete Math. 164 87-147 (1997)


Irregularity of language of words whose length is of power of 2 How to show that the language containing the words whose length is a power of $2$, $L=\{w\mid|w|=2^i\}$, isn't regular using the pumping lemma?
The pumping lemma says that

Let be M a regular language. Then it exists a number $p>0$ such that for each word $w\in L$, such that $|w|\ge p$, it exists $x,y,z$ such that :

$w=xyz$
$|y|>0$
$|xy|<p$
For each $i\ge 0$ we have $xy^iz\in L$.

(I don't perfectly understand this lemma...). I have great difficulties to understand the examples which I can provide you in French here.
My question is different from How to prove that a language is not regular? as far as all answers are based on $L=\{w\mid|w|=a^pb^q\}$ scheme, mine only have one element and is playing on the size rather than the scheme.
My attempt
We take $w=a^{2^n}$. Therefore we have $w\in L$ and $|w|\ge p$. We need a partition $w=xyz$ (to fill in condition 1.) such that $|xy|<p$ (condition 3) and $|y|>0$ (condition 2).

Let's assume $L$ is regular.
I thought about taking $|w|>n$
$x = aaaa....$ , $y = aaaa...$,
$|x|=s$, $|y|=k$. We need to consider ALL the options, that is all
the possible $s,k$ such that $s≥0$,$k≥1$ and $s+k≤n$.

Let's take $i=0$, then $xy^iz=xz=a^{n-k}a^n\not\in L$ whatever may $s,k$ be and since $k\ge 1$, $L$ isn't regular at all (but why) and we reach a contradiction.
I have some difficulties understanding the conclusion.

The strategy for proving a language non-regular is a proof by contradiction:

We assume that $L$ is regular. This then means that there exists a $p > 0$ such that every string $w \in L$ where $|w| \geq p$ can be partitioned as $s = xyz$ such that this partition satisfies conditions 1, 2 and 3. But now it is enough to find some $w$ where $|w| \geq p$ such that no partition can satisfy all three conditions simultaneously.

In the concrete case, you have not told us what alphabet $\Sigma$ we are considering. I assume that $\Sigma = \{ a,b\}$, but this is not important.

So we assume that $L$ is regular, and therefore there must exist a $p > 0$ such that every string $w \in L$ where $|w| \geq p$ can be partitioned as $s = xyz$ such that this partition satisfies conditions 1, 2 and 3.

But now consider $w = a^{2^p}$. Clearly, $w \in L$. Moreover, we have that $|w| \geq p$, so there should be some partition of $w = xyz$ that satisfies conditions 1, 2 and 3.

If the partition must satisfy condition $3$ then the first two parts of the partition, that is, $xy$, must have total length less than $p$. Therefore, $|y| \leq p$. If the partition must also satisfy condition $2$, then $y$ cannot be the empty string, so $y = a^k$ for some $k$ where $0 < k < p$.

But can such a partition then also satisfy condition $1$? No. It is enough to find an $i \geq 0$ such that $xy^iz \notin L$ to see this. Take $xy^2z$. This string has length $2^p + k$, and since $k < p$, we know that $2^p + k$ cannot be a power of $2$. So $xy^2z \notin L$.

–

In other words: The appropriate strategy is to try to satisfy the conditions one by one. Usually, we first try to satisfy condition $3$. This will tell us where $y$ can appear (among the first $p$ symbols) and how long it can be. Given that, we then try to also satisfy condition $2$, and this usually just provides with the useful information that the string $y$ that can be repeated, is non-empty. Finally, we show that we can "pump our way out" of the language with this partition, thereby violating condition $1$.


How to compute all primes between upto $n$ in time $O(n)$ time? Suppose that I want to compute all the prime numbers between 2 and $n$. The natural way or most obvious way to do so is given below. Let $A$ is an array contain the numbers from $1$ to $n$.

For $j=2$ to $j=\sqrt n$
mark multiples of $j$ from $A$

Running time of this algorithm is $O(n \log n).$ It is easy to see that after first iteration there will be $n/2$ many unmarked elements and so on.

The problem with this method is that some of the elements may be marked more than one time.

Question : How to compute all the primes upto $n$ in $O(n)$ time?

You can use a sieve to enumerate all prime numbers up to $n$.  There are multiple algorithms; see the Wikipedia article I link for some examples.  The sieve of Atkin and wheel sieves apparently run in $O(n)$ time.


BVH construction without sorting Common algorithms for creating bounding-volume-hierarchies (BVH) rely on grouping primitives together that are not necessarily adjacent in memory. This is either done by rearranging the primitives directly or using an index which is then sorted. What if we are not allowed to change the order of the primitives? More formally:
Let $P=\{p_1, p_2, ..., p_k\}$ be an ordered set of primitives. A BVH can be constructed by splitting the set of indices $I=\{1,2,...,k\}$ into two subsets $I_l$ and $I_r$ so that $I_l\cap I_r=\emptyset$ and $I_l \cup I_r=I$. $I_l$ and $I_r$ correspond to the indices of all primitives in the left and right child node of the root node. This procedure then repeats recursively for $I_l$ and $I_r$ and so on.
Now add the additional constraint that $\forall i \in I_l \forall j \in I_r(i<j)$. This prevents rearranging and makes the problem quite interesting in my opinion.
The quality of the best achievable BVH without rearranging primitives depends heavily on the initial order of the primitives. Instead of choosing a spatial split position, for example using the surface area heuristic, we are restricted to choosing a split index instead. My guess is that this would make agglomerative clustering algorithms much more attractive, as only adjacent primitives can be clustered together, not arbitrary pairs of primitives.
Has this problem been studied in the literature before?

Just some pointers:

I remember seeing a paper about kd-trees being executed on a GPU, which I think implied them being presorted and then moved into GPU memory. Kd-Trees are not BVHs though.

Also, there are bulkloaded R-Trees (R-Trees are basically BVHs), such as the STR-R-Trees (sort-tile-recurse) which pre-sort primitives, but not necessarily with memory locality in mind, but that could easily be achieved.

Finally, there is the PH-Tree (disclaimer: I wrote the paper about it). It stores all geometric data for each node in a single byte-stream for this node (maximum memory locality), however, the parent and children of a node are not necessarily neighbors in memory (the actual implementation, e.g. V13, uses object pooling, so many nodes are likely to be close in memory, but that is not a given, let alone scientifically evaluated. Also, the PH-Tree is not a BVH, it is more like a quadtree. Also, the PH-Tree has come a long way since the original version, it now supports rectangles/boxes (the original paper only mentions points).


Particularly Tricky Recurrence Relation (Master's Theorem) Master's theorem is shown below,

The recursive function to be solved is shown below,

I understand that a refers to the number of recursive calls in this function (3 in this case). b refers to what the input size is being divided by in each recursive call. Which I believe should be 4.
d refers to the overhead of each recursive call, which should be 1.

So we have:

a = 3
b = 4...?
d = 1

The problem is, b apparently doesn't equal 4.

Now the actual answer shows that the answer is:

Which seems incorrect, since given the Master's Theorem, I don't see how n is being subtracted by a constant.

Thank you for your help.

Since n refers to "the length in bits of x", you should translate n with the binary log of x, and (n-2) with the binary log of x/4.

Hope it helps.


What are the differences between LCF's Theorem and Automath's Prop? How are the fundamental approaches to proving theorems by LCF and Automath different? Considering their modern descendants - Isabelle for LCF and Coq for Automath, both rely on type checking to do proof checking.
Theorems in Isabelle have a theorem type and the only functions that can create instances of this theorem type are inference rules of the logic.
Theorems in Coq have a Prop type and the only way to create Props is by creating proof terms that have the proposition as their types.
If I'm not wrong, LCF and Automath were developed independently around the same time so there wasn't an influence from one to the other, but perhaps by coincidence, is LCF's (Isabelle's) Theorem just a more generic version of Automath's (Coq's) Prop?
I would appreciate it if you could also point out any other fundamental differences between LCF and Automath that have manifested into their modern successors.

The difference is in what kind of type theorem/Prop is.
In Isabelle, theorem is a type in the underlying implementation language, that is made abstract so that the only way to create an inhabitant of that type (i.e. a valid theorem) is in the end to resort to the primitives provided by the kernel. So it is the typing constraints of the implementation language together with the restricted primitives that forces you to inhabit only correct theorems. Also, in that setting proofs can be any program in the implementation language producing an object of type theorem, but they have no specific status, and cannot be manipulated directly.
On the contrary, Prop is a type in the theory of Coq, but not in its implementation language: if you look at the OCaml code, there is no such thing as a Prop type, only a type of terms. Verifying that a term (written in a specific language called Gallina, the proof/programming language of Coq) is indeed a valid proof is a job of a specific type-checker. This type-checker is the kernel. In that setting, proofs have a specific status, being syntactical objects of a given type of terms in the implementation, and as such can be manipulated, inspected and so on. In particular, the tactic languages are used to generate such proofs, which is not the same as directly constructing an inhabitant of theorem, because such terms will still in the end be inspected by the kernel, which is the only judge of what is a valid proof.


Linked List fundamental concepts I am trying to understand the basics of Linked List. The definition of my LinkedList class is as follows:

public class ListNode {
 int val;
 ListNode next;
 ListNode(int x) { val = x; }

Now I am facing a problem. My code is as follows:

ListNode dummy = new ListNode(0);
dummy.next =  head;
ListNode prev = dummy;
ListNode slow = head;
head.next = null;
prev.next = slow;

ListNode temp = slow.next;
prev.next = temp;

System.out.println(dummy.next); //comes out null

Why is it coming out as null? dummy.next was pointing to head and I only changed slow and prev?

Can we use slow and head interchangeably? If yes, then why does this happen?

// head points to a Linked list starting from 1 in 1 -> 2 -> 3
ListNode curr = head;

while(curr.next!= null){
    curr= curr.next;
}

System.out.println(curr);
System.out.println(head); //these are different and head does not change

This has nothing to do with linked lists and everything to do with references (see also pointers). When you assign a mutable object to a variable, the variable holds a reference to the actual object: its memory address. If you assign the same object to two different variables, they both reference the same object; both variables internally hold the same memory address (and changing its members will change the underlying object). But when you then reassign one of those variables, that one now points to a different object again.


Looking for an example of proving space upper bounds for computing functions on a DTM Like think of the function $f\colon \{ 0,1\}^* \rightarrow \{0,1\}^*$ which maps a binary string string $x$ to say a string of $0$s of length $\vert x \vert ^2$ whre $\vert x \vert$ is the length of the input string.

This to my mind looks like a work that can be done using only a linear amount of space on the work tape. All you really need to do is just have a counter to count the length of the input string in one pass and then you know what $\vert x \vert$ is and then squaring it is a constant time process and then just output those many $0$s.

Is my intutiion correct? How is one supposed to formally prove such a space-bound on the working of a (deterministic Turing Machine) DTM? Can someone kindly show how to write this up formally?

Perhaps the simplest way to show that a certain task can be done with small space is writing C-like pseudocode for it. If you are only using a constant number of variables, and each variable is exponentially bounded in terms of the input length (i.e. $|x| = O(k^n)$ for fixed $k$), then the resulting computation uses at most linear space. You can use the fact that addition, multiplication and division can be done in linear space ($O(n)$), as well as operations like determining the input length.

As an example, here is pseudocode for your algorithm:

f(x) {
  l = |x|;
  y = l * l;
  for i from 1 to y do:
    output 0;
}

The variables here are $l,y,i$ ($x$ is on the input tape so doesn't count). All operations are in linear space (as long as the inputs are small enough), $l \leq n$ and $y,i \leq n^2$, so the algorithm uses linear space.

If the bounds on the variables are polynomial ($O(n^k)$) rather than exponential ($O(k^n)$), then the resulting program is logspace (uses $O(\log n)$ space); all operations mentioned can be implemented in logspace. Indeed, since the bounds in your case are polynomial, your algorithm is logspace; the fact that the output is larger doesn't matter, since we only count space on the work tape.


CPU Cache is managed by which software component? CPU caches are used by exploiting temporal and spatial locality. My question is who is responsible for managing these caches? Is this Operating system that identifies a particular access pattern and then manages (i.e store the data in) cache, using low level OS function calls?

The CPU caches are operational from the very moment on when the CPU is powered up. Neither the BIOS nor an OS are strictly speaking “necessary” to control the caches. The BIOS and the OS can change cache configuration settings in the CPU but they don’t control the normal operation, this is all built into the CPU itself.


Why is recursive programming problematic for branch predictors Consider for example the following recursive program:

function fibonacci(int n) {
    if (n < 2) {
        return 1;
    } else {
        return fibonacci(n - 2) + fibonacci(n - 1);
    }
}

The question is now, why recursive programs are problematic for branch predictors? I think that this is due to the fact that the branch-instruction inside these programs follows a very hard to predict pattern. When considering for example fibonacci(4), it holds that

fibonacci(4) = fibonacci(2) + fibonacci(3)

fibonacci(4) = fibonacci(0) + fibonacci(1) + fibonacci(1) + fibonacci(2)

fibonacci(4) = fibonacci(0) + fibonacci(1) + fibonacci(1) + fibonacci(0) + fibonacci(1).

Thus the following function calls will be performed in this order:
fibonacci(2), fibonacci(3), fibonacci(0), fibonacci(1), fibonacci(1), fibonacci(2), fibonacci(1), fibonacci(0). This results in following sequence of Taken / Not Taken for the if-statement:
NT NT T T T NT T T, which is quite irregular.

My question is now, if my answer and reasoning is correct?

It would seem that recursion isn't the problem at all, but a pattern of branches that is hard to predict. For example, if you calculate n! using recursions (if n = 0 -> return 1 else return n * factorial (n-1)) that should play very nicely with branch prediction. For example 25! will start with 25 taken branches, followed by one branch not taken.

If you calculated fib (n) by simulating the recursion using a stack, you would have mostly a loop, with the exact same branches inside the loop, and as far as branch prediction is concerned, it would be just as good / bad with no recursion anywhere in sight.

PS. This was about predicting whether a branch is taken or not taken. Newer processors use other branch-related predictions: Predicting the target of a branch (for example for virtual functions, where a branch will lead to one of possibly many implementations of a virtual functions), and prediction of the target of a "return" instruction, where the processor predicts that a "return" instruction most likely branches to the instruction after the previous "call subroutine" instruction.


Edit distance of list with unique elements Levenshtein-Distance edit distance between lists
is a well studied problem.
But I can't find much on possible improvements if
it is known that no element does occurs more than once in each list.

Let's also assume that the elements are comparable/sortable
(but the lists to compare are not sorted to begin with).

In particular I am interested
if the uniqueness of elements makes it possible to improve upon
Ukkonen's algorithm for edit distance
which has time complexity $O(\min(m,n)s)$ and
space complexity $O(\min(s,m,n)s)$,
where $s$ is the minimum cost of the editing steps.

More formally,

  how efficiently can we compute the edit distance between two given strings
  $s,t \in \Sigma^*$
  with the promise that they don't have any repeated letters?

$\Sigma$ is a very large alphabet.

TL;DR: A slightly more restrictive kind of edit distance, in which we can only insert and delete individual characters, can be computed in linearithmic time when both (or even just one) of the strings have unique characters.  This gives useful upper and lower bounds on the Levenshtein edit distance.

Insert/delete edit distance, and longest common subsequences

Levenshtein edit distance allows single-character insertions, deletions and substitutions, assigning each a cost of 1.  If we restrict to just insertions and deletions, we get a similar distance measure that now causes substitutions to have a cost of 2 (since any substitution can be mimicked using an insertion and a deletion).  I don't know a standard name for this more restrictive kind of edit distance, so I'll call it "insert/delete edit distance".  It corresponds closely to the longest common subsequence (LCS) problem, in which we are given two strings, of length $m$ and $n$, respectively, and want to know the length of the longest subsequence that appears in both.  If two strings have LCS $L$, then they have insert/delete edit distance $n+m-2L$: the easiest way to see this is to align the strings so that characters in the LCS appear stacked on top of each other, while characters not in the LCS appear opposite a - gap character.  It will then be apparent that we can edit the first string into the second by making an insertion wherever there is a - in the top row, and a deletion wherever there is a - in the bottom row.  For example:

-C-IRC-LE
T-RI-CKLE

Here the LCS of CIRCLE and TRICKLE, ICLE, has length 4, and the edit distance is indeed $6+7-2*4=5$.

Longest increasing subsequences

The reason for this detour is that there is a very efficient way to calculate the LCS (and thus the insert/delete edit distance) when at least one of the sequences contains only distinct characters: In this case, the LCS problem can be transformed into the problem of finding a longest increasing subsequence, which can be solved in time $O(n \log n)$.  Suppose we are given two strings $A$ and $B$, and string $A$ has distinct characters.  We can rename the first character in $A$ to 1, the second to 2 and so on, keeping track of what number we assigned to each character in a table.  Then in $B$, we rename its characters using this table (i.e., every occurrence of whatever was the first character in A is changed to 1, etc.).  Finally, we look for a longest increasing subsequence in B.  This corresponds to a LCS between A and B, and from there we can immediately calculate the insert/delete edit distance.  The total time needed is just $O(n + m\log m)$ if $A$ and $B$ have lengths $n$ and $m$, respectively.

Bounds on Levenshtein edit distance

The insert/delete distance clearly provides an upper bound on the Levenshtein distance (since any valid sequence of edit operations under the insert/delete distance is also a valid sequence of Levenshtein edit operations).  Dividing the insert/delete edit distance by 2 also gives a lower bound, since in the worst case any Levenshtein edit operation can be changed into 2 insert/delete edit operations.

Generalisations

Already in 1977, Hunt and Szymanski came up with an algorithm that can be viewed as a generalisation of the longest increasing subsequence algorithm.  It is efficient whenever the number of pairs of matching character positions between the two strings is small.  If there are $r$ such pairs, their algorithm takes $O((r + n)\log n)$ time.  (Notice that $r \le n$ if all characters in one string are distinct.)  This algorithm was the basis of the original diff program, which treated entire lines of text as individual characters.  diff later switched to using Myers's $O(nd)$-time algorithm, where $d$ is the insert/delete edit distance, as this performs better when overall differences are small but some "characters" (text lines) appear frequently (such as a line containing just an opening brace in C program code).

  Hunt, J.; Szymanski, T. (1977), "A fast algorithm for computing longest common subsequences", Communications of the ACM, 20 (5): 350–353, doi:10.1145/359581.359603


Gramatical evolution doesn't result on creating good constants I'm using Grammatical Evolution for symbolic regression tasks (i.e. searching the space of mathematical expressions to find the model that best fits a given dataset).

I'm evolving solutions according to a user-specified grammar:

 (0)
 <expr> ::= <expr> <op> <expr>      (0)
          | <const>                 (1)
          | <var>                   (2)
          | <unop>                  (3)

 (1)
 <op> ::= *     (0)
        | +     (1)
        | -     (2)
        | /     (3)

 (2)
 <const> ::= 0.1            (0)
           | 1.0            (1)
           | 10.0           (2)

 (3)
 <var> ::= x                (0)

 (4)
 <unop> ::= sin             (0)
          | cos             (1)
          | -               (2)

The population is a collection of arrays of integers. For example:

[0, 1, 2, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1]

is the genotype of the individual +(x, +(1, +(1, 1)) (function $x + 3$).

The translation is performed using the integers to look up the table which describe the BNF grammar:

Step  Sequence  Rule   State
  1      0       0.0   <expr> <op> <expr>
  2      1       1.1   <expr> + <expr>
  3      2       0.2   <var> + <expr>
  4      0       3.0   x + <expr>
  5      0       0.0   x + <expr> <op> <expr>
  6      1       1.1   x + <expr> + <expr>
  7      1       0.1   x + <const> + <expr>
  8      1       0.1   x + 1.0 + <expr>
  9      0       0.1   x + 1.0 + <expr> <op> <expr>
 10      1       1.1   x + 1.0 + <expr> + <expr>
 11      1       0.1   x + 1.0 + <const> + <expr>
 12      1       2.1   x + 1.0 + 1.0 + <expr>
 13      1       0.1   x + 1.0 + 1.0 + <const>
 14      1       2.1   x + 1.0 + 1.0 + 1.0

The fitness function is the reciprocal of the sum, taken over the fitness
cases, of the absolute error between the evolved and the target function.

My problem is that, while the algorithm finds the general model, it often has trouble finding the right constants.

For example, if the target function is $x^2 + x - 12$, it finds something like:

$$x^2 + x - (10 + \sin(x))$$

or

$$x^2 + x - (1 + 1) \times (10 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1) \times ((10 - (10 / (1 + 1)) - (10 / (1 + 1 + 1 + 1 + 1)))$$

which is correct but requires a great effort to discover the constant.

Are there efficient techniques for generating numerical constants?

It sounds like you're saying that your approach is able to effectively find the shape of the expression, but it takes it a lot longer to find the right constants.

One possible approach is to generate an expression of the correct shape using your genetic programming method, then fill in the constants using a different method.  I would recommend trying numerical optimization techniques.  Replace each constant in your expression with a symbolic value $\alpha$.  Each different constant (at each different syntactic position) gets its own symbolic value.  Then, use numerical optimization to find the value of the constants.

Example 1. For instance, consider your complex expression $x^2 + x - (\text{stuff})$.  Replace this with $x^2 + x - \alpha$ (when you have an entire subtree that contains only constants, no variables, replace the entire subtree with a single symbolic value).  We now get a function $f(x,\alpha) = x^2 + x - \alpha$.  Use the training set $(x_1,y_n),\dots,(x_n,y_n)$ to define an objective function:

$$\Phi(\alpha) = \sum_{i=1}^n (f(x_i,\alpha) - y_i)^2.$$

Finally, use numerical optimization methods to search for $\alpha$ that minimizes $\Phi(\alpha)$.  You could try gradient descent, Newton's method, or other techniques.  The value for that subtree deriving using genetic programming supplies a reasonable starting point for the search.

Example 2. In some cases, you will have more than one constant.  For instance, you might get the expression $x^2 + 2x - 3$.  Replace each constant with a symbolic value, so we get $f(x,\alpha,\beta) = x^2 + \alpha x - \beta$.  Now you can derive an objective function as above:

$$\Phi(\alpha,\beta) = \sum_{i=1}^n (f(x_i,\alpha,\beta)-y_i)^2,$$

and use optimization methods to search for $\alpha,\beta$ that minimize $\Phi(\alpha,\beta)$.


A variant of coin change problem Consider a cashier machine that takes payments in coins. We feed the machine coins one by one until the value is more than the amount we should have paid. Then the machine returns the extra amount in coins in the least number of coins possible. So we have k type of coins and a limited amount of each type. Also the machine has an unlimited amount of each of the k types of coins so it can return us the exact amount it should (there is always coin with value 1). So we want to minimize the number of coins we have after we have paid for the items we have bought. Consider this example: We have 3 kinds of coins of values 1, 2 and 4 and we have to pay 15 dollars. We have 10 coins with value 1, 7 coins with value 4 and 5 coins with value 2. There are multiple ways to minimize our coins after the process. One of them is to give the machine 10 coins with value 1 and 3 coins with value 2. Thus we have paid 16 dollars with 13 coins and the machine should return to us 1 dollar and it returns us 1 coin with value 1. So we have spent 12 coins. The other way is to give the machine 9 coins with value 1 and 3 coins with value 2 and the machine doesn't return us anything. So we have paid 12 coins.

My approach to the problem is to divide the problem to two separate coin change problem. The easier problem is when the machine returns us the extra amount of money we have paid. I think this is a simple coin change problem that we want to change some amount of money to the minimum number of coins. The main problem is to pay the machine some maximal amount of coin with the restrictions mentioned above. The restrictions were that we have limited number of each coin and if want to pay A dollars the machine stops receiving coins when the amount of money we have paid becomes equal or greater than A. So For example if we have to pay to 15 dollars and we want to use a total amount of 18 dollars to pay we should use at least a coin with value 4 (18-15+1) or else at some point in the process of paying the amount we have given to the machine surpasses 15 and it won't receive any more coins.

So what I have done so far is this

A //amount we should pay
D //value of the coin with max value among all present coin types
for value_to_change in A to A+D-1
   clear the memoized table for maximal_change
   r = maximal_change(value_to_change,0,0)
   d = minimal_change(value_to_change-A)
   ans = max( ans, r-d )

max_coin // the maximum value of the coin we have used so far
maximal_change( value_to_change, index_of_coin_type, max_coin )
   if we have computed (value_to_change, index_of_coin_type)
       return the computed value
   if (it is the last coin type) AND (max_coin > A-value_to_change)
       if value_to_change % value[index_of_coin_type]==0
            return value_to_change / value[index_of_coin_type]
       else
            return we cant change this value with this coin // -1
   for i in [0, number_of_available_coins_with_this_type]
       n = maximal_change( value_to_change - i*value_of_this_coin_type,
                           index_of_coin_type+1,
                           max(max_coin, value_of_this_coin_type) )
       if n != -1 // we can change the value
           result = max(n+i, result)
   dp[value_to_change][index_of_coin_type] = result;
   return result

now my problem is my solution is slower than what is expected and I think it is because that I clear the memoized table for every value to change. This is only because in each value to change we are required to use a coin with value at least (value_to_change-A+1). Anybody has a better solution?

link of the full description of the problem
link of my implementation

I agree with your solution of the isolated case. Your problem is to reuse your memoisation table. Suppose there are n cases.

What I imagine you could do is:

Allocate a matrix to hold all cases. It has dimensions: T, 1 <= coin value = 50. Call the maximum coin value C. The maximum number of coins is 1000. You could store each count in an unsigned 16 bit int. This max total memory so far of 100 * 50 * 16 = 80KB. We're given 65536, so this isn't too bad. Call this M1.

You now want to devise a plan to reuse your memoisation table as much as possible. As far as I can see, you can reuse a table if and only if the multi-set of coins of the next case is a superset of the previous.

You need to find a way of partitioning the rows into M1 into sequences where each successive vector represents a superset of the previous. That is, the values of coin counts should be non-decreasing over successive vectors.

What you would like to do is minimise the number of partitions. Given two plans with the same number of partitions, you would choose the one which minimises the maximum number of differing coins for a given partition, which would in turn make the solution of the isolated cases cheaper.

I'm not completely sure about the complexity of this, although I imagine that it is NP-Hard, given the number of possible partitions and its similarity to the partition problem. It seems like there might be a cheap randomised greedy algorithm to find a set of initial sequences and work from there.

To run the plan, iterate over the sequences, initialising the memoisation table each time. Run the first case as normal. Run the second case by computing change combinations only for the set of new larger combinations of each coin.


if an argument of a lambda only passes itself if it is further evaluated, is runtime always finite? In order for a lambda expression to run forever, there must be at least one lambda in the expression
in which an argument is passed to itself. For example the following runs forever.

$$
(\lambda x.xx)(\lambda x.xx)
$$

However, I am curious if an expression could run forever if arguments were only passed to themselves
like in $\lambda x.x(xy)$ in that each time it is passed, it becomes further evaluated. I suspect that
this is true (that it can be evaluated in finite time) however am unsure how to prove this formally.
Informally the idea is that each recursive call is guaranteed to leave the lambda in a further reduced state
since the original cannot be preserved.

So my question is:

 What is a formal proof or counterexample to this claim?

A few notes:

The opposite is definitely not true, expressions of the form $\lambda xy.(xy)x$ can run forever. For example,
the following runs indefinitely.

$$
(\lambda xy.(xy)x)(\lambda xG.(Gx)G)(Lx.x)
$$

Also, if when passed to itself both parts are passed an additional argument, such as $\lambda xy.(yx)(yx)$ it
can run forever. For example

$$
(\lambda xy.(yx)(yx))(\lambda x.x)(\lambda xy.(yx)(yx))
$$

Additionally, I am assuming all lambdas within the expression meet the criteria, not just some subset of them.
So something like the following would not be a counterexample

$$
(\lambda x.x(xy))(\lambda x.xx)(\lambda x.xx)
$$

Edit:

As chi pointed out below, I had not given a very good definition of the criteria for this question, so I've added one.

A lambda is reduced in X if it can be written in the following form (as <reduced-lambda>)

<id> := [[all valid variable names except X]]
<id-list> := <id> <id-list> | <epsilon>
<filler> := <epsilon> | <nonempty-filler>
<nonempty-filler> := (lambda <id> <id-list> . <nonempty-filler>) <filler> | <id> <filler> | (<nonempty-filler>) <filler>
<reduction> := (X <filler> <reduction>) | (X <nonempty-filler>)
<base-reduction> := (lambda <id> <id-list> . <filler> <base-reduction> <filler>) | (<filler> <base-reduction> <filler>) | <reduction> | X
<reduced-lambda> := (lambda <id-list> X <id-list> . <filler> <base-reduction> <filler>)

An expression E is reduced if for every lambda L in E, for every argument A in L, L is reduced in A.

And the more precise question becomes: does every reduced expression terminate?

Edit 2:

I did change the above formulation slightly, the old version is in the edit history and is incorrect (twice)

(This is not a proper answer, but I wanted to share some thoughts)

To have a definitive answer one would need to precisely define what's allowed and what's not.

I noticed this, however, which perhaps could help. The term $M = \lambda xy. x(xy)$ is typeable in the simply-typed lambda calculus, which is strongly normalizing.

Instead, your other two examples, $\lambda xy. (xy)x$ and $\lambda xy.(yx)(yx)$ are not typeable in STLC.

Perhaps exploiting this, and formalizing everything precisely, one can indeed prove that using $M$ "alone" does not lead to non termination. It's hard to say, since the STLC constrains the calculus significantly.


Does every 3CNF propositional formula has an equisatisfiable 2CNF propositional formula Does every 3CNF propositional formula has an equisatisfiable 2CNF propositional formula?

Yes.  If the 3CNF formula is satisfiable, here is an equisatisfiable 2CNF formula: True.  If the 3CNF formula is not satisfiable, here is an equisatisfiable 2CNF formula: False.  So yes, every 3CNF formula has an equisatisfiable 2CNF formula.

If you want to actually find that formula in a reasonable amount of time, then we don't know of any way to find such a formula in polynomial time (existence of such a method would prove that P = NP).


Iteration can replace Recursion? I've been seeing all over stack Overflow, e.g here, here, here, here, here and some others I don't care to mention, that "any program that uses recursion can be converted to a program using only iteration".

There was even a highly upvoted thread with a highly upvoted answer that said yes it's possible.

Now I'm not saying they're wrong. It's just that that answer counters my meagre knowledge and understanding about computing.

I believe every iterative function can be expressed as recursion, and wikipedia has a statement to that effect. However, I doubt the converse is true. For one, I doubt non-primitive recursive functions can be expressed iteratively.

I also doubt hyper-operations can be expressed iteratively.

In his answer(which I don't understand by the way) to my question @YuvalFIlmus said that it's not possible to convert any sequence of mathematical operations into a sequence of additions.

If YF's answer is indeed correct (I  guess it is, but his reasoning was above my head) then doesn't this mean that not every recursion can be converted into iteration? Because if it was possible to convert every recursion into iteration, I'd be able to express all operations as a sequence of additions.

My question is this:

  Can every recursion be converted to iteration and why?

Please give an answer a bright highschooler or a first year undergrad will understand. Thank you.

P.S I don't know what primitive recursive is (I do know about the Ackermann function, and that it isn't primitive recursive, but is still computable. ALl my knowledge on it comes from the Wikipedia page on the Ackermann function.)

P.P.S: If the answer is yes, could you for example write an iterative version of a non-primitive-recursive function. E.g Ackermann in the answer. It'll help me understand.

It's possible to replace recursion by iteration plus unbounded memory.

If you only have iteration (say, while loops) and a finite amount of memory, then all you have is a finite automaton. With a finite amount of memory, the computation has a finite number of possible steps, so it's possible to simulate them all with a finite automaton.

Having unbounded memory changes the deal. This unbounded memory can take many forms which turn out to have equivalent expressive power. For example, a Turing machine keeps it simple: there's a single tape, and the computer can only move forward or backward on the tape by one step at a time — but that's enough to do anything that you can do with recursive functions.

A Turing machine can be seen as an idealized model of a computer (finite state machine) with some extra storage that grows on demand. Note that it's crucial that not only there isn't a finite bound on the tape, but even given the input, you can't reliably predict how much tape will be needed. If you could predict (i.e. compute) how much tape is needed from the input, then you could decide whether the computation would halt by calculating the maximum tape size and then treating the whole system, including the now finite tape, as a finite state machine.

Another way to simulate a Turing machine with computers is as follows. Simulate the Turing machine with a computer program that stores the beginning of the tape in memory. If the computation reaches the end of the part of the tape that fits in memory, replace the computer by a bigger computer and run the computation again.

Now suppose that you want to simulate a recursive computation with a computer. The techniques for executing recursive functions are well-known: each function call has a piece of memory, called a stack frame. Crucially, recursive functions can propagate information through multiple calls by passing variables around. In terms of implementation on a computer, that means that a function call might access the stack frame of a (grand-)*parent call.

A computer is a processor — a finite state machine (with a huge number of states, but we're doing computation theory here, so all that matters is that it's finite) — coupled with a finite memory. The microprocessor runs one giant while loop: “while the power is on, read an instruction from memory and execute it”. (Real processors are much more complex than that, but it doesn't affect what they can compute, only how fast and conveniently they do it.) A computer can execute recursive functions with just this while loop to provide iteration, plus the mechanism to access memory, including the ability to increase the size of the memory at will.

If you restrict the recursion to primitive recursion, then you can restrict iteration to bounded iteration. That is, instead of using while loops with an unpredictable running time, you can use for loops where the number of iterations is known at the beginning of the loop¹. The number of iterations might not be known at the beginning of the program: it can itself have been computed by previous loops.

I'm not going to even sketch a proof here, but there is an intuitive relationship between going from primitive recursion to full recursion, and going from for loops to while loops: in both cases, it involves not knowing in advance when you'll stop. With full recursion, this is done with the minimization operator, where you keep going until you find a parameter that satisfies the condition. With while loops, this is done by keeping going until the loop condition is satisfied.

¹  for loops in C-like languages can perform unbounded iteration just like while, it's just a matter of convention to restrict them to bounded iteration. When people talk about “for loops” in theory of computation, that means only loops that count from 1 to $n$ (or equivalent).


Implications of Rice's theorem Every time I think I get what Rice's theorem means, I find a counterexample to confuse myself. Maybe someone can tell me where I'm thinking wrong.

Lets take some non-trivial property of the set of computable functions, for example let $L = \{ f : \mathbb{N} \to \mathbb{N} \;|\; \text{f is a computable and total function} \}$. Obviously, $L$ is countably infinite and there's also a countably infinite number of computable functions not in $L$.

Now lets consider a turing complete programming language over of a finite set of instructions $\Sigma$ and the set of syntactically correct programs $P \subseteq \Sigma^*$, with $|P| = |\mathbb{N}|$. If I can choose the semantics of my language as I please, I may also number the programs as I please and so it should be possible to design a programming language where some subset of the programs computes exactly some arbitrary subset of the computable functions, as long as the cardinality matches.
For example, let $P_{pal} = \{ w \in \Sigma^* \;|\; w\text{ is a palindrome} \}$, and each program $p \in P_{pal}$ compute a total function. Since $|P_{pal}| = |L|$, such a language should exist.

However, $isPalindrome(w)$ is obviously turing-computable and since $isPalindrome(w) \iff isTotal(w)$, we would thus have a program which decides the non-trivial property $L$, which is not possible according to Rice's theorem.

Where is the error in my deduction? Does this mean there is no programming language where each palindromic program (or rather of any computable structure) computes exactly the total functions (or rather any set of computable functions)? This really perplexes me.

What you forget is that all the mappings you use have to be
computable. When you state that matching cardinalities ensure the
existence of a mapping, that may be true, but the mapping is unlikely
to be computable, precisely because that would let you get a
contradiction with Rice theorem. In computability (at least for what I
know of it), everything is either finite or countably infinite. So existence of
mappings is usually not an issue. The problem is whether it is a
computable one.

To say it differently, there is certainly a mapping (actually
uncountably many) that associates precisely palindromic words with
total computable functions. But, given such a palindrom $w$, which the
mapping associates with a function $f_w$ there is no way you can
actually use such a mapping to get the result of applying $f_w$ to
some argument. You mapping does not give you any way of identifying
the function or computing with it. Your language has non computable
semantics.


Uncurrying and Polymorphism How do we uncurry functions when they are polymorphic? For example, is it possible to uncurry the following types? If so what is the uncurried type?

$\forall X. X \rightarrow int \rightarrow X$ ?
$int \rightarrow \forall X. X \rightarrow X$ ?
$int \rightarrow \forall X. X \rightarrow int \rightarrow X$ ?

The other answers are good, I just wanted to make it explicit that currying for dependent types is
$$
\textstyle
\prod (x : A) . \prod (y : B(x)) . C(x, y)
\ \cong \
\prod (p : \sum (x : A) . B(x)) . C(\pi_1(p), \pi_2(p))
$$
which is more suggestive in Agda-style notation:
$$
(x : A) \to (y : B(x)) \to C(x,y)
\ \cong\
(p : (x : A) \times B(x)) \to C(\pi_1(p), \pi_2(p))
$$
In your case, replace $\Pi$ and $\Sigma$ with $\forall$ and $\exists$.


What is an reflective tower? I've just read in a discussion about dynamic typing

  Reflective towers is an open problem for statically typed languages.

What are reflective towers?

I think it might be related to reflection, but I'm not sure.

If you create an example, I would prefer Java.

A reflective tower is a model for language extension. It is modeled as an infinite (tower) series of interpreters. Each interpreter is executing a program which is the interpreter one level bellow it with the programmers' program being at level 0.

Each program is a piece of code that performs computation and in that sense a function but it is also a modifiable struct (it is a data-structure).

You can read about it here


How to implement a maximal munch lexical analyzer by simulating NFA or running DFA? I'm planning to implement a lexical analyzer by either simulating NFA or running DFA using the input text. The trouble is, the input may arrive in small chunks and the memory may not be enough to hold one very long token in the memory.

Let's assume I have three tokens, "ab", "abcd" and "abce". The NFA I obtained is this:

And the DFA I obtained is this:

Now if the input is "abcf", the correct action would be to read the token "ab" according to the maximal munch rule and then produce a lexer error token. However, both the DFA and the NFA have state transitions even after "ab" has been read. Thus, the maximal munch rule encourages to keep on reading after "ab" and read the "c" as well.

How do maximal munch lexers solve this issue? Do they store the entire token in memory and do backtracking from "abc" to "ab"?

One possibility would be to run the DFA with a "generation index", potentially multiple generations and multiple branches within generation at a time. So, the DFA would go from:

{0(gen=0,read=0..0)},

read "a",

{1(gen=0,read=0..1)},

read "b",

{2+(gen=0,read=0..2,frozen), 2+(gen=0,read=0..2), 0(gen=1,read=2..2)},

read "c",

{2+(gen=0,read=0..2,frozen), 3(gen=0,read=0..3)},

read "f",

{2+(gen=0,read=0..2,frozen)}.

Then the lexer would report state 2+, and since there is no option to continue, would report an error state. Not sure how well this idea would work...

For "abcd", it would work like this:

{0(gen=0,read=0..0)},

read "a",

{1(gen=0,read=0..1)},

read "b",

{2+(gen=0,read=0..2,frozen), 2+(gen=0,read=0..2), 0(gen=1,read=2..2)},

read "c",

{2+(gen=0,read=0..2,frozen), 3(gen=0,read=0..3)},

read "d",

{2+(gen=0,read=0..2,frozen), 4+(gen=0,read=0..4,frozen), 4+(gen=0,read=0..4), 0(gen=1,read=4..4)}.

Now of these, it's possible to drop the first (there is a longer match) and the third (there are no state transitions out), leaving:

{4+(gen=0,read=0..4,frozen), 0(gen=1,read=4..4)}.

Then the lexer would indicate "match: 4+" and continue reading input from state 0 using generation index 1.

Is this idea of mine, running DFAs nondeterministically, how maximal munch lexical analyzers work?

There are two ways to handle this issue:

The most common implementation (the one used in lex, flex and other similar scanner generators) is to always recall the last accept position and state (or accept code). When no more transitions are possible, the input is backed up to the last accept position and the last accept state is reported as the accepted token.

If you're trying to do streaming input, you will need a fallback buffer to handle this case.
Alternatively, if the scan reaches an accepting state but another transition is available, we can start performing two scans in parallel: one on the assumption that the transition will be taken, and the other on the assumption that it will not. The second thread may need to fork again, although there is a maximum number of forks, as with generalised LR parsing. In this model, we need to keep a buffer of possible "future" tokens which will be processed if the optimistic thread fails.

I don't know of a practical implementation of the second strategy in a general purpose scanner generator, although there are some papers about how you might do it. Apparently it can be done in time and space linear to the size of the input, which is (in theory) better than the quadratic time consumption of backtracking.

However, it is pretty rare that you find a token grammar which needs to allow unrestricted backtracking. The most common cause of unrestricted backtracking is failing to take into account the fact that things like quoted strings might not be correctly terminated in an incorrect program, so you end up with just the rule:

["]([^"]|\\.)*["]   { Accept a string }

instead of the pair of rules

["]([^"]|\\.)*["]   { Accept a string. }
["]([^"]|\\.)*      { Reject an unterminated string. }

(Maximal munch will guarantee that the second rule will only be used if the first rule cannot match.)

So while the second strategy may have some theoretical appeal, it seems to me that it's of little practical use. Flex even has some options which will help you to identify rules which could backup on failure, and this can help you craft your lexical grammar to avoid the problem. It's not always easy to eliminate 100% of backing up (although it often is, and if you manage to do so, flex will reward you by generating a faster lexer), but it's pretty rare to find a lexical grammar which requires more than a few characters of back-up, and the cost of a small fallback buffer is really not worth worrying about, in comparison with the complexity of the alternative (which, of course, also needs extra memory.)

I have seen intermediate strategies for particular grammars. If you know your grammar well enough, you could hand-build the speculative tokenisation in order to avoid backing up. I've seen that, years ago, in SGML lexers which eliminate the rescan of > following a tagname by including a redundant rule which recognised a tag immediately followed by a > and handled both tokens at once. That must have saved a few cycles, but it's hard to believe that it really made a huge difference, and the difference would likely be even less significant today. Still, if you are the type who obsesses about saving every possible cycle, you could do it.


The difference between theoretical complexity and practical efficiency If I have this pseudocode:

for i=0 to n/2 do
   for j=0 to n/2 do
       ... do anything ....

The number of iterations is $n^2/4$.

What is the complexity of this program?
Is it $O(n^2)$?

What is the intuition formal/informal for which is that complexity?

Next, if i have this other pseudocode :

for i=0 to n do
   for j=0 to n do
       ... do anything ....

The complexity is again $O(n^2)$ -- is that correct?

Is there any difference between efficiency in practice and theoretical complexity in this case?  Is one of these faster than the other?

Big O Formally

$O(f(n)) = \{g(n) | \exists c > 0, \exists n_0 > 0, \forall n > n_0 : 0 \leq g(n) \leq c*f(n)\}$

Big O Informally

$O(f(n))$ is the set of functions that grow slower (or equally fast) than $f(n)$. This means that whatever function you pick from $O(f(n))$, let's name her $g(n)$, and you pick a sufficiently large $n$, $f(n)$ will be larger than $g(n)$. Or, in even other words, $f(n)$ will eventually surpass any function in $O(f(n))$ when $n$ grows bigger. $n$ is the input size of your algorithm.

As an example. Let's pick $f(n) = n^2$.

We can say that $f(n) \in O(n^3)$. Note that, over time, we allowed notation abuse so almost everyone writes $f(n) = O(n^3)$ now.

Normally when we evaluate algorithms, we look at their order. This way, we can predict how the running time of the algorithm will increase when the input size ($n$) increases.

In your example, both algorithms are of order $O(n^2)$.
So, their running time will increase the same way (quadratically) as $n$ increases. Your second algorithm will be four times slower than the first one, but that is something we're usually not interested in **theoretically*. Algorithms with the same order can have different factors ($c$ in the formal definition) or different lower order terms in the function that evaluates the number of steps. But usually that's because of implementation details and we're not interested in that.

If you have a algorithm that runs in $O(log(n))$ time we can safely say it will be faster than $O(n)$ [1] because $log(n) = O(n)$. No matter how bad the $O(log(n))$ algorithm is implemented, no matter how much overhead you put in the algorithm, it will always [1] be faster than the $O(n)$ algorithm. Even if the number of steps in the algorithms are $9999*log(n) = O(log(n))$ and $0.0001*n = O(n)$, the $O(log(n))$ algorithm will eventually be faster [1].

But, maybe, in your application, $n$ is always low and will never be sufficiently large enough so that the $O(log(n))$ algorithm will be faster in practice. So using the $O(n)$ algorithm will result in faster running times, despite $n = O(log(n))$

[1] if $n$ is sufficiently large.


Probabilistic halting problem I'm a physics and math student working through Nielsen & Chuang's text on quantum computation and information. I don't have much experience in CS theory, so some of these exercises are confusing to me:

Suppose we number the probabilistic Turing machines and define the probabilistic halting function $h_p(x)$ to be 1 if machine $x$ halts on input of $x$ with probability at least 1/2 and 0 if machine $x$ halts on input of $x$ with probability less than 1/2. Show that there is no probabilistic Turing machine which can output $h_p(x)$ with probability of correctness strictly greater than 1/2 for all $x$.

I'm sure we're supposed to assume that there is a probabilistic Turing machine that does this, and then show that we can solve the deterministic halting problem using this machine, thus obtaining a contradiction. I don't have a clue how to go from this probabilistic Turing machine to a deterministic one, though.

Let $A$ be a randomized procedure which outputs $h_p$ with success probability larger than $1/2$.

Consider the following code, with input $x$:

Let $y$ be the machine corresponding to machine $x$ running on itself as input.
If $A(y) = 1$, go into an infinite loop, otherwise halt.

Denote this program by $B$.
What happens if we run $B$ on itself? Let us consider two cases. In both cases, let $y$ be the machine corresponding to $B$ running on itself.

Case 1: $B$ halts on $B$ with probability at least $1/2$. In this case, $h_p(y) = 1$, and so with probability more than $1/2$, $A(y) = 1$. Therefore $B$ goes into an infinite loop with probability more than $1/2$, contradiction.

Case 2: $B$ halts on $B$ with probability smaller than $1/2$. In this case, $h_p(y) = 0$, and so with probability more than $1/2$, $A(y) = 0$. Therefore $B$ halts with probability more than $1/2$, contradiction.

(This generalizes the usual proof of uncomputability of the halting problem via diagonalization.)


Given the Turing machines M1 and M2, is L (M1) = L (M2)? is decidable? I thought to reduce from the halting problem to conclude undecidability, yet I don't know how to do it. Perhaps the problem reduces to other decidable problem, and thus it is also decidable?

As you suggested, think how to reduce from the halting problem $Halt_{TM} = \{ \langle M, w\rangle: \text{$M$ halts on $w$} \}$. On input $\langle M, w\rangle$, the reduction should output a pair of TMs $\langle K_1, K_2\rangle$; such that $M$ halts on $w$ iff $L(K_1) = L(K_2)$.
This is somehow a basic reduction that can be done by standard tricks, so it would be a nice exercise to solve it alone. Here is a hint.
Hint: you can simplify things by fixing one of the machines $K_1$ or $K_2$ to be a constant machine that recognizes some fixed language. Then, think how to define the other machine depending on the reduction's input $\langle M, w\rangle$.


Improving heading measurements from low cost compass module I have heading measurements of two Sensors (BNO055 and HMC6343) and also accurate measurements from better sensors for comparison from a rotating platform. Most of the measurements are with some kind of potentional error source like passing train, large ferromagnetic materials.

The measurements of the BNO055 can't be used at all since he mostly doesn't even react to changes in angle. The measurements of the HMC have some other problems.

Large Offset at the Start that only converges towards the true value after some movement of the sensor (elevation change) i guess sensors needs to calibrate at the start every time
Sometimes small global offsets towards the true value
Larger periodic deviations and noise (esp. near rails)

If you don't want to read the paragrpahs of my endeavors below. My question is basically is it possible to get major improvements with only positional data from one sensor and the reference data and nothing else?

I'm kind of at a loss how i could improve the measurements. I started to learn about Kalman filter and tried a simple kalman filter with a linear model: x+vt+at^2/2 (x being angle etc.). But neither sensors fusion is an option because of useless BNO measurements and also a filter with just HMC measurements with state vectors (x,v) and (x,v,a) don't really improve my measurements. (x,v,a) vector is actually even worse.

I'm kind of at a loss here. I'm trying to understand unscented/extended kalman filter but atm i don't really see the point since its for nonlienar models and i don't know how i could't describe the angular movement differently than with the simple movement equation above.

I also read something about calibrating with neural networks but are not quite sure if it's worth to invest more time into it since my time is limited.

Edit: I added some pictures of the measurements so people who might want to chip in have a better idea. The blue and red lines are not interesting. Green are the accurate measurements. Orange are the measurements of my sensor. A big problem is also that the sensor doesn't measure the right heading at the start if the antenna hasn't changed elevation yet. He seems to need to calibrate for a bit to reach his estimated value.

While 'major' improvements is subjective, you can certainly improve your system more than it is (at least as you have described). Based on your problem description, it sounds as if your measurements may be non linear (you will have to confirm this). If this is the case, then a linear filter, such as the Kalman Filter, won't work well at all.

From here, you need to determine if these 'large periodic deviations and noise' are normally distributed or not. If they are, then you can try a non-linear filter such as the Unscented Kalman Filter (If the deviations are truly 'large', the unscented filter is preferable to the extended as it is more robust to higher levels of non-linearity). If your noise and 'periodic deviations' are not normally distributed, then you will have to consider non-parametric approaches such as the Particle Filter.

As far as sensor calibration, you could try more advanced techniques, but typically the sensor manufacturer will supply some form of calibration procedure. This procedure is typically recommended unless you are absolutely sure about a different strategy.


Why does Randomized Quicksort have O(n log n) worst-case runtime cost Randomized Quick Sort is an extension of Quick Sort in which the pivot element is chosen randomly. What can be the worst case time complexity of this algorithm. According to me, it should be $O(n^2)$, as the worst case happens when randomly chosen pivot is selected in sorted or reverse sorted order. But in some texts [1] [2] its worst case time complexity is written as $O(n\log{n})$

What's correct?

Both of your sources refer to the "worst-case expected running time" of $O(n \log n).$ I'm guessing this refers to the expected time requirement, which differs from the absolute worst case.

Quicksort usually has an absolute worst-case time requirement of $O(n^2)$. The worst case occurs when, at every step, the partition procedure splits an $n$-length array into arrays of size $1$ and $n-1$. This "unlucky" selection of pivot elements requires $O(n)$ recursive calls, leading to a $O(n^2)$ worst-case.

Choosing the pivot randomly or randomly shuffling the array prior to sorting has the effect of rendering the worst-case very unlikely, particularly for large arrays. See Wikipedia for a proof that the expected time requirement is $O(n\log n)$. According to another source, "the probability that quicksort will use a quadratic number of compares when sorting a large array on your computer is much less than the probability that your computer will be struck by lightning."

Edit:

Per Bangye's comment, you can eliminate the worst-case pivot selection sequence by always selecting the median element as the pivot. Since finding the median takes $O(n)$ time, this gives $\Theta(n \log n)$ worst-case performance. However, since randomized quicksort is very unlikely to stumble upon the worst case, the deterministic median-finding variant of quicksort is rarely used.


Assuming an infinite amount of computing resources, would the minmax algorithm always win in chess? The minmax algorithm is a popular strategy used to design chess engines. Usually, since the state-space of chess is huge, we choose a fixed depth and evaluate the game tree down to that level, and pick the best sequence of moves so far.

Let's suppose we remove this limit, and we search for the whole tree. Would this techinque always win? If the answer is no, would it ever lose? (so, would it only win+draw, or also lose?)

A good answer would include theoretical underpinnings of why or why not this would work, both from the game-theoretic aspects of chess and from the proprieties of the minmax algorithm.

By definition, minmax chooses the move that results in the best possible outcome if the adversary plays optimally, but within the bounds of what the evaluation function takes into account. More precisely, minmax results in the best outcome that can be guaranteed no matter how the adversary plays, as long as the adversary's behavior is no worse than what the evaluation function predicts.

If minmax searches on the whole tree, then it never calls the evaluation function, and therefore it models the adversary perfectly. So in this case, minmax achieves the best guaranteed outcome that can be guaranteed against an arbitrary adversary. This is true regardless of the game.

For chess, there are three possible outcomes: win, draw, loss (from best to worst). We don't know what the best guaranteed outcome for each player is. But whatever it is, if you can run minmax on the whole tree, you'll get that outcome or better (the outcome can be better if the adversary plays suboptimally). Of course, this is only practical near the end of the game when there are few pieces remaining in play.


If $L$ is recursive then so is $L^*$, and vice versa Given a language $L$ over the alphabet $\{0,1\}$. Let $L^*= \{ w_1w_2...w_n | n \ge 0, w_1,...,w_n \in L\}$.

Prove:

If $L$ is recursive, then $L^*$ is recursive as well.
If $L^*$ is recursive, then $L$ is recursive as well.

For the first proof I have this idea:
If $L$ is recursive, then a turing machine $M_L$ can decide all the words $\{w|w \in L\}$. So $M_L$ can decide $\{w_1,...,w_n | w_1w_2...w_n \in L^*\}$ and appearently it can decide $L^*$ as well.

For the second proof I tried the same but actually it does not work that way. Any hints and ideas?

The second claim is wrong. Let
$$ L = \{0,1\} \cup \{010^n : \text{the $n$th Turing machine halts}\}. $$
Then $L^* = \{0,1\}^*$ is recursive, but $L$ isn't recursive.

For the first claim, your proof is not convincing. You need to explain how a Turing machine can decide whether a given word $w \in \{0,1\}^*$ can be written as a sequence of words from $L$. One way is to consider all possible partitions into non-empty subwords, and check whether one of them has the property that all subwords are in $L$.


Huffman Coding - probabilities I am having trouble understanding a question related to Huffman Coding. We haven't studied it a lot, so I am not even sure how to start.

Given $n ≥ 2$ characters, with probabilities $p_{1} \geq p_{2} \geq ... \geq p_{n}$ Let $p_{i} = 2^{k_{i}}$ with $k_{i} \in \mathbb{N}$ and $\sum_{i=1}^{n} p_{i} = 1$

Show that $p_{n-1} = p_{n}$ and that the minimum expected codelength amount to
$$- \sum_{i=1}^{n} p_{i} \log p_{i}$$

Help?

It's better to use the parametrization $p_i = 2^{-k_i}$. Multiply the equation $\sum_{i=1}^n p_i = 1$ by $2^{k_n}$ to get
$$
\sum_{i=1}^n 2^{k_n-k_i} = 2^{k_n}.
$$
The right-hand side is even, so the number of $i$ such that $k_i = k_n$ must be even as well (why?). This implies that $p_{n-1} = p_n$.

For your second question, it is known that the minimum expected codeword length is at least $H(p) = \sum_i p_i \log (1/p_i) = \sum_i p_i k_i$. The converse to Kraft's inequality shows that there is a prefix code with codeword lengths $k_1,\ldots,k_n$, and so with expected codeword length $H(p)$.