The Halting problem proof is wrong? First, let's see the pseudocode proof of halting problem:

P(x) =
  run H(x, x)
  if H(x, x) answers "yes"
      loop forever
  else
      halt

Then we have a problem:

When param x is the encoding string of P itself, the code line run H(x, x) will go to an infinite loop.

Because:

How does H know whether x halts on x?

The answer is H must simulate x on x, then it will call P(x) again and again, then go to an infinite recursive calling. So the pseudocode will stuck in this line run H(x, x), and never can continue.
So I think the pseudocode proof is not correct.

Edit:

H seems like a future teller of P. no matter what H says about P, when P actually act x on x, P does the opposite of what H says, which shows that the future teller of P does not exist.

We know that future teller does not exist. so the H does not exist.

First, let us see what the halting proof attempts to prove:

  There is no program $H$ that, on input $(x,y)$, always halts, and returns whether the program encoded by $x$ halts when run on the input $y$.

We call the function which $H$ is supposed to compute the halting predicate.

The program you are suggesting, which consists of simulating a run of program $x$ on input $y$, definitely doesn't always halt. What we are attempting to show is that there is no other devious way to computing the halting predicate in a way which does always halt.

The proof you are describing is a proof by contradiction. We assume that there is a program $H$ that always halts and computes the halting predicate correctly. Under this assumption, we reach a contradiction. Hence the conclusion is that no such program exists.

  How does $H$ know whether $x$ halts on $x$?

The assumption that the proof by contradiction is making is that there does exist an $H$ which computes the halting predicate. What the proof shows is that $H$ actually doesn't compute the halting predicate correctly. So $H$ cannot tell whether $x$ halts on $x$, and that is exactly what the proof shows.

  The answer is $H$ must simulate $x$ on $x$.

This is not true. There are similar predicates which can be computed. For example, we can decide whether a program halts on all inputs within 100 steps. We can do so even though there are infinitely many potential inputs, and so the naive solution, which is to run the program on all inputs for 100 steps, can be improved.

What the proof shows is that there is no computable way to decide whether a given program $x$ halts on a given input $y$. It doesn't show that $H$ must simulate $x$ on $y$; indeed, $H$ could store the answers for selected pairs $(x,y)$ in a table, and for these pairs it could just return the correct answer by doing a table lookup. This approach can only handle finitely many pairs $(x,y)$, and the proof shows that no other computable approach works.


PDA for all non-palindromic strings of even length I had a homework assignment where I had to build a PDA over the alphabet $\{a,b\}^*$, accepting $L = \{x \mid x \text{ is even but not a palindrome}\}$.

I already turned it in, but I know I had it wrong and it's driving me insane that I can't figure out this construction.

I tried a Cartesian product construction of the following languages and then deselected the accepting states of $L_2$, but I obviously did it wrong:

$L_1 = \{x \mid x \text{ is even}\}$

$L_2 = \{xx^R\}$, where $x^R$ denotes $x$ reversed.

I kept running into a problem where it would still accept because Palindromes are even and I was basically accepting all even numbers.

The solution is very much similar to PDA for palindromes of even length, except at atleast one place you have mismatched symbols.


The essential difference between spiking neural networks and earlier generation ANN's I have been studying Spiking Neural Networks online from various papers, mainly Maass (1997). I am not entirely sure I understand what makes SNN's pulse-code in contrast to earlier ANNs which are considered rate-code.
I have background in neuroscience so I understand the terms and ratio, I'm asking regarding the actual implementation.

Is the practical difference in the fact that when each neuron updates its current state in an SNN it deals with the entire history of every pre-synaptic neuron and not only the last step? Is that what gives it temporal characteristics which previous generation ANN's lack?

Yeah; each neuron in the spiking network integrates its input, instead of just summing the input of the previous timestep as in the old analog model.


Where I can I find Pre Trained CNN Datasets for Facial Emotion Recognition? I am working on a project that involves recognising emotion from images. There are two parts in the project: One where I will generate features from images using API's and then classify the emotion and the other part is where I will first use a CNN on a dataset and then take some layer of features and then give it to SVM to classify.

So, I need a dataset of images as well as pre-trained CNN on that dataset also. I have searched quite a lot on google and I am not able to find any. In some cases, I found a pre-trained CNN dataset but could not find the original dataset of images on which CNN was trained.

You are probably interested in IAPS, and want to read Analysis of Physiological Signals for Emotion Recognition Based on Support Vector Machine.

But to be honest this classification is doomed in advance, not only pictures are stripped of below threshold of effector activisation but also you do not get baseline as point of reference.

If you are really interested then start from reading everything that Ekman or Sejnowski wrote and feed your NN with only relevant parts, otherwise the most of the data feeded is noise.


What does the intersection symbol (∩) mean when applied to two non-set elements? I came across a piece of literature in which I saw the intersection symbol (∩) being used on two non-set elements in the definition of an equivalence relation; I have posted it below for reference. The elements in question are meant to represent different files on a computer. What could that intersection symbol mean in this context?

  Let $x_1$ and $x_2$ be two files and let v be a given computer virus. We then define the equivalence relation $R_v$ as follows:

  $x_{1}\!\mathit{R_{v}}\,x_{2} \;\; if \;\; x_{1} \cap x_{2} \in \left \{ x_{1},x_{2},v \right \}.$

  This is an equivalence relation and any equivalence class of a
  given element $x$ is defined by $C(x) = \left \{ y |y\in S \;\; and \;\; x \mathit{R_v} y \right \}$.
  The class $C(v)$ contains every file infected by $v$. Every class
  which is a singleton contains an uninfected file.

This text appears in the paper just before the excerpt above and may provide more context:

  Most of self-reproducing codes that exist at the present time
  are worms and thus a single copy of the malware is present
  in the system. But it is not the case as far as virus are considered
  (many copies exist in the system at the same time). In
  order for our model to be general, we will consider that all the
  different copies of a malicious codes are in fact a single one,
  e.g. the viral code. In the very special case of k-ary viruses,
  the viral code is the disjoint union of k different files.

  From a mathematical point of view, it is equivalent to consider
  the following equivalence relation, which is defined on
  a set S (the file system).

And even earlier, the text the author describes the $x_i$ variables as boolean variables:

  In order to define
  the working context, let is consider an operating system containing
  $n$ files ($n$ is of arbitrary size). These are all possible
  files that exist or may exist in the system at a given time.
  Each of these files are described by a Boolean variable $x_i$ ,
  $i = 1, 2, . . . , n$. No particular assumptions is made about the
  status of any of these files (executable or not, data. . .).

Source for the paper: https://link.springer.com/article/10.1007/s11416-007-0044-2

Eh.  $\cap$ doesn't mean anything on non-set variables.  Looking at the paper, that part of the paper doesn't make any sense to me either.  The paper says $x_1,x_2$ are Boolean variables, but the notation $x_1 \cap x_2$ is not well-defined on two Boolean variables; you can't take the set-intersection of two Boolean variables.  If $x_1,x_2$ were sets somehow (which the paper says they aren't), then the meaning of $x_1 \cap x_2 \in \{x_1,x_2,v\}$ is that either $x_1 \subseteq x_2$ or $x_2 \subseteq x_1$ or $x_1 \cap x_2 = v$.

So it's anyone's guess what that formula was supposed to represent.  If you absolutely must understand the paper, you'll probably have to read the surrounding context to guess what the intention was.  Better yet, find a better paper to read, if you can.  In any case, the reason you are confused is because what's written is confusing and seems like mathematical gibberish to me.  It happens; no one is perfect.  Don't assume that just because a paper is published in a journal, that what's written there will necessarily be correct or useful or meaningful.


Find $k$ subsets containing a particular element quickly Suppose there are $n$ subsets of $U$. I want to quickly (in terms of average-case) find k $ (< n)$ subsets that contain $e \in U$ (call this Extraction(e)). Elements are integers.

To that effect, I want to preprocess/encode the $n$ subsets so that this extraction operation can occur relatively quickly, regardless of what $e$ is (assume that this item is uniformly selected over queries).

I don't have a good intuition for various methods to do this and after how much prerocessing space/time diminishing returns kick in. I'm certainly looking for something that takes polynomial time/space.

I was thinking about encoding the subsets as hashsets and then hashing together $q$ of these subsets together at a time, so that I end up with $\lceil\frac{n}{q}\rceil$ packaged hashsets. $q$ would be inferred in some fashion from the frequency distribution of all elements in U. Then I could iterate over these packaged hashsets and check for containment of $e$ in constant time (average-case).

Is this problem well-studied?

Use a hash table, keyed on elements of $U$.  For each subset $S$ of $U$, say $S=\{x_1,\dots,x_\ell\}$, you'll add $S$ to the hash table $\ell$ times, once for key $x_1$, once for key $x_2$, and so on.  Now to find all subsets containing some element $e$, just look into the corresponding bucket in the hash table and you can iterate over sets containing $e$ very rapidly.

This is basically just applying the idea of "indexes" from databases to your problem.  It is straightforward and provides excellent time complexity, at the cost of modest space complexity (approximately doubling the space needed to store all of the subsets).


Prove that finding largest subset of undirected graph that is almost independent is NP-hard A subset $S$ of vertices in an undirected graph $G$ is called almost independent if at most 100 edges in $G$ have both endpoints in $S$. Prove that finding the size of the largest almost-independent set of vertices in a given undirected graph is NP-hard.

For these types of problems, I know that I should try to find a polynomial time reduction of an algorithm that is already known to be NP-hard.  I tried my hand at trying to manipulate the k-coloring problem, but without any luck.

How would I go about proving this function is NP-hard?

The proof is by reduction from independent set. Given an instance $(G,k)$ of independent set, construct a new instance $(G',1000k)$ in the following way: each vertex $x \in G$ is replaced by an independent set $I_x$ of size 1000, and each edge $(x,y)$ is replaced by a complete bipartite graph $I_x \times I_y$.

If $G$ contains an independent set $S$ of size $k$, then $G'$ contains an independent set $\bigcup_{x \in S} I_x$ of size $1000k$. In the other direction, suppose that $G'$ contains an almost independent set $S$ of size $1000k$. Remove all vertices incident to any edges within $S$ to obtain an independent set $S' \subseteq S$ of size at least $1000k-200$. Let $T = \{ x : I_x \cap S' \neq \emptyset \}$, and note that $T$ is an independent set of $G$. Finally, since $S'$ can contain at most 1000 vertices from each $I_x$, we see that $|T| \geq \lceil |S'|/1000 \rceil = k$.


What are the essential differences and similarities among "data", "Information" and "knowledge" in the context of Computer Science? The terms "data", "information" and "knowledge" are quite interchangeably used in Computer Science. Strictly speaking, they do carry a very different meaning. I want to know their precise meanings and their context and usage.

According to my limited experience, data is simply "raw fact and figures" whereas information is "meaningful data" and knowledge is information via which one can predict the unknown or infer something new. Please correct me if I am wrong.

