Combinatorial optimization - is there a formal name for this problem? I am looking for a formal name and an algorithmic approach to the following problem.

Given is a set of services each coming with a price:

{s1, 300}
{s2, 400}
{s3, 800}

Additionally there is a set of servicepackages each with a price that may differ from the total cost of the individual services:

{p1, {s1, s2}, 600}
{p2, {s2, s3}, 1050}
{p3, {s1, s3}, 950}
{p4, {s1, s2, s3}, 1250}

Now given a list of services (each service may appear many times) you want performed find the combination of packages and individual services with the lowest price. You can only use a package if you can completely fill it with services. A package may be ordered many times.

For example:
Services to order :{s1,s2,s1,s3,s2,s3,s1}

possible Solutions:

{p4, p4, s1} : 2800
{p1, p1, p3, s3} : 2950

In this case the first solution would be the winner.

An exhaustive approach will quickly explode because it is O(n!) or even worse.

What is the formal name of this problem (if there is one)? How would you algorithmically approach that problem for hundreds of services and packages?

I don't know the name of your problem, if there is one.

But, concerning the complexity: The decision-version of your problem seems to be strongly NP-complete.
You can easily reduce ExactCoverBy3Sets to it:

Given a ground set $X = \{1, \ldots, 3q\}$ and a set $\mathcal{C}$ of 3-element subsets $C_i$ of $X$. Is there a subcollection $\mathcal{C'} \subseteq \mathcal{C}$ of disjoint subsets that cover $X$ ?

Assume we have $3q$ services $1,\ldots,3q$, each with a price of $q+1$. Furthermore, for each $C_i$, we have a package of the corresponding three elements at a price of $1$. Now, given the list $1,\ldots,3q$ of services to order, there is a solution with cost at most $q$ if and only if there is a solution to the given instance of ExactCoverBy3Sets. Since there are no double orders and since  "You can only use a package if you can completely fill it with services", the sets are disjoint and cover the whole ground set $X$.

So, you won't succeed in finding a polynomial (exact) algorithm or an FPTAS. However, you can search for approximation algorithms for the above problem and/or the related problems SetPacking and MinimumCover (cf. Garey/Johnson, "Computers and Intractibility", Problems SP2, SP3 and SP5).


Disjoint Set Connected Components With Weighted Graph I have been trying to solve this HackerRank problem (link).

The basic premise of this problem is that there is a tree with undirected, but weighted, edges. The cost of a path in this tree is taken to be the MAXIMUM cost of any edge in the path. I will be given a series of queries in the form of [L, R] and I have to output how many paths in that tree have a cost in the provided inclusive range.

This is the code I've written -

class DisjointSetRep():
    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0

class DisjointSetNode():
    def __init__(self, val):
        self.val = val
        self.next = None
        self.head = None

class DisjointSetLinkedList():
    def __init__(self):
        self.rep = DisjointSetRep()

    def add_node(self, node):
        if not self.rep.head:
            self.rep.head = node
        self.rep.count += 1
        self.rep.tail = node
        node.head = self.rep

def make_set(v):
    new_linked_list = DisjointSetLinkedList()
    new_head_obj = DisjointSetNode(v)
    new_linked_list.add_node(new_head_obj)
    return new_linked_list, new_head_obj

def find_set(v, node_map):
    return node_map[v].head

def union(u, v, node_map, sets_map):
    u_node, v_node = node_map[u], node_map[v]

    if u_node.head.count > v_node.head.count:
        small_rep = v_node.head
        large_rep = u_node.head
    else:
        small_rep = u_node.head
        large_rep = v_node.head

    # update all nodes to point to new rep
    temp = small_rep.head
    while temp:
        temp.head = large_rep
        temp = temp.next
    # update last node in first list to point to head of second list
    large_rep.tail.next = small_rep.head
    # update new tail
    large_rep.tail = small_rep.tail
    # update count
    large_rep.count += small_rep.count
    del sets_map[small_rep]
    return large_rep

def create_data(edges, node_map, sets_map):

    # sort the edges first, according to cost
    edges.sort(key=lambda x:x[2])
    cost_map = {} # key - cost, value - no of paths
    largest_cost = edges[-1][2]

    for edge in edges:
        if find_set(edge[0], node_map) != find_set(edge[1], node_map):
            unioned_set = union(edge[0], edge[1], node_map, sets_map)
            cost_map[edge[2]] = unioned_set.count - 1

    prefixed_cost_data = {0: 0}
    for i in xrange(1, largest_cost+1):
        val = cost_map.get(i, 0)
        prefixed_cost_data[i] = prefixed_cost_data[i-1] + val

    return prefixed_cost_data

if __name__ == '__main__':
    n, q = map(int, raw_input().split())
    sets_map = {}
    node_map = {}
    for i in xrange(1, n+1):
        new_set, new_node = make_set(i)
        sets_map[new_node.head] = new_set
        node_map[i] = new_node
    edges = []
    for _ in xrange(n-1):
        edges.append(map(int, raw_input().split()))
    prefixed_cost_data = create_data(edges, node_map, sets_map)
    for _ in xrange(q):
        l, r = map(int, raw_input().split())
        print prefixed_cost_data[r] - prefixed_cost_data[l-1]

Let me explain the logic above, which I have derived from this comment -

I sort the edges according to their cost. I then iterate over them and construct the tree edge-by-edge by unioning each vertex, which is initially a disjoint set containing itself (make_set). At any point, no_of_vertexes - 1 gives the no of paths in the tree that contain the maximum cost, which is what I use in unioned_set.count - 1.

This gives me a cost_map with keys as the costs and the values as the number of paths. I also generated a prefixed sum array so that to get the output for [L, R], instead of calculating the no of paths for each value in the range, I can just do prefixed_cost_data[r] - prefixed_cost_data[l-1].

The implementation of the disjoint set is taken straight from CLRS (Section 21.2).

I think the above logic is correct, but I guess it's too slow since most of the test cases timeout.

Can anyone help me in optimizing it? I guess the entire logic needs to be revamped.

Using arrays instead of classes and objects would make it easier for you to implement the disjoint set union concept.

Here's a resource to start off with:- Disjoint Set Union

for edge in edges:
    if find_set(edge[0], node_map) != find_set(edge[1], node_map):
        unioned_set = union(edge[0], edge[1], node_map, sets_map)
        cost_map[edge[2]] = unioned_set.count - 1

cost_map[edge[2]] will not be equal to the size of resultant set after union - 1.

It will be equal to the product of size of two individual sets.

Over here,

for i in xrange(1, largest_cost+1):
    val = cost_map.get(i, 0)
    prefixed_cost_data[i] = prefixed_cost_data[i-1] + val

largest_cost can be >10^9. Neither can you store an array of that size, nor can you execute a loop with 10^9 operations with a time limit of 1sec.

Try using binary search on the L R query.

If you implement disjoint union set with arrays and make the above corrections , then I believe the code should work.


To which character or characters does a Kleene star apply? If you have a Kleene star applying to a set of characters not in any closure, does it apply to that whole string, or just the one character it belongs to? Any examples I search don't specify.

For example:

(A)BB*

Does this mean 1: one A followed by zero to an infinite number of BB's, or does it mean 2: one A followed by at least one B and zero to infinite number of B's?

Kleene stars applies to the character(s) it belongs, so in your example the correct option is the 2° one.

ABB* = {AB, ABB, ABBB, ABBBB, ..}

A(BB)* = {A, ABB, ABBBB, ABBBBBB, ..}


How I can find all equivalence classes by Myhill-Nerode? first of all I'm sorry for my bad English and second I'm sorry for my mistakes of understanding the following topic, I still going to school and learning this for interest.

The topic is Myhill-Nerode and the equivalence classes of a regular or non regular language.

I know that every element of a equivalence class by Myhill-Nerode
fulfills this property:

$ \equiv_{A} \triangleq\{(x, y) | \forall z \in \Sigma^{*} \cdot(x z \in A \leftrightarrow y z \in A)\} $

If I understand this right, than a equivalence class consist of element (words) $x$ which we can expand with a word $y$ but for all words $x$ and $y$ of the same class must apply, adding a word $z$ to them both must be in or out of the language.

Hope that is right until now.

Now I will show you my problem:

I have the language (its from a book):

$  \mathrm{B} \triangleq\left\{73 \mathrm{a}^{n} 7 \mathrm{b}^{\mathrm{m}} | \mathrm{n}, \mathrm{m} \in \mathbb{N} \wedge \mathrm{n}=\mathrm{m}+2\right\} $ with  $ \Sigma_{\mathrm{M}} \triangleq\{\mathrm{a}, \mathrm{b}, 3,7\} $

And a complete solution:

$1: [\lambda]\equiv_{B}=\{\lambda\}  $

$2: [7]\equiv_{B}=\{7\}  $

$3: \left[73 a^{k}\right] \equiv_{B}=\left\{73 a^{k}\right\}  $ für $  k \in \mathbb{N} $

$4: \left[73 a^{l+2} 7\right] \equiv_{B} =\left\{73 \mathrm{a}^{\imath+2+n} 7 \mathrm{b}^{\mathrm{n}} | \mathrm{n} \in \mathbb{N}\right\} \quad  $ für $  l \in \mathbb{N} $

$5: [3]_{\equiv \mathrm{B}}=\Sigma^{*} \backslash\left([\lambda]_{\equiv \mathrm{B}} \cup[7]_{\equiv \mathrm{B}}\right.  \cup\left(\bigcup_{k \in \mathbb{N}}\left[73 a^{k}\right] \equiv_{B}\right) \cup \left(\bigcup_{\mathfrak{l} \in \mathbb{N}}\left[73 \mathrm{a}^{\ l+ 2} 7\right] \equiv_{\mathrm{B}}\right) ) $

So in $1$ they build a class of the empty word $\lambda$ and $z = B$ has to be the language by her self to be in the language?

In $2$ they build they build the class of $7$ and z has to be something like this $ z = \left\{3 \mathrm{a}^{n} 7 \mathrm{b}^{\mathrm{m}} | \mathrm{n}, \mathrm{m} \in \mathbb{N} \wedge \mathrm{n}=\mathrm{m}+2\right\}$ to be in the language.

In $3$ they build a class or better infinitely many classes. But here is my problem. I cannot find a $z$ which is working for all classes.

For example we have the words $x_i$ and $z_i$

$x_1 = 73 \to z_1= {a}^{n+2}7b^n$ with $n\in N$

$x_2 = 73a \to z_2= {a}^{n+1}7b^n$ with $n\in N$

$x_3 = 73a^2 \to z_3= {a}^{n}7b^n$ with $n\in N$

$x_4 = 73a^3 \to z_4= {a}^{n}7b^n+1$ with $n\in N$

and so on.

But why is this ok? I Mean they are 2 words in this class for example $x_1$ and $x_2$ who $x_2$ would not be in $B$ with $z_1$.

I hope you can tell me on a simple and understanding way how those classes by Myhill work and how i can find them without making big mistakes.

$\Bbb N$ denotes the set of natural numbers, that is, the set $\{0,1,2, \cdots\}$. If $\Bbb N$ is the set of positive integers, the treatment will be roughly the same.

  So in $1$ they build a class of the empty word $\lambda$ and $z = B$ has to be the language by her self to be in the language?

Since the above paragraph in the question, $z=z(C)$ is understood/redefined to be the set of words such that Cz is a subset of $B$, given a set of words $C$. That is, $cw\in b$ for any $c\in C$ and $w\in z$.

With the above understanding, yes, $z([\lambda]_{\equiv_{B}})=z(\{\lambda\})=B.$

  $3: \left[73 a^{k}\right]_{\equiv_{B}}=\left\{73 a^{k}\right\}  $ for $  k \in \mathbb{N} $

Case 3 gives one equivalent class for each $k\in\Bbb N$. It lists infinitely many equivalent classes as the following, each with different $z$.

Letting $k=0$, we have $\left[73\right]_{\equiv_{B}}=\left\{73\right\}\,.$
Letting $k=1$, we have $\left[73 a^1\right]_{\equiv_{B}}=\left\{73 a^1\right\}\,.$
Letting $k=2$, we have $\left[73 a^2\right]_{\equiv_{B}}=\left\{73 a^2\right\}\,.$
Letting $k=3$, we have $\left[73 a^3\right]_{\equiv_{B}}=\left\{73 a^3\right\}\,.$
$\vdots$

Their $z$'s are the following, which are more or less listed in the question.

$z\left(\left[73\right]_{\equiv_{B}}\right)=z\left(\left\{73 \right\}\right)=\left\{a^n7b^m \mid n,m\in \Bbb{N} \wedge n=m+2\right\} \,.$
$z\left(\left[73 a^1\right]_{\equiv_{B}}\right)=z\left(\left\{73 a^1\right\}\right)= \left\{a^n7b^m \mid n,m\in \Bbb{N} \wedge n=m+1\right\} \,.$
$z\left(\left[73 a^2\right]_{\equiv_{B}}\right)=z\left(\left\{73 a^2\right\}\right)=\left\{a^n7b^m \mid n,m\in \Bbb{N} \wedge n=m\right\} \,.$
$z\left(\left[73 a^3\right]_{\equiv_{B}}\right)=z\left(\left\{73 a^3\right\}\right)=\left\{a^n7b^m \mid n,m\in \Bbb{N} \wedge n=m-1\right\} \,.$
$\vdots$

Once you have understood the above, it should be easy to figure out case 4 and the rest of the given solution. You did have a pretty good understanding of the  Myhill-Nerode equivalence classes.

Here is another way to write the same solution in the question.

$1: [\lambda]_{\equiv_{B}}=\{\lambda\}  $

$2: [7]_{\equiv_{B}}=\{7\}  $

$3: \left[73\right]_{\equiv_{B}}=\left\{73\right\}$

$4: \left[73a\right]_{\equiv_{B}}=\left\{73a\right\}$

$5: \left[73a^2\right]_{\equiv_{B}}=\left\{73a^2\right\}$

$6: \left[73a^3\right]_{\equiv_{B}}=\left\{73a^3\right\}$

$\vdots$

$\infty+1: \left[73 a^2 7\right]_{\equiv_{B}} =\left\{73 a^{2+n} 7 b^{n} \mid n \in \mathbb{N}\right\}$

$\infty+2: \left[73 a^3 7\right]_{\equiv_{B}} =\left\{73 a^{3+n} 7 b^{n} \mid n \in \mathbb{N}\right\}$

$\infty+3: \left[73 a^4 7\right]_{\equiv_{B}} =\left\{73 a^{4+n} 7 b^{n} \mid n \in \mathbb{N}\right\}$

$\infty+4: \left[73 a^5 7\right]_{\equiv_{B}} =\left\{73 a^{5+n} 7 b^{n} \mid n \in \mathbb{N}\right\}$

$\vdots$

$2\infty+1: [3]_{{\equiv B}}=\Sigma^{*} \setminus\left([\lambda]_{\equiv B} \cup[7]_{\equiv B}  \cup\left(\bigcup_{k \in \Bbb{N}}\left[73 a^{k}\right]_ {\equiv_{B}}\right) \cup \left(\bigcup_{k \in \Bbb{N}}\left[73a^{k+ 2} 7\right]_{\equiv_B}\right)\right)\,. $

Exercise. Given the language
$$ A \triangleq\left\{1^{n} 0^{n} \mid n \in \mathbb{N}\right\} \text { with } \Sigma_{A} \triangleq\{1,0\}, $$
give all equivalence classes of the Myhill-Nerode relation. (Check here for an answer.)


Slowdown when accessing data at page boundaries? Hi I have a program which accesses memory words that are located X bytes apart in virtual address space. For instance, for (int i=0;<some stop condition>;i+=X){array[i]=4;}.

I measure the execution time with a varying value of X. Interestingly, when X is the power of 2 and is about page size, e.g., X=1024,2048,4096,8192..., I get to huge performance slowdown. But on all other values of X, like 1023 and 1025, there is no slowdown. The performance results are attached in the figure below.

I test my program on several personal machines, all are running Linux with x86_64 on Intel CPU.

What could be the cause of this slowdown? We have tried row buffer in DRAM, L3 cache, etc. which do not seem make sense...

Go to Agner manuals page and download them all, you will find tons of interesting info there. In particular, microarchitecture.pdf says

  There is a false dependence between memory addresses with the same set and offset, i.e. with a distance that is a multiple of 4 Kbytes:

;Example 9.6. Sandy bridge false memory dependence
mov [rsi],eax
mov ebx,[rsi+1000H] ;False memory dependence

I.e. the access becomes slower because cpu thinks that it may be the same address, so the load in the second line may depend on the store in the first line and thus cpu serializes execution of these operations.

AFAIR, it wasn't changed in latest Intel cpus.


Proving that shortest path distance of adjacent nodes can't differ by more than one Could someone explain this proof to the following question?

Lemma 22.1 from intro to algorithms
Let $G=(V,E)$ be a directed or undirected graph, and let $s\in V$ be any vertex. Then, for any edge $(u,v)\in E$,
$$\mathrm{dist}(s,v)\leq \mathrm{dist}(s,u)+1\,.$$
Proof.
If $u$ is reachable from $s$, then so is $v$. In this case, the shortest path from $s$ to $v$ cannot be longer than the shortest path from $s$ to $u$ followed by the edge $(u,v)$ and thus the inequality holds.

I drew this to visualize the problem but I don't see how what I drew is wrong and how the proof is correct.

If going from $s$ to $u$ has less vertices along that path than going from $s$ to $v$, than the shortest distance of $s$ to $v$ should be greater than going from $s$ to $u$ and $s$ to $u$ to $v$.

I don't understand your diagram but the point is that, if there is a $x$–$y$ path of length $k$ then the distance from $x$ to $y$ cannot be bigger than $k$.

So, suppose the shortest path1 $P$ from $s$ to $v$ has length $k$. If that path includes $u$, then there is a path of length less than $k$ from $s$ to $u$. Since there is a path of length less than $k$, the distance from $u$ to $v$ is less than $k$, so it is less than or equal to $k+1$, as required.  On the other hand, if $P$ does not include $u$, then $P$ followed by the edge $uv$ is a path from $s$ to $v$ of length $k+1$. Since there is a path of length $k+1$, the shortest path can't be longer than that, so the distance is at most $k+1$.

1 I should really say "a shortest path", since there can be multiple different paths, all of the same length.


Calculating the kth largest distance among $n$ points on a number line in $O(n\log n)$? I have got some difficulties to solve this algorithm problem.

I have been given a set of n points on a number line. Those points are not sorted in the set. For any two points $(a, b)$ in the set, their distance is calculated as $|a-b|$. Now I need to calculated the kth largest among all possible distances of the n points in $O(n \log n)$ time using a randomized algorithm and a deterministic algorithm respectively.

To solve this problem, I begin with sorting the n points in $O(n \log n)$ time. I noticed that this problem it is similar to the quick select for the kth largest of the array. The naive approach is to calculate all possible distances and do quick select. But this takes $O(n^2)$ running time. It seems that I have to run the quick select with only necessary distances calculated. Now I have to do two things recursively:

partition all distances with a randomly chosen pivot, and
find out the numbers of distances on each side to determine which part for recursion.

There would be $O(n \log n)$ steps for the recursion. So, I have to do the two things above in $O(n)$ time. And I have difficulties with that.

Please help me. Thank you very much.

Given some pivot $K$, you can count the pairs with differences above it in $O(n)$, whether you use a random pivot or binary search.

The pairs form a kind of uneven grid in the plane, and you can search diagonally along the line $y = K+x$ to find the border between $x_j - x_i \le K$ and $x_j - x_i \gt K$ in $O(n)$ as follows (Bresenham's Line Drawing Algorithm):

Start at the y axis and find minimum $j$ so that $x_j - x_0 > K$
$Count = n-j+1$
For $i = 1$ to $n-1$ do

While $x_j - x_i < K$, $j = j+1$

If $j=n$ break

$Count = Count + n - j + 1$

(There are some adjustments for when K is larger than the range, but the main idea is here.)

Basically you move right and then slide $j$ up until you cross the line, then add all the entries above that point to the count. As you continue right you're always at or above the $j$ you used in the previous column, so you do $O(n)$ pair tests for the whole scan.


Clarification in the proof for the Bellamn-Ford algorithm While proving the correctness of the Bellman-Ford algorithm, we prove the following lemma:

  After k (k >= 0) iterations of relaxations, for any node
  u that has at least one path from s (the start node) to u with at most k edges, the distance of from s to u is the smallest length of a path
  from s to u that contains at most k edges.

We prove this lemma using mathematical induction as follows:

Base case: After 0 iteration, all distance values are infinity,
but for s the distance is 0, which is correct!
We assume the lemma is true for k iterations and now we have to prove it for k+1 iterations!
Before k + 1th iteration, dist[u] (which is the distance of u, from s) is the smallest length of a path from s to u containing at most k edges. Each path from s to u goes through one of the incoming edges (v, u). Relaxing by (v, u) is comparing it with the smallest length of a path from s to u through v containing at most k + 1 edges -- this proves it!

Now, I have doubt in the 3rd point. Let us say that in the k+1-th iteration the node u has got a new distance after some edge relaxations, now according to the above lemma, this distance must be the shortest of the distances of all the paths with at most k+1 edges from s to u. Now, consider another node w, that has an edge to it, from u. Now, the length of the path form s to w via v will have at most k+2 edges, but if this edge is relaxed to reduce the dist[w], then in k+1-th iteration itself, we will have included a path (to w) that has almost k+2 edges right? Is it not a contradiction? Can it not happen?

To be more precise I am unable to reason the fact that, the lemma holds true throughout the k+1-th iteration -- I am not convinced with the 3rd step of the proof.

If someone can explain to me the 3rd step or whole proof more clearly, it would be really helpful! If someone can share a proof that does not use mathematical induction will also be really helpful!

The claim you are trying to prove by induction is wrong, and I believe this is exactly the source of your confusion.

  The correct claim is the following: Consider the values of
  $\text{dist}[\cdot]$ computed at the end of the $k$-th iteration of
  Bellman-Ford. For any vertex $u$, let $d^{(k)}_u$ be the length of the
  shortest path from $s$ to $u$ that uses at most $k$ edges (if no such path exists then $d^{(k)}_u = +\infty$). It holds
  that $\text{dist}[u]\le d^{(k)}_u$.

Notice the $\le$ sign!

The above claim implies that, after the $(n-1)$-th iteration all distances stored in $\text{dist}[\cdot]$ are smaller than or equal to the true distances in the graph.

Clearly, it also holds that all the distances stored in $\text{dist}[\cdot]$ are larger than or equal to the true distances in the graph (since every time you a distance is updated, the new distance is always the length of some path from $s$).

Combining the previous two properties, you can conclude that $\text{dist}[\cdot]$ stores the exact distances from $s$, i.e., that the Bellman-Ford algorithm is correct.

Let me prove my claim formally. To avoid confusion this is the pseudocode of the Bellman-Ford algorithm I will be using:

Bellman-Ford(G=(V,E; w), s):
  For u in V:
    dist[u]=+infinity

  dist[s]=0
  For k=1,..., n-1:
    For (v,u) in E:
      dist[u] = min(dist[u], dist[v] + w(v,u))

The proof is by induction on $k=0, \dots, n-1$ (where the end of the $0$-th iteration corresponds to the state of the algorithm just before the first iteration of the outer for loop).

The base case is $k=0$. There is only one vertex $u$ such that the path from $s$ to $u$ uses $k=0$ edges, namely $u=s$. The claim holds for $s$ since $\text{dist}[s] = 0 = d_s^{u}$. For $u \neq s$, the claim holds since $\text{dist}[u] = +\infty = d_u^{(k)}$.

Suppose now that the claim holds for $k-1 \ge 0$. We will prove that it also holds for $k$. Consider any vertex $u \in V$, let $P$ be the shortest path from $s$ to $u$ that uses at most $k$ edges, let $w(P)$ be the (weighted) length of $P$, and let $|P|$ denote the number of edges of $P$. We distinguish two cases:

If $|P| < k$ then $d_u^{(k)} = d_u^{(k-1)}$ and, by inductive hypothesis, at the end of the $(k-1)$-th iteration of the outer for loop we had $\text{dist}[u] \le d_u^{(k-1)} = d_u^{(k)}$. The claim follows since the values of $\text{dist}[\cdot]$ never increase during the execution of the algorithm.

If $|P|=k$ then $|P| \ge 1$. Let $(v,u)$ be the last edge of $P$ and let $P'$ be the subpath of $P$ from $s$ to $v$.
Let $\delta$ be the value of $\text{dist}[v]$ at the end of the $(k-1)$-th iteration of the outer for loop.
By the suboptimality of shortest paths we know that the (weighted) length $w(P')$ of $P'$ is exactly $d_v^{(k-1)}$. Moreover, the inductive hypothesis ensures that $\delta \le d_v^{(k-1)}$.
Consider the situation at end of the iteration of the inner for loop that considers edge $(v,u)$, during the $k$-th iteration of the outer for loop. Since values of $\text{dist}[\cdot]$ never increase, we must have:
$$
\begin{align*}
\text{dist}[u] &\le \text{dist}[v] + w(v,u) \\
&\le \delta + w(v,u) \\
&\le d_v^{(k-1)} + w(w,v) \\
&= w(P') + w(v,u) = w(P) = d_u^{k}.
\end{align*}
$$
Once again, since the values of $\text{dist}[\cdot]$ never increase, the above inequality must also hold true at the end of the $k$-th iteration of the outer for loop.


How to calculate combination from given n,r and rank? Suppose that $S=\{1,2,...,n\}$ and we are given an integer $r\leq n$.

An $r$-combination of $S$ is obtained by selecting $r$ distinct integers out of the $n$. We order all $r$-combinations for a given $r$ lexicographically. Call the rank of an $r$-combination its rank in this ordering.

I am interested in finding a $r$-combination given $n$, $r$ and the rank.

For example, if $n=10$, $r=5$, rank $=72$, then the answer should be $1, 3, 5, 6, 7$.

How can we compute this efficiently? In particular, can we do this faster than generating the entire enumeration?

I assume that your rank starts at $0$, as this simplifies the code (for me).

The core question you must be able to answer is how many elements there are in a substructure of yours.
So in your example, we're ordering combinations lexicographically so we can use the binomial coeffecient to find how many elements there are of our substructures. We'll first try to find the first element of our combination.

Suppose our first element is $x$, then there are $\binom {n-x}{r-1}$ ways the rest of the elements can be chosen. So how do we find $x$? We repeatedly compare our rank to $\binom {n-x}{r-1}$. Is our rank smaller than this, then we must be in this range of sets. Otherwise we subtract this from our rank to skip these sets and try the next $x$.

Once we have found our $x$, we move on to the second element, etc until we are done. Initially we search with $x = 1$, but we increment $x$ after each element found because we want a strictly increasing lexicographically ordered set.

def binom(n, k):
    if k > n: return 0
    if n - k < k: k = n - k
    r = 1
    for d in range(1, k+1):
        r = r*n//d
        n -= 1
    return r

def derank_one(n, r, rank, x):
    while True:
        size = binom(n - x, r - 1)
        if rank < size:
            return x, rank
        if size <= 0:
            raise ValueError("rank is out of range for this set")
        rank -= size
        x += 1

def derank(n, r, rank):
    x = 1
    result = []
    while r > 0:
        x, rank = derank_one(n, r, rank, x)
        result.append(x)
        r -= 1
        x += 1
    return result

And indeed we find that derank(10, 5, 71) == [1, 3, 5, 6, 7] ($71$ because we count starting from $0$).


set cover where only certain special subsets are allowed I am trying to solve a problem which turns out to be a form of the set cover problem. I've implemented the greedy Set cover approximation algorithm for set cover, but it turns out to not be accurate enough for my needs.

Specifically I have a fixed, finite, list of special sets and I am trying to create a function which when given a set returns the smallest list of special sets which cover that given set, and that list should contain no sets which contain elements not in that given set. The fixed list seems like it should make the problem easier to solve than set cover, but I'm not sure how the additional requirement of no extra elements affects the difficulty. My sets also have a known maximum size which should also make this easier to solve.

A toy version of the problem is as follows:

  Let $U$ be the set $\{a,b,c,d,e,f,g,h\}$. All the sets we mention from
  here on will be subsets of this set.

  Let $S$ be a list of special sets. For this version of the problem we
  can use the following list:

  $$ S = [\{a,b,c,d,e,f,g,h\}, \{a,b,c,d\}, \{e,f,g,h\}, \{a,e\}, \{b,f\}, \{c,g\}, \{d,h\}, \{a,b\}, \{b,c\}, \{c,d\}, \{d,e\}, \{e,f\}, \{f,g\},\{g,h\}, \{a\}, \{b\}, \{c\}, \{d\}, \{e\}, \{f\}, \{g\}, \{h\}]$$

  For a given set $G$ what is the smallest list of sets which are part
  of $S$ which cover $G$, (that is where the union of the sets in the
  list is $G$).

For the above toy problem, the greedy approximation I've implemented, if presented with a set like $\{b, c, g, h\}$, produces $[\{c, g\}, \{b\}, \{h\}]$ instead of the smaller list $[\{b, c\}, \{g, h\}]$.

Has this sort of problem been well studied? Is there a known non-approximate algorithm given the additional constraints, that would be better than naive dynamic programming? A well-known name for the version of set cover where extra elements are not allowed would also be useful.

Your problem is hardly easier than the general set cover problem.

Given a set $G=\{b, c, g, h\}$, we remove all elements in $S$ that are not contained in $G$, obtaining a collection of set $C=[\{c,g\}, \{b,c\}, \{g,h\}, \{b\}, \{c\}, \{g\}, \{h\}]$. Now the problem becomes the standard set cover problem with $G$ being the universe and a collection of 7 subsets. Since this reduction process takes $O(n^2)$ time where $n$ is the total number of elements in $U$, your problem cannot not significant easier than the general set cover problem unless there are further conditions to be exploited.

Unfortunately, the general set cover problem is NP-hard. It is one of Karp's 21 NP-complete problems. Even more unfortunately, the simple greedy algorithm achieves about the best approximation ratio, $H(s')$, where $S'$ is the maximum cardinality of the sets. Here $H(n)$ is the $n$-th harmonic number.

If you have to obtain the exact minimum set cover, you will have to resort to exponential algorithms. One simple simplification that can be done is to remove all elements in $C$ that are subsets of another element of $C$. That is, we can replace $C$ by $[\{c,g\}, \{b,c\}, \{g,h\}]$. A simple brute force algorithm is just to test all subsets of $C$ of size 1, those of size 2, those of size 3, etc. A common way to attack the problem is by integer linear programming.

Just in case, you might want to take a look at some literature on the set cover problems. For example, An Exact Algorithm for Unicost Set Covering and LP techniques for set cover.


Suitability of high-level languages for embedded systems Low-level languages have for a long time dominated the field of embedded systems due to their rapidity and flexibility. As high level languages are becoming faster and faster, might the situation get reversed soon? Can high-level languages become frequent in embedded systems in a near (or not so near) future? What would it take for a high-level language to be suitable for embedded systems?

What is a high level language? What is an embedded system? Once upon a time C was a high level language and a Raspberry Pi would have changed the outcome of major wars, now almost every microcontroller can be programmed with C and we use Pis that run a full-blown desktop OS to turn servo motors. Let's say a high level language is a language that has strong abstraction mechanisms and an embedded system is a system with very limited memory and a processor with few features.

That alone is not enough to say whether this language is suitable for embedded programming or not. The important part is how the programs in the language can be compiled. Many languages (have to) add something called a runtime to the programs. For Haskell for example the runtime added by GHC is about 50k LOC and includes a garbage collector, a scheduler and a bunch of other stuff. That is quite a lot of code for a small chip to handle and might require processor features that aren't present.

Rust is another language that I'd call high-level, but it is possible (in theory at least) to run Rust on many embedded systems. This is because Rust has the possibility to use a much smaller runtime that can be handled by simpler processors and doesn't add as much overhead.

So in summary, the important part is not the features of the language, but how much of those features need support at runtime as opposed to a clever compiler. Garbage collection is typically too difficult for embedded systems, but a surprising amount of abstraction power can be provided without any extra costs at runtime.

Note that in practice you're still limited to C or Assembler in many cases, because you need a compiler that supports your target architecture. Unfortunately it is often the case that the architecture is proprietary and you're limited to using the compiler provided by the manufacturer. That is typically a compiler that supports some flavor of C.


How can a cyclic tag system halt with an output? For example, we can say we have a abstract program that, given a finite binary string as input, removes all of the zeros (i.e. 0010001101011 evaluates to 111111), which is definitely a Turing-computable function.

How can a cyclic tag system compute this (which it can, by definition of it being Turing-complete) when it only halts when it reaches the empty string? The Wikipedia article gives an example of converting to a 2-tag system, but it adds an emulated halt that the original system does not have.

I can't find any reference to how a cyclic tag system halts meaningfully. What is its output supposed to be? I've considered things like

Number of steps (but then input restricts possible output without some kind of fancy encoding I can't find)
The last production (but that only has a finite output range)
Fixed points (which can't be detected in this system and only exist with very limited production rules and inputs)

but they don't work, at least not in any way I can see.

Neary and Woods describe an efficient simulation of Turing machines using cyclic tag systems, improving on work of Matthew Cook. Turing-completeness is a somewhat fluid and informal notion. A computing system X simulates another computing system Y if given each program in Y we can come up with a program in X such that looking at the transcript of the X-program, we can recover a transcript of the Y-program.

You can look at the papers above to see what this means for cyclic tag systems. The basic idea is that when the Turing machine halts, the cyclic tag systems keeps going, forever repeating the same sequence of configurations, representing the halting configuration of the Turing machine. In this sense it can actually compute functions.

In an earlier answer I noted that some computation models can only compute decision problems, in the sense that they either don't halt, or they halt with just one bit of output. In that case you can encode general function in at least two ways:

Given a function $f$, consider the language of pairs $\langle x,f(x) \rangle$.
Given a function $f$, consider the language of triples $\langle x,i,b \rangle$ such that the $i$th bit of $f(x)$ (if any) equals $b$.

As usual, we require that the machine always halt.


What are constraints on some new logic programming language and system? As I understand, everyone can create logic programming language and system by declaring that the valid program of some logic programming language is the set of statements in the form: body->head, where body is arbitrary expression of boolean type and the head is set of expression that, in some cases, can change the current valuation function (function for some logic that assigns values to the variables of this logic), e.g. by assignment operations. There is no need to prove any properties of such programming system, because one can expect that such system is Turing complete and hence there is no important properties (e.g. termination) to prove. Practical termination can be achieved even by very rude methods (e.g. as in Drools), e.g. by allowing to declare that no more than e.g. 10 rules can be fired in one execution step. Am I right? Does the definition of new logic programming system/language for scientific and practical purposes ineed allow such great freedom without any constraints and duties to prove some properties of this system?

Of course, some works on logic programming tries to prove stable model properties but I am interested (and practice usually requires) in non-monotonic logic programs (as almost any program used for business purposes change the state and hence the valuation function of variables) and they can not have such stable models.

There is such background for my question: I am aware of the logic programming system for agent modelling http://jason.sourceforge.net/wp/ Jason AgentSpeak. I am not satisfied with the expressibility of the base logic used by AgentSpeak. I have reason to state, that special kind of linear logics can be more appropriate base logic for agent modelling. That is why I am trying to create my own new logic programming system that is based on special kind of modal linear logic with actions. So - can I simply form the set of expressions of the type body->head from the language of modal linear logic and announce them as logic programs in modal linear logic? I am required to prove anything?

It sounds like you have the impression that there are some rules on what languages you are allowed to define.  There are no such rules.  You can define whatever language you want.  You can do whatever what you want -- you're not required to do anything (there are no language police who will come arrest you for failing to prove some theorem about it).  Whether it will be useful, or used by anyone else, is a different matter.


What are the drawbacks of fully-convolutional neural networks? It is possible to replace the fully-connected layers of a CNN with convolutional layers, making it fully convolutional. Fully-convolutional networks (FCNs) can be applied to inputs of various sizes, whereas a network involving fully-connected layers can't. Still, for the input size the network was designed for (e.g. 224x224 in the case of VGGNet) the mathematical operations performed are exactly the same in both. What are the drawbacks of a FCN? Can we just throw away all fully-connected layers and replace them with their convolutional counterpart?

All-convolutional network is a great idea exactly because it has much more advantages than disadvantages. Most of modern convolutional networks are designed to use CONV for everything. If you are focused specifically on disadvantages, here're a few:

An FC to CONV layer replacement means great reduction in the number of parameters. It's cool to save the memory, but it's loss of flexibility nevertheless. In my experiments, CIFAR-10 classification accuracy dropped slightly after this single change, though it was certainly within one standard deviation. But I'm sure there are cases when this loss of flexibility makes a bigger impact.
A convolution is a significantly slower operation than, say maxpool, both forward and backward. If the network is pretty deep, each training step is going to take much longer.
The network is a bit too slow and complicated if you just want a good pre-trained model. That's why the researches still use AlexNet and VGGNet for experiments. They are simple (in terms of architecture), well-known and provide good performance - that's exactly needed.


Differences between linear/nonlinear vs. deterministic/nondeterministic neural nets When speaking of neural networks, I don't get the difference between nonlinear and non-deterministic. Basically, both say that the output of something is not directly correlated to the input?

Hope someone can illuminate me.

Non linear means that there may be a correlation with the input, but it is not a linear one. A function is say to be linear in some argument (the input) when the ratio result/argument is constant. In your case, it is the ratio output/input. Actually, the mathematical definition is a bit more general.

Non determinism is of a different nature. The input/output relation is said to be non-deterministic when one of several result may occur, without any a priori known cause. This is usually modelelled mathematically, either by using a relation rather than a function, of by considering a function from the input domain to the domain of subsets of the output domain.

For example: if you consider inputs and outputs in the domain of integer, for each integer input, you have a set of possible outputs that are all integers.

When this set always contains only a single element, the function is deterministic, and the set can be replaced by this unique element.


Evaluating tree data iteratively Community,

I'm working on a project lifting assembler code to a AbstractSyntaxTree-like structures like these:

In order to be able to evaluate the final value of a tree given only leafes with constant values, I implemented an recursive approach: Each node class has its own value function. For all nodes except constants, it will query the value function of its children.

e.g. A add node has a value function which works like this:

self.children[0].value() + self.children[1].value()

This seems simple and stores Operation-Logic where it belongs: into operation nodes. The main problem is that these trees tend to be become very large and I fear an recursive approach might not be the best way here.

The most common operations ran on this tree are tree merging and optimization (transversal + modification). At the moment we use single-linked notes, since this serves the use cases in the best way.

Is there any iterative way of archiving this value evaluation? Any help appreciated.

A recursive function is only bad if it ends up repeating work and in this case it does not have too. A postorder traversal of the tree is what you want to do here, and the iterative solution exists, but is considerably more difficult to implemant. A post order traversal will only visit each node once, and you will not beat that for complexity.


Verifying a solution vs. finding one There is an algorithmic problem $A(n)$, where $n$ is the size of the problem.

It is known that, for every candidate solution S, the time it takes to verify whether it is a correct solution to $A(n)$ is $T(n)$.

Does this imply a lower bound on the time it takes to find a correct solution to $A(n)$ (e.g. that it takes at least time $T(n)$)? This seems obvious to me, but obvious and true do not always coincide. Since $P \subseteq NP$, the implication probably holds if $T(n)$ means "polynomial time". But does it hold in general, for arbitrary complexity classes?
Does this imply any upper bound on the time it takes to the time it takes to find a correct solution to $A(n)$ (e.g. that it can be done in time $2^{T(n)}$)?

You should define carefully what it means to "find a correct solution". In trivial problems, this may be different than verifying. For example, consider the problem of deciding whether a graph is colorable in some number of colors. This problem is trivial, since every graph is colorable in $|V|$ colors. Moreover, it is easy to define such a coloring - give a distinct color for each vertex.

However, verifying that a coloring is correct takes quadratic time.

As for an upper bound - if verifying a solution takes time $T(n)$, than going over all solutions will take time $2^{O(T(n))}$, so not exactly $2^{T(n)}$, but close.


minimizing the maximum between a degree of a tree and its height I'm interested in asymptotically minimizing the maximum between the height of a tree of degree $k$ with $n$ leaves, and $k$, i.e. minimizing $\max(k, \log_kn)$ asymptotically.

If I set $k = \frac {\log n}{\log \log n}$, then the height of the tree is
$\log_\frac{\log n}{\log \log n}(n) = \frac{\log n}{\log \frac {\log n}{\log \log n}}$.

What is the asymptotic height of that tree, is $$\frac{\log n}{\log \frac {\log n}{\log \log n}} = \Theta(\frac{\log n}{\log \log n})$$ and if so, is this optimal?

Yes, it is true that $\dfrac{\log n}{\log \frac {\log n}{\log \log n}} = \Theta(\dfrac{\log n}{\log \log n}).$ In fact, we have the following more accurate approximation,
$$\frac{\log n}{\log \frac {\log n}{\log \log n}} \sim \frac{\log n}{\log \log n}.\tag{app}$$

Proof. $$\begin{aligned}
\lim_{n\to\infty}\frac{\ \frac{\log n}{\log \frac {\log n}{\log \log n}}\ }{\ \frac{\log n}{\log \log n}\ }&=\lim_{n\to\infty}\frac{\log\log n}{\log \frac {\log n}{\log \log n}}
=\lim_{n\to\infty}\frac{\log\log n}{\log\log n-\log\log \log n}\\
&=\frac{1}{1-\lim_{n\to\infty}\frac{\log\log \log n}{\log\log n}}
=\frac{1}{1-0}=1.
\end{aligned}$$

So, if we set $k = \frac {\log n}{\log \log n}$, then the height of the tree,  $\frac{\log n}{\log \frac {\log n}{\log \log n}}$ is $\frac{\log n}{\log \log n}$ asymptotically and, hence, so is the larger one between the height of the tree and $k$.

Now, the question is what is the asymptotic behavior of the minimum of the larger one between $\log_kn $ and $k$, i.e. $h(n)=\min_k\max(\log_kn,k)$.

Since $k$ is increasing with respect to $k$ while $\log_k n$ is decreasing with respect to $k$, the minimum of the larger one between $k$ and $\log_k n$ for a given $n$ is obtained when $k=\log_k n$, assuming $k,n>1$.

What is the solution to $k=\log_k n$ for a given $n$?
$$k=\log_kn\Leftrightarrow k= \frac{\log n}{\log k}\Leftrightarrow \log k\cdot k= \log n\Leftrightarrow \log k\cdot e^{\log k}= \log n$$
By the definition of the Lambert $W$ function, we should have
$$\log k = W_0(\log n),$$
where $W_0(\cdot)$ is the principal branch of the Lambert $W$ function, as we are only interested in the real positive values. So,
$$k = e^{W_0(\log n)}.$$
Accordingly,
$$h(n)=\left.\max(\log_kn,k)\right|_{k=e^{W_0(\log n)}}=e^{W_0(\log n)}.$$

The same article on Lambert $W$ function tells that
$$ W_0(x) = \log x - \log\log x + o(1).$$
Substituting $\log n$ for $x$, we have
$$ W_0(\log n) = \log\log n - \log\log\log n + o(1).$$
So,
$$ h(n) =e^{W(\log n)}= e^{\log\log n} e^{-\log\log\log n} e^{ o(1)}=\frac{\log n}{\log\log n}\ e^{o(1)},$$
Since $e^{o(1)}$ goes to 1 when $n$ goes to infinity,
$$h(n)\sim{\frac{\log n}{\log\log n}}.$$

Combining the above conclusions, we see that if we set $k = \frac {\log n}{\log \log n}$, then the larger one between the height of the tree and $k$ approaches its minimum $h(n)$ as well as ${\frac{\log n}{\log\log n}}$ asymptotically.

To be nit picky, it should  be pointed out that we have been ignoring the expected requirement that $k$ should be an integer. It would require cumbersome analysis to adapt the above analysis and conclusion for integer $k$. In the end, we have still
$$\min_{1\lt k\le n,\ k\in\mathbb N}\max(k, \log_kn)\sim\frac{\log n}{\log\log n}.$$


Enhance B-Tree with find(k) function I have a question to enhance a B-Tree and add a function called find(k) which gets a key - k and returns the index of it in the sorted keys of the tree, using $O(N)$ space complexity, and it needs to be in $O(t \cdot \log_t{n})$ time complexity. I also need to show that the function does not make the regular functions (insert, delete, split child) any different then what they used to be before ( time complexity- wise)
for example, for this tree (Only example! max degree = 3, t=2 because $MaxDeg = 2 \cdot t - 1$):

find(50) would return: 6 (because its in the sixth element of the sorted keys: 10 10 20 20 20 50 60 70 80)
I thought about storing how many keys are before each key, and thus we can actually do it in $O(1)$ but it seems unrealistic, if the question asks for $O(t \cdot log_t{n})$
Thank you!

First take the case when you don’t have any key repeated: you can use an ordinary Binary Search Tree (BST) and perform an inorder traversal for searching the required key. Since inorder traversal gives you the keys in sorted order, so you can simply maintain a counter which you increase every time you visit a new node.

Since, you want to allow multiple occurrences of keys, you need need to modify the node to have a integer to hold the number of times that key has been added.

It’s quite easy to fill the details.


create large data sets for machine learning I am trying to research a new topic using machine learning. The problem is, I have a very small dataset, consisting of 5 months of data. I have been told that my dataset is too small. I want to know if there is any way of making my dataset larger, using an automated tool/algorithm I can implement fast, and more than that, if it is a good idea.

My dataset contains also months with peculiar data (or outliers) and they have cases from generic and standard to unexpected data.

I mention that I have already searched for similar datasets on the available websites. The dataset I am interested in it's about personal budgets, incomes, expenses, consumer behavior.

I know nothing about machine learning, so take the following with a pinch of salt. (I originally posted it as a comment and was encouraged to repost as an answer, so I guess it can't be terrible.)

You get more data by, well, collecting more data...

Simply using some algorithm to generate more data similar to the data you already have won't help, because it doesn't change the distribution of the data, so doesn't do anything to address the problem that your data might not be representative of reality. For example, suppose I make a crappy painting (I can't paint at all) and I ask ten people from my family and close friends if it's any good. They all say, "Yes, David, it's wonderful" because they don't want to hurt my feelings. If you advise me to ask more people's opinion, that's because you feel that I didn't get a proper variety of opinions. Just asking the same ten people again won't change anything: it'll just make me more confident in my bad data because now "twenty" people have told me that my crappy painting is wonderful.

Ultimately, the same problem applies to any algorithmic approach: the best it can do is to generate more data like the data you already have, but that can't possibly have higher quality. And note that any algorithmic approach is, essentially, "use machine learning to generate more data like the data I already have, and then use machine learning to do X with all that data" so it can't be any better than just using machine learning on the original dataset.


Recurrence formula for a known sequence? Problem: How do we can generate some mathematical close form of the following sequence, which has following 256 entries:

1   7   7   7   7   9   9   9   7   9   9   9   7   9   9   9   7   11  11  11  11  13  13  13  11  13  13  13  11  13  13  13  7   11  11  11  11  13  13  13  11  13  13  13  11  13  13  13  7   11  11  11  11  13  13  13  11  13  13  13  11  13  13  13  7   11  11  11  11  13  13  13  11  13  13  13  11  13  13  13  9   13  13  13  13  15  15  15  13  15  15  15  13  15  15  15  9   13  13  13  13  15  15  15  13  15  15  15  13  15  15  15  9   13  13  13  13  15  15  15  13  15  15  15  13  15  15  15  7   11  11  11  11  13  13  13  11  13  13  13  11  13  13  13  9   13  13  13  13  15  15  15  13  15  15  15  13  15  15  15  9   13  13  13  13  15  15  15  13  15  15  15  13  15  15  15  9   13  13  13  13  15  15  15  13  15  15  15  13  15  15  15  7   11  11  11  11  13  13  13  11  13  13  13  11  13  13  13  9   13  13  13  13  15  15  15  13  15  15  15  13  15  15  15  9   13  13  13  13  15  15  15  13  15  15  15  13  15  15  15  9   13  13  13  13  15  15  15  13  15  15  15  13  15  15  15

Origin/background of Problem:
                              These number are generated from a divide and conquer algorithm. For example if we have a 8 bit binary-string and we are asked to find the location of 1's in minimal number of questions then, the above sequence is the # of questions asked for each possible binary 8-bit word i.e from 00000000, 00000001 ....11111111 the corresponding # of questions are elements of above sequence i.e 1,7,..15, respectively.

Algorithm:

Lets take 0000 0001, for instance:

1) First question: Is it (i-e 0000 0001) equal to ZERO (i-e 0000 0000) ? The answer is No, for our case.

2) Then divide the original 8 bit word into two 4 bit segments, and again ask the same question for each of the two 4 bit words. So for our case it would be YES for the first segment (0000) and NO for the other segment (0001)?

3) Now, this time I will be questioning only the segment where I got NO. In our case it was 0001. Then, I will now again divide  this 4-bit segment into two segments and pose the same question. Hence, is 00 equal to ZERO? answer : YES. For the other segment , 01, the answer is NO.

4) This is the final step. I will again divide the 2-bit word into two 1-bits, i-e 0 and 1. So, my first question: is 0 equal to 0? answer is YES. And for the other remaining bit, is 1 equal to 0? Answer is NO.

So, I asked a total of 7 questions to find the location of 1 in a binary word of 0000 0001. Similarly, we will go through other binary words.

Here is how to calculate the cost of the algorithm. Start with the bit vector $x$, and consider the following operation $O$, which divides $x$ into pairs of bits and computes their ORs. Thus $|O(x)| = |x|/2$. Compute a sequence $O(x),O(O(x)),O(O(O(x))),\ldots$ until you get a vector of width $1$. Count the total number of 1s in the sequence. If you got $N$, then the cost is $2N+1$.

For example, suppose $x=00010101$. Then the sequence is
$$ 0111, 11, 1, $$
and so $N = 6$ and the cost is $13$.


Prove key of leaf is larger or smaller than key of parent if leaf is largest key in smaller tree or smallest in larger tree with respect to parent Show that for any leaf v in a binary search tree, if u is the parent of v, then either key[v] is the largest key in the tree smaller than key[u], or key[v] is the smallest key in the tree larger than key[u].

I don't understand "key[v] is the largest key in the tree smaller than key[u]" and "key[v] is the smallest key in the tree larger than key[u]." Can someone help explain the problem to me?

In Order traversal sorts key in an ascending order. If $u$ is the parent of leaf $v$ then $v$ is either left or right child of $u$. If $v$ is left child then $key[v]\leq key[u]$ which implies $key[v]$ is the largest key in the tree smaller than $key[u]$. Similar intuition follows if $v$ is right child.


Winning strategy using Dynamic Programing Let $G=(V,E)$ be a DAG and let $v_0\in V$.
Alice and Bob are playing a game in which every player has his own turn and Bob is starting. In every turn $i$, the player is picking an edge $e=(v_i,x)$, then $x$ become $v_{i+1}$ and then it becomes the other player's turn. The player which doesn't have an edge to choose (the vertex $v_i$ has no out edges) is losing.

Propose an algorithm which determines if Bob has a winning strategy.

For a vertex $v \in V$, let $W(v)$ be the following predicate: "a player starting at $v$ wins". If $N(v)$ is the set of outward neighbors of $v$, then
$$
W(v) = \bigvee_{u \in N(v)} \lnot W(u),
$$
where the empty disjunction is simply false.

This suggests a strategy to compute $W(v_0)$ using dynamic programming.


How does a predictive coding aid in lossless compression? I'm working on this lab where we need to apply a lossless predictive coding to an image before compressing it (with Huffman, or some other lossless compression algorithm).

From the example seen below, it's pretty clear that by pre-processing the image with predictive coding, we've modified its histogram and concentrated all of its grey levels around 0. But why exactly does this aid compression?

Is there maybe a formula to determine the compression rate of Huffman, knowing the standard deviation and entropy of the original image? Otherwise, why would the compression ratio be any different; it's not like the range of values has changed between the original image and pre-processed image.

Thank you in advance,

Liam.

Huffman coding, as usually applied, only considers the distribution of singletons. If $X$ is the distribution of a random singleton, then Huffman coding uses between $H(X)$ and $H(X)+1$ bits per singleton, where $H(\cdot)$ is the (log 2) entropy function.

In contrast, predictive coding can take into account correlations across data points. As a simple example, consider the following sequence:
$$
0,1,2,\ldots,255,0,1,2,\ldots,255,\ldots
$$
Huffman coding would use 8 bits per unit of data, whereas with predictive coding we could get potentially to $O(\log n)$ bits for the entire sequence.


Why do we reject turing machines that use space less than the log of the length of the input? In Computational complexity: Modern Approach by Arora and Barak, it's mentioned that

  We will require however that $S(n)> \log n$ since the work tape has length $n$, and we would like the machine to at least be able to remember the index of the cell of the input tape that is currently reading.

What does that exactly mean? I don't see the point, what does "remembering the index of the cell currently read by the head of the input-tape" mean? Any clarifications?

Note that we does not count the movements of the input-tape into our space considerations so we only count for the work-tape

Consider any program in high-level language that has a loop going over all items:

for i from 1 to n
    do something
end for

Implementing this loop takes $O(\log n)$ work space, since the variable $i$ takes $O(\log n)$ bits to store. If you're not allowed to use even that much memory, then you have to be very careful when implementing any non-trivial algorithm, if it is possible at all; for instance, any results will be highly dependent on the exact definition of the model of computation.

Arora and Barak don't want to focus on such issues, so they just assume that you are given at least logarithmic space.  There are enough interesting things to say without having to worry whether some general reduction can be carried out in sublogarithmic space.  (And if you want to study regular languages -- languages that can be recognized with constant space -- you don't need complexity theory.)


