Comparing variations of A* I am running some experiments with a maze, and trying different variations of A*. Based on my experiments, I have been able to form some opinion (that at least in those cases, graph checking is better than IDA).

I am looking for online articles that have done similar experiments, comparing variations of A* with respect to expanded nodes, but have not come across anything concrete.

Well, there is a lot of bibliography on whether one algorithm is better than the other. In particular, the main insight is: "in the presence of duplicates (e.g. grids), A$^*$ should be preferred, whereas in other cases IDA$^*$ should be in general preferred". For example, heuristic planners usually prefer best-first search strategies such as A$^*$ instead of IDA$^*$ (just because duplicates occur in many domains). For example, to solve the $N$-Puzzle, the $N$-Pancake, or the TopSpin, IDA$^*$ is the current algorithm of choice. For other cases, such as Rubik's Cube or Towers of Hanoi, IDA$^*$ is still the algorithm of choice but be careful and try to implement a good strategy for handling symmetries. In the case of grids, A$^*$ is the right choice.

There is a wonderful paper about how to implement A$^*$ and makes a lot of considerations that, I think, fit your question: Ethan Andrew Burns, Matthew Hatem, Michael J. Leighton, Wheeler Ruml. Implementing Fast Heuristic Search Code

Let me know, please, whether this helps or not,


Have I invented a new data structure? EDIT: Seems like what this structure is nothing more than a 26-bit bitwise trie, as KWillets suggested in the comments! You can think of the words we insert the trie as 26-bit Bitsets where the i-th bit indicates whether the word contains the i-the letter in the alphabet.

As I was tackling an interview problem I came up with this tree-like data structure. Actually it IS a binary tree that is maximum 26(English alphabet size) nodes deep.
Basically the problem is:

  There are a set of dictionary words and a set of license plate numbers. Write a code/algorithm to find the shortest dictionary word which contains all the letters in the license plate, irrespective of the order of characters

This data structure is specifically designed for the problem of finding words from a given list containing all letters from a set of letters.
 I call this operation getSupersetWords().

It can also be used for finding words containing ONLY a set of letters.(In fact my empirical tests show that this is the use case giving the best performance gain over linear search (over 16 times faster on average for a list of 73k English words)).
I call this operation getSubsetWords().

To give you an example:

Lets say we have list of words = [ “cat” ,”dog” “cow”, “case”].

On query getSupersetWords([‘a’, ‘c’]) we get [“cat”, “case”].

On query getSubsetWords(['c', 'o', 'w', 'a', 't']) we get ["cat", "cow"].

How to add a string to this data structure ?
As I said earlier the data structure is a binary tree.
 At every level of the tree we make a decision. If the word contains the next letter of the alphabet(we start from 'a' at level 1) we go right, else we go left.
 If we have made all the 'right' possible decisions for the given word we place it in the current node.(A node contains a reference list of strings).

How to answer a query from this data structure ?
Now to answer a getSubsetWords() query we traverse the tree recursively in DFS making both decisions if the query contains the character at the current letter, or 'left' if it doesn't and adding the words at the given Node to a list
(this is VERY confusing to type out...but not so much in code :/).

It sounds confusing, that's why I made a simple diagram illustrating the idea.

Assume we have a list of strings = {"a","aaa","baa","ab","bb"}.

Now If we had 'z' in the list the tree would be 26 nodes deep, but because the 'biggest' letter is 'b' We only need 3 levels.

The circle shapes are lists of strings, the rectangles are the nodes.
I was wondering if this structure is something I have 'invented' or it is already well known, (Which probably is the case :).

I've never seen this data structure before.  However, it doesn't seem like a good choice for storing a set of words, for most purposes.  I see three significant disadvantages:

Performance. Looking up a word in this data structure can potentially be quite slow.  In particular, when looking up a word of length $n$, checking whether it contains a particular letter involves looking at all $n$ characters of the word.  Therefore, traversing the entire tree (all 26 levels) might require reading the entire word 26 times.  In contrast, a trie reads each character of the word only once, so might be about 26x times faster.  Same for a hashtable.
Space usage. This might take a lot of space.  I am assuming you won't construct a node unless it is needed (i.e., if it has only one child, you'll omit the node).  With that optimization, the depth of the tree is at most 26 if you're using words with letters a-z.  If you are storing strings in Unicode, the depth of the tree might be enormous, and in the worst case this might devolve to a data structure where the depth of the tree is proportional to the number of words in the set, and then the space usage is bad and the time for a lookup is very bad (linear in the size of the set).  Without that optimization, the number of the nodes in the tree can be as large as $2^{26}$ for letters a-z, or enormous for Unicode strings.
Incomplete. This isn't a complete data structure.  It cannot distinguish between two words with the same set of letters, e.g., between words that are permutations of each other (anagrams).  Therefore, you'll need another data structure for storing the second-level sets (your circle shapes).  If we had a good data structure for that purpose, why wouldn't we use it for all the words, and skip your data structure?  Conversely, if you use a poor data structure for that, then your data structure inherits the limitations of that data structure: for instance, if you store all the words in the circle in a linked list, then lookups will be slow as they might need to traverse the entire list.


Is there a TM that halts iff P = NP? Is there a Turing machine that halts iff P = NP? There are Turing machines that halt iff the Goldbach conjecture is false, or the Riemann hypothesis is false. How about the P vs. NP question? This is an expressiveness question, but I have not seen such a construction before.
Update: There are competitions to construct the smallest TM that halts iff Goldbach is false. The current record is 27 states. Basically the TM puts successively larger even numbers in unary on the tape and checks if there is a cut dividing the unary even number into two primes. This is the spirit that I intended; my question is not about existential, nonconstructive arguments or provability from ZFC.

The answer to your question is formally "yes". This is because one possible Turing machine that halts iff P=NP is either (i) a Turning machine that always halts or (ii) a Turing machine that never halts (regardless of its input).
However, the following argument might be closer in spirit to what you are asking:
Assume that $P=NP$ is not independent from the axioms you are (implicitly) using.
Since proofs are enumerable you could build a Turing machine $T$ that iterates over all "candidate proofs" that P=NP.
When a candidate proof $\pi$ is considered, $T$ checks whether $\pi$ is an anctual proof. If it is, $T$ halts immediately. If it isn't, $T$ continues with the next candidate proof.
It follows that $T$ halts iff $P=NP$.


How to write an algorithm which doubles stack in order to accommodate for new members where push is in constant time in the worst case? We're given the algorithm which uses stack in order to store data (stack is implemented via an array). When the stack is full the algorithm does the following:

Creates a new array double the size of the original one.
Copies all elements of the old array to the new array, preserving the order.

Adjust the algorithm so that the insertion of new element will be in constant time in the worst case.

The limitation here is we must use arrays as stack implementation.
The worst case is when for example the old stack of size $n$ is full and now we need to insert a new element. So we create a new stack $S_2$ of size $2n$ and we want to insert the new element to $S_2[n+1]$.
I'm stuck with the constant time requirement, I'd appreciate any hints to the right direction.
NB: I'm aware that the title is a bit general, I couldn't think of anything more specific, if you know under which category of algorithms it falls under please let me know and I'll edit the heading.

I don't think that it is possible to push an element to a full array-based stack in worst case $\mathcal{O}(1)$ time. However, you can rest assured that each push runs in constant amortized time whenever you multiply the length of the full array by a factor of $q > 1$ (like you do; $q = 2$ in your case). This is why:

Suppose the initial array capacity is $m$. Next we choose $q > 1$ such that $\lfloor qm \rfloor > m$, or namely, $q$ must be sufficiently large in order to trigger an array expansion.

Suppose the total accumulated work of adding $n$ elements to the stack is

$$W = m + mq + mq^2 + \dots + \overbrace{mq^k}^n$$.

We require $k$ to be the smallest integer such that $mq^k \geq n$, which leads us to the following inequalities:

$$
\begin{aligned}
mq^k &\geq n \\
q^k &\geq \frac{n}{m} \\
\log_q q^k &\geq \log_q \Bigg( \frac{n}{m} \Bigg) \\
k &\geq \log_q n - \log_q m.
\end{aligned}
$$

Since $k$ is required to be the smallest integer satisfying the above inequality, we can set $k = \lceil \log_q n - \log_q m \rceil$. Also,

$$
\begin{align}
qW = mq + mq^2 + \dots + mq^{k + 1} &\Rightarrow W - qW = m(1 - q^{k+1}) \\
    &\Rightarrow W = m\frac{1 - q^{k+1}}{1-q}.
\end{align}
$$

Since $k = \lceil \log_q n - \log_q m \rceil$, we obtain
$$
\begin{align}
W &= m\frac{1 - q^{\lceil \log_q n - \log_q m \rceil + 1}}{1 - q} \\
  &\leq m\frac{1 - q \cdot q^{\lceil \log_q n \rceil}}{} \\
  &\leq m \frac{1 - q \cdot q^{\log_q n + 1}}{1- q} \\
  &= m \frac{1 - q^2n}{1 - q}.
\end{align}
$$

Now we have that

$$
\begin{align}
\frac{1}{n} W &\leq \frac{1}{n} \Bigg[ m \frac{1-q^2n}{1-q} \Bigg] \\
              &= \frac{1}{n} \Bigg[ \frac{m}{1-q} - \frac{nmq^2}{1-q} \Bigg] \\
              &= \frac{m}{(1-q)n} - \frac{mq^2}{1-q} \\
              &\leq \frac{m}{1-q} - \frac{mq^2}{1-q} \\
              &= \frac{m(1-q^2)}{1-q},
\end{align}
$$
which is constant since $m$ and $q$ are fixed parameters independent of $n$.


Is it better to store the magnitude of an arbitrary-precision number in BigEndian or LittleEndian order in an integer array? I'm implementing a class which provides arbitrary-precision arithmetic (also called "bignum", "BigInteger", etc.).

My questions is about a practical implementation detail:

I'm wondering if there is a significant difference in implementation and computational complexity between an implementation which stores the magnitude in an integer array in BigEndian order vs. LittleEndian order.

My data structure is basically:

class BigInt
  val signum: Int
  val magnitude: Array[Int] // two-complement (unsigned)

Supported operations are for instance:

+, -, * (Long multiplication, Karatsuba, Cook3, Schönhage-Strassen), /, squaring
Conversion to other number types
Comparison, equality, representation as a String

The implementation is immutable, so every operation will return a new value and will not change the any existing.

Feel free to ask for clarifications!

You are replacing magnitude[i] by magnitude[SZ-i]. That won't have any effect on complexity nor ease of implementation. Depending on the way simplifications occur, one or the other could have slightly less index adjustments, but I won't dare a guess which. Little endian seems slightly more in line with the usual presentations of the algorithms (for instance in TAOCP), big endian had a more intuitive representation of the number in memory, but that's an opinion more than a fact.

If you look at memory access patterns, there was a time when cache prefiller handled better increasing consecutive accesses (which would have favored little endian), but nowadays, I don't think it still make a difference at least on workstation and server processors.

So I don't think there is a compelling argument to choose BE over LE or ortherwise. Take the one which make you more at ease.


Is huffman coding tree a heap or a trie? I study Huffman Coding tree from "Data Structures and Algorithm Analysis" of Shaffer and it says that Huffman Coding tree is an opportunity to experience a search trie. However, the code implements it with a heap class.

