Subset sum exponential solution - how does the sorting work? The wiki for the subset sum problem found here it states that you take the list of N elements and split it into two lists of N/2 elements.  You then generate all the subsets for each list (each having $2^{N/2}$ subsets).  It then states...

"Each of these two lists is then sorted. Using a standard comparison sorting algorithm for this step would take time $O(2^{N/2}N)$. However, given a sorted list of sums for k elements, the list can be expanded to two sorted lists with the introduction of a (k + 1)st element, and these two sorted lists can be merged in time $O(2^{k})$."

Can someone illustrate/explain this part of the algorithm?

The idea is that two sorted lists of length $n$ can be merged into one sorted list of length $2n$ in time $O(n)$. This is a standard procedure used in the mergesort algorithm. Given a list of integers $x_1,\ldots,x_m$, you proceed as follows:

Start with $A_0 = 0$.
Merge $A_0$ and $A_0 + x_1$ into $A_1$.
Merge $A_1$ and $A_1 + x_2$ into $A_2$.
...
Merge $A_{m-1}$ and $A_{m-1} + x_m$ into $A_m$.
Output $A_m$.

Here $A_k + x_{k+1}$ is formed by adding $x_{k+1}$ to all elements of $A_k$, preserving the order.

Since $A_k$ has length $2^k$, the total running time is
$$
O(|A_0| + |A_1| + \cdots + |A_{m-1}|) = O(1 + 2 + \cdots + 2^{m-1}) = O(2^m).
$$


Why does my code work: bijecting binary trees to Dyck paths The number of Dyck paths (paths on a 2-d discrete grid where we can go up and down in discrete steps that don't cross the y=0 line) where we take $n$ steps up and $n$ steps down follows the Catalan numbers. Another set of objects that follows the Catalan numbers is the number of binary search trees with $n$ nodes.
This suggests we can biject binary trees to Dyck paths (see here). We get a hint on how to do the bijection based on why the two objects satisfy the same recurrence (for Catalan numbers):
$$C_{n+1} = \sum\limits_{j=0}^{n}C_{j}C_{n-j}$$
Binary trees satisfy it because you designate one node as the root, then create a binary tree on its left (with $j$ nodes) and another one on its right. Dyck paths satisfy it by conditioning on the first time the path hits the y=0 line (which is what $j$ in the equation above represents). So we first take a mandatory step up, then we make a path of $2j$ steps that doesn't cross the $y=1$ line; then we go down one step to touch $y=0$ for the first time, and finally we make another path of $2(n-j)$ steps that doesn't cross the $y=0$ line.
This suggests we might be able to construct a Dyck path given a binary search tree (with node-keys labelled from $1$ to $n$ and there is just one way to assign them, see here) recursively, starting at the root. When we go to the left node of the tree, we need to consider the sub-path one level above the current level (where we start at level-0) and when we go to the right, we simply stay at the same level. Since the key of the node we're processing tells us where the path first struck the current level from the start, we know that it 2 times the number of steps representing the key from the start must be a step down.
The Python code below demonstrates this idea and works (tested it extensively). If you don't use python, the idea is very simple; I just set the path array to all 1's ("up" steps) and the recurse on the tree, inserting -1's ("down" steps) based on the keys on the tree nodes.
import numpy as np

class TreeToDyck():
  def __init__(self, tree_node, n):
    # Initially create an array of 2n ones. All steps are set to "up".
    self.path = np.ones(2*n)
    # Now insert downs at appropriate places.
    self.tree_to_dyck(tree_node, 1)

  def tree_to_dyck(self, tree_node, start):
    if tree_node is None:
        return
    # Go down. Bear in mind the "path" array is 0-indexed.
    self.path[start+2*tree_node.key-2] = -1
    self.tree_to_dyck(tree_node.left, start+1)
    self.tree_to_dyck(tree_node.right, start)

Now, the thing to note is that the key of the node we're at gives us many hints about the path. But, I ignore most of them and simply insert a "down" step. I start with all steps in the path array set to go up. Then, based on the keys of the tree nodes, I insert down steps.
Surprisingly, this is enough. Which means the following two statements must be true:

The down steps will never collide with each other. So, we'll never insert a "down" step at the same location twice. This will ensure we insert $n$ down steps, as the path must contain.
The last step in the Dyck path is always a "down" step. So, we will always end up inserting a "down" at the very last position in the array no matter the tree.

I want help proving the above two statements. And if there is any other requirement needed to prove that the algorithm will work.

My answer is not a formal proof, but I hope it contains enough information to make you feel confident about your own solution. My strings start at $1$. Sorry, old habit.
Consider a binary tree $T$ with $n$ nodes. Assume $T$ has $n$ nodes, subtrees $T_\ell$ and $T_r$. If the root of $T$ has label $k$ this means that $T_\ell$ has $k-1$ nodes.
A tree with $n$ nodes has a Dyck codes of length $2n$. There are two ways of determining the Dyck code $dyck(T)$ of tree $T$. One is recursively:
$dyck(T) = U \; dyck(T_\ell) \; D \; dyck(T_r)$.
In this string we observe exactly one $D$, which is associated to the tree $T$, other $D$'s are written recursively. The position of this single $D$ is exactly at $2k$. We know this because the length of $dyck(T_\ell)$ equals $2(k-1)$.
Note that the symbols generated by $dyck(T_\ell)$ are shifted by one, because of the $U$ that is written before its code. This is the main observation: it is due to a left branch, and those left branches is what you are counting in your code.
The other way of determining $dyck(T)$ is graphical. Draw the tree and make a traversal around it. Write $D$ for a left child (even when that leads to an empty subtree) and $U$ for a right child. (We visit each node twice: this is both an pre-order and inorder-traversal.) If you try this you will see that each $D$ appears at the number of the node plus the number of times we went left as seen from the root.
The tree below has code (with subscripts that count position in the string and superscript which is the inorder label associated to the root of the corresponding subtree) $U_1^3 U_2^1 D_3^1 U_4^2 D_5^2 D_6^3 U_7^{10} U_8^6 U_9^4 D_{10}^4 U_{11}^5 D_{12}^5 D_{13}^6 U_{14}^8 U_{15}^7 D_{16}^7 D_{17}^8 U_{18}^9 D_{19}^9 D_{20}^{10} U_{21}^{11} D_{22}^{11}$.


Is it always possible to have one part of the reduction? So I have been asked this question during my comprehensive and I have a few answers to it, I just wanted to check with the community whether I'm on track with them.

Is the following statement true?

$\forall A,B \subseteq \Sigma^{*}, \exists\ f : \Sigma^{*} \rightarrow \Sigma^{*}, s.t. \forall x \in A \implies f(x) \in B $

The function  $f$ had to be decidable in polynomial time, as in the notion of reductions. So, the question in english stands as, is it always possible to find a polytime computable function of the like written above, for any two languages, s.t. one direction of the notion of reduction holds.

So, at that moment I couldn't argue for polytime computability, but , the obvious idea of having a map from $\Sigma^{*}$ to an element in B, was all I could come up with. Later, on subsequent thinking I realised that it basically becomes a membership checking question for arbitrary B. Another idea, also struck and that being when B $\ =\ \phi$, then $(A,\phi)$ serve as the counterexample sought, where A is any language.

So, in case we do not allow for B being the empty language, any instance of B which is undecidable or rather, takes more than polynomial time for membership checking [Not sure about the second one as its unknown whether P!=NP] holds, right?

Other questions associated to this, are:

(1) if A=3SAT and B $\in \mathbb{P}$ , then does the existence of such a  $\ f$, prove P=NP or do you need the reverse direction of reduction to hold as well, to conclude that?

(2) What about when $\ f$ is allowed to be decidable, or semidecidable, what changes?

(3)And, what if the reverse direction of reduction was the condition to be satisfied by $\ f$, ie, $\forall x \in \Sigma^{*},\  f(x) \in B \implies x \in A$ then what changes? [ I worked this out, taking the contrapositive , ie, $\forall x \not\in A \implies f(x) \not\in B$ it basically boils down to membership checking for the complement language, ie, $\overline{B}$ ]

EDIT : Sorry (1) was trivial. As pointed out by the answer below, $\mathbb{P} \subseteq \mathbb{NP}\ $ means I can just use the same f trivially for the reverse direction.

If you define "reduction" using a single implication as in $x\in A \implies f(x) \in B$, then $A$ indeed always "reduces" to any nonempty $B$. Take any $b\in B$, and define $f(x)=b$ the be a constant function. This is computable in O(1), hence in polytime.

It does not matter if $B$ is decidable, or in P, or anything else -- as long as it is not empty, that's enough.

1) No, it does not prove anything. If you have that $A$ reduces to a PTIME $B$ with your proposed reduction, you can't conclude $A$ is PTIME. $HALT$ would reduce to checking if a number is $12$ (which is PTIME), but $HALT$ is surely not PTIME.

2) $f$ above is constant, hence always decidable. (There is no such a thing as a semicomputable function)

3) Similarly, the converse implication is satisfied, for any $A$ and non-full $B$, if we take the constant function $f(x)=b \notin B$.

Below, I consider the more standard definition of reduction with the double implication.

The halting problem is not reducible (polytime or not) to its complement, nor its complement is reducible to the halting problem.

This is because $A\leq B$ holds iff $\bar A \leq \bar B$, hence in either case the complement of $HALT$ would reduce to $HALT$, but the first is not recursively enumerable, and the second is, so we get a contradiction.

For the others:

1) Yes. The reverse direction is trivial, since if $B\in P$ then $B\in NP$ hence it reduces to 3SAT.

2) The $HALT$ counterexample above holds for any computable $f$. There is no such a thing as a semicomputable function -- semidecidability only applies to problems.


What exactly is transmission time? Seems very trivial but I'm confused which one of these correctly define transmission time.

Time taken by a message to reach receiver.
Time taken to push message on the link by the sender.

Which one is correct one?

Time taken by a message to reach receiver : Propagation delay or time
Time taken to push message on the link by the sender : Transmission time

Transmission time is the time from the first bit until the last bit of a message has left the transmitting node. Or, in simple word it's the amount of time required for the router to push out the packet.

Packet transmission time = Packet size / Bit rate

Reference :

in2p3.fr/actions/formation/InfoTempsReel/IN2P3-Ch1-datatran-tr.pdf


Sort an array where $0\leq a_n\leq n^2$ and $a_n\in\mathbb{N}$ sort an array where $0\leq a_n\leq n$
sort an array where $0\leq a_n\leq n^2$(hint represent every element in base $n$)
All the elements are integers
for the first 1 I used counting sort and for the second one I thought maybe after changing to base $n$ using raddix?  ONe more thing,i've been asked to prove correctness for this first 1 but I've never see how to do this.
Any hints?

You can make a list of length $n^k$ which $k$ is $1$ for the first case and $2$ for the second one.
So you have an array and you can put each element in the relevant position. This idea may waste space but it's fast.
Time complexity of this algorithm is $O(n)$.
Space Complexity is $O(n^k)$.


