When solving dynamic programming in a grid, how do you recognize whether the solution should start at the bottom-right of the table or top-left? Example of start top-left, Coin Collecting problem in grid:
https://www.youtube.com/watch?v=94FEC_uNwVM

Example of start bottom-right, Dungeon Game problem in grid: https://leetcode.com/problems/dungeon-game/description/

I knew the Coin Collecting problem, so I started trying to solve Dungeon Game the same way, starting from the top-left (although it can also be solved bottom-right). Turns out Dungeon Game is solved from the bottom-right. How do I recognize this earlier?

function initTable(m, n, f) {
  var T = [];
  for (var r = 0; r < m; r++)
    T.push(Array(n).fill(f));
  return T;
}

var grid = [
  [-2,-3,3],
  [-5,-10,1],
  [10,30,-5],
];

function calculateMinimumHPFromTopLeft(dungeon) {
    var M = dungeon.length;
    var N = dungeon[0].length;

    var hp = initTable(M+1, N+1, Number.POSITIVE_INFINITY);
    hp[0][1] = 1;
    hp[1][0] = 1;

    for (var i = 1; i < M+1; i++) {
        for (var j = 1; j < N+1; j++) {
            var need = Math.min(hp[i-1][j], hp[i][j-1])-dungeon[i-1][j-1];
            hp[i][j] = need <= 0 ? 1 : need;
        }
    }

    return hp[M][N];
}

function calculateMinimumHPFromBottomRight(dungeon) {
    var M = dungeon.length;
    var N = dungeon[0].length;

    var hp = initTable(M+1, N+1, Number.POSITIVE_INFINITY);
    hp[M][N-1] = 1;
    hp[M-1][N] = 1;

    for (var i = M-1; i >= 0; i--) {
        for (var j = N-1; j >= 0; j--) {
            var need = Math.min(hp[i+1][j], hp[i][j+1])-dungeon[i][j];
            hp[i][j] = need <= 0 ? 1 : need;
        }
    }

    return hp[0][0];
}

console.log(calculateMinimumHPFromTopLeft(grid))   // 6 (wrong)
console.log(calculateMinimumHPFromBottomRight(grid))  // 7 (correct)

If a cell depends on cells to its left and bottom, the solution should start at the bottom-left. And so on for all other combinations of left/right and top/bottom.


Robot follows a path near an obstacle without colliding I have a problem that I would like to solve it. A robot have to move near an obstacle (e.g a wall) without colliding. He should also try to be always near the obstacle.
The following picture can help you to understand what I need to do:

In red is the wall
Black dots is the robot moving
The dashed line is the path of the robot

The robot doesn’t have any information about the wall. He has only a sensor that can tell him approximately what the distance to the wall is.
A perfect robot is a robot who can move within a distance of 1m to the wall.  The robot some times doesn’t respect that distance:

The distance can be sometimes  > 1m
The distance can be less often < 1m
The robot can collide but it should be very rare and it is better to
avoid it all the time.

Do you have a solution for this problem?
I am new to AI and there is a lot of material to read. So on which topic of AI should I concentrate to find a solution for this problem?

Robot Motion Planning is an important topic in Computational Geometry. There have been a lot of research in this field.

Here are some pointers that might help you:

Slide: http://www.mpi-inf.mpg.de/departments/d1/teaching/ss10/Seminar_CGGC/Slides/06_Bazhenova_RMP.pdf

Slide: http://www.cs.cmu.edu/afs/cs/academic/class/15381-s07/www/slides/020807motion.pdf

Book: http://books.google.com/books?hl=en&lr=&id=_VRM_sczrKgC&oi=fnd&pg=PR11&dq=robot+motion+planning&ots=zFkR07oxBJ&sig=efsVfaDPAlhKgxZwClKS136moCI#v=onepage&q=robot%20motion%20planning&f=false

Website: http://correll.cs.colorado.edu/?p=965


NFA to recognize bit strings containing 01111110 Basically, I currently have two ideas but unsure on which is correct for the following question:
"The High level data link control protocol (HDLC), is a popular protocol used for point-to-point data communication. In HDLC, data are organised into frames which begin and end with the sequence 01111110. This sequence never occurs within the main body of the frame, only at the beginning and end (in order to avoid confusion).

a.)Design an NFA which recognises the language of binary strings which contain one or more HDLC frames"

My possible solutions:

The next part is to convert to DFA, but I first need to get this part right.

Might as well go for a DFA directly.

First, recognize the string 01111110. If you see something you don't expect, then the information is malformed and you should enter a dead state.

Once you've seen 01111110, start looking for 01111110 again, but this time, if you see something you don't expect, begin looking for 01111110 again from scratch. Once you see a complete 01111110, you have consumed an entire frame, and you should be in an accepting state.

Then, from this halting state, we add the same transitions we have on our initial state; i.e., we leave open the possibility that there are additional frames. Here's a transition table corresponding roughly to what I've indicated:

  State     Input     New State
  q0        0         q1
  q0        1         dead
  q1        0         dead
  q1        1         q2
  q2        0         dead
  q2        1         q3
  q3        0         dead
  q3        1         q4
  q4        0         dead
  q4        1         q5
  q5        0         dead
  q5        1         q6
  q6        0         dead
  q6        1         q7
  q7        0         q8
  q7        1         dead
  // we've seen the leading 01111110
  q8        0         q9
  q8        1         q8
  q9        0         q9
  q9        1         q10
  q10       0         q9
  q10       1         q11
  q11       0         q9
  q11       1         q12
  q12       0         q9
  q12       1         q13
  q13       0         q9
  q13       1         q14
  q14       0         q9
  q14       1         q15
  q15       0         q16
  q15       1         q8
  // we have now seen the trailing 01111110, a whole frame
  // q16 is the only accepting state.
  q16       0         q2
  q16       1         dead

Naturally, you'll want to check that very carefully. If the goal is outputting the message in between the leading and trailing patterns, you might need some extra states to remember input symbols that may or may not be part of the trailing pattern; but for accepting input which consists of a finite number of valid frames, this (or something close to it, if I've made a silly blunder) should be enough.


Left quotient finite automata This is very unclear to me. I understand what the left quotient is, however, can someone explain this:

A={0,101}
B=01,10,001}

then how is A\B={1,01}

I mean where are these strings extracted from? I dont see them in A. How can I appeand 01 to anything is B to get something in B?

By definition, $A \backslash B$ is the set of all strings $x$ such that $ax \in B$ for some $a \in A$. In our case, $1 \in A \backslash B$ since $01 \in B$ and $0 \in A$, and $01 \in A \backslash B$ since $001 \in B$ and $0 \in A$.


Proving non-confluency and adding an equation to make it confluent and terminating I currently have a system that has {f(a) = b, f(f(x)) = x} (part of an exam question - look at page 5 - exercise 1).

To start off with proving non-confluency, I am thinking along these lines:

f(f(x)) and f(a) can be unified by using {a -> f(x)}.

Then we can rewrite:

f(f(x)) = x                 [eq.1]
f(f(x)) = b                 [eq.2]

The above two cannot be reduced any further, and do not have any common ancestor or successor. Therefore the system is not confluent.

To make this confluent, we can add a third equation to the system:

x = b

This way, the equation will both be confluent and terminate. Another alternative would be:

f(x) = b

Is there anything I have missed? Or is this pretty much the gist of it?

The notion you are looking for is that of critical pair (see the wikipedia entry for instance). The idea is to find the "most simple" term which allows both rewrite rules to be applied. In this case the rewrite rules are:

$$ f(f(x))\rightarrow x$$
$$ f(a) \rightarrow b$$

To find a critical pair, you look for the most general (in a precise sense) instance of the variables on the left-hand side which allow one term to be the (non-trivial) subterm of another. In this case, we can instantiate $x$ to $a$ and obtain

$$ a\leftarrow f(f(a)) \rightarrow f(b)$$

This is a most general instantiation: we can't apply both rules if $x$ isn't sent to $a$. The equations you gave imply $a = f(b)$. To obtain a confluent rewrite system, we therefore need to add one of two rules:

$$ a \rightarrow f(b)$$
or
$$ f(b)\rightarrow a $$

Note that either rule will not make more terms equal, as the equality already holds! We can choose either rule to add to our system, but it is tempting to add the second one, as it seems more "computational". Now you have made your critical pair harmless: $f(f(a))$ rewrites to $a$ regardless of our choice of rule applications.

But we are not done! We have a new critical pair:

$$ b\leftarrow f(f(b))\rightarrow f(a)$$

However that critical pair is harmless, as both sides reduce to $b$.

Now every critical pair is harmless, and so we have verified the property of local confluence. This by itself is not enough to have confluence! However in your case, you have the additional property of termination: no term has an infinite rewrite sequence. This, in combination with local confluence, implies confluence, thanks to Newman's lemma.

Note that this whole approach (find critical pairs, add rewrite rules, check for termination, repeat) can be made systematic, to attempt turning any rewrite system into a terminating one; it is often called Knuth-Bendix completion.


Modifying Dijkstra’s algorithm to favor the path with least amount of edges I need to modify the Dijkstra's algorithm to get the shortest path in a directed graph and get the one with the least amount of edges if there are equal paths.

I am thinking to add another data field to count the number of edges from start and compare them in same way as weights. Would that work?

Yes, it should. You can simply keep a count of edges traveled. If you discover a new shortest path which is of the same distance as the last shortest path, make an if statement asking whether or not the new path has less number of edges. Here is a short pseudo code that you can use in the "relaxation" part of algorithm.

if (new_path == shortest_path && new_path_edges < shortest_path_edges)
    shortest_path= new_path
elseif (new_path < shortest_path)
    //The relaxation part of Dijkstra's algorithm

EDIT. Fuller answer below.

 1  function Dijkstra(Graph, source):
 2      for each vertex v in Graph:
 3          dist[v]      := infinity;
            dist_edges[v]:= 0;
 4          visited[v]   := false;
 5          previous[v]  := undefined;
 6      end for
 7
 8      dist[source]  := 0;
        dist_edges[source] := 0;
 9      insert source into Q;
10
11      while Q is not empty:
12          u := vertex in Q with smallest distance in dist[] and has not been visited;
13          remove u from Q;
14          visited[u] := true
15
16          for each neighbor v of u:
17              alt := dist[u] + dist_between(u, v);
                alt_edges := dist_edges[u] + 1; //Note the increment by 1
                if (alt = dist[v] && alt_edges < dist_edges[v])
                    previous[v] := u;
                    dist_edges[v]= alt_edges
18              if alt < dist[v]:
19                  dist[v]  := alt;
                    dist_edges[v] := alt_edges;
20                  previous[v]  := u;
21                  if !visited[v]:
22                       insert v into Q;
23                  end if
24              end if
25          end for
26      end while
27      return dist;
28  endfunction


set cover to edge cover I want to find set cover of this problem.
I have sets, each of cardinality 3. I want to find set cover.
This is what I am doing.
Treat each set as an edge, which is incident on each of its element.
I am considering each element as a vertex.
Now I will find minimum edge cover of this graph(hyperGraph).
Is this the right way to do?