As a result, I wonder if Huffman Coding tree is actually a heap or a trie? If it is a heap, is it a mimHeap or a maxHeap. I'm somehow confused because there are some online resources calling it a minHeap, as it should be a maxHeap.

Anyway, thank you very much in advance.

A Huffman tree is a trie: its edges are labeled by $0,1$, and its paths spell out binary words.

Huffman's algorithm uses a min-heap to construct the Huffman tree. At each step, we choose the two items with minimal probability, and merge them.


Is Big-Oh notation preserved under monotonic functions? I was just looking at the big-Oh notation. I wanted to know if the following is true in general
$$f(n)=O(g(n)) \implies \log (f(n)) = O(\log (g(n)))$$

I can prove that this is true if $g$ is monotonically increasing, but am not sure if this holds in general.

By definition,
$$ f(n) \in O(g(n))$$
means there exists some positive constant $c$, such that for any large enough $n$,
$$ |f(n)| \le c |g(n)|$$
or equivalently, $\lim_{n\to\infty} \frac{f(n)}{g(n)}  \le c < \infty$

Taking $\log$ of both sides, for any large enough $n$ it holds that
$$ \log (f(n)) \le log (c) + \log(g(n)) $$

so,
$$\frac{\log f(n)}{\log g(n)} \le \frac{\log c}{\log g(n)}+ c$$

Now can this go to infinity? only if  $\log(g(n)) \to 0$

So let's try, and take $f(n)=2^{-n}$ and $g(n)=1/n$. Obviously $f(n) \in O(g(n))$.
Yet, taking the logs we have $\log f(n) = -n$, $\log g(n) =-\log n$, and it is clear that no constant $c'$ will satisfy $|\log f(n)| \le c' |\log g(n)|$ for large enough $n$. Yet, I always find it weird to discuss $O$ of negative functions.

EDIT:

Here's example w/o negative function. Get back to the requirement of $\log(g(n)) \to 0$. Take $g(n) = 1+1/n$. Thus $\log (g(n)) \to 0$.
(actually, the above example of $2^{-n}$ vs $1/n$ satisfies $g(n)\to 0$ rather than $log(g(n))\to 0$. Oops).

If we take $f(n) = 2 + 1/n$ then $\log f(n) \to 1$ (binary log, obviously).

so while $f(n) \le 3g(n)$ for every $n\ge 1$, it is not true that
$\log f(n) \le c' \log g(n)$ for all large enough $n$, as the right-hand side approaches zero, while the left-hand side approaches 1.


What should I call algorithms with non-linear non-constant time? I am writing a paper in which I want to refer to a group of algorithms. Some of these algorithms are of complexity O(NlogN), and some of the are more complex (e.g polynomial-time) and I want to refer to them all in one term. Is there any common term to use in such a situation?

linearithmic refers to O(NLOGN) algorithms and it's narrower than what I'm looking for. I don't think of non-linear as a good term to use here. If it is, then correct me please.

my sentence:

  In such a setting, state-of-the-art community-detection algorithms does not scale well. To reduce the running time of these XYZ algorithms, each sub-graph is partitioned into chunks.