How are Neural Networks made so general? After reading this blog about Deep Neural Networks learning about selfies I'm struck by how generic the network in question is.

In short: I'm thinking of trying to write something vaguely similar for solving cryptic crosswords, but I can't fathom how to make the general algorithms it uses generic enough that it can develop them ?

A contextual example from the blog is how the network 'understands' filters? Would I need to teach the network about tokenizing the input around keywords, or is that something the network has to 'figure out'? How do I 'seed' the operations the network can perform?

Neural nets don't "understand", they are trained. Despite the fancy term, a neural net is simple a regression model on steroid - often high-dimensional. It's a bunch of weights (vectors) connected in a graph, with an input side and some updating rule (for example, gradient descent).

You'll need a lot of labeled data for the training set. The neural net is trained by feeding these input and telling it about the supposed output, and it readjusts its weights in the regression model.

Apart from that it's a blackbox - kinda magical. But you can't use a neural net trained to recognize selfies to do cryptography (or anything else).


PCP with commutative alphabet Post's Correspondence Problem is known to be undecidable. A variant of PCP, namely PCP with partially commutative alphabets is also known to be undecidable.
Is the following variant also known to be undecidable?

PCP with commutative alphabet.
Given and alphabet $\Sigma = \{a_1, a_2, \ldots, a_K\}$ and $2N$ sequences $\gamma_1, \gamma_2, \ldots, \gamma_N, \delta_1, \delta_2, \ldots, \delta_N \in \Sigma^*$.
Determine if there is a sequence of integers $\{i_j\}_{j=1}^M$ such that for each $1 \leq j \leq M$, $i_j \in \{1, 2, \ldots, N\}$ and for each $1 \leq m \leq K$,

$\#(a_m, \gamma_{i_1} \gamma_{i_2} \ldots \gamma{i_M}) = \#(a_m, \delta_{i_1} \delta_{i_2} \ldots \delta_{i_M})$
where $\#(a, w)$ denotes the number of occurences of the symbol $a$ in the string $w$.

Notice why I used the term "commutative" for the alphabet: the order of the symbols in the strings does not matter; only the counts need to be equal.

In general, is any variant of (unbounded) PCP with commutative alphabet known to be decidable or undecidable?

Let  $\gamma_{ij},\delta_{ij}$ be the number of characters $\sigma_j$ in $\gamma_i,\delta_i$ (respectively). Then the PCP instance has a solution if there exist non-negative integers $a_1,\ldots,a_N,b_1,\ldots,b_N$ such that for all $j \in \{1,\ldots,K\}$,
$$
\sum_{i=1}^N a_i \gamma_{ij} = \sum_{i=1}^N b_i \delta_{ij}.
$$

While integer programming is hard in the general case, in this case we can solve it using linear programming in polynomial time. I claim that the program above has a solution in non-negative integers iff it has a solution in non-negative reals. One direction is obvious. In the other direction, suppose that the linear program corresponding to the integer program above (replacing non-negative integers with non-negative reals) is feasible. Then there is a solution for the program above in the non-negative rationals (every vertex of the polytope would do). Multiplying this solution by a common denominator, we obtain a solution of the original integer program.


Efficiently computing the smallest integer with n divisors In order to tackle this problem I first observed that

$$\phi(p_1^{e_1} \space p_2^{e_2} \cdots \space p_k^{e_k}) = (e_1 + 1)(e_2 + 1)\cdots(e_k +1)$$

Where $\phi(m)$ is the number of (not necessarily prime) divisors of $m$. If $m$ is the smallest integer such that $\phi(m) = n$, then

$$\phi(m) = n$$
$$(e_1 + 1)(e_2 + 1)\cdots(e_k +1) = n$$

Now we must choose $e_i$ such that $\prod_{i} p_i^{e_i}$ is minimal. The choices for $p$ are trivial - they are just the primes in ascending order.

However, my first thought for choosing $e_i$ was incorrect. I thought you could simply factor $n$, sort the factors in descending order and subtract 1. Most of the time this works fine, e.g. the smallest integer with $n = 15$ divisors is:

$$15 = 5 \cdot 3$$
$$15 = (4 + 1)(2 + 1)$$
$$m = 2^4 3^2 = 144$$

But this is incorrect for $n = 16$:

$$16 = 2 \cdot 2\cdot 2 \cdot 2$$
$$16 = (1 + 1)(1 + 1)(1 + 1)(1 + 1)$$
$$m = 2^1 3^1 5^1 7^1 = 210$$

Whereas the correct answer is:

$$16 = (3 + 1)(1 + 1)(1 + 1)$$
$$m = 2^3 3^1 5^1 = 120$$

So it's clear sometimes we need to merge factors. In this case because $7^1 > 2^2$. But I don't exactly see a clean and direct merging strategy. For example, one might think we must always merge into the $2$ power, but this is not true:

$$1552 = (96 + 1)(1 + 1)(1 + 1)(1 + 1)(1 + 1)$$
$$m = 2^{96} 3^1 5^1 7^1 11^1 > 2^{96} 3^3 5^1 7^1$$

I can't immediately think of an example, but my instinct says that some greedy approaches can fail if they merge the wrong powers first.

Is there a simple optimal strategy for merging these powers to get the correct answer?

Addendum. A greedy algorithm that checks every possible merge and performs the best one on a merge-by-merge basis, fails on $n = 3072$. The series of one-by-one merges is:

$$2^2 3^1 5^1 7^1 11^1 13^1 17^1 19^1 23^1 29^1 31^1$$

$$2^3 3^2 5^1 7^1 11^1 13^1 17^1 19^1 23^1 29^1$$

$$2^5 3^3 5^1 7^1 11^1 13^1 17^1 19^1 23^1$$

However the optimal solution is:

$$2^7 3^3 5^2 7^1 11^1 13^1 17^1 19^1$$

Here's a solution, based on my comments above.  I make no claims this is optimal.

The idea is to consider $T(n,m)$, which we defines as "the smallest positive integer with exactly $n$ divisors and $m$ distinct prime factors". We make the easy observations:

\begin{align}
T(n, 1) &= 2^{n-1}\\
T(2^m, m) &= p_1p_2\cdots p_m
\end{align}

And we also have the recurrence:

\begin{equation}
T(n,m) = \min_{d|n} [T\left(\frac{n}{d}, m-1\right)\cdot p_m^{d-1}]
\end{equation}

Finally, the quantity you're looking for is
\begin{equation}
\min_{1\le i\le\lceil\log(n)\rceil} T(n, i)
\end{equation}

To that end, here is some Python code, which agrees with all the numbers you gave above.  Note that it works with the logarithms to keep the numbers smaller: so the actual integer you seek is round(2**smallest(n)).

import functools
import itertools
import math

# All primes less than 100.
PRIMES = [
  2, 3, 5, 7, 11,
  13, 17, 19, 23, 29,
  31, 37, 41, 43, 47,
  53, 59, 61, 67, 71,
  73, 79, 83, 89, 97,
]

LOG_PRIMES = [math.log2(p) for p in PRIMES]

def smallest(n):
  max_factors = math.ceil(math.log2(n))
  min_so_far = float('Infinity')
  factors = factorize(n)
  memo = {}
  for i in range(1, max_factors+1):
    t = T(n,i, factors, memo)
    if 0.0 < t < min_so_far:
      min_so_far = t
  return min_so_far

def T(n, m, factors=None, memo=None):
  if memo is None:
    memo = {}
  if n < 2 or m < 1:
    return 0
  elif m == 1:
    # Everything on the smallest prime.
    return (n-1) * LOG_PRIMES[0]
  elif n < 2**m:
    return 0
  elif n == 2**m:
    # Product of first m primes, in log.
    return sum(LOG_PRIMES[:m])
  elif (n,m) in memo:
    return memo[(n,m)]

  if factors is None:
    factors = factorize(n)
  if len(factors) < m:
    return 0

  smallest = float('Infinity')
  for factor_list in powerset(factors):
    divisor = product(factor_list)
    first = T(divisor, m-1, factor_list, memo)
    # No such product.
    if first < 1.0:
      continue
    second = (n/divisor - 1) * LOG_PRIMES[m-1]
    total = first + second
    if total < smallest:
      smallest = total

  memo[(n,m)] = smallest
  return smallest

def product(nums):
  return functools.reduce(lambda x,y: x*y, nums, 1)

def factorize(n):
  prime_factors = []
  for p in PRIMES:
    while n%p == 0:
      n //= p
      prime_factors.append(p)
    if n == 1:
      break
  return prime_factors

def powerset(lst):
  # No empty set.
  return itertools.chain.from_iterable(itertools.combinations(lst, r)
                                       for r in range(1, len(lst)+1))


What are the reasons to learn different algorithms / data structures serving the same purpose? I have been wondering about this question since I was an undergraduate student.
It is a general question but I will elaborate with examples below.

I have seen a lot of algorithms - for example, for maximum flow problems, I know around 3 algorithms which can solve the problem: Ford-Fulkerson, Edmonds-Karp & Dinic, with Dinic having the best complexity.

For data structures - for example, heaps - there are binary heaps, binomial heaps & Fibonacci heaps, with Fibonacci heap having the best overall complexity.

What keeps me confusing is: are there any reasons why we need to know them all? Why not just learn and get familiar with the best complexity one?

I know it is the best if we know them all, I just want to know are there any "more valid" reasons, like some problems / algorithms can only be solved by using A but not B, etc.

There's a textbook waiting to be written at some point, with the working title Data Structures, Algorithms, and Tradeoffs. Almost every algorithm or data structure which you're likely to learn at the undergraduate level has some feature which makes it better for some applications than others.

Let's take sorting as an example, since everyone is familiar with the standard sort algorithms.

First off, complexity isn't the only concern. In practice, constant factors matter, which is why (say) quick sort tends to be used more than heap sort even though quick sort has terrible worst-case complexity.

Secondly, there's always the chance that you find yourself in a situation where you're programming under strange constraints. I once had to do quantile extraction from a modest-sized (1000 or so) collection of samples as fast as possible, but it was on a small microcontroller which had very little spare read-write memory, so that ruled out most $O(n \log n)$ sort algorithms. Shell sort was the best tradeoff, since it was sub-quadratic and didn't require additional memory.

In other cases, ideas from an algorithm or data structure might be applicable to a special-purpose problem. Bubble sort seems to be always slower than insertion sort on real hardware, but the idea of performing a bubble pass is sometimes exactly what you need.

Consider, for example, some kind of 3D visualisation or video game on a modern video card, where you'd like to draw objects in order from closest-to-the-camera to furthest-from-the-camera for performance reasons, but if you don't get the order exact, the hardware will take care of it. If you're moving around the 3D environment, the relative order of objects won't change very much between frames, so performing one bubble pass every frame might be a reasonable tradeoff. (The Source engine by Valve does this for particle effects.)

There's persistence, concurrency, cache locality, scalability onto a cluster/cloud, and a host of other possible reasons why one data structure or algorithm may be more appropriate than another even given the same computational complexity for the operations that you care about.