Yes. This is a right and possible way to go.

One can also consider the formulation of the set cover problem as an Integer Program, using the LP relaxation of such program you can obtain what is referred as $f$-approximation. Details and analysis can be found in most standard books on approximation algorithms.


Is P closed under subwords? Given a language $L\subseteq \Sigma^*$ in $P$, is the language

$subwords(L) = \{v\in\Sigma^* : \text{there exist } u,w\in \Sigma^* \text{ with } uvw\in L\}$

that consists of all subwords of words in $L$ also guaranteed to lie in $P$?

Hint: Let $L$ be the language consisting of a description of a Turing machine (bounded by $\#$ on both sides) followed by a terminating computation (both description and computation are over $\{0,1\}$). What is the language $\mathit{subwords}(L) \cap \#\Sigma^*\#$?


Find Optimal Permutation/Positioning to Minimize the Total Distance for a Given Path Summary:
A task for picking certain objects is given in the form of an ordered sequence (eg. to pick apple, banana, apple, apple, orange, order matters). The objects have to be preassigned to certain physical locations with all the pairwise distance being known and fixed. The question is how to efficiently find the best location assignment so that the total traveling distance is minimized.
What I Have Tried:
I cannot map this problem to any other algos that I know. For example, Dijkstra is to find the path given the graph, Knapsack is to find the right combination which the order doesn't matter.

I posted this question on Stackoverflow
I wrote an article on my blog to describe the problem in more detail for your reference
I wrote a script to demonstrate how to find the optimal position assignment in a brute force way for a small number of objects.

Right now, this is at a complexity I believe of O(n!) and will totally explode as we increase the number of different objects.
# task is a sequence of order picking
task = '1212103' # means first pick up obj1, then obj2, then obj1, ..etc.

result = []
for c in permutations(range(4), 4):
    # c contains the positions for all objects
    # (1, 0, 2, 3) means obj0 stored at pos1, obj1 stored at pos0, etc.
    res = 0

    for f,t in zip(task, task[1:]):
        pos_f = c[int(f)]
        pos_t = c[int(t)]
        # abs(...) is one oversimplief way to calculating distance between two positions
        # in a 1d space for demonstration purpose
        res += abs(pos_f - pos_t)
    result.append((c, res))

And the outputs are all the permutations and the total distance:
[((1, 2, 3, 0), 6),   # optimal position assignment #1 the yields the shortest distance
((2, 1, 0, 3), 6),    # optimal position assignment #2 the yields the shortest distance
((0, 2, 3, 1), 7),
((1, 3, 2, 0), 7),
((2, 0, 1, 3), 7),
((3, 1, 0, 2), 7),
((0, 1, 2, 3), 8),
((0, 3, 2, 1), 8),
((3, 0, 1, 2), 8),
((3, 2, 1, 0), 8),
((0, 2, 1, 3), 9),
((3, 1, 2, 0), 9),
((0, 1, 3, 2), 11),
((1, 0, 2, 3), 11),
((1, 2, 0, 3), 11),
((2, 1, 3, 0), 11),
((2, 3, 1, 0), 11),
((3, 2, 0, 1), 11),
((0, 3, 1, 2), 13),
((3, 0, 2, 1), 13),
((1, 0, 3, 2), 14),
((2, 3, 0, 1), 14),
((1, 3, 0, 2), 15),
((2, 0, 3, 1), 15)]

Let us call your problem as $TD$ (Total Distance problem).
Now, we will show that there is a polynomial-time reduction from the $k$-clique problem to $TD$. Note that, the $k$-clique problem is $NP-hard$ and is defined as follow:

Given an undirected graph $G_{C} = (V_{C},E_{C})$. Does there exist a clique of size $k$ in $G_{C}$?

The reduction from $k$-Clique to $TD$ happens in the following way:
Define a complete weighted undirected graph $G = (V,E)$ such that $V = V_{C}$ and for an edge $(u,v) \in E$, the weight $w(u,v) = \infty$ if $(u,v) \notin E_{C}$, and $w(u,v) = 1$ if $(u,v) \in E_{C}$. Here, the vertex set $V$ represents the set of locations and weight on an edge represents the travelling cost between two locations.
A $k$ size clique can be easily stated by some object sequence $S$. For example, suppose $k = 4$, then the object sequence would be: $S = (1,2,3,4,1,3,4,2)$. Similarly, for $k = 5$, the object sequence would be: $S = (1,2,3,4,5,1,3,5,2,4,1)$. Note that, we have $n$ number of distinct objects but only $k$ of them appears in the sequence. Now, the problem instance of $TD$ consists of the graph $G$ and sequence $S$. This completes the construction.
Now, suppose $A$ is an algorithm of $TD$ that returns a correct mapping of the objects to the locations such that the total traveling cost is minimized.
Now, if the traveling cost of the mapping is $\infty$ then $G$ does not have a $k$ size clique. And, if the mapping gives the finite traveling cost then $G$ does have a $k$ size clique.
The above reduction implies that $TD$ is also $NP-hard$. So, we can not expect a polynomial-time running algorithm for $TD$.

Note that, in the reduction, instead of setting the edge weights of $G$ to be $\infty$, you can also use finite weights but with sufficiently large values such as $|V|^{|V|}$. That would also work.


Is $\{a^mb^nc^n \mid m,n \geq 0\} \cup \{b,c\}^*$ regular or not? Show if $L = \{a^mb^nc^n \mid m,n \geq 0\} \cup \{b,c\}^*$ is regular or not.
My attempt:
I think the Pumping lemma won't work in that constellation, so I'm working with "The intersection of regular languages is regular".
Assuming $L$ is regular. I already know that $S=\{ab^* c^*\}$ is regular. I'll now look at the intersection $L \cap S$.
$$(\{a^mb^nc^n \mid m,n \geq 0\}\cap \{ab^* c^*\}) \cup (\{b,c\}^*\cap \{ab^* c^*\})$$
$$\{ab^nc^n \mid n \geq 0\} \cup \emptyset = \{ab^nc^n \mid n \geq 0\}$$
Which is not regular according to Pumping lemma. Is this idea correct?

Pumping lemma works easily. Somewhere it says "if the language is regular then for every string in the language..." Just check the pumping lemma for strings that start with exactly one a.


Is there a running hash algorithm that can efficiently handle arbitrary updates to a file's contents? This question is about file-hashing/fingerprinting algorithms (similar to SHA-1 and MD5 and so on).  Those algorithms are handy because they give you a small (and fixed-sized) hash code for any file, which can be later used to efficiently determine if that file is different from another file, and (if we are willing to ignore the unlikely possibility of hash-collisions) also whether two files are the same.

One small downside to computing the hash/fingerprint for a file is that you have to read the entire file in order to do so; if the file is very large (e.g. gigabytes or more) this can be an expensive operation.

A good way to avoid that expense is to compute the file's hash code as you are writing it to the disk, and store the hash code with the file.  You can even resume  updating the hash code later on, if/when you append more bytes to the end of the file, and (assuming no bugs or filesystem corruption) you'll have the file's fingerprint/hash cheaply available to you at all times.

However, the above "update as you go" approach seems like it may break down if you want to update the file in other ways besides appending -- in particular, if you want to truncate the file, or overwrite some existing bytes within the file with new values, you might have to then re-read the entire file in order to update the fingerprint/hash to the appropriate new value.

My question is, is there a type of hashing/fingerprinting algorithm that can efficiently handle file-truncation and byte-overwrite operations, and still provides reasonably good-quality hashing/fingerprinting?   ("efficiently" in this case means that one could perform one of these operations on the file and then compute the correct new hash/fingerprint without having to re-read other parts of the file)

One way to achieve it is to keep a dynamic balanced tree augmented with hashes. This will give you logarithmic slowdown for overwrites and truncation, and also will work with any hashing algorithm.

Let the file be partitioned in blocks of fixed size, $H$ be a hash-function, and $h_t$ be a value stored in a node $t$. If $t$ is a leave, then $h_t$ is a hash of the corresponding block. If $r$ is a parent of $a$ and $b$, then $h_r = H[(h_a,h_b)]$.


Difference between properties of good hash function: uniformity and randomness I did go through Korth's book of DBMS and I got these definitions:

Uniformity:

Each bucket is assigned the same number of search-key values from the set of all possible values.

Randomness:

Each bucket will have the same number of records assigned to it irrespective of the actual distribution of search-key values in the file.

These definitions seem  similar to me. Can anyone please differentiate, I did search on net but can't understand.

Uniformity is about potential values, while randomness is about actual values.

For example, suppose you make a very simple hash function that takes the first byte of a string, resulting in 256 buckets. It is uniform, because the number of possible strings starting with a particular byte doesn't depend on. But it is not random for most data sets: at least 12.5% of the values consist of nonprintable characters (control characters) that most data sets don't contain, some characters like )]} rarely appear at the beginning of a string, an English dictionary contains more words beginning with a than with z, etc.

Randomness is defined with respect to a specific data set. For example, if the data set consists of SHA-1 hashes of typical strings, then taking the first byte satisfies the randomness property. If the data set consists of people's surnames, it doesn't. If the data set consists of SHA-1 hashes strings that are deliberately chosen so that their SHA-1 hash starts with the byte 0, then taking the first byte doesn't satisfy randomness either.

In fact, there is no hash function that satisfies randomness for all datasets: for any hash function (with at least two buckets), a data set consisting solely of values that hash to bucket 0 violates randomness. The best you can hope is hash functions that satisfy randomness for datasets that are not deliberately crafted to violate randomness. This is possible in practice if the hash function includes a random factor which is based on a secret seed.


It has been asked to prove that a grammar is unambiguous which seem ambiguous to me S->aAB

  A->bBb

  B->A|epsilon

It seems that the string abbbb can be derived by using more than one ways.
After using the starting production and the production for A, we get:
S=>abBbB.

From here, either of the B's can be replaced with epsilon and the other one replaced with bBb. So, there are two ways of deriving abbbb.

Isn't this ambiguous grammar?

It's a question from Formal Languages and Automata by Peter Linz (5th edition) Exercise 5.2.16

You need to revisit the definition of ambiguity. The point is not whether multiple derivations exist; all non-linear grammars have many derivations per word.
You have to check if there is only one left-derivation per word. Equivalently, you can check right-derivations or syntax trees.

If you think this grammar is ambiguous, prove it by giving two different syntax trees for some word.

If you think it is unambiguous, see here for how to prove that; it's often more tricky.


Algorithm to split $n$ distinct items into $k$ nonempty unlabelled subsets The number of ways to split $n$ items into $k$ nonempty unlabelled subsets ($k<n$) is a Stirling number of the second kind.(https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind)

Is there an algorithm to generate all the possible combinations?