I want to change `XYZ' in the above, to what I am asking for.

As mentioned by Bryce Kille in the comments, superlinear is what you are looking for. From Wiktionary:

  (mathematics) Describing a function that eventually grows faster than any linear one

(By the way, the first phrase in your question strikes me as rather odd: "[...] I want to refer to a group of algorithms that are mostly polynomial-time, but one of them is of complexity $O(N \log N)$." Do you simply mean "linear" instead of "polynomial-time"?)


In a distributed system is it possible for both parties to simultaneously agree a message exchange was made? Given that the two generals problema is unsolvable, which means that both parties involved cannot agree that both know something, i ask something simpler.  Is it possible for both parties to agree that a message Exchange occurred? In other words, is it possible for both parties to agree that a "conversation" occurred?

For instance, if A and B communicate with messages Mx

A -M1 -> B
A <-M2 - B
A -M3 -> B

At this point B knows that a message Exchange occurred, but can he be sure that A also knows so?

Thanks in advance

I think it is the "two general" problem.

The "two general" problem is informally stated as follows [1]:

  The commanding general of the first division wishes to coordinate a simultaneous attack. The generals can communicate only by means of messengers. Normally, it takes a messenger one hour to get from one encampment to the other. However, it is possible that he will get lost in the dark or, worse yet, be captured by the enemy.

What is the difference between this and your "message-exchanging" problem?

[1] Reasoning about Knowledge. By Ronald Fagin, Joseph Y. Halpern, Yoram Moses and Moshe Vardi.


Semi-decidable problems with linear bound Take a semi-decidable problem and an algorithm that finds the positive answer in finite time. The run-time of the algorithm, restricted to inputs with a positive answer, cannot be bounded by a computable function. (Otherwise we’d know how long to wait for a positive answer. If the algorithm runs longer than that we know that the answer is no and the problem would be solvable.)

My question is now: Can such an algorithm still have a, say, a run-time bound linear (polynomial, constant,...) in the input size, but with an uncomputable constant? Or would that still allow me to decide the problem? Are there example?

For your sketched decision algorithm to work, it is sufficient that the run-time is majorized by a computable function. Every linear function $n \mapsto c\cdot n$ even for non-computable c is majorized by a computable function, viz., $n \mapsto \lceil c \rceil \cdot n$. Thus the answer to the question is no: a semi-decision procedure for an undecidable problem cannot have linear run-time (or a run-time majorized by any computable function.)


Efficiently compute the sum of edge weights product of all possible path in a DAG I thought of using Depth First Search (DFS) to find all possible paths in O(|V|+|E|). However, computing the product of all the edge weights for a path is O(2^N). Is there any way to compute this more efficiently?

You can actually solve this in $O(|V|+|E|)$ time. Since it is a DAG, we can apply dynamic programming.

Let $p = u_1u_2\dots u_k$ be a path and $cost(p) = w(u_1,u_2)\times w(u_2,u_3)\times\dots \times w(u_{k-1}, u_k)$ be the edge weight product of the path. One important observation is that $cost(u_0p_1) = w(u_0,u_1)\times cost(p_1)$.

Now, for each node $u$, let $dp(u)$ be the sum of edge weight products of all paths originating from $u$.

Let the children of $u$ be $v_1,v_2,\dots,v_m$. We can compute $dp(u)$ using the relation

$$dp(u)=\sum_{i=0}^m w(u,v_i) \times dp(v_i)$$

A Topological sorting can find the order of nodes to compute. Then, the final answer is the sum of all $dp$

$$\sum_{u\in V} dp(u)$$


Is this path finding problem in a 01-matrix NP-complete? The problem:
Input: An $n \times n$ matrix of 0's and 1's, and a position pos of this matrix (i.e. a pair of integers $i,j$ with $1 \leq i,j \leq n$)
Output:
YES if there exists a path through adjacent matrix entries $\dagger$, starting at pos, covering each matrix entry with a 1 exactly once, and not covering the matrix entries with a 0.
NO otherwise.

$\dagger$ a matrix entry is adjacent to the one immediately to its left, to the one immediately to its right, to the one immediately upwards and the one immediately below.

Informally, the matrix can be seen as a labyrinth where the 0's are walls, you start somewhere, and you have to walk through the whole maze without repeating any position.
Example input:
1100
1100
0000
0001
Pos: (1,1)

Corresponding output:
No (because you can't reach the position (4,4))

Is this problem NP-complete? If it is, what other NP-complete problem has been reduced to it? If it isn't, what approach can I use to design an efficient algorithm?
I think this is a particular case of the hamiltonian path problem (except that you have a fixed starting point). The graph can be constructed by taking the matrix entries with 1's as vertices. 2 vertices are adjacent iff their corresponding matrix entries are adjacent. So I think that reducing this problem to the hamiltonian path problem should be easy. Of course, to prove it is NP-complete, we would have to do the reduction backwards.

Your problem is to determine if there is a Hamiltonian path in a grid graph (an induced subgraph of a rectangular grid). This is NP-complete: see Itai, Papadimitriou and Szwarcfiter, Hamilton Paths in Grid Graphs (SIAM J. Comput., 11(4):676–686, 1982) PDF.


Prove that "Finishing the degree in three years" problem is NP-Complete I was asked in an interview the following question:

We'll define the "Finishing the degree in three years" problem in the following manner:

Given a list of courses $C=\{c_1, c_2,\ldots, c_n\}$, where every course $c_i\in C$ is given a list $R_i\subseteq C$ of the precondition courses for this course, and also we are given the maximal amount of courses in each year $m_1, m_2, m_3$, and we need to decide if it is possible to finish the degree in three years. Meaning, can we divide the courses for three years $Y_1, Y_2, Y_3 \subseteq C$, such that the following conditions are satisfied:

All courses are studied within 3 years: $Y_1\cup Y_2\cup Y_3=C$.
Each courses is studied only after all of its precondition courses have been studied, meaning: for any $c_i\in Y_1: R_i\subseteq\emptyset$, for any $c_i\in Y_2: R_i\subseteq Y_1$, for any $c_i\in Y_3: R_i\subseteq Y_1\cup Y_2$.
The number of courses studied in each year is not higher than maximum allowed, meaning: $|Y_i|\le m_i$ for each $i\in\{1,2,3\}$.

Prove that the "Finishing the degree in three years" problem is NP-Complete.

I was told that the reduction should be from the clique problem but it has been a week since I've started thinking about it and I couldn't prove it. If someone can please post a thorough solution I would appreciate it a lot.

Consider an instance $(G,k)$ of the clique problem: deciding whether there is a clique of size $k$ in the graph $G$. Construct a course for each vertex (say "vertex course") and for each edge (say "edge course") in $G$. Each edge course has two precondition vertex courses corresponding to its two endpoints. In addition, we set $m_1=k,m_2=+\infty, m_3=m-\binom{k}{2}$ where $m$ is the number of edges in $G$. Now we can see there is a clique of size $k$ in $G$ if and only if it is possible to finish the degree in three years.


Find median of unsorted array in $O(n)$ time To find the median of an unsorted array, we can make a min-heap in $O(n\log n)$ time for $n$ elements, and then we can extract one by one $n/2$ elements to get the median. But this approach would take $O(n \log n)$ time.

Can we do the same by some method in $O(n)$ time? If we can, then how?

This is a special case of a selection algorithm that can find the $k$th smallest element of an array with $k$ is the half of the size of the array. There is an implementation that is linear in the worst case.

Generic selection algorithm

First let's see an algorithm find-kth that finds the $k$th smallest element of an array:

find-kth(A, k)
  pivot = random element of A
  (L, R) = split(A, pivot)
  if k = |L|+1, return pivot
  if k ≤ |L|  , return find-kth(L, k)
  if k > |L|+1, return find-kth(R, k-(|L|+1))

The function split(A, pivot) returns L,R such that all elements in R are greater than pivot and L all the others (minus one occurrence of pivot). Then all is done recursively.

This is $O(n)$ in average but $O(n^2)$ in the worst case.

Linear worst case: the median-of-medians algorithm

A better pivot is the median of all the medians of sub arrays of A of size 5, by using calling the procedure on the array of these medians.

find-kth(A, k)
  B = [median(A[1], .., A[5]), median(A[6], .., A[10]), ..]
  pivot = find-kth(B, |B|/2)
  ...

This guarantees $O(n)$ in all cases. It is not that obvious. These powerpoint slides are helpful both at explaining the algorithm and the complexity.

Note that most of the time using a random pivot is faster.


Confused between the terms Process and Process Control Block I was reading about the Long term scheduler, when I read that when memory is not enough and load on the CPU due to multiprogramming is too high, a process might be moved to secondary storage space (namely swap space). I am slightly confused as too what exactly happens when a process is moved out of memory. Is its "PCB(Process Control Block)" moved out and store in Hard disk or something else like "process state".
I believe that this confusion is due to lack of clarity between "process in memory" and "process control block". Are the two things different or the same?

The above two diagrams have been picked from the 3rd chapter of Operating Systems Concepts 9th edition.

The point of swapping is to make room in RAM. What is moved to disk is what the book calls “process in memory”, not the process control block. The PCB block is a small amount of memory, so moving it to disk wouldn't help much. Additionally, some of the PCB is necessary even if the process is never scheduled, for example to know whether a file is open or not (which matters if the file is deleted or when taking a lock on the file), to know what events (such as I/O becoming available) might cause the process to become runnable (this information would be in the “process state”), and the knowledge of where the process data is in the swap space (that would be the process's “memory limits” while it's swapped out). In contrast, none of the process's own memory is necessary while the process is not scheduled.
Note that most operating systems don't swap out a whole process, but parts of its memory. Some books make a distinction between “swapping” a whole process and “paging” parts of memory, but in modern usage, the words “swapping” and “paging” are usually synonymous and refer to any mechanism that temporarily moves process memory to swap, whether it moves a whole process at a time (uncommon) or parts of process memory (common).


prove that a language is context free given a regular language R is a regular language over $\Sigma=\{0,1\}$
$Sub(R)=\{0^i1^j \mid \exists w\in R.|w|=i-j \}$
I need to prove that Sub(R) is context free.

I know that the quotient of a context free language with a regular language is context free
but I can't seem to continue for there..

Let $\phi(R) \subseteq 0^*$ result from $R$ by substituting $0$ for $1$. Alternatively, $\phi(R) = \{ 0^{|w|} : w \in R \}$. The previous description makes it clear that $\phi(R)$ is also regular. Now
$$
\operatorname{Sub}(R) = \phi(R) \{ 0^j 1^j \},
$$
the concatenation of the regular language $\phi(R)$ and the context-free language $\{0^j 1^j\}$.


Are event and mode well defined terms in CS literature? From my experience in programming small imperative scrips for personal usage with JavaScript,
I can conclude that an event is "A perceived change in the output of a system" (such as clicking a link from client side or refreshing a page from server side),
while a mode is a situation or "state of affairs" of a program (such as a "saved game" state we can later "load") and if a certain state has happened the program can behave in some way (such as terminating itself).

But if at all, are event and mode well defined terms in CS literature and if so, what is the difference between them?

I'm not sure whether they have accepted meanings, but to the extent that they do, an "event" happens at an instantaneous point in time, as opposed to something ongoing.  If I was reading something that used the word "mode", I probably wouldn't be sure what is meant by "mode" without looking at the context.

I'm not sure whether you should expect precise, widely-accepted definitions for terms that are used informally.


Set of Turing machines $S$ such that any $A \in S$ halts on input the description of any $B \in S$ Does there exist a maximal set of Turing machines $S$ over the alphabet $\{0,1\}$ such that any $A \in S$ halts on input the description of any $B \in S$?

Take S to be the set of deciders. Then S satisfies the property, but is not maximal, because for example we can take:

The set of TMs which are not equal to 0 and which halt on input any string not equal to 0. (Assuming 0 is not a deciding TM.)
Where $A$ is any set of non-deciding Turing machines, the set of TMs which are not in $A$ and halt on input any string not in $A$.

Maybe we can construct such a set $S$ by infinite recursion or by Zorn's lemma, but I haven't been able to see how.

Edit: By maximal, I mean there is no $S' \supsetneq S$ satisfying this property.

Let us construct a Turing machine $M$ such that $M$ first generates its own description $\langle M \rangle$ by recursion theorem. Then for any input $w$ it first checks if $w=\langle M \rangle$, if yes it halts. If not it starts counting infinitely. Now let $S=\{\langle M \rangle\}$. If you try to add any other Turing machine $T$ to $S$ , it could not be part of $S$ as $M$ won't halt on $\langle T \rangle$. Thus following your definition of a maximal set,  $S=\{\langle M \rangle\}$ is such a set.


How to generate graphs with a Hamiltonian path? I need to create a graph generator for my next project. Generally algorithms are trying to find a Hamiltonian path in a graph. So I can create a graph generator, generate a graph, and then I can decide whether the graph has a Hamiltonian path or not. If not, I can regenerate the graph but this is not a cool way.

I want my generated graphs that always have a Hamiltonian path. My graph has two additional conditions:

Vertices can only have 2, 3, or 4 edges.
Possible number of vertices follow the sequence 6, 10, 15, 20, 25...n-5,n where n % 5 = 0.

How should I start, and how do I achieve this easily?

The simplest solution is the one suggested by Yuval Filmus. That is, take a simple path on $n$ vertices, and finish the construction after you have added some number of edges. Clearly, it is easy to enforce the maximum degree condition as well.

Alternatively, you could generate graphs whose structure guarantees the existence of a Hamiltonian path. For example, as shown by Tutte, every 4-connected planar graph has a Hamiltonian path (see e.g., Wikipedia for the statement). Then, a high-performance tool for generating planar graphs is plantri. My feeling is that this is unnecessarily complicated for your use case, but it gives you a possible another approach you might be interested in later on.


Is genetic programming relevant today? My main concern is whether the genetic programming is an active field of research, with some promising applications in practice. It seems like in field of machine learning, the neural networks are the main buzzword, with mentions in mainstream news today, but I have never heard of similar genetic programming "success story".

The research is well in progress, though not so much talked about in comparison to machine learning, deep learning in particular.

Genetic algorithms are applied in particular research areas (examples: "Genetic Programming for Estimation of Heat Flux between the Atmosphere and Sea Ice in Polar Regions" (link), "Genetic Programming with Alternative Search Drivers for Detection of Retinal Blood Vessels" (link), "Optimal placement of water-lubricated rubber bearings for vibration reduction of flexible multistage rotor systems" (link)).
If you are interested in a research of genetic algorithms themselves, see the papers by Claire Le Goues.
There is an annual conference dedicated to evolutionary computation.
Programming frameworks are far from dead as well.

  Is genetic programming relevant today?

Not so long ago, in early 2000-s, people asked the same question about neural networks. Hugo Larochelle mentions how the neural networks papers have been reviewed back then. And we know how it turned out. So don't be so quick in your conclusions, it all can change one day.


how do I find a undecidable subset of a set that's decidable? Given that Let S = {a | |a| is odd}. I know that since S is decidable, but does there exist a subset within S that is undecidable?

Hint: For every language $L$, the language $M = \{ 1^{2x+1} : x \in L \}$ is a subset of $S$.


Drawing Annotated Parse Tree for Syntax Directed Definition Im trying to draw an annotated parse tree for 3*5+4n, the text book shows the following:

[Compilers - Principles, techniques and tools (Dragon Book) by Aho, p308]

I have a few questions regarding this

Why is 3*5+4 considered as a single string? Can't I draw a parse tree something like
for the same string ie:with operator at the node
What is the need for giving T.VAL=3 and then giving another child F.VAL=3. (I understand that the integer attribute for digit needs to be supplied by the lexical analyzer)

The Dragon book style starts with the parse tree of the expression, i.e., the root (I think the very top is a mistake, the expression is an error as written) is the step $E \Rightarrow E + T$. The tree is then decorated giving the attributes their value (like $E.val = 19$). In an attributed grammar you give the grammar and the attributes, so that the grammar looks in part as (subindices mark diferent uses of the same symbol, left to right):
\begin{eqnarray}
E \rightarrow T \quad E.val \leftarrow T.val \\
E \rightarrow E + T \quad E_0.val \leftarrow E_1.val + T.val
\end{eqnarray}
You see that the answer to your second question is that the value of the child $F$ is used to compute the value of $T$.


Find maximal subgraph containing only nodes of degree 2 and 3 I'm trying to implement a (Unweighted) Feedback Vertex Set approximation algorithm from the following paper: FVS-Approximation-Paper. One of the steps of the algorithm (described on page 4) is to compute a maximal 2-3 subgraph of the input graph.

To be precise, a 2-3 graph is one that has only vertices of degree either 2 or 3. By maximal we mean that there is no other 2-3 subgraph which contains the maximal subgraph as a proper subgraph. It does not have to be a maximum subgraph.

The authors of the paper claim that the computation can be carried out by a simple Depth First Search (DFS) on the graph. However, this algorithm seems to elude me. How can the maximal subgraph be computed?

Basically, in 2-3 graph, the lower bound 2 means that any node has to be in a cycle.

In DFS, when you reach an already visited node, you found a cycle. Just check if adding this cycle to your subgraph also respect the upper bound 3.

As you suggested, the maximal 2-3 subgraph is not unique. But if you built it following this method, you ensure that any node/vertex of $G$ you did not select in your subgraph:

either is not part of any cycle and would lead to a vertex of degree 1 if selected
either is part of cycles that would all lead to a vertex of degree 4 if selected

Thus, your 2-3 subgraph is maximal.


Why descriptive power of context-free grammar is greater than regular expression? Below is a saying from this article.

  Regular expressions sit just beneath context-free grammars in descriptive power: you could rewrite any regular expression into a grammar that represents the strings matched by the expression. But, the reverse is not true: not every grammar can be converted into an equivalent regular expression.

Can anyone tell me if the saying is correct and why? Per my understanding, they should have same power and the differernce is a context-free grammar has recursive definition.

Let the set of languages that can be represented by regular languages be $R$. And set of languages that can be generated by a context free grammar be $G$. Then surely $ R \subset G$. For the proof that every regular language has a context free grammar that generates it, I encourage you to look up Michael Sipser's book on complexity. And for the second part, there are many languages which have a context free grammar generating them but are not regular. For example $L=\{ww^{reverse}\}$, where $w^{reverse}$ is reverse of the string $w$. How do we know $L$ has a context free grammar ( you can easily come up with a push down automata for it ), look up Sipsers. And look up pumping lemma in the book to prove $L$ is not regular.

To get an intuition, any regular language can be represented by a finite state automata $FSA$ and vice versa. And any context free grammar can be represented by a push down automata $PDA$ and vice versa ( again read the proof from Sipsers ). And in a  $PDA$ in addition to the states ( like in $FSA$ ) you also have an infinite memory stack. Thus intuitively context free grammars have "power" greater than that of $FSA$.


Pumping lemma for regular languages. Proof Please help me understand the following
$L = \{ a | a ∈ \{0, 1\}^∗, |a| = k ≥ 4, a = a_1a_2...a_{k−1}a_k, ∃i ∈ N, 1 ≤ i < k : a_i = a_{i+1} \}$
To prove: The language $L$ has regular pumping property
My argumentation:
Let $p = 4 $. Let $z$ in $L$, with $z$ $\geq $ $p$. Set $u$ to $\epsilon$. Than $x$ is the first letter, and $w$ the rest.
$x$ $\neq$ $\epsilon$
For all $i$ $\geq $0$: ux^iw$ is in $L$
But if i set i to 0 the word is not in the language? And therefor does not have the regular pumping property? What am i missing? Example $0010$, after pumping $4$ $\geq $ $010$?

I assume that you want to show that the language $L$ does satisfy the Pumping Lemma, as it indeed is regular. In words your language consists of all strings that have length at least 4 and contain two consecutive symbols that are the same. The position of a pair of equal letters letters is indicated here with $i$. (Note $i$ in general is not unique.)
So we need to explain that all strings in the language (above a certain length) can be pumped within the language.
You must realize that your division into $uxw$ can actually depend on the string $a$ itself.
So if $a$ starts with a repeated letter, e.g., $a = 00\dots$, we can pump the third letter. Otherwise if the repeated pair is assumed to be not in the first position, we can then pump the first symbol and we keep the repetition in the string while pumping.


Turing-completeness, Conway's Game of Life and Logical Gates I was recently given an assignment at university asking me to discuss the universal computational capability of Conway's Game of Life.
I'm not required to actually build up a Universal Turing machine in Life, but rather I'm supposed to provide a step-by-step explanation of universality of GoL (as well as the meaning of such result).
I decided to follow this path:

Introduce Turing machines, the notion of universality, and Universal Turing machines.
Introduce the notion of Turing-completeness and its relation with computational universality.
Using such notions and based on previous works and papers, show how Life can be used to simulate a Universal Turing machine.

(Is it a correct reasoning?)
The last point of the assignment asked me to prove the universality of Life by providing an implementation of logical gates in such model, and here come my doubts. I have read dozen of times in StackExchange forums, papers, etc. that the necessary conditions for a system to be Turing-complete are:

A form of conditional repetition or conditional jump (while, for, if and goto)
A way to read and write to some storage mechanism

But I never read anywhere about logical gates (or logical propositions in general). So, my questions are:

Is the capability of implementing logical gates (i.e. evaluate any arbitrary logical function) another requirement? Or, is it an alternative requirement?
Which is the correlation between Turing-completeness and logical gates?

Thank you in advance!
EDIT
Here is a link to the pdf file of the report that I submitted, thanks for your suggestions!

A form of conditional repetition or conditional jump (while, for, if and goto)
A way to read and write to some storage mechanism

The computer you typed this message onto is Turing Complete (well, sort of), yet the only tool it uses is logic gates.  I can give you a simple(ish) example of each:

For the first requirement, processors can use multiplexers to create conditional jump options.  Multiplexers are basically just a bunch of AND gates.

Number 2 is a bit more complex.  Computer memory consists of logic gates that feed back into themselves.  If you study memory, you begin by studying latches and flip-flops.  Here is a simple latch that stores which of the two input lines on the left turned on most recently:

Thus, it stands to reason that, if you can imitate logical gates, you can create a Turing-Complete machine just as you would if you could simulate a Turing Machine.  So, it may be that you don't need to show how to simulate a TM in GoL nodes, but instead take a step to show that logical gates are sufficient to be Turing Complete.

I have one further thought for you that might make your life simpler.  You don't need every gate.  NAND and NOR are each sufficient, on their own, to create every other logic gate.  You can easily do a search like "nand logical completeness" to find the logic gate diagrams to show this.


Fast comparison with a tolerance I am trying to find a way to compare two real numbers (actually floating-point) with a tolerance, i.e. test $|r-s|\le\epsilon$. Without loss of generality, $\epsilon=1$.

I want to do this by replacing the numbers by a discrete key computed on them in such a way that when two keys differ, they map two significantly distant numbers.

$$K(r)\ne K(s)\implies |r-s|\ge 1.$$

The converse,

$$K(r)=K(s)\implies |r-s|<1.$$

may only partially hold, but should be false in a minority of the cases. ($K(r):=0$ is indeed a trivial solution to the first requirement, but is of no use because of the second.)

In my context (database search), the key being discrete and a single comparison for equality being sufficient are essential properties.

The first idea that come to mind is simple rounding, or equivalently, flooring, i.e.

$$K(r):=\lfloor r\rfloor.$$

Anyway this doesn't work as all values in range $[r,r+1)$ map to $K(r)$; the values $1$ unit away from these span $(r-1,r+2)$, which maps to one of $r-1,r,r+1$. So you would need a triple equality test

$$|r-s|<1\implies \lfloor r\rfloor=\lfloor s\rfloor-1\lor \lfloor r\rfloor=\lfloor s\rfloor\lor \lfloor r\rfloor=\lfloor s\rfloor+1.$$

If I am right, the reasoning can be extended to any function $K$: the numbers that map to $K(r)$ are in the set $K^{-1}(K(r))$; the numbers one unit away are in the Minkowski sum $K^{-1}(K(r)) + (0,1)$, which cannot be covered by a single $K^{-1}(K(s))$.

I can also accept a scheme where the key function is computed differently for $s$, but the single comparison principle must remain

$$K(r)\ne L(s)\implies |r-s|\ge 1.$$

Is this a known problem ? Is there a solution or a workaround ?

Update: the problem statement was reformulated in the original text.

If for all $|r - s| < 1$ it is the case that $K(r) = K(s)$ then $K$ is constant (exercise).

What you are asking is impossible.

One thing which is possible is to compare keys with three rather than two possible outcomes:

If $K(r)$ is close to $K(s)$ then $|r - s| < 1$.
If $K(r)$ is far from $K(s)$ then $|r - s| \geq 1$.
Otherwise, we don't know.

Of course, the aim is that the third case happens as rarely as possible. One simple way to achieve this is to choose a random $x$ and some small (non-random) $\epsilon > 0$, and to use
$$
K(r) = \lfloor r/\epsilon + x \rfloor.
$$
Under this definition, the only uncertainty is for $r,s$ at distance $(1-\epsilon,1+\epsilon)$. The random component mitigates even this uncertainty, albeit only by a little.


Assumption of a generation of the dataset by a probability distribution Consider the following paragraph from the deeplearningbook

  The training and test data are generated by a probability distribution
  over datasets called the data-generating process. We typically make a
  set of assumptions known collectively as the i.i.d. assumptions. These
  assumptions are that the examples in each dataset are independent from
  each other, and that the training set and test set are identically
  distributed, drawn from the same probability distribution as each
  other. This assumption enables us to describe the data-generating
  process with a probability distribution over a single example. The
  same distribution is then used to generate every train example and
  every test example. We call that shared underlying distribution the
  data-generating distribution, denoted $p_{data}$. This probabilistic
  framework and the i.i.d. assumptions enables us to mathematically
  study the relationship between training error and test error.

Bolded area is difficult for me to comprehend. Here I have the following issues in interpreting.

1) How probability distribution is generating a dataset?

2) Are the generation process and probability distribution the same?

3) What is the sample space and random experiment for the underlying probability distribution?

The main takeaway from this paragraph is that the authors assume that the training data and test data are sampled i.i.d. from the same distribution, because then if we are able to estimate some statistic of the distribution we sample the training data from, we will be able to do the same on the test data.

As for your specific points:

  1) How probability distribution is generating a dataset?

We sample from a large set according to some distribution. The precise method depends on the problem.

  2) Are the generation process and probability distribution the same?

No, the generation process provides a sample from a distribution. A probability distribution is an abstract mathematical object, while a generation process is a specific algorithm that provides a dataset. In a way, the distribution provides a probabilistic description of what the generation process should return.

  3) What is the sample space and random experiment for the underlying probability distribution?

The sample space depends on the problem in question. I'm not sure what you mean by 'random experiment', but the definition of the random distribution is problem-specific.


Which algorithm can calculate an optimal allocation of students to projects? I am trying to find an algorithm which calculates an optimal and stable allocation of $n$ students to $m$ projects, where each student strictly ranks all projects by preference. The available projects are predetermined and of fixed number and each student needs to be allocated to exactly one project. Each project needs at least one student, but can hold up to a maximum of $y$ students.

For my purposes, there will be on average between 8 to 15 projects available and 80 to 250 students to assign to these projects, resulting in average group sizes of 8 to 15 students per project. A reasonable value for $y$ is usually $\frac{n}{m}+2$.

The definition of optimal and stable as put by @Gassa:

(1) There is no student $S$ assigned to project $P$ such that $S$ likes $Q$ more and $Q$ has an empty slot; (2) there is no pair of students $(S,T)$ such that the current assignments are $S→P$ and $T→Q$, but $S→Q$ and $T→P$ would both be more preferred.

All sort relevant sources I could find so far (listed below) either require an equal number of students and projects (stable marriage) or allocate only one student to each project (exchange-stable matching [1] / the matching problem) and I find it non-trivial to adapt these algorithms for the described purpose.

Sources

[1] Pages 41ff of Algorithmics of Two-Sided Matching Problems by David J. Abraham
[2] A Systematic Approach to the Implementation of Final Year Project in an Electrical Engineering Undergraduate Course by C. Y. Teo and D. J. Ho
[3] Student Project Allocation Using Integer Programming by A. A. Anwar and A. S. Bahaj
[4] Similar (but not identical) question Assignment based on ranked preference on Stack Exchange

This sounds much like a problem for minimum-cost maximum flow.

Construct a network.
The nodes will be the students, the projects, and the added source and sink.

Add an edge with capacity $1$ and cost $0$ from the source to each student.

Add an edge with capacity $y$ and cost $0$ from each project to the sink.

Add an edge with capacity $1$ and cost $r_{i,j}$ from each student $i$ to each project $j$, where $r_{i,j}$ is the rank given by student $i$ to project $j$, the most preferred being ranked $1$.
(Alternatively, we can give negative scores, $-m$ up to $-1$, or even $-(2^m)$ up to $-(2^1)$, and more negative is more preferred.
I believe the exact scheme is not significant.)

Now find the minimum-cost maximum flow.
The maximum-ness of the flow means that each student is assigned to some project, because the maximum flow is obviously equal to the number of students.

The condition which can break is that each project gets at least one student.
(Before proceeding to remedy this, first, check if the values $n$, $m$, and $y$ make failing this condition at all possible.)
We can force it by splitting the edges from projects to the sink: instead of one edge of capacity $y$ and cost $0$, we can have an edge of capacity $1$ and cost $-L$, and another of capacity $y - 1$ and cost $0$.
The value $L$ is a large constant, effectively infinite compared to all other costs: if we just use the ranks from $1$ to $n$, perhaps something like $m \cdot n$ will suffice.
This way, a minimum-cost flow will have to add at least one student to every project in order to use all of the available edges of cost $-L$.

The thing left to prove is that the resulting arrangement is stable.
Indeed, if the stable condition was not satisfied, we could just make a local change, like switching a student to their more preferred project, or swapping the projects for two students.
These would result in strictly lower cost with the same flow, which would in turn contradict the fact that we found the minimum cost flow.

I'm not going into details here (we should start with a formal definition of stableness when only one side has preferences), but hope that they turn out trivially right.
In the unfortunate case they don't, the first I'd do is revisit the cost assignments for $r_{x,y}$.


If a decision problem $A \in \text{NP}$ and there exists reduction so that $A \leq_p B$, for decision problem B, what can be deduced about B? I think that it implies that B can be solved by a non-deterministic polynomial time or worse Turing machine, but I realise that there is possibly some greater result that I'm missing.

Thanks in advance.

$B$ cannot be the language $\emptyset$ or the language $\Sigma^*$.  Apart from that, you can conclude absolutely nothing about $B$.

So, the given condition doesn't rule out anything useful about $B$; just about everything remains possible.  $B$ could be in $P$, or it could be in $NP$, it could be harder than anything in $NP$; you can't rule any of those out.


Why does binary search take $O(\log n)$ time? My question seems like an elementary question, but it's really not.

Suppose I have one million cars in a line sorted in alphabetical order by license plate. I am standing at the top of the line with the car with license plate AAA111. I want to find the car with license plate ZZZ999. I could do binary search to find the car with license plate ZZZ999, but I'm still going to have to walk the distance of one million cars, not a distance on the order of $\log 10^6$.

So this is why I'm asking how or why did computer scientists come up with the idea that binary search takes $O(\log n)$ time?

This is only possible in data structures which allow random access like arrays and vectors.

So if you already know that you have to access the last car , then you can do it in O(1) time.
Data structures like linked lists won't allow you to perform a binary search in O(logn)

The example you have mentioned is similar to using binary search on a linked list. So it will need O(n) time as you will need to traverse all the nodes to reach the last node in the worst case.

So your argument that you cannot reach the middle car in no time is valid in your example but not in data structures which offer such properties.


Semantics for de Bruijn levels There is an exceptionally simple way to embed simply typed lambda calculus with de Bruijn indices in a functional host language (discussed by Carette, Kiselyov & Shan, and by Kiselyov). The construction here, expressed in Haskell, is from Kiselyov's paper:

z :: (a, b) -> a
z (x, _) = x

s :: (a -> b) -> (c, a) -> b
s v (_, h) = v h

lam :: ((a, b) -> c) -> b -> a -> c
lam e h x = e (x, h)

app :: (a -> b -> c) -> (a -> b) -> a -> c
app e1 e2 h = e1 h (e2 h)

eval :: (() -> a) -> a
eval e = e ()

So, for example eval (lam (lam (app z (s z)))) 2 succ evaluates to 3, as our lam expression eval's to the Haskell value \x -> \f -> f x.

This embedding uses de Bruijn indices: to find the binder of a variable, count upward from the variable. I am curious about whether there is an analogous embedding of de Bruijn levels, where to find a variable's binder we count downward. Concretely, \x -> \f -> f x would be represented in such an embedding as lam' (lam' (app' (s' z') z')).

The above embedding uses (as Kiselyov notes) nothing beyond the Hindley-Milner subset of Haskell 2010. It is not obvious to me whether de Bruijn levels can be implemented in such a simple type system. Indeed, it seems quite difficult: the environment tuples built by lam would need to be turned inside-out, or our variables would need to behave differently depending on the depth of the environment tuple. If we only had variables of one type, we could use lists; given that our variables have multiple types, do we require HLists?

======

Late edit to expand on the points in the last paragraph...

One way to think about de Bruijn levels is that lam append's (rather than cons's) to the environment. This way, from the perspective of a variable, the head of the environment (in a closed term) will always correspond to the highest lam. In terms of homogeneous lists:

zL :: [a] -> a
zL (x:h) = x

sL :: ([a] -> b) -> [a] -> b
sL v (_:h) = v h

lamL :: ([a] -> b) -> [a] -> a -> b
lamL e h x = e (h++[x])

appL :: ([a] -> b -> c) -> ([a] -> b) -> [a] -> c
appL e1 e2 h = e1 h (e2 h)

evalL :: ([a] -> b) -> b
evalL e = e []

This models de Bruijn levels, in the sense that lamL (lamL (sL zL)) [] 2 3 evaluates to 3. But it isn't simply typed lambda calculus, since it only allows variables of one type -- e.g., lamL (lamL (appL (sL zL) zL)) is a type error.

To allow variables of multiple types, we can use HList:

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE TypeOperators #-}

import Data.HList

zH :: HList (a ': b) -> a
zH (HCons x h) = x

sH :: (HList a -> b) -> HList (c ': a) -> b
sH v (HCons _ h) = v h

lamH :: HAppendList a '[b] =>
        (HList (HAppendListR a '[b]) -> c) -> HList a -> b -> c
lamH e h x = e (hAppendList h (HCons x HNil))

appH :: (HList a -> b -> c) -> (HList a -> b) -> HList a -> c
appH e1 e2 h = e1 h (e2 h)

Then lamH (lamH (appH (sH zH) zH)) HNil 2 succ evaluates to 3, as desired. But this is a significantly heavier-duty approach than the embedding we began with. Do de Bruijn levels require all this artillery?

Here is a provisional answer. The de Bruijn index and level of a bound variable sum up to the number of enclosing lambdas: $i+l=n_\lambda$. Since the index can be recovered from the level by subtraction, levels can be implemented as 'predecessor' indices p:

z :: (a, b) -> a
z (x, _) = x

s :: (a -> b) -> (c, a) -> b
s v (_, h) = v h

-- ^^^ as above

p :: (((), a) -> b) -> a -> b
p v h = v ((), h)

-- (p . s) v == v

app :: (a -> b -> c -> d) -> (a -> b -> c) -> a -> b -> d
app e1 e2 v h = e1 v h (e2 v h)

-- app manages an extra bit of context: the number of enclosing lambdas

lam :: (((a, b) -> c) -> (d, e) -> f) ->
       (b -> c) -> e -> d -> f
lam e v h x = e (s v) (x, h)

-- lam increments that context

eval :: (((a, env) -> a) -> () -> b) -> b
eval t = t z ()

-- evaluating closed terms...the starting context is z

This seems reasonable, and terms with just one variable (and arbitrary numbers of lambdas) behave as expected. But the type-checker chokes on terms with distinct variables -- e.g., app (p . p) p, our representation of the open term $21$, gives an 'infinite type' error.

To see why, let's consider a concrete evaluated closed term, eval $ lam (lam (app (p . p) p)). If you churn through the reductions by hand, eventually you end up with the following:

\x f -> s (s z) ((), ((), (f, (x, ())))) (s (s z) ((), (f, (x, ()))))

If both occurrences of s (s z) are polymorphic, this appears well-typed, and can be further simplified, to \x f -> f x, as desired (well, our de Bruijn level representation of this term is $\lambda\lambda 21$... close enough!). The problem, it seems, is that the Haskell type-checker insists that the two occurrences of s (s z) have the same monomorphic type, and therefore seems related to the absence of 'first-class polymorphism' in Haskell.

It is not obvious to me how 'deep' the problem here goes -- whether it can be massaged in Haskell; and if not, whether the implementation here can be coherently stated in, e.g., System F (Hindley-Milner seems out due to the need for first-class polymorphism).


Finding containing sets in a set of sets Suppose I have a set of sets of integers $A$, is there an efficient algorithm/data structure that will allow me to query for all sets of integers that include a given input set? That is, given input $I\subset \mathbb Z$, find $C$, the sets in $A$ that include all of $I$, that is $C=\left\{ B \in A \mid I\subseteq B\right\}$.

Looking for the best of a few solutions.

The right approach will generally tend to depend on your data -- size of sets, number of sets, range of elements, size of input, number of queries etc. Here are a couple of approaches:

Approach 1: You could use a Bloom filter for each of the sets in $A$, and for the input set $I$. Assuming the same number of bits for each set, and the same $k$ hash functions for each bloom filter, you could do a bitwise AND of two filters to do a probabilistic test for subsets. This will give no false negatives, but may give false positives. For example, let $F_I$ and $F_{A_i}$ be the bit-arrays of the Bloom Filters for the input set $I$ and some set $A_i$ in $A$. Then, if $F_{A_i} \cdot F_I = F_I$, then there is a possibility that $I \subseteq A_i$. If they are not equal, then $A_i$ definitely does not contain $I$. Using 64 bit integers, you can quickly perform bitwise AND, and comparison operations on a large number of bits, and so can quickly eliminate sets which do not contain $I$. If they turn out to be equal, then for confirmation, you might then have to check each element of $I$ for presence in $A_i$, where $A_i$ might be a hash set.

One downside of Bloom filters is that addition of elements to the set increases the probability of false positives, and deletion of elements is not possible (in simple implementations) since they introduce false negatives. So for deletion of some integer from a set in $A$, the corresponding Bloom filter will have to be recreated. Also, this method will generally give best results when the size of sets is large enough that querying from hash sets starts becoming slow.

Approach 2: If the number of sets is fairly large, but the data distribution is such that there are relatively few unique integers (what is relatively few will depend on your implementation and requirements), you could store the unique integers instead of the sets. You could have a hash-map where each integer is the key, and the value contains a bit-vector (or list) of the sets to which the integer belongs to. Then, you check each integer of $I$ for presence in the hash-map. If it is not found in the hash-map ($O(1)$), then no set of $A$ contains $I$. Otherwise, keep taking the intersection of the sets associated with the integer being checked, with the sets so far found that contain all elements checked thus far. Thus, the problem boils down to efficient set intersection. If the list of sets in the hash map is a bit vector, you need to perform bitwise AND. If they are a list (say, sorted), you can use an adaptation of merge-sort.


Maximizing number of selected squares in a grid We have an $n\times n$ grid of squares, each square has a non-negative integer. Two distinct squares are neighbours if they share a row or column. A selection of squares is good if every selected square has a number of selected neighbours less than or equal to its number.

Is there a known way to find the maximum number of elements in a good selection? Clearly there is a $\mathcal O(2^{n^2}n^2)$ brute force algorithm (we can test for goodness of a selection in time $\mathcal O (n^2)$ by precomputing number of selected squares in each row and column).

There is a dynamic programming algorithm whose running time is $O(2^{4n})$.

Suppose we have already chosen a configuration for the first $i$ columns.  Mark a cell in the $i$th column as "red" if the cell to its right cannot be selected (i.e., the number of selected neighbors, not counting its right neighbor, is equal to the number in that cell), or "green" if the cell to its right can be selected.

Let $c \in \{R,G\}^n$ be a sequence of $n$ colors, and $x \in \{0,1\}^n$ be a sequence of $n$ bits.  Define $A[i,c,x]$ to be the maximum number of elements in a good selection for the first $i$ columns that induces the coloring $x$ on the $i$th column and where $x$ describes which cells are selected in the $i$th column.  Then it is easy to calculate $A[i+1,c',x']$ from $A[i,c,x]$: we have

$$A[i+1,c',x'] = |x'| + \max_{c,x} A[i,c,x],$$

where the max is taken over all $c,x$ that are consistent with $c',x'$ (i.e., such that it's possible to have a selection for the first $i+1$ columns that has selection $x$ in column $i$, selection $x'$ in column $i+1$, colors $c$ in column $i$, and colors $c'$ in column $i+1$).  To be consistent, we must have  $c_j=R \implies x'_j=0$ for all $j$, and $x_j + x'_{j-1} + x'_{j+1}$ must be at most the number in column $i+1$, row $j$ (and $c'_j=R$ iff they are equal).

This yields a dynamic programming algorithm with $O(n \times 2^{4n})$ running time: we need to fill in $n \times 2^{2n}$ entries of $A[\cdot,\cdot,\cdot]$, and each entry requires us to compute a max over at most $2^{2n}$ numbers.


Algorithm for finding cliques Given an arbitrary undirected graph $G = (V,E)$, I am interested in a low-polynomial time algorithm which can find several moderately large (ideally $O(n^\epsilon)$ vertices per clique for $\epsilon > 0$) cliques in $G$, provided they exist.

I am aware that the problem of finding the maximal clique is NP-hard. For my purposes, however, I don't need maximality per say. Rather, it would be helpful to have an algorithm which runs relatively quickly and with high probability finds some nontrivial cliques.

I am aware that for fixed $k$, finding a $k$-clique if it exists can be done in $n^k$ time by simply testing all subsets of $k$ vertices. This algorithm appears to be of limited use because of the exponential growth in $k$.

Does there exist an algorithm or multiple which can, with high probability, find multiple moderately large cliques in a general undirected graph?

Suppose that there exists a polytime algorithm which finds a clique of size $n^\epsilon$ if there is any. Then you can approximate maximum clique to within $n^{1-\epsilon}$ (assuming $\epsilon \leq 1/2$), which is NP-hard by a classical result of Håstad. Indeed, run your algorithm (stopping it if it exceeds its advertized running time), and check whether its output is a clique of size at least $n^\epsilon$. If so, output $n^\epsilon$, otherwise output $1$.

You might want to look into the planted clique problem, in which the goal is to find a clique "planted" inside a uniformly random graph. This is possible in polytime (with high probability) as long as the clique is large enough, $\Omega(\sqrt{n})$. Your case may be different, but similar ideas might work in practice.


Algorithm deciding if a radius of a graph is two Given an unweighted, undirected graph, what is the time complexity to decide if its radius is at most 2? Are there any faster algorithms than doing BFS on each node?

Yes. Given the adjacency matrix representation of a graph, computing its second power will allow you to see what nodes are connected by a path of length at most 2. The fastest known matrix multiplication algorithm is $O(n^{2.373})$, which is better than the $O(VE)$ you would get from doing BFS on each node.


About a particular use of hashing Look at the last problem on page 2 here,
http://www.cs.nyu.edu/~khot/CSCI-GA.3350-001-2014/sol3.pdf

All one wants to do is to convert a $x \in \{ 0,1\}^n$ into a $y \in \{0,1\}^k$ . Then just a linear transformation would have been enough. Why install this vector "b"?
If $a_1,x_1,x_2 \in \{0,1\}^n$ and $b_1,y_1,y_2 \in \{0,1\}$ then why is demanding simultaneous satisfaction of the equations $a_1^Tx_1 + b_1 = y_1, a_1^Tx_2 + b_1 = y_2$ the same as claiming the simultaneous satisfaction of the equations, $a_1^T(x_1 \oplus x_2) = y, b_1 = y \oplus y_1$ ?( where $y = y_1 \oplus y_2$)

For your first question, the vector $b$ is necessary to make sure $\text{Pr}_{A,b}[\vec{a_1} x^{T} + b_1 = y] = 1/2$, for $k = 1$.

Otherwise, it is easy to see that $\text{Pr}_{A,b}[\vec{a_1} x^{T} = 0] = 3/4$ and $\text{Pr}_{A,b}[\vec{a_1} x^{T} = 1] = 1/4$, for $n=1$. By conditional probability and the law of total probability, we can get $\text{Pr}_{A,b}[\vec{a_1} x^{T} = 0] = 5/8$ and $\text{Pr}_{A,b}[\vec{a_1} x^{T} = 1] = 3/8$, for $n=2$. This approach can be generalized to arbitrary $n$.


Longest substrings of common length with the same parity Given two sequences $a$ and $b$, find largest $x$ such that in $a$ there is substring $A$ and substring $B$ in $b$ meeting those conditions:

length of both $A$ and $B$ is equal to $x$;
sum of elements in $A$ has the same parity as sum of elements in $B$.

Lengths of $a$ and $b$ are up to $5\times10^5$, so simple $O(n^2)$ solution won't do.

Example:
$a = [0, 1, 2, 3, 4, 5]$
$b = [3, 1, 3, 6]$
Answer: 3 (one of the possible solutions is $A = [2, 3, 4], B = [3, 1, 3]$).

I've thought about it for hours and can't find a solution. How to do this in linear or linearithmic time complexity?

I'm quite sure the problem can be simplified to for index $i$, storing only sum of elements up to $i$ modulo $2$. However, it doesn't help me much.

(The problem comes from a rather-old Israeli book תכנות תחרותי: סביב אתגרים ('Competetitive programming') by Mordechai Ben-Ari. The book isn't well known and I couldn't find any solution in Hebrew, so I translated the problem into English for a better chance of getting answer.)

Any help will be appreciated.

Here is an $O(n\log^2 n)$ solution.

The first step is to reduce to an easier problem:

  Given $x_1,\ldots,x_n \in \{0,1\}$, determine, for all $0 \leq i \leq n$ and $b \in \{0,1\}$, whether there is a contiguous subarray of length $i$ whose sum is equal to $b$ modulo 2.

Applying this to both $A$ and $B$, we can solve the original problem in $O(n)$.

The basic idea is to use divide and conquer. Given an array $x_1,\ldots,x_n$, divide it into two arrays $x_1,\ldots,x_m$ and $x_{m+1},\ldots,x_n$ of roughly equal size. Every contiguous subarray of $x_1,\ldots,x_n$ of length $i$ with parity $b$ has one of the following forms:

Contiguous subarray of $x_1,\ldots,x_m$ of length $i$ with parity $b$.
Contiguous subarray of $x_{m+1},\ldots,x_n$ of length $i$ with parity $b$.
The concatenation of a subarray $x_{m-i_1+1},\ldots,x_m$ of parity $b_1$ with a subarray $x_{m+1},\ldots,x_{m+i_2}$ of parity $b_2$, where $i_1+i_2 = i$ and $b_1+b_2 \equiv b \pmod{2}$.

We can determine whether subarrays of the first two forms exist, for all $i$ and $b$, by running the procedure recursively on the two halves. The interesting part is the third form. We start by determining the parity of all arrays of the form $x_{m-i_1+1},\ldots,x_m$ and of the form $x_{m+1},\ldots,x_{m+i_2}$ for all $i_1,i_2$, which takes time $O(n)$. Let $L_{b_1}$ be the set of $i_1$ such that $x_{m-i_1+1},\ldots,x_m$ has parity $b_1$, and define $R_{b_2}$ analogously. Using FFT (exercise), for each $b_1,b_2$ we can determine in $O(n\log n)$ the set $X_{b_1b_2}$ of $i$ such that there exist $i_1 \in L_{b_1}$ and $i_2 \in R_{b_2}$ summing to $i$. Given the sets $X_{b_1b_2}$ for all $b_1,b_2$, we can determine whether subarrays of the third form exist, for all $i$ and $b$.

In total, denoting the running time of our algorithm by $T(n)$, we get the recurrence
$$ T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + O(n\log n), $$
whose solution is $T(n) = O(n\log^2 n)$.


To build a special unary regular expression Say that there's a prime number P,
And we can easily build an unary regular expression [E0]for every number that is divisible by P:
E0::= (aaaa...a)*,with p "a",

The question is, how do we build the opposite unary regular expression [E1], for every number that isn't divisible by P?

Do I need to build the E1 by listing all the number mod p=1,2, to p-1, or there can be a easier way to build it ?

There is a "smart" way of following your approach:
$$
(a^p)^*a(\epsilon+a)^{p-1}
$$
Here $r^p$ is shortcut for $r$ concatenated $p$ times.

This regular expression has length $O(p)$. On the other hand, using the pumping lemma it is not hard to show that the minimal NFA for the language contains at least $p$ states, and this gives a lower bound of $\Omega(p)$ on the size of a regular expression for the language, since a regular expression can be translated to an NFA with only a constant multiplicative blow-up in size.


Polynomial time reductions I'm having a very hard time understanding what's what.

$$L_{1}\leq_{p}L_{2}$$

If $L_2$ is stated to be in $\textbf{NP}$, is it necessarily true that $L_1$ is $\textbf{NP}$-Complete? I need to show the following for an assignment, but I'm having a dispute with a fellow student because he claims that I can't claim that $L_1$ is $\textbf{NP}$-Complete...

  Suppose that $L_1\leq_p L_2\leq_p L_3$. Also suppose that $L_3$ is in $\textbf{NP}$. Explain how to solve $L_1$ deterministically in exponential time.

I say (and I could be wrong - and that's a strong possiblity since I have very little understanding of this material) that since $L_3$ is in $\textbf{NP}$, $L_2$ also has to be in $\textbf{NP}$, and so therefore $L_1$ has to be in $\textbf{NP}$. And if that's the case, then $L_1$ can easily be converted to a deterministic algorithm through a breadth first search through the non-deterministic computation tree. Is there something I'm missing?

You asked two questions.  What you are missing is that those two questions are unrelated.

Question 1:

  $$L_{1}\leq_{p}L_{2}$$

  If $L_2$ is stated to be in $\textbf{NP}$, is it necessarily true that $L_1$ is $\textbf{NP}$-Complete?

No.  Consider the case where L1 and L2 are the same easy problem.

Question 2:

  I need to show the following for an assignment, but I'm having a dispute with a fellow student because he claims that I can't claim that $L_1$ is $\textbf{NP}$-Complete...

    Suppose that $L_1\leq_p L_2\leq_p L_3$. Also suppose that $L_3$ is in $\textbf{NP}$. Explain how to solve $L_1$ deterministically in exponential time.

  I say […] that since $L_3$ is in $\textbf{NP}$, $L_2$ also has to be in $\textbf{NP}$, and so therefore $L_1$ has to be in $\textbf{NP}$. And if that's the case, then $L_1$ can easily be converted to a deterministic algorithm through a breadth first search through the non-deterministic computation tree. Is there something I'm missing?

There is nothing wrong with your proof.  (Okay, I would not call the exponential-time simulation of a nondeterministic polynomial-time Turing machine “breadth-first search,” but that is a separate issue.)  As your fellow student said, it is true that you cannot claim that L1 is NP-complete, and indeed you have never claimed that L1 is NP-complete, so your proof for Question 2 does not contradict the answer to Question 1.


Types as first class Citizen Coming from a C++ background I don't understand why one needs types / type expressions as first class citizen?
The only language I know that supports this feature is Aldor.

Does anybody have some literature about types as first class citizen or know some reasons why it's useful?

First class types enable something called dependent typing. These allow the programmer to use values of types at type level. For example, the type of all pairs of integers is a regular type, while the pair of all integers with the left number smaller than the right number is a dependent type. The standard introductory example of this is length encoded lists (typically called Vector in Haskell/Idris). The following pseudo-code is a mixture of Idris and Haskell.

-- a natural number
data Nat = Zero | Successor Nat

data Vector length typ where
  Empty : Vector Zero typ
  (::)   : typ -> Vector length typ -> Vector (Successor length) typ

This piece of code tells us two things:

The empty list has length zero.
consing an element onto a list creates a list of length n + 1

This looks very similar to another concept with 0 and n + 1, doesn't it? I'll come back to that.

What do we gain from this? We can now determine additional properties of the functions we use. For example: An important property of append is that the length of the resulting list is the sum of the lengths of the two argument lists:

plus : Nat -> Nat -> Nat
plus          Zero n = n
plus (Successor m) n = Successor (plus m n)

append : Vector n a -> Vector m a -> Vector (plus n m) a
append Empty  ys = ys
append (x::xs) ys = x :: append xs ys

But all in all this technique does not seem all to useful in everyday programming. How does this relate to sockets, POST/GET requests and so on?

Well it doesn't (at least not without considerable effort). But it can help us in other ways:

Dependent types allow us to formulate invariants in code - rules as how a function must behave. Using these we get additional safety about the code's behaviour, similar to Eiffel's pre- and postconditions. This is extremely useful for automated theorem proving, which is one of the possible uses for Idris.

Coming back to the example above, the definition of length-encoded lists resembles the mathematical concept of induction. In Idris, you can actually formulate the concept of induction on such a list as follows:

              -- If you can supply the following:
list_induction : (Property : Vector len typ -> Type) -> -- a property to show
                  (Property Empty) -> -- the base case
                  ((w : a) -> (v : Vector n a) ->
                      Property v -> Property (w :: v)) -> -- the inductive step
                  (u : Vector m b) -> -- an arbitrary vector
                  Property u -- the property holds for all vectors

This technique is limited to constructive proofs, but is nonetheless very powerful. You can try to write append inductively as an exercise.

Of course, dependent types are just one use of first class types, but it's arguably one of the most common ones. Additional uses include, for example, returning a specific type from a function based on its arguments.

type_func : Vector n a -> Type
type_func Empty = Nat
type_func v     = Vector (Successor Zero) Nat

f : (v : Vector n a) -> type_func v
f Empty = 0
f vs    = length vs :: Empty

This is a nonsensical example, but it demonstrates something you cannot emulate without first class types.


Why and how is a quantum computer faster than a regular computer? I'm currently reading a book (and a lot of wikipedia) about quantum physics and I've yet to understand how a quantum computer can be faster than the computers we have today.

How can a quantum computer solve a problem in sub-exponential time that a classic computer can only solve in exponential time?

A quantum computer by itself isn't faster. Instead, it has a different model of computation. In this model, there are algorithms for certain (not all!) problems, which are asymptotically faster than the fastest possible (or fastest known, for some problems) classical algorithms.

I recommend reading The Limits of Quantum by Scott Aaronson: it's a short popular article explaining just what we can expect from quantum computers.


Can a probabilistic Turing Machine compute an uncomputable number? Can a probabilistic Turing Machine compute an uncomputable number?

My question probably does not make sense, but, that being the case, is
there a reasonably simple formal explanation for it. I should add that
I am pretty much ignorant of probabilistic TM and randomized algorithms.
I looked at wikipedia, but may even have misunderstood what I read.

The reason I am asking that is that only the computable numbers can have their digits enumerated by a Turing Machine.

But with a probabilistic Turing Machine, I can enumerate any infinite
sequence of digits, hence also sequences corresponding to non
computable numbers.

Actually, since there are only countably many computable numbers,
while there are uncountably many reals that can have their digit
enumerated, I could say that my probabilistic Turing Machine can be
made to enumerate the digits of a non computable number with
probability 1.

I believe this can only be fallacious, but why? Is there a specific
provision in the definition of probabilistic TM that prevents that?

Actually, I run into this by thinking whether various computation models can be simulated by a deterministic TM, in question "Are nondeterministic algorithm and randomized algorithms algorithms on a deterministic Turing machine?". Another p[ossibly related question is "Are there any practical differences between a Turing machine with a PRNG and a probabilistic Turing machine?".

Consider the following reasonable definition for a Turing machine computing an irrational number in $[0,1]$.

  A Turing machine computes an irrational $r \in [0,1]$ if, on input $n$, it outputs the first $n$ digits (after the decimal) of the binary representation of $r$.

One can think of many extensions of this definition for probabilistic Turing machines. Here is a very permissive one.

  A probabilistic Turing machine computes an irrational $r \in [0,1]$ if, on input $n$, (1) it outputs the first $n$ digits of $r$ with probability $p$; (2) it outputs any other string with probability less than $p$; (3) it never halts with probability less than $p$.

Under this definition, it is not immediately clear whether everything that you can compute is indeed computable (under the sense of the first definition).

However, there are some modifications that do allow us to conclude that the resulting number is computable, for example:

We can insist that the machine always halt.
We can insist that $p > 1/2$.

Other modifications are not necessarily enough. For example, does it help if we assume that the non-halting probability tend to $0$ with $n$?

Summarizing, it might depend on the model.


(Un)Decidability of disjoint decidable and undecidable sets I thought of this question today: given are a decidable set $A$ and undecidable set $B$ for which $A \cap B = \emptyset$. Is $A \cup B$ decidable or undecidable?

I am almost sure that it is undecidable but cannot come up with an argument/proof as to why, or even a counterexample.

Hint: Suppose you could decide $A \cup B$. Using an algorithm for deciding $A$ and an algorithm for deciding $A \cup B$, can you decide $B = (A \cup B) \setminus A$?


What is a standard way to construct a turing machine for any function to compute I am new to turing machines, I am having problems with mapping a function to a turing maching that computes that particular function. for example:

f(x) = 2x + 3 n>= 0
MIN(x,y) leaves the smallest between x and y on the tape. e.g. x=2 y = 3 i.e. #aabaaa

I am not looking for a solution to the above but some kind of pattern i can use to solve these kind of particular problems quicker, in terms of transitions and what to have in mind before starting to solve.

Designing a Turing machine is pretty much like writing a program. You
have to choose a representation for the data and a corresponding code
(read * transitions*) to manipulate the data. Remember how we do
arithmetics (addition, multiplication, quotient, ...) by manipulating
in strange ways strings of symbols that represent numbers, whether in
unary or positional representation, or even with Roman numerals.

The difficulty is generally that the means for data representation are
pretty elementary: symbols on a tape. So you have to find ways to
encode everything into that. Also the programming instructions are
very simple. So you have to find a way (for complex machines) to
decompose the problem into parts, and to assemble the coresponding
machine parts. Pretty much what you do when you define functions and
subprograms in usual programming.

You can make your life easier by using different sets of states for
each subprogram. But basically people rarely design Turing machines,
except for specific proofs. Then the problem is often how to combine into one several simpler machines that have been separately designed. You can find that in textbooks.

It can be amusing to find elegant solutions for simple problems. Like
puzzles. You can add constraints. For example, you second question can
be solved in several ways. Some use more tape than others.

Exercise: do long multiplication of two binary numbers, then two
ternary numbers. Well, just think about it. Where would you store the
multiplication table?


Context-free languages not closed under making them "extension-free" For a language $L$, define:
$$
NE(L) = \{x \in L : x \text{ is not the proper prefix of any string in } L\}
$$

I'm trying to show context-free languages are not closed under this operation.
I've been struggling for a long time now trying to find a counterexample, that is, a language $L$ such that $L$ is context-free but $NE(L)$ is not context-free, and have come up with nothing. I'd appreciate ideas or hints about languages to look into.

Edit: For the vast majority of context-free languages, it seems that either $NE(L) = L$ or $NE(L) = \varnothing$. I'm having trouble even finding candidate languages.

Rather than the language $L\subseteq \Sigma^*$ consider the language $L' =L\$\$$, so concatenate every string by two copies of $\$$ where $\$$ is a new symbol not in $\Sigma$.

Let $x\in \Sigma^*$.
String $x\$$ is not a proper prefix of $L'$ iff $x\$\$ \notin L'$ iff $x\notin L$.

That should start you going.


Is Terra the only system programming language able to compile code at runtime? I stumbled across Terra last year, and the most similar language I can think of is Julia. Terra is inspired by and uses Lua for templating/metaprogramming instead of being derived from e.g. the Lisp or ML families, but like many JITted language implementations it blurs the line between compile-time and run-time.
Are there any other low-level (no VM, small runtime, etc.) programming languages I'm missing that can compile and run code at runtime (besides assembly)? Maybe Forth-likes, or Extempore's xtlang? Terra calls this (multi-)staged programming.

No. So far the only ones I've found are pretty obscure/old, both variations of C:

`C
E-Code