Having said that, that doesn't mean that you should memorise a bunch of algorithms and data structures just in case. Most of the battle is realising that there is a tradeoff to be exploited in the first place, and knowing where to look if you think there might be something appropriate.


Finding a complexity by solving inequality I would like to calculate the complexity of an algorithm using the "inequality strategy".

This algorithm takes two integers as an entry $n, m$. Moreover this algorithm is recursive and if we denote $C_{n,m}$ the number of operations this algorithm does for entry $n, m$ we have the following inequality :

$$C_{n,m} \leq C_{n, (m-1)} + C_{(n-1), (m-1)} + O(1)$$

Moreover the algorithm terminates for the entry : $(0,k)$ and $(k, 0)$ for all $k \in \mathbb{N}$ and $C_{0,k} = O(1)$ and $C_{k, 0} = O(1)$.

So now I need to somehow solve the inequality to get $C_{n,m}$ for all $n, m$. Yet I don't really know how to do this.

The problem is that it seems to me that any function work. For example If I say : $C_{n,m} = O(m)$ then it's tre since by unduction we then have :

$C_{n,m} \leq O(m-1) + O(m-1) + O(1) = O(m-1)$

Moreover If I say that :  $C_{n,m} = O(n)$ then it also work since by induction :

$C_{n,m} \leq O(n) + O(n-1) + O(1) $

So what is the problem with I am doing, and how to solve this inequality to get the complexity of $C_{n,m}$ ?

Thank you !

You can’t use $O(m) + O(m) = O(m)$ in an inductive proof, since the hidden constant will keep blowing up. To see this more closely, suppose that you bound $C_{n,m}$ with $A\cdot m$. Then
$$
C_{n,m} \leq C_{n,m-1} + C_{n-1,m-1} + O(1) \leq 2A(m-1) + O(1).
$$
The right-hand side will generally not be at most $Am$.

Instead, let's try to use Pascal's identity, $\binom{a}{b} = \binom{a-1}{b} + \binom{a-1}{b-1}$. We guess that $C_{n,m} \leq A\binom{m}{n}-B$. Then
$$
C_{n,m} \leq C_{n,m-1} + C_{n-1,m-1} + O(1) \leq \\
A\left(\binom{m-1}{n} + \binom{m-1}{n-1}\right) - 2B + O(1) =
A \binom{m}{n} - 2B + O(1).
$$
For $B$ larger than the hidden constant in $O(1)$, the right-hand side will be at most $A\binom{m}{n} - B$, and so we will be able to prove the induction hypothesis. For given $B$, we can choose large enough $A$ so that $C_{0,k} \leq A \binom{k}{0} - B$ would hold. However, we reach a problem when considering the other base case $C_{k,0} \leq A \binom{0}{k} - B$. Therefore we need to fix our strategy.

At this point, we leave it to the reader to find the right binomial coefficient to add.


Halting problem for turing machines with one input My question is:

Is there a simple construction similar to Turing's 'liar' program that shows that Turing machines plus a halting oracle cannot decide if a given Turing machine halts on all inputs.

When I talk about the liar program I am referring to the standard proof that a Turing machine can't determine the halting of all other Turing machines, since case analysis on the following leads to contradictions
def Liar(T):
   if Halts('T(T)'):
      loop()
   else:
      return

I can see that having a Halting oracle would allow me to determine if a Turing machine halts on any finite set of inputs (We would just run it all in order).
If we call regular Turing machines level 0, we can call Turing machines plus the halting oracle level 1. I have seen that the proof using the Liar program works just the same to show that level 1 machines have their own Halting problem which is undecidable for them.

What you call a "liar" program is typically called a diagonalization argument, since it somehow resembles Cantor's diagonalization argument.
Usually what we mean by that is that if we try to enumerate all elements with a certain property, then we can point out, by construction, an element that is necessarily "incorrect", and we do so by showing that it does not satisfy the property with regards to itself (this is completely hand-wavy, but if you've seen the argument, you'll hopefully understand what I mean).
Now, what you're asking is whether we can do the same in order to show that ALL_TM (TM universality) is not decidable by a TM with oracle to HALT_TM.
Well, not really. At least not in a natural way: the argument would have to start by assuming there exists an oracle machine M that decides ALL_TM, and then constructing from M some other machine N (what you call a "liar" machine), which would yield a contradiction when we run N on N.
However, the machine N would have to be an oracle machine, not a standard TM (or you would essentially lose the power of the oracle in M). But since the oracle in N takes as input standard TMs, then the inner working of N would somehow need to create a standard TM to feed to the oracle. This doesn't seem like a natural construction, and it would certainly not be simple.
Now, perhaps there is some convoluted way of giving a direct diagonalization argument for this claim, but it's not well motivated, given that proving the claim directly (namely that ALL_TM is not decidable by a TM with oracle to HALT) is not difficult using standard tools, such as reductions.


How would I write a single expression involving count, x and y that has exactly the same effect as shown (below)? count=0
x=7
y=3
while(y<x):
     y+=1
     count+=1

I'm having trouble writing this as a single expression.

I'm assuming that you're interested in the following more general situation:

Input: $x,y$.
Initialize $count$ to $0$.
While $y < x$: Increment both $y$ and $count$.

You want to know the values of $x,y,count$ at the end.

If $y \geq x$ to start with, then the while loop never runs, so nothing happens. If $y < x$ (and both are integers), then the loop runs $x - y$ times (why?). At this point you should be able to tell what are the values of $x,y,count$ at the end of the code.


Correspondence between automata and formal grammars? From Wikipedia

  Since there is a one-to-one correspondence between linear-bounded
  automata and such grammars, no more tape than that occupied by the
  original string is necessary for the string to be recognized by the
  automaton.

Note: If I am correct, "such grammars" mean context-sensitive grammars.

I wonder if the quote means that:

  a context-sensitive language can have multiple  context-sensitive grammars that can generate it, and multiple linearly bounded machines that can have it as their recognized languages, and there exists a one-to-one correspondence between the linearly bounded machines and the context-sensitive grammars, for the context-sensitive language.

More generally, a recursively enumerable formal language can have multiple formal grammars that can generate it, and multiple Turing machines that can have it as their recognized languages. So I wonder if there exists a one-to-one correspondence between Turing machines and formal grammars, for a recursively enumerable formal language.

Given a formal grammar, how can we construct a Turing machine to have the language generated by the grammar as its recognized language?

Conversely, given a Turing machine, how can we construct a formal grammar which can generate the language which is the one recongized by the Turing machine?

The expression "one-to-one correspondence" seems a little too strong for me. It suggests that for every grammar there is a specific automaton. It should be read as: for every grammar an automaton can be constructed for the same language and vice-versa.

Context-sensitive languages are accepted by linear bounded automata and generated by context-sensitive grammars.
Context-sensitive grammars have productions of the form $\beta A \gamma \to \beta\alpha\gamma$ where $A$ is a nonterminal and $\alpha$ is nonempty. They are equivalent to length-increasing (more properly noncontracting, or monotone) grammars, which have the form $\alpha\to \beta$ where $|\alpha| \le |\beta|$ (usually $\alpha$ is assumed to include at least one nonterminal).

The languages of Turing machines are generated by unrestricted, or type-0, grammars. See Chomsky Hierarchy.


Finding $k$ claws ($K_{1,3}$ bipartite graphs) in a graph? Usually questions deal with claw-free graphs, but suppose we are given a graph $G$ and there are $k$ vertex-disjoing claws in the graph, how can we derive a randomised algorithm using color coding to find them. My intuition is to approach this with $k$ colors, but not really sure how to start it. Could someone give me some hints and ideas on how to approach this?

Finding vertex-disjoint copies of a subgraph $H$ in a graph $G$ is known as Graph Packing.

You could use Divide and Color to find the claws in $O^*(4^k)$, also deterministically (look for Chen et al. construction of universal set for derandomization).


The Power of Randomized Reduction I try to figure out a redundant power of two-sided error randomized Karp - reduction.

It's well known fact and it is relatively hard to show that BPP is reducible by a one-sided error randomized Karp-reduction to coRP (in case of promise problem).

Without delving into details it make sense that the combination of the one - sided error probability of the reduction and the one-sided error probability of coRP leads to two-sided error probability of BPP. Of course the proof of that is not so intuitive.

The question it is possible by two-sided error randomized Karp-reduction to reduce BPP to some constant set in P? In the light of the power of one - sided randomized Karp - reduction, it make sense that two-sided randomized Karp - reduction is strong enough to reduce BPP to constant set, but how to show it formally?

Addendum:

BPP is the set of the problems that is solvable in polynomial time by two-sided error randomized algorithm, so as a result of two - sided error randomized algorithm we will get some output, them the problem in BPP can be reduced to problem P by two-sided error randomized Karp - reduction in sense that reduction is allowed to make error on both sides. Does it mean that two - sided error randomized reduction will justify the two-sided error that was made by the algorithm in solving the problem in BPP?

We can think of a BPP algorithm $A$ for a language $L$ as accepting two inputs, the real input $x$ and a random string $r$, whose length is polynomial in $x$. Now take the Boolean circuit evaluation problem, which is P-complete. Since $A(x,r) \in P$, we can reduce $A$ to this problem, substituting random $r$. Then if $x \in L$ then the reduction yields a YES instance with probability at least $2/3$, and if $x \notin L$ then it yields a NO instance with probability at least $2/3$.


Subset Sum to SAT reduction I have seen numerous ways to reduce CNF-SAT to SS, but is there any way to reduce SS to SAT (or one of its variations)? I have tried researching it, but all it brings up is the (apparently) much more common opposite reduction.

You can reduce addition to a circuit with XOR, AND, OR gates.

Each element of the sum must first be ANDed with an extra variable that is true if the element belongs to the subset, and false otherwise.

Then the circuit can be trivially reduced to 3-SAT. The clauses are determined by the gates.

For example each AND gate (A & B = C) requires these 4 clauses:

(A | !B | !C)

(!A | B | !C)

(A | B | !C)

(!A | !B | C)

Why? Because:

false & true != true

true & false != true

false  & false != true

true & true != false

Each clause eliminates one impossible situation for the gate.

Then if you want the result of the sum to be zero, you add one unit clause for each bit of the result.


I want to figure out whether my problem described below is reducible to the set cover problem I have a collection of non-empty sets $S_i$, where $1 \le i \le n$, which are constructed from elements of a universe $U$.

I need an algorithm that gives me a set $T$ of minimum cardinality ($T \subseteq U$), such that $T \cap S_i \ne \phi, \forall i$, where $1 \le i \le n$.

I am not sure whether it is an NP-complete problem and can be reduced to minimum set cover in some way. I thought of reducing it to vertex cover, by taking the sets as vertices, and putting an edge between any two sets if their intersection is non-empty, but that doesn't quite seem to work either.

Hint: For each element $x \in U$, let $A_x = \{i : x \in S_i\}$. Then $T$ is a solution to your problem iff $\{A_x : x \in T\}$ covers all of $\{1,\ldots,n\}$. This problem is known as minimum hitting set.