Concretely, let us count the number of ways to partition $[n]$ into $k$ non-empty ordered subsets, which are themselves ordered by increasing order of the first element. For example, a valid partition of 10 into 5 sets is
$$
\{1,4,5\},\{2,3,6\},\{7\},\{8,10\},\{9\}.
$$
Note that $1<2<7<8<9$.

The base cases $k=0,k=1,k=n$ are easy, so suppose $2 \leq k < n$. A partition of $[n]$ into $k$ ordered subsets can be obtained in two ways:

Taking a partition of $[n-1]$ into $k-1$ ordered subsets, and adding a new subset containing only $n$.
Taking a partition of $[n-1]$ into $k$ ordered subsets, and adding $n$ to the 1st subset, the 2nd subset, ..., the $k$th subset.

By recursively generating all partitions of $[n-1]$ into $k-1$ or $k$ ordered subsets, you can thus generate all partitions of $[n]$ into $k$ ordered subsets.

As D.W. mentions, this is just the recurrence for the Stirling numbers.


Context free grammar for a palindrome of even length + cc Suppose the language is $\{AA^R: A \in \{a,b\}^*\}$.

I know that I can make a context free grammar for it:

$$S\to aSa \mid bSb\mid\epsilon$$

Now if the language was $\{AA^Rcc: A \in \{a,b\}^*\}$, so the same thing but with $cc$ at the end. Would the following context free grammar work?

$$\begin{aligned}
S&\to aS \mid bS\mid\epsilon\mid T\\
T&\to  cc\\
\end{aligned}$$

I think it works cause you have the options to make the original string and its reverse, but unlike in the first example, the grammar doesn't fit how the output is suppose to be and so you kind of have to remember what the original string was to make the reverse and then append $cc$ at the end. But then I remember that automata doesn't have memory of previous states so what would be correct grammar?

This CFG does not work
$$\begin{aligned}
S&\to aS \mid bS\mid\epsilon\mid T\\
T&\to  cc\\
\end{aligned}$$
It generates $acc$ by $S\Rightarrow aS\Rightarrow aT\Rightarrow acc$, which is not of form $AA^Rcc$. In fact, it generates the language $(a+b)^*(\epsilon+cc)$.

You might have missed the basic mindset to write a context-free grammar (CFG).
Every non-terminal in a CFG stands for a language.
Thinking in terms of languages instead of strings should be more helpful sometimes for constructing the CFG.
Since the language $S=\{AA^Rcc: A \in \{a,b\}^*\}$ is the concatenation of the language of the palindromes of even length,  $P=\{AA^R: A \in \{a,b\}^*\}$ and the language of one word, $C=\{cc\}$, the corresponding substitution rule is
$$ S\to PC$$
to which we add the substitution rules for $P$ and $C$
$$\begin{aligned}
P&\to aPa\mid bPb\mid\epsilon\\
C&\to  cc.\\
\end{aligned}$$
The collection of all substitution rules above is the CFG wanted. Note that each of the symbols $S, P, C$ is abused to denote a non-terminal as well as the languages it stands for, i.e, the context-free language generated if we treat it as the starting symbol.
Exercise
Write a CFG for the language $\{AA^RbcBB^R: A \in \{a,b\}^*, B\in\{c,d\}^*\}$.


Can synchronous data transfer be used for transferring large data in case of computer architecture and organization? I am learning computer architecture and organization.

I have this confusion, can synchronous data transfer be used for transferring large data in case of computer architecture and organization?

I have read that synchronous data transfer can be used for transferring large data but I think it is true only in case of computer networks, in case of computer architecture and organization I think DMA is used for transferring large data. So if someone asks me if synchronous data transfer be used for transferring large data in case of computer architecture and organization. Should I say yes or no?

I think that the question has no clear answer. Data can be transferred in a synchronous or asynchronous manner. Each has its own pros and cons. Synchronous communication is irrelevant for some systems, e.g., when there is no joint clock or where the distance causes too large clock skews. Both methods are capable of transferring large amounts of data. For instance, USB is kinda asynchronous, in the sense it has no clock (it uses synchronization strings to maintain synchronization) and yet it is capable of transferring large amount of data.
DMA is a mechanism within some chip that allows transferring data (small amount or large amount) without the involvement of the CPU. Within a chip most communication is synchronous (there are exceptions). However, the DMA communication might have gaps within its transmissions as the BUS might be needed for the CPU. It might depend on the exact mode of DMA operation.


How do people measure performance overhead? How do people measure performance overhead? Whenever someone is bragging about how their program or application performs better than another, they talk about particular measurements, eg time, performance etc.

Whilst I understand how time to perform a task can be calculated, I cannot understand how performance is measured, and I can't find out thought Google.

Are there multiple ways? Are they all accepted or do people have issues with certain methods?

The meaning of overhead is usually an additional expense occurring in
addition to normal cost (whatever normal cost may be).

In the case of program, you may talk of overhead if it is run under
conditions such that it will cost more than it normally should, in
time or in memory usually, but it could be some other measure.

For example, at a time when compilers did not produce very good code,
compiled programs code size or execution time was compared with
programs handwritten in machine code. The quality of the compiler was
measured by the overhead of the generated code compared to a similar
program written in machine code. The overhead could be defined by the
ratio of the two costs, or by the percentage to be added.

An overhead of 20% in code size meant that the compiled programhad a
machine code version 20% larger than the hanwritten one. An overhead
of 20% in speed meant that the compiled program took 20% more time to
execute. An overhead of 20% in memory meant that the compiled program
required 20% more memory to execute.

Nowadays, compilers are quite good and this kind of overhead would
probably be negative.  Compilers make the better code.

In the case of a virtual machine, you can have a program that run
directly on the hardware, or runs under the control of a virtual
machine that hides (and protect) somewhat the hardware. Running on a
virtual machine will slow the program, and the variation in running
time is the overhead (extra time cost) caused by the virtual machine.
You just measure the time taken by the same program running in both
situations, and you determine the percentage of additional time
required when running in a virtual machine.  It may depend on the type
of application you use to test the overhead of the virtual machine.

Overhead is a measure of extra cost. It applies to devices or programs
or procedure that cause an extra cost (but usually provide an extra
servive).

You could also measure the time overhead incurred by your programs
when you reduce the available real memory.

Overhead is a way of comparing two related performances, intended to
achive the same result, separately measured.

Does this clarify things for you?


How to prove that $2^{n+3} = O(2^n)$? I am a little confused on how to prove/disprove Big O.

For the problem, $2^{n+3}= O(2^n)$, I did the following:

$$2^{n+3} \leq K \times 2^n$$

Set $K = 1$

$$2^{n+3} \leq 2^n$$

Test for large values of n (so I plugged in n = 100)

$2^{103} \leq 2^{100}$  --- which is false therefore Big O is disproven

Is this process correct?

Just, replace the constant $K = 2^3$, and you have to use this constant for your proof.

$$ 2^{n+3}  = K\times 2^n$$

So, $O(2^{n+3})  = O(2^n)$.


What is a type definition? When reading about data types, "type definition" is often used without any prior explanation to what it means.

For example, in https://en.wikipedia.org/wiki/Type_system, we have the sentence "...  since C++ has stronger rules regarding type definitions  ..."

Any help in clarifying what the difference between, for example, type and type definition is greatly appreciated!

"Defining" a type is the act of building a new type composed of one or more pre-existing data types. For example, the "Complex Number" type is often declared as an ordered pair of "Real Numbers" :

Type Complex
  Real a
  Real b
End

a and b being the real and imaginary parts.

This sample of pseudo-code is a "Type Definition".


How can I solve this deadlock related problem mathematically? I came across following problem:

  A system has n resources R0,…,Rn-1,and k processes P0,….Pk-1.The implementation of the resource request logic of each process Pi is as follows:

if (i % 2 == 0) {
      if (i < n) request Ri
      if (i+2 < n) request Ri+2
}
else {
      if (i < n) request Rn-i
      if (i+2 < n) request Rn-i-2
}

  In which one of the following situations is a deadlock possible?
  (A) n=40, k=26
  (B) n=21, k=12
  (C) n=20, k=10
  (D) n=41, k=19

The given solution takes following form:

  Even numbered process $P_i$ request even numbered resources $R_i$ and $R_{i+2}$. Thus they share no more than 1 resource.
  Odd numbered process $P_i$ request

  Odd numbered resources $R_{n-i}$ and $R_{n-i-2}$ if $n$ is even
  Even numbered resources $R_{n-i}$ and $R_{n-i-2}$ if n is odd.

  In this example, for deadlock to occur, two processes must request same set of processes. For this, we need n to be odd so that some odd numbered process will request same set of even numbered resources as some even numbered process.
  Thus option A and C are not possible as they have even n.
  For option D, n = 41, k = 19. Resources requested will be:

  Thus no two processes request same set of resources.
  For option B, n = 21, k = 12. Resources requested will be:

  P7 and P10 request same set of resources R12 and R14.
  P9 and P8 request same set of resources R10 and R12.
  P11 and P6 request same set of resources R8 and R10.
  These pairs can cause deadlock if one of them come first and request one of the resources and then other comes and requests other resource and lastly both request the respective remaining resource.

I was guessing whether I can solve this mathematically to speed up. I thought following

  When i is even, Pi requests $R_i$ and $R_{i+2}$
  When i is odd, Pi requests $R_{n-i}$ and $R_{n-i-2}$
  Then I though I need to equate as follows:

  $i = n-i-2 \rightarrow 2i=n-2$
  $i+2 = n-i \rightarrow 2i=n-2$

  Then try out for option A as:

  $40-2 = 38 \rightarrow i=19$

  But later I realize, this was simply stupidity and remained directionless.

I still dont know whether I can solve this problem quickly mathematically without forming those tables. Is it possible?

(Sorry for more mathematical problem than the one involving Operating Systems or Computer Science concepts.)

As per the question, all the even processes request only even resources(i.e. Ri & Ri+2)
Where as odd processes request:
either,
odd resources(i.e. Rn-1 & Rn-1-2) when 'n' is even.
or,
even resources (i.e. Rn-1 & Rn-1-2) when 'n' is odd.

Deadlock can only happen when even and odd processes request overlaps i.e. odd processes have to request even resources which means 'n' must should be odd.

Mathematically,

Let Pn-i be an odd process then,

n-i<=k

or,ceil(n-i)=k   here ceil() is ceiling function since the value at max can be equal to k.

i=ceil(n-k)---eqn(i)

For deadlock to happen,

i=n-i-2

substituting value of i from eqn(i), we have,

ceil(n-k)=n-i-2

solving further we get,

k=ceil((n+2)/2)  where 'n' is odd

since, 'n' must should be odd option A and C can be ignored now coming to option B substituting n=21 we get k=12
In option D substituting n=41 we get k=22.

so option B is correct.For option D to be in deadlock k should be equal to 22.


How to determine the carry vector of an integer addition An integer addition can be represented as following:

$A + B = A \oplus B \oplus carry_{vector}$

My question is how to determine the carry vector from $A$ and $B$ (not from the result)?

The generation of the carry vector is a recursive process where the results of lower bits factor into the current carry output.