Is exponentiation in P? I think the following problem belong to class P, but I don't know how I can prove it, could somebody help me?

Inputs: two numbers $(a,b) \in \mathbb{N}$
Output: $a^b$

Your problem is not in P, for two different reasons:

P is a class of decision problems, but your problem is a function problem.  Instead of P, you should consider its functional equivalent FP.
The output could be exponentially large in the input length: encoding $b$ takes about $\log b$ bits, but encoding $a^b$ takes about $b \log a$ bits.

This still leaves open the possibility that the following problem is in P:

  Given natural numbers $a,b$ and an index $i$, determine the $i$th bit of $a^b$.

While I don't know what the answer to this question is, here is a related problem in FP:

  Given natural numbers $a,b,c$, determine $a^b \bmod c$.

This can be shown using the important technique of repeated squaring.


Generalized geography game graph I'm studying the Sipser textbook for my theory of complexity class. In a part of the book (i.e., Space Complexity chapter), for showing that Generalized Geography game is PSPACE-complete, the author has given an argument to model this game with TQBF problem (which is proven to be PSPACE-complete).

In a step of the argument, he has tried to construct a directed graph by using the definitions of TQBF problem (universal and existential quantifiers). What he has come up with is the following graph:

I have some questions about this graph:

I, actually, don't get it why the diamond structure has been used for showing choice possibilities of player $x_i$. Couldn't we use a simple structure like what we do on binary trees?