Greedy Solution for Selecting Prefix Sum Given $n$ arrays. Each has size of $h$. Let $a_{i, j} \in \mathbb{I}$ be the $i$-th element of $j$-th array. You can select at most $k$ numbers from all arrays but if you pick $a_{i, j}$, you have to pick $a_{1, j}, a_{2, j}, \dots, a_{i-1, j}$ as well. Each element can only be picked once. Find maximum sum of elements.

My greedy solution is : Let $p_{i, j}$ be $\sum_{x=1}^{i} a_{x, j}$. Sort a list of $\frac{p_{i, j}}{i}$ for all $i$ and $j$ in descending order. Then iterate through the list and check each value whether we have included the prefix sum of this array into our final answer or not. If no and $h \geq j$, we include it in the final answer, subtract $i$ from $h$, and mark $j$ as included. If yes and $j >$ the index of the previous one, we do the same thing just the part extended from the previous one.

Is this solution optimal or is there a better solution to this problem?

Unfortunately, your greedy algorithm may return elements whose sum is not the maximum. For example, let $n=h=k=2$ and
$$\begin{pmatrix}
a_{11} & a_{12}\\
a_{21} & a_{22}
\end{pmatrix} =
\begin{pmatrix}
3 & 1\\
2 & 1
\end{pmatrix}.$$
Your algorithm will pick 3 and 1. The optimal elements should be 3 and 2.