In general:

$$
Carry_{n} = (A_{n} \bullet B_{n}) + ((A_{n} \oplus B_{n}) \bullet Carry_{n-1})
$$
Note the $$ Carry_{n-1} $$ term. The presence of this term means that carry data ripples through the adder chain.

This is the reason that so much effort was devoted in older computer implementation technologies to speeding up this process. This was done by brute force computing the carry for groups of bits in a process called carry look-ahead. Let's see this for two bits:

$$
Carry_{n} = (A_{n} \bullet B_{n}) + ((A_{n} \oplus B_{n}) \bullet ((A_{n-1} \bullet B_{n-1}) + ((A_{n-1} \oplus B_{n-1}) \bullet Carry_{n-2})))
$$

As bits get added, this gets messy in a hurry.

The classic 74181 ALU used this method for the 4 bits handled by the chip and was often paired with the 74182 Carry Look Ahead chip to speed carry propagation by performing the same between up to four chips. If more that 16 bits needed to be processed, another layer of 74182 was employed to speed up carry propagation in the lower layer. Thus an ALU with 16 74181s, 4 74182s, and one top level 74182 could process 64 bits with a delay of roughly 3 times the four bit ALU delay, instead of 16 times.

It is noteworthy though, that there is no easy solution to the problem. Each added bit of look ahead, increases the complexity of the carry generator.


What is the difference between a collection of Turing Machines and a family of Circuits? Given a Collection of Turing Machines $T_1, T_2, T_3,...T_n$ where $T_1$ denotes that the Turing machine can only take in an input of size 1. Is there any difference in computational power to a family of Circuits $C_1, C_2, C_3,...C_n$ ?

What if we assumed that each Turing machine, encoded special information for that specific input size to make each instance efficient?

If there is no difference in computational power, then maybe we could use this to define non-uniform algorithms instead of circuits?

What you describe is essentially Turing machines with advice, the advice for length $i$ being simply the description of $T_i$. It is a classic result that the two models are equivalent in the case of poly-time TMs and poly-sized circuits, that is, both produce the same class $\mathsf{P}/\mathrm{poly}$. If the description length of $T_i$ is allowed to be arbitrary, there is also no computational power to be gained since you can then express all Boolean functions for each length (just as with circuits).


What are the minimum requirements for a language to be considered Turing Complete? Possible Duplicate:
  Are there minimum criteria for a programming language being Turing complete?

I overheard a conversation on the topic and the conclusion that one gent came to was that in order to be Turing complete, given one has infinite storage, all one needs is a conditional control structure and a jump instruction.

Is this true?

If it is true, and Turing completeness requires that the language that is Turing complete be able to simulate every instruction available in another Turing complete language, how do those two simple elements achieve that?

The machine you describe would be turing complete with the addition of an assignment operator (you need this to take advantage of memory), and at least one comparison operator (which could be folded into the jump, like a jump-if-(not)-zero). (Note that an increment operator is necessary - either as a primitive, or appropriate representations need to be available such that one can roll ones own).

However, there are many turing-complete models of computation with completely different primitive operations, such as lambda calculus, or petri nets.


Algorithm to test whether a language is regular Is there an algorithm/systematic procedure to test whether a language is regular?

In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n : n \in \mathbb{N}\}$), test whether the language is regular or not.  Imagine we are writing a web service to help students with all their homeworks; the user specifies the language, and the web service responds with "regular",  "not regular", or "I don't know".  (We'd like the web service to answer "I don't know" as infrequently as possible.)  Is there any good approach to automating this?  Is this tractable?  Is it decidable (i.e., is it possible to guarantee that we never need to answer "I don't know")?  Are there reasonably efficient algorithms for solving this problem, and be able to provide an answer other than "don't know" for many/most languages that are likely to arise in practice?

The classic method for proving that a language is not regular is the pumping lemma.  However, it looks like requires manual insight at some point (e.g., to choose the word to pump), so I'm not clear on whether this can be turned into something algorithmic.

A classic method for proving that a language is regular would be to use the  Myhill–Nerode theorem to derive a finite-state automaton.  This looks like a promising approach, but it does requires the ability to perform basic operations on languages in algebraic form.  It's not clear to me whether there's a systematic way to symbolically perform all of the operations that may be needed, on languages in algebraic form.

To make this question well-posed, we need to decide how the user will specify  the language.  I'm open to suggestions, but I'm thinking something like this:

$$L = \{E : S\}$$

where $E$ is a word-expression and $S$ is a system of linear inequalities over the length-variables, with the following definitions:

Each of $x,y,z,\dots$ is a word-expression.  (These represent variables that can take on any word in $\Sigma^*$.)
Each of $x^r,y^r,z^r,\dots$ is a word-expression.  (Here $x^r$ represents the reverse of the string $x$.)
Each of $a,b,c,\dots$ is a word-expression.  (Implicitly, $\Sigma=\{a,b,c,\dots\}$, so $a,b,c,\dots$ represent a single symbol in the underlying alphabet.)
Each of $a^\eta,b^\eta,c^\eta,\dots$ is a word-expression, if $\eta$ is a length-variable.
The concatenation of word-expressions is a word-expression.
Each of $m,n,p,q,\dots$ is a length-variable.  (These represent variables that can take on any natural number.)
Each of $|x|,|y|,|z|,\dots$ is a length-variable.  (These represent the length of a corresponding word.)

This seems broad enough to handle many of the cases we see in textbook exercises.  Of course, you can substitute any other textual method of specifying a language in algebraic form, if you have a better suggestion.

The answer is no. Deciding whether a given context-free grammar generates a regular language is an undecidable problem.

Update. I gave this negative answer to the general question

  Given a language specified in algebraic form, test whether the
  language is regular or not

since context-free languages are solutions of algebraic equations in languages: see Chapter II, Theorems 1.4 and 1.5 in the book of J. Berstel Transductions and Context-Free Languages.

However, the same question is decidable for deterministic context-free languages, a nontrivial result due to Stearns [1] and improved by Valiant [2]:
[1] R. E. Stearns, A Regularity Test for Pushdown Machines, Information and Control  11 323-340 (1967). DOI:10.1016/S0019-9958(67)90591-8.
[2] L. G. Valiant. Regularity and related problems for deterministic pushdown automata J. ACM 22 (1975), pp. 1–10.

There is another positive result, closer to the specifications given in the second part of the question. Recall that the semilinear subsets of $\mathbb{N}^k$ are exactly the sets definable in Presburger arithmetic. There are also the rational subsets of $\mathbb{N}^k$. In particular, a subset of $\mathbb{N}^k$ defined by linear inequations is rational. Now, given a rational subset $R$ of $\mathbb{N}^k$, it is decidable whether the language
$$
  L(R) = \{ u_1^{n_1} \dotsm  u_k^{n_k} \mid (n_1, ...,n_k) \in R \}
$$
is regular. Indeed, it is known [Ginsburg-Spanier] that $L(R)$ is regular if and only if $R$ is a recognizable subset of $\mathbb{N}^k$ and it is decidable [Ginsburg-Spanier] whether a given rational subset of $\mathbb{N}^k$ is recognizable.

S. Ginsburg and E. H. Spanier., Semigroups, Presburger formulas, and languages,  Pacific J. Math. 16 (1966), 285-296.

S. Ginsburg and E. H. Spanier. Bounded regular sets, Proc. of the American Math. Soc. 17, 1043–1049 (1966).

This does not solve the second part of the question, which might be undecidable because of the word variables, but it gives a reasonable fragment to start with.


Proof: "If the list is then k-sorted for some smaller integer k, then the list remains h-sorted" Shellsort is a generalization of insertion sort that allows the
  exchange of items that are far apart. The idea is to arrange the list
  of elements so that, starting anywhere, considering every hth element
  gives a sorted list. Such a list is said to be h-sorted. Equivalently,
  it can be thought of as h interleaved lists, each individually
  sorted. Beginning with large values of h, this rearrangement allows
  elements to move long distances in the original list, reducing large
  amounts of disorder quickly, and leaving less work for smaller h-sort
  steps to do. If the list is then k-sorted for some smaller integer
  k, then the list remains h-sorted. Following this idea for a
  decreasing sequence of h values ending in 1 is guaranteed to leave a
  sorted list in the end.

[Source]

What is the mathematical proof for the quoted claim (in bold)?

An attempt at the proof (for the case when number of elements is $2n+1$):

My initial array is $A = \{x_0, \cdots, x_n\}$ and i have $x_0 < x_n$. Say that after first pass $x_0$ switches place with $x_m$, so the final array $B$ starts with the entry $x_m$ regardless of the position of $x_0$ (which can further switch place with $x_{2m}$ and so on). Thus, $x_m < x_0$. Now, in the final pass $x_n$ can switch place with $x_k$ (which, before the last pass, is in the $(n-m)$-th position in the array). We don't care about $k$, but we just know that $x_n < x_k$. So the last entry in the final $m$-sorted array $B$ is $x_k$.
Sum it up: $x_m < x_0 < x_n < x_k$.

That means $B$ is $n$-sorted.
If we assumed the switchings of $x_0$ and $x_n$ didn't happen during $m$-sorting, we are trivially done, because the starting and final entries of $B$ are $x_0$ and $x_n$ respectively, and since $x_0 < x_n$, $B$ is $n$-sorted.

Say $A = \{x_0, \cdots, x_n, \cdots, x_{2n}\}$ is $n$-sorted. We can assume the subarray $\{x_0, \cdots, x_n\}$ is $m$-sorted WLOG and because of what we proved earlier. Suppose now that while $m$-sorting, $x_n$ and $x_{n+m}$ are switched; then $x_{n+m} < x_n$. And then on the last entry, $x_k$ (in the $2n-m$ th position) and $x_{2n}$ are switched. Then $x_{2n} < x_k$.

After the $m$-sorting is over, the $n$-gap subarray starting at $x_0$ is $\{x_0, x_{n+m}, x_k\}$. We have $x_0 < x_m < x_{n+m} < x_n < x_{2n} < x_k$, where $x_m < x_{n+m}$ is because $A$ is $n$-sorted.

So, this is proof that if a $2n+1$ array is $m$-sorted after being $n$-sorted, it remains $n$ sorted.

However, I don't know how to generalize that for any size of array.

the claim follows easily from a careful definition of "k-sorted". define k-sorted as "for all i there does not exist a j > k such that for two elements in the list a[i+j] < a[i]." then if a list is k-sorted, it is h-sorted for h > k.

to look into deeper/ more general theory realize that k-sorted is a "measure of disorder" eg as in question how to measure sortedness. see this paper a survey of adaptive sorting algorithms, / Castro, Wood, measures of disorder, sec 1.2. h-sorted appears to be equivalent to measure #1, Dis, "largest distance determined by an inversion".


How many structurally different trees can be formed with n nodes? Is there any exact formula for finding number of structurally different unlabeled trees can be formed with $n$ nodes? I searched a lot and I found some approximation formulas, e.g. here.

Check out A000055. Even if this is not what you want, it is probable that the OEIS has your sequence. The easiest way to look for a sequence in the OEIS is by calculating the first few numbers.


What is a regular expression that matches all strings over the alphabet except a particular substring? I've come across this problem in my studies, and I've abstracted it to the more general case here.

Given a finite alphabet, what is a regular expression that matches all strings over the alphabet, except one particular finite substring?

As an example:

Given $\Sigma = \{a, b, c\}$

What is a regular expression that matches all of $\Sigma$ except the substring $
ba$?

What I really want is simply $\Sigma^* - ba$.

Just draw the minimal complete DFA accepting your string, change the final states to get the complement and now convert this new DFA to a regular expression.

In your case, you will get $\mathcal{A} = (Q, A, \cdot, 1, F)$ with $Q = \{0, 1, 2, 3\}$, $A = \{a, b, c \}$, $F = \{3\}$ and $1 \cdot b = 2$, $2 \cdot a = 3$ and $q \cdot x = 0$ for all other transitions. Thus the automaton for the complement is $\mathcal{A}' = (Q, A, \cdot, 1, F')$ with $F' = \{0, 1, 2\}$.