You're description is pretty accurate. There is no formal definition or precise meaning coming from a high level. There are only formal definitions in specific fields such as information theory for Information (bits) and knowledge such as in cognitive architectures. Data doesn't have a precise meaning either, haven't seen a formal model of that in any case.


Is it Possible to Get Maximum Weighted Input Value in a Neural Network? Let's say that I have a standard feedforward neural network which has $M$ inputs, some number of hidden layers $N$, and a single neuron in the output.

Is it possible to construct a network such that the output neuron's output value is the maximum weighted input value?

I know that I could easily hard code something to make this happen, but I'd like to limit the construction to "standard" operations where the activation of a neuron is the dot product of the input vector and the weight vector with a bias added, then putting that value through a differentiable activation function.

No, not with standard activation functions, but you might be able to approximate it.  For instance, if the activation function is differentiable, then the output of such a network will always be differentiable, but the "max" function is not differentiable.

You're more likely to get a useful answer if you provided some context about what you're trying to accomplish or how you'll use the answer.  I suspect an XY problem.


Where do you exactly use data structures? I know what data structures is, How it works & importance of it. I just have some doubts on where do we actually use it.

When database can do filtering, fetching, sorting efficiently, Why we need to use data structures in db data?

I was working on a project which uses Cassandra database. In that I'd to filter data based on two fields. The two fields are indexed. But I can't filter it as it will force me to use Allow filtering but It's not a recommended one.

In this case I thought to fetch rows filtered by one indexed column & rest by our program (Java/Python etc) so we need to use better data structure here. Is this a correct approach? If not what's the solution for these kind of problems?

Let's assume I've billions of list of string data in a db table, I want to use it for autocomplete for that it's better to use tries data structure, How can I do this? fetch all data into memory and process?

If my approach is wrong, Are data structures mainly used for in memory data?

This is a broad question but will attempt to answer.

From my understanding of your question, you have billions of strings which you want to use for autocomplete.

The way most typical autocomplete examples work is you load the entire set of strings into memory and build a trie. That works well for small datasets like the list of countries, or a small list of tags.

Searching for how google implements its autocomplete doesn't return any results, but that would be sort of what you're asking I'd think.

What I imagine is slow in your current implementation is, you have billions of rows in your database, with a column containing the string of interest. Then you are just doing a LIKE search to match substrings. So it has to scan every string in the billions of records, which is very slow.

The (typical relational) database won't offer you much support here.

One solution to this problem is to use a "full text search database" such as Lucene. The problem this solves is indexing. Another related index that might help is an inverted index. An inverted index might use a B+tree for indexing the terms (words perhaps) in documents (or strings in your case). But this just means it will match individual terms/words, not complete sentences or exact substring matches like the LIKE query will do.

So you have to decide how you want your autocomplete to work. If they can search for exact strings in the text, then the best solution is probably to create a gigantic trie for all the strings. If the trie doesn't fit into main memory, as probably is your case, then you could potentially try creating a string b-tree data structure instead of a trie. This is better as an on-disk data structure. If instead they can search for tokens/terms/words like a keyword search, then you can use an inverted index B-tree, such as with Lucene. Either way you will need another data structure on top of the relational database, and probably one that efficiently works with a file system.


DFA - Equivalence classes I am preparing for my exam in formal languages and I need some help with one question from one old exam.

I know that the number of equivalence classes of some regular language L, is the number of states of the minimal DFA for that language.

But how do I give a DFA for one of the equivalence classes ?

Thanks in advance

An elaborate hint: recall that the proof of the Myhill-Nerode theorem works (in one direction) by constructing a DFA for a language, given its equivalence classes.

In the constructed DFA (i.e the minimal DFA), each state corresponds to an equivalence class. We then set the accepting states to be those that correspond to equivalence classes that are contained in the language.

Now, suppose you create the DFA for the equivalence classes of $L$, without knowing in advance which equivalence classes are in L, and which aren't. If you choose one particular class, and set the state that corresponds to it to be accepting, then the language of the DFA is exactly that equivalence class, which is what you wanted.

Indeed, the property of the minimal DFA is that for every two words $w,w'$, the runs of the DFA on $w$ and on $w'$ end in the same state iff $w\equiv_L w'$.

Observe that you may end up with a DFA that is not minimal for the equivalence class.


If P is a property of turing machines, does P $\leq_T$ COUNT_P imply that P $\in$ RE $\cup$ coRE? Fix an input and tape alphabet $\Sigma$ and $\Gamma$. Let P be a property of turing machines over these alphabets, i.e., a subset of $\{\langle M \rangle \mid M \text{ is a TM over the alphabets } \Sigma \text{ and } \Gamma\}$. Define COUNT_P to be the function $\mathbb{N} \to \mathbb{N}$ describing the number of $n$-state turing machines over these alphabets which satisfy property $P$ (here, we also fix the states to be $\{1, 2, \dots, n\}$, so that we can't have two turing machines which are the same but with differently named states. Basically, we want the set of $n$-state turing machines to be finite).

One can show that if P is a recognizable (or co-recognizable) property, then P $\leq_T$ COUNT_P (here $\leq_T$ denotes Turing-reducibility). What can be said about the converse of this statement? Indeed, if P $\leq_T$ COUNT_P, is P either recognizable or co-recognizable? I don't have any real reason to believe that this is true or false, but just would like to know an answer in either direction (seems difficult to find a counter-example or to prove it to be true).

Let $L \subseteq \mathbb{N}$ be a set of your choice, let $N(M)$ be the number of states in a Turing machine $M$, and let $P = \{ \langle M \rangle : N(M) \in L \}$. Then $P$ reduces to $\mathsf{COUNT}_P$, but $P$ can be arbitrarily hard.


Sorting a stack using Bubble sort How to sort a stack using bubble sort? Can use another stack if necessary.

You must need an extra stack to sort an stack. With the help of two stacks this problem can be solved.

So, suppose you have n elements in the stack. and you have an other stack, which is empty.

Now, in bubble sort, after each iteration highest element reaches to its final position. So, to implement this algorithm, we can make use of that second stack.

For the first Iteration:
There are n elements in the stack, pop each element one by one in the empty(second stack) stack and keep track of highest element at each stage. After the first stack is completely empty, you will have the highest element of the stack. Now push that highest element in the first stack and then pop all the elements from the second stack and push them in first stack. So, after this iteration, highest element is set to its position. and we now have n-1 unsorted elements. Be alert to not to push highest element again in the first stack.

  for example, elements are 5,10,7,2,15. So, after first iteration stack
  content is 15,5,10,7,2.

For the next Iterations:
So, after 1st iteration highest element is set, and we are remaining with n-1 unsorted elements in first stack, while the second stack is empty. So, during this iteration, instead of n elements, pop only n-1 elements to the second stack and keep track of maximum. After n-1 elements are pushed to second stack we have highest element among those n-1 elements, which second highest element of original stack. Push that element in the first stack, above the highest element already there. And then push all the elements back in the first stack from second stack.

  So, after first iteration stack content is 15,10,5,7,2.

Then reduce the size to n-2 and follow same method.

Complexity of this method is same as bubble sort, which is $O(n^2)$.


What is the intuition on why the longest path problem does not have optimal substructure? I was learning about longest paths and came across the fact that longest paths in general graphs is not solvable by dynamic programming because the problem lacked optimal substructure (which I think the statement needs to be corrected to longest simple paths on general graphs is not solvable by dynamic programming).

If we assume they have to be simple (for some reason this is required which I don't appreciate yet) and longest, then its easy to create a counter example. Consider the square graph with 4 nodes A→B→C→D→A.

A longest path from A to D is clearly A→B→C-D. But the longest path from B to C is not part of the longest path to from A to D because the longest path from B to C is B→A→D→C which is clearly not the same as the path B→C (which in this case is in fact a shortest path!).

This seems to work only because we required the paths to be simple. Is it necessary to assume that the paths must be simple for us to prove that optimal substructure is not present?

I think that the counter example should be good evidence/proof (which I don't deny), I just don't find the counter example very enlightening at all. I see why it proves the point that it doesn't allow optimal substructure but it fails to provide me real understanding or intuition why it should be obvious that there should be no longest path optimal substructure. Like for example, why doesn't a cut and paste argument work? If the subpath isn't longest, then just stick in a longer path! It sounds very tempting, I mean, if we put in place something longer then of course it should get longer...though, this is for some reason wrong. Does the example actually in fact prove that DP can never solve longest (simple?) paths efficiently? I don't require for a general proof that its not in P (since thats might be asking for a P vs NP solution). I am just after a proof that its not solvable by DP (or at least very strong evidence that DP can never solve this longest paths problem or that the problem does not have optimal substructure).

I have definitively seen in wikipedia that the problem should be NP-Hard, which means that there is probably no fast algorithm. Not sure if that is the only type of evidence/intuition that exists to provide that optimal substructure should be obviously lacking (or if its not lacking, that it can't be used to make the problem faster). Is that the only way to show that it should not be solvable by a fast dynamic program?

Is the reason we require simple just because if we don't place that requirement the problem becomes trivial/uninteresting? In other words, if there is any cycle then one has solved the longest path problem to all nodes reachable from that cycle (by finding any path to that cycle). For the nodes that don't have any cycle reachable, we have a acyclic graph, which is solvable by DP (if the weights are positive?). In addition if there are cycles, we have automatically made things have optimal substructure (I think) because any longest path just is made up of longest path which covers two cases, 1 the paths through the cycle or 2 the paths through the DAG, which both contain optimal substructure. So the problem has become trivial without the requirement of simple paths? Or am I missing something or are there better explanations to why simple paths are required? Doesn't the algorithm in this paragraph show that general longest paths are solvable by DP?

I am also not 100% sure what requirements are needed to guarantee that DP can't be used. Is it necessary to negative edge weights, positive, un-weighted, directed, undirected...what are the requirements?

The longest path problem does have optimal substructure, and this can be used to improve the trivial $O(n!)$ algorithm to an $\tilde{O}(2^n)$ algorithm. First we have to generalize the problem:

  Generalized longest path: Given a graph $G=(V,E)$, two vertices $s,t \in V$, and a set of vertices $A \subseteq V \setminus \{s,t\}$, find the longest path in $G$ from $s$ to $t$ avoiding the vertices in $A$.

Denoting the solution to this problem by $\ell(s,t,A)$ (the graph is understood), we have the recurrence
$$
\begin{align*}
&\ell(s,t,A) = 1 + \max_{\substack{x \notin A \cup \{s\}: \\ (s,x) \in E}} \ell(x,t,A \cup \{s\}) \qquad (s \neq t), \\
&\ell(t,t,A) = 0.
\end{align*}
$$
If the maximum in the first case is over the empty set (that is, if there is no path from $s$ to $t$ avoiding $A$), we assign $\ell(s,t,A) = -\infty$.

You can solve this recurrence using dynamic programming in time $\tilde{O}(2^n)$.

While there is optimal substructure here, there are too many parameters to keep track of, and this is what makes the problem intractable.


Context free grammar for $L=\{a^n b c^n | n \ge0\}$ I'm having trouble with this problem. Can't find a CFG. Someone an idea?

$$L=\{a^n b c^n | n \ge0\}$$

$$\begin{align}X&\to aXc\\
               X&\to b\end{align}$$


Does 2NF require 1NF? From Database   System Concepts, by  Silberschatz, Korth and Sudarshan :

  A domain is atomic if elements of the domain are considered to be
  indivisible units. We say that a relation schema R is in ﬁrst normal form (1NF) if
  the domains of all attributes of R are atomic.

  A functional dependency A →B is called a partial dependency if
  there is a proper subset C of A such that C → B. We say that B
  is partially dependent on A. A relation schema R is in second
  normal form (2NF) if each attribute X in R meets one of the
  following criteria:

  • It appears in a candidate key.

  • It is not partially dependent on a
  candidate key.

If I am correct, the definition of 1NF in the book is the same as in Wikipedia which says

  A relation is in first normal form if and only if the domain of
  each attribute contains only atomic (indivisible) values, and the
  value of each attribute contains only a single value from that domain.

Is the definition of 2NF in the book the same as in Wikipedia
    which says

  a relation is in 2NF if it is in 1NF and no non-prime attribute is dependent on any proper subset of any candidate key of  the relation.

?

Specifically:

I don't think the definition of 2NF in the book requires a relation
schema being in 1NF, and I wonder if I am wrong and why?
While 2NF is related to functional dependency, is 1NF related to
functional dependency between attributes in a relation schema? (I
don't see the definition of 1NF involves functional dependency.)
Does the definition of 2NF in Wikipedia require that there can't be duplicate rows?

Does the definition of 2NF in Wikipedia rely on a different
definition of 1NF? For example, see
Does 1NF require that there can be no duplicate rows?

Thanks.

I will focus on questions 2 and 3, mainly by recalling a little bit of history of the Relational Data Model.

The first foundamental paper on the Relational Model was published in 1970 by the Turing Award Edgar F. Codd, Codd, E. F. “A Relational Model of Data for Large Shared Data Banks.” Communications of the ACM 13, no. 6 (June 1, 1970): 377–87. (bibliographic description, search pdf).

In that paper it is expressed clearly that relations are sets:

  The term relation is used here in its accepted mathematical sense. Given sets S1, S2, ... , Sn, (not necessarily distinct), R is a relation on these n sets if it is a set of n-tuples each of which has its first element from S1, its second element from S2 , and so on ...

So, the requirement of the unicity of the tuples precedes each possible definition of normal form.

Noting that the Codd’s definition leaves open the possibility that the elements of the domains (the Si) can be complex, for instance repeated, Codd introduced the first normal form (1NF) in a 1972 paper:  “E. F. Codd (Oct 1972), Further normalization of the database relational model, Courant Institute: Prentice-Hall, ISBN 013196741X,”. In such paper it is said that:

  A relation is in first normal form if it has the property that none of its domains has elements which are themselves sets.

As you have noted, this has nothing to do with functional dependencies, neither with other forms of dependencies (multivalued, join, etc.), and for this reason, it has been considered an essential requirement of the “normal” Relational Data Model. Other data models, the so called non-1NF model, abandon this requirement, and constitute a sort of bridge towards late object-oriented data model (but this is another subject...)

Only later, C.J. Date, a collaborator of Codd, wrote in the paper: “What First Normal Form Really Means,” in “Date on Database: Writings 2000-2006. Berkeley, Calif., Apress (2006)”:

  A table is in first normal form if and only if it is "isomorphic to some relation" ... There are no duplicate rows...."

The emphasis is mine, note that he’s talking about tables, not relations, specifying what are the characteristics that tables should have to be considered relations.

So, to summarize:

The relational model is based on the mathematical concept of relation, which is a set.
The 1NF has nothing to do with functional dependencies, and in the original definition has only to do with complex values (i.e. relations) inside tuples.
The other normal forms are defined ony in the context of the relational data model, in which relations are set.
Relational Database Management Systems (RDBMS) manage “tables”, which are loosely modeled on the mathematical concept of relation as defined in the Relational Data Model, but the normalization theory (functional dependencies, other kind of dependencies, normal forms, etc.) is only partially applicable to them, since it is defined only on the Relational Data Model.


Calculate minimum and maximum Ethernet (IEEE 802.3) frame size from frame format According the frame format of Ethernet

Minimum Frame Size should be :

7Bytes + 1Bytes + 6Bytes + 6Bytes + 2Bytes + 46Bytes +4Bytes = 72Bytes

Maximum Frame Size should be :

 7Bytes + 1Bytes + 6Bytes+ 6Bytes + 2Bytes + 1500Bytes + 4Bytes = 1526Bytes

But it is said that the minimum frame size is $64Bytes$ while the maximum frame size is $1518 Bytes$.

How the frame sizes are calculated ?

The preamble and SFD do not count towards the frame size since they are only part of the Ethernet packet (i.e., layer 1), not of the Ethernet frame (i.e., layer 2); see here, for instance. Recall that Ethernet is not a pure layer 2 protocol but actually a mix of layers 1 and 2.


Why do compilers produce assembly code? Assembly language is converted in to machine language by assembler. Why would a compiler convert high-level language to assembly? Can't it directly convert from the high-level language to machine code?

Other reason for compilers to produce assembly rather than proper machine code are:

The symbolic addresses used by assemblers instead of hard-coding machine addresses
 make code relocation much easier.
Linking code may involve safety checks such as type-checking, and that's easier
 to do with symbolic names.
Small changes in machine code are easier to accomodate by changing the assembler
 rather than the code generator.


Can a new company make a processor compatible with Windows and current software? Would anyone apart from Intel and AMD ever be able to make a processor that can be used on a personal computer, or is it impossible? I believe it is due to them owning the x86 instruction set, which means that a company doesn't have the right to produce a processor which could run a personal computer. But what if the processor used a different instruction set, but in between it translated the x86 architecture to its own? Would that also be breaching the ownership?

In theory a new microprocessor manufacturer could enter the market. In practice this is very unlikely, but not for any reason to do with the x86 architecture - the barrier is economics.

Manufacturing modern microprocessors is a highly complex engineering challenge which requires a lot of very expensive equipment. Getting the design right in the first place requires a massive upfront investment. And the profit margin on each unit is tiny, so in order to turn a profit you also have the additional overhead of investing in automation - you cannot just employ an army of production line staff.

A saturated market place with established players, high fixed costs and low profit margins is not going to be attractive to start-ups or new entrants, or to their investors.

The one thing that might change this is a breakthrough in technology. If you invent a way to manufacture a portable quantum computer from household waste in your garage using a few DIY tools, then you are home and dry.


Efficient encoding of sudoku puzzles Specifying any arbitrary 9x9 grid requires giving the position and value of each square. A naïve encoding for this might give 81 (x, y, value) triplets, requiring 4 bits for each x, y, and value (1-9 = 9 values = 4 bits) for a total of 81x4x3 = 972 bits. By numbering each square, one can reduce the positional information to 7 bits, dropping a bit for each square and a total of 891 bits. By specifying a predetermined order, one can reduce this more drastically to just the 4 bits for each value for a total of 324 bits. However, a sudoku can have missing numbers. This provides the potential for reducing the number of numbers that have to be specified, but may require additional bits for indicating positions.  Using our 11-bit encoding of (position, value), we can specify a puzzle with $n$ clues with $11n$ bits, e.g. a minimal (17) puzzle requires 187 bits.  The best encoding I've thought of so far is to use one bit for each space to indicate whether it's filled and, if so, the following 4 bits encode the number. This requires $81+4n$ bits, 149 for a minimal puzzle ($n=17$). Is there a more efficient encoding, preferably without a database of each valid sudoku setup? (Bonus points for addressing a general $n$ from $N \times N$ puzzle)

It just occurred to me that many puzzles will be a rotation of another, or have a simple permutation of digits.  Perhaps that could help reduce the bits required.

According to Wikipedia,

  The number of classic 9×9 Sudoku solution grids is 6,670,903,752,021,072,936,960 (sequence A107739 in OEIS), or approximately $6.67×10^{21}$.

If I did my math right ($\frac{ln{(6,670,903,752,021,072,936,960)}}{ln{(2)}}$), that comes out to 73 (72.498) bits of information for a lookup table.

But:

  The number of essentially different solutions, when symmetries such as rotation, reflection, permutation and relabelling are taken into account, was shown to be just 5,472,730,538[15] (sequence A109741 in OEIS).

That gives 33 (32.35) bits, so it's possible that a clever method of indicating which permutation to use could get below the full 73 bits.

Is there a more efficient encoding, preferably without a database of each valid sudoku setup?

Yes. I can think of an encoding improving your 149-bit encoding of a minimal $9\times 9$ puzzle in 6 or 9 bits, depending on a condition. This is without a database or any register of other solutions or partial boards. Here it goes:

First, you use $4$ bits to encode a number $m$ with a minimal number of appearances in the board. The next $4$ bits encode the actual number $\ell$ of times $m$ appears. The next $7\ell$ bits encode each of the positions in which $m$ appears.

The following $81-\ell$ bits are flags indicating whether the remaining positions have a number or not (you just skip the positions in which $m$ is). Whenever one of these bits is 1, then the next 3 bits indicate which number it is (in the ordered set $\{1,\ldots,9\}$ without $m$). For example, if $m=4$ and the 3 bits are 101, then the number in the corresponding position on the board is the the 5th (counting from 0) in the set $\{1,2,3,5,6,7,8,9\}$, so it is $6$. Numbers $j<m$ will be encoded in binary as $j-1$, while numbers $j>m$ will be encoded as $j-2$. Since we had already written $\ell$ positions, only $3(n-\ell)$ bits will be added to encode the rest of the board in this step.

Thus, the total number of bits required to encode a board using this procedure is $$B=4+4+7\ell+(81-\ell)+3(n-\ell)=89+3\ell+3n.$$

For $n=17$, we note that $\ell$ can be 0 or 1 (in general, $\ell\leq\lfloor n/9\rfloor$). Thus, $B$ can be 140 or 143 depending on whether there's a number not appearing on the board.

It's worth pointing out that Kevin's solution is way better in the general case. This encoding uses at most 149 bits only for $n\in\{17,18,19\}$, or for $n=20$ provided that $\ell=0$. At least it shows a general idea on how to take advantage of the fact that $N=9$ is very close to $2^{\lfloor\log_2N\rfloor}$ (which means we tend to "lose memory" by using 4 bits per value, since 4 bits allow us to express $N=16$ numbers as well.

Example. Consider the following board with $n=17$ clues.

.  .  .   .  .  .   .  1  .
4  .  .   .  .  .   .  .  .
.  2  .   .  .  .   .  .  .

.  .  .   .  5  .   4  .  7
.  .  8   .  .  .   3  .  .
.  .  1   .  9  .   .  .  .

3  .  .   4  .  .   2  .  .
.  5  .   1  .  .   .  .  .
.  .  .   8  .  6   .  .  .

Here, no number does not appear on the board, and numbers 6, 7 and 9 appear only once. We take $m=7$ (0111) and $\ell=1$ (0001). Reading the positions from left to right and then from top to bottom, $m$ appears in the position $36$ (0100100). Thus, our encoding begins with 011100010100100.

Next, we need seven 0s, one 1 and the 3-bit encoding of the number $1$, then a 0 followed by a 1 and the 3-bit encoding of $4$, etc. (0000000100101100). Eventually, we will skip the position where $m=7$ is, and we will encode 8 as 110 (the 6th number counting from 0 on the list ${1,2,3,4,5,6,8,9}$) and 9 as 111. The full encoding goes as follows:

// m=7, l=1 and its position on the board.
011100010100100
// Numbers 1 and 4 at the beginning. Note that 1 is encoded 000, and 4 is 011.
0000000100001011
// Numbers 2 and 5.
0000000001001000000000001100
// Numbers 4 and 8. We skip the appearance of 7 and encode 8 as 110.
010110001110
// 3, 1 and 9. 9 is encoded as 111.
00010100000100001111
// 3, 4, 2, 5, 1, 8, 6 and the last empty cells.
0000101000101100100100011000100000000000111001101000

The complete encoding is 01110001010010000000001001010110000000001001000000000001100010110001110000101000001000011110000101000101100100100011000100000000000111001101000, and the reader can check the length of that string is indeed 143 :-)


Inductive proof for the Bubblesort algorithm I'm studying Algorithms and Data Structures from The Algorithm Design Manual and I'm having a hard time going through the exercises.
Specifically, the proofs are a bit hard and not really explained in the book(It only gives two proof exmaples).
Prove the correctness of the following sorting algorithm.
    Bubblesort(A)
        for i from n to 1
            for j from 1 to i − 1
                if (A[j] > A[j + 1])
                    swap the values of A[j] and A[j + 1]

I would really appreciate if you could help me with an inductive (or any kind of proof I don't really know) for this exercise.

What is a Proof of Correctness:
Algorithms are identified with pre-conditions and post-conditions. The pre-conditions are assumptions you make about the algorithm's inputs. Post-conditions describe what we want the algorithm to have accomplished once it terminates.
For an algorithm to be considered "partially correct", whenever the pre-conditions hold, the post-conditions must follow. For it to be considered "totally correct", it must be partially correct and halt, i.e. take a finite number of steps.
Pre and post-conditions are something one specifies about an algorithm, not something one proves about it. A typical precondition for a sorting algorithm might be "A[1...n] is an array of integers". A typical postcondition might be "A[1...n] is a sorted array of integers with the same values it had before the algorithm was executed".
That's a lot of formalism to get out of the way before we even talk about the problem, but it's important to be rigorous.
Showing Bubblesort is correct
To show Bubblesort is correct, we should show that the post-conditions follow assuming the pre-conditions hold. Total correctness will follow since Bubblesort trivially halts.
Loop Invariants
This is something you see everywhere in proofs of correctness that have loops. Instead of talking about the whole algorithm "at once", it's useful to come up with something that will be true for each iteration of the loop. This often lends itself to an inductive argument. The loop invariant you want to come up with is something that will help you conclude what you want to conclude at the end of the day - that A[1...n] is sorted once we terminate.
Here's what I came up with to that end. For any iteration $i$ of the outer loop: For any $a \in \{1,...,n\}$:
If there is a $b \in \{1,...,n\}$ such that $a>b$ but $A[a]<A[b]$ at the start of the iteration, then at some point in the inner loop, $A[a]$ and $A[a-1]$ will swap. Similarly, if there is a $b>a$ such that $A[a]>A[b]$, then $A[b]$ and $A[b+1]$ will have swap at some point in the inner loop.
Else, $A[a]$ won't change.
To prove this, it would be helpful to first show that whenever an $a$ satisfies the conditions in the "If" part, $a \leq i$ is true. This lemma could use an inductive argument. By the way this is one (possible clunky) way of coming up with the invariants, you might have a more concise way of phrasing what you need. I haven't written the full proof so I might have inefficiencies up there.
Wrapping Up
Once you show the loop invariants above are true, we can use them to conclude that $A[1..n]$ comes out the other end a sorted list of integers. Let $A[1..n]$ refer to the original list, and $A'[1...n]$ refer to the modified list. Let $a \in \{1,...,n\}$ be arbitrary, and let $c \in \{1,...,n\}$ be a correct sorted index of $A[a]$ in $A[1..n]$, i.e. $c$ is the index $A[a]$ should be at in a sorted version of $A$. We want to show that $A'[c]=A[a]$.
If $a$ was already in it's correct position in $A[1..n]$ (i.e. $a=c$) then we're done, because this means for any $b < a$, $A[b]<A[a]$, thus the swap condition in the inner loop will never be satisfied, meaning $A'[a]=A[a]$. Otherwise, either there exists some $b<a$ such that $A[b] > A[a]$, or some $b>a$ such that $A[b]<A[a]$. In either case, the loop invariants tell us that $A[a]$ will move at least one step in the correct direction after each outer-loop iteration. The maximum distance between $a$ and $c$ is $n-1$, and since the "Else" of the loop invariant essentially tells us that $A[a]$ will stop moving when $a=c$, we can say that $A[a]$ will get to index $c$ and stop, so $A'[c]=A[a]$ as required.
That's the gist of it, I left out the proofs of the invariants, and there might be other gaps in my response. Hopefully you can fill those in. Sorry for the long answer.


String matching and bioinformatics I'm interestd in string-matching, I would like to know recent open problems in string-matching in field of bioinformatics.

The list of open problems in bioinformatics: string matching is outlined in Some string matching problems from Bioinformatics which still need better solutions this article is old, but problems remain.
There is also presentation Analytic pattern matching: From DNA to Twitter.

Some are related to graph automorphism (so may remain open for a bit longer) for example:

  Extend String Pattern Matching to Graph Pattern Matching, that is, replace the text T by a graph G and find the number of occurrences of a given subgraph/pattern g in G for different models of graph G generation.


How to find max flow in a graph after decrementing an edge capacity? We're given a graph $G=(V, E)$, with source $s$ and sink $t$, $s\neq t$, and that all capacities are non-negative integers. Also the max flow itself is given, so we receive the value of max flow for each edge.  We're also given some edge $e'$.

How can the max flow be found if we decrement the capacity value of an edge $e'$ by $1$ in linear time?

If the capacity of edge $c(e') \ge f(e') + 1$ i.e. the max flow remains the same, there is no chance max flow increase, as it would increased without decreasing $c(e')$.

Suppose that $c(e') = f(e')$ (this edge is saturated) and we decrease the capacity in $1$ unit. You need to remove one unit of flow from $s$ to $t$ that goes through edge $e'$. Let say that $e'= (u,v)$.

Removing flow: Just run two BFS, one starting from $s$ to $u$ going through edges that has flow greater that $0$, the other from $v$ to $t$ equally from edges that has flow greater than $0$. (It is guaranteed you will reach your goal in both cases since there is a unit of flow traversing this edge). Select a path from $s$ to $u$ and remove $1$ unit of flow from each edge and do the same with a path from $v$ to $t$. Complexity: $O(|V| + |E|)$

Recover max flow: Now we have a valid flow network but not necessarily the network with max flow. So now you just need to run one iteration of augmenting path with the capacity of edge $e'$ reduced. (Just like running one iteration of Ford-Fulkerson algorithm) Running just one iteration has the complexity of a single DFS which is $O(|V| + |E|)$.

Overall complexity of this approach would be $O(|V| + |E|)$ which is linear in the amount of nodes and edges.


Find minimal spanning tree of graph with edge values from 1 to 5 integers How can I find the minimal spanning tree of graph with edge values from 1 to 5 integers (no need to be unique) most effectively? I know I can use Kruskal algorithm, but how can I modify the algorithm to find it faster when I know there are edges with values only 1, 2, 3, 4 or 5? I cant figure it out how it could be faster when I know this limitation on edges.

Take a look at the complexity of Kruskal's algorithm. Since the edges are with integer weights, you can sort them in linear time. The entire algorithm will take a total of $O(|V|\alpha(|E|)+|E|)$. We need $O(|E|)$ to sort, and an additional $O(|V|\alpha(|E|))$ for Kruskal's algorithm.


What does $\cdot$ mean as a notation with complexity classes? In the wikipedia page for Toda's Theorem, the notation $A\cdot B$ is used where $A$ and $B$ are two complexity classes, but without explanation as to its meaning.

SO given two classes $A$ and $B$ what does $\cdot$ mean in $A\cdot B$?

Using an example for the cited page, what would $BP \cdot \oplus P$ mean?

Is it correct to say $A\cdot A=A$, and when is it true that $A\cdot B=B$ or $A$?

Reading Toda's original paper, it's not clear that a general application of $\cdot$ has meaning, however it may have been extended later.

Toda introduces three operators: $\oplus\cdot$, $\mathsf{BP}\cdot$ and $\mathsf{C}\cdot$, so the $\cdot$ is, in this context, not an independent piece of notation. Toda is extending the $\mathsf{BP}\cdot$ operator introduced by Schöning (but with uglier notation - $BP\mathscr{C}$ for the operator applied to class $\mathscr{C}$).

The three operators give (intuitively) the closures of classes under three different types of reductions. I'll reproduce the definition (and intuitive explanation) for $\mathsf{BP}\cdot$ for Toda's paper (p. 867):

  $L \in \mathsf{BP}\cdot\mathbf{K}$ if there exist a set $A \in \mathbf{K}$, a polynomial $p$, and a constant $\alpha > 0$ such that, for all $x\in \Sigma^{\ast}$,
  $$
\text{Prob}(\{w\in\{0,1\}^{p(|x|)}:x\#w\in A \leftrightarrow x \in L\}) \geqq \frac{1}{2}\alpha
$$

The intuitive definition is (p. 865):

  Intuitively speaking, a set is in $\mathrm{BP}\cdot\oplus \mathbf{P}$ if and only if it is reducible to a set in $\oplus\mathbf{P}$ under a polynomial-time randomized reduction with two-sided bounded error probability.


Not all Red-Black trees are balanced? Intuitively, "balanced trees" should be trees where left and right sub-trees at each node must have "approximately the same" number of nodes.
Of course, when we talk about red-black trees*(see definition at the end) being balanced, we actually mean that they are height balanced and in that sense, they are balanced.
Suppose we try to formalize the above intuition as follows:

Definition: A Binary Tree is called $\mu$-balanced, with $0 \le \mu \leq \frac{1}{2}$, if for every node $N$, the inequality
$$ \mu \le \frac{|N_L| + 1}{|N| + 1} \le 1 - \mu$$
holds and for every $\mu' \gt \mu$, there is some node for which the above statement fails. $|N_L|$ is the number of nodes in the left sub-tree of $N$ and $|N|$ is the number of nodes under the tree with $N$ as root (including the root).

I believe, these are called weight-balanced trees in some of the literature on this topic.
One can show that if a binary tree with $n$ nodes is $\mu$-balanced (for a constant $\mu \gt 0$), then the height of the tree is $\mathcal{O}(\log n)$, thus maintaining the nice search properties.
So the question is:

Is there some $\mu \gt 0$ such that every big enough red-black tree is $\mu$-balanced?

The definition of Red-Black trees we use (from Introduction to Algorithms by Cormen et al):
A binary search tree, where each node is coloured either red or black and

The root is black
All NULL nodes are black
If a node is red, then both its children are black.
For each node, all paths from that node to descendant NULL nodes have the same number of black nodes.

Note: we don't count the NULL nodes in the definition of $\mu$-balanced above. (Though I believe it does not matter if we do).

Claim: Red-black trees can be arbitrarily un-$\mu$-balanced.

Proof Idea: Fill the right subtree with as many nodes as possible and the left with as few nodes as possible for a given number $k$ of black nodes on every root-leaf path.

Proof: Define a sequence $T_k$ of red-black trees so that $T_k$ has $k$ black nodes on every path from the root to any (virtual) leaf. Define $T_k = B(L_k, R_k)$ with

$R_k$ the complete tree of height $2k - 1$ with the first, third, ... level colored red, the others black, and
$L_k$ the complete tree of height $k-1$ with all nodes colored black.

Clearly, all $T_k$ are red-black trees.

For example, these are $T_1$, $T_2$ and $T_3$, respectively:

[source]

[source]

[source]

Now let us verify the visual impression of the right side being huge compared to the left. I will not count virtual leaves; they do not impact the result.

The left subtree of $T_k$ is complete and always has height $k-1$ and therefore contains $2^k - 1$ nodes. The right subtree, on the other hand, is complete and has height $2k - 1$ and thusly contains $2^{2k}-1$ nodes. Now the $\mu$-balance value for the root is

$\qquad \displaystyle \frac{2^k}{2^k + 2^{2k}} = \frac{1}{1 + 2^k} \underset{k\to\infty}{\to} 0$

which proves that there is no $\mu > 0$ as requested.


Searching for an algorithm with $\Theta(n2^n)$ time complexity I am searching for an algorithm with a time complexity of $\Theta(n2^n)$ time complexity.
I am aware, that e.g. the Fibonacci sequence has a time complexity of $\Theta(2^n)$.
My plan was to add a loop in the implementation, so that before you go into recursion, you are going
to count from 1 to $n$. My question is, whether my plan is successful or if I made any mistakes.

If you just want any algorithm with running time $\Theta(n 2^n)$ you can trivially compute $\ell = n 2^n$ from the input size $n$ and then have a loop of no-ops (or any constant number of "useless" elementary operations) iterate $\ell$ times.
If you are looking for a "reasonable" algorithm for a "well-known" problem with that time complexity, you can look for example at the brute-force solution for the subset-sum problem.
Given an input collection of $n$ non-negative integers $X=\{x_1, x_2, \dots, x_n\}$ and $T \in \mathbb{N}$ the problem asks to decide whether there exists a subset $S$ of $X$ for which $\sum_{x_i \in S} x_i = T$.
A trivial brute-force algorithm for this problem looks at $2^n$ possible binary vectors $v_1, v_2, \dots \in \{0,1\}^n$ of length $n$, where each vector $v_i$ represents a subset of $X$. For each $v_i$ we explicitly check, in $\Theta(n)$ time, whether $(x_1, \dots, x_n) \cdot v_i = T$.
After all vectors have been examined, return "yes" if one such vector was found and "no" otherwise.


How do I choose an optimal cell size when searching for close pairs of points, and using cells to implement this? Suppose that I have a set of $N$ points in $k$-dimensional space ($k>1$), such as in this question, and that I need to find all pairs with a distance¹ smaller than a certain threshold $t$.  The brute-force method would require $N(N-1)$ distance calculations, which is not acceptable.  I attack the problem by first sorting the cells in a grid¹, such as in this answer, followed by brute-force within each grid cell and a number of neighbours (which is easily calculated from the cell size $w*h$ and the maximum distance $t$).

My solution seems to work acceptably well for my purposes, and the results appear to be correct.  However I'm neither a computer scientist nor a mathematician, and I'm not sure what tools I could use to calculate the optimal cell size.  In fact, I developed the aforementioned possibly naive algorithm because it seemed like a reasonably okay method.  I guess the optimal cell size depends in some way on $N$, $t$, on the cost of the distance function, and on the implementation of the sorting in cells, on the distribution of points, and on other things.  How would I make a guess of the optimal values of $w$ and $h$, with or without a priori knowledge on the approximate number of pairs I expect to find?

Does the answer change if the N points are divided in two sets $S_1$ and $S_2$, and each pair shall consist of one element from each set?

¹Not necessarily euclidian.  The points may, for example, be locations on a sphere, i.e. on Earth, with latitude and longitude.

There's an enormous amount of work on data structures and algorithms for this sort of problem.  I suggest you start by reading the general literature on this problem.

Start by reading about algorithms for nearest neighbor search, including all nearest neighbors and the fixed-radius nearest neighbors problem.  Those techniques are applicable to your problem.

Then, read about quadtrees, octrees, k-d trees, VP trees, and the general category of BSP trees.


Good resources for Graph labelling I'm searching for good resources on different graph labelling, especially Graceful, Antimagic and Antibandwidth Labelling. Could anyone please help me with that? It will be very much appreciated. Thanks in advance.

You will hardly find anything more comprehensive than the 400-page dynamic survey of Gallian [1] discussing almost 2300 references.

[1] Gallian, Joseph A. "A dynamic survey of graph labeling." The Electronic Journal of Combinatorics 16, no. 6 (2016): 1-219.


Can this system of polynomial equations be solved in polynomial time? I have these $n$ equations, with $n$ variables. Variables are first $n$ positive integers, constants can be any rational number including zero. Given that there is always a solution, how do we  find a solution to the system:

\begin{align}
ax^{1}+by^{1}+cz^{1}+\cdots&=k_{1}\\
ax^{2}+by^{2}+cz^{2}+\cdots&=k_{2}\\
ax^{3}+by^{3}+cz^{3}+\cdots&=k_{3}
\end{align}
so on ... till
$$ax^{n}+by^{n}+cz^{n}+\cdots=k_{n}$$

for variables $x,y,z\in \{1,2\ldots, n\}$.

The value of constants $a$,$b$,$c$... remain same in all these equations.

And these constants can also be equal to each other. For e.g: $a = b$ so that values of $x$ and $y$ can become interchangeable. In such cases one working solution is suffice.

Can we find a solution or determine none exist in polynomial time?

Edit: For the sake of clarity here is a simple example.

If $n=3$, I know $x,y,z$ can only take 1, 2 or 3 as their values. So if I have $x + y + z = 9$, I clearly know that $x, y$ and $z$ are all 3. But if I have $x + y + z = 6$, I don't know whether they are $2,2,2$ or $1,2,3$. Then I can make use of $x^2 + y^2 + z^2 = 14$. Then I will know they are $1,2,3$.

Let us denote the unknowns by $x_1,\ldots,x_n$, and the coefficients by $c_1,\ldots,c_n$. For a polynomial $P(x)$, we denote
$$
[P(x)] = \sum_{i=1}^n c_i P(x_i).
$$
We are given the values of $[1],[x],\ldots,[x^n]$, from which we can calculate $[P(x)]$ for every polynomial of degree at most $n$. In particular, we can compute, for each $j \in \{1,\ldots,n\}$, the value
$$
\left[ \prod_{k \neq j} \frac{x-k}{j-k} \right] = \sum_{i\colon x_i=j} c_i.
$$
To complete the solution, we need to solve several SUBSET-SUM instances, which possibly interact.

Conversely, we can encode SUBSET-SUM using your equations. Given a set of positive coefficients $c_1,\ldots,c_n$ summing to $C$ and a target $S$, we encode a solution using $\{1,2\}$-valued variables (where $1$ represents a value in the subset summing to $S$), and can compute $[x^k] = S + (C-S)2^k$. These numbers satisfy
$$
[x^k(x-1)(x-2)] = [x^{k+2}-3x^{k+1}+2x^k] = \\
(S + (C-S)2^{k+2}) - 3(S+(C-S)2^{k+1}) + 2(S+(C-S)2^k) = \\
(1-3+2)S + (4-6+2)(C-S)2^k = 0.
$$
Therefore the argument above shows that every $\{1,\ldots,n\}$-valued solution is actually $\{1,2\}$-valued. Therefore a solution to your problem exists if and only if the SUBSET-SUM instance is a Yes instance.

When all coefficients $c_i$ are equal, the argument above allows us to calculate directly the number of $x_i$'s equal to $j$. Let us take your example: $[1] = 3$, $[x] = 6$ and $[x^2] = 14$. Denoting by $y_j$ the number of $x_i$'s equal to $j$, we compute
$$
\begin{align*}
y_1 &= \left[ \frac{(x-2)(x-3)}{(1-2)(1-3)} \right] = \frac{[x^2-5x+6]}{2} = \frac{14-5\cdot6+6\cdot3}{2} = 1, \\
y_2 &= \left[ \frac{(x-1)(x-3)}{(2-1)(2-3)} \right] = [-x^2+4x-3] =
-14+4\cdot6-3\cdot3 = 1, \\
y_3 &= \left[ \frac{(x-1)(x-2)}{(3-1)(3-2)} \right] = \frac{[x^2-3x+2]}{2} =
\frac{14-3\cdot6+2\cdot3}{2} = 1.
\end{align*}
$$


Arbitrary depth nested for-loops without recursion Suppose I have an array of n values I want to apply nested for-loops over to an arbitrary depth m.

const array = [1, 2, 3];

// 2-depth for-loop
for (const i of array) {
  for (const j of array) {
    // do the thing
  }
}

// 3-depth for-loop
for (const i of array) {
  for (const j of array) {
    for (const k of array) {
      // do the thing
    }
  }
}

The obvious solution is to use recursion.  In JavaScript/TypeScript, a generator lends itself well here.  For an example problem, let's calculate the probability distribution of the sum of rolling m 6-sided dice.

type Reducer<T, TResult> = (current: T, accumulator?: TResult) => TResult;

function* nestForLoopRecursive<T, TResult>(
  array: T[],
  depth: number,
  reduce: Reducer<T, TResult>
): Generator<TResult> {
  for (const value of array) {
    if (depth === 1) {
      yield reduce(value);
    } else {
      for (const next of nestForLoopRecursive(array, depth - 1, reduce)) {
        yield reduce(value, next);
      }
    }
  }
}

function reduceSum(current: number, prev = 0): number {
  return current + prev;
}

const pips = [1, 2, 3, 4, 5, 6];

interface RollDistribution {
  [key: number]: number;
}

function rollMDice(m: number): RollDistribution {
  const results: RollDistribution = {};

  for (const result of nestForLoopRecursive(pips, m, reduceSum)) {
    results[result] = results[result] !== undefined ? results[result] + 1 : 1;
  }

  return results;
}

for (let m = 1; m <= 3; m++) {
  console.log(`Rolling ${m} ${m === 1 ? 'die' : 'dice'}`);
  console.log(rollMDice(m));
  console.log();
}

Output

Rolling 1 die
{ '1': 1, '2': 1, '3': 1, '4': 1, '5': 1, '6': 1 }

Rolling 2 dice
{
  '2': 1,
  '3': 2,
  '4': 3,
  '5': 4,
  '6': 5,
  '7': 6,
  '8': 5,
  '9': 4,
  '10': 3,
  '11': 2,
  '12': 1
}

Rolling 3 dice
{
  '3': 1,
  '4': 3,
  '5': 6,
  '6': 10,
  '7': 15,
  '8': 21,
  '9': 25,
  '10': 27,
  '11': 27,
  '12': 25,
  '13': 21,
  '14': 15,
  '15': 10,
  '16': 6,
  '17': 3,
  '18': 1
}

My understanding is that any recursive function can be rewritten iteratively, though it usually requires some augmentation.  (For example, an in-order traversal of a binary tree can be done iteratively if you augment each node with two bits and a parent pointer.)

How can I rewrite nestForLoopRecursive() without using a stack or any other recursive data structure?  In particular, is it possible to do this in at most O(n lg(m)) space?

Here's a CodeSandbox with everything needed written in TypeScript.  The code yet to be written starts at line 16.  Feel free to answer using whatever language you choose, though, including pseudocode.

It is impossible to do this in $O(n \log m)$ space, by a counting argument. Fix $n = 2$ and consider the number of iterations for which the program must execute. There are $m$ nested loops, each with $2$ indices, so the inner statement executes exactly $2^m$ times and then the iteration terminates. But the configuration space of the program only has $2^{O(\log m)} = \operatorname{poly}(m)$ possible states. So as $m \rightarrow \infty$, by the pigeonhole principle some state must be visited twice during the iteration, which is impossible because it would result in an infinite loop.

On the other hand, you can easily do this in $O(\log(n^m)) = O(m \log n)$ space. (Note that this is reversed from what you wrote!) All you have to do is count in base $n$. That is, keep an array of integers of size $\log n$ and treat them as the base $n$ digits of a single number that you are incrementing. Or you can use an arbitrary precision integer data type and use division and modulo operators to extract the base $n$ digits. Either way, this is trivially equivalent to using a stack, but maybe it feels less "recursive" to you.


Is there a computer which can simulate all computers? I have looked for proof that a machine cannot compute itself in more than realtime (Which would allow infinite computing speed) and I came to the conclusion that it is impossible for any computer to simulate all other computers. However, I lack proof of this intuition.

So the idea is that the state of every (modern, non-quantum) computer can be represented as a finite bitstring (just every state of registers, memory cells, and hard-drive...). However, in order to predict what this computer would do given any state, you would need a longer or at least equally long (in some trivial cases this might work) bitstring. But since there is always a bigger computer (with a longer bitstring - representation) there is no computer which can compute all computers.

However, I am wondering about the following:

Let $f$ be a function which maps a computable function $g$ and a valid input $i_g$ of that function $g$, to the result of $g$ given $i_g$:

$$f(g,i_g) = g(i_g)$$

Can you proof that:

$$\exists i_f: f(f, i_f)  \mbox{ does not halt, while } f(i_f) \mbox{ does.}$$

Note that $i_f$ is just a bitstring, and $g$ can be represented by a program and therefore can be a bitstring too...

Your intuition sounds wrong to me.  It's not surprising you couldn't prove it, because it isn't true.  Roughly speaking, it is possible to find a computer that can simulate all other computers.

A universal Turing machine can simulate any other Turing machine, and can be used to simulate any other program in any Turing-complete language.  Thus, there is a reasonable sense in which it can simulate all other computers, if we make precise what we mean by "computers" in a particular way (e.g., if we accept the Church-Turing thesis).

If you want to know whether it is possible to simulate another computer and also do it faster, that's a different matter.  You'd have to formalize what you mean by "faster" to make that question well-defined.

Your question at the end of the post is not well-formed; computability is a property of languages, not of a single value (like $f(f,i_f)$).  Also, you defined $f$ to be a function of two arguments, so $f(i_f)$ doesn't type-check.


Points-in-a-plane from HackerRank I've been struggling with this problem for days now, making no progress:

There are N points on an XY plane. In one turn, you can select a set of collinear points on the plane and remove them. Your goal is to remove all the points in the least number of turns. Given the coordinates of the points, calculate two things:

The minimum number of turns (T) needed to remove all the points.
The number of ways to to remove them in T turns. Two ways are considered different if any point is removed in a different turn.

-- https://www.hackerrank.com/challenges/points-in-a-plane
I've tried a greedy exhaustive solution, where I draw a line between each pair of points, then start to eliminate the lines in descending order based on the number of points they cross. Unfortunately, there is at least one case where this approach produces suboptimal results:
For ease of discussion, I will call lines "longer" or "shorter", based on how many points they include. The greedy algorithm is simply to eliminate lines in order of descending length.
Suppose we have a set of N longer lines, and another set of M shorter lines. Our greedy algorithm will eliminate the long lines first. But what if every single point of the long lines is also included in a short line?  In that case,our initial elimination of the N longer line was a waste, since we would have gotten those lines "for free" had we just eliminated the shorter lines. Specifically, our greedy approach will require N + M eliminations, where we could have cleared all points in just M steps.
The simplest example input demonstrating this is:
(0, 1), (1, 2), (2, 4), (3, 3)
(0, 0), (1, 0), (2, 0), (3, 0)
(0,-1), (1,-2), (2,-4), (3,-3)

As you can see, we have a line of length 4 running along the X axis, and 4 shorter vertial lines of length 3 perpendicular to it. Our greedy algorithm will first eliminate the longest line, after which there will be 8 sets of points remaining, with no more than 2 of them collinear. Eliminating those will thus take 4 steps, for a total 5, where we could have eliminated all points in just 4 steps, had we simply eliminated the 4 vertical lines first.
Could someone provide at least a hint at the general body of knowledge required to approach this? I solved many other HackerRank questions, but can't make any headway with this one.

this is the problem of covering points with lines or linear facility location
which is NP-Hard. This is why you couldn't find a greedy solution. There are approximation and exact algorithms for this problem. If you want an exact algorithm that is efficient on large inputs I suggest you a simple version of parametrized solution for this problem.


Packing objects into bins to minimize the number of bins There is a list of objects. Each object cannot be in a bin with some other objects. How can I find the minimum number of bins required to hold all the objects (and the objects in them)?

My current algorithm:

For each object in the list, see if any of the currently existing bins will hold it. If yes, stick it in the first bin we come to that will hold it. If we exhaust the list of bins without finding a bin, create a new bin and stick the object into it.

Will this algorithm find the minimum number of bins? If not, what algorithm will (NP-hard algorithms OK: I have only about 12 objects)?

Feel free to add any tags you think appropriate - I'm not sure which one is

This is the clique cover problem in disguise, and finding an optimal solution  NP-hard.


Reduce Dominating Set to Minesweeper So, I have two problems:

Minesweeper: given an undirected graph where some vertices have a whole number associated with them, check if there is a way to mark some of the non-numbered vertices such that the number in each numbered vertex is equal to the amount of its marked neighbours.
Dominating set: given an undirected graph and an integer $k$, check if there is a way to mark exactly $k$ vertices such that each non-marked vertex has at least one marked neighbour.

I need to construct a polynomial reduction from the second problem to the first (that is, using the solution to the first problem, construct a polynomial solution to the second).

I do understand that I will need to add some additional numbered vertices to the graph (because numbering any of the existing vertices will prevent it from being marked). I've tried to add a support vertex for all of the original ones and connect each support vertex to the same vertices, and after that brute-force my way through numbers in each support vertex. The problem is --- that's $O(n^n)$ and definitely not a polynomial.

How can I do this in polynomial time?

Given an instance $(G, k)$ of DOMINATING SET, we construct our instance of MINESWEEPER as follows.

Add a new vertex $s$, connect $s$ with all the vertices of $V(G)$. Label $s$ with $k$.
For each $v\in V(G)$, add a new vertex $s_v$. Connect $s_v$ to all the vertices of $N(v)\cup\{v\}$ (the neighborhood of $v$ and $v$ itself). Connect $s_v$ to $|N(v)| - 1$ new dummy vertices. Label $s_v$ with $|N(v)|$.

Call the constructed graph $G'$. The produced MINESWEEPER instance is $G'$ itself.

We claim that $(G, k)$ is a YES instance of DOMINATING SET iff. $G'$ is a YES instance of MINESWEEPER.

Proof:
If $(G, k)$ is a YES instance of DOMINATING SET, we have a dominating set $S\subseteq V(G)$ with $|S| = k$. By simply marking all the vertices of $S$, we satisfy the label of $s$ in $G'$. Then, for each $s_v\in V(G')$, according to the number of marked vertices (up to now) in $N(v)\cup\{v\}$, we mark some of the dummy vertices connected with $s_v$. Note that, since $S$ is dominating, $N(v)\cup\{v\}\cap S\neq\emptyset$, so at most $|N(v)|-1$ dummy vertices needs to be marked to satisfy the label of $s_v$, so we always have enough number of dummy vertices connected to $s_v$.

Conversely, if $G'$ is a YES instance of MINESWEEPER, we denote by $S$ the non-dummy vertices (which also means that these are in $V(G)$) in the solution to this instance. We now show that $S$ is a dominating set of $G$ and $|S|=k$, which concludes our proof. Indeed, to satisfy the label of $s$, we have that $|S|=k$. For each vertex $s_v$, at most $|N(v)|-1$ dummy vertices connected to it are marked. So in order to satisfy its label, namely $|N(v)|$, either $v$ or some vertex in $N(v)$ is marked. So, in particular, if $v$ is not marked, i.e. $v\not\in S$, there must be some marked vertex in $N(v)$, i.e. $N(v)\cap S\neq\emptyset$. This suffices to prove that $S$ is a dominating set of $G$.$\square$


Advantage of Stack-Based Allocation for Local Variables While learning stack allocation, I came across this paragraph in the textbook (Programming Language Pragmatics - 3rd Edition):

  Even in a language without recursion, it can be advantageous to use a stack for
  local variables, rather than allocating them statically. In most programs the pattern of potential calls among subroutines does not permit all of those subroutines to be active at the same time. As a result, the total space needed for local variables of currently active subroutines is seldom as large as the total space across all subroutines, active or not. A stack may therefore require substantially less memory at run time than would be required for static allocation.

I would appreciate if anyone could explain how stack allocation would save memory when used for allocating local variables. I tried reading this many times. But I can't understand the author meant.

Consider the following program:

f1();
f2();

If local variables are allocated statically, there's a space in memory that's reserved for the local variables of f1, and a separate space for the local variables of f2. If f1 needs $n_1$ bytes of memory for its local variables and f2 needs $n_2$ bytes, the program above needs $n_1 + n_2$ bytes.

If local variables are allocated on a stack, the same stack space is first used for the local variables of f1, then reused for the local variables of f2. The program only needs $\max(f_1, f_2)$ bytes of memory.

With more functions in a program, the amount of static memory grows linerarly with the number of functions and the size of their local variables. The amount of stack memory only grows as fast as the depth of the call chain.

In addition, static allocation does not permit recursion or concurrency: if f1 is already active, you can't invoke it again since the second invocation would overwrite the local variables used by the first invocation. Stack allocation does.

Stack allocation has been standard practice since the very early days of computers.


How to check if two strings are permutations of each other using O(1) additional space? Given two strings how can you check if they are a permutation of each other using O(1) space? Modifying the strings is not allowed in any way.
Note: O(1) space in relation to both the string length AND the size of the alphabet.

Denote the arrays by $A,B$, and suppose they are of length $n$.

Suppose first that the values in each array are distinct. Here is an algorithm that uses $O(1)$ space:

Compute the minimum values of both arrays, and check that they are identical.
Compute the second minimum values of both arrays, and check that they are identical.
And so on.

Computing the minimum value of an array clearly uses $O(1)$ space. Given the $k$th smallest element, we can find the $(k+1)$st smallest element by finding the minimal value larger than the $k$th smallest element (here we use the fact that all elements are distinct).

When elements are allowed to repeat, we modify the algorithm as follows:

Compute the minimum values $m_{A,1},m_{B,1}$ of both arrays, count how many times each appear, and verify the $m_{A,1} = m_{B,1}$ and that the counts are identical.
Compute the minimum values $m_{A,2},m_{B,2}$ larger than $m_{A,1},m_{B,1}$ in the two arrays (respectively), and count how many times each appear. Verify that $m_{A,2} = m_{B,2}$, and that the counts are identical.
And so on.


Is there a unit of measurement that can express code execution speed in absolute terms? I've always seen code execution speed measured either in units of time (e.g. t milliseconds), or using asymptotic analysis (e.g. O(n log n)). Execution speed will vary depending on hardware performance, and asymptotic analysis can tell us how code will perform relative to the size of the input, but they're not absolute terms.

For space performance, we have asymptotic analysis, but we can also measure performance in bytes, which allows us to express (and predict) space performance in both relative and absolute terms. e.g. algorithm X's space complexity is O(n) or n * 32 bytes of memory for implementation Y in language Z.

For example we can look at this code:

for i in n:
    pass

And if we know this will be executed using a 64-bit build of CPython, we can say this for loop will take up 72 + n * 8 bytes for the integer array and 8 bytes for each reference (independent of context/overhead).

My question is: Is there a unit of measurement we can use to express a piece of code's execution speed (or CPU usage) in absolute terms, similar to how we can with bytes for memory?

I think the comparison is a bit clouded actually. Some unspoken concerns are that you can't claim python will compile to precisely 72+8n bytes by reading the high-level code.  There's a virtual machine with untold optimization and overhead heavily dependent on memory layouts, CPUs, your OS, even your version of Python. Memory blocks might be allocated in fixed increments: 1KB page even if all you need is 100 bytes.  Then within your fancy hyperthreaded CPU it might decide to pack bytes together, or rip them apart to run someone else's code along side yours.  So how many physical bytes you use in the program can be far more than you expect you need.  I think those issues seem to hit at the same ambiguity you considered with time.

In the literature on complexity these concerns are usually given with footnotes.  That is we accept that asymptotics are necessary for modeling time and space because we cannot quantify the really fine details, and if we could, the results would be unusable.

So I think the answer to your question is no, there is no such unit, but that there isn't one for space either.  It is important to remember that the role of modeling an algorithm is to know its behavior in broad strokes.  If you model it so precisely that you can predict it to the fine detail chances are your model is as complex to evaluate as the thing it is modeling.  We need models that simplify so we can get at identifying the big bottlenecks and not get stuck in the weeds.  (Probably that is a theorem whose proof is basically the same as the proof that there exist Kolmogorov random sequences -- but I only speculate on that point.)

As a side remark, there are time-space complexities which measure the two together and these can come closer to modeling resource use in real life.  These can be quantified with units of "power" (Watts) or in economic models as "cost" ($$ spent to run).


Computational complexity of counting symbols Consider the counting function $\{x\}^* \rightarrow \mathbb N$ that counts the number of occurrences of the symbol $x$.

I am confused about the (asymptotic) complexity of computing this function, where the output should be represented in a non-unary system (e.g., binary). My intuition strongly suggests that this should be linear, i.e., $O(n)$ where $n$ is the number of occurrences of the symbol $x$ in the input.

As far as my understanding goes there are multiple interpretations of computation - e.g.,

single-band Turing machines, for which my best idea has run time $\Omega(n^2 \log n)$ I think (the $\log n$ comes from the assumption that the binary successor function has $\Omega(n)$ run time, where $n$ is the length of a binary representation of a natural number, and the $n^2$ comes from the assumption that the Turing machine has to travel over all the $x$'s to reach its current count),
multi-band Turing machines, for which I think I have an idea of run time $\Omega(n \log n)$,
random-access machines, which I don't know at all.

So my question is the following.

What is the computational complexity of the counting function in the various models of computation? Is it linear in any of them?

If at all relevant, I ask from the point of view of abstract algebra, where I am trying to assess the computational complexity of the word problem in some specific group.

Turing machines are a nice model with several advantages, mostly their simplicity, but they are not the first choice when analyzing algorithms. Algorithms are typically implicitly analyzed on the RAM machine model, and in some cases, on the BSS model.

Here are some comments on the computational complexity of counting in various models:

Single-tape Turing machine: These are only considered since it is relatively easy to prove lower bounds on them. They are even less realistic a computation model than multi-tape Turing machines.

Multi-tape Turing machine: It is a standard example in amortized complexity that an increasing counter can be implemented using $O(1)$ amortized bit operations. This is because half the time, only one bit changes, one quarter of the time, only two bits, and so on, for a total number of changed bits which is $1/2 + 2/4 + 3/8 + \cdots = 2$. The Turing machine complexity is linear in that, and so counting can be implemented in $O(n)$.

RAM machine: A RAM machine consists of finitely many registers and a random-access memory. The registers are $O(\log n)$-bits long, where $n$ is the size of the input. Reasonable operations on registers take constant time. In particular, increasing a counter that can count up to $\mathit{poly}(n)$ takes $O(1)$ worst-case time. In particular, your function will run in $O(n)$.

BSS machine: One has to be careful when performing arithmetic on large numbers. On the RAM machine, arithmetic takes constant time only if the magnitude of the operands is $\mathit{poly}(n)$. A BSS machine allows access to special registers which store values in some field, say the real numbers. You can perform constant-time arithmetic and comparisons, but not functions like floor. You are also not allowed to use such values for indexing. (If you don't limit yourself enough, you will soon be solving SAT in polynomial time.) You can think of a BSS machine as accommodating floating-point operations, which in practice take constant time, while ignoring the finite precision involved in them.


More details on a language decided in $\Theta(\log \log n)$ space In Language with $\log \log n$ space complexity?, the following non-regular language is described:

$$L = \{b(0) \# b(1) \# \dots \# b(2^k-1) \mid k\in \mathbb{N}\}$$

where $b(i)$ is the $k$-bit binary representation of $i$. This can evidently be computed in $\log \log n$ space, where $n$ is the length of the string, using the typical TM with input-output tapes.

This is apparently a common example used in complexity theory, however I would like some clarification on the method of calculation -- the answer given is very unclear and differs from the method defined in the reported source.

In the answer given, it says we do the check only when $m$ is smaller than the width of the first block. Am I misunderstanding this? If we do this, we never check the MSB of each representation, so for example the string $10\# 11 \# 10 \# 11$ would be accepted since it never checks $m=2$.
Do we check if the $m$ least significant bits form a counter modulo $m$, or modulo $2^m$? The lecture cited checks the ending modulo $2^m$, but the answer says modulo $m$. Wouldn't having a counter that goes up to $2^m$ take $m$ space which is already too much space ($m = O(\log n)$)? If we're supposed to make the counter modulo $m$, how do we take binary numbers modulo $m$ while still satisfying the space requirement? If $m$ is a power of two we can just do addition with overflow, but what about when it's not?I don't see an obvious, space-efficient algorithm for doing this in general.
Furthermore, even if we can do this in the given space, I don't see why the method taking modulo $m$ decides the language. For example, I can give you $00 \# 11 \# 10 \# 11$ and the LSBs form a counter "modulo $1$" and the two LSBs form a counter modulo $2$.

If anyone can clear up my questions that would be greatly appreciated. I think it's likely that there's just one thing I'm fundamentally misunderstanding about the presentation here which is causing everything else to not make any sense.

The trick here is to forget about the details as stated in the answer, and think about what would make the claim correct.

If $k$ were known, you could verify that the input is indeed $b(0)\#\cdots\#b(2^k-1)$ as follows: (below, a word is stuff between adjacent sharp signs)

The first word is $0^k$.
For any two contiguous words $x,y$, it holds that $y=x+1$.
The last word is $1^k$.

This can be accomplished in space $O(k)$.

Unfortunately, we don't know $k$ in advance, and even if we did, it's not necessarily the case that $k = O(\log \log n)$ – there could be much less than $2^k-1$ words. Therefore we use a slightly different approach. Let $K$ be the length of the first word. For each $t \leq K$, we verify the following:

The first word ends with $0^t$.
For any two contiguous words $x,y$, the $t$-bit suffixes $x',y'$ satisfy $y'=x'+1$ modulo $2^t$.
The last word ends with $1^t$.

If these tests pass for all $t \leq K$, then we accept the word. The $t$th test can only pass if the input is at least $(t+1)2^t-1$ symbols long and uses only $O(\log t)$ space, and this implies that the algorithm uses $O(\log\log n)$ space.


How can I show this language is Regular? (Foundations of computing) Σ(alphabet) contains 3x1 column matrices
[[0],[0],[0]], [[0],[0],[1]] , [[0],[1],[0]]... [[1],[1],[1]] such that each
element in the language is a THREE SET
of the columns where the bottom row is the sum of the two top rows

example
[[0],[0],[1]], [[1],[0],[0]] , [[1],[1],[0]] is an element of the Language

BUT

[[0],[0],[1]], [[1],[0],[1]] , [[0],[0],[0]] is not an element of the language.

Your question was already asked before, but got no answer: How to prove for string of triplets that it is a Regular Language?. I merely summarize the comments given there.

You need to implement binary addition. That is easier when you consider first the language in reverse, the lower bits first.

Standard letters are (in a more intuitive notation) [00|0], [01|1], [10|1], [11|0]. In the last case however, we realize that we should take a carry to the next position. This can be solved by adding a special state for that case, and adapting the letters accordingly.


Hidden Markov Models for Hand Gestures I am completing a final year project for hand gesture recognition using Hidden Markov Models
I have a fair understanding of Hidden Markov Models and how they work using simple examples such as the Unfair Casino and some Weather examples.
I am looking to implement multiple Hidden markov models where each model corresponds to a single gesture, similarly to this paper where the observed states are the angles between the coordinates of different points. This would create a sequence of numbers from 0 to 18 as seen in Figure 3 and Figure 4. .
What would the hidden states be in terms of this scenario?
The weather example has the observations 'Walk', 'Shop' and 'Clean' which would be the numbers 0-18 in the hand gesture case, however I do not know what the states 'Rainy' and 'Sunny' would correspond to in the hand gesture scenario.
Edit:
I am generating a sequence of numbers that will correspond to a certain gesture using the method mentioned above. I will then use that sequence to train a HMM and will then test that HMM using another set of recorded numbers similar to the training set. Here is an example of my scenario:
Recorded data of observed states (theta) during a gesture:
observations = [0,1,4,15,4,3,1,0,19,18,17,16,15,15,16,3,1,1,0,18...]

Recorded data of test gesture:
test = [0,2,4,15,4,2,1,0]

My goal is to create  a model from the first set of observations (which will be much longer as the gesture will be recorded many times) and determine the likelyhood of the test gesture to be from said model.
Will I need to generate a hidden state to create an accurate model of the gesture or can I just use unsupervised training for a model?
If i do have to use supervised training, should I create the hidden states using quadrants (i.e. 0-90 degrees = quadrant1, 90-180 degrees = quadrant2...)?

You say that your goal is to create a model and compute the likelihood of a test sample using that model.  For that purposes, you do not need to find a way to interpret the hidden states, and you do not need to engineer the model so the hidden states have a meaning that you can understand.  Instead, let the standard Baum-Welch algorithm compute a reasonable model that fits the training data, and don't worry about the meaning of the hidden states.
If you had a physics model where you knew what the hidden states "should" be, based on some domain knowledge (e.g., about the movement patterns of bones and joints), then you could incorporate that into your model in hopes of improving the model... but that's not required.  Since you don't seem to start from such a place, there is no need to try to force the hidden states to take on any particular human-understandable meaning.


If $g ∘ f$ is primitive recursive, are $f$ and $g$, too? Assuming I have functions $f, g : \mathbb{N} \to \mathbb{N}$ and I know that $g \circ f$ is a primitive recursive function. What can I tell about $f$ and $g$? Are they primitive recursive as well? Or at least one of them?

Let $f$ be a bijective function, which is not primitive recursive. We know, that such a function exists. Let further be $g=f^{-1}$ the inverse function of $f$. Therefore $f\circ g$ is the identity function, which is clearly primitive recursive.


Why does the NP completeness of the Hartree-Fock method not lead to difficulty in practical calculation? I read  Computational Complexity of interacting electrons
and fundamental limitations of Density Functional Theory. In appendix, it is claimed that

  In the following, we show that approximating the
  ground state energy using the Hartree-Fock method is
  an NP-complete problem

As far as I know, if a problem being NP-hard, it is unlikely to be solved within polynomial time. If Hartree-Fock is NP-complete, computation for large system is unlikely to be possible. However, experience seems to suggest that Hartree-Fock could always be done within polynomial time. There are vast applications of Hartree-Fock method on various many-electron system: atoms, molecules, and solids. The claim from the arxiv paper is rather in contraction with my experience

My question is, why the Hartree-Fock method is applicable to wide class of many-electron system while it is NP-complete? Is that because its average complexity is low or any other reason?

There is plenty of precedent for problems that are NP-hard (in worst-case complexity) but can often be done in practice on many instances that arise in practice (e.g., because their average-case complexity is low, or for other reasons).

NP-hardness relates to the worst-case complexity of a problem.  However, worst-case hardness isn't always representative of typical-case hardness.  Sometimes typical instances are much easier than the worst-case instances.  Therefore, NP-hardness results aren't always an indication that the problem can't be solved acceptably well in practice.

As Yuval Filmus explained so well in a comment:

  I'm not sure there is any better answer than the fact that the algorithms work on real-world instances. NP-hardness is a worst-case concept, and sometimes the worst case is simply irrelevant. It is a challenging problem to characterize which properties of real-world instances render the problem solvable. Smooth analysis is one answer, and there might be others in the non-rigorous literature.

I recommend you take a look at Dealing with intractability: NP-complete problems for an overview of common methods for dealing with NP-hardness: i.e., for figuring out ways to solve a problem good enough for practical purposes, when we know it is NP-hard.


How does a compiler infer a value's type? From A Swift Tour — The Swift Programming Language (Swift 5):

var myVariable = 42
myVariable = 50
let myConstant = 42

  A constant or variable must have the same type as the value you want to assign to it. However, you don’t always have to write the type explicitly. Providing a value when you create a constant or variable lets the compiler infer its type. In the example above, the compiler infers that myVariable is an integer because its initial value is an integer.

How does this work?

You did not provide an explicit type identifier in the left part of the variable declaration & initialization statement. However, by implicitly specifying an initialization value in the right part to have type int, which the compiler can infer from values of 42/50, these statements triggered the procedure of the compiler to handle S-Attributed Grammar.


Is Euler's totient function a primitive recursive function? We consider the function $g$ which associates the number of prime integers with $n$ in the set $\{0,...,n\}$. I have to prove that $g$ is a primitive recursive function.

First I defined the set $A=\{i∈\{0,...,n\}:\gcd(i,n)=1\}$. To show that $A$ is a primitive recursive set I said that : $\{0,...,n\}$ is primitive recursive because ${k}$ is primitive recursive by characteristic function and $\{0,...,n\}=\bigcup\limits_{k=0}^{n} \{k\}$ is primitive recursive by the property of $⋃$.

Then the function $\gcd$ is primitive recursive. Indeed we can see that with the function $lcm$. We have $lcm(a,b)=μk≤ab (∃j,l≤ab,aj=k∧bl=k)$
which is a primitive recursive expression. Then by operator division $\gcd$ is a primitive recursive function.

So $A$ is a primitive recursive set.

Now, to prove that $g$ is primitive recursive can I take :

$g(i)=\sum\limits_{i=0}^{n} \chi_{A}(i)$ with $χ_A(i)=1$ if $i∈A$.and $g$ is a finite sum of primitive recursive functions so it is primitive recursive?

A computable function is primitive recursive if and only if it can be computed by a program whose running time is upper-bounded by some primitive recursive function. Your function (usually known as Euler's totient function $\varphi$) can be computed in exponential time, and so is primitive recursive.


A factoring conversion There was a comment here that " It is possible in principle to reduce the factorization of a $256$-bit number (which is computable in TFNP) to the Permanent on a matrix of dimension $N\times N$ where $N\leq c\cdot256^c + c$ for some hopefully small constant $c$. However the computation of a nice upper bound on $c$ would probably take substantial effort. It's possible c is no more than 2 or 3."

Is it possible to convert factoring integers to calculating permanent? That is given $\log N$ bit integer to factor, how can one reduce factoring such an integer to calculating permanent of $(\log n)^c\times(\log n)^c$ matrix for a fixed $c$?

I also ask if computing $a(a+1)(a+2)\dots(a+n)$ with $a\in\Bbb N$ is also easy (done in $\log^cn$ steps if permanent of $N\times N$ matrix is easy (done in $N^c$ steps). Note that at $a=1$ we have $n!$, and permanent of all $1$ matrix needs $n\times n$ size and hence needs $n^c$ time even if permanent is easy.

The language of tuples $\langle n,i,j,b \rangle$ such that the $j$th bit of the $i$th prime factor of $n$ is $b$ is in NP. In particular, it is in #P. More accurately, there is a #P algorithm that on input $\langle n,i,j \rangle$ gives the $j$th bit of the $i$th prime factor of $n$ (either $0$ or $1$). Since the permanent is #P-complete, we can reduce this algorithm to the computation of some polysize permanent.


Equivalence between alternative definitions of NP I'm having some problems in understanding the two alternative definitions of NP. They're presented as equivalent, but to me they seem to define different class of problems. Intuitively, we can think of a non-deterministic TM as branching at every step to check all possible alternatives in parallel. Also, we can see it as guessing the right next state at every stage of the computation. In both cases, if there is a computation path which terminates in an accepting state, the TM is said to accept its input, otherwise it rejects it. On an informal level, we can define NP in two ways.

The class of problems solvable in polynomial time by a NTM. That is, given an instance $x$ of the problem, there is a NTM $M$ which accepts $x$.
The class of problems which can be verified in polynomial time by a TM. In this case, together with the input we get a certificate which provides a proof that $x$ is a solution. We can then check if this is the case by some polynomial time procedure.

Now, what baffles me is that taking the first definition, it would seem as if a NTM would always find the accepting computation path and will thus always be able to accept its input (provided this is in the language recognized by the TM). On the other hand, by the second definition, since we're given only one certificate, $x$ could actually be in the language recognized by $M$, but we cannot tell because we've been given the wrong certificate.

On a second thought, the problem here could be that I'm thinking as a NTM as actually performing a computation, while it is just a theoretical construct. That is, even if we allow the TM to accept if at least one computation path accepts, no one guarantees that a concrete run of the algorithm will "follow" this computation path. So, in this sense we could see the equivalence by stating that, in the case of a verifier, the TM accept if there is at least one certificate which proves that the input is in the language recognized by the TM; this parallels the way in which a NTM needs only to have at least one computation path which accepts the input.

Any deeper insight or also formal derivations would be very appreciated.

The definition of $\text{NP}$ in terms of verification can be formally stated as follows:

  A language $L$ is in $\text{NP}$ if there exists a polynomial verifier for $L$ such that for every $x$:
  $$x \in L \iff \exists u: V(x,u) = 1.$$

  Here $u$ serves as a certificate.

To prove that the other definition $\text{NP}$ in terms of NTM implies the one above, you should construct such a polynomial verifier $V$ with the desired property. That is, for every $x \in L$, you need to find a certificate $u$ (you are not given a certificate $u$) such that $V(x,u) = 1$. Note that for every $x \in L$, there is a sequence of nondeterministic choices that makes the NTM $M$ accept $x$. This sequence is the certificate we need. What the polynomial verifier $V$ need to do is just to simulate the action of $M$ using these nondeterministic choices.