The natural approach to this problem is dynamic programming.

Here are the subproblems.

For nonnegative integers $t$ and $j$ such that $0\le j\le n$ and $0\le t \le \min(nh, t)$, find $dp(t,j)$, the maximal sum of $t$ elements from the first $j$ arrays where all elements selected from the same array must be a prefix of that array. The wanted maximum sum is the maximum number of all $dp(t,j)$.

In order to select $t$ elements from the first $j$ arrays, we can select $i$ elements from the $j$-th array and $t-i$ elements from the first $j-1$ arrays for some $i$, $0\le i\le \min(t,h)$. Hence we have the following recurrence relation.

$$ dp(t,j) = \max_{0\le i\le \min(t,h)}\left(dp(t-i, j-1) + \sum_{1\le k\le i}a_{k,j}\right)$$

The base cases and the boundary cases can be figured out easily.


Why is the inapproximability $2^{n^\epsilon}$? Many inapproximability factors are $2^{n^\epsilon}$. I don't know why this is 2 instead of 3, 4, ..., etc.

To be precise, given a problem,

theorem 1 says: It's NP-hard to approximate the problem to $2^{n^\epsilon}$ for any $0 \leq \epsilon < 1$;

theorem 2 says: It's NP-hard to approximate the problem to $3^{n^\delta}$ for any $0 \leq \delta < 1$.