Will the machine ever reach on any other state other than start state? Given a TM M, will it ever reach any other state other than start state if it starts with blank tape ?
Is the above problem decidable ?

I think that if a TM really reaches any other state other than start state then we can check the transitions and find out. But if it doesn't at any point of time then we can't say that it will never reach other state in future too so it results in infinite waiting.

So the problem is undecidable or R.E according to me but the answer is decidable.

Please tell me where am I going wrong .

Say $M$ has start state $s$ and transition function $\delta$. Construct a new Turing machine $M'$ with $Q = \{s, HALT\}$ (where s != HALT) and $\delta'$ as it's transistion function, defined by the following. $s$ is again the start state and $HALT$ is the accept state.

$$ \delta'(s, x) = \begin{cases}
      s & \delta(s, x) = s \\
      HALT & \mbox{otherwise} \\
   \end{cases} $$

$M'$ will halt IFF $M$ ever transitions out of the start state.

If you know what the maximum shifts function is for two states and your symbols then you can simulate $M'$ for that many steps to determine if $M'$ halts or not. Non constructively even if we can't compute the busy beaver function for your number of symbols it has some value and therefore our argument still goes through.

This shows that, at least classically speaking, this problem is decidable. It also constructively shows that it's decidable for any number of symbols that we can constructively prove an upper bound on the maximum step function for. This algorithm runs in constant time...where the constant might be very large. So asymptotically it's ideal. I'm not sure if there's an algorithm that does this with a smaller constant but I'm betting it's not possible.


When Turing Machine behaves like Finite state automaton I read following:

  Turing Machine with finite (fixed sized) tape is essentially Finite state automaton.

Is this fact correct? My doubt is Turing Machine can go infinite loop even on finite tape if it keeps moving from left to right and finite state machine does never go in such infinite loops. So, do we also need restrictions like "only right head movements are allowed" along with finite tape to turn Turing Machine to finite state automaton?

Yes, this is (kind of) correct, in the following sense:

The set of languages that can be recognized by Turing Machines with a fixed tape is equivalent to the set of regular languages (i.e. the set of languages recognizable by finite automata).

The reason behind this is that such Turing Machines have a finite number of configurations, which is independent from the input.

Note that crucially, for this to hold we need one tape for the input which is read-only, and a fixed-space working tape.

A bit more precisely, for such a TM, we can construct a 2-way DFA, by having a state for every possible configuration of the TM, as well as a 2-way read only input tape. The latter model is equivalent to DFAs, by a clever construction using "crossing sequences".

An important observation, however, is that these machines can be far more succinct than their equivalent DFAs (or even NFAs).


Greatest fixpoint of the type of lists I'm working through Samuel Mimram's book Program = Proof. In the first chapter, he discusses recursive types in OCaml, and inductive types. An exercise he provides on the topic has me a little bit confused. In the exercise, he asks the reader to define the function induced by the inductively defined type of lists, and then show that it has a greatest fixpoint, distinct from the smallest fixpoint, and provide a concrete description of it.
I believe I'm able to define the function he mentions. If we had the type of lists of integers:
type list =
    | Nil
    | Cons of int * list

Then our induced function $F : \mathcal{P}(\mathcal{U}) \rightarrow \mathcal{P}(\mathcal{U})$ (where $\mathcal{P}(\mathcal{U})$ is the powerset of all possible values of our type list) looks like:
$$
F(X) = \{ \mathrm{Cons}(n, l) \ | \ n \in \mathbb{Z},\ l \in X \} \cup \{ \mathrm{Nil} \}
$$
In the book, we learn that the least fixpoint of such a function defines the set of values inhabiting our type. That makes sense. He also goes through a proof of the Knaster-Tarski theorem to demonstrate that such a least fixpoint will exist, due to the fact that $\langle \mathcal{P}(\mathcal{U}), \subseteq\rangle$ is a semilattice and $F$ is monotonic.
I can't find any intuition for reasoning about the greatest fixpoint of this function. My naïve assumption is simply that the greatest fixpoint would be the set of all infinite lists, but I think I'm missing a really crucial idea here, and I can't tie it down in my understanding. If anybody could provide some information or input on this, I would really appreciate it!

The greatest fixed point cannot contain only the infinite lists, because it must contain all the elements of the least fixed point (and every other fixed point). Another way to see this is that just the infinite lists are not even a fixed point, since applying $F$ will add $\mathrm{Nil}$, which is not infinite.
However, adding the infinite lists is the right thing to do. I'm not familiar with the book you're reading at all, so I don't know exactly how this would be realized in its setting. For instance, I don't know what $\mathrm{Cons}$ and $\mathrm{Nil}$ are intended to be exactly as operations on $\mathcal{U}$ (or what $\mathcal U$ consists of). But the idea would likely be that $\mathcal U$ has both finite and infinite things built completely out of them, the least fixed point collects just the finite ones, and the greatest fixed point collects all of them.


Single Input Single Output Sequential Circuit Explanation Required I'm a student of Formal Methods in Software Engineering, I'm trying to study this question for two days but still haven't figured it out, I couldn't even find a similar solution or explanation, so please if anyone can explain in detail the question and it's solution I've provided in the image, it'll be a real help. One last thing, my guess is that the solution provided in the image is not correct, or maybe its my logic that isn't, so please help me with this. Thank You.

Create a FSA that falls on the same state at the end of a 100 sequence.
Create a second independent FSA that falls on the same state upon the end of 011 sequence.
Now feed a zero to both FSAs at the same time and take note of the pair of states reached. Now go back and feed a 1 and take note of the pair of states reached, and so on. You will end up with a new FSA made up of pairs of states belonging to the Cartesian product of the set of states of the first and second FSA.
The output at the transition between two pairs of states is the logical OR of the outputs of the original FSAs.

In fact, you can also build a non deterministic FSA that does the job then turn it into a FSA.

Another solution is to create a set of states representing the last one or two inputs, namely 0, 1, 00, 01, 10, 11 in addition to a start state. The transitions are obvious. 1 is emitted when transitioning from 01 to 11 or from 10 to 00. In fact state 11 can be merged with state 1 and state 00 can be merged with state 0. That leaves us with a total of 5 states that should do the job. I assume here that the outputs are emitted upon transitioning. Assuming the output is emitted upon entering a state, then states made of the last 3 inputs need to be made. Similarly, some states can be merged.


defining lambda expressions I am studying for my exam and I wanted to do some extra excercises, but I have some problems with solving :) Can anyone please help or give me some advice where to start? Thank you!

We can represent every list of lambda expressions $x_0, x_1, ..., x_k$ with lambda expression $[x_0, x_1, ..., x_k]$ , defined as:
$[x_0, x_1, ... , x_k] = \lambda c n. c \, x_0 \, (c \, x_1 \, (... (c \, x_k \, n) ...))$

Define lambda expression s, satisfying the equation  $s([\underline{n_0}, ..., \underline{n_k}]) = \underline{n_0 + ... + n_k}$ , where  $\underline{n}$ is a Church numeral, representing natural number $n$.

Define lambda expression $r$ , satisfying the equation  $r([x_0, ..., x_k]) = [x_k,  ..., x_0]$ .

Define lambda expression $h$ and $t$ , satisfying the equation  $h([x_0, ..., x_k]) = x_0 in t([x_0, x_1, ..., x_k]) = [x_1, ..., x_k]$ .

Hint: This way lists are represented as folds. So if you have a lambda term representing a list, you just supply a folding function and a value to start with and the result will be the folded value.


Concise way to say "increases with n or some term of n" I'm writing a thesis proposal and one of the systems involved has unknown complexity. It's not a focus of the proposal, but I wanted to include a line like this, as speculation:

  Presumably the complexity of each new connection scales with the number of rules.

Unfortunately I don't know if asymptotic complexity (space and time) will be O($\log{n}$), O($n$), O($n\log{n}$) or even O($n^{99}$). But I do doubt that it will be constant, so increasing $n$ will have some effect on it.

What is a good, accurate way to write this concisely? I'm asking here and not at English Language and Usage because the CS accuracy is essential.

"Presumably the complexity of each new connection is an increasing function of the number of rules."

But you don't mean complexity. Problems have complexity, algorithms have running time (or, more generally, resource usage), functions have growth rate.