How would it be if we use a hexagon shape instead of diamond for showing choices of $x_i$?

Your graph based on a binary tree would have exponential size (it would require at least $2^k$ nodes), which is probably no good for the reduction; an exponential blow-up in the size of the problem instance isn't ok.

Yes, you could use a hexagon instead of a diamond.  I don't see any advantage, but it would also provide a valid reduction.


Least number of guesses needed to determine all unknown subsets of a set Say I have a set $\mathbb{S}=\{1,2,...,n\}$. I have an adversary who breaks up $\mathbb{S}$ into $k$ unknown and disjoint subsets. Denote this new set $\mathbb{A}$. I can guess any combination $s$ and my adversary has to tell me if $s$ is itself a subset of any element in $\mathbb{A}$.

For example, if $n=4$, a valid $\mathbb{A}$ might be $\{ \{2\}, \{1,3,4\}\}$. All "true" guesses are $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$, $\{1,3\}$, $\{3,4\}$, $\{1,4\}$, $\{1,3,4\}$.

What's the fastest algorithm and the upper bound on number of guesses I need to make to fully reverse engineer $\mathbb{A}$?

Obviously the brute force algorithm takes $^nC_1 + ^nC_2 + ... + ^nC_n $ guesses for every possible subset.

But I think I only need to test all possible subsets of size 2 i.e. exactly $^nC_2$ guesses?