Converting $\mathcal{A}'$ to a regular expression gives
$$
  1 + b + (c + bc + baA)A^*
$$


Are there problem instances which we know to be unsolvable? As it says in the title:

  Are there problem instances which we know to be unsolvable?

Or equivalently

  Are there any promise problems with a finite number of possible inputs
  which are undecidable?

Please note:
I realize that many computational problems are known to be unsolvable, but to the best of my knowledge (limited it may be) all must take an infinite number of inputs. Therefore, their existence does not imply that there cannot be an infinite number of algorithms each solving a subset of these problems.

Remark: I only wish to consider well-defined problems, i.e. every input has a correct output.

On a related note, is there a complexity hierarchy for promise problems with only a finite number of possible inputs?

Every problem with a finite number of inputs is computable.

Proof: Suppose that the inputs are $i_1,\ldots,i_n$ and that the desired outputs are $o_1,\ldots,o_n$. Then the following program solves the problem:

If the input is $i_1$, output $o_1$.
If the input is $i_2$, output $o_2$.
...
If the input is $i_{n-1}$, output $o_{n-1}$.
Output $o_n$.


Two "bubble" loops in pseudocode; would they return the same thing? I am trying to create a new form of a bubble loop and want to see if they would return the same truth values during runtime. Could I get a second pair of eyes to confirm if this is the case?
Note: prod is equal to a target product of a sequence.
Code #1
For c = 1 to x
For d = 1 to c - 1
If (a,c * a,d = prod) return True
End For

Code #2
For c = 1 to x
For d = c + 1 to x
If (a,c * a,d = prod) return True
End For

I did data collection and found that in each case, the return true value would be the same. Is this always the case? If so, is this just because our index is simply starting at the second to the beginning as compared to skipping the end?

In the first code, the values taken by $(c, d)$ are in the set $\{(c, d)| 1 \leq d < c \leq x\}$. In the second code, the set is $\{(c,d)|1\leq c < d \leq x\}$. Since $c$ and $d$ play symmetrical roles in the boolean test, it is expected that you obtain the same result.
Note that if $c$ and $d$ would not play symmetrical roles, the result could be different (for example, if the test was a, c * d, a = prod).


How do you determine the number of errors in the Welch-Berlekamp algorithm? In the Welch-Berlekamp algorithm for decoding Reed-Solomon codes, one is given a list of points $(a_i, b_i)$ representing a message with $e$ errors on the $b_i$ in unknown locations (and $e$ is given to the algorithm). The output is a polynomial passing through all of the given points except those in which errors occurred.

The method involves solving a system of linear equations of the form

$$b_i E(a_i) = Q(a_i)$$

for all $i$ where $E$ has degree $e$ and $Q$ has degree at most $e+k$. The variables are the coefficients of $E$ and $Q$.

To ensure that $E$ has degree $e$ one usually adds the constraint that the coefficient of $x^e$ is 1 to the linear system above. However, in practice one doesn't necessarily know $e$. One inefficient (but still polynomial time) way to deal with this is to try $e$ for all values starting with $(n+k-1)/2 - 1$ going down until a solution is found.

My question is: is there a more efficient way to determine $e$? Alternatively, is there a modification to the linear system that allows one to use an upper bound on $e$ instead of the exact value?

In particular I want to use this specific decoder for Reed-Solomon codes, and not a completely different algorithm based on other techniques.

In response to DW's answer, here is my working example. Everything is done modulo 7.

plain message is: [2, 3, 2]
polynomial is: 2 + 3 t^1 + 2 t^2
encoded message is: [[0, 2], [1, 0], [2, 2], [3, 1], [4, 4]]
corrupted message is: [[0, 2], [1, 0], [2, 3], [3, 1], [4, 4]]

So the error is in the third point.

When $e=2$ the polynomial equation in question is

$$b_i(e_0 + e_1x + e_2x^2) - q_0 - q_1x - q_2 x^2 - q_3x^3 - q_4x^4 = 0$$

And plugging in $x = 0,1,2,3,4$ gives the system in matrix form:

[2, 0, 0, 6, 0, 0, 0, 0, 0]
[0, 0, 0, 6, 6, 6, 6, 6, 0]
[3, 6, 5, 6, 5, 3, 6, 5, 0]
[1, 3, 2, 6, 4, 5, 1, 3, 0]
[4, 2, 1, 6, 3, 5, 6, 3, 0]
[0, 0, 1, 0, 0, 0, 0, 0, 1]

The last row is the constraint that $e_2 = 1$. Applying Gaussian elimination we get

[1, 0, 0, 0, 0, 0, 1, 4, 0]
[0, 1, 0, 0, 0, 0, 3, 3, 1]
[0, 0, 1, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 0, 2, 1, 0]
[0, 0, 0, 0, 1, 0, 2, 2, 5]
[0, 0, 0, 0, 0, 1, 4, 5, 2]

And picking 1 for both free variables we get a solution vector of

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

Which translates to

E is 2 + 2 t^1 + 1 t^2
Q is 4 + 1 t^1 + 0 t^2 + 1 t^3 + 1 t^4

And $E$ does not divide $Q$. Note that $Q$ factors as $(t + 6) (t^3 + 2t^2 + 2t + 3) \mod 7$

For $e=1$ I get a good solution:

system is:
[2, 0, 6, 0, 0, 0, 0]
[0, 0, 6, 6, 6, 6, 0]
[3, 6, 6, 5, 3, 6, 0]
[1, 3, 6, 4, 5, 1, 0]
[4, 2, 6, 3, 5, 6, 0]
[0, 1, 0, 0, 0, 0, 1]

reduced system is:

[1, 0, 0, 0, 0, 0, 5]
[0, 1, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 3]
[0, 0, 0, 1, 0, 0, 3]
[0, 0, 0, 0, 1, 0, 6]
[0, 0, 0, 0, 0, 1, 2]

solution is [5, 1, 3, 3, 6, 2]
Q is 3 + 3 t^1 + 6 t^2 + 2 t^3
E is 5 + 1 t^1
P(x) = 2 + 3 t^1 + 2 t^2 # this is correct!
r(x) = 0

Note that while the counterexample above was generated by code I wrote from scratch (it was basically the first thing I tried), one can check the solutions are valid by hand, so even if my code is buggy it's still a valid counterexample to the claim that using $e=2$ works.

The same procedure actually works to correct any number of errors up to $e$.

The requirement is that the error polynomial $E(x)$ has to be zero at every point $a_i$ where there was an error.  Nothing says it has to be zero at only those points; you can have an $E(x)$ that is zero at other points too, and that's OK, as long as its degree is $e$.

So, if $e$ is an upper bound on the number of errors, there will exist a polynomial $E(x)$ with all the desired properties (i.e., has degree exactly $e$ and is zero at every point where there is an error).  For instance, if there are fewer than $e$ errors, then there exists a polynomial $E(x)$ that's zero at every error, and zero at a few more points to get the number of zeros up to exactly $e$.

Finally, the correctness theorem says that if such a polynomial $E(x)$ exists, then the Berlekamp-Welch algorithm will be able to find it.   So, even if there are fewer than  $e$ errors, the procedure will still work correctly to identify $E(x)$.  Once you have $E(x)$, you can identify $n-e$ positions that are error-free, and then you can decode in a straightforward way.

To document the result of the conversation about the "counterexample" in the question:

That's actually not a valid counterexample.  The flaw was in the calculation of how many errors you should expect Berlekamp-Welch to be able to correct.  The distance is $n-k+1$, so you should expect it to be able to correct up to $(n-k)/2$ errors (as Ran G. points out).  In your counterexample $n=5$ and $k=3$, so $(n-k)/2=1$, so you should only expect this procedure to be able to correct one error, i.e., $e=1$.  So, when you ran the procedure on an example with $e=2$, there's no reason to expect the procedure to work correctly.

So, the counterexample isn't actually a counterexample, and it doesn't contradict my answer above.


Practical Applications of Radix Sort Radix sort is theoretically very fast when you know that the keys are in a certain limited range, say $n$ values in the range $[0\dots n^k -1]$ for example.  If $k<\lg n$ you just convert the values to base $n$ which takes $\Theta(n)$ time, do a base $n$ radix sort and then convert back to your original base for an overall $\Theta(nk)$ algorithm.

However, I've read that in practice radix sort is typically much slower than doing for example a randomized quicksort:

  For large arrays, radix sort has the lowest instruction count, but
  because of its relatively poor cache performance, its overall
  performance is worse than the memory optimized versions of mergesort
  and quicksort.

Is radix sort just a nice theoretical algorithm, or does it have common practical uses?

Radix sorts are often, in practice, the fastest and most useful sorts on parallel machines.

Zagha and Blelloch: Radix sort for vector multiprocessors. Supercomputing, 1991: 712-721.
Blelloch, Leiserson, Maggs, Plaxton, Smith, and Zagha: A Comparison of Sorting Algorithms for the Connection Machine CM-2. Symp Parallel Algorithms and Arch (SPAA-3):3-16, 1991.
Arpaci-Dusseau, Arpaci-Dusseau, Culler, Hellerstein, and Patterson: High-performance sorting on networks of workstations. Conf on Mgt of Data, (SIGMOD-1997):243-254.
Arpaci-Dusseau, Arpaci-Dusseau, Culler, Hellerstein, and Patterson. Searching for the sorting record: experiences in tuning NOW-Sort. ACM Sigmetrics Symp Parallel and Distributed Tools, (SPDT-2):124-133, 1998.

On each node of the multiprocessor you probably do something like a quicksort, but radix sort allows multiple nodes to work together with less synchronization than the various recursive sorts.

There are other situations too.  If you need a stable sort (a sort where whenever two keys are equal they stay in the same order rather than getting rearranged) then I'm not aware of any version of quicksort that will be of use.  Mergesort is also stable (if implemented correctly).  Your link is the first time I've ever heard anyone say that mergesort could be made to have better cache behavior than radix sort.


Is the Nearest Neighbor Algorithm a valid algorithm to find a Minimum Spanning Tree? I just wrote a program that runs the Travelling Salesman Problem using the Nearest Neighbor Algorithm. Afterwards, I started looking into Minimum Spanning Trees (MST).

From my understanding:

The Nearest Neighbor Algorithm traverses a graph starting at one vertex, and then it travels to the next vertex following the edge with the shortest distance (lightest weight) between them.

An MST is a subgraph of the original graph whose vertices are all connected. The total of the edge weights in the subgraph should be as small as possible. You can use Kruskal's algorithm to find MSTs.

As I was looking at the paths taken when implementing the Nearest Neighbor Algorithm, I noticed that it could possibly sometimes return a MST.

Is the Nearest Neighbor Algorithm a valid algorithm to find a Minimum Spanning Tree?

It seems like it should be. It's terribly similar to Kruskal's algorithm (from what I have read so far). However, I never see it listed as a possible option for finding MSTs.

Thanks for any help in advance.

Edit for clarity:

The Nearest Neighbor Algorithm is described here. From what I read, it works like so:

startVertex = vertex V
for (egdes : totalEdges){
    find the edge with the smallest weight connected to vertex V that has    not been visited
}
nextVertex = vertex on the other end of the edge with the smallest weight
move to nextVertex

Here is an example:
Each vertex is visited and, looking at the red lines, you get an MST for that graph.

If you do that, you get an MST. My question is, is that a valid way of getting an MST? It seems like it is since it's so much like Kruskal's or Prim's algorithm.

Your algorithm starts at some vertex and then always move to the closest vertex that's not been visited so far. That's not guaranteed to find the minimum spanning tree, as the example in your question shows.

First, in a general graph, the algorithm might get stuck: you might end up at a vertex where you've already visited all the neighbours.  For example, if you start your algorithm at $D$, it will go to $B$, then $C$ and then it's stuck because it's already visited both of $D$'s neighbours. The set-up of Hamiltonian cycle avoids this possibility by having an edge between every pair of vertices.

Second, even if your graph contains every possible edge, the algorithm can only produce a path, so it won't produce the minimum spanning tree in any graph where the M.S.T. isn't a path.  For example, take vertices $\{1, \dots, n\}$ with $w(1,i)=1$ for all $i$ and $w(i,j)=2$ for all $i,j\geq 2$. The M.S.T. is all the edges from $1$, and this has weight $n-1$. But your algorithm will find some path that uses only one or two of the weight-$1$ edges, so will have weight $2n-3$ or $2n-4$.


How shall I resolve a nonlocal name in a language with deep binding? From Programming Language Pragmatics by Scott,

  Figure 3.14 Deep binding in Python. At right is a conceptual view of the run-time stack.
  Referencing environments captured in closures are shown as dashed boxes and arrows. When
  B is called via formal parameter P, two instances of I exist. Because the closure for P was
  created in the initial invocation of A, B’s static link (solid arrow) points to the frame of that earlier
  invocation. B uses that invocation’s instance of I in its print statement, and the output is a 1.

  The catch is that a running program may have more than one instance of an object that is declared within a recursive subroutine. A closure in a language with
  static scoping captures the current instance of every object, at the time the closure
  is created. When the closure’s subroutine is called, it will ﬁnd these captured instances, even if newer instances have subsequently been created by recursive calls.

So basically, the quote tries to explain that the following program (which is the same as the one in the screenshot) prints out 1:

def A(I, P):
    def B():
        print(I)
    # body of A:
    if I > 1:
        P()
    else:
        A(2, B)

def C():
    pass # do nothing

A(1, C) # main program

I don't quite understand the reason being "because the closure for P was
created in the initial invocation of A, B’s static link (solid arrow) points to the frame of that earlier invocation", and "When the closure’s subroutine is called,  it will ﬁnd these captured instances". So I modify the example, and then the new example prints out 2 instead of 1:

def A(I, P):
    def B():
        print(I)
    if I > 2:
        P()
    elif I > 1:
        A(3, B)
    else:
        A(2, B)

def C():
    pass

A(1, C)

Another modified example prints 1:

def A(I, P):
    def B():
        print(I)
    if I > 2:
        P()
    elif I > 1:
        A(3, P)
    else:
        A(2, B)

def C():
    pass

A(1, C)

So how can I know which closure matters when resolving a nonlocal name in a language with deep binding?

Generally, is a closure created whenever a function is passed as an argument to another function?

Thanks.

Roughly put, every time you define a function, as in def B(): ... you define B to be a closure. This is a pair contains a representation of the body of the function (possibly compiled to a simpler language), and a reference to the current environment (possibly restricted to what B actually needs). The current environment is the one we are in when we run def B(): ....

In the example you provide, B is defined inside A, so its associated closure gets a reference the the current call frame of A. This is why, if you pass P=B in the recursive call, after the call running P prints the value of I in the previous call frame.

Note that, in many languages, closures can be returned, which makes the current call frame to be not freed after the return. For example,

def A(I):
  def B():
    print(I)
  def C():
    nonlocal I  # Python for "use A's I, don't create a fresh local I"
    I += 1
  return (B,C)

# main
(b,c) = A(10)
b() # 10
c()
b() # 11
c()
b() # 12

Above, we can see that, even if A returned, its local variable I is still live! It can be accessed through the two returned closures, which contain a reference to the A's call frame, even if A is now finished.


Is L decidable or not Let $L = \{\lt M\gt | M$ is a $TM, L(M) = \{1^n0^n | n\ge0\}\}$.
Create a reduction from $A_{TM}$ (acceptance problem) to $L$. Is $L$ not decidable?
 But isn't $L$ decidable since it is possible to make a CFG (or PDA) of that language. And if I can make a reduction, $L$ would become not decidable because of $A_{TM}$.

The decision problem that corresponds to $L$ deals with the behaviour of Turing machines, not with strings of $1$'s and $0$'s.

More precisely, the decision problem is

  Given a Turing machine $M$, is it the case that $L(M) = \{ 1^n0^n \mid
> n \geq 0 \}$

A decider for this decision problem would take as input the description $\langle M \rangle$ of an arbitrary Turing machine $M$ and tell us if $M$ accepted exactly those strings that are of the form $1^i0^i$ for some $i \geq 0$. A pushdown automaton that recognizes the language $\{ 1^n0^n \mid
> n \geq 0 \}$ is clearly not such a decider.

A reduction from $A_{TM}$ to $L$ will, given an instance $\langle M,w \rangle$ build a description $\langle M' \rangle$ such that

$$M \text{ accepts } w \iff L(M') = \{ 1^n0^n \mid
> n \geq 0 \}$$

Here is $M'$:

  On input $x$

  If $x \neq 1^i0^i$ for some $i \geq 0$, reject
  Else simulate $M$ on $w$ and answer what $M$ answered.

Clearly, if $M$ accepts $w$ then $L(M') = L$. If $M$ does not accept $w$, then $L(M') = \emptyset$.


Why in simulated annealing, thermal equilibrium need to be meet for each temperature throughout the iterations? I have read in this book, simulated annealing, on page 40-41, if temperature $t$ tend to $0$, then the stationary distribution will be distributed among optimal solutions. What i can not understand here is that, if with temperature $0$, the stationary distribution will be distributed among optimal solutions, so why we need to have initially large temperature and reduce it slowly, so that at each temperature, the algorithm reaches the thermal equilibrium? Why do not we set the temperature to $0$ at the start of the algorithm and iterating until reaching thermal equilibrium for temperature $0$.

Form physical point of view, i know that, if in the annealing process, the temperature reduced quickly, the meta-stable amorphous structures will be reached rather than the low energy crystalline lattice structure. But from theoretical point of view, i can not understand the depth of the subject.

At temperature 0, simulated annealing degenerates into local search (also known as hill climbing). The problem with local search is that it gets stuck at local optima. Simulated annealing is a way to overcome this difficulty by letting the algorithm sometimes make moves that temporarily deteriorate the value of the current solution.


Detect cycles of odd total weight in a graph with {0,1}-weighted edges Given an edge-weighted digraph $G = (V, E \subseteq V^2, w \in E \to \{0, 1\})$, is there an algorithm that returns TRUE if there is a cycle in this graph whose total weight is odd and FALSE otherwise, which runs faster than $O((|V| + |E|)(c + 1))$ (where $c$ is the number of simple cycles in the graph, which is of course $\Omega(2^{|V|})$)?

As the question implies, I already came up with an algorithm that runs in $O((|V| + |E|)(c + 1))$ time. This algorithm involves first running Johnson's simple cycle enumeration algorithm, which gives us all the simple cycles in the graph. Since even + even = even, and all cycles are made by adding together simple cycles, the graph contains a cycle of odd length iff it contains a simple cycle of odd length. Thus, we just compute the parity of the simple cycles and return TRUE if any of them are odd, and FALSE otherwise.

Can anyone come up with a more efficient approach? Ideally, one that is not just "replace Johnson's algorithm with another simple cycle enumeration algorithm that has slightly better asymptotics", since the graphs I'm dealing with really aren't that large, and constant factors may well dominate as a result.

Construct the edge-vertex incidence matrix: rows correspond to edges, columns to vertices, and there is a $1$ if the edge is incident to the vertex. Add another columns full of $1$'s. You want to know whether there is a subset of the rows summing to the vector $0,\ldots,0,1$ (modulo 2). You can find out using Gaussian elimination, in polynomial time.

What is happening here? Let us consider the original edge-vertex incidence matrix. Rows corresponding to cycles sum to zero, since each vertex appears in exactly two edges. Conversely, if we have a set of rows summing to zero, then the degree of each vertex is even. Starting at an arbitrary edge, we can trace a walk that will eventually close onto itself. We remove the corresponding cycle (which need not contain the original edge), and continue. In this way, we see that a set of rows summing to zero correspond to an edge-disjoint union of cycles.

By adding an additional $1$ column to the matrix, we are tracing the parity of the cycle. An odd cycles sums up to the vector $0,\ldots,0,1$. Conversely, if a set of rows sums to $0,\ldots,0,1$, then it corresponds to a set of cycles whose total length is odd, so one of the cycles is odd.

Finally, finding whether a vector is in the row space of the matrix is a standard problem in linear algebra, which can be solved using Gaussian elimination and related algorithms.


Do languages in $\mathsf{coRE} \setminus \mathsf{R}$ have Turing machines? What can we say about languages in $\mathsf{coRE} \setminus \mathsf{R}$? Are there Turing machines for these languages?
I know that $\overline{HP} \in \mathsf{coRE}$ doesn't have a Turing machine, and also that all the language that do have Turing machines are in $\mathsf{RE}$, so is it true that for any language that is in $\mathsf{coRE} \setminus \mathsf{R}$ there's isn't a Turing machine? I wonder why is that so, can someone elaborate?

We can associate a language to a Turing machine in several ways.
If the Turing machine halts on all inputs, then the language accepted by the Turing machine consists of all words which cause the Turing machine to halt in an accepting state. The class $\mathsf{R}$ consists of all languages which are accepted by some Turing machine.
For an arbitrary Turing machine, the language recognized by the Turing machine consists of all words that cause the Turing machine to halt (in any state). The class $\mathsf{RE}$ consists of all languages which are recognized by some Turing machine.
If $L \in \mathsf{coRE} \setminus \mathsf{R}$, then in particular $L \notin \mathsf{R}$, and so no Turing machine accepts $L$. If $L$ were recognized by some Turing machine then $L \in \mathsf{RE}$. However, this is impossible, since then $L \in \mathsf{RE} \cap \mathsf{coRE} = \mathsf{R}$.


Instructing operating system - Knowing it's functionalities TL;DR: I would like to know how a programming language, the OS and drivers work together to perform a task.

I (and we all) have used various softwares/modules/packages on the top of our OS which provides us with a very simple API/GUI/CLI to perform tasks. But one question which keeps me disturbing is:

How does that software/module/package actually perform any specified action? I mean, it actually should be instructing OS to do that. So, OS should be providing procedure calls. But many functionalities aren't provided by the OS itself but the device driver provides it. So, how does the OS know what functions are supported by this particular device? And how can we instruct a particular device to perform a particular task?

Like suppose we are planning to change the IP address of a computer, we can do it through the OS's GUI or CLI. IP address is a logical thing and doesn't belong to a specific device (hardware), so we don't need any device driver for that. Keeping this simple, how can I write a module in python (without using already available API functionality) to change the IP address of a computer? Suppose the language itself i.e. python or a module/package written in python provides this functionality that calling a function such as change_ip() does the task. But how does it actually work in background? I know the background job is different for different OSes but I don't know how that module/package/language interacts with the OS. Or is it doesn't actually interact with the OS and performs the operations itself? (Maybe its possible in some cases)

Now, some other example. Suppose I would like to change the MAC address of the machine. Now, this operation is device dependent (the Network Card). Also, few NICs doesn't support this MAC changing functionality. This is actually dependent on the device driver and not the driver itself. So how can the OS know if the function is supported or not? Also, if the module/package/language is directly performing tasks without the help of OS, how can it know if the functionality is supported?

A very few might understand this question.. I don't know how to ask.. I am pursuing BE in Computer Engineering and I know several concepts and theories. But our education system makes us learn the things separately and not understand them in a combined manner. Like what would be the benefit if I know Operating System and Python but I don't know how they interact with each other and work in a combined manner. So, this is the base of my query.

I looked for an answer on Google but never found one.. Thank you..

There are many possible OSes, each one with its own design philosophy and technical conventions. Here's a rough, but reasonably common design for an OS.
Beware that, for brevity, I had to simplify things a bit and cut some corners. OS design is a huge topic (we have whole university courses covering that!), so don't expect this to be comprehensive.

First, we exploit some hardware support to separate the OS from the userland processes. At any time, a bit register inside the CPU tells whether the CPU is executing in "OS mode" (AKA supervisor mode) or "user mode".

In OS mode, the CPU runs unrestricted, and can read/write everywhere in RAM, modify any register of the CPU, send messages to devices ("To video card: make pixel at 542,234 black"), and so on. In user mode, the CPU can only read/write at some RAM address, and use only some CPU registers. It can not directly send messages to devices.

Crucially, it can not flip the bit which turns the CPU into OS mode, otherwise a process could bypass the protection and pretend to be the OS.

Well, almost. The CPU actually allows executing a kind of magic instruction -- let's call it help! -- which precisely flips that bit and put the CPU in OS mode. There is a big catch, though: help! also acts as a jump to a special address in RAM where OS code lies. So, a process can not go in OS mode and still execute its code, but it has to jump to a specific location, causing a part of the OS code to be executed.

Usually, before asking help!, the process writes some numbers in the CPU registers.

After help! is called, the OS reads those CPU registers, and interprets those numbers as a request from the process. For example, if in register r1 there is number 0, this could be a request to change a pixel in the screen (the pixel having coordinates in registers r2 and r3 and the new color in r4).
The OS then runs the code to ask the video card to change that pixel. Since every card likely requires a different message to be sent for that, the OS first calls a device driver with an hardware-independent message (color pixed X,Y as C) and that driver will then craft and send the message to the video card. Note that the driver is run in OS mode -- it is a component of the OS (in this basic design, at least).

If instead register r1 there is number 1, this could request a file to be opened (the file name being specified by r2). This could involve asking the disk diver to access the disk.

And so on. When the OS is done, it flips the CPU mode back to "user mode" and jumps to the process code, so that it can continue.

There are usually many possible requests from a process to the OS, usually specified by an ABI (application binary interface) which describes what registers to write and with what. Sometimes there's no public ABI, but programmers are supposed to call instead a usermode library, typically written in the C programming language. That library has a public API (in C), and will provide a bridge from that to the internal OS unpublished ABI.

There requests are known as "system calls" or "syscalls", by the way.

If you want to do a syscall in python, without relying on absolutely any library, you can not. This is because bare python does not give you a way to control the registers, or to run the help! instruction. Python is not special here, bare C also does not allow that, as with most programming languages.

Usually, though, one exploits some library. Or, if one really wants to go low-level, one can write a small module directly in assembly, and then call that from C or python (or anything else). That could require to use a "foreign function interface", so to link the assembly module with the language. In C it's usually very easy to do, since the language is low level. In python, calling assembly could be harder to do, but it's surely doable.

I strongly recommend you try to read an OS textbook. It should cover these topic in much more detail than we can do here.


Matrix covering by squares I wonder about the following decision problem :

Instance: We consider a $n\times p$ matrix $M$ of zeros and ones, and two integers $N$ and $k$.

Question: is it possible to cover all the ones of the matrix with $N$ squares of side length $k$?

It is possible that the squares cover some of the zeros in the matrix, and they can overlap with each other.

I get the impression that it is $\textsf{NP}$-complete (it is clearly $\textsf{NP}$), I find some similarities with Grid covering by rectangles but can't find a good reduction.

Might I get some insight on the problem?

Thanks.

EDIT: After days of reflexion, these are the ideas I've got:

I try to create a reduction from a Satisfiability problem with the following approach.

Given $\varphi = \bigwedge\limits_{i=1}^m C_i$ where $\forall i \in [\![1,m]\!]$, $C_i = (\ell_{i1}\vee \ell_{i2}\vee\ell_{i3})$ and $\ell_{ij}$ is either $x$ or $\neg x$ where $x\in\mathcal{V} = \{x_1,…,x_n\}$. I create the matrix $A$ with dimensions $(2m+2)\times (6n-1)$ defined by:

$\forall j \in [\![1,n]\!], a_{1,6(j-1)+3} = a_{2m+2,6(j-1)+3} = 1$;
$\forall i,j\in [\![1,m]\!]\times [\![1,n]\!]$, for $k = 2i - 1$ and $k = 2i$ and for $p = 6(j-1) +2$, $p = 6(j-1) + 3$ and $p = 6(j-1) + 4$, $a_{kp} = 1$;
all other coefficients are set to 0.

Here's a visual representation of the matrix:

With this matrix, if, for a variable $j$, we allow the use of $2m-1$ squares of size $2\times 2$, we can either cover all of (except extremities) the column $6(j-1)+1$ or the column $6(j-1) + 5$, but not both and not a mix between them. This can simulate a boolean variable!

The idea I got then was to put ones in the column $6(j-1)+1$ save if $x_j$ appears in the clause $C_i$ in which case, $a_{2i-1, 6(j-1)+1}$ and $a_{2i,6(j-1)+1}$ stay to zero (and do the same thing similarly in the column $6(j-1)+5$ with the $\neg x$ litteral).

If we then allow the use of $2n-1$ squares for each clause $C_i$, we need one of the variables to be set correctly in the clause to cover all ones in lines $2i-1$ and $2i$. The problem with this reduction is that you can "gain" some squares in a clause with multiples variables set correctly to change the disposition of a variable elsewhere.

My second idea was to create a reduction from $\texttt{ONE-IN-THREE-SAT}$, in which we ask if there is an assignation to $\varphi$ which satisfies exactly one litteral per clause, or even its restriction where we can suppose that $\varphi$ contains no negations, but I couldn't find something satisfying, so I'd like some help again!

This was proved NP-complete in "Optimal Packing and Covering in the Plane are NP-complete" (Fowler, Paterson and Tanimoto, Information Processing Letters 1981). I found a freely available version of the paper here. They give a neat reduction from 3SAT -- I'll summarise this below, but the paper is short and easy-to-read with several diagrams, and I recommend reading it!
For each variable they construct a "loop of wire" having an even number of points (1-cells in your formulation), and such that a single square can cover two adjacent points in the loop but no more. This means that there are two ways to cover all points in the loop using a minimal number of squares: Either use a square to cover points 1 and 2, another square to cover points 3 and 4, and so on, or use a square to cover points 2 and 3, another square to a cover points 4 and 5, and so on. Which minimal cover is used corresponds to whether the variable is assigned a value of true or false.
For each clause, they add a single extra point out to the right, and "extrude" the wire loops for the three relevant literals near this point. If any of them is in the right state, the extra point for this clause can be covered "for free" by a square in that loop. Negated literals are achieved simply by slightly compressing a few links in the loop, so that at a position to the right of the compression zone the "parity" of the wire is reversed.
In order to thread the loops through each clause they participate in, wires need to be able to cross over with their signals remaining independent. Interestingly, this "just works" without any additional gadgets.


Solving subgraph isomorphism in polynomial time So I am a bit confused about the reduction between SAT, subgraph isomorphism (SI) and graph isomorphism (GI).
I know that GI is in NP, and that SI is NP-complete.
So I'm thinking if we can decide instances of SAT in polynomial time, then we can also solve GI and SI in polynomial time since SAT is NP-complete and if one NP-complete problem is solved, then all others are also solved.

Am I correct? Thank you!

Here is a more general theorem:

  Let $X$ be some NP-complete problem. Then $X$ can be solved in polynomial time iff all problems in NP can be solved in polynomial time.

Indeed, if all problems in NP can be solved in polynomial time, then since $X$ is in NP, then $X$ can be solved in polynomial time.

In the other direction, suppose that $X$ can be solved in polynomial time. Let $Y$ be any problem in NP. Since $X$ is NP-hard, there is a polytime reduction $f$ from $Y$ to $X$. Using this reduction, we can reduce $Y$ to $X$, and so solve $Y$ in polynomial time. (I'm only sketching this part, since this is a standard argument which I assume you were shown in class.)


Trying to find two CFGs for the following languages I'm trying to get CFGs for these two languages which still remain unsolved in my practice problems sheet:
$L = \{ a^kb^ra^m | m=k+r\}$
$L = \{ a^nb^m | 1\leq n\leq 2m\}$
With the first one, I thought of this:
$$S\rightarrow aSa | T$$
$$T\rightarrow b T a | \epsilon$$
but what if $k>r$ or $r>k$?
With the second one, I think it is really simple but I cannot wrap my mind with $1\leq n\leq 2m$ (maybe I'm special...), should I have at least as many $a's$ as the double of $b's$ but not strictly? how could I specify that?

You can write the first language as
$$
\{ a^k b^r a^r a^k \mid k,r \geq 0 \}.
$$
The corresponding context-free grammar is exactly the one you give. If you apply $k$ times the rule $S \to aSa$ and $r$ times the rule $T \to bTa$, then you will get $a^k b^r a^r a^k$.
As for the second language, let us start with the slightly easier
$$ \{ a^n b^m \mid n \le 2m \}. $$
For each $b$ that you add, you can add up to two $a$'s. This leads to the grammar
$$ S \to Sb \mid aSb \mid aaSb \mid \epsilon. $$
In your case, you have to guarantee at least one $a$. Write this as follows:
$$
\{ a^{n+1}b^{m+1} \mid 0 \leq n \leq 2m+1 \} =
\{ a^{n+1}b^{m+1} \mid 0 \leq n \leq 2m \} \cup
\{ a^{n+2}b^{m+1} \mid 0 \leq n \leq 2m \}.
$$
Thus you can add the following rules to the preceding grammar, making $T$ the new starting symbol:
$$
T \to aSb \mid aaSb.
$$


Defining computable functions on arbitrary sets Turing machines take inputs that are strings of symbols from some alphabet, and they give outputs that are strings of symbols from the same alphabet. To show that a function is computable, we have to exhibit a Turing machine that computes it. In the case where the function is not from strings to strings, something about this bothers me.
I will introduce the problem with a simple example. Suppose that I define a function from binary trees to binary trees, and I want to show, formally, that it's computable. To do that I would have to exhibit a Turing machine that computes it. Since binary trees are not strings, I first have to design a string representation of binary trees. For example, I could represent the tree

as ((*,*),(*)). Having done this, I can then pass binary trees to Turing machines in string form, and get trees back in string form, no problem.
But here's my problem: the representation of binary trees as strings is itself a function (in fact a bijection) from binary trees to strings. How can I know formally that this function is a computable one?
On an intuitive level I have no problem seeing that it is, but on a formal level I can't exhibit a Turing machine to verify it, because then I would need a string representation of binary trees, and we quickly get into an infinite regress. For simple things like binary trees the computability of the representation is obvious, but for more complicated sets it might not be.
Can this circle be squared --- is there a formal definition of computability for functions of arbitrary countable sets that might not admit an obvious mapping to strings of symbols?
Additional thoughts
Here is another way of explaining my question: we might choose to define a model of computation that operates inherently on trees or some other set rather than strings. Indeed, many such models of computation have been proposed, including the lambda calculus and combinator calculi (which are arguably more naturally seen as operating on trees rather than strings), the recursive functions (which operate on integers), and various cellular automata (which operate on infinite strings or two dimensional lattice configurations, rather than finite strings). It's only really historical accident that led the string-based Turing machines to become the gold standard against which other models of computation are judged.
The problem is that without being able to talk about computable mappings between these sets, it's not strictly formally possible to say whether these other models of computation are equivalent to Turing machines or not. While it usually doesn't raise any practical problems to just think of everything in terms of string representations, it seems dissatisfying that our theory of computation doesn't treat all models of computation equally, but instead privileges those whose input and output are from a particular kind of set.
So really my question is whether a theory of computation exists has been formulated that is model-agnostic, in precisely this sense of not privileging one particular kind of set for input and output. It's quite an abstract question, motivated more by a desire for formal niceness than by any practical concerns.
One suspects, for example, that the category theorists might have done some work in this direction. This is because category theory tends to talk about the properties of functions without talking much about the sets they map, so a "category of computable functions" would probably not know or care whether its underling objects were sets of strings or something else. This is an approach I would be particularly keen to read about if it exists. (I've asked another question, specifically about the category theory aspect, over at MathOverflow.)

Effective model theory studies computable structures. The collection of all finite trees is a two-sorted computable structure in which one sort consists of vertices (which can be identified with the natural numbers) and the other sort consists of trees. It has the following relations:

$\operatorname{vertex}(x)$, which is true if $x$ is a vertex.
$\operatorname{tree}(x)$, which is true if $x$ is a tree.
$\operatorname{appears}(x,T)$, which is true if $x$ is a vertex that appears in the tree $T$.
$\operatorname{edge}(x,y,T)$, which is true if $x,y$ are two vertices in $T$ which are connected by an edge.

(We don't really need both $\operatorname{vertex}$ and $\operatorname{tree}$, but we do need to be able to express being in the domain of the structure, i.e., either a vertex or a tree.)

Formally speaking, to complete the definition of the structure we have to specify an encoding of the domain, either as strings or as natural numbers (this is an arbitrary choice which doesn't make much difference). Under any reasonable encoding, all the relations above will be computable, and so we have a computable structure.

A computable presentation of this structure is an isomorphism which maps this structure to another computable structure. This mapping has to be an isomorphism of structures, but it doesn't have to be computable. A computable structure $\mathcal{A}$ is computably categorical if whenevever $\mathcal{A}$ is isomorphic to a computable structure $\mathcal{B}$ (by a computable presentation), then there is a computable isomorphism between the two structures.

Using this vocabulary, what you might be asking is whether the computable structure of finite trees is computably categorical. (There is actually more freedom in your question, since you might want to use a different relational structure.) Some simple computable structures are computably categorical (for example, the rationals with the order relation, and the natural numbers with the successor function) and some aren't (for example, the natural numbers with the order relation), see Computable structures: presentations matter by Shore.


Implementation-level of a Turing machine that accepts a specific language I'm trying to figure out a way to implement this kind of a Turing machine that accept the following language:

$$\Sigma = \{ 0,1,2 \}, \quad\quad
L(A) = \{ abc \mid a=b \land c = a^R \}$$

I was thinking of a 3-tape Turing machine or using $\#$ symbol that separates the $a$, $b$ and $c$, but I'm struggling for the $c$ part.

I only need Implementation-level or the way it works.

I will use two tapes with deterministic Turing Machine.

Say you have $123321233223321B$ on first tape as input, where B is blank symbol.

At first use three states counter and add some symbol to the second tape, say # every third symbol. Check whether input is divisible by 3 (otherwise reject).

After first iteration you have:
$123321233223321B$
$#####$

Here you do not reject, as it is divisible by 3.
Now move elements from first tape to second one. After this step you have:
$1233223321$
$12332$

Compare elements from second tape with first one (deleting from first one). After that step you have:
$23321$
$12332$

Place head on first tape at the beggining and head of second tape at the end. Compare char by char moving in oposite directions (erasing symbols). If anywhere during comparison there was a mismatch then reject, otherwise accept (if this is required leave something in the first tape at that point).


Implementing a Boolean function with NOR gates Implement f(a, b, c, d) = Σ m(3, 4, 5, 6, 7, 11, 15) as a 2-level gate circuit
  (a) Using OR gates and NOR gates.
  (b) Using NOR gates only.

I have found that F=ab+d using Karnaugh map.
I have also been able to construct the logic expression using OR gates and NOR gates as in part a of the question.

Can you please provide me some idea on how to construct the logic expression ab+d using NOR gates only?

Please do not say this is a homework help question and close this thread.
I'm not asking to do the entire homework, I have only asked for some idea on how to do part b.

Hint: you know it's a two-level circuit using only NOR gates. There is only one such circuit:

  OUT
   |
  NOR
  / \
 |   |
NOR NOR
/ \ / \
? ? ? ?

Can you now figure out where to place a, b and d to correctly construct the circuit? Since you have to repeat (at least) one input, does looking at symmetry help?


Prove that $SEQ_{DFA}$ = {⟨A,B⟩ | A,B are DFAs and L(A) ⊆ L(B)} is decidable Consider the following language $$EQ_{DFA} = \{ \langle A, B\rangle: A \ and \ B \ are \ DFAs \ and \ L(A) = L(B)\}$$

Given the fact that $EQ_{DFA}$ is decidable, how can I prove that the language $$SEQ_{DFA} = \{ \langle A, B\rangle: A \ and \ B \ are \ DFAs \ and \ L(A)\subseteq L(B)\}$$ is also decidable?

Thank you in advance

There are several ways to prove that $SEQ_{DFA}$ is decidable. One of them is by using the fact that $EQ_{DFA}$ is decidable.

Assume that $L_1$ and $L_2$ are languages such that $L_1\leq_m L_2$ (that is, there is a mapping reduction from $L_1$ to $L_2$). It holds that if $L_2$ is decidable, then so is $L_1$. Hence,  in order to prove that $SEQ_{DFA}$ is deciadable, we reduce it to $EQ_{DFA}$. As hinted in the comment, we propose the following reduction.

The Reduction:
Let $C$ be a fixed DFA for the empty language, that is, $L(C) = \emptyset$. The reduction operates as follows. Given instance $\langle A= \langle Q_{A}, \Sigma, q^{A}_0, \delta_{A}, F_{A}\rangle, B= \langle Q_{B}, \Sigma, q^{B}_0, \delta_{B}, F_{B}\rangle\rangle$ of $SEQ_{DFA}$, the reduction computes a product automaton, $D$, for $L(A)\cap L(B)^C$ and outputs $\langle D, C\rangle$.
Correctness: $L(A)\subseteq L(B)$ iff $L(A)\cap L(B)^C = \emptyset$ iff $L(D) = \emptyset$ iff $L(D) = L(C)$. (the first equivalence mentioned in the comment is simple enough and thus is left for the reader).
Computability: the only non-trivial part is to compute $D$ given $A$ and $B$. We claim that $D$ is defined by $D = \langle Q_{A}\times Q_{B}, \Sigma, (q^{A}_0, q^{B}_0), \delta_{D}, F_{D}\rangle$. Where:

1) For every $(q, s)\in Q_{A}\times Q_{B}$ and $\sigma \in \Sigma$, $\delta_{D}$ is defined by: $$\delta_{D}((q, s),\sigma) = (\delta_{A}(q, \sigma), \delta_{B}(s, \sigma))$$

2) $F_{D} = F_{A}\times (Q_{B}\setminus F_{B})$.

Note that $D$ is a standard product automaton and thus for every finite word $w\in \Sigma^*$, we have that $\delta_{D}((q, s), w) = (\delta_{A}(q, w), \delta_{B}(s, w))$ (this can be proven by induction on $|w|$). Therefore, $w\in L(D)$ iff $\delta_{D}((q^{A}_0, q^{B}_0), w) \in F_{D}$ iff $(\delta_{A}(q^{A}_0, w),\delta_{B}(q^{B}_0, w) ) \in F_{A}\times (Q_{B}\setminus F_{B})$ iff $w\in L(A)$ and $w\in L(B)^C$ iff $w\in L(A)\cap L(B)^C$. Therefore $L(D) = L(A)\cap L(B)^C$ and thus we're done.