Can Earley parser work in parallel? Since Earley parser finds all possible application variants for a token, can it parse text in parallel, unlike the usual parser like stack-based, etc.
You just need to modify the start of each parallel chunk of tokens, then while going backwards while constructing a table you combine and validate the found rules like in standart Earley approach. But since vector operations are done there, it is possible to parallel this too. And splitting on tokens also. So its (theoretically, i haven't see project like that)  GPGPU support for Earley parsing.

Yes, Earley's algorithm can be parallelized, but not in the way that you are thinking.
Earley's Algorithm In Particular
You ask about Earley's algorithm specifically. Parallelizing the algorithm in the way you suggest is unlikely to be faster. Researchers Peter Ahrens, John Feser, and Robin Hui report:

We first tried to naively parallelize the Earley algorithm by processing the Earley items in each Earley set in parallel. We found that this approach does not produce any speedup, because the dependencies between Earley items force much of the work to be performed sequentially.

The reason Earley's algorithm in particular is difficult to parallelize is because of interdependencies within the computation. To answer how successfully Earley's algorithm parallelizes, we need to solve this  demarcation problem: What should be call Earley's algorithm? Seth Fowler and Joshua Paul explain:

There  are  several  published  algorithms  (see,  for  example, Hill and Wayne[6]) for parallelizing a variant of the  the  Earley  algorithm,  the  CYK  algorithm.   Unfortunately,  in  practice  CYK  has  a  much  longer  running time than Earley (even though it has the same worst-case complexity of $O(n^3)$), and so it is not typically used.

Most researcher's agree that there are few successful parallelizations of the algorithm, however. Fowler and Paul continue:

For  the  Earley  algorithm  itself,  there  are  very  few parallelization  methods  published  (though  there  are many  optimizations—see,  for  example,  Aycock  and Horspool [1]).   One  such  method  by  Chiang  and  Fu [3] uses  a  decomposition  similar  to  the  one  we  develop,but goes on develop the algorithm for use on a specialized VLSI. Similarly, Sandstrom[7] develops an algorithm based on a similar decomposition....

Nonetheless, there are parallel versions. Peter Ahrens, John Feser, and Robin Hui who we cited earlier present "the LATE algorithm, which uses additional data structures to maintain information about the state of the parse so that work items may be processed in any order. This property allows the LATE algorithm to be sped up using task parallelism." The researchers claim a "120x speedup over the Earley algorithm on a natural language task."
Parallel parsing in general - usually impractical
Parallel parsing techniques have been studied for decades.  Other parsing algorithms are more amenable to parallelization, such as the CYK algorithm mentioned above. But parallelizing parsing is only rarely a practical strategy. Most parsing tasks you are likely to encounter are much more efficiently performed serially, that is, in the old fashioned single-threaded way.
The reason parallel parsing algorithms are generally impractical is because parallelism has a lot of overhead that needs to be recouped by the gain in speed, while most parsing tasks can be performed incredibly quickly. (See parallel slowdown.) Quoting from Parsing Techniques: A Practical Guide, by Dick Grune and Ceriel J. H. Jacobs:

From a practical point of view, parallel parsing is interesting only for problems big enough to require considerably more time than a fraction of a second on a single processor. There are three ways in which a parsing problem can be this big: the input is very long (millions of tokens); the grammar is very large (millions of rules); or there are millions of inputs to be parsed. The last problem can be solved trivially by distributing the inputs over multiple processors, where each processor processes a different input and runs an ordinary, sequential, parser. Examples of very long inputs requiring parsing are hard to find. All very long parsable sequences occurring in practice are likely to be regular: generating very long CF sequences would require a place to store the nesting information during sentence generation. ...
The situation is different for parsing with very large grammars. These are found most often in linguistics. They are especially bothersome there since most linguistic applications require general CF parsing techniques, the speed of which depends on the grammar size.

References
Seth Fowler and Joshua Paul. "Parallel Parsing: The Earley and Packrat Algorithms." (2009). Note that this is a student project report for an undergraduate course.
Peter Ahrens and John Feser and Robin Hui. "LATE Ain’T Earley: A Faster Parallel Earley Parser." (2018) The arXiv, 1807.05642.
Grune D., Jacobs C.J.H. (2008) Parallel Parsing. Parsing Techniques. Monographs in Computer Science. Springer, New York, NY.


Given n sets of points in the plane find the shortest path which passes from exactly one point from each set I am trying to find an algorithm for this. You can imagine each set $(S_1, S_2, \ldots, S_n)$ as points with different colour. Also it isn't necessarily $|S_1|=|S_2|=\cdots=|S_n|$.

For $n=1$ we trivially have a single (random) point.

For $n=2$ we have two sets of points $S, Q$ and we seek to find the (distance of the) closest pair of points $p, q$ such that $p\in S$ and $q \in Q$. I have also found an efficient algorithm for this, using voronoi diagrams.

For $n>2$ things get tricky. I have no clue where should I head to.  Let's say we have $x$ red, $y$ green and $z$ blue points laid down in an Euclidian plane. How do we find the minimum distance of a route passing for one red, one green and one blue point?

Is this some special case of the Traveling Purchaser Problem?

This problem is a generalization of TSP known as Set TSP. Not surprisingly, it is both NP-complete and well-studied.


functional programming in terms of Set I'm writing some notes about functional programming, so I'd want to describe some features of the category theory.

I visited wiki page about Category of Set, and I found this:

"The epimorphisms in Set are the surjective maps, the monomorphisms are the injective maps, and the isomorphisms are the bijective maps".

I'd want to explain Category theory it in term of computer science, so my question is:

It's correct to consider only the category of Set?
It's correct to consider only the category of Set when I explain functional
programming in term of Monoid/Functor/Algebraic Data/Product type and so
on?

I know that Category theory is not only Set, but It's important for me define a boundary where all my examples are correct on assumptions and definitions.

thanks
Mike.

You can use the category of sets as your model of how functional programming works as long as you do not allow general recursive definitions.

To see why general recursion is not valid in the category of sets, consider the following program (written in Haskell):

fix :: (Bool -> Bool) -> Bool
fix f = f (fix f)

If we interpret Bool as any set $B$ with at least two elements (for instance $B = \{0, 1, \bot\}$) then there will be a map $f : B \to B$ which does not have a fixed point (for instance $f(0) = 1$, $f(1) = \bot$, $f(\bot) = 0$). However, fix always computes fixed points.

You can use sets as long as all the recursive definitions are well-founded, i.e., the recursive calls always happen on strictly smaller arguments. Typical fold and map operations on lists and other inductively defined structures are like that.

To model recursion one has to change something. One possibility is to use domains which were invented precisely for this purpose.


CFG for words that are not a concatenation of the same word I am teaching myself formal languages, and yesterday i got stuck at an exercise asking for a context free grammar for the language:

$ L = \{x  \in  \Sigma ^{+} | \ \forall w \in \Sigma ^{+} \ x \neq ww\} $ with $ \Sigma = \{a,b\}$

I am trying some rules of the form

$L \Rightarrow a | b $

$S \Rightarrow aSbS\ |\ bSaS\ |\ L\ |\ ab\ |\ ba $

However this is wrong since for example the grammar does not accept 3-symbol strings.
I am a little bit stuck with it so any help would be greatly appreciated.

The question has been asked before, but since it's faster to describe the answer than to find the previous question, I'll outline the answer here.

We can characterize words in $L$ as belonging to one of two classes:

Words of odd length.
Words $z_1 \ldots z_n w_1 \ldots w_n$ where $z_i \neq w_i$ for some $i$.

It is easy to generate words of the first type. As for words of the second type, for fixed $i$ and $n$ we can generate them using rules of the form $\Sigma^{i-1} a \Sigma^{n-i} \Sigma^{i-1} b \Sigma^{n-i} = \Sigma^{i-1} a \Sigma^{i-1} \Sigma^{n-i} b \Sigma^{n-i}$ and its counterpart with $a,b$ replaced by $b,a$. I'll let you figure out how to generate all of these words (for all $i,n$).


How do I continue learning programming, beyond the basics? DISCLAIMER: I understand that I might not be posting in the right part of StackExchange, or this question might have been asked before (I haven't found it). If this offends anybody, I apologize.

I'm 15 and a sophomore in High School. I have an interest in Computer Science in general. The thing is, I've learned a few languages here and there, but I just don't know how to keep learning on a regular basis. What I mean by this is that yeah, I can make a calculator with java, or some really basic scripts with python, but the fact of the matter is that I don't know what to do after that. Making a script that can count the words in a book seems so pointless.

What can I do to learn a programming language, practice it, and have an overall mastery of it? Anybody can learn how to do basic things like I've done, but what can I do so that at the end of some time, I can look back and say "yeah, I'm a real programmer now." I know that sounds cheesy, but help me out here.

If you're looking for some hands-on programming experience that also allows you freedom to do what you want, why not join an open source project? One such project is the Sage Math project

http://www.sagemath.org/development.html

It basically is an open-source project that develops a Python-like language for coding math. It has some cool features, especially in algebra and graphs, but also suffers from many bugs. Of course, there are many other open source projects you could find.

This would help you on many levels

Learn at your own pace
Work on anything that you like (provided that it is math related)
It will give you hands on experience at code development, committing, bug reporting and tracking. Basically anything and everything that you'll ever need to become a full-on programmer. Many people who work on such projects are top notch experts in their fields, so this could be a real opportunity.
You are contributing to society!

Alternatively, you could also take some online coding tasks (http://www.topcoder.com/) and even get paid for them. However, if your coding knowledge is not too great, this may not be the ideal place to start.

Good luck!


Is there a relation between the size of the domain/range of a function and its computability? This was a question given in a course, without answer. The referenced literature (just a few books) do not cover it, unfortunately.

I think there is no relation with the range as the range of the Halting problem is {0,1} and the range of the successor function is infinite. But I feel like I'm missing some subtleties here.

(Note: As mentioned by Apass.Jack in the comments, there are apparently two different usages of the terms "domain" and "range". In this answer, I adopt the usages which I am more familiar with. That is, given a function $f\colon X \to Y$ (i.e., $f \subseteq X \times Y$), $X$ is the domain of $f$ in the sense that $f(x)$ is defined for all $x \in X$; similarly, the range (or codomain) $Y$ is a set such that $f(x) \in Y$ for all $x \in X$. Additionally, every function is total; partial functions are explicitly denoted as such.)

Let $f\colon X \to Y$ be a function. The question is: What can we say about the computability of $f$ (strictly) based on $|X|$ and $|Y|$? The following is more or less a structured breakdown of what I have written in the comments:

Domain

Case 1: $|X|$ is finite. Then the values $f(x)$ of $x \in X$ may be hardcoded (e.g., as a lookup table) in an algorithm to compute $f$.
Case 2: $|X|$ is infinite. There are plenty of both computable and uncomputable functions in this case.

Range

If $Y$ is such that the image $\text{im}(f) = \{ f(x) \mid x \in X \}$ of $f$ is a proper subset of $Y$, then there is not much that can be said about $f$ (e.g., $Y$ could be an infinite set but $f = \{ \}$ the empty function; see Case 1 below). Thus, let us assume $\text{im}(f) = Y$ holds.

Case 1: $|Y| = 0$. Then $f$ must be the empty function $\{ \}$, which indicates $|X| = 0$; see "Domain", Case 1.
Case 2: $|Y| = 1$. $f$ is computable by an algorithm which ignores its input and outputs the only possible value for $f$.
Case 3: $|Y| \ge 2$ but $|Y|$ finite. An example of an uncomputable $f$ is, for instance, the membership relation for the halting problem (as mentioned in the question) or any non-recursive (i.e., undecidable) language; similarly, a computable $f$ would be the membership relation for a recursive (i.e., decidable) language.
Case 4: $|Y|$ infinite. As in case 3, there are both computable and uncomputable choices for $f$. For example, $X = Y$ and $f = \text{Id}_X$ is trivially computable. An uncomputable example for $f$ (off the top of my head) would be the busy beaver function.

It is possible to extend these results if further assumptions are made about $X$, $Y$, and $f$. In the general case, however, this is as much (and it is not much, I know) we can say about the computability of $f$.

If we are dealing with a partial function $f \subseteq X \times Y$ instead, note there is always a (maximal) $X' \subseteq X$ such that $f \subseteq X' \times Y$ is a (total) function $X' \to Y$. As pointed out by chi in the comments, it might be tempting to say we may simply generalize the above discussion by considering the total restriction of $f$ instead. This does not work, however, since, for example, the partial function $f \subseteq \mathbb{N}_0 \times \{ 1 \}$ with $f(x) = 1$ if and only if TM number $x$ does not halt is not computable, despite its image having a single element (cnf. "Range", Case 2). Nevertheless, note this is the only case in which the generalization fails.


Given the "programs as proofs" isomorphism, how do we know that the program isn't lying? I've been studying constructive type theory (CTT) and one of the things that I'm not clear on is  the proof part: Proving the correctness of a program in a form of a proof that's nothing but the program itself (Curry-Howard Correspondence)

Most examples that I've seen in books (e.g., Type Theory and Functional Programming - Thomson and TaPL) show the "proofs" on $\lambda$-abstractions and applications on terms (i.e., literally $a, b, e...$). The proofs seem to mostly rely on the type signatures of the functions, under the assumption that the function does what it claims. Not much is discussed about the "how" of the function's correctness.

For example, when writing a real program (e.g., in Haskell and other [pure] functional languages), the function under consideration could do any arbitrary computation and return a term of the correct type for the proof to go through (statically speaking). So how do we know that the program is computationally doing the "right" thing (dynamically speaking) and not just faking it to get past a proofing system?

From what I understand, here's how things should go (and probably are, but I'm not sure if I'm right), crudely speaking:

Given a program's specification in something like predicate logic we "convert" it into an equivalent "typed representation"
Using backward inference we substitute the "functions" with their appropriate values, which themselves could be other functions (i.e., we replace the functions with their computation rules, but I'm thinking more on the lines of replacing the function with its body, from a programming point of view, for the sake of argument. Assuming that they're "returning" the correct type this seems like a believable substitution)
We continue doing #2 above till we hit primitive operations (again, crudely speaking) which we can trivially prove (or if not, maybe the proof is "simple" enough).
Once we've hit all the "axioms" (or trivial proofs) along all the branches of backward inferences, we stop.
QED

Two questions:

Is my understanding/intuition of "how" the proof of correctness works in CTT works correct? It looks like it won't be possible for the program to "cheat" this or can it?
And secondly, is this what proof assistants like Coq help you prove/analyze (at a high level)?

Proving the correctness of a program in a form of a proof that's nothing but the program itself

This is not quite how the Curry-Howard-Correspondence works.

First one has to show that the language of choice actually corresponds to some consistent logic. Different languages correspond to different logics, and many languages correspond to inconsistent logics which are not good for proving things. Haskell doesn't correspond to a consistent logic, because in Haskell, we can write nonterminating programs which would correspond to infinite proofs. But infinite proofs are invalid, so not every Haskell program corresponds to a valid proof.

Now what does it mean that a language corresponds to a logic? It means that:

a type in the language corresponds to a formula in the logic
a program in the language corresponds to a description of a proof in the logic
a well-typed program in the language corresponds to a description of a valid proof in the logic.
a program of a specific type in the language corresponds to a proof of a specific formula in the logic
a value in the language correspond to truth in the logic
evaluation of programs to values corresponds to soundness of the proving rules
reification of values to programs corresponds to completeness of the proving rules
...

No need to understand all aspects of the correspondence at once, but it is good to keep in mind that the correspondence relates not just programs and proofs, but many (all?) aspects of the languages and the logic. For the question here, only the first four aspects are relevant.

A minor issue is that only well-typed programs correspond to valid proofs. That's why type signatures of functions are so relevant to the Curry-Howard-Correspondence.

The key issue is that a well-typed program doesn't correspond to a valid proof of its own correctness, but to a valid proof of whatever formula corresponds to the program's type.

For example, let us consider the following two programs (using Haskell syntax, but assuming a version of Haskell that corresponds to a consistent logic):

f :: a -> a -> a
f x y = x

g :: a -> a -> a
g x y = y

The functions f and g are well-typed programs of the same type, so they correspond to valid proofs of the same formula. The formula is "forall propositions p, p implies that p implies p".

But clearly, f and g are different programs. And of course, they correspond to different proofs of the same formula. The program f corresponds to the proof "We know that p implies p, so also p implies (whatever implies p)". And the program g corresponds to the proof "We know that p implies p, so also whatever implies (p implies p)."

Usually, with programming languages, we care about the difference between programs like f and g, and with logics, we don't care about the difference between the two proofs that correspond to f and g. But when thinking about the Curry-Howard-Correspondence, it is important not to forget that there can be multiple different valid proofs of the same formula.

  So how do we know that the program is computationally doing the "right" thing (dynamically speaking) and not just faking it to get past a proofing system?

We don't. We only know that the program proves the formula we have encoded in the program's type. So how can we use the Curry-Howard-Correspondence to prove a program correct? We have to encode a statement about program correctness into the type of the program. This requires a very expressive type system, of course, which is exactly what the languages inside tools like Coq or Agda provide.


Is the language $0^n 1^n 0^n$ recursive? I have to find out whether the language $J_1=\{0^n1^n0^n \mid n \in \mathbb{N}\}$ and $J^{c}_{1}$ is recursively enumerable.

I already know that $J_1$ is RE, because I have found Turing machine which accepts $J_1$.
I would also like to prove this for  $J^{c}_{1}$ by using the following theorem:
$J\in RE \wedge J^{c} \in RE \Leftrightarrow J \in Rec$.

So I have to prove that $J_1 \in Rec$. I have already tried but I am stuck. Can anybody please help me?

Explaining intuitively why this language is recursive is easy: it's almost trivial to write a computer program in a high-level programming language (e.g. Java, C) that decides this language. Since TMs can simulate high-level languages, you get the result.

If you need a concrete TM that decides this language, try the following:

First, erase a 0 and go right until you encounter 1. Replace this 1 with some new symbol $X$.
Go back left, and repeat the process until you are out of 0s on the left.
Then go back right and do the same thing with the $X$s and 0s on the right.

If, at any point, something "unexpected" happens, (e.g. you run out of 1s, or have too many 1s), then reject. Otherwise you will end up with an empty tape, at which point you can accept.


Sort an array in specific bounds Given an array with size of $n$ and except from $\sqrt{n}$ ( lower value ) elements in the array, all of the other elements are integers between the bounds of [$\sqrt{n}$, $n$$\sqrt{n}$]
I will need to write an algorithm that sorts that array in $\Theta$($n$)
Furthermore, will the same mission could be performed if, now it is given that except from $n/2$ ( lower value ) elements in the array, all of the other elements are integers between the bounds of [$\sqrt{n}$, $n$$\sqrt{n}$]
And how about $n/log(n)$ ( lower value )?
( In this time thare are ( $n$ - $n/log(n)$ ) ( lower value ) integers in the given bounds )
Note - We can not know where are the the integers located in the array

MY METHOD: For the first question I tried to seperate the array to 2 arrays, and then for the array with the numbers inside the bounds of
[$\sqrt{n}$, $n$$\sqrt{n}$] - I have converted the elements to $n$
based and sorted it with counting-sort. For the second array - sort it
with any other sorting method and then merge the 2 arrays

My questions are:

Does my approach is correct to the first question ( in terms of run-time, algorithm )?
What would be the best solution for the other question asked

I am not sure counting sort would work, since it does not depend on the base, but on the range of the sorted values. In this case, you would need to create an array of size $(n-1)\sqrt{n}$ to count, so you would be in $\Omega(n^{3/2})$. As suggested in the comment, radix sort may do the trick here.

It is not possible to sort in $O(n)$ for one of the other bounds. Indeed, the problematic part would be sorting values not in the bounds $[\sqrt{n}, n\sqrt{n}]$: sorting $\frac{n}{2}$ values requires $\Omega(n\log n)$ time.
On the other hand, sorting $\frac{n}{\log n}$ values can be done in $O\left(\frac{n}{\log n}\log\left(\frac{n}{\log n}\right)\right) = O(n)$ time.


Why is one often requiring space constructibility in Savitch's theorem? When Savitch's famous theorem is stated, one often sees the requirement that $S(n)$ be space constructible (interestingly, it is omitted in Wikipedia). My simple question is: Why do we need this? I understand the requirement for $S(n)$ being in $\Omega(\log n)$, which is clear from the proof. But no proof I have seen so far explicitly uses that $S(n)$ is space constructable.

My explanation: in order to call the procedure REACH (or PATH or whatever you like to call it), the last parameter needs to be "spelled out", and in order not to leave our space bounds of S(n) for one call, we must not need more than $S(n)$ space to write it down.

This is elaborated nicely in Dexter Kozen's Theory of Computation textbook, in chapter 2.

Savitch's Theorem (Theorem 1 in his paper) says: if $S(n) \ge \log n$, then $\text{NSPACE}(S(n)) \subseteq \text{DSPACE}(S(n)^2)$.  Space-constructibility often seems to be assumed in a proof, but this requirement can be removed by restarting the search with a fixed space bound that is allowed to increase with each attempt.

The confusion perhaps arises because the original Savitch paper is largely about investigating whether $\text{NSPACE}(S(n)) \not\subseteq \text{DSPACE}(S(n))$.  It therefore spends a lot of effort on space-constructible functions, due to the following observation from the paper:

  It is natural to ask if there is any storage function whose deterministic and nondeterministic complexity classes are equal. The answer was given by Manuel Blum and is "yes". Blum showed that there are arbitrarily large storage functions L(n) such that a set is accepted within deterministic storage L(n) if, and only if, it is accepted
  within nondeterministic storage L(n). These functions L(n) are not, however, "well-behaved" and Theorem 3 does not apply to them.

(Here "well-behaved" refers to the space-constructible functions, called measurable by Savitch.)


How to explain the steps in the implementation of hashing functions like SHA1 I was reading the article about the SHA1 hashing function (I know it is not secure anymore) and I've found a pseudocode implementation on Wikipedia.

I can see that there are a lot of mathematical operations, and what I wanted to know is the justification of each step in this hashing function. I want to know, for example, how each part increases the security of the function. How do we know that these operations are gonna produce a drastic change in the output when a minimum change is made in the input?

Is there a book about the theory behind hashing function? Maybe a book that explains mathematical functions or operations that maps the input to a very large output space such that is very hard to do the inverse way.

Is there a very simple hashing function that can be studied and that are examples of attacks? Is there some paper that explains the evolution of these functions and the justification for some math operations in this?

I recommend you spend some time with some crypto textbooks, in particular the Handbook of Applied Cryptography and Antoine Joux's Algorithmic Cryptanalysis.  They explain some of the details of hash functions.  You might also try reading some of the questions on Crypto.SE; there's a lot written there.

In addition, do some self-study about unbalanced Feistel networks.  They are part of the core of SHA1.  You can find information about them on Wikipedia and in the cryptographic literature.

You might also like to read the submissions to the SHA3 competition.  Every one came with a detailed technical document that explains the design criteria and security analysis of the hash function.


How do I find the number of inversions using a red black tree? I'm trying to figure out a way to find the number of inversions in permutation time O(nlogn) using red black trees. Here's how I think it can be done. So if I have an algorithm that inserts a new node into a red black tree then by inserting the node if it inserts properly then it means the values are in the proper order and there's no inversions. If a value is inserted and the order property is not satisfied then we need to either rotate the tree or change the color of the branches to satisfy the order property. So I have an insert method that looks like this:

private Node put(Node h, Key key, Value val){
        if(h==null)
            return new Node(key, val, 1, RED);
        int cmp = key.compareTo(h.key);
        if (cmp < 0) h.left = put(h.left, key, val);
        else if (cmp > 0) h.right = put(h.right, key, val);
        else h.val = val;

        if (isRed(h.right) && !isRed(h.left))
            h = rotateLeft(h);

        if (isRed(h.left) && isRed(h.left.left))
            h = rotateRight(h);

        if (isRed(h.left) && isRed(h.right))
            flipColors(h);

        h.N = size(h.left) + size(h.right) + 1;
        return h;
    }

Now if I declared a variable that kept count of all the inversions then at what points would I need to put it at and is there any code that is unnecessary when counting the inversions? What I'm thinking of doing is replacing all the rotations and color changes with inversion incrementing. Would doing that still give me the right number of inversions in O(nlogn) time?

What you are trying to do is correct. However only number of rotations will not be able to tell you anything about the inversions. The whole procedure is as follows.

You start with an empty red-black tree. Then you insert the elements in the given sequence one by one, in the order that they occur in the sequence.

Whenever an element $x$ in the sequence is inserted, the elements larger than $x$ already existing in the red-black tree are inversions. You need to calculate this number.

You total up all the inversions for all elements and you get the total number of inversions.

You need to augment the red-black tree by keeping the size of sub-trees in the interior nodes. Then you can find the number of elements larger than $x$ either during insertion or after insertions by doing a search of element $x$.

Since you are confused about the strategy, I suggest you should use the second method. Don't count the larger elements during the insertion stage. Count them immediately after the insertion is done and before another insertion is to be done (in a separate function). This will take additional  $O(\log n)$ on the augmented tree.

If all your numbers are distinct then this algorithm suffices. However, if some numbers are same, then you have to modify your insertion to insert only at the rightmost possible position and/or counting only the strictly larger elements depending on your algorithm. You will need to further augment the data structure to hold the min-value and max-value of the sub-tree in the node.


Meaning of the notation Typ := TVar | (Typ → Typ) In the paper "introduction to type theory" by Herman Geuvers, it states the following definition for the type theory of propositional logic (I've added "convention 2" just for reference):

Given that this is an introduction, I'd assume that he would explain the meaning of a statement like $\mathrm {Typ}:=\mathrm {TVar}|(\mathrm {Typ}\to \mathrm {Typ})$, or what a "type variable" is.

My question is twofold:

What do these two things mean?
What background knowledge is this introduction assuming, that I would need to study before reading this "introductory" text?

Intuitively, a type variable is like a variable in an expression, except that it stands in for a type rather than standing in for a number/bitstring/etc.

Formally, we choose a countably infinite set $\mathsf{TVar}$, and then define a type variable to be a member of $\mathsf{TVar}$.

The notation $\mathsf{Typ}:=\mathsf{TVar}|(\mathsf{Typ}\to \mathsf{Typ})$ is an instance of Backus normal form.  It is an inductive definition of $\mathsf{Typ}$.  It says that if $\alpha$ is a type variable (i.e., if $\alpha \in \mathsf{TVar}$), then $\alpha$ is an element of $\mathsf{Typ}$; and if $\alpha,\beta$ are type variables (i.e., $\alpha,\beta \in \mathsf{TVar}$), then the term $\alpha \to \beta$ is an element of $\mathsf{Typ}$.  $\mathsf{Typ}$ is the set of terms that can be constructed in this way.  We call a term a type if it is an element of $\mathsf{Typ}$.


2-clause satisfiability associated graph A 2-clause is a clause with at most two propositions (clauses?) : $(p \wedge q,\neg p \wedge q, \neg p,...)$. I have to show that the folllowing problem is $\in$ P:

2-SAT:
Input : A conjunction $\Phi$ of 2-clauses.
Question : Is it satisfisable?

For each set of 2-clause $C$ we associate  $G_C$ defined as

$V_{G_C}$ contains two vertices $x$ and $\neg x$ for each variables in $C$.
$E_{G_C}$ contains an edge $\alpha \rightarrow \beta$ if and only if $\neg \alpha \vee\beta$ or $\beta \vee\neg\alpha$ is in $C$.

This graph should help me show this problem belongs to P. Yet,

Why is $C$ satisfiable if and only if $G_C$ doesn't have any loop?
Why does $G_C$ space is polynomial?
Why is $G_C$ calculation from $C$ is polynomial?

You already have a description of how the graph is built from the formula. Think about a possible algorithm for doing the job. For example, you first scan over all variables in the formula, and you add two vertices into your graph for each. Now you only need to add in the edges into the graph. You can scan over the clauses, and if you see either form you describe, you add in an edge into your graph. This all can be implemented to run in polynomial time; just observe you are performing two scans over the formula, and you do a bit of work for every step of the scan. Similar reasoning will make you see the graph only needs polynomial space.

For your first question, an answer is given in the Wikipedia article on 2-SAT, but has also been touched upon in other question (see e.g., here).


Merging of two convex polygon chains in O(log n) Assume I have a polygon chain implementation which is backed by a key-value store which stores the position of a point inside the chain as key and the point itself as value. So a polygon chain of the points $p_1\rightarrow p_2\rightarrow p_3$ is stored as $\{0\Rightarrow p_1,1\Rightarrow p_2,2\Rightarrow p_3\}$. The key-value store is implemented with a data structure which allows the operations split and join in $O(\log n)$ time.

I want to join the chain $P = p_1\rightarrow p_2\rightarrow p_3$ and the chain $Q = q_1->q_2->q_3$ to a chain $p_1\rightarrow p_2\rightarrow p_3\rightarrow q_1\rightarrow q_2\rightarrow q_3$.

Is there a way to join two polygon chains in logarithmic time without updating the keys? If I do a simple join, I get a problem with duplicated keys, so the keys of $Q$ have to be updated before the join, but this destroys my logarithmic time approach as I need linear time for updating the keys.

Am I wrong here already?

If not, is there a way to keep the logarithmic time?

You are asking for a data structure for sequences (aka vectors or arrays) that permits efficient concatenation.  I suggest using any standard binary tree data structure, e.g., AVL tree, red-black tree, splay tree, treap, etc.  They support $O(\lg n)$ time concatenation and $O(\lg n)$ time lookups.  The differences between them come down to details related to implementation complexity and constant-factor differences in running time.

With these algorithms, the keys are not stored explicitly.  Instead, they are implicit.  To lookup key $i$, you search for the $i$th leaf from the left, but the key $i$ is never stored anywhere.  Thus, when concatenating two trees, there is no need to renumber the keys.  You can find the $i$th leaf in $O(\lg n)$ time: augment the data structure so that each node keeps a count of the number of leafs underneath it; then it's clear how to traverse the tree during a lookup (whether to go left or right at each node is an easy decision, given the information  stored in each node).


Minimal hypergraph transversals the exact complexity for hypergraph transversal problem is yet unknown and is an open research problem.

However, I would need a fast way to compute, on paper, the minimal transversal of a hypergraph. A transversal intersects all hyperedges of the graph.

A transversal is minimal if it does not contain any transversal as a proper subset.

Let us look at this example, where V = {a,b,c,d,e}

Hyperedge 1: de
Hyperedge 2: abce
Hyperedge 3: bd

How can I compute, on paper, the minimal transversal of this hypergraph? Computing the minimal transversal with only 2 hyperedges is trivial, but in the 3 hyperedges case, the complexity increases.

Looking forward to your input.

The problem is NP-hard by a reduction from hitting set. Thus, there is no efficient or "easy" algorithm in this sense. Of course, any algorithm you might execute with pen and paper can also be realized on a computer.

With that being said, just try all possibilities by hand. As you observe, it is easy to see if the solution is of size one or two. It can get much more tedious after that, and the reason is NP-hardness.


Successor of 6 is 7 or 9? What is the successor of 6 in this tree: 7 or 9?

There are many ways to traverse a tree, and what is the 'successor' of 6 depends entirely on how you are traversing the tree. To illustrate this, here's the answer for some common traversal methods:

Pre-order traversal: 3.
In-order traversal: 9.
Post-order traversal: 17.
Level-order left-to-right: 18.
Lever-order right-to-left: 20.

And for completeness, you can get 7 as a successor of 6 through reverse pre-order.


How to determine the pre and post conditions of a program (Hoare-logic) Problem
Below is a program named X:
y = 1;
while(y < x){
    y = 10 * y;
}

What does this program X do? What are appropriate pre and post conditions?
 (Assume that x and y are integers).

My solution
Given a whole number x > 1, X should give us a power of 10 greater than or equal to x.
pre-condition: (|x = x0 ∧ x0 > 1|)
post-condition: (|y ≥ x ∧ ∃n(y=10n)|)
However, I don't know if my solution is correct. It would be nice to know how to solve this trivial problem.

Here are two other programs that have the same postcondition given the same precondition:
y = 1;
while (y < x) {
    y = 100 * y;
}

x = y = 1;

Your postcondition doesn't describe the output it enough detail. In particular:

The program doesn't change $x$.
The value of $y$ is the smallest power of 10 which is at least $x$.


Consutrcting a transition diagram of a deterministic Turing machine I'm having some issues constructing a transition diagram of a deterministic Turing machine for $L = \{0^i1^j2^j3^k \ | \ i = j + k\}$

The point where I get stuck is how I should make sure that $i = j + k$

My thoughts:

My thought was to initially do something similar to do something including an addition turing machine where I check that the final tape is of the structure generated by the language i.e we should have 2 $0$s, 1 $1$, 1 $2$ and 3 $1$s = 6 and if it is correct then we'd go through checking if $0$s come before $1$s, $2$s before $1$s and $3$s before $2$s.

I think this is a really complicated way to do it, and that's why I'm asking.

Question: Construct a transition diagram of a deterministic Turing machine for $L = \{0^i1^j2^j3^k \ | \ i = j + k\}$. What I'm asking is for some guidance.

Thanks in advance!

This is meant to give you a hint, but if you are lost, you could think about doing it in three large steps:

Make a single pass through, making sure that you encounter $0$s followed by $1$s followed by $2$s followed by $3$s.  You should think through the end conditions if this process goes smoothly, or what items you might encounter on the tape that could send you to a reject state.
Now check that there are the same number of $1$s and $2$s: go back and find the start of the $1$s.  For every $1$, replace it with an $i$, run off to the right and find a corresponding $2$ (which you must also replace with some symbol, such as $T$).  Again, think through the end conditions, and how you will know if something unexpected has happened.
Finally, check if $i=j+k$.  Run to the beginning of the $0$s, and for every $0$ you replacing (with, say, $o$), run off and find the next $T$ or $3$ and replace that with some other symbol ($F$?).  At the end, a pass left will be sufficient to tell you that there are no more $0$s, and a pass right will be sufficient to tell you that there are no remaining $T$s or $3$s.


Sorting array of strings (with repetitions) according to a given ordering We get two arrays:

ordering = ["one", "two", "three"]

and

input = ["zero", "one", "two", "two", "three", "three", "three", "four"];

We want to find the array output so that

output = ["one", "two", "two", "three", "three", "three", "zero", "four"]
// or
output = ["one", "two", "two", "three", "three", "three", "four", "zero"]

The strings (with possible repetitions) should be sorted as in the ordering array. Not found/contained strings should be put at the end of the new array and their order doesn't matter.

The $n^{2}$ solution is obvious, can we do better? The memory doesn't matter and it doesn't have to be an in-place algorithm.

The other answers provide correct solutions. However, you can do a bit better considering multivariate complexity. Note that the provided running times in the other answers are not quite specific since they ignore either the size of the first array or the lengths of the strings.

Here are 2 different methods with their specific running times. The first of which is a brief description of the method in the other answers with specific analysis of the running time. The second of which has better running time and is almost optimal.

Let us call the first (ordered) list in the input $A$ and the second (to be ordered) $S$. Let $n$ be the size of $A$ and $m$ the size of $S$. Let $l$ be the maximum length of a string in the input.

The first method.
This span the methods in the other answers. Note that in both we need to find for each string the whether it lays in the original ordered array and if so at what position exactly. We need either apply a linear search which will cost something like $O(ml)$ per element or we can build some kind of a dictionary data-structure such as search trees and hashing tables or a "trie" (prefix-tree) data structure to achieve each look-up operation in linear time in the size of the strings. Using this we can achieve a running time of $O((m+n)l)$ for finding the positions over all strings. Afterwards we need to sort all strings in $O(n \log n)$ if we assign the indices directly to the strings (using pairs) or $O(l n \log n)$ by applying the look-ups while searching. So the best running time we can achieve using the methods in the other answers would be $O(l (n+m) + n \log n)$.

The second method. Note that we did not make use of the original sorted array and that is why we had to sort the strings again. We can solve the problem more efficiently by using this extra informaiton. To achieve this, let us bild a dictionary $D$ (for the sake of the theoretical bounds let us define it as a trie but in you can implement it as a hash-table as well). Let us define a new list $L$ (a linked list) and a function $C$ that counts how many times each string appeared in the first array. Assume $D$ assigns to each string a distinct number from $1$ to $m$ and $C$ is an array of length $m$.
The algorithm goes as follow:

For all i in {1, .., m}
 Set C[i] := 0
// Now build D
Set index := 0
For each string s in A do
 Set D[s] = index
 Increase index by one
// Now find how many times each string occurs
Let L be an empty list
For each string s in S do
 If s in D then
  Find index = D[s]
  Increase C[index] by one
 Else
  Append s to L
//Now output
For each string s in S do
 Find index := D[s]
 Find c := C[index]
 while c > 0
  output s
  decrease c by one
For s in L
 output s

This algorithm runs in $O(l(n+m)$ which is linear (optimal) if the lengths of the strings are bounded by a constant.


When is a first-order formula is existential and when is it universal? So I have a few questions about determining which formula it is:

So if a binary predicate symbol $X$ denotes an edge between two variables, say $x$ and $y$, for the following formulas

Why is $\forall x \exists y\,(X[xy]\lor X[yx])$ universal and $\exists x \forall y\,(X[xy]\lor X[yx])$ existential? I mean for the second formula all $y$ are within the scope of $\forall y$, so shouldn't it be universal as well?
And if you have a formula like this: $(\exists x X[xy]) \odot X[yx]$,
where $\odot$ denotes an arbitrary binary connective, would this be a binary connective formula or an existential formula?

Thanks.

The key to the usage is to transform the formula to an equivalent formula that is in prenex form.

A formula $F$ is in prenex form if $F \equiv Q_1 x_1 ...Q_m x_m\; G$ where $G$ is a quantifier free formula and $Q_1,...,Q_m$ are quantifiers.

A formula $F$ is universal if it is equivalent to a formula in prenex form that has only universal quantifiers.

There is an important model theoretic property of universal formulas: a universal formula that is satisfiable in some structure $S$ is also satisfiable in any substructure $P$ of $S$.

  Why is $\forall x \exists y(X[xy]∨X[yx])$ universal and $\exists x \forall y(X[xy]∨X[yx])$ existential? I mean for the second formula all $y$ are within the scope of $\forall y$, so shouldn't it be universal as well?

Either sentence is neither universal nor existential. One can easily come up with an example structure where $F\equiv\forall x \exists y(X[xy]∨X[yx])$ is true but is not true for a substructure.

   Let $S=\{0,1\}$ and $X[xy]\equiv x\not=y$, then F is true in $S$ but is not true for any one-element substructure of $S$.

Now for the second question

  And if you have a formula like this: $H\equiv(\exists x X[xy])⊙X[yx]$, where ⊙ denotes an arbitrary binary connective, would this be a binary connective formula or an existential formula?

In order to find the prenex form we rename the variable $x$ in the scope of the existential quantifier to get $H'\equiv(\exists z X[zy])⊙X[yx]$.

Now suppose $⊙$ is disjunction or conjunction then we can consider an equivalent formula $H''\equiv\exists z X[zy]⊙X[yx]$ that is in prenex form and is an existential formula.

However if $⊙$ were an implication then the formula $H$ would be equivalent to $H'''\equiv\forall z X[zy] \Rightarrow X[yx]$. The formula $H'''$ is clearly a universal formula.


Unrecognizability of functional variant of halting problem Let $L_0 = \{ \langle M, w, 0 \rangle \mid M \text{ halts on } w\}$ and $L_1 = \{\langle M, w, 1\rangle \mid M \text{ does not halt on } w\}$.
In $\langle M,w,i \rangle$, the $i$ indicates a specific bit such as $0$ for language $L_0$ and $1$ for language $L_1$.
I want to prove that $L = L_0 \cup L_1$ is unrecognizable and so is $\overline{L}$.
I think: the halting problem $\{\langle M,x \rangle \mid M \text{ halts on input } x \}$ is recognizable, that is, given a machine $M$ and a string $w$, I can always get acceptance if $M$ stops on $w$ by simply running it.
Assume that $L_0$ and $L_1$ are recognizable, that is, there are machines $M_0$ and $M_1$ such that $M_0$ accepts $x \in L_0$ and halts, $M_1$ accepts $x \in L_1$ and halts. Then to recognize $x \in L_0 \cup L_1$, we can have a hypothetical $M_\cup$ that can recognize (not decide) $L_0 \cup L_1$:

we can run $\langle M, w, 0 \rangle \in L_0$ on $M_0$
and $ \langle M, w, 1 \rangle \in L_1$ on $M_1$

So:

If $M_0$ stops we know $M$ halts on $w$ and
if $M_1$ stops we know $M$ does not halt on $w$

(Note that any $x \not \in L_0 \cup L_1$ will lead to divergence on these two machines. That’s why $M_\cup$ can only recognize $L_0 \cup L_1$ and cannot decide.)
Thus we have solved the halting problem: for any $M$ and $w$, $M_\cup$ will accept and halt for both

$M$ halts on $w$
$M$ does not halt on $w$

This is a contradiction (halting problem is undecidable) and so both $M_0$ and $M_1$ cannot exist simultaneously. This proves that $L = L_0 \cup L_1$ is not recognizable.
For the $\overline{L}$ case: $\overline{L} = \overline{L_0} \cap \overline{L_1}$. As stated previously, $L_0$ is recognizable and $L_1$ is not recognizable (“no Turing machine can recognize all Turing machines that never halt”: Corollary 2 here).

$\overline{L_0}$ is not recognizable
$\overline{L_1}$ is recognizable
$\implies \overline{L}$ is not recognizable

Is this a valid chain of arguments for this proof?

A Turing machine $T$ decides the halting problem if on input $\langle M,w \rangle$:

If $M$ halts on $w$, then $T$ halts and outputs "Yes".
If $M$ does not halt on $w$, then $T$ halts and outputs "No".

In order to show that $L$ is not recognizable, you assume that $L$ is recognizable, and use that to construct a Turing machine $T$ which decides the halting problem. This is not quite what you are doing:

You are assuming that $L_0,L_1$ are recognizable, but you don't explain how this follows from $L$ being recognizable.
You don't explain why $M_{\cup}$ always halts. This is only the case if you run $M_0$ and $M_1$ in parallel, and halt whenever one of them halts.
You state that $M_{\cup}$ always accepts and halts whether $M$ halts on $w$ or not. However, such a machine is easy to construct: all you need to do is to immediately halt, without even reading the input. What we need is that $M_{\cup}$ halts with a different answer depending on whether $M$ halts on $w$ or not.

Moving forward, for $\overline{L}$, you express $\overline{L}$ as the intersection of a non-recognizable language and a recognizable language, and conclude that $\overline{L}$ is not recognizable. Unfortunately, this step is invalid. For example, the empty language is the intersection of a non-recognizable language of your choice and the empty language, which is recognizable; yet the empty language is recognizable.
Instead, you need an argument very similar to the one you use for $L$ itself.


acyclic and disjoint union I would like to find a prove of (a) so that the two E are acyclic and disjoint union and I dont unterstand b Could someone shed light on this problem, preferably spiced with some intuition?
Thanks, DarkDragon.

You can solve the first part by providing a valid topological ordering of the vertices, which shows that the graph is a DAG. To show that the union is equal to $E$ show that each arc in $E$ belongs to one of the two sets
The second part needs more context, what is OPT here?


Bitarithmetrics to Base X I've got the following theoretical problem which puzzles me a bit:

I can obtain a string of n bytes (as octets, one byte = one octet = eight bits) of random data. I need to preserve the randomness while reducing the base from 256 to x where x is below 256 (and not 0, 1, 2, 4, 8, 16, 32, 64 or 128).

As I want to preserve the randomness, I don't want to cut-off (waste) any information from this string until I've obtained the number of chunks I need. This is for reason of randomness which can be a limited resource on the computer.

I had the idea to do this for base64 which is simple because I can just create 4 numbers out of a single byte (by shifting bits for example: encode64()). But how to do with a base like 254 for example? I can not cut off at bit-boundaries here, can I?

Do I probably need to create a number large enough out of base 2 based bits that can contain both bases? (This is one of the ideas I have so far).

Would be great to get some feedback, I normally paint pictures with such problems, however, just discovered this website here yesterday and I normally use Stackoverflow so I thought I give it a try :D

If you're interested in some non-theoretical background to my question, see "What is the meaning of the term “simple string” for the SALT string in Unix crypt using SHA-256 and SHA-512?", you might get an idea why I don't want to loose any information bits from the random source.

You can use "arithmetic decoding". Interpret your random data as a random bit stream which encodes a random number between $0$ and $1$. Then write this number in base $B$.

A much simpler method is "rejection sampling". Suppose for example that $128 < B < 256$. Given a random byte $x$, if $0 \leq x < B$ then output $x$, otherwise reject. If $x$ is close to $256$ then this is pretty efficient. (To get higher efficiency, try the same trick with some power of $B$, i.e. output several digits at once.)


Is the halting problem undecidable or unrecognizable? Is the Halting problem in the class of undecidable problems, or it is just in the set of unrecognizable problems?

I understand that if it is undecidable, then it is also unrecognizable. I have seen the two being used interchangeably, however I believe it is possible for a language to be recognizable but not decidable, so was hoping for clarification

Encode a Turing machine $M$ and an input string $I$ into a single string $(M,I)$. Create a Turing machine $U$ that behaves as follows:

$U$ rejects any input that is not a valid encoding
When given valid input $(M,I)$, $U$ emulates the behavior of $M$ with input $I$
If $M$ eventually halts when given input $I$ then $U$ halts and accepts input $(M,I)$

If $M$ eventually halts when given input $I$ then $U$ will (eventually) accept input $(M,I)$. So $U$ recognizes the language

$L=\{(M,I) : M \text{ eventually halts when given input } I \}$

Note, however, that $U$ does not decide $L$ because it does not explicitly reject $(M,I)$ if $M$ never halts given input $I$ - in this case $U$ will also never halt when given input $(M,I)$.

The Halting Theorem tells us that $L$ is undecideable (over Turing machines) but we have just shown that $L$ is recognizeable.