Then, I can represent each of the correct guesses of size 2 as an undirected edge in a graph. Every member of $\mathbb{A}$ of size 3 or greater should form a simple cycle in this graph. So I just need to DFS on every node in this graph, removing the longest cycle detected from the graph, and repeat for all remaining nodes until only lone edges (subsets of size 2) or unconnected vertices (subsets of size 1) remain.

This graph should have $n$ vertices and at most $^nC_2$ edges. So the fastest algorithm has a time complexity of $\mathbb{o}(n^{2}\cdot{}^{n}C_{2})$. Is there an approach with fewer guesses or a faster graph algorithm?

P.S.: In case anyone's interested about the context: One example use case is if $n$ known services are hosted on unknown $k$ servers with unknown grouping, and you have some way to overload any subset of services to mount a denial attack on a server. The problem becomes if you can profile the servers with the least number of queries. I came across a similar scenario and thought this was a pretty interesting problem with no literature on.

A simple algorithm may be:

Loop on:

take the next unassigned element Ei and create a new set Si assigning Ei to it.
loop on all unassigned elements Ej, testing the pair {Ei,Ej}. If it is true, assign j it to Si.

In worst case, this is O(kn) as you won't do this loop more than k times. In average case, I am not sure...


Proving that $L=\{ w \mid \lvert w \rvert$ is prime $\}$* is a regular language I'm trying to prove that the following languague is a regular language:
$L=\{ w \mid \lvert w \rvert$ is prime $\}$*
What I have thought is to divide each word $w \in L$ into subwords of length 2 if the word is even and and if the word is odd end with a suffix of length 3, in this way I would get the following regular expression:
(aa + ab + ba + bb)* (aaa + aba + abb + aab + baa + bab + bba + bbb + $\epsilon$)
Is my reasoning correct?
Otherwise I would appreciate so much any help.