Can we say theorem 2 is tighter?

I know that given $\delta < 1$, we can find $\epsilon < 1$ such that $3^{n^\delta} \in \mathcal O(2^{n^\epsilon})$. However, the definition of approximation factor is not in asymptotics. We should get $3^{n^\delta} \leq 2^{n^\epsilon}$ if we want to say the two theorems are actually same.

The two theorems are equivalent. You can write
$$
3^{n^\delta} = 2^{\log_2 3 \cdot n^\delta} = 2^{n^{\delta + \frac{\log \log_2 3}{\log n}}} = 2^{n^{\delta + o(1)}}.
$$
In particular, for any $\delta' > \delta$ there exists $N$ such that $3^{n^\delta} \leq 2^{n^{\delta'}}$ for all $n \geq N$. Conversely, $3^{n^\delta} \geq 2^{n^\delta}$.

Hardness of approximation results are only about "large enough $n$". Every problem can be solved exactly in polynomial time (even constant time) for all inputs of size at most $N$, for any fixed $N$.


Connected components and graph edition There are known algorithms to find the connected components of a given graph.  Those I know are easily extensible to support addition of nodes and edges to the graph and then find the resulting components more quickly than by recomputing from scratch.

What I'm looking for is an algorithm with an associated data structure which allow the efficient determination of connected components after removal of nodes and edges.

In general, what you are looking for is known as dynamic connectivity: it comes with different flavors depending on whether vertices/edges can be added, deleted, or if both operations are allowed.

Many relevant papers are summarized in this answer on TCS.SE. If you are looking for a practical implementation, a possible starting point is [1]. Here, the authors perform experiments and provide some C++ code (these are for fully dynamic algorithms).

[1] Iyer, R., Karger, D., Rahul, H., & Thorup, M. "An experimental study of polylogarithmic, fully dynamic, connectivity algorithms." Journal of Experimental Algorithmics (JEA) 6 (2001): 4.


Proof Idea: There are irrational numbers whose decimal expansion cannot be computed The online lecture I am watching stated a proof idea:

The set of all possible programs is countably infinite, yet
the set of irrational numbers is uncountably infinite.

I don't think this is sufficient, it assumes one program can only return one irrational number.
How to show that I can not write one program that returns all irrational numbers?

You can't even write a program that outputs one single irrational number. What you can do, is write a program which will output for example every decimal digit of some irrational number, one after the other, assuming unlimited resources and unlimited time, and which will output every single digit eventually (but will never output all digits). We count that as "outputting a number".

If you tried to write a program that first outputs all digits of π, followed by all digits of e, that wouldn't work because it never will finish outputting the digits of π. What you could do is output the first decimal of π, followed by the first decimal of e, followed by the second digits of π and e, and so on. So a program can output two (or three or four or a billion) irrational numbers, if we change the definition a bit.

You could write a program that outputs a countable infinite number of irrational numbers. Start with the first digit of the first number. Then the second digit of the first, followed by the first digit of the second number. Then the 3rd digit of the first, 2nd digit of the second, and 1st digit of the third number, and so on forever. So this program would eventually output each digit of a countable infinite number of irrational numbers.

You can't extend this to an uncountable numbers. Being uncountable, it is impossible for example to output just the first digits of all these numbers.

So the best you can do, with a modified definition of what "outputting an irrational number" means, is that you can have a countable number of programs, which each calculate a countable number of irrational numbers, but countable times countable is still countable, so you cannot output all irrational numbers.


Big-O and not little-o implies theta? If $f(n)$ is in $O(g(n))$ but not in $o(g(n))$, is it true that $f(n)$ is in $\Theta(g(n))$?

Similarly, $f(n)$ is $\Omega(g(n))$ but not in $\omega(g(n))$ implies $f(n)$ is in $\Theta(g(n))$?

If not, can you provide an explanation/counter-example, please?

Let's start with the simple case $g = 1$, and $f$ having positive values only (that's all we care about with functions that represent complexity).

$f \in O(1)$ means that $f$ is bounded: there exists $B$ such that $f(n) \le B$ (for sufficiently large values of $n$).
$f \in o(1)$ means that $\lim_{n\to\infty} f(n) = 0$.
$f \in \Theta(1)$ means that $f$ is bounded above and below: there exists $A \gt 0$ and $B$ such that $A \le f(n) \le B$ (for sufficiently large values of $n$).

Note that $f \in \Theta(1)$ requires a positive (nonzero) lower bound for $f$: for sufficiently large $n$, $f(n) \ge A$. If $f \in o(1)$ then for sufficiently large $n$, $f(n) \lt A$. It is possible for neither of these to hold if $f$ oscillates between “large” (bounded below) and “small” (converging to zero) values, for example
$$f(n) = \begin{cases}
  1 & \text{if \(n\) is even} \\
  1/n & \text{if \(n\) is odd} \\
\end{cases}$$
Informally speaking, half of $f$ is $\Theta(1)$ (the even values) and half is $o(1)$ (the odd values), so $f$ is neither $\Theta(1)$ nor $o(1)$, despite being $O(1)$.

With $g = 1$, there are regularity conditions on $f$ that's sufficient to make $O$ and not $o$ imply $\Theta$: this does hold if $f$ is monotonic; more generally, it holds if $f$ has a limit at $\infty$. With arbitrary positive $g$, these sufficient conditions translate to conditions on the quotient $f/g$ being monotonic (because $f \in O(g)$ iff $f/g \in O(1)$, etc.). It isn't enough for $f$ and $g$ to be both increasing or any such condition from real analysis. You can take any $g$ and multiply it by the $f$ above to get a counterexample to your conjecture.

With algebraic conditions on $f$ and $g$, if they are taken from sufficiently restricted sets of functions, the conjecture may hold. For example, it holds if they're both polynomials (for polynomials, $f \in O(g)$ if $\deg(f) \le \deg(g)$, $f \in o(g)$ if $\deg(f) \lt \deg(g)$ and $f \in \Theta(g)$ if $\deg(f) = \deg(g)$). But as soon as you add “perturbations” to $f$ and $g$, all bets are off.


Progress of algorithms in problem spaces Continuing in the vein of two prior questions (1) and (2), we started with sorting, where we had

a set of $n!$ input possibilities
a goal space of only one element consisting of the one correct sorted sequence

We then arrived at a generalized argument which I'll alter slightly and call A:

Define a space of input possibilities
Define the goal space, a subset of the input space
Reason about constraints in order to set a lower bound

Three Questions: given that there are quadratic algorithms for sorting,

Can we conclude for the quadratic sorting algorithms, where we have an input space of $n!$ input possibilities and roughly $n^2$ steps, that there are $O(n!/n^2)$ possibilities removed from the search space per step on average?
Let's say we're given a problem formalizable in the form of argument A above where the input space is exponential in terms of the size of the input, $O(2^n)$, and the problem is solvable in polynomial time, $O(n^c)$, for some constant $c$. Can we conclude there are $O(2^n/n^c)$ possibilities removed from the search space per step on average?
Can we at least conclude that a $O(2^n)$ problem cannot be solved in polynomial time by removing one element from the input space per step?

Yes and No. If you see this as "amortized" number of possibilities removed in each step, then yes (follows trivially since you need $n^2$ time but have a search space of $n!$), but it is very difficult to formalize a notion of how many possibilities in each step are removed. You would need a notion of what a "step" is. An elementary operation, like an addition? Then how does one addition in the middle of, for instance, bubble sort reduce the search space? Instead, you have some kind of "checkpoints" during the algorithm at which the search space gets smaller, for instance when you find the 1st element, the 2nd, and so on. A concrete counter example to your idea is an algorithm that uses $n^2$ time in a dummy loop, and then solves the problem. In the first $n^2$ steps therefore, the solution space does not get smaller.
No, see above.
Yes, trivially?


Reduction rule for IF? I'm working through Simon Peyton Jones' "The Implementation of Functional Programming Languages" and on page 20 I see:

IF TRUE ((λp.p) 3) ↔ IF TRUE 3         (per β red)   (1)
                   ↔ (λx.IF TRUE 3 x)  (per η red)   (2)
                   ↔ (λx.3)                          (3)

Step 1 to 2 is explained as η-conversion. But from 2 to 3 it says "The final step is the reduction rule for IF." I'm not sure what this reduction rule is.

The reduction rule you ask for is the usual one for IF statements. It consists of two computation rules and one context rule:

  $\text{IF TRUE}$ $a$ $b$ $\to$ $a$
  $\text{IF FALSE}$ $a$ $b$ $\to$ $b$
  $\dfrac{a\to a'}{\text{IF}~a\ b\ c\to \text{IF}~a'\ b\ c}$

In both the call-by-value (strict) and call-by-need (lazy) settings, both $a$ and $b$ can be arbitrary expressions. They need not be values.

Rules of this kind, that reduce specific functions (here IF), are often called delta rules.

Now, the reason step (2) above is necessary is so that the reduction rules for $\text{IF}$ can apply. $\text{IF}$ requires 3 arguments, but in the original term it has only two, so cannot be reduced. ($\text{IF}$ is being partially applied, just
like any function in Haskell. This means that only part of its arguments need to be supplied.) The use of $\eta$-expansion provides the additional argument, without changing the semantics.


Is $\Theta$ symmetric? For example if
$$ f(x)= \Theta (g(x)) $$

from the definition of the theta notation, there exist c1 and c2 constants such that

$$c_1 g(x) \le f(x) \le c_2 g(x)$$

then if only we took the constants $1/c_1$ and $1/c_2$ we could say from the definition that

$$ g(x)= \Theta (f(x)) $$

Right?

Right, except that the constants are actually $1/c_2$ and $1/c_1$.  That is, $$c_1 g(x) \leq f(x) \leq c_2g(x) \Rightarrow \frac{1}{c_2}f(x) \leq g(x) \leq \frac{1}{c_1}f(x)\,.$$
Also, remember that the inequalities only apply for large enough $x$.


Finding duplicate in immutable array in linear time and constant space We have a array of $N$+1 integers. The integers range from 1 to $N$. The array contains at least one duplicate. Our goal is to find one of the duplicate entries. We have the constraint that we cannot modify the input array. Is there any solution to this problem which has $O(N)$ time complexity and $O(1)$ space complexity?

Let us denote the array by $a_1,\ldots,a_{n+1}$. Define a function from $\{1,\ldots,n+1\}$ to itself as follows: $f(i) = a_i$. The graph of the function is a directed graph in which each node has outdegree 1. Since $n+1$ has indegree 0, the connected component of $n+1$ has a node with indegree 2, which corresponds to a duplicate entry. This node can be found using a cycle detection algorithm in linear time and constant space.


Viterbi training vs. Baum-Welch algorithm I'm trying to find the most probable path (i.e., sequence of states) on an hidden Markov model (HMM) using the Viterbi algorithm. However, I don't know the transition and emission matrices, which I need to estimate from the observations (data).

To estimate these matrices, which algorithm should I use: the Baum-Welch algorithm or the Viterbi Training algorithm? Why?

In case I should use the Viterbi training algorithm, can anyone provide me a good pseudocode (it's not easy to find) ?

From my comment:

This answer on crossvalidate.SE may be of use. I wasn't aware of viterbi-training. I have only used BW or other EM-based methods in the past. Based on the answer in the link, I think BW would be the most useful. It seems Viterbi-Training gives no guarantee on bounds. However, the latter does have useful application if BW takes far too long to compute.