Selection of parameters for genetic algorithm How can one select the proper number of parameters for a genetic algorithm to model a given system?

For example, say you want to optimize production of cars, and you have 1,000 measurements of hourly efficiency at various tasks for each of 1,000 different employees.  So, you have 1,000,000 data points.  Most of these are likely to be weakly correlated to the overall efficiency of your factory, but not so weakly that you can say they are irrelevant with statistical confidence.  How do you go about picking inputs for your GA so that you don't have 1,000,000+ degrees of freedom, resulting in very slow convergence or no convergence at all?

Specifically, what are the algorithms one could use to pre-select or selectively eliminate features?

One approach I have used myself in this scenario is to evolve the parameter selection itself, so I might have parents like {a,b,c}, {b,d,e,q,x,y,z}, and so on. I would then mutate the children to add or drop features. This works well for a few dozen features. But the problem is that it is inefficient if there is a large number of degrees of freedom. In that case, you are looking at 10^n combinations (in the example above, 10^1,000,000), which makes some pre-filtering of features critical to get any kind of useful performance.

First of all - the example doesn't seem well suited because you would probably use some regression or classical ML methods to solve this. Secondly - you are referring to a general problem of feature selection (Kira, Rendell, 1992) or attribute selection (Hall, Holmes, 2003) or variable selection (Guyon, Elisseeff, 2003) or variable subset selection (Stecking, Schebesch, 2005) or feature extraction (Hillion, Masson, Roux, 1988) or dimensionality reduction (Roweis, Saul, 200) or state abstraction (Amarel, 1968). This problem is relevant not only to genetic algorithms but for almost all machine learning techniques when dealing with high dimensional data.

Three cases can be distinguished here: the last instance of this problem known as state abstraction is usually related to process modelling (which suits your example, but not the GA context). The first three, i.e. feature selection, attribute selection or variable selection seem to be most relevant when taking your question literally. In this context a common solution is the mRMR approach (Peng, Long, Ding, 2005). From my experience it doesn't always work well with continuous data - however, mutual information can be substituted with other coefficients, like correlation for example. Another possible approach is to use cross-validation (Picard, Cook, 1984) for this. You can have multiple models each using different features, and by means of model selection with cross-validation techniques you choose the best model, which gives you the information on which features work best for the given task.

The feature extraction and dimensionality reduction cases allow to not only select initial features, but also their combinations. A well known example solution for this case is the PCA algorithm (Pearson, 1901), which produces the optimal, in terms of explained variance, set of features being linear combinations of input features.

Also note, that there are many models that handle feature extraction task by themselves. Some examples are: Growing Neural Gas Network (Fritzke, 1995), LASSO (Tibshirani, 2011), RFE SVM (Zeng, Chen, Tao, 2009), Decision Trees (Quinlan, 1986).

References:

Kenji Kira and Larry A. Rendell. 1992. A practical approach to feature selection. In Proceedings of the ninth international workshop on Machine learning (ML92), Derek Sleeman and Peter Edwards (Eds.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 249-256.
Hall, M.A.; Holmes, G., "Benchmarking attribute selection techniques for discrete class data mining," Knowledge and Data Engineering, IEEE Transactions on , vol.15, no.6, pp.1437,1447, Nov.-Dec. 2003
Isabelle Guyon and André Elisseeff. 2003. An introduction to variable and feature selection. J. Mach. Learn. Res. 3 (March 2003), 1157-1182.
Ralf Stecking, Klaus B. Schebesch. 2005. Variable Subset Selection for Credit Scoring with Support Vector Machines, Operations Research Proceedings 2005, Springer Berlin Heidelberg, (2005), pp.251-256
Hillion, A.; Masson, P.; Roux, C., "A nonparametric approach to linear feature extraction; application to classification of binary synthetic textures," Pattern Recognition, 1988., 9th International Conference on , vol., no., pp.1036,1039 vol.2, 14-17 Nov 1988
Nonlinear dimensionality reduction by locally linear embedding.
Sam Roweis & Lawrence Saul.
Science, v.290 no.5500 , Dec.22, 2000. pp.2323--2326.
Amarel, S. (1968). On representations of problems of reasoning about actions, Machine Intelligence, (3), 131--171
Peng, H.; Fulmi Long; Ding, C., "Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancy," Pattern Analysis and Machine Intelligence, IEEE Transactions on , vol.27, no.8, pp.1226,1238, Aug. 2005
Richard R. Picard and R. Dennis Cook, Journal of the American Statistical Association Vol. 79, No. 387 (Sep., 1984), pp. 575-583
On lines and planes of closest fit to systems of points in space Philosophical Magazine, Vol. 2, No. 6. (1901), pp. 559-572 by K. Pearson
A Growing Neural Gas Network Learns Topologies, Bernd Fritzke, Conference: Neural Information Processing Systems - NIPS , pp. 625-632, 1994
Regression shrinkage and selection via the lasso: a retrospective, Robert Tibshirani, Journal of the Royal Statistical Society Series B, 2011, vol. 73, issue 3, pages 273-282
Xiangyan Zeng; Yen-wei Chen; Caixia Tao; Van Alphen, D., "Feature Selection Using Recursive Feature Elimination for Handwritten Digit Recognition," Intelligent Information Hiding and Multimedia Signal Processing, 2009. IIH-MSP '09. Fifth International Conference on , vol., no., pp.1205,1208, 12-14 Sept. 2009
J. R. Quinlan. 1986. Induction of Decision Trees. Mach. Learn. 1, 1 (March 1986), 81-106.


If you can represent/model a Conditional IF statement with AND + NOT or OR + NOT I am still trying to wrap my head around this, which shows how to simulate control-flow without using an if-statement.

I've been looking at basic logic today and learned that you can represent all logic with 1 (like NAND), 2 (AND + NOT, OR + NOT, etc.), or 3 logical primitives.

This makes me wonder if you can represent the if-statement using just AND + NOT or OR + NOT (and what it might look like), such that a program loop would be able to evaluate an expression such as if (a) b(), or something more complex like in the first link above.

This is partly possible.

Assume your code is

if (a==b)
  x = y;
else
  z = w;

where all vars are ints

This can be rewritten as

c = (a==b) -1 // true 1-1=0; false 0-1=0xfffffffff

x = (~c &  y) | (c & x); // or ~(~(~c&y)&~(c&x)) to only use & and ~
z = (c &  w) | (~c & z);

This can be applied to arbitrarily complex expressions, even nested, but you cannot have function calls, which seriously limits application area.

Note that this is routinely used to program SIMD extensions like SSE or AVX. In SIMD, you do several operations simultaneously and the only way to perform if-then-else if by mean of masking and anding/oring.

Similarly, there is the same problem on a GPU where hundred of processing elements work simultaneoulsy. It is hidden from the user, but internally the controller transforms if-then-else to logic ops. It even keeps track of it across function calls.


Is it possible to use machine learning to interpret a programming language and guess it's output I know machine learning can make some predictions. With enough input data and example output data a machine can accept an image as input and determine that the image is likely a "flower" (output).

Could the same method apply to an interpretive programming language? Let's say Python for example. The inputs on every "line" of python would be existing memory and the new "line" of syntax. So if x = 2 (some data in ram as say CPython would set it instead of the actual syntax). Our new line of syntax is x + 2. The output is 4 (perhaps the updated ram state could also be considered an output). With enough sample input and output could a machine learning algorithm effectively "invent" it's own python interpreter? Perhaps our invented interpreter would determine there is a 98% chance that 2 + 2 results in 4.

A few people are asking why would anyone would want to do this. Curiosity mostly and certainly reading too much Godel, Escher, Bach. I think it's interesting because:

Perhaps it would find novel optimizations. Computers already find new strategies in chess. Why not interpreters or compilers?
The idea of a programming language interpreting syntax probabilistically, that doesn't even have to follow strict rules, is interesting. Can we go from 2 + 2 = 4 to 2 plus 2 equal four to Please add two and two.
Making a really horrible python interpreter would be funny.

I doubt it.  That requires learning a pretty complex function, which seems beyond the reach of current machine learning techniques.

But there's probably no reason to use machine learning for this, as we already know how to program an interpreter, and that will be more effective than using machine learning.


How does the union of two machines which accept language of form $0^{mx+b}$ look like I am doing Shai Simonson's course on Theory of computation. I am not able to understand part b of one of its problem sets.

a. Prove that languages of form $0^{mx+b}$, where m and b are positive integer constants and x ranges from 0 to infinite, is regular.

b. Give an example of a regular set over the alphabet {0} which is not of form $0^{mx+b}$.

In the solution set, for part b, it is given that union of machines which accept language of form $0^{mx+b}$ describes a regular set, but is not of form $0^{mx+b}$.
Q1. I want to understand of what form the union is?
Q2.And also, we are talking about union of finite number of machines, right? Because the union of all such machines(which is infinite) will not be regular. Am I correct?
Q3. I would also like to know is there any other example of a regular language which is not of the given form but is regular.
Q4. I also want to clarify what does set of the union of two such machines will look like. Will it be {$0^{2x_1+3}$ $\bigcup$ $0^{7x_2+4}$}   or
{$0^{2x+3}$ $\bigcup$ $0^{7x+4}$} i.e. will the $x's$ be different or same in both the machines. I think the two sets are independent so they should be different but still want to confirm.

It is written union of machines (I suppose here machine means finite automaton), but it is only an union of languages, i.e. the union of the languages accepted by said automata.
Indeed it should be finite otherwise it could be not regular. To prove this fact, for $k\in \mathbb{N}$, consider $L_k = \{0^{n(2k+3)},n\in\mathbb{N}\}$, and $L = \bigcup\limits_{k\in\mathbb{N}}L_k$. Then $L$ is the set of words over the alphabet $\{0\}$ that have a length which is the multiple of an odd number greater than $2$. That means that the complement of $L$ is $\overline{L} = \{0^{2^n}, n\in\mathbb{N}\}$. Since $\overline{L}$ is not even context-free, then $L$ cannot be regular.
$L = \{0^{2n}, n\in \mathbb{N}\}\cup \{0^{3n}, n\in\mathbb{N}\}$ satisfy the condition. To prove it, suppose $L = \{0^{an+b}, n\in\mathbb{N}\}$. Since $\varepsilon \in L$, then it means that $b = 0$. Since $0^2\in L$, it means that $a\mid 2$. Since $0^3\in L$, it means that $a\mid 3$. We conclude that $a\mid\text{gcd}(2, 3) = 1$, so that $a = 1$. Since it is clear that $L \neq \{0^n, n\in\mathbb{N}\}$ (because $0^5\notin L$ for example), $L$ is regular and not of the said form.
There seems to be a bit of misunderstanding about the variable $x$ here… And to be precise and avoid any mistake, you should write $\{0^{2x+3}, x\in\mathbb{N}\}$ instead of just $0^{2x+3}$. That way you will understand that $x$ is just a free variable and it does not matter how you write it.


Designing a rationing algorithm for a store Suppose I have a store and I have n units of item x. I want to sell all n units at the end of the day. I do not know how many customers will be coming in today. One customer could theoretically come in and buy all remaining units. This would not be desirable, as the next customer would not be able to buy this item, and would end up frustrated that we do not keep enough in stock.

In general, how does one design a rationing algorithm that balances the need to sell as much quantity as possible with serving the most amount of (unknown number of) customers? Is this even possible?

This sounds like a maximization problem. The algoritm should try to maximize something, let us call it utility.  What You need to start with is to define the utility funktion: is it better to sell all to first customer or end the day with unsold goods?


Which is more fundamental: key-value or subject-predicate-object? There seems to be two approaches to store data in NoSQL databases:

Key-Value - The Key is usually stored in a hash-table referencing a Value, or Object, which can be either a key (with specific semantic) or any arbitrary data. Examples are Riak, Redis, Dynamo, CouchDB...

Subject-Predicate-Object - Subject and Predicate are interpreted as keys and Object can be either a key or an arbitrary data. This will cover not only all RDF stores, but also graph databases. Examples are Neo4j, Virtuoso, AllegroGraph...

Now I am not that interested in exact definition and which database falls into which category. We know that there are plenty of RDF triple stores implemented on top of SQL databases, as well as that any SQL database can be represented using only RDF triples. And there are other database types too, like column and document databases.

I am interested in finding out which representation is more fundamental in the sense that for example for a given processor assembler is more fundamental than C (because C is written in assembler) and C is more fundamental than Erlang (because Erlang is written in C), and so on. Or also that binary representation is more fundamental than any other (octet, decimal, hexadecimal) because it uses the smallest amount of different numbers (0 and 1). Unfortunately I don't have a strict definition of what more fundamental means exactly.

In other words, if we assume the following:

A Key is an IRI resource (globally unique identifier, like used in RDF)
A Blob is some arbitrary binary data we can't interpret

Then we can define the following two database types:

Key-Value: Where Key is an IRI and Value is either an IRI or a Blob
Subject-Predicate-Object: Where Subject, Predicate are IRIs, and Object is either an IRI or a Blob

In particular, those would be the fundamental data types stored in those two databases:

Ad 1: Key-Key, Key-Blob

Ad 2: Key-Key-Key, Key-Key-Blob

I have no doubt that any data stored in any database type (graph, column, table, key-value, triple, etc) can be represented in either of those databases. I have also no doubt that data stored in one of those databases can be represented in the other, for example let's assume to represent a Key-Value pair as {Key, Value} and Subject-Predicate-Object as {Subject, Predicate, Object}. Then:

Example 1:

{1, "abc"} can be represented as two triples {2, 3, 1}, {4, 3, "abc"} where 2 means Key, 3 means Stores or Holds, 4 means Value.

Example 2:

{1, 2, "abc"} can be represented as three tuples {1, 1}, {1, 2}, {1, "abc"} where Key = 1 means triple number 1, Value = 1 means Subject position, Value = 2 means Predicate position, Value = 3 means Object position.

The means is a conceptual shortcut for having a proper IRI representing that meaning.

Is there any scientific evidence that one representation is more fundamental than the other? Or, because there is no strict definition of "more fundamental", if we could put it as which representation can more easily and/or efficiently represent data stored in any other database type? And I am asking that because I hope that there isn't just an answer like "it depends" :)

Following your simplicity argument (binary is more fundamental than octal), I'd say that key-value stores are more fundamental.
I think that Subject-Predicate is essentially a 'compound' or 'aggregate' key, so a subject-predicate-object store is a key-value store with additional requirements on the key (namely that it can be split into two).


A pathfinding algorithm for graphs in which arc weights can change over time So I'm not really sure even what to be googling for solutions to this. Hence this question, hopefully, someone can point me in the right direction.

Here's the situation, I have a weighted undirected graph of nodes and arcs. I have an implementation that uses A* for pathfinding on this graph. However, I now have a situation where the weights (cost) of each arc can change over time. That is at each step in the A* pathfinding algorithm the weights of the entire graph can change.

So I'm trying to see if there is an existing algorithm or alteration of A*-like algorithm that handles changing weights well. If anyone has any keywords I should be looking into I'd appreciate any pointers you can provide.

Look at pathfinding algorithms in the context of robotic navigation. In many such applications, the observed world is modeled as a graph. Naturally, the environment changes meaning the graph evolves as well.

For a start, have a look at D* Lite in the work of Koenig & Likhachev. This is a rather standard work in the area, and you'll find plenty of more work regarding replanning by looking at papers that reference it.

[1] Koenig, Sven, and Maxim Likhachev. "Fast replanning for navigation in unknown terrain." IEEE Transactions on Robotics 21.3 (2005): 354-363.


sorting stone Problem My friend asked this problem recently & am not sure which sorting to use for this kind of problem:-

There are 20 stones of different heights. Each stone is so heavy, we need to sort the stones such that smallest stones are to left and highest to right. As stones are heavy make algorithm which moves stone least distance possible

Which sorting method suits this kind of problem?

Original question.

  Could Any one provide a better solution for this?

I didn't see any solution provided, so that is not a valid question. Just pointing out that we expect an effort to be made by you on solving your problem before we put in an effort to help you.

Revised question.

  Which sorting method suits this kind of problem?

If I understand this correctly, it is not the choice of a sort algorithm that is important but getting the least number of moves that is important.

So first you can choose any sort method and find the correct order of the stones.

Now knowing the unsorted order and the sorted order, find the least number of moves. Since I will take it that there is a place off to the side that you can place one stone, it should take no more than a maximum of n+1 moves to sort all of the stones.

If that is not the kind of answer you expected, then you need to add more info to the question.


Why does the ouput of an NC0 circuit depend on only a constant number of input bits? I understand that NC0 circuits have a constant depth and bounded gate fan-in of two, but I'm struggling how to understand why the language is in NC0 iff there is a constant c such that for every n, there is a set c variables that determine it's membership.

An $\mathsf{NC}^0$ circuit with single output of depth $\ell$ has $O(2^\ell)$ nodes, and in particular can depend on at most $O(2^\ell)$ many input bits.

$\mathsf{NC}^0$ circuits become more interesting when we allow them to have many outputs. Amazingly, there are some things you can actually do with some circuits. Check out the classic paper Crypography in $\mathsf{NC}^0$ by Applebaum, Ishai, and Kushilevitz.


Find m smallest elements in an array of size n where m = n/2 So we have an unsorted array, we need to find the first $m$ elements in ascending order (or $m$ smallest elements) where $m = \mathrm{array.size}/2$ (or $n/2$). How would we do this in linear $O(n)$ time.

What I was thinking of doing was use the SELECT algorithm to find the kth smallest element until $k = m$, but this way the complexity would be $n/2 \cdot O(n) = O(n^2)$.

Find the median in $O(n)$ time. Then go over the array and take out all elements smaller than the median.


What does "satisfactory definition" mean? I am reading the book Artificial Intelligence (A modern approach) by Stuart Russell and Peter Norvig. While reading the book, I saw the below sentence in the book.

The Turing Test, proposed by Alan Turing (1950), was designed to provide a satisfactory operational definition of intelligence.

Now the question is, what does the writer mean by saying satisfactory definition?
Does it have a special mathematical meaning (like as we say in some problems: f(x) satisfies some conditions)? or does the satisfactory adjective just mean good enough (as stated in Longman dictionary)?

It means nothing in particular.  You can read it as "good enough".  It is not encoding some specific technical meaning.


Clustering Application with a Huge Number of Clusters I am wondering if there are any clustering applications in practice where the number of clusters, i.e., the $k$ in the $k$-means problem is very high ($k>50$, optimally $k>200$), if possible with a citation.
The clustering can take place in any metric space.

In `Learning Feature Representations with K-means' [1] the authors apply unsupervised learning, i.e., k-means to learn 256 features (centroids, centers).
They also claim that the huge number of centers, in this case, k=256 is a limitation to this approach.
p[11]:
``Indeed, it is frequently best to set k as large as compute resources will
allow, considering data requirements. Though performance typically asymptotes
as k becomes extremely large, increasing the size of k is a very effective way
to squeeze out a bit of extra performance from an already-built system''
[1] https://www-cs.stanford.edu/~acoates/papers/coatesng_nntot2012.pdf


Non-Parametric Methods Like K-Nearest-Neighbours in High Dimensional Feature Space The main idea of k-Nearest-Neighbour takes into account the $k$ nearest points and decides the classification of the data by majority vote. If so, then it should not have problems in higher dimensional data because methods like locality sensitive hashing can efficiently find nearest neighbours.

In addition, feature selection with Bayesian networks can reduce the dimension of data and make learning easier.

However, this review paper by John Lafferty in statistical learning points out that non-parametric learning in high dimensional feature spaces is still a challenge and unsolved.

What is going wrong?

This problem is known as the curse of dimensionality. Basically, as you increase the number of dimensions, $d$, points in the space generally tend to become far from all other points. This makes partitioning the space (such as is necessary for classification or clustering) very difficult.

You can see this for yourself very easily. I generated $50$ random $d$-dimensional points in the unit hypercube at 20 evenly selected values of $d$ from $1..1000$. For each value of $d$ I computed the distance from the first point to all others and took the average of these distances. Plotting this, we can see that average distance is increasing with dimensionality even though the space in which we are generating the points in each dimension remains the same.

Average distance vs. dimensionality


Distribution of $(X_1,X_2)$ if $X_1\pm X_2$ are two independent $N(1,4)$ $X_1+X_2$ and $X_1-X_2 $ are i.i.d. $N(1,4)$. What is the distribution of $X = (X_1,X_2)^T$?
I know i.i.d. is an independent and identically distributed random variable but I don't know how to use it to solve this problem that contains a column vector.

Let $Y = (Y_1,Y_2)$ be two i.i.d. $N(1,4)$ variables. Then $Y$ is a multivariate normal distribution, and so any affine transformation of $Y$ is a multivariate normal distribution. In particular, if we define $X_1 = \frac{Y_1 + Y_2}{2}$ and $X_2 = \frac{Y_1 - Y_2}{2}$ then $X = (X_1,X_2)$ is a multivariate normal distribution which satisfies $X_1 + X_2 = Y_1$ and $X_1 - X_2 = Y_2$. In other words, it is the random variable you're interested in.
It is routine to calculate
$$
(X_1,X_2) \sim N\left(\begin{pmatrix} 1 & 0 \end{pmatrix}, \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix}\right),
$$
that is, $X_1 \sim N(1,2)$ and $X_2 \sim N(0,2)$, and $X_1,X_2$ are independent.


Existence of polynomial time reduction from P to R? Why the next idea doesn't work:

If L_2 in R and L_1 in P and the languages are not trivial,
then there is a polynomial-time reduction from L_1 to L_2

I know that if such reduction exists, than L_1 is also in R --> But L_1 is in P and P is in R, so everything looks OK :)

Will be glad for your help here.

The claim is correct, therefore, you need to give a proof that such a reduction exists. I see that you're trying to prove it by contradiction, so your question is a bit unclear. If you did not get to a contradiction by assuming the correctness of the claim, that does not mean that the claim is correct. Instead, you're assuming that it is correct.

By a similar reasoning to yours: as far as i see, if $P\neq NP$ then everything is ok :) Or if $P=NP$ then everything is okay. So maybe the claim is not correct but we don't have the tools to show that yet. Or maybe you can assume both!

Regarding the specific claim you mentioned, consider the following more general claim.

Claim: every non-trivial language $L_2 \notin \{\emptyset, \Sigma^*\}$ is $P$-hard. That is, if $L_2$ is non-trivial language and $L_1\in P$, then $L_1 \leq_p L_2$.

To begin with, note that the claim you wrote is a special case to the above claim. Indeed, we just drop down the assumptions that $L_2$ is in $R$ and $L_1$ is non-trivial.

Solution: let $L_2$ be a non-trivial language and let $L_1\in P$.  We describe a reduction from $L_1$ to $L_2$. To begin with, since $L_2$ is non-trivial, we have that there is a word $x_{in}\in L_2$ and a word $x_{out} \notin L_2$.

Defining the reduction: the reduction, denoted $f$, operates as follows. For the input word $w$, check whether $w$ is in $L_1$. If $w\in L_1$, the reduction outputs $x_{in}$. Otherwise, the reduction outputs $x_{out}$.
Correctness: follows immediately from the fact that $w\in L_1$ iff $f(w) = x_{in} \in L_2$.
Runtime: note that the reduction runs in polynomial time in $|w|$ (the input's length). Indeed, since $L_1\in P$, we have that there is a deterministic TM that decides $L_1$ in polynomial time and thus one can decide whether $w\in L_1$ in polynomial time in $|w|$. $x_{in}$ and $x_{out}$ are constants (they do not depend on the input $w$), hence they do not affect the runtime of the reduction (you can think about them as words hardcoded in the reduction itself).

Note: a machine that decides $L_1$ in polynomial time exists, $x_{in}$ and $x_{out}$ exist and thus the reduction exists.


Turing Machine with additional finite memory of size $n$ The question itself:

Let us define a generalization of Turing Machines to include a finite memory of >size $n$.
We denote such
a Turing Machine formally as:
$M_{mem} = (Q, Σ, γ, δ_{mem}, n, q_0, q_a, q_r)$
where all the definitions are identical to the standard Turing Machine except >that there is the finite memory size n and the transition function δmem. At each >step, the transition depends on the
current state, the input on the tape and all the memory. The transition to the >next step can update
the entire memory.
Formally: $δ_{mem} : Q × Γ × Γ^n → Q × Γ × Γ^n × {L, R}$.
Given a finite memory Turing Machine $M_{mem}$, define $formally$ a (standard) Turing Machine $M$ such
that $L(M) = L(M_{mem})$. Namely, both Turing Machines accept the same language.

my approach
I am asked to give two different constructions of such a turing machine. The first way that I managed to come up with is to encode the memory into the states of the turing machine and I managed to do so. I thought that a second way to do it is to encode the memory into the tape itself by concating the string in the memory into the input char itself but this causes problems because the turing machine doesn't have access to the memory in such a way because it will write down the encoding and then move left or right so it won't see the encoding of the memory no more. please guide me with the second approach and/or suggest me another way to do it.

I don't think that you can "embed" the extra memory into the alphabet and "carry" it with the head moving around without a $|Q|$ blow-up (blow-up comparable to the one of approach 1).

So a (weird!) approach to keep the size of $|Q|$ low, that can work is the following:

embed both the extra memory and $Q$ into the alphabet $\Gamma_M = \{H,h\} \times Q \times \Gamma \times  \Gamma^n$
use only ONE cell (marked with embedded symbol $H$) to represent the current state of $M_{mem}$ + symbol under its head + the content of the extra-memory
use some additional states to SHIFT the tape around the cell $H$

Very informally you have:

                  q1
                  S
....0 1  1 1 0 0 [0] 1 1 0 0 0 ...
    h h  h h h h  H  h h h h h
                  ^
                  q_sim

In this condition, the (standard) Turing machine $M$ is on state $q_{sim}$ and is on symbol $\langle H,q_1,0,S \rangle$ that represents: head of $M_{mem}$ is on state $q1$, reading a $0$ and the content of the extra memory is $S$

Now if $M_{mem}$ writes a 1, writes $S'$ on the extra memory, moves $L$eft and enters $q_2$; the standard $M$ on state $q_{sim}$ writes $\langle H,q_2,1,S' \rangle$ and enters a sequence of states $q_{r_1},...,q_{r_k}$ that shift the whole tape one cell to the right and returns back on the cell marked with $H$ and state $q_{sim}$; simulating in this way the movement of the $M_{mem}$'s head:

                  q2
                  S'
....  0 1  1 1 0 [0] 1 1 1 0 0 0 ... << tape shifted right
      h h  h h h  H  h h h h h h
                  ^
                  q_sim

Note that the standard $M$ simulates $M_{mem}$ transitions using only a single state $q_{sim}$ (plus two extra-states for accept/reject).

Also note that the symbol corresponding to the extra memory $S'$ is NOT MOVED, so the total number of states of $Q_M$ required to shift the "underlying" tape (simulating the move of the head of $M_{mem}$) depends only on $\Gamma$, not on $n$:

$\Gamma_M = \{H, h\} \times Q \times \Gamma \times \Gamma^n $

$\delta_M = Q_M \times \Gamma_M \to Q_M \times \Gamma_M \times \{L,R\}$

and $|Q_M| = k |\Gamma|+c$

You can also choose to embed the states of $M_{mem}$ into $Q_M$: in this case the alphabet is: $\Gamma_M = \{H, h\} \times \Gamma \times \Gamma^n $, but you must use more states: $|Q_M| = k |Q| |\Gamma|+c$

The above construction can also be generalized to standard Turing machines and (very informally) it roughly represents a switch from:

$\delta : Q \times \Gamma \to Q \times \Gamma \times \{L,R\}$ to

$\delta : \Gamma \times Q \to \Gamma \times Q \times \{L,R\}$


Defining polynomial hierarchy with oracle machines and quantifiers While trying to understand the concept of polynomial hierarchy, I noticed that there are several ways to define it. And the most confusing thing about the situation is to see the equivalence between those definitions intuitively. What I want to know for now is the relation between oracle machines and existential/universal quantifiers from the viewpoint of polynomial hierarchy.

By Wiki, the polynomial hierarchy is the generalization of the classes P, NP, and co-NP to oracle machines. The addition of oracles (not sure this is a suitable expression) results in the increase of the hierarchy.

On the other hand, another way to define the polynomial hierarchy is to use the quantifiers $\forall$ and $\exists$. According to this lecture note (http://www.cs.cornell.edu/courses/cs6810/2009sp/scribe/lecture5.pdf),
a language $L$ is in $\Sigma_i$ iff $\exists$ a polynomial time relation $R$ s.t. $x\in L$ iff
\begin{equation}
\exists y_1\forall y_2\cdots Q_iy_iR(x,y_1,\cdots y_i),
\end{equation}
where $Q_j=\forall$ if $j$ is even and $Q_j=\exists$ if $j$ is odd. And $L$ is in $\Pi_i$ iff its complementary $\bar{L}$ is in $\Sigma_i$.

From the above definitions, it seems that there exist a sort of one-to-one correspondence between the inclusion of oracle and the addition of quantifiers.

Can anyone help me understand how the oracles in a Turing machine plays the role of quantifiers in predicates?

The oracles do not play the role of quantifiers, they play the role of everything but the first quantifiers.

First, observe how NP relates to $\exists yR(x,y)$ with $R$ in P. That means that NP allows existential nondeterminism followed by computation in P.

Similarly, $\Pi_1$ "is" $\forall yR(x,y)$ with $R$ in P.
Now for $\Sigma_2$ we have the same with an additional $\exists$ at the front: $\exists y_1\forall y_2R(x,y_1,y_2)$ with $R$ in P. Or, in other words,
$\exists y_1 R'(x,y_1)$ with $R'$ in $\Pi_1$. So we have existential nondeterminism followed by computation in $\Pi_1$. And that is more or less the same as NP with a $\Pi_1$ oracle.

In general, the first quantifier specifies whether we are in the existential or universal case. The rest of the formula then describes a lower level of the hierarchy which we use as an oracle.


Why was primality test thought to be NP? To check if $n$ is prime, one only need to try dividing $n$ by numbers up to $\sqrt{n}$, meaning that the complexity would be $O(\sqrt{n})$. In my opinion, $O(\sqrt{n}) < O(n)$ so this simple algorithm is already P. But why did people think that primality test is NP, and were surprised by the AKS primality test?

To start, any decision problem with a witness verifiable for a "yes" answer in polynomial time is in NP.

$\bullet$ The problem 'Is $p$ composite?' has a witness $k$, and it can be tested in polynomial time whether $k$ divides $p$, therefore is in NP.

$\bullet$ The problem 'Is $p$ prime?' has a polynomial certificate (which can be found here), therefore is also in NP.

Now, your complexity analysis is not correct. If your input is a number $p$, then the input size is $\log (p)$, since you need $log(p)$ bits to represent it. Therefore, $n=\log(p)$ and $\sqrt{p}=\frac{1}{2} \log(p)$ bits. So the time required (in respect to $n$) checking all the numbers up to $\sqrt{p}$ will be $2^{\frac{1}{2}n}$, and is in fact exponential in terms of input size $n$.

The question "Where exactly does the Primality problem lie" has been answered in the link here


Are there any existing problems that wouldn't be solvable with a halting oracle? I understand that most problems are trivial if a halting oracle is available (or, I think equivalently, hyper-computation). However, applying the argument that shows the Halting Problem is impossible for a Turing machine also shows that it is impossible for a Turing+oracle to decide the Halting Problem for a Turing+oracle. Are there any actual, practical, examples of problems unsolvable by a halting oracle?

Note: by "oracle" I mean oracle for a standard Turing machine, not a TM with an oracle itself.

Just take a problem whose Turing degree is above $0'$, which is the degree of The Halting Oracle. In terms of the arithmetical hierarchy you want problems which are above $\Sigma^0_1$. Examples of such problems (where $\phi_n$ is the $n$-th partial computable function and $W_n = \{k \in \mathbb{N} \mid \text{$\phi_n(k)$ is defined}\}$ is the $n$-th computably enumerable set):

$\{n \in \mathbb{N} \mid \text{$\varphi_n$ terminates for finitely many inputs}\}$ is $\Sigma^0_2$-complete.
$\{n \in \mathbb{N} \mid \text{$\varphi_n$ is a total function}\}$ is $\Pi^0_2$-complete.
$\{n \in \mathbb{N} \mid \text{$W_n$ is a computable set}\}$ is $\Sigma^0_3$-complete.

None of these can be solved even if you have a Halting Oracle. For instance, consider the second example, "is $\varphi_n$ total?" Given $n$ how would the Halting Oracle help us decide whether the Turing machine encoded by $n$ halts on every input?

[Added 2014-06-03] For a "practical" aspect of all of this, consider the problem: a programmer has written a function void charge_credit_card(int card_number, int amount) and we would like to know whether the function terminates on all inputs. It is impossible to write a compiler which can automatically check this in general. Moreover, even if we allow the compiler to ask us questions of the form "does charge_credit_card terminate when given input (k,m)?", it is still impossible.


Why do they say `A, B, C, ... implies M` instead of `A∧B∧ C∧ ... implies M`? The conclusion follows from all the premises. It seems to me that this means that conclusion from the conjuntion of the premises. Right? Why does logic uses comma instead?

It's a distinction between language and metalanguage.

$A, B \vdash M$ says: if I have both $A$ and $B$ amongst my hypotheses, then I can deduce $M$.
$A \wedge B \vdash M$ says: if I have $A \wedge B$ amongst my hypotheses, then I can deduce $M$.
The fact that the two are equivalent comes from the definition of the operator $\wedge$.

I could define a new operator $?$ with these deduction rules (using the sequent calculus formulation):
$$
  \frac{A \vdash M}{A ? B \vdash M} \qquad
  \frac{B \vdash M}{A ? B \vdash M} \qquad
  \frac{\vdash A, M \quad \vdash B,M}{\vdash A?B,M}
$$

This new operator has the same rules as $\wedge$ (in the sequent calculus), so I could substitute $?$ and $\wedge$ in a true judgement and still get a true judgement, and vice versa. Nonetheless, they are syntactically speaking two different propositions.

It takes a while to internalize the difference between the language and the metalanguage, especially in the beginning when you only study a logic which models our everyday reasoning. There are logics such as intuitionistic logic and linear logic which diverge further, and while these logics (especially linear logic) are more advanced, they are in some ways easier to handle because there is a clearer separation between the logic and the meta-logic.

I'll briefly discuss “and” in linear logic, to illustrate this point. To put it in a nutshell, in everyday logic, if you have a hypothesis, you can use it at multiple points in a proof. In linear logic, a hypothesis can only be used once, unless it's marked as reusable. Linear logic can thus model processes that aren't proofs as you think of them, but more physical processes, such as “if I have a cake before eating it, then I have no cake after eating it”. Linear logic has two conjunction operators. Both say: if I have a process that produces an $A$, and I have a process that produces a $B$, then I have a process that produces an $A$ “and” a $B$. They differ in how the processes are combined:

Multiplicative conjunction puts the two processes next to each other: given $\vdash \Gamma, A$ and $\vdash \Delta, B$ (a process that produces an $A$ and some more stuff, and a process that produces an $B$ and some more stuff), I can combine them to make $A \otimes B$ and the combined output of the two processes: $\vdash \Gamma, \Delta, A \otimes B$. For example, if I make a plate of spaghetti and an apple pie, I can eat a plate of spaghetti and an apple pie.
Additive conjunction runs the two processes together: given $\vdash \Gamma, A$ and $\vdash \Gamma, B$ (I can run the process and produce $\Gamma$ plus either $A$ or $B$), I can run that same process and produce both: $\vdash \Gamma, A \& B$. For example, if I can spend \$10 to get a plate of spaghetti or I can spend \$10 to get an apple pie, then \$10 gets me the choice of spaghetti or pie (but it doesn't get me $A \otimes B$, where I have both spaghetti and pie).


What are some approaches to solve these classes of problems efficiently Good day,

Please consider the following problem:
3 friends named Alice, Bob and Cindy have 3 food items (cheese, tomato, bread) in the fridge.

Each person has a particular numerical preference score (any positive number) for each food item.

It has been agreed upon that each person should take one and exactly one food item. (cheese bread and tomato can not be broken up to pieces)

we are interested in coming up with a matching that would maximising the total happiness.

Here is a concrete example:

Foods Vector: [Cheese, Tomato, Bread]

preferance vector: (Preference score for Cheese, Tomato and Bread in order)
Alice (4,3,3)
Bob   (2,4,5)
Cindy (5,1,3)

brute force: try all combos

//Cheese belongs to Alice, Tomato belongs to Bob, Bread belongs to Cindy...
total score for [Alice,Bob,Cindy]: 11

total score for [Alice,Cindy,Bob]: 8

total score for [Bob,Cindy,Alice]: 6

total score for [Bob,Alice,Cindy]: 8

total score for [Cindy,Bob,Alice]: 12

total score for [Cindy,Alice,Bob]: 13  //best solution

It looks like we should give Cheese to Cindy, Tomato to Alice, and Bread to Bob for the greater good of the republic.

Of course the naive brute force method is acceptable here because n=3, however if we have 100 people and 100 food items this method would be prohibitively expensive.
it seems to me that n! will be the asymptotic complexity which is worse than exponential.

I attempted to relate this problem to other well known problems like knapsack or Interval scheduling with no success.

I would appreciate informed input on the type of this problem and if there are other approaches to find the optimal or good approximation solution in reasonable time.

I have come up with a greedy algorithm that can do well in some cases, here it is:

      Cheese  Tomato  Bread
Alice 4       3       3
Bob   2       4       5
Cindy 5       1       3

1- for each Person, find the Food among remaining foods that is preferred, assign that food to the person.
2- eliminate the chosen food from the list of available foods
3- repeat until you are left with the last person

in my going step by step it would look like this:

Step 1:

      Cheese  Tomato  Bread
Alice *4      -       -
Bob   -       4       5
Cindy -       1       3

Step 2:

      Cheese  Tomato  Bread
Alice *4      -       -
Bob   -       -       *5
Cindy -       1       -

Step 3:

      Cheese  Tomato  Bread
 Alice *4      -       -
 Bob   -       -       *5
 Cindy -       *1       -

This will take n steps as opposed to n!, and in this case gives us a reasonable answer (10) but in other situations the discrepancy between optimal solution and greedy solution is huge:

preferance vector: (Preference score for Cheese, Tomato and Bread in order)
Alice (3,2,1)
Bob   (9,1,2)
Cindy (5,0,9)

brute force: try all combos

total score for [Alice,Bob,Cindy]:   13

total score for [Alice,Cindy,Bob]:   5  //greedy!!!

total score for [Bob,Cindy,Alice]:   10

total score for [Bob,Alice,Cindy]:   20 //best

total score for [Cindy,Bob,Alice]:   7

total score for [Cindy,Alice,Bob]:   9

This is an instance of the assignment problem.  There are polynomial-time algorithms for solving the assignment problem, e.g., using the Hungarian algorithm (or other algorithms).


Is this a valid representation of a function in Lambda Calculus? Let's say I want to define a function:

This function multiplies an input by two, adds one to this integer, then divides it by two in that order.

f represents the multiplication, g represents the addition, and h represents the division.

Could I represent this as λx.fxgh, when explicitly defined with parentheses is shown as λx.(((fx)g)h))?

I would think that is correct, because you evaluate the innermost function first, then move outwards treating each evaluated function on the inside as input for the next one, no?

It's valid (because it respects $\lambda$-calculus syntax) but won't work as you expect. To see that just take your favorite language and try it out:

let f = \x -> 2*x
let g = \y -> y+1
let h = \z -> z/2

(\x -> (((fx)g)h))) 1 won't evaluate to $1.5$. Why?

Because $g$ and $h$ are functions and take one argument each, and application happens when there's an abstraction to the left. So if you change the order you will get the expected behavior.

$$ \lambda x. (h (g (f ~ x))) $$

or

$$ \lambda x. ((h  \circ g  \circ f)  ~ x) $$

In Haskell:

(\x -> (h . g . f) x)

where . ($\circ$) is for function composition.

Example:

$$ \big(\lambda x. (h (g (f ~ x)))\big) 1  \rightarrow (h (g (f ~ 1))) \rightarrow (h (g ~ 2)) \rightarrow  (h ~ 3) \rightarrow 1.5 $$


Is reaching in less lines semi-decidable? Assuming we have two programs $p_1$ and $p_2$ and two line numbers $n_1$ and $n_2$. Does $p_1$ reach $n_1$ in less computational steps than $p_2$ reaches $n_2$? By reduction from Halting, this is clearly not decidable, but I think it is semi decidable.

To do so, I would build an interpreter, that executes $p_1$ and $p_2$ simultaneously step by step and count the steps for each program. As soon as $p_1$ reaches $n_1$, I compare the number of steps to $n_2$ and return true if it is less. If $p_2$ reaches $n_2$ first, I return false. In case no program reaches $n_1$ or $n_2$, nothing happens (following semi-decidability).

It's only semi-decidable if you word your decision problem very carefully. And you have to word it in such a way that the case where both programs never reach their $n$s is in the REJECT category. Since $\infty < \infty$ is ambiguous/undefined I would explicitly mention this case in your decision problem.

Other than that, yes it's correct. Your machine halts if either $p_1$ or $p_2$ halts (viewing reaching $n$ as just another halting condition) and provides the correct answer in such a scenario. If you patch up the above issue then when neither $p_1, p_2$ halts you are in the REJECT case and thus you are allowed to never halt as well by semi-decidability.


How to convert this recursive algorithm to an iterative form? Let us assume there's a folder structure as shown below: The letters a-d represent folders and the number 1-5 represent video files where for the file n, size(n)=n. So, 1 = 1MB, file 2 = 2MB, etc.

a
├── 1
├── b
│   ├── 2
│   └── 3
└── c
    ├── 4
    └── d
        └── 5

3 directories, 5 files

I want to write a script that takes as input a directory (e.g., a), and tells us the total video duration in that folder (iT=immediateTime) and the total video duration in that folder and all its sub-folders (tT=totalTime).

My pseudocode is:

function calcTime(dir)
{
    tT = iT = singleLevelCalcTime(dir);
    foreach(subdirectory in dir) {
        t+= calcTime(subdirectory);
    }
    echo iT;
    echo tT;
    return t;
}

Now, according to the Crunch-Turing thesis, essentially, every recursive function is mathematically proven to have an equivalent iterative version. My problem is I can't find any way to do this using just loops. I've read that explicit stacks (instead of the implicit ones generated by the nature of recursion) can solve this, but I can't figure out how.

For example, the first part of the algo is simple - iT can be calculated by the same method as in the original algorithm. Now, the program must enter each sub-directory and perform the same task again. However, without using recursion, I'd have to provide multiple levels of nested loops (unknown number of levels) to loop through each file/folder in each level. Please tell me where my approach is lacking. I can't really comprehend how to build an explicit stack that can solve this!

You have to perform a visit of the directory graph, such as a DFS. Since the graph you're dealing with is a tree, you can use a tree traversal instead, which is conceptually identical but should be easier to implement.

Just a pedantic note: you don't need the Church thesis to say that every recursive function is Turing-computable, it can be proven formally.


Non-computability and Undecidability? Is there a difference between a non computable problem and an undecidable problem? Or is one included in the other?

Non computable problems are also undecidable. Basically undecidable is a subset of non computable.

This is because if you can't even say yes or no then you can't compute it. Take for example the Halting Problem of a Turing Machine, suppose someone asked you after how many steps the Turing Machine will halt on a given input. To answer the exact number you first have to answer whether the Turing Machine is going to halt or not. Then i may count the steps.

What we do is to convert our optimization problem to a decision problem. And if we are not able to give answer of that decision problem we cannot compute it. So, computing is harder than saying yes or no. So if the problem is undecidable then it will be also non computable.


Fast algorithm for interpolating data from polar coordinates to cartesian coordinates I have a set of solution nodes generated over a polar grid. I would like to convert / interpolate these solution nodes onto a Cartesian grid:

That is, using the image above, for each node in the Cartesian grid I would interpolate a value from the closest existing nodes (red).

Currently, my approach is to generate a kd-tree for the original solution nodes, then use a nearest-neighbor search to obtain the three closest nodes. I then use barycentric interpolation to obtain a value from these three points. The problem, however, is that my polar grid is much finer along the radial direction than it is in the azimuthal direction, which means that my nearest-neighbor search almost always selects points from the same radial. This has the result of creating "striations" in my new solution, instead of smoothly interpolating along the azimuthal direction (i.e., the results look no different than if I had simply mapped the nearest point to the "interpolated" point).

Unfortunately, I don't know how to achieve a better sampling without sacrificing the kd-tree and losing a lot of the speed improvements. Am I being thick-headed and missing an obvious solution? Or does anyone know a better way to approach this problem?

I don't know if this has been studied by others.  Speculating off the top of my head, let me outline two possible approaches.

Applying standard rectangular methods to polar coordinates

Here's one way to adapt more familiar interpolation methods (that work with Cartesian coordinates) to your setting.  Let's start by looking at bilinear interpolation.

Let $P$ be the point on the Cartesian grid whose value you want to compute, using interpolation.  Find the smallest "rectangle" of four nodes that surround the point $P$.  A "rectangle" in polar coordinates is just like a rectangle in a Cartesian grid, except with up/down replaced with "inward"/"outward" and right/right replaced with "clockwise"/"counterclockwise".  For instance, here is an example of a "rectangle" in a polar-coordinate grid:

This gives you 4 nodes that surround $P$.  Finally, use these 4 nodes to interpolate and form the value for $P$.  For instance, you could do bilinear interpolation, in the same way we do bilinear interpolation on a Cartesian grid, but now working with polar coordinates / barycentric coordinates.

This also makes clear how to generalize to other interpolation schemes, such as bicubic interpolation.

Ad-hoc method: supplement from adjacent radials

One possible approach you could try would be to pick the 3 closest nodes, then supplement them with a few other nodes from adjacent radials.

Let $P$ be your point.  Start by picking the closest 3 nodes to $P$ (say).  Then, supplement them.  For instance, suppose all 3 nodes are on the radial $\theta$.  Look at the radial just to the left of it, $\theta-\epsilon$, and out of all nodes on that radial, pick the 1 or 2 nodes that are closest to $P$.  Similarly, look at the radial just to the right of it, $\theta+\epsilon$, and out of all nodes on that radial, pick the 1 or 2 nodes that are closest to $P$.

Now use those points to interpolate.  You might use weighted least-squares regression to fit a linear (or bilinear/bicubic/etc.) model, where the nodes that are closer to $P$ receive a higher weight.  If you experiment a bit with the number of points chosen, the type of model, and the weights, you might find a scheme that reduces the "striation" artifacts.

Maybe better schemes are known; I don't know.  I'm not expert in this area.


Time Complexity of Sort-Merge Join According to this German Wikipedia article, the time required to merge relations $R$ and $S$ is $\in \mathcal{O}(|R| + |S|)$ if both relations are already sorted.
[Note: You don't really need to read the text and the link jumps right to where the time complexity is stated. But I added a translation of that section to this question for some clarity.]

Assume $R = S$ with $R$ having 2 columns. One is a random number and one is always 5 for every line. Join $R$ and $S$ on the column which is 5 for every line. The resulting output's space complexity is $\in \Theta(|R| \cdot |S|)$. Time complexity is always $\in \Omega(\text{spaceComplexity})$.

How can the time complexity stated by the Wikipedia article be true?

Here is the "Sort-Merge Join" section translated to English. Sorry, no markdown quote, just everything from here on is the quote. It's translated poorly (not how you would write it in English if you know what you're writing) in some parts to preserve the meaning as well as possible. I marked my own inline comments with ///.

Quote of https://de.wikipedia.org/wiki/Joinalgorithmen#Sort-Merge_Join

Sort-Merge Join

Both relations get sorted by their join attributes. The result can be determined via a single scan through both sorted relations.

The algorithm is only suited for natural join and equi-join.

Pseudocode

Implementation of $R\bowtie_{R.a=S.a} S$ in pseudocode:

p_r := first tuple in R
p_s := first tuple in S
while(p_r != endof_r && p_s != endof_s)
    // Collect all tuples in S with the same join attributes.
    M_s := set with contents p_s /// Yes, it says "with", not "of".

    foreach(t_s in S > p_s)
        if(t_s.a = p_s.a)
            M_s += set with contents t_s
        elseif // I think they mean "else".
            p_s := t_s
            break foreach
        endif
    endforeach

    // Seach suitable start tuple in R. /// "passend" can also be translated "fitting" or "matching", not just "suitable".
    foreach(t_r in R > p_r)
        p_r = t_r
        if(t_r.a >= t_s.a)
            break foreach
        endif
    endforeach

    // Output tuples.
    foreach(t_r in R > p_r)
        if(t_r.a > t_s.a)
            break foreach
        endif

        foreach(t_s in M_s)
            Write output: (t_r, t_s)
        endforeach
        p_r = t_r
    endforeach
endwhile

Evaluation

Sorting can be done with effort $\mathcal{O}(|R|\log|R|+|S|\log|S|)$. The number of block accesses to sort $S$ is $b_s\left(2\log\frac{b_s}{b_{free}}\right)+b_s$ in the worst case, analogous for $R$.

A merge of both relations after sorting them costs $\mathcal{O}(|R|+|S|)$. In the best case – i.e. the relations are already sorted –, the costs of merging are the only ones.

In the normal case, the total costs are $\mathcal{O}(n\log n)$.

Variants

[Not translated because it doesn't seem to be important for the question.]

You are absolutely correct.  Wikipedia has an error -- or perhaps, if we are feeling more charitable, we could call it an oversimplification.

It is not true that the running time is at most $O(|R|+|S|)$.  For instance, if we consider the case where the value of attribute $a$ is 42 for all elements of $R$ and $S$, we output $|R| \times |S|$ tuples.  It is also easy to see that the pseudocode does $|R| \times |S|$ iterations of the nested inner loop (i.e., that many iterations of the statement "Write output:"), so the running time is also $O(|R| \times |S|)$.

Here are some statements that are true:

If there are no repeated values of $a$ (i.e., each value for $a$ appears at most once in $R$ and at most once in $S$), then the running time for the merge is $O(|R|+|S|)$, and the size of the output is also $O(|R|+|S|)$.
If any value appears at most $c$ times in attribute $a$, where $c$ is a constant, then the running time for the merge is $O(|R|+|S|)$, and the size of the output is also $O(|R|+|S|)$.
If we count only the I/O complexity (the number of disk/cache transfer operations), and if memory is large enough to hold $|S|$ items, then the I/O complexity is $O(|R|+|S|)$... though the running time and the size of the output might be as large as $O(|R| \times |S|)$.  More generally, the same statement is true if any value for attribute $a$ appears at most $k$ times in $S$, and main memory is large enough to hold at least $k$ items (here $k$ does not need to be a constant).

So Wikipedia's statement is misleading or wrong or (at best) over-simplified.  Perhaps what they really meant was one of the bullet items above.  Your understanding is absolutely correct.


∅-free regular expressions? This is a question involving regular expressions for regular languages.

I am currently stuck trying to prove that the operand ∅ is not necessary unless the language is the empty set. That is, a regular expression is either equivalent to ∅ or is a ∅-free regular language. (A language is ∅ free if it contains no occurences of ∅)

This seems to be an induction proof, but I'm not really sure how to prove this. It seems like you're possibly trying to show that if a set is ∅ free, then doing anything involving ∅ will either result in the language ∅ or a ∅ free language.

So if r is ∅ free, then (r+∅) = r, r∅=∅ etc

I'm not really sure if this is really complete. I'm not overly comfortable with regular languages yet, so any help is much appreciated.

Preforming the proof by induction on the structure of the tree is good way to go about this. I like to think about how I would write a program to remove them because this directly leads to a constructive proof.

Say our regular expressions have the following form

$$
\begin{align}
regex ::=& \,\, regex \,\, regex \\
        |& \,\, regex^* \\
        |& \,\, regex^+ \\
        |& \,\, regex\,? \\
        |& \,\, regex + regex \\
        |& \,\, char \\
        |& \,\, \varnothing
\end{align}
$$

The bases cases are the cases in which the regex is either a character or $\varnothing$

To give an inductive step say we have a regular expression of the form $regex + regex$. We can then recursively convert the two sub parts to regular expressions which either are the empty set or contain no empty set. So we have 4 cases

case 1: Both expressions contain no $\varnothing$ in which case we are done

case 2/3/4: One of the sides (possibly both) is $\varnothing$ so we remove that side. One needs to prove that this is valid but it isn't hard.

all the cases are going to precede as such with different proofs that the empty set can be eliminated.


Keeping a binary search tree by splitting nodes (like a B-Tree) A B-tree is kept balanced (i.e. all leaves at same depth) by splitting a node when adding a child that won't fit, and propagating this splitting up to the root.

Can the same technique be used to keep a regular binary search tree balanced (since a binary search tree can be viewed as a 2 child maximum B-tree)? If so, does that rebalancing method have a name, and what are its advantages/disadvantages to other ways of keeping a BST balanced, such as Red-Black trees?

1-2 Brother Trees, as in "Purely Functional 1-2 Brother Trees" by Ralf Hinze in some way allow splitting a node. Like in 2-4 trees where nodes have 2 to 4 children, in 1-2 brother trees, nodes have 1 to 2 children.

The advantages are a bit hand-wavey: it is sometimes faster, and sometimes simpler, and sometimes uses less space.


More efficient vertex-labelling algorithm than BFS? I am using the C++ boost library implementation of the push relabel algorithm to solve a max-flow problem. The output from that algorithm is a residual graph and in order to find the min-cut of my original graph, I need to find all of the vertices which are reachable from the source vertex in the residual graph.

I was planning to use BFS or DFS to traverse the residual graph, but I was wondering if there was any more efficient algorithms that anyone can suggest, as the size of my graphs are pretty large.

I plan on implementing my own, modified version of the push relabel algorithm eventually, and then I can probably label them as I go. But for now I would like to just run it with the boost library, so that I have something for comparison - but unfortunately that requires labelling the vertices separately.

Any suggestions would be greatly appreciated

For graphs that fit into main memory (or even in a largish L3 cache), you probably can't do much better than your library's traversal algorithm without significant effort.

But anyway, you're way into "try and measure" territory. Robert Sedgewick has a nice talk Putting the Science back into Computer Science, that explores flow problems as an example. He uses Ford-Fulkerson, not push-relabel.


How does these Probing time occurs for hash tables I am having a hard time understanding the numbers of probing which might occur due to using different collision prevention method such as separate chaining, Linear Probing, double probing, which is given here.

  Let $\alpha = N/M$ (the load factor: average number of keys per array index). Analysis is probabilistic, rather than worst-case.

  Expected number of probes:

  $$\begin{eqnarray*}
&\text{not found} & \quad\text{found}\\
\text{chaining}\quad & 1+\alpha &\quad1+\frac\alpha2\\
\text{linear probing}\quad & \frac12 + \frac1{2(1-\alpha)^2} &\quad \frac12 + \frac1{2(1-\alpha)} \\
\text{double hashing}\quad &\frac1{1-\alpha} &\quad \frac1\alpha \ln\frac1{1-\alpha}
\end{eqnarray*}$$

A clarification of why the numbers are as they are would be appreciated. :)

To give you a test of the analysis, here it is for chaining.

When the load factor is $\alpha$, the length of the list at each cell is distributed $\mathrm{Bin}(N,1/M)$, and its expected value is $N/M = \alpha$. When the probe is not found, we have to go over the entire list, and thus we have something like $\alpha$ probes in expectation. When the probe is found, the length of the list is $\mathrm{Bin}(N,1/M)$ conditioned on being positive, which is somewhat larger than $\alpha$ (and can be calculated exactly). In this case, assuming that the probed element is chosen at random from the set of all elements, its position in the list is uniformly random, and so in expectation it is found at the middle of the list, and therefore we have something like $\alpha/2$ probes.

If we are more careful then we will probably get the formulas stated at the first row of the table, or at least something very close.

The other rows of the table result from similar analysis. Each case is different. If you want to know more, I suggest you look for other online or offline resources rather than probing us here.


$\{a^n b^n\} \cap \{a^*b^*\}$ regular or not? I have been asked a very interesting question in preparation for my exam coming up. The question is as follows:

Is $L=\{a^n b^n : n \geq 0\} \cap \{a^*b^*\}$ regular or not?

Assume $L$ is regular. Then, $L^c$ should be regular as well. Thus, $L^c = \{a^n b^n : n \lt 0\} = \{\}$, so if I compliment the compliment, I should get $L = U$ (the universal set). So, then $L=\{a^n b^n : n \geq 0\} \cap \{a^*b^*\} \neq U$, because $L$ does not contain words of the form $baba$, or $baaaababa$, etc. Therefore the language is not regular.

Is this an acceptable answer for the upcoming exam? Does this persuade anyone?

The complement of $\{a^nb^n \mid n \geq 0\}$ is not $\{a^nb^n \mid n < 0\}$. And the complement of the complement should always equal the original set. The rest of your argument falls apart here.

As an example, abb is a string that is not $a^n b^n$, thus it should be in the complement of L.

To hint at an answer, is there any string $a^nb^n$ that is not $a^*b^*$? What does this say about the intersection of the two?


Proper TSP implementation by brute force I need to implement TSP algorithm by brute force for learning purposes.

I've understood there's a set of cities, let's call it V and it's possible to get a matrix representation for the costs for going from a v1 city to a v2 city. I'll assume there are not cycles, so  it's no possible to going from v1 back to v1

Then, I should generate a matrix after these sum series:

However, I really can't see in a practice way how a matrix would be outputed from restrictions.

Let's say we got 3 cities:

  Madrid, Berlin and Malmo

So the path costs are (and they're not forced to be the same for ways back):

From Madrid to:

Berlin: 12
Malmo:  20

From Berlin to

Madrid: 32
Malmo:  12

From Malmo to:

Madrid: 14
Berlin: 17

So my input is:

$$\begin{bmatrix} 0 & 12 & 20 \\ 32 & 0 & 12 \\ 14 & 17 & 0\end{bmatrix}$$

How should the matrix be outputed according to the sum series?

  I assume the algorithm would need to generate a matrix from this exampple:

There are 3 cities x1, x2 and x3 and got the costs matrix shown below:

$$\begin{bmatrix} 10 & 2 & 1 \\ 3 & 10 & 2 \\ 11 & 2 & 10\end{bmatrix}$$

Following, example shows the next matrix:

$$\begin{bmatrix} x_{11}+x_{12}+x_{13} &  &  \\  & x_{21}+x_{22}+x_{23} &  \\  &  & x_{31}+x_{32}+x_{33}\\x_{11} & x_{21} & x_{31} \\ x_{12} & x_{22} & x_{32} \\  x_{13}& x_{23} & x_{33} \end{bmatrix}$$

Which would be the same as:

$$\begin{bmatrix} 1&1&1&0&0&0&0&0&0\\ 0&0&0&1&1&1&0&0&0\\ 0&0&0&0&0&0&1&1&1\\ 1&0&0&1&0&0&0&1&0\\ 0&0&1&0&0&1&0&0&1\\ 0&1&0&0&1&0&0&1&0\\ \end{bmatrix}$$

Then, considering the power ser of the three cities, matrix got the following rows added:

$$\begin{bmatrix} 0&1&1 & 0&0&0 & 0&0&0 \\ 0&0&0 & 1&0&1 & 0&0&0 \\ 0&0&0 & 0&0&0 & 1&1&0 \\ 0&0&1 & 0&0&1 & 0&0&0 \\ 0&1&0 & 0&0&0 & 0&1&0 \\ 0&0&0 & 1&0&0 & 1&0&0  \end{bmatrix}$$

Finally, the whole generated matrix is:

$$\begin{bmatrix} 1&1&1&0&0&0&0&0&0\\ 0&0&0&1&1&1&0&0&0\\ 0&0&0&0&0&0&1&1&1\\ 1&0&0&1&0&0&0&1&0\\ 0&0&1&0&0&1&0&0&1\\ 0&1&0&0&1&0&0&1&0\\ 0&1&1 & 0&0&0 & 0&0&0 \\ 0&0&0 & 1&0&1 & 0&0&0 \\ 0&0&0 & 0&0&0 & 1&1&0 \\ 0&0&1 & 0&0&1 & 0&0&0 \\ 0&1&0 & 0&0&0 & 0&1&0 \\ 0&0&0 & 1&0&0 & 1&0&0 \end{bmatrix}$$

I don't think you should build your matrix according to the integer program, but rather the distance matrix is given as input.

Label your cities in some way, for example let $1$ be Madrid, $2$ be Berlin, and $3$ be Malmo. In your matrix, the entry $(i,j)$ will contain the distance from the city $i$ to city $j$. So you'll get a $3 \times 3$ matrix with zeros on the diagonal (the distance from Madrid to Madrid is zero):

$$\begin{bmatrix} 0 & 12 & 20 \\ 32 & 0 & 12 \\ 14 & 17 & 0\end{bmatrix}$$

Notice that the matrix would be symmetric, if the distance from city $i$ to $j$ would equal the distance from $j$ to $i$.


Can we separate P and E? Let $\mathsf E$ be deterministic exponential time with linear exponent.  Do we know that the inclusion $\mathsf P\subseteq\mathsf E$ is strict?  If so, what's the proof?

The time hierarchy immediately separates, for instance, $\mathsf E$ and $\mathsf{TIME}(2^{n\log n})$.  Diagonalizing directly on $\mathsf P$ yields essentially the same bound (because diagonalizing polynomials gives $n^n=2^{n\log n}$).  But none of this yields a linear exponential upper bound...

Hint: The time hierarchy theorem implies that there is a function $g$ solvable in time $f(n) = n^{\log n}$ but not in time $o(f(n)/\log f(n)) = o(n^{\log n}/\log^2 n)$. In particular, $g$ cannot be solved in polynomial time.


Is NPSPACE also closed under polynomial-time reduction and under log-space reduction? The complexity classes P, NP, and PSPACE are closed under polynomial-time reduction.

The complexity classes L, NL, P, NP and PSPACE are closed under log-space reduction.

I wonder if NPSPACE is also closed under polynomial-time reduction and/or under log-space reduction.

Savitch's theorem implies that NPSPACE is equal to PSPACE, and so it is closed under polynomial time reductions.


Time complexity of $\sim c \cdot n^3$ with a computer which is 10 times faster I am trying to solve the following question

  There's an algorithm with time complexity $\sim c \cdot n^3$. Suppose
  there's another computer which is 10 times faster. How much bigger can
  our $n$ be to be solved in the same time?

My answer so far is $\sqrt[3]{10}$.

$n^3$ can be 10 times bigger, so I have to multiply N with $\sqrt[3]{10}$. Is my conclusion correct or is there a fault in my reasoning?

You've correctly reasoned that the additional speed doesn't change the $n^3$ part of the tilde expression. The only component left for it to effect then is $c$.

Let $c_1$ be the constant of the first computer and $c_2$ the constant of the second. If the second computer is 10x faster, then $c_2 = c_1/10.$ Now, all you need to do is solve the following equation:

$$c_1 \cdot n^3 = \frac{c_1 \cdot n'^3}{10},$$

which gives the same answer you came up with!


Compression algorithm for statistical data with a desired outcome size I did some basic research on regular lossy and lossless compression algorithms but somehow I couldn't really figure the right direction for the information I need.
My basic problem is that I would like to compress a series of numbers with an unknown number of data points (can be 10, can also be a 1000). The numbers themselves are domain-specific in a way that I know what they mean. For example I have LAT/LONG from GPS-Data but also Degrees from a Gyroscope or Acceleration in G's from an Accelerometer.
What I am doing is basically whenever something changes for example in acceleration I store the value. At the end what I want to do is to compress this series of data by providing the maximum size of the compressed data which should then affect not the data itself but its actual accuracy. For example acceleration would always result in a simple diagram at the end with more or less accuracy depending on the provided output size.
Does something like that exists? Could you maybe throw me into the right direction?
The basic idea is to become independent from time (like store the accel value every XX seconds) and instead store all data changes. Then being able to set the "resolution" by time say if I then get this compressed data only every 10 minutes the data is less accurate (but still close enough) to then saying I get the compressed data every 1 minute.
I hope its understandable if not please let me know so I can try to explain the issue a little bit further.

Does something like that exists? Could you maybe throw me into the right direction?

The basic idea is to become independent from time (like store the accel value every XX seconds) and instead store all data changes. Then being able to set the "resolution" by time say if I then get this compressed data only every 10 minutes the data is less accurate (but still close enough) to then saying I get the compressed data every 1 minute.

When talking about signals that change over time with a fixed sample rate your question actually has a proper mathematical answer. It can be beaten for very specific kinds of signals that have patterns in them you already know beforehand, but if it's a generalized signal over time without any further information, it's essentially as good as it gets.
And that answer is found in the Fourier transform. By first transforming your data from the time domain into the frequency domain you get all the power you desire. You become time-independent, and you can drop the coefficients that are above frequencies you care about. You can also downsample, using more/less bits for coefficients that are important/not important.


Does big-Oh impose an ordered partition on the set of the "usual" functions? The example in this answer proves the fact familiar to CS students - that the "big-O" is not a total order. However, most algorithm running times analyzed using big-Oh notation are not expressed in piecewise form like this example. In fact, most algorithms I am familiar with have a running time expressed in terms of polynomials, exponentiations and logs.
Consider the recursively defined class of functions which includes $f(n) = c$ for any constant $c$, $f(n) = n$, and any functions of the form $f + g, f \cdot g, \log(f), \exp(f)$ where $f,g$ are in the class. Does $O$ impose an ordered partition on this class of functions? The functions with the same big-$O$ growth is in the same part.
Here are my thoughts:
Note that specifying $f \cdot g$ is actually redundant, since $f \cdot g = \exp(\log(f) + \log(g))$. Since the functions are inductively defined, perhaps there is an inductive proof.

This was shown by Hardy in his monograph Orders of Infinity.


What are all the differences between the Gibbs phenomenon artefects and JPEG artefacts? I thought the Gibbs phenomenom is the result of Fourier analysis estimation (but was it Fourier Series estimation or can it also be Fourier Transform estimation?)

JPEG uses the Discrete cosines Transform. A DCT is similar to a Fourier transform in the sense that it produces a kind of spatial frequency spectrum.

But what are the differences between the Gibbs phenomenom artefacts from Fourier and the artefacts from the Discrete Cosine?

There are three kinds of JPEG artifacts.  The first and (arguably) most important one is described in Yuval's answer: To a first order the problem is that under high compression all the high frequency information is discarded, and the lowest frequency information remaining is the average color of each 8x8 square.  When you take the inverse but leave out the high frequency information, the result is a square of a single color.  A decoder can't perform any low-pass filtering to remove the blocky effect because that would cause significant error in the case that you used a high-quality setting to encode.

The second artifact is exactly the Gibbs phenomenon.  Fine detail in the image will get "halos" if highly compressed.  For example, here is a 64x64 image with a single dot at pixel 35,35:

Here's the same image saved by GIMP as a Jpeg with low quality (25%):

There is a halo around the pixel in the 8x8 block the pixel is in.  (To make it easier to see, here is an image of that block scaled up by a factor of 8:

This effect is called ringing.  (In audio processing it really produces a ringing noise.)  This occurs because high levels of compression are chopping out the highest frequencies, which leaves ripples at the highest remaining frequency.  (I.e., it's the Gibbs phenomenon.)

The third artifact is the inverse of the Gibbs phenomenon.  The Gibbs phenom is because the multiplication of the brick-wall filter in the frequency domain is equivalent to convolution with the sinc function in the time domain.  The inverse problem is using a box-car filter for downsampling in the time domain leads to a sinc function in the frequency domain, and thus a large amount of high-frequency noise gets aliased into the resulting downsampled image.  This is essentially what JPEG is doing when it breaks the image into 8x8 blocks.  The lowest-frequency component of each 8x8 block is the average (box-car) of the pixel values in that 8x8 block, so actually contains significant high-frequency aliasing.  For example, consider the following image.  (It is 64x64 with a horizontal stripe each third pixel.  So has significant amount of high frequency information.

Now if I encode with jpeg at very low quality I get this:

The high frequency information from the original image is not being completely filtered by the box-car averaging, and thus gets aliased into a lower-frequency error in the image.


Asymptotic Time Analysis for BFS Tree Suppose I want to broadcast from my root to all the nodes in a BFS tree. What is the time complexity of this process? I know that it is suppose to be proportional to the depth of the tree, like O(Depth). A more formal way of saying this could be O(Diameter) or maybe O(Radius of the Root) if you want to be more specific.

However, these parameters do not provide any insight. O(Depth) or O(Diameter) could be O(n) if the tree were a line. Since BFS is not guaranteeing a balanced tree or a binary tree or whatever, it does not give any topological clue to me.

Should I say O(n) then? Or should I say O(Depth) to give a more precise answer?

You can say whatever you want as long as it is accurate.  Both $O(n)$ and $O(\text{Depth})$ are accurate, so you can say either one.  $O(\text{Depth})$ is more descriptive, since $\text{Depth} \le n$ always holds.

I don't know why you don't think it provides any insight; I think it does provide some potentially useful information.


Alternatives to multiplication/division/modulo for encoding choices? The obvious way to encode, with minimum entropy, choosing s out of n (equiprobable) choices when x is already encoded is to identify s with a number [0, n) and set x = n * x + s, decoded with s = x % n, x = x / n.

Is this optimal if the only constraint is that the encoded result must be a bitstring? Would *+/% still be the choice if they were not available as instructions?

I know arithmetic coding (and ANS) exists, but it also can't avoid big integer arithmetic without giving up some entropy.

You can implement ANS using only additions, masks and shifts. Take a look at Finite State Entropy (FSE), it's a performance-focused version of ANS with accurate compression.


Segmenting an English string with no spaces using dynamic programming Suppose you have a function quality(x) that returns the quality of a sequence of letters x. Given a string such as "howareyoutoday," what is the most efficient way to determine that the segmentation is "how are you today" (i.e. quality(how)+quality(are)+quality(you)+quality(today) is the maximum quality possible)?

I was thinking that we could have something like the following:

A[0] = h, A[1] = o, ..., A[n] = y
Q[0] = quality(A[0]), Q[1] = quality(A[0]A[1]), ..., Q[n] = quality(A[0]...A[n])

Now to determine the segmentation, we find max{Q[0], .., Q[n]} which will return some Q[i] (the first space is after this). Then, we find max{Q[i+1], .. Q[n]} which returns another Q[i] (second space is after this), etc. until max returns Q[n].

I have some questions though: is this method even correct, and does it use dynamic programming? It seems to me that it does, since we build the initial Q with subproblems to the original problem. Also, is this an optimal solution? To my understanding, the worst case would be O(n^2), which would be when max returns Q[0], then Q[1], then Q[2], etc.

I'm assuming your quality function measures something similar to the likelihood of the string being a word. The problem with your algorithm is that it makes a hard decision about where the first space should go before considering where the other spaces go. If you make a suboptimal decision for where the first space goes it will mess you up later on.

The dynamic programming algorithm for this problem is called the Viterbi algorithm. https://en.wikipedia.org/wiki/Viterbi_algorithm You have to keep a table of the highest quality segmentations seen so far as you process the string from left to right. When the algorithm finishes you will be left with a ranked list of the highest quality segmentations.


Is this problem NP-hard? select k sets from a collection of sets such that each selected set has an empty intersection with the non selected ones select k sets from a collection of sets such that each selected set has an empty intersection with the non selected ones

Your problem can be solved in polynomial time.  Form an undirected graph where each set is a vertex, and there is an edge between two sets if they have a non-empty intersection.  Decompose it into connected components, and let the sizes of the connected components be $n_1,\dots,n_t$.  Then there exists a solution to your problem if and only if there is a subset of the integers $n_1,\dots,n_t$ that sums to $k$.  This is the unary subset-sum problem, and it has a polynomial-time algorithm (via dynamic programming).  Consequently, your problem can be solved in polynomial time, too.

In contrast, set packing (does there exist a way to select k sets so that each selected set has an empty intersection with all the other selected ones?) is NP-hard.


Correctness of Strongly Connected Components algorithm for a directed graph I have been reading up on algorithm for finding the strongly connected components in a directed graph $G=(V,E)$. It considers two DFS search and the second step is transposing the original graph $G^T$.

The algorithm is the following :

Execute DFS on $G$ (starting at an arbitrary starting vertex), keeping track of the ﬁnishing times of all vertices.
Compute the transpose,
Execute DFS on $G^T$, starting at the vertex with the latest ﬁnishing time, forming a tree rooted at that vertex. Once a tree is completed, move on to the unvisited vertex with the next latest ﬁnishing time and form another tree using DFS and repeat until all the vertices in $G^T$ are visited.
Output the vertices in each tree formed by the second DFS as a separate strongly connected component.

My question is :

What is the intuition behind this middle step of computing a transpose?

Transposing the adjecency matrix $A$ does

$\qquad A[i,j] = 1 \iff A^T[j,i] = 1$.

In terms of graphs, that means

$\qquad u \to_G v \iff v \to_{G^T} u$.

In other words, transposing reverses the direction of all edges. Note that $G^T$ has the same strong components as $G$.

The algorithm you are looking at is Kosaraju's algorithm. Be carful with your notion of "finishing time": it's not the time the node is visited, but when the search has traversed the subgraph reachable from it. Wikipedia proposes to use a stack to manage this, which I think is a good idea.

Why is it correct to use $G^T$, intuitively? Assume $x$ is the first node of its strong component visited by the DFS.

The DFS on $G$ traverses the whole strong component of $x$ after reaching $x$, plus some others via edges that leave the component.
Since we use a stack order for remembering the order of nodes, $x$ is also the first node of its strong component visited (as starting node, even) in the second phase.
Since $G$ and $G^T$ have the same strong components, all nodes in the strong component of $x$ are visited when searching $G^T$ from $x$. Those edges leaving the component in the first phase point in the wrong direction in $G^T$ and are thus not followed. All edges leaving the component of $x$ in $G^T$ have already been removed because of the stack order.


Proving the singleton language {x} is regular for all x ∈ Σ* So I'm aware that the singleton language is in fact regular for all x ∈ Σ*, but I do not understand why it is. A formal proof would help, but also getting some intuition as to why it is regular would also be appreciated! As of now I'm just aware of it as a property, but I don't have a good grasp on why it is regular.

$\Sigma^*$ is a set of finite strings. There are infinitely many of them, but each one is finite – just like there are infinitely many natural numbers but each one of them is finite.

So, for any $x\in\Sigma^*$, $\{x\}$ is a finite language (it contains one string) of finite strings (because everything in $\Sigma^*$ is finite), so it's regular.


How is Hypergraph Isomorphism (HI) reduced to Graph Isomorphism (GI) in polynomial time? This question states that the problem of Hyper-graph Isomorphism is equivalent to Graph isomorphism. I have not been able to find a description of the reduction so I am wondering how that might work and what is its complexity. If I understand the post in the link correctly, the reduction has to be polynomial in order for the Hyper-graph isomorphism solution to inherit the same complexity as the Graph-isomorphism problem. Is the reduction only valid for a special case of the Hypergraph isomorphism problem or in general?

A description is given in the first paragraph of [1], where HI stands for Hypergraph Isomorphism and GI for Graph Isomorphism:

Given a pair of hypergraphs $X=(V,E)$ and $X'=(V',E')$ as instance for HI, the reduced instance of GI consists of two corresponding bipartite graphs $Y$ and $Y'$ defined as follows. The graph $Y$ has vertex set $V \uplus E$ and edge set $E(Y) = \{\{v,e\} \mid v \in V, e \in E, v \in e\}$, and $Y'$ is defined similarly. Here, $C \uplus D$ denotes the disjoint union of the sets $C$ and $D$. It is easy to verify that $Y \simeq Y'$ if and only if $X \simeq X'$ assuming that $V$ can be mapped only to $V'$ and $E$ can be mapped only to $E'$. This latter condition is easy to enforce.

The other direction is trivial as every graph is also a hypergraph.

[1] Arvind, Vikraman, Bireswar Das, Johannes Köbler, and Seinosuke Toda. "Colored hypergraph isomorphism is fixed parameter tractable." Algorithmica 71, no. 1 (2015): 120-138.


On graph isomorphism for weighted graphs Is there a $O(n^2)$ algorithm to resolve isomorphism between two weighted $n$-vertex graphs? This is a much easier problem than graph isomorphism.

Basically take an real edge weight set $\{w_1,\dots,w_s\}$

All weights on the graph edges are from this set.

This on contrary appears to be a problem of greater difficulty than graph isomorphism. If you had a polynomial time solution to this problem,you can reduce graph isomorphism to it by keeping each edge weight say equal to some constant $c$. Also graph isomorphism is not known to have a polynomial time solution. It is a still an open question.


What is the name of a rooted tree whose nodes may have edges to their descendants? A tree is a special kind a graph.

However, I came across a data structure which is a like a rooted tree, but where nodes are authorized to have direct links to any of their descendants. Shortcuts if you will.

This is not a tree anymore.

This is a specialized DAG that has more restriction. That is, it has a single root (or source)

Does this type of graph have a name?

CLARIFICATION:

By 'tree', I'm referring to the tree data structure, not a tree in graph theory. It seems crazy to me that such related objects have the same name even though they don't mean the same thing.
The tree data structure is always rooted but there are rooted DAG that are not trees.

{1→2, 2→3, 1→3, 4→2} doesn't qualify because 4→2 is an edge toward an ancestor, not a descendant.
{1→2, 1→3, 2→4, 3→4} doesn't qualify.

{1→2, 2→3, 1→3} and {1→2, 1→3, 2→4, 3→5, 3→6, 1→4, 1→6} both qualify.

I'm not aware of any standard term. The graphs that you describe are subgraphs of the transitive closure of a tree, if that's of any help to you, but one wouldn't want to use that phrase twenty times in a paper.

But... as Pål GD alludes to in a comment, every DAG on $n$ vertices is a subgraph of the transitive closure of the $n$-vertex directed path. So this answer is a bit of a fail, really.


1 bit register with data flip flop doesn't store bit? A 1-bit register:

  Credit:
  Elements of Computing Systems
  by Noam Nisan and Shimon Schocken
  ISBN-13: 978-0262640688

I know that the data flip flop outputs the input at the previous time step.

Based on this, I created this table (not sure if correct):

Note: For the Mux, 1 is for in and 0 is for DFF output.

$$
\begin{array}{|c|c|c|c|}
\hline
\text{In} & \text{DFF In} & \text{Load} & \text{Out} \\ \hline
1 & 1 & 1 & 0 \\ \hline
1 & 0 & 0 & 1 \\ \hline
1 & 1 & 0 & 0 \\ \hline
\end{array}
$$

The output is always alternating, no bit is being stored. It should constantly output 1 while load is 1 because that's what we initially stored.

I know that a register does actually store data, so something is wrong in my understanding of this.

Your table is incorrect. A MUX element selects one of its inputs based on a secondary input. In this case it's a binary mux and load is used to select the input.

If we say that load = 0 means it selects the DFF and load = 1 means that it selects in you shall see that when load = 0 the circuit repeatedly refreshes the previous value, and load = 1 will read the new value from in.


Algorithm with no closed-form exact complexity Does there exist an algorithm for which an exact complexity provably cannot be expressed in closed-form?

Here closed-form means a finite composition of addition, subtraction, product, division, factorial, power with any exponent, logarithm, trigonometric function, inverse trigonometric function, hyperbolic function, and inverse hyperbolic function. You may choose a subset of the above functions to allow in a closed-form expression; this makes the problem easier. However, the larger the set of allowed functions, the better, since this also answers the problem for the subsets.

Exact complexity is a function from the input-set to a real number. You may group the input by some property, and then study exact worst-case complexity instead (or exact best-case complexity).

Any computational model will do, as well as counting any resource (e.g. number of comparisons). To close off a trivial solution, a function without a closed-form expression cannot be a primitive operation of the computational model.

If yes, is there a simple example of such an algorithm?

The runtime of an algorithm that computes the Ackermann function can't be expressed using primitive recursive functions. All commonly known named functions (well, besides the Ackermann function) are primitive recursive as far as I know.


Power of nondeterministic type-1 min-heap automaton with both a heap and a stack I have asked a series of questions concerning capabilities of a certain class of exotic automata which I have called min-heap automata; the original question, and links to others, can be found here.

Two of my last questions seem to have been quickly dispatched; one completely, and the other mostly (I have edited it to make it more viable). In either event, I actually had one other question I meant to ask, and would be interested to lay this subject to rest for good and all. So here it is:

  A two-stack PDA can simulate a Turing machine. A $k$-heap nondeterministic type-1 min-heap automaton cannot (it seems; see the linked question). What about a $k$-tape nondeterministic type-1 min-heap automaton augmented with a stack (similar to that of a PDA)? Can it simulate a Turing machine? If not, does an augmented $(k+1)$-heap nondeterministic type-1 min-heap automaton accept a class of languages which is a proper superset of languages accepted by augmented automata with only $k$ heaps?

Thanks, and I promise this is the last of these questions.

A heap and a stack can both be used to implement a counter. 2 counters suffice to recognize $RE$. (See also)


Why $o(\log n)$ bits instead of $O(\log n)$ bits needed for succinct data structure? Succinct data structure = succinct representation of data + bits for indexing. Link

Let $S$ be  subset of  of $\{1,2,\ldots,n\}$ then $\lceil \log (2^n) \rceil + o(\log n )$ bits are needed in succinct representation. The $o(\log n)$ bits needed for the indexing of the succinct data structure. I have a doubt, why $o(\log n)$ not $O(\log n)$ bits? Where $O(\log n)$ do not play any role when talking about conventional representation of data.

Note that $\lceil \log(2^n) \rceil = n$.

An algorithm that uses $n$ bits to represent the set would be fine (it would count as a succinct data structure).  An algorithm that uses $n + 2 \sqrt{n}$ bits would also be fine.

An algorithm that uses $2n$ bits to represent the set would not be fine (it would not count as a succinct data structure).  Similarly, an algorithm that uses $1.01n$ bits would not be fine.

This is just what the definition says.  You could imagine some other definition, but that's what the standard definition of "succinct data structure" is saying.  It is saying that you can use a little bit more space than required by the information-theoretic lower bound, but not too much -- not a multiplicative factor.


Is there a sorting algorithm of order $n + k \log{k}$? I'm given an integer vector which is said to contain many duplicate values (total of k distinct integers), for example

[1, 4, 2, 5, 5, 3, 4, 2, 2, 5]
(n = 10, k = 5)

and am asked to find a sorting algorithm that averages $O(n + k\log{k})$. I've concluded that partial quicksort (or quickselsort) might achieve this, but doesn't seem to utilise that the vector contains duplicates. Am i missing some basic algorithms here?

The short answer is no, in the worst-case comparison based algorithms, for reasons stated here.

Using a counting technique will at least take $O(n \log n)$ worst case and $O(n \log k)$ if you use a BST. Here I'll give a variant of quick-sort which also achieves $O(n \log k)$ With a slight modification and a more careful analysis of quick-sort. We will change the "pivot" of quick-sort to never put duplicate elements in separate sub-problem. The partition procedure is as follows:

partition(list A of size n):
  x = SELECT(A, n/2)

  left = list of all elements less than x
  right = list of all elements greater than x
  center = list of all elements equal to x

  return (left, center, right)

Then the overall quick-sort looks like this:

quick-sort(list A of size n):
  if all elements in A are the same:
    return A
  left, center, right = partition(A)
  quick-sort(left)
  quick-sort(right)
  return concat(left, center, right)

The important thing here is the base case, when we only have one unique element in the list, just return the list. This will ensure that we have exactly $k$ leaf nodes in our recursion tree. The recurrence at face-value is:

$$T(n) \leq \max_{i,j} \{T(n - i) + T(n - i - j)\} + O(n)$$

Obviously with some constraints on $i$ and $j$, but that's the idea. Another thing to note is that via SELECT we ensure that center contains all the median elements, this would imply that we only recurse on two sub problems of size less than $n/2$, leading us to:

$$T(n) \leq \max_{l,r} \{T(\tfrac{n}{2} - l) + T(\tfrac{n}{2} - r)\} + O(n)$$

Where $l$ would be the overlap of the median on the left side and $r$ would be overlap of median on the right side. Note that $r + l$ is the number of elements equal to the median. With this we see a clear upper bound of $O(n \log n)$. However, when we include the base cases this becomes better. If we assume that each unique element is repeated $c = n/k = n^*/k$ times (distributed evenly) then we can get the recurrence:

$$T(n) \leq \begin{cases}
1 & n \leq n^*/k\\
T(\tfrac{n}{2} - n^*/2k) + T(\tfrac{n}{2} - n^*/2k) + O(n) & \text{otherwise}
\end{cases}$$

If we do recursion tree analysis on this we can see it is $O(n \log k)$.

We could also take advantage of the fact that we do not do $n$ work at each level of recurrence, but rather at level 0 we do $O(n)$, at level 1 we do $O(n - n/k)$, at level 2 we do $O(n - 3n/k)$, at level 3 we do $O(n - 7n/k)$ and so on. Without out our assumption the analysis becomes more tricky, and we would need to do average case analysis. However, I would claim that this assumption is worst case. Intuitively if this assumption did not hold, then we have fewer repetitions for some element $x_i$, but more repetitions for some element $x_j$. Thus, making $x_j$ more likely to be in one of the center's without going too deep in the recursion tree. This would reduce the amount of work on the remaining subproblem(s)
more by removing more than $n/k$ elements from the list.


Independent set poly reducible to Strongly independent set? A strongly independent set of a graph $G'$ is a subset $S$ of vertices such that the distance in $G'$ between every two distinct vertices in $S$ is larger than $2$.

It is possible to reduce an instance $\langle G, k\rangle$ of the decision version of independent set to an instance $\langle G', k\rangle$ of the decision version of strongly interdependent set by (1) replacing each edge $e=(u,v)$ of $G$ with two edges $(u, w_e)$ and $(w_e, v)$, where $w_e$ is a new vertex; and (2) connecting all the vertices $w_e$ with a clique.

In the newly created Graph $G'$, why does adding a middle node prevent us from choosing that node? Basically, how does the reduction step help us?

Solution Notes: http://www.cse.iitd.ernet.in/~amitk/SemI-2015/tut11.pdf

Assume that the integer $k$ of the (decision version of the) independent set instance $G$ you are reducing from is larger than $1$ (the case $k \le 1$ is trivial).
Let $G'$ be the graph of the corresponding instance of strongly independent set.

As it is written in your solution notes, all the additional vertices are connected to one another with a clique. If you select any of them, say $w_e$, then you cannot select any other vertex $v$ in $G'$ since the distance in $G'$ between $v$ and $w_e$ is at most $2$. This implies that the size of a maximum strongly independent set of $G'$ is $1$. Therefore, if there is a strongly independent set of $G'$ of size $k$, it must not include any vertex $w_e$.

The correctness of the reduction is then easy to see:

If $S$ is an independent set for $G$, then $S$ is also a strongly independent set for $G'$ since all pairs vertices in $S$ are at a distance of at least $2$ in $G$ and hence they are at distance of at least $4$ in $G'$.
If $S$ is a strongly independent set for $G'$ with $|S| \ge k$, then $S$ cannot include any vertex $w_e$, and is therefore a subset of the vertices of $G$. The distance between any two distinct vertices in $S$ is larger than $2$ in $G'$, and hence it is larger than $1$ in $G$.


Proof of algorithm correctness I am studying about algorithm correctness and have enctountered this problem.
function add(y,z)
comment Return y + z, where y,z are natural numbers
x :=0; c:=0; d:=1;
while(y>0)v(z>0)v(c>0) do
    a := y mod 2;
    b := z mod 2;
    if a XOR b XOR c then x := x+d;
    c:= (a AND b) v (b AND c) v (a AND c);
    d :=2d; y:= floor(y/2);
    z := floor(z/2);

The book that I'm reading says that loop invariant is $(y_j + z_j + c_j)d_j + x_j = y_0 + z_0$ and I honestly can't understand the conclusion. How do you come up with this? Why is this true?

In order to prove an algorithm correctness a loop invariant should include:

Initialization:It is true prior to the first iteration of the
loop.
Maintenance: If it is true before an iteration of the loop, it
remains true before the next iteration.
Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

Let's look at your invariant:
Initialization then is before entering the loop, so choose any number for $y$ or $z$ such that $y,z \in N$ (I'll use $n_1$ and $n_2$ respectively) then you will have that your property is satisfied since at this point: $d=1$, $c=0$ and $x=0$.
So your invariant will be: $(n_1 + n_2 + 0)*1 + 0 = n_1 + n_2$.
Maintenance: This one you can prove it with induction. Here a complete example with induction. Is slightly more complicated, but you can see in your case that it holds, since at every iteration you "divide" $y$ and $z$ by 2, but $d$ duplicates every time, therefore balancing the division. The $c$ is there in case of odd numbers.
Loop termination: at this point according to the while, nor $y$ nor $z$ nor $c$ can be higher than $0$, but at the same time they are all natural numbers, therefore they are all $0$. Now we have that $x = y+z$ and if you plug it into the invariant you have: $(0 + 0 + 0)*d + x = y_0 +z_0 \Rightarrow y + z = y_0 + z_0$