In fact this follows from a general property of the star operation. When we start with an arbitrary language $L$ of all strings of certain lengths, then the star $L^*$ of that language is always regular. More precisely:

Let $A\subseteq \mathbb N$, and $L = \{w\in \Sigma^*\mid |w|\in A\}$.
Then $L^*$ is regular.

This is a consequence of a property of unary languages, i.e., languages over a single symbol. See this question:
If $L$  is a subset of  $\{0\}^∗$ , then how can we show that  $L^∗$  is regular?
So for $\Sigma = \{0\}$ the statement above is true. For larger alphabets perform an alphabetic substitution (say $\Sigma = \{a,b\}$, then in a regular expression for $L^*$ replace every $0$ by $(a+b)$).


Show the Language is Recursive I have devised the following TM for the language EQUAL.

EQUAL accepts all strings with the same number of a's and b's. It is context free but non regular.

Using the TM I devised, how can I show that EQUAL is recursive? How can I show that it crashes when the input is not in EQUAL.

A language is recursive if a Turing Machine decides it: On input w, the TM always halts, and accepts if w is in the language, and rejects if w is not in the language.

So to show that the language is recursive, you just need to show that your Turing Machine gives the correct answer on every input string (accepts if # of a's equals # of b's, rejects otherwise). That will also show that it halts on all inputs, so you're done.

As Hendrik says in the comment, a Turing Machine should have both an accept state and a reject state. (That's what it means to accept/reject -- to enter the appropriate state.)

So first, you'll need to make this change.

Then, to prove your construction correct, you use the following type of proof. First, suppose I have a string $w$ that does have an equal number of a's and b's. Then I will show that, when I feed $w$ into my TM, it halts in the accept state. Second, suppose I have a string $x$ that does not have an equal number of a's and b's. Then I will show that, when I feed $x$ into my TM, it halts in the reject state.

You should convince yourself that this proof accomplishes what I said is required above!

But note your TM is not quite there yet: Consider what will happen on input string "bbb"!


Cache strategies, what reference article could I study? So as to optimize an application, I must implement data caching: not to recompute some data - those heavy on cpu but that don't change often.

When playing with the idea, I imagined something like the way win32/MFC manages the windows screen i.e.:

While a part is valid, it is not repainted.
When a rectangle or a region is invalidated, this part is repainted during the next painting session - launched by the OS.

I was imagining a way to validate and invalidate my cached value, so as to recompute only what is necessary when it is necessary.

Then I read this wikipedia page about Cache Algorithms, and none of the listed algorithm was using the technique I explained above. So I feel ill at ease, and I need to read some work about caching.

Do you know of some resources that I could rely on before I start implementing my own cache process ?

The best strategy to find the best suitable algorithms for caching is to read survey papers in this area. I recommend the paper A survey of Web cache replacement strategies by Podlipnig and Böszörmenyi (2003) which reviews many general techniques for caching.


Why does the Pumping Lemma Constraint |xy| ≤ p mean that y can't be 1 in the string 0p1p I am trying to get my head around the Pumping Lemma to prove a language is non-regular.
I am reading the Sipser text book and he gives the following example.
Let B be the language $\{0^n 1^n | n \ge 0\}$
Let $s = 0^p 1^p$
I understand that the idea is you can split this string into xyz such that y can be pumped. It is the constraint of $|xy| \le p$ that is confusing me.
Sipser notes that due to this constraint y could not equal 01 nor could it equal 1. Why would y equaling either of those values violate the given constraint.
I am generally quite confused by the Pumping Lemma so any general advice or good resources you can recommend, I would appreciate.
Thanks!

Let $p$ be the pumping length of your language.
As you say, the string $s$ can be written as $s = xyz$ where $|xy| \le p$.
By the choice of $s=0^p 1^p$, you know that the first $p$ characters of $s$ are all $0$, therefore $xy$ (which contains at most $p$ character) must be a string containing only $0$s.
Since $y$ is a suffix of $xy$, $y$ must also contain only $0$s.


Inplace sorting of variable length records Is there an in-place algorithm for sorting variable length records?

For example a vector of arbitrary length strings.

Most provided in-place algorithms assume that you can switch two elements without affecting the rest of the structure.  However this does not work if your records differs in size.

Googling leads me to this. However, they finish with:

  After writing all sorted output blocks, merge them into the final sorted file using any convenient merging algorithm. When allocating buffers or making other preparations, the merging steps can take advantage of the fact that every variable-length block written by step 7 has the same maximum size (just less than the size of buffer 1 or 2)." I do not feel that doing in-place merging of arbitrary length records is in any way trivial.

If we're just dealing with packed variable-length records, swapping two adjacent elements is not difficult, so bubble sort will work.

There are some techniques for creating space while sorting to use for auxiliary data structures, based on the fact that (partially) sorted data has less entropy than unsorted.  See Radix Sorting With No Extra Space by Franceschini, Muthukrishnan, and Patrascu for examples.  They don't deal with variable length records specifically, but some of the ideas there might be useful.


Is there any algorithm so it can solve stable marriage problem with incomplete preference lists I have a slightly different formulation of the stable marriage problem. Basically, I can match one man to one woman, but the preference list is incomplete, which means that a man has expressed interest only in a subset of women and vice versa. I don't think the original Gale Shapley algorithm would work for this, if so what modifications do I need to make? If Gale Shapely does not work here, is there any algorithm to solve this? code suggestions, especially in python for this kind of problem, are very welcomed.

Men = [1, 2, 3, 4, 5]
Women = [a, b, c, d, e]

preferences:

men:
1: a, c, d
2: d, a, b
3: a, e, b
4: c, a, d
5: e, d, a

women:
a: 1, 3, 4
b: 4, 2, 5
c: 5, 1, 4
d: 3, 2, 1
e: 5, 3, 1

I need to match each man to one and only one woman

and the number of preferences allowed is fixed and less than the number of candidates.

I am not completely familiar with the problem, but maybe these couple of papers (or references therein) dealing with stable marriage with partial preferences (of which your setting could perceived as a special case) may be helpful:

https://www.math.unipd.it/~frossi/stc-care5-cr.pdf

https://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6840/6488


Inputting a superposition into a cNOT gate I am unsure how to calculate what happens when you put a superposition as the control qubit into a cNOT gate or what happens when  you put a superposition as the target qubit into a cNOT gate. I know what matrix represents the cNOT and I know that each superposition would be represented by $\alpha |00\rangle + \beta|01\rangle+\gamma|10\rangle+\delta|11\rangle$, but would you take these two four dimensional vectors and multiply them both by the cNOT matrix? If so, in what order? I just don't quite understand.

Any help would be appreciated. Thanks!

This is more of a question on linear algebra rather than a question about quantum computation. You should probably have a firm grip on basic linear algebra (vector spaces, linear operators, inner product, etc) before delving into quantum computation (there's no way around it).

CNOT is a linear operator in our vector space, $\mathbb{C}^4$ (were only dealing with linear transformations, specifically unitary). In order to specify how a linear transformation operates on an arbitrary vector, it is enough to specify how it operates on each member of a basis for our vector space. Suppose we apply some linear operator $T$ on an arbitrary superposition, then by linearity:

$T\left(\alpha |00\rangle + \beta|01\rangle+\gamma|10\rangle+\delta|11\rangle\right)=
\alpha T|00\rangle+\beta T|01\rangle + \gamma T|10\rangle + \delta T|11\rangle$

$T|ij\rangle$ is the application of the operator $T$ on the vector $|ij\rangle$. The application of a linear operator in a finite dimensional vector space can be described by matrix multiplication, so this means multiplying the matrix representing $T$ by the vector $|ij\rangle$. The "order" you refer to does not matter, because addition in a vector space is commutative.

Since you  know how to apply CNOT to the four basic states, the above equality shows you how to apply it on an arbitrary superposition.

When talking about matrix representation, the vector $\alpha |00\rangle + \beta|01\rangle+\gamma|10\rangle+\delta|11\rangle$ is represented by
$
\begin{pmatrix}
\alpha\\
\beta\\
\gamma\\
\delta
\end{pmatrix}
\in\mathbb{C}^4$, so applying CNOT to this state means multiplying it's matrix by this vector, i.e.

$CNOT\left(\alpha |00\rangle + \beta|01\rangle+\gamma|10\rangle+\delta|11\rangle\right)=
\begin{pmatrix}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 0 & 1\\
0 & 0 & 1 & 0
\end{pmatrix}
\begin{pmatrix}
\alpha\\
\beta\\
\gamma\\
\delta
\end{pmatrix}=
\begin{pmatrix}
\alpha\\
\beta\\
\delta\\
\gamma
\end{pmatrix}
$.

This is obviously equivalent to applying CNOT to each of the four vectors in $\mathbb{C}^4$ and adding up the results.


Is there a "well known" example of a constraint satisfaction problem on a 3-element set which is polynomial-time solvable? I'm basically looking for an example (in maybe graph theory) of a constraint satisfaction problem which has a 3-element set as a domain and the problem is known to be polynomial-time solvable.

If you want a graph, it needs to be bipartite. Hence the path of two edges or any subgraph thereof. (Here I am following the convention that graphs have no loops. As David Richerby points out in a comment, graphs with loops also have polynomial-time CSPs (by virtue of triviality).)

A more interesting example is linear algebra over the three-element field: The domain is the set of congruence classes $\bmod 3$ and the constraint relations are given by linear equations.


Design a 1-bit ALU using the smallest MUX possible Implement a one-bit ALU which takes two one-bit operands $a_0$, $b_0$, and produces a one-bit output $z_0$.  The ALU has a two-bit control input $cont_0$,   $cont_1$, with codes as shown below.

|$cont_0$|$cont_1$ |selects
|--- 0 ---|--- 0 ---| AND
|--- 0 ---|--- 1 ---| NOR
|--- 1 ---|--- 0 ---| OR
|--- 1 ---|--- 1 ---| XOR
(Sorry I didn't know how to make a properly formatted table)

The questions is:
Design the ALU using the smallest MUX possible.

I made a truth table as a start, then I came up with an ALU model, but I am not too confident with it. Any input on how to tackle this problem is appreciated.

Here's the truth table I made:

And here's the ALU that I'm doubtful about because it seems too easy of an approach.

If you consider the table as a 4 input combinational circuit and try to derive an expression from the K-map you will get
$$Z_0 = cont_0'cont_1a_0'b_0'+cont_0a_0b_0'+cont_0 a_0'b_0+cont_1'a_0b_0$$

Now you can see the pattern with $a_0$ and $b_0$ so you can make a smaller circuit with a 4x1 MUX having $a_0$ and $b_0$ as selection bit.


Find equivalent LTL formula, without Y (Yesterday) operator. How can I handle first state? The task is to find an equivalent LTL formula for $G(a \Rightarrow Yb)$, which doesn't contain the Y operator. My idea is to search for invalid path patterns with 2 $a$'s in a row, e.g. bbbbaab.

Therefore I'm thinking of $G(Xa \Rightarrow b)$, so whenever an $a$ occurs in the next state the the current state must be true for $b$. But I have a problem with the starting states. Consider a path starting with $a$, e.g. s3->s4->... this path would be false for the original formula (iv), since Yb is always false for the first state. But this exact state would be true for the formula $G(Xa \Rightarrow b)$.

How do I have to modify my formula to also cover the starting states correctly?

Initial states are somewhat of an anomaly. A similar problem is encountered in the $X$ operator when you try to define LTL over finite words. That is, it somehow would have made more sense to define PLTL over computations that are "infinite on both sides".

So, being an anomaly, it is probably easiest to treat it as such, and just explicitly deal with the initial state, requiring the first state not to have $a$.

Thus, an equivalent formula would be $G(Xa\to b)\wedge \neg a$.


Haskell: implementation issues of some basic features I'm taking a "Programming Language: Design and Implementation" course and our professor asked to make a case study about: Haskell programming language. In this case study he asks to make a report about: "implementation issues of some basic features. Can anybody list any good sources for this?

The Wikipedia article cites a wide range of sources and has a decent "Further reading" section.


Do you ever "download" a language? When one "downloads" a language (say, downloading the python file, or doing apt-get ruby or something), is it always the compiler/interpreter you are downloading?

In other words, does a "language" ever exist outside of its syntax and behavioral descriptions?

Perhaps standard libraries can be written in the language itself -- but other than that, would it be correct to say that we ever only "download" implementations of the language?

A programming language is a formal language, informally speaking a collection of words with a well-formed set of specific rules. As such, you can write down the definition of a formal language and thus a programming language on a piece of paper.

Also, if I've written down somehow digitally the definition of a programming language, surely you can represent and download that description. So then you might talk about an interpreter or a compiler for a language. That is not a programming language, that's an interpreter or a compiler. It's a program you might download.

If the question is "does a programming language exist outside of its description", the answer is no with the above definition: a programming language is defined by a formal language.


Effective computation on linear data without random access recently I've started thinking about caching problems in modern CPUs, where they struggle to adequately fetch program data (not instructions) in time, so that it can be computed further.
   So then I came up with the idea, why don't we restrict random access on program data and make it all as a continuous stream (input and all eventual locals), which moves strictly in one direction through some "processing head", where you only have a possibility to read in some x amount of symols, write, let through and append symbols at the head position (this is a data stream, not an instruction stream).
The question is, whether you can effectively run computations in that system:
    Is it possible to order all functions and allocate all local data/variables at compile time in such order that they will produce usable stream of data for all further functions, so that you will never need to "loop" the tape to access some particular element? (thus, emulating random access, by waiting for desired element to come by)
I've tried to look up this topic on the internet and found nothing. And maybe it is because this idea is obviously stupid, so no one bothers with it :)
Thank you for your help!

No.  Consider an algorithm on a graph (e.g., network flow).  It fundamentally requires random access to memory.  The restriction you propose would be painful and make many standard algorithms impossible.


How to show that a function is not computable? I know that there exist a Turing Machine, if a function is computable. Then how to show that the function is not computable or there aren't any Turing Machine for that. Is there anything like a Pumping lemma?

Before I answer your general question, let me first take a step back, give some history background, and answer a preliminary question: Do non-computable functions even exist?

[notational note: we can relate any function $f$ with a language $L_f=\{ (x,y) \mid y=f(x) \}$ and then discuss the decidability of $L_f$ rather than the computability of $f$]

Undecidable languages do exist

There are some languages that no Turing machine can decide. The argument is simple: there are "only" countably many $(\aleph_0)$ different TMs, but uncountably many $(\aleph)$ different languages. Thus there are at most $\aleph_0$ decidable languages, and the rest (infinitely many) are undecidable. Further reading:

"Why are there more non-computable functions than computable ones?" and
"Why are the total functions not enumerable?".

In order to put our hand on a specific undecidable language, the idea is to use a technique named diagonalization (Georg Cantor, 1873) which was originally used to show that there are more real numbers than integers, or in other words, that $\aleph > \aleph_0$.

The idea for constructing the first undecidable language is simple: we list all Turing machines (which is possible since they are recusively enumerable!), and create a language that disagrees with each TM on at least one input.

$$
\begin{array}{c|ccccc}
    & \varepsilon & 0 & 1& 00 & \cdots \\ \hline
M_1 & \color{red}{1} & 0 & 1 & 0 & 1 \\
M_2 & 0 & \color{red}{1} & 0 & 0 & 0 \\
M_3 & 0 & 0 & \color{red}{0} & 1 & 0 \\
\vdots & & & & \ddots &
\end{array}
$$

In the above, each row is one TM and each column is one input. The value of the cell is 0 if the TM rejects or never halts, and 1 if the TM accept that input.
We define the language $D$ to be such that $D$ contains the $i$-th input if and only if the $i$-th TM does not accept that input.

Following the table above, $\varepsilon \notin D$ since $M_1$ accepts $\varepsilon$. Similarly, $0\notin D$, but $1\in D$ since $M_3$ does not accept $1$.

Now, assume $M_k$ decides $D$ and look up line $k$ in the table: if there is $1$ in the $k$-th column, then $M_k$ accepts that input but it is not in $D$, and if there is a $0$ there, the input is in $D$ but $M_k$ does not accept it. Therefore, $M_k$ doesn't decide $D$, and we reached contradiction.

Now for your question. There are several ways to prove that a language is undecidable. I'll try to touch the most common ones.

1. Direct proof

The first method, is to directly show that a language is undecidable, by showing that no TM can decide it. This ususally follows the diagonalization method shown above.

Example.

  Show that the (complement of the) diagonal language
  $$\overline {L_D} = \{ \langle M \rangle \mid \langle M \rangle \notin L(M) \}$$
  is undecidable.

Proof.
Assume $\overline {L_D}$ is decidable, and let $M_D$ be its decider. There are two cases:

$M_D$ accepts $\langle M_D \rangle$: but then, $\langle M_D \rangle \in L(M_D)$ so $\langle M \rangle \notin \overline {L_D}$. So this can't happen if $M_D$ decides $\overline {L_D}$.
$M_D$ does not accept $\langle M_D \rangle$: so
$\langle M_D \rangle \notin L(M_D)$ and thus $\langle M \rangle \in \overline {L_D}$. But if it is in $L_D$, $M_D$ should have accepted it, and we reached contradiction again.

2. Closure properties

Sometimes we can use closure properties to show some language is not decidable, based on other languages we already know not to be decidable.

Specifically,
if $L$ is not decidable (we write $L\notin R$), then also its complement $\overline{L}$ is undecidable: if there is decider $M$ for $\overline{L}$ we could just use it to decide $L$ by accepting whenever $M$ rejects and vice versa. Since $M$ always halts with an answer (it is a decider), we can always invert its answer.

Conclusion: The diagonal language ${L_D} = \{ \langle M \rangle \mid \langle M \rangle \in L(M) \}$ is undecidable, $L_D \notin R$.

A similar argument can be applied by noting that if both $L$ and its complement $\overline{L}$ are recursively enumerable, both are decidable. This is particular useful if we want to prove that a language is not recursively enumerable, a strong property than undecidability.

3. Reducing from an undecidable problem

Usually, it's quite difficult to directly prove that a language is undecidable (unless it is already constructed in a "diagonal" fashion). The last and most common method for proving undecidability is to use another language which we already know to be undecidable. The idea is to reduce one language to another: to show that if one is decidable, then the other must also be decidable, but one of them is already known to be undecidable which leads to the conclusion that the first one is also undecidable. Read more about reductions in  "What are common techniques for reducing problems to each other?".

Example.

  Show that the diagonal language
  $$HP = \{ \langle M,x \rangle \mid M \text{ halts on } x \}$$
  is undecidable.

Proof.
We know that $L_D$ is undecidable. We reduce $L_D$ to $HP$ (this is denoted $L_D \le HP$), that is, we show that if $HP$ was decidable we could use its decider to decide $L_D$, which is a contradiction.

The reduction works by converting a candidate $w$ for $L_D$ (i.e. an input for any potential decider/acceptor for $L_D$) to a candidate $w'$ for $HP$ such that $w\in L_D$ if and only if $w' \in HP$. We make sure that this conversion is computable. Thus, deciding $w'$ tells us whether or not $w\in L_D$, so if we can decide HP we would be also able to decide $L_D$.¹

The conversion is as follows. Take some $w=\langle M \rangle$, and output $w'=\langle M' , \langle M \rangle\rangle$,² where $M'$ is a TM that behaves just like $M$, but if $M$ rejects, then $M'$ goes into an infinite loop.

Let's see that $w,w'$ satisfy the requirements.
If $w\in L_D$, it means that $M$ halts and accepts the input $\langle M\rangle$. Therefore, $M'$ also halts and accepts the input $\langle M\rangle$.
Thus, $\langle M', \langle M\rangle \rangle \in HP$.
On the other hand, if $w\notin L_D$ then $M$ either rejects or never halts on $\langle M\rangle$. In both cases $M'$ will go into an infinite loop on $\langle M\rangle$. Thus, $\langle M', \langle M\rangle \rangle \notin HP$, and we are done showing that $w\in L_D$ if and only if $w'\in HP$, and have thus shown that $HP\notin R$.

Further reading: many examples for reductions and proving undecidablility of languages can be found via the reductions tag.

There are some more restriction on the reduction to be valid. The conversion itself must be computable, and well defined for any input.
An input of $HP$ looks like $\langle M,x\rangle$, where $M$ is a TM and $x$ is some string. So here we choose the string $x$ to be an encoding of the machine $M$, which is just some string..

4. Rice's Theorem

"So every time we wish to prove $L$ is undecidable, we need to reduce $L_D$ (or $HP$) to it? Isn't there any shortcut?"

Well, in fact, there is. This is Rice's Theorem.

The theorem says that many languages that have a certain structure, are undecidable. Because all these languages have this certain structure, we can do the reduction once and apply it to any language that admits a similar structure.

The theorem is formally stated in the following way,

  Theorem (Rice).  Given a property $\emptyset \subsetneq S \subsetneq RE$, the following language $L_S$ is undecidable
  $$ L_S = \{ \langle M \rangle \mid L(M) \in S  \} $$

The set $S$ is a subset of languages in $RE$; we call it a property because it describes a property of the accepted language $L(M)$. All the TMs whose language satisfies this property belong to $L_S$.

For instance, $S$ can be the property that the accepted language $L(M)$ contains exactly two words:

  $$S_2 = \{ L \mid |L| =2 , L \in RE\}.$$
  In this case $L_{S_2}$ is the set of all TMs whose language consists of exactly two words:
  $$L_{S_2} = \{\langle M \rangle \mid L(M) \in S\} = \{\langle M \rangle \mid |L(M)|=2\}.$$

The property can be very simple, but it cannot be all the RE languages, or none of the RE languages. If $S=\emptyset$ or $S=RE$ then the property is said to be trivial, and the induced $L_S$ is computable. An example for a simple $S$ is one the contains only a single language, say $S_{complete}=\{ \Sigma^*\}$. Note that although $S$ contains only a single language, there are infinitely many machines $M$ whose language is $\Sigma^*$, so $L_{S_{compete}}$ is infinite, and undecidable.

The theorem is very powerful to prove undecidability of many languages.

Example.

  The language $L_\emptyset = \{ \langle M \rangle \mid M \text{ never reaches the accepting state} \}$, is undecidable

Proof.
We can write $L_\emptyset$ as $\{ \langle M \rangle \mid L(M)=0 \}$, that is $L_\emptyset=L_S$ for the property $S=\{ L \in RE, |L|=0\}$. This is a non-trivial property (it includes the language $L=\emptyset$, but does not include, for instance, the language $L=\{1, 11, 111,\ldots\}$. Therefore, by Rice's Theorem, $L_\emptyset$ is undecidable.

We now prove the theorem. As mentioned above, we are going to show a reduction from $HP$ to $L_S$ (for any arbitrary non-trivial $S$).

Proof.
Let $S$ be a non-trivial property, $\emptyset \subsetneq S \subsetneq RE$. We show $HP \le L_S$, that is, we reduce $HP$ to $L_S$ so that if we can decide $L_S$ we will be able to decide $HP$ (which we know to be impossible, therefore, $L_S$ cannot be decidable). In the proof below we assume that the empty language is not part of $S$, that is $\emptyset \notin S$. (if the empty language is in $S$, an equivalent proof works on the complement property $\overline S = RE \setminus S$, I'll omit the details). Since $S$ is nontrivial, it includes at least one language; let's call that language $L_0$ and assume $M_0$ is a machine that accepts $L_0$ (such machine exists, since $S$  includes only languages in RE).

Recall that in such a reduction (See section 3 above), we need to show how to convert an input $w$ for $HP$ into an input $w'$ for $L_S$ so that
$$ w\in HP \quad \text{ if and only if }\quad w' \in L_S$$

Let $w=(\langle M \rangle, x)$, we convert it into $w'=\langle M' \rangle$ where the description of the machine $M'$ (on an input $x'$) is the following:

Run $M$ on $x$.
If Step 1 above halts, run $M_0$ on $x'$ and accept/reject accordingly.

We see that this conversion is valid. First note that it is simple to construct the description of $M'$ given $w=(\langle M \rangle, x)$.

If $w\in HP$, then $M$ halts on $x$. In this case, $M'$ proceeds to step 2, and behaves just like $M_0$. Therefore its accepted language is $L(M')=M_0\in S$. Therefore, $w'=\langle M' \rangle \in L_S$.
If $w\notin HP$ then $M$ loops on $x$. This case, $M'$ loops on any input $x'$ — it gets stuck in step 1. The language accepted by $M'$ in this case  is empty, $L(M')=\emptyset \notin S$. Therefore, $w'=\langle M' \rangle \notin L_S$.

4.1 The Extended Rice Theorem

Rice's theorem gives us an easy way to show that a certain language $L$ that satisfies certain properties is undecidable, that is, $L \notin R$. The extended version of Rice's theorem allows us to determine whether the language is  recursively-enumerable or not, that is, determines whether $L \notin RE$, by checking if $L$ satisfies some additional properties.

  Theorem (Rice, extended).  Given a property $S \subseteq RE$, the  language
  $$ L_S = \{ \langle M \rangle \mid L(M) \in S  \} $$
  is recursively-enumerable ($L_S \in RE$) if and only if all the following three statements jointly hold

  For any two $L_1, L_2 \in RE$, if $L_1 \in S$ and also $L_1 \subseteq L_2$ then also $L_2 \in S$.
  If $L_1\in S$ then there exists a finite subset $L_2 \subseteq L_1$ so that $L_2 \in S$.
  The set of all finite languages in $S$ is enumerable (in other words: there is a TM that enumerates all the finite languages $L\in S$).

Proof.
This is an "if and only if" theorem, and we should prove both its directions. First, we show that if one of the conditions (1,2,3) does not hold, then $L_S \notin RE$. After that we will show that if all three conditions hold simultaneously, then $L_S \in RE$.

If (1,2) hold, but (3) does not, then $L_S \notin RE$.
Let's assume that $L_S \in RE$, and we'll see that we have a way to accept any finite languages in $S$ (and thus, the set of all these languages is RE), thus condition (3) holds and we reach a contradiction. How to decide if a finite $L$ belongs to $S$ or not? Easily – we use the description of $L$ to construct a machine $M_L$ that accepts only the words in $L$, and now we run the machine of $L_S$ on $M_L$ (remember - we assumed $L_S\in RE$, so there is a machine that accepts $L_S$!). If $L\in S$ then $\langle M_L \rangle \in L_S$ and since $L_S\in RE$, its machine will say yes on the input $\langle M_L \rangle$, and we are done.

If (2,3) hold, but (1) does not, then $L_S \notin RE$.
We assume that $L_S \in RE$ and we'll show that we have a way to decide $HP$, leading to a contradiction.

Because condition (1)  doesn't hold, there is a language $L_1 \in S$ and a superset of it, $L_2 \supseteq L_1$ so that $L_2 \notin S$. Now we are going to repeat the argument used in Section 4 to decide $HP$: given an input $(\langle M \rangle,x)$ for $HP$, we construct a machine $M'$ whose language is $L_1$ if $(\langle M \rangle,x)\notin HP$ or otherwise, its language is $L_2$. Then, we can decide $HP$: either $M$ halts on $x$, or the RE-machine for $L_S$ accepts $M'$; we can run both in parallel and are guaranteed that at least one will halt.

Let's give the details of constructing $M'$ (on input $x'$):

Do the following in parallel:
1.1 run $M$ on $x$.
1.2 run the machine of $L_1$ on $x'$
If 1.2 halts and accepts - accept.
If 1.1 halts: run the machine of $L_2$ on $x'$.

Why does this work?
If $(\langle M \rangle,x)\notin HP$ then 1.1 never halts, and $M'$ accepts exactly all the inputs that are being accepted at step 1.2, so $L(M')=L_1$.
On the other hand, if $(\langle M \rangle,x)\in HP$ then, at some point step 1.1 halts and $M'$ accepts exactly $L_2$. It may happen that $1.2$ accepts beforehand, but since $L_1 \subseteq L_2$, this doesn't change the language of $M'$ in this case.

If (1,3) hold, but (2) does not, then $L_S \notin RE$.
Again, we will assume $L_S\in RE$ and show that $HP$ becomes decidable, which is a contradiction.

If condition (2) doesn't hold, then for any $L_1\in S$, all its finite subsets $L_2 \subseteq L_1$ satisfy $L_2 \notin S$ (note that $L_1$ must be infinite, since $L_1\subseteq L_1$).
As in the above, in order to decide $HP$ for a given input $(\langle M \rangle,x)$, we construct a machine $M'$ whose language is $L_1$ if $(\langle M \rangle,x)\notin HP$ and some finite $L_2$ otherwise. The contradiction follows in a similar way as above.

The construction of this machine is quite similar to the previous $M'$ we constructed. The machine $M'$ (on input $x'$) does:

Runs $M$ on $x$ for $|x'|$ steps.
If $M$ halts during step 1 – reject
Otherwise, run the machine of $L_1$ on $x'$.

It holds that, if $(\langle M \rangle,x)\in HP$, then at some point, say after 1000 steps, $M$ halts on $x$. Therefore, step 1 will halt on (and reject) any input $x'$ of length $>1000$. Therefore, in this case, $L(M')$ is finite. Also note that $L(M') \subseteq L_1$, and in particular, by our assumptions on the invalidity of condition (2), we have that $L(M) \notin S$.

On the other hand, if $(\langle M \rangle,x)\notin HP$, then step 1 never halts, and we never reject at step 2. In this case it is easy to see that $L(M)=L_1$ and in particular, $L(M)\in S$.

We are left to show the other direction of the extended theorem. That is, we need to show that if all the conditions (1,2,3) hold, then we have a TM that accepts $L_S$, that is, $L_S \in RE$. In other words, we need to show a machine $M_S$ so that for any input $\langle M \rangle$ for which $L(M) \in S$, the machine accepts this input, $M_S(\langle M \rangle) \to \textsf{accept}$.

Here is how the machine $M_S$ behaves (on input $\langle M \rangle$):

Let $M_{\text{enum }S}$ be the machine that enumerates all the finite languages in $S$, guaranteed by condition (3).
Run the following in parallel (by dovetailing, see e.g., this and this) for $i=1,2,...$
2.1 Run $M_{\text{enum }S}$ until it outputs the language $L_i$
2.2. Check if $M$ accepts all the words of $L_i$ (run $M$ on these words, again in parallel).
2.3. If for some $i$, $M$ accepts all the words of $L_i$ – accept.

Why does it work?
If $L(M) \in S$ then it has a finite subset $L_j \in S$, and once $M_{\text{enum }S}$ outputs that subset, step 2.2/2.3 will find that $M$ accepts all the words in that language and accept.

On the other hand, if $L(M) \notin S$ it cannot be accepting all the words in $L_i$ for any $i=1,2,...$. Indeed, by condition (1), any $L' \supseteq L_i$ is also in $S$, so if $M$ accepts all the words in $L_i$ for some $i$, then $L(M)\supseteq L_i$ and thus $L(M) \in S$, in contradiction.

Finally, note that the following is a simple (and very useful) corollary of the above:

  Corollary (Rice, extended).  Given a non trivial property $S \subsetneq RE$, so that $\emptyset \in S$, the  language
  $$ L_S = \{ \langle M \rangle \mid L(M) \in S  \} $$
  is not recursively-enumerable, that is, $L_S \notin RE$.


non-deterministic finite automaton state transition table language question I have the nfa problem below which I dont quite understand. I have been reading many slides on this but I'm having a really hard time understanding them enough to be able to complete the question. I can see that on the $q_0 $ state when we have an $a$ it should stay in the $q_0$ state and for the $q$ state when we have an $a$ it should go to the $q_0$ state but still dont understand the other information given well enough to construct the diagram.

If anyone could help me understand the problem below it would be much appreciated.

Starting from the $M$ you gave in a comment (which you should really include in the question), we have the transition table
$$\begin{array}{r|cc}
\delta & 0  & 1 \\ \hline
q_0    & q_1 & q_2\\
q_1    & q_0 & q_2\\
q_2    & q_2 & q_2
\end{array}$$
with $q_0$ the start state and $q_1$ the final state. Now we modify this to a new NFA $M'$ by adding another final state $q'_0$ and construct the transitions $\delta'$:

$\delta'(q'_0, 0) = \{\delta(q_0, 0), q_0\}=\{q_1,q_0\}$, since $\delta(q_0,0)=q_1\in F$
$\delta'(q'_0, 1) = \{\delta(q_0, 1)\}=\{q_2\}$, since $\delta(q_0,1)=q_2\notin F$
$\delta'(q_0, 0) = \{\delta(q_0, 0), q_0\}=\{q_1,q_0\}$, since $\delta(q_0,0)=q_1\in F$
$\delta'(q_0, 1) = \{\delta(q_0, 1)\}=\{q_2\}$, since $\delta(q_0,1)=q_2\notin F$
$\delta'(q_1, 0) = \{\delta(q_1, 0)\}=\{q_0\}$, since $\delta(q_1,0)=q_0\notin F$
$\delta'(q_1, 1) = \{\delta(q_1, 1)\}=\{q_2\}$, since $\delta(q_1,0)=q_2\notin F$
$\delta'(q_2, 0) = \{\delta(q_2, 0)\}=\{q_2\}$, since $\delta(q_2,0)=q_2\notin F$
$\delta'(q_2, 1) = \{\delta(q_2, 1)\}=\{q_2\}$, since $\delta(q_2,0)=q_2\notin F$

giving us this transition table for $M'$
$$\begin{array}{l|cc}
\delta'     & 0           & 1 \\ \hline
\{q'_0\}    & \{q_0,q_1\} & \{q_2\}\\
\{q_0\}     & \{q_0,q_1\} & \{q_2\}\\
\{q_1\}     & \{q_0\}     & \{q_2\}\\
\{q_2\}     & \{q_2\}     & \{q_2\}\\
\{q_0,q_1\} & \{q_0,q_1\} & \{q_2\}
\end{array}$$
with $\{q'_0\}$ the start state and $\{q'_0\}, \{q_1\}, \{q_0,q_1\}$ the final states. Notice that $\{q_0\}$ and $\{q_1\}$ are unreachable so can be eliminated from the NFA. Notice also that in both FAs, state $q_2$ is a "trap" state: once you enter it (on input $1$), you'll never leave. This means that neither FA will accept any string containing a $1$ and from there it's not too hard to see what $L(M)$ and $L(M')$ are.