Fast, stable, almost in-place radix and merge sorts I've developed LSD radix sort algorithm that is

stable,
about as fast as the classic LSD radix sort,
require only $O(\sqrt{RN})$ extra space when we sort into R buckets.

The same technique also allows to perform stable, efficient, almost in-place merge & quick sorts; as well as stable almost inplace merge/partition operations; and also applicable to some other list processing algorithms.

I describe it in my answer to this question. I believe that the proposed modifications to classic algorithms has important practical value. Other known techniques for (almost) in-place stable sort:

WikiSort and GrailSort that have even smaller memory requirements but seems to perform more data moves than the simple mergesort
highly theoretical in-place stable sorts that doesn't even pretend to have practical usefulness

EDIT: I've found this technique described 4 years ago in section 3.2.3 of paper A comprehensive study of main-memory partitioning and its application to large-scale comparison- and radix-sort

Here is description of the proposed algorithm.

The algorithm is further improvement of the one proposed in Parallel radix sort with virtual memory and write-combining. They implemented fastest parallel LSD radix sort that avoids the counting pass by using "indefinite" space for output buckets. Each bucket allocs space on-demand using hardware paged memory support. A comprehensive study of main-memory partitioning and its application to large-scale comparison- and radix-sort took this idea further, proposing software implementation of the paged memory, that allows to perform stable radix/merge/quick sort using only $O(\sqrt{NR})$ extra memory.

Basic operations of radix, merge and quick sort have something in common:

radix sort pass: read from 1 stream and write into R streams
merge: read from R streams and write into 1 stream
partition: read from 1 stream and write into R streams

Each of these operations process its input and output streams in strictly sequential manner. On every step, input plus output streams contain exactly N elements total - we neither produce nor consume any data items, but only move them between streams. This allows to implement in-place list-processing versions of these algorithms that don't move any data at all and only modify next list pointers. And this brings us to idea that we can perform these operations on array in-place, allocating only a little more space to perform home-made memory management of the array space.

To accomplish that, we split input and output streams into fixed-size pages and maintain list of pages in the each stream. When an input stream consumed all data on a page - this page is moved into the freepage list. When output stream needs more space - it allocs a page from the freepage list. Each stream may have incomplete first and last page, so in the worst case we may have 2*R*PAGESIZE unused items at any given moment - it's the extra space we need to alloc in addition to the page management structures. It's easy to find that the optimal PAGESIZE is $O(\sqrt{N/R})$ and the entire extra memory usage is $O(\sqrt{NR})$.

A few concrete examples:

2-way sorting of 1 million 8-byte items, i.e. 8 MB: we need 4 extra pages and can fit page number into 16 bits. 2 KB pages are optimal, and we need 16 KB of extra space total.
256-way sorting of the same array: we need 512 extra pages, while page number still fits into 16 bits. 256 byte pages are optimal, and we need 192 KB of extra space total. It's 2% of 8 MB, which is the largest proportion among these examples.
2-way sorting of 128 millions 8-byte items, i.e. 1 GB: we need 4 extra pages, and page number still fits into 16 bits. 32 KB pages are optimal, and we need 192 KB of extra space total. You may note that the two later cases has the same R*N and hence the same memory requirements.
256-way sorting of the same array: we need 512 extra pages, and page number finally requires full 32 bits. 4 KB pages are optimal, and we need 3 MB of extra space total.

TL;DR: sorting more than 1 MB of data usually requires less than 10% extra space, and the proportion reduces as datasize grows.

Algorithm: utility functions

Let's define data structures for our memory manager:

// Number of items per page
const int PAGESIZE = 1024; // just for example

const int PAGE_COUNT = N/PAGESIZE;

// next_page[page] is either -1 (meaning EOF)
// or index of the next page in the same stream
int next_page[PAGE_COUNT];

// Input and output streams
StreamDescriptor in_streams[R];
StreamDescriptor out_streams[R];

struct StreamDescriptor
{
    int first_page;
    int first_element;  // index of first element on the first page
    int last_page;
    int last_element;  // index of last element on the last page + 1
    // all pages between the first and last ones are fully populated
};

Here is the "memory manager" which allows to alloc new pages for output streams and release pages consumed from input streams:

// head of the available pages LIFO queue
int first_available_page;

int AllocPage()
{
    int page = first_available_page;
    assert(page != -1);
    first_available_page = next_page[first_available_page];
    return page;
}

void ReleasePage(int page)
{
    next_page[page] = first_available_page;
    first_available_page = page;
}

// Main data storage (holding N elements) provided by the caller
T* MainArray;

// Extra memory allocated for temporary data storage
T* ExtraPages;

// Return address of given memory page
T* Page (int page)
{
    if (page < PAGE_COUNT)
        return MainArray + PAGESIZE*page;
    else
        return ExtraPages + PAGESIZE*(page - PAGE_COUNT);
}

And these operations read item from given input stream and write item into given output stream:

T get_next_item (int input_stream)
{
    StreamDescriptor s = in_streams[input_stream];
    if (s.first_page == s.last_page  &&  s.first_element == s.last_element)
    {
        ReleasePage(s.first_page);
        return EOF;
    }
    if (s.first_element == PAGESIZE)
    {
        int next = next_page[s.first_page];
        ReleasePage(s.first_page);
        if (next == -1)
            return EOF;
        s.first_page = next;
        s.first_element = 0;
    }
    return Page(s.first_page)[s.first_element++];
}

void put_item (int output_stream, T item)
{
    StreamDescriptor s = out_streams[output_stream];
    if (s.last_element == PAGESIZE)
    {
        int next = AllocPage();
        next_page[s.last_page] = next;
        s.last_page = next;
        s.last_element = 0;
    }
    Page(s.last_page)[s.last_element++] = item;
}

Algorithm: LSD radix sort

Initialization depends on the amount of input and output streams. For example, prior to first pass of LSD sort we do the following:

void LsdRadixSort (T* data_to_sort, int N)
{
    MainArray = data_to_sort;
    ExtraPages = new T[2*R*PAGESIZE];

    // Setup first input stream as containing the entire MainArray contents
    in_streams[0].first_page = 0;
    in_streams[0].first_element = 0;
    in_streams[0].last_page = PAGE_COUNT-1;
    in_streams[0].last_element = N % PAGESIZE;

    for (int i=0; i<PAGE_COUNT-1; i++)
        next_page[i] = i+1;
    next_page[PAGE_COUNT-1] = -1;

    // Alloc one initial page for each outstream
    for (int i=0; i<R; i++)
    {
        int page = PAGE_COUNT+i;
        out_streams[i].first_page = page;
        out_streams[i].first_element = 0;
        out_streams[i].last_page = page;
        out_streams[i].last_element = 0;
    }

    first_available_page = -1;

    ...
}

Prior to second and following passes of LSD sort, we perform this:

// Make old out_streams new in_streams
for (int i=0; i<R; i++)
{
    in_streams[i] = out_streams[i];
}

cur_input_stream = 0;

// Alloc one initial page for each outstream
for (int i=0; i<R; i++)
{
    int page = AllocPage();
    out_streams[i].first_page = page;
    out_streams[i].first_element = 0;
    out_streams[i].last_page = page;
    out_streams[i].last_element = 0;
}

In the first pass, data should be read with get_next_item(0) calls until it returns EOF. On the second and following passes, data should be read using the following procedure, also up to EOF:

// Enumerate contents of all input streams in order
T get_next_item_2nd()
{
    if (cur_input_stream >= R)
        return EOF;

    T item = get_next_item(cur_input_stream);
    if (item==EOF)
    {
        ++cur_input_stream;
        return get_next_item_2nd();
    }

    return item;
}

One pass of LSD radix sort:

void one_pass(int pass)
{
    for(;;)
    {
        T item  =  pass==1? get_next_item(0) : get_next_item_2nd();
        if (item==EOF)
            break;
        int bucket = calc_bucket(item,pass);
        put_item(bucket,item);
    }
}

Algorithm: reordering data

Once sorting is finished, the caller may either read data in sorted order using the same get_next_item_2nd() procedure, or data may be placed in proper order in original array.

Reordering requires two steps:

compact data into single stream, removing "holes"
move each page of the compacted stream into right place

For the first step, we can just append to the first stream contents of remaining streams:

// Make old out_streams new in_streams (except for the first one)
for (int i=1; i<R; i++)
{
    in_streams[i] = out_streams[i];
}

cur_input_stream = 1;

// Move data from all streams into the first one
for(;;)
{
    T item = get_next_item_2nd();
    if (item==EOF)
        break;
    put_item(0,item);
}

For the second step, we start with enumerating pages in the single stream remaining, and marking all other (i.e. free) pages with -1:

// final_place and next_page are the same array used in different roles
int* const final_place = next_page;

int page_i = out_streams[0].first_page;

for (int i=0; i<PAGE_COUNT; i++)
{
    int next = next_page[page_i];
    final_place[page_i] = i;
    page_i = next;
}

while (first_available_page != -1)
{
    int next = next_page[first_available_page];
    final_place[first_available_page] = -1;
    first_available_page = next;
}

From this point on, final_place[pg] is a page where current contents of page pg should be finally placed, or -1 for a page whose contents is garbage and so can be overwritten. Now all that remains is the classic "move them all to their final places" algorithm:

for (int i=0; i<PAGE_COUNT+2*R; i++)
{
    int page = i;

    while (final_place[page] != -1  &&  final_place[page] != page)
    {
        mem_exchange( Page(page), Page(final_place[page]), PAGESIZE*sizeof(T));
        std::swap( final_place[page], final_place[final_place[page]]);
    }
}


Cycles in hardness of ST-CON for the class NL It seems to me that the problem of $s$, $t$ connectivity in a DAG should still be NL-Complete.

I am aware that ST-CON without the DAG restriction is complete for NL, so obviously the DAG restriction is still in NL, but I believe hardness follows as well:

For a turing machine that runs in space $s(n)$, its configuration graph is of size $2^{O(s(n))}$. Furthermore, this implies the time for an NL machine to solve any problem, if it halts at all, is also $2^{O(s(n))}$. Then you can blow up the configuration graph by including a counter for any possible time step a configuration is reached, resulting in a graph of size $2^{O(s(n))} \cdot 2^{O(s(n))} = 2^{O(s(n))}$. At this point the typical reduction to ST-CON can be used since the graph is the same size.

If this is true, then I do not understand why the result SL = L did not follow trivially from the formulation of SL. Namely, an undirected acyclic graph is a tree, and a simple maze algorithm can determine $s$, $t$ connectivity in log-space (and linear time!).

Another strange implication would be that the cyclic or non-cyclic versions of $s$, $t$ connectivity on directed or undirected graphs are equivalent for log-space computation. This implies a simple algorithm like the tree-based one for $s$, $t$ connectivity on a generic undirected graph.

It turns out st-connectivity on a general digraph is log-space mapping reducible to st-connectivity on a DAG. Here is the reduction:

Given a directed graph $G$ of size $n$ and two vertices $s$ and $t$, first create a graph $G'$ by making $n$ copies of every vertex $u$ in $G$ as the new vertex $(u, i)$ in $G'$, where $i$ goes from $1$ to $n$ for the respective copies. Then, represent each edge $(u, v)$ in $G'$ by the transition $(u, i) \mapsto (v, i+1)$. Since any path from $s$ to $t$ is of length at most $n$, it then follows that a path from $s$ to $t$ exists in $G$ if and only if it exists in $G'$. Furthermore, since $i$ is always increasing in $(u, i)$, it is clear $G'$ is a DAG. Finally, the mapping can be computed in logarithmic space.

However, the approach does not work for undirected graphs, because cycles can occur in the layering technique. So although st-connectivity is easy on a tree, as described by my algorithm in the comments, undirected st-connectivity is not (directly) reducible to st-connectivity on a tree.

Therefore SL=L was not established until Reingold showed st-connectivity on an undirected graph is indeed solvable in log-space.


Trying to understand the question(well spaced points ?) better Let us have a sorted array of n numbers and we would like to find a well spaced set of C of them, More specifically, we want to get a subset $ S\subset T$ with |S| = C and with $min_{i,j  \in S,i\ne j} |i-j|$ as large as possible. Come up an algorithm for fining the best S.

What is the correct output if the sorted array as 1, 2, 3, 4 ,5 ,6 and c is 3. What about if the sorted array as 1, 10, 11, 12, 23, 24, 25 and c is 3 ?
also appreciated any hints to approached this question if you clearly understand what the question is asking.

What is the correct output if the sorted array as 1, 2, 3, 4 ,5 ,6 and C is 3?

Let us try. How about (1,2,3)? Too closely together. We should push away 3. (1,2,6) looks more far apart. Hmm, (1,2) is not good. (1, 3, 6) is the best.

  What about if the sorted array as 1, 10, 11, 12, 23, 24, 25 and C is 3 ?

We should include the smallest and biggest numbers, 1 and 25. Then we should choose a number as close to the middle as possible. (1,12,25).

...

Let us analyze $\min_{i,j  \in S,i\ne j} |i-j|$. Suppose $S=\{a_1, a_2, \cdots, a_C\}$, where $a_k\le a_{k+1}$. Then
$$\min_{i,j  \in S,i\ne j} |i-j|=\min_{1\le k\lt C}|a_{k+1}-a_k|$$
since the difference between two non-adjacent numbers $a_k$ and $a_{k+t}$ must be greater than the difference between $a_k$ and $a_{k+1}$.

So the minimum difference among numbers in $S$ seems in "reverse proportion" to the difference between the adjacent or nearby numbers of the given array.

I will leave the above as a hint. Hopefully it is enough for you to figure out the rest.


What does "no value is acceptable" in Machine Learning hypothesis representation I am new to machine learning. I am reading the book, where I have:
– Most general hypothesis
< ? ? ? ? ? ? >
– Most specific hypothesis
< Ø Ø Ø Ø Ø Ø >

in
Sky AirTemp Humid Wind Water Forecast
< Sunny ? ? Strong ? Same>

I understand that for a learning instance, "?" means it can take on any value, so the outcome of the hypothesis would be 1, as long as the specific attribute is met.

I am confused about "Ø". The book says any value is unacceptable.

Does that mean, if a hypothesis is < ? ? ? ? ? Ø>, no matter what first 5 attributes are, since the last one is unacceptable, the outcome of the hypothesis will be 0?
If so, what is the difference between < ? ? ? ? ? Ø>, and < Ø Ø Ø Ø Ø Ø >?

Yes, that's right.  Those two hypotheses are equivalent, in that they assign the same classification to every possible instance.  Sometimes there are two different ways to represent the same thing.


Why do Alice and Bob get the same key even after modular reduction in Diffie-Hellman Cryptography? In this cryptography scheme, we take $g$ and $p$ (a large prime number). and taking the customary clients Alice and Bob who chose $a$ and $b$ secretly whereas $p$ and $g$ are known in public. I haven't mentioned the other requirements taken into consideration for selection of these parameters.

So here is how this works:

Alice calculates $A = (g^a)\mod n $.
Bob calculates $B = (g^b)\mod n$.
Alice sends $A$ to Bob who then computes $(A^b)\mod n$ to get the final key. Vice-versa happens when Bob sends $B$ to Alice.
The end resulting keys of both Bob and Alice have to be equal.

Now, my doubt is that how come $(((g^a)\mod n)^b)\mod n = (((g^b)\mod n)^a)\mod n $ holds true?

In general, we have that $a\cdot b \mod n = (a\mod n) \cdot (b\mod n) \mod n$ for any positive integers $a,b,n$. To see this, we write $a= k n +r_a$ and $b=ln+r_b$, where $r_a= a \mod n$ and $r_b = b\mod n$.
So, we get
\begin{align}
a\cdot b \mod n &= (kn +r_a) (ln+r_b) \mod n \\
&= kln^2 +knr_b + ln r_a + r_ar_b \mod n\\
&= n (kln +kr_b + lr_a) + r_ar_b \mod n\\
&= r_ar_b \mod n\\
&= (a\mod n) \cdot (b\mod n) \mod n
\end{align}

From this, it follows that $a^b \mod n = (a\mod n)^b \mod n$ for any positive $a,b,n$. Using this equality, we can 'move' exponents through modular reductions, from which your equality follows.


Is the Jacobian matrix calculation process correctly on this energy function? When I implemented the paper Dynamic Fusion published in 2015 CVPR, I came into the trouble with how to solve the energy function:
$$E(W_t, V, D_t, \mathcal{E}) = \text{Data}(W_t, V, D_t) + λ\text{Reg}(W_t, \mathcal{E})$$
Where:

Wt is a set of 4x4 transformation matrix at time t;
V is a set of 3D vertices from canonical model;
Dt is a depth map at time t;
ε is used to find Wt matrices;
Data is a point-to-plane error;
Reg is a smooth term which enforce the two adjacent transformation matrix W to be similar.

To simplify the question, I try to solve the Data term and throw away Reg term.
$$E(W_t, V, D_t, \mathcal{E}) = \text{Data}(W_t, V, D_t)$$
Here is the Data term:
\begin{align*}
r &= \text{Data}(W_t, V, D_t)= \sum_u n_u^{\intercal}\cdot (v_u-vl) \\
where,\text{v}_u &= W_t×\text{v}(u)  \\
\text{n}_u &= W_t×\text{n}(u)
\end{align*}
All the information but $W_t$ is known, use Gauss-Newton to solve the parameter:
$$\begin{gather*}
\underset{W_t}{\text{minimize}}\ r^2 \\
W_t^{(t+1)} = W_t^t - (J^\intercal J)^{-1}Jr
\end{gather*}$$
It seems to me that I need to calculate the Jacobian matrix $J$, so I expand r in matrix form:
$where\ W_t=$
\begin{bmatrix}
    1  & -\gamma & \beta & t_x \\
    \gamma & 1 & -\alpha & t_y \\
    -\beta & \alpha & 1 & t_z \\
    0 & 0 & 0 & 1
\end{bmatrix}
$v, n, vl$ are all 4x1 vector. (sorry, I don't know how to display matrix multiplication)
If I print all of the calculation, there are about 50 values containing $(\alpha,\beta,\gamma,t_x,t_y,t_z)$ to sum up for one Data term. My question is, can I directly do partial differential to the parameters $(\alpha,\beta,\gamma,t_x,t_y,t_z)$ of a $W_t$ matrix to get Jacobian matrix $J$?  It it correct to update $W_t$ by $W_t^{(t+1)} = W_t^t - (J^\intercal J)^{-1}Jr$?
I cannot believe this is a good approach because it is kind of messy, and maybe inefficient.
Please give me some advice how to solve this energy function, and I am curious why researchers only give energy function without explicit deviation on how to solve the function. Because energy function deviation is a common knowledge? If so, which course teach about it? I really want to take a course. Thanks.

That is not an equation to be solved; it is an objective function to be minimized.  They apparently describe how they optimize it in Section 3.3.3 of the paper.  I suggest trying to understand that section.


Lambda term satisfying two equations using Bohm Trees Hi I'm trying to solve this exercise but I can't find any material online, it's not an homework I actually have sort of a solution (it looks incomplete though), but from that I can't really understand much about how to tackle the problem. Anyway we're asked to find a term $\Delta$ such that:
$$
\left\{\begin{matrix}
\Delta(\lambda x y. x (y(\lambda u.yuy)x)x)=y_1
\\
\Delta(\lambda xy.x(y(\lambda u.yu(\lambda abc.cab))x)x) = y_2
\end{matrix}\right.$$

I looked at a similar exercise where the idea was to define $\Delta$ to be an abstraction of the type $\lambda x. x R_3$ where $R_3$ is the ROTATION operation on Bohm Trees (takes the leftmost child of a tree with k+1 subtrees and makes it the new root).

Could someone please explain me how to solve these type of problems? thanks

This task can be solved very well by observation and inserting simple functions.

First, $\Delta$ should obviously be a function applying its argument to at least two terms (because it's $\lambda x y.$). So let's set $\Delta = \lambda f.fXY$, which gives $$X(Y(\lambda u.YuY)X)X=y_1
\\
X(Y(\lambda u.Yu(\lambda abc.cab))X)X = y_2$$
Now we see that $Y$ is mostly applied to other terms that seem complex enough to solve this task for themselves, so why not just set $Y=I(=\lambda t.t)$?
This leads us to $$X(XI)X=y_1
\\
X(X(\lambda abc.cab))X = y_2$$
$X$ is now an abstraction of at least two variables, but we see that the second one (it's always $X$ in the first application) can probably be ignored. Setting $X=\lambda p q.Mp$: $$M(\lambda q.MI)=y_1
\\
M(\lambda q.M(\lambda abc.cab)) = y_2$$
The same ways we did with $\Delta$, we see that M takes an argument with at most three abstractions, so we make $M=\lambda f.(f P Q R)$. Doing several beta reductions, this yields $$PQRQR=y_1
\\
RPQQR = y_2$$
with the obvious solutions $P=\lambda a b c d.y_1$ and $R=\lambda a b c d.y_2$ and the free parameter $Q$.
Now finally, we can insert these terms back into $M$, $X$ and $\Delta$ to yield the solution $$\Delta=\lambda f.f(\lambda p q.p(\lambda a b c d.y_1)I(\lambda a b c d.y_2))I$$ (setting $Q=I$ for brevity's sake).
There could very well be a smaller solution, but I think the derivation process is the simplest you can get with this one.


How to check rapidly if an element is present in a large set of data I am trying to harvest scientific publications data from different online sources like Core, PMC, arXiv etc. From these sources I keep the metadata of the articles (title, authors, abstract etc.) and the fulltext (only from the sources that provide it).

However, I dont want to harvest the same article's data from different sources. That is, I want to create a mechanism that will tell if an article that I am trying to harvest is present in the dataset of the articles that I already harvested.

The first thing I've tried was to see if the article (which I want to harvest) has a DOI and search in the collection of metadatas (that I already harvested) for that that DOI. If it is found there then this article was already harvested. This approach, though, is very time expensive given that I should do a serial search in a collection of ~10 millions articles metadata (in XML format) and the time would increase much more for the articles that don't have a DOI and I will have to compare other metadatas (like title, authors and date of publication).

def core_pmc_sim(core_article):
    if core_article.doi is not None:      #if the core article has a doi
        for xml_file in listdir('path_of_the_metadata_files'):  #parse all PMC xml metadata files
            for event, elem in ET.iterparse('path_of_the_metadata_files'+xml_file): #iterate through every tag in the xml
                if (elem.tag == 'hasDOI'):
                    print(xml_file, elem.text, core_article.doi)
                    if elem.text == core_article.doi:  # if PMC doi is equal to the core doi then the articles are the same
                        return True
                elem.clear()
    return False

What is the most rapid and memory-efficient way to achieve this?

(Whould a bloom filter be a good approach for this problem?)

If you knew that every article had a DOI, you could just store a hashtable of the DOIs of the papers that you've already harvested.  Of course, in practice, many papers don't have a DOI or don't list their DOI.

If you knew that the paper would be listed with the correct title and authors, you could use a hash of the titles and authors and store that in a hashtable.  Of course, in practice it is common for titles to be mis-spelled, or for there to be variations in how they are listed (e.g., changes in capitalization; do you list the full first name of each author or just their first initial; and so on and so on).

If you knew the list of all variations, you could try to canonicalize the title and authors (e.g., lowercase the title, use only the last names of the authors, and so on).  Of course, in practice we probably can't know all the variations.

If you figured that all variations would be at small edit distance, you could use fuzzy matching and some kind of database that allows approximate match lookups.  (e.g., Efficient map data structure supporting approximate lookup, How fast can we identifiy almost-duplicates in a list of strings?, How to compare/cluster millions of strings?)  However, I suspect that in practice edit distance might not be enough to find all matches.  Also, there is a risk that you might end up conflating two different papers (for instance, I have seen a series of papers with titles like "Catching the Bugblatter, Part I" and "Catching the Bugblatter, Part II" with the same authors).

Hopefully all of this is conveying that in practice I suspect the problem is messy and there is no single clean answer.  Perhaps a pragmatic solution is to use some of the above techniques to find obvious matches, with the idea that this will take care of most cases of matches.  For the remainder, just accept that you might store the article multiple times, but hopefully this won't be too common.  Ultimately, storage space is extremely cheap, so storing the same article a few times probably isn't so bad.


Can parallel downloading with many ip's possible? I am not too intelligent,but i got this in my mind.Lets say i download a file from abc.com
and the speed is limited for an IP(say 60kbps).Can i initiate parallel downloads from multiple ip addresses which could be virtual IP's OR two diff.devices and break my download into parts,download each part at 60kbps and then join all.So that now it takes less time?IS this possible some kind of software to create Virtual Ip addresses?Or in multiple devices?

If the limitation is coming from the site, then it depends if the server allow you to resume partial downloads. If yes you can have two devices, one downloads the first part of the file, and the second one downloads the second part (telling the server it has already the first part).

The IP-address is given to you by your internet provider and it is unique. So you only have one and it can't be changed with software. (unless sometimes when you restart your router you can have a different one, but you can only have one at a time).

The device which downloads the second part needs to be connected to a network with a different ip-adress (for example your neighbor's Wlan).

But i don't think this is very practical.


Where to get graphs to test my search algorithms against? I am implementing a set of path finding algorithms such as Dijkstra's, Depth First, etc.

At first I used a couple of self made graphs, but now I'd like to take the challenge a bit further and thus I'm looking for either

graphs used in benchmarks;
graphs of real world cities (or a way to download that kind of info off google maps, or any other kind of source, if possible).

I'd like those sources to either have or allow me to easily create frontiers such that I can try my algorithms for different sized sets of graphs, if possible.

I'm looking for simple solutions, as I'd prefer not to be diverted from main goal (compare a set of different algorithms), so I'd need a quick way to convert that graph data into my own format (basically, a set of connected (x, y) points).

To be more concrete, what I'm looking for are 2D cyclic graphs. If those graphs reflect real world city streets (taking into consideration one-way streets, two-way streets, etc, better yet!).

Search the inter-webs.

SNAP is a set of networks hosted by a prof at Stanford. Several real world examples in a variety of settings.

Net Wiki is hosted by a UNC math prof., again several links to real datasets as well as links to other data resources.

OpenFlights Has airports and routes between them (spatial network).

OpenStreetMap user edited network of roads for most of the world. You can also download subsets (e.g. just roads in Ohio, or just highways in North America). Format is in xml, not super easy to parse, but its a real world ~2d cyclic network.

There are several other resources as well, you'll just have to dig a little.


Proving iff statement with reductions I have a statement I am trying to prove, and I'm very close, but I think I'm missing a couple of key concepts about regular and context-free languages.

Question: Let
$
A = \{ ww \ | \ w \ \epsilon \ \Sigma^{*} \}
$.

Show that any language $L$ is Turing-decidable if and only if $L$ is many-one reducible to $A$.

Where I am so far:

Language $A$ is not context-free, but the complement of $A$ is context-free.
Both $A$ and the complement of $A$ are decidable.

So, that means I can prove one direction of the iff statement fairly easily:

If $L$ is many-one reducible to $A$ then since $A$ is decidable from statement (2) above, also $L$ is decidable.

The other direction is giving me problems. This is all I have  gleaned so far:

If $L$ is Turing-decidable, then $L$ is a regular language.

Is there some relation between regular and context-free languages with respect to reductions that I am missing? Or should I be making a different logic jump in this part of the proof?

There is a more general theorem which says that if $A$ is a decidable language and $B$ is a decidable language that is not trivial (in the sense that $B\ne\Sigma^*$ and $B\ne\emptyset\, $), then $A\le_m B$. Roughly speaking, this says that all non-trivial decidable languages are many-to-one reducible to each other, meaning that $\le_m$ is too coarse a metric to distinguish between decidable languges.

In your problem, suppose that $L\subseteq \Gamma^*$ and define a mapping $f:\Gamma^*\rightarrow\Sigma^*$ defined by:
$$
f(x) =
 \begin{cases}
   \mathtt{aa} & \text{if $x\in L$}\\
   \mathtt{a} & \text{if $x\notin L$}
 \end{cases}
$$
for some $\mathtt{a}\in\Sigma^*$. This is a total computable function (since by definition, we can use the computable decider program to determine $x$'s membership in $L\, $) and it's easy to verify that $x\in L$ iff $f(x)\in A$, which is all you need to show $L\le_m A$. As Yuval noted, you don't need any results about regular or context-free languages to answer this question.


Proof that type does not have decidable equality in Agda Can one create such function in Agda ?

ℕ→ℕ-undecidable : ¬ ( (f g :  ℕ → ℕ ) → Dec (f ≡ g))
ℕ→ℕ-undecidable = ?

I am particularly interested in proof using cubical Agda.

ℕ→ℕ-undecidable is not provable in Agda. If we postulate the law of excluded middle (LEM), it follows that equality on every set is decidable, contradicting ℕ→ℕ-undecidable. Since Agda is consistent with LEM, it follows that ℕ→ℕ-undecidable is not provable in base Agda. This holds the same for cubical and vanilla Agda.


A several equivalent NP definitions There are two definitions of NP I found:

1) NP is a set of problems that have poly-size certificates, and with a given input, there is a poly-time certifier that checks the proposed solution.

2) NP is a set of problems that can be solved by non-deterministic algorithm in polynomial time.

I think (1) is a standard definition that appears everywhere, but I found (2) from one of the lecture videos, but to the best of my knowledge, I think the reason why they're equivalent is that, a non-deterministic algorithm can make a lucky guess out of polynomially many options in constant time, and a result of these guesses would be our certificate.

But why (2) is restricted to guess one out of polynomially many options? Why can't it guess one out of exponentially many options? I don't have any knowledge about how non-deterministic algorithm  or turing machine works.

The standard definition you'll usually find is the second one, but it makes no difference since they're indeed equivalent, and you can prove both arrows, I'll give a sketch of proof:

To see that (1) $\Rightarrow$ (2), consider a machine that non-deterministically guesses a certificate and then acts as a poly-time certifier.

On the other hand, to see (2) $\Rightarrow$ (1), observe that if a nondeterministic Turing machine decides $x \in L$ in polynomial time, then the set of nondeterministic choices it made in the path towards the accepting state is a certificate for $x$, and it must have polynomial size because by hypothesis every branch of the computation must terminate in polynomial time.

As for your second question, it is not true that a nondeterministic Turing machine can only guess out of polynomially many options (if it were the case, it could be simulated by a polynomially related deterministic machine). The limitation is that every computational branch must terminate in polynomial time. For instance, consider a nondeterministic machine for $\textsf{SAT}$: the number of valuations is exponential in the number of variables.

The reason why we give the characterization you cite in (1) is that we want to prove that $\textsf{NP}$ is the class of problems for which you can "guess" a solution and verify it in polynomial time, but a certificate that is more than polynomial in size cannot be "guessed" in polynomial time.


What makes type inference for dependent types undecidable? I have seen it mentioned that dependent type systems are not inferable, but are checkable. I was wondering if there is a simple explanation of why that is so, and whether or not there is there a limit of "dependency" where types can be indexed by values, below which type inference is possible and above which it is not?

For a rather simple version of dependent type theory, Gilles Dowek gave a proof of undecidability of typability in a non-empty context:

Gilles Dowek, The undecidability of typability in the $\lambda\Pi$-calculus

Which can be found here.

First let me clarify what is proven in that paper: he shows that in a dependent calculus without annotations on the abstractions, it is undecidable to show typeability of a term in a non-empty context. Both of those hypotheses are necessary: in the empty context, typability reduces to that of the simply-typed $\lambda$-calculus (decidable by Hindley-Milner) and with the annotations on the abstractions, the usual type-directed algorithm applies.

The idea is to encode a Post correspondence problem as a type conversion problem, and then carefully construct a term which is typeable iff the two specific types are convertible. This uses knowledge of the shape of normal forms, which always exist in this calculus. The article is short and well-written, so I won't go into more detail here.

Now in polymorphic calculi like system-F, it would be nice to be able to infer the type abstractions and applications, and omit the annotations on $\lambda$s as above. This is also undecidable, but the proof is much harder and the question was open for quite some time. The matter was resolved by Wells:

J. B. Wells, Typability and type checking in System F are equivalent and undecidable.

This can be found here. All I know about it is that it reduces the problem of semi-unification (which is unification modulo instantiation of universal quantifiers, and is undecidable) to type checking in System F.

Finally it is quite easy to show that inhabitation of dependent families is undecidable: simply encode a Post problem into the constructor indices. Here are some slides by Nicolas Oury that sketch the argument.

As to whether there is a "limit", it much depends on what you are trying to do with your dependent types, and there are many approximations which try to be either decidable, or at least close enough to be usable. These questions are still very much part of active research though.

One possible avenue is the field of "refinement types" where the language of expression of type dependencies is restricted to allow for decidable checking see, e.g. Liquid Types. It's rare that full type inference is decidable even in these systems though.


What type is this sorting algorithm? I needed to sort vertices into buckets as an optimization for collision detection later. I came up with this:

Go over all the vertices and count the size that each bucket needs to be to contain them into an array.
Shift the size array index by -1 unit and use it as offset array instead.
Create a single array for all the indices, go over all the vertices again and place their indices according to the offsets while bumping the offset each time.
Use the index list to translate vertices to their new positions (or optionally move the vertices on step 3 if you don't need a map but I did for transforming other primitives).

Surprisingly enough, it's much faster than std::sort (by 10x) or a gpu bitonic sort (by 13x) that I implemented earlier. It can't be a new idea since it's so simplistic in its concept.  So what is it called? I want to see what other people have done with it to perhaps make it even faster.

This is known as counting sort. On a domain of size $d$, counting sort runs in time $O(dn)$, compared to $O(n\log n)$ of comparison-based sorts. When $d\ll\log n$, i.e., when the domain is small compared to the total number of elements, we would expect counting sort to be faster. Counting sort can even be iterated, and this is known as radix sort.

If $d = o(\log n)$, then counting sort runs in time $o(n\log n)$, which might seem to contradict the well-known $\Omega(n\log n)$ lower bound on sorting. There is no contradiction, however, since the lower bound only holds for comparison-based sorts, which counting sort evidently isn't.


Question about Prims algorithm where weights are between 1 and some constant W I came across a couple of solutions to one of the problems that is in the CLRS textbook (pg. 637 23.2-5 edition 3).  I am wondering if anyone can make a clarification as to the stated running time of the solution.

Q:  Given that we know the edge weights on a graph are between $1$ and some constant $W$, how fast can we make Prim's algorithm run?

Solution:

Uses an array of linked lists where each index corresponds to a given weight [$1\dots W + 1$]
Each link linked lists contains a series of vertices with the weight of the index as their key

The run time given is $O(E)$

They break it down as follows:

$O(1)$ to find the vertex with smallest weight
       - I understand this part since we scan at most $W$ array slots to find a non-empty list and $W$ is constant.

$O(1)$ for decrease key
     - This makes sense as far as the actual removing of a link from one list and inserting it into another

My question is about the decrease key step.  Say for example we pull the node $A$ from the 3rd slot, that is the next node to be processed.  We look at $A$'s adjacency matrix and see that it has edges to $B, C, F$.  Since we are using linked lists we have no choice other than to look at all array slots from $4$ to $W$ and see if we can find the vertices listed in the linked list for that particular index. Then delete the vertex from its current list and add it to the correct list if we find it. Possible search time = $O(V)$ [since we store vertices in the linked lists and could search all before finding our desired vertex] not $O(1)$.

Since each decrease key takes $O(V)$ and we process all vertices running time = $O(V^2)$.

If anyone could let me know where I am going astray in my analysis I would greatly appreciate it.

The solution is to preprocess the adjacency matrix so that each vertex now has a list of adjacent vertices. When decreasing keys, you address each edge at most twice, so this part of the algorithm runs in $O(E)$.

The basic observation here is that you can implement a priority queue in $O(W)$ if the number of different weights is $W$. You have to be careful to maintain an array mapping the vertices to their current location in the priority queue, but then all operations are indeed $O(W)$.


What are efficient ways to compute the derivatives of iterated functions? The derivatives of iterated functions at a fixed point $z_0$ are useful in constructing a Taylors series of iterated analytic functions - in other words, the Taylors series of a dynamical system $f^t(z_0)$.

A simpler version of the problem casts light on possible approaches. Instead of iterated functions, consider composite functions and Faà di Bruno's formula The combinatorial structure integer partitions serves as the index to the summations in Faà di Bruno's formula. So the first step of evaluation is to enumerate all integer partitions of a given order.

While combinatorial structure integer partitions are associated with the derivatives of composite functions, the unlabeled version of the labeled combinatorial structure total partitions are associated with iterated functions. See Partition Diagrams for more information on the different relevant combinatorial structures. The following Mathematica code does what I need, but the cost of simplicity is that it first enumerates the labeled total partitions to compute the unlabeled total partitions. So for $n=10$, $D^{10}f^t(z_0)$, there are 282,137,824 labeled total partitions, while there are only 2,312 unlabeled partitions.

Combinatorial Examples

a(4)=5 unlabeled total partitions: (oooo),(oo(oo)),(o(ooo)),(o(o(oo))),((oo)(oo)).

b(4)=26 labeled total partitions: ((1,4),2,3), (1,(2,4),3), (1,2,(3,4)), (((1,4),2),3), ((1,(2,4)),3), ((1,2),(3,4)), (((1,4),3),2), ((1,(3,4)),2), ((1,3),(2,4)), ((1,4),(2,3)), (1,((2,4),3)), (1,(2,(3,4))), (1,2,3,4), ((1,2,4),3), ((1,2),3,4), ((1,3,4),2), ((1,3),2,4), (1,(2,3,4)), (1,(2,3),4), ((1,2,3),4), (((1,2),4),3), (((1,2),3),4), (((1,3),4),2), (((1,3),2),4), (1,((2,3),4)), ((1,(2,3)),4)

b(4) = 12 (o(o(oo))) + 3 ((oo)(oo)) + 6 ((oo(oo)) + 4 (o(ooo)) + (oooo) = 26

I would like to have an efficient way to reproduce the preceding results.

Mathematica code

TotalPartitions[0] = {{}};
TotalPartitions[1] = {{1}};
TotalPartitions[2] = {{1, 2}};
Match[l_List, pattern_] := Extract[l, Position[l, pattern]];
TP1[l_List, next_Integer] :=
  Map[( l /. # -> {#, next}) &, Match[l, _Integer] ];
TP2[l_List, next_Integer] :=
  Map[( l /. # -> Append[#, next]) &, Match[l, _List] ];
TP3[l_List, next_Integer] :=
  Map[( l /. # -> {#, next}) &, Match[l, _List] ];
TotalPartitions[n_Integer] :=
  TotalPartitions[n] =
   Flatten[ {Map[(TP1[#, n] ) &, TotalPartitions[n - 1]],
     Map[(TP2[#, n] ) &, TotalPartitions[n - 1]],
     Map[(TP3[#, n] ) &, TotalPartitions[n - 1]]}, 2];

u = TotalPartitions[4] /. _Integer -> 1
> {{{{1, 1}, 1}, 1}, {{1, {1, 1}}, 1},
>  {{1, 1}, {1, 1}}, {{1, 1}, {1, 1}},
>  {1, {{1, 1}, 1}}, {1, {1, {1, 1}}},
>  {{1, 1}, 1, 1}, {1, {1, 1}, 1},
>  {1, 1, {1, 1}}, {{{1, 1}, 1}, 1},
>  {{1, {1, 1}}, 1}, {{1, 1}, {1, 1}},
>  {{1, 1, 1}, 1}, {{1, 1}, 1, 1},
>  {1, {1, 1, 1}}, {1, {1, 1}, 1},
>  {1, 1, 1, 1}, {{1, 1, 1}, 1},
>  {{1, 1}, 1, 1}, {{{1, 1}, 1}, 1},
>  {{{1, 1}, 1}, 1}, {1, {{1, 1}, 1}},
>  {{1, {1, 1}}, 1}, {{1, 1, 1}, 1},
>  {{{1, 1}, 1}, 1}, {{{1, 1}, 1}, 1}}

SetAttributes[Z, Orderless];
Tally[Apply[List, Apply[Z, u, Infinity], Infinity]]
>  {{{1, {1, {1, 1}}}, 12}, {{{1, 1}, {1, 1}}, 3}, {{1, 1, {1, 1}}, 6},
>   {{1, {1, 1, 1}}, 4}, {{1, 1, 1, 1}, 1}}

Note that the Tally function displays the number of occurrences of labeled total partitions for each unlabeled total partition, so that $12+3+6+4+1=26$ shows how the 5 unlabeled total partitions of order 4 map to the 26 labeled total partitions. I've tried pure analytic approaches, combinatorial approaches and a hybrid of the two in my Mathematica programs Schroeder Summations and Iterate. I believe this is a useful problem in dynamics and combinatorics and merits an efficient answer.

An unordered hierarchical partition of $n \geq 2$ is composed out of two ingredients:

A non-trivial partition $n_1,\ldots,n_k \vdash n$, where $n_1 \leq \cdots \leq n_k$ and $k > 1$.
For each $n_i$, an unordered hierarchical partition of $n_i$. Furthermore, if $n_i = n_{i+1}$ then in some fixed order of hierarchical partitions of $n_i$, the one chosen for $n_i$ must precede or equal the one chosen for $n_{i+1}$.

In the base case $n = 1$ there is a single unordered hierarchical partition.

This gives the following algorithm for generating all unordered hierarchical partitions. We generate a list $P^{(n)}_1,\ldots,P^{(n)}_{q(i)}$ of all $q(n)$ unordered hierarchical partitions of $n$. For $n = 1$, the list consists of the single trivial partition. In order to generate the list for $n$:

Go over all non-trivial partitions $n_1,\ldots,n_k \vdash n$. We can write this partition more succinctly as $1^{m_1},\ldots,(n-1)^{m_{n-1}}$, where $m_i$ is the multiplicity of $i$.
For each $i \in \{1,\ldots,n-1\}$, make a list of all non-decreasing sequences of length $m_i$ consisting of numbers in $\{1,\ldots,q(i)\}$; there are $\binom{q(i)+m_i-1}{q(i)}$ of these.
Each choice of one sequence for each $i$ from the corresponding list corresponds to one unordered hierarchical partition of $n$.


FP^NP-complete problems Is there any other standard FP^NP-complete problem other than the Traveling Salesman Problem? For instance, in the canonical propositional logic?

TSP is actually OptP-complete and so are many other optimization problems, including Knapsack, MAX-SAT, 0-1 Integer Linear Programming. This class and proof technique is largely the work of Mark Krentel; orig paper STC'86. The journal version of the paper has more details, including the fact that OptP is subclass of FPNP.

LEX-MIN-SAT, finding the lexicographically smallest satisfying assignment, is OptP-complete under metric reductions. There's also an analogue of Schaefer's dichotomy theorem
for LEX-MIN-SAT proved by Reith and Vollmer http://arxiv.org/pdf/cs/9809116.pdf

I think is almost a research-level, or at least graduate-level question, by the way.


Which algorithms are usable for heatmaps and what are their pros and cons This is a cross post from Stack Overflow, and DSP at Stackexchange since I cannot really decide which part of Stackexchange is most fitting. If this is the wrong place please tell me and I'll remove the question.

I have a matrix with numerical data. The matrix contains values from 0 to an arbitrary integer value.

Each element of the matrix is equivalent to a coordinate on a map.

I want to display that data as a heatmap overlayed the original map.

The three approaches I have found so far are

Linear interpolation. I guess the interpolation is don from the original datapoint to some set distance away from it in each direction.
Average of surrounding cells. Each empty cell gets the average value of the eight adjacent cells.
Gaussian blur as suggested on the SO thread.
Box blur with 1..n passes.

Are there any more methods? What are the pros and cons of the different approaches? What is a good source, online or print, for a discussion on heatmaps or similar problems?

If I have understood your question correctly (an illustrative example would have been helpful), I would recommend either Gaussian blurring or linear interpolation depending on the behavior you are after. Both are simple and should perform relatively fast even on a handheld device.

Linear interpolation (or rather bilinear interpolation) is simple but requires a square heat sample grid and you get some boundary effects that might be undesirable. The method is the most representative since "empty cells" (i.e., cells without heat information) are simply empty because of sparse sampling and not because they are void of heat. The interpolation tries to fill in the missing heat information in the empty cells by looking at the nearby heat samples.

Cell averaging will give you an equally high response in a cell neighboring the heat sample as in the heat sample cell itself (granted that the average is computed for all cells including the cells containing heat samples). If the average is computed for empty cells only (i.e., for cells with no heat information) then the cells with the heat sample will keep its full signal while adjacent cells will contain an average, which in a sparse sample grid will be 1/8 of the heat sample, resulting in a distribution almost as misleading as only using the original heat samples.

Gaussian blurring with a wide enough kernel is simple and gives a better  representation of the impact of the heat samples than the cell averaging. However, the values in the blurred heat map for the empty cells will only be affected by the heat "spread" from the sample cells. So if the heat map is sparse, there will likely be empty cells on equal distance between two heat cells that do not get any heat information at all.

I hope this helps.


How can I check if $n >m$ in $a^n b a^m$? How can I design a Turing machine that takes string $a^n b a^m$ and check if $n>m$ then convert the string to $a^{n-m}$, otherwise reject it?

Start with placing tape over $b$, then go to the rightmost $a$, put blank, go back to $b$ and delete the rightmost $a$.
Every time you scratch out $a$s on both sides, $n - m$ does not change until one side is blank.
Check if the left side is not empty, delete $b$ (and if it is required, go back to the beginning of the tape) and accept, otherwise reject.


n-th non-decreasing sequence I have a generator of non-decreasing sequences of numbers 0..M:

M = 9;
c = 0; //counter

for (i1 = 0;  i1 <= M; i1++)
    for (i2 = i1; i2 <= M; i2++)
        for (i3 = i2; i3 <= M; i3++)
            for (i4 = i3; i4 <= M; i4++)
                printf("%d. %d%d%d%d", ++c, i1, i2, i3, i4);

Result:

1. 0000
2. 0001
3. 0002
...
10. 0009
11. 0011
12. 0012
...
19. 0019
20. 0022
21. 0023
...

I need to calculate ONLY the n-th element. For example:

input: n = 21
result: 0023

It takes O(M^4) iterations to calculate it

How can I calculate the n-th element more efficiently? (without generating all previous elements)
Is there an O(1) algorithm for this problem?
If not how can we show that there is no such algorithm.

Thank you!

This is yet another example of combinatorial enumeration. There are altogether $\binom{M+4}{4}$ different quadruples. Given $j_0$, there are $\binom{M+3-j_0}{3}$ quadruples with $i_0 = j_0$. This means that the first $\binom{M+3}{3}$ quadruples start with $0$; the following $\binom{M+2}{3}$ start with $1$; the next $\binom{M+1}{3}$ start with $2$; and so on. In this way, given a number between $1$ and $\binom{M+4}{4}$, you can find $i_0$.

You then zoom in on a list of length $\binom{M+3-i_0}{3}$, and again you are given a $1$-based index to it. There are $\binom{M+2-(j_1-i_0)}{2}$ quadruples with $i_1 = j_1$. This means that the first $\binom{M+2}{2}$ quadruples start with $i_0,i_0$; the following $\binom{M+1}{2}$ with $i_0,i_0+1$; and so on. Having found $i_1$ this way, you can find $i_2$ and $i_3$ by repeating the same argument twice more.

The same argument, run in reverse, can be used to calculate the index given the quadruple.  Assuming binomial coefficients can be calculated in constant time and that integer arithmetic is constant time, this algorithm runs in time $O(4\cdot M)$, or $O(4\cdot\log M)$ with $O(4\cdot M)$ preprocessing (for fixed $M$). I'm including the $4$ since if you had $t$-tuples instead of quadruples, you could replace it with $t$.


Wrong proof about maximum matching Given a bipartite graph $G=(U,V,E)$, find a maximum matching.

Algorithm G:

Let $S\gets\emptyset$
Mark all edges unmatched
For $i\gets1$ to $|E|$

If $i$ is unmatched

$S\gets S\cup\{i\}$

End If

End For

Proposition:
   Algorithm G is optimal.

Proof: Feasibility is easy by induction. We prove that $|S|$ is maximum. By contradiction. Assume that there exists a set $S'$ of edges that has more edges than $S$. Since $S$ is maximal, then no edge could have been added to it without violating its feasibility. Thus, $|S|$ cannot be increased. Since $|S'|>|S|$, we reach a contradiction.

This is, of course, wrong, but I cannot find the error?

Consider the path graph of length 3: $x-y-z-w$.

Take $S$ to be $y-z$, and $S'$ to be $x-y,z-w$.

A set of constraints for which your kind of argument does work is known as a matroid. The greedy algorithm that you describe does work for matroids (and, more generally, for greedoids). Your set of constraints satisfies a weaker condition: it is 2-extendible, meaning that in order to add a new element (in this case, an edge), you need to throw out at most two existing elements. The greedy algorithm always gives a 2-approximation for such systems of constraints.


Planar regular languages In my class a student asked whether all finite automata could be drawn without crossing edges (it seems all my examples did). Of course the answer is negative, the obvious automaton for the language $\{\; x\in\{a,b\}^* \mid \#_a(x)+2\#_b(x) \equiv 0 \mod 5 \;\}$ has the structure of $K_5$, the complete graph on five nodes. Yuval has shown a similar structure for a related language.

My question is the following: how do we show that every finite state automaton for this language is non-planar? With Myhill-Nerode like characterizations it probably can be established that the structure of the language is present in the diagram, but how do we make this precise?

And if that can be done, is there a characterization of "planar regular languages"?

It isn't true that every DFA for this language is non-planar:

Here is a language that is truly non-planar:
$$
\left\{ x \in \{\sigma_1,\ldots,\sigma_6\}^* \middle| \sum_{i=1}^6 i\#_{\sigma_i}(x) \equiv 0 \pmod 7 \right\}.
$$
Take any planar FSA for this language. If we remove all unreachable states, we still get a planar graph. Each reachable state has six distinct outgoing edges, which contradicts the known fact that every planar graph has a vertex of degree at most five.


Recover PRNG description from consecutive outputs Given the outputs of the pseudorandom numbers generator how can one determine the type (e.g. Linear Feedback Shift Register), Multiply-With-Carry, Linear Congruential Generator etc.) and recover the function and the seed?

The given array of numbers is for sure generated by PRNG (not Cryptographically Secure) - this is known in advance. The outputs are clean, the PRNG is a black box returning consecutive numbers (no modified, no skipped values. Now the task is to find the function and seed from the values.

The simple idea is try all schemes until match is found, but I am interested in more algorithmic approach.

There's no single method to determine the type of the PRNG.  Indeed, for a cryptographic-strength PRNG you can't distinguish its output from truly random, so you can't determine the type of such PRNGs solely by looking at their output.

Instead, for each of the schemes that you list, there is a way to recover the seed and predict future bits from its output.  The way to do that is different for each type of PRNG.  So, the natural approach is: for each candidate type, try the method for recovering the seed that works for that type of PRNG, and see if you're successful.  If you are, you've figured out the type of PRNG.

I don't think there's a more efficient or general technique.  And, frankly, I don't think a more efficient one is needed.  For the types you list, there are very efficient algorithms for cryptanalyzing them, given enough output.  So, I suspect it's going to be hard to beat the "try all schemes" approach.

This works if your set of PRNG types contains only PRNGs that are cryptographically weak, i.e., where it is possible to predict future outputs given enough past outputs.

For details of how to do this for any specific type of PRNG, I suggest you ask a separate question focused on that one type of PRNG.  Here are some resources on some of the PRNG types you listed:

LFSR: See the Berlekamp-Massey algorithm, which is very efficient.  See also https://crypto.stackexchange.com/q/5293/351.
Linear congruential generators (LCG): There are very efficient ways to recover the seed, based on modular arithmetic.  See https://security.stackexchange.com/q/4268/971.
Multiply with carry (MWC): If you have enough output, it's easy to check whether the output appears to be consistent with a MWC generator: see https://crypto.stackexchange.com/q/10359/351.  If you don't have much output, I'm not sure it is possible (for information-theoretic reasons, since the seed and internal state is so large).


Undecidability instance on a "find a proof/disproof" machine I'm following through the proof of the impossibility of the Halting problem for the umpteenth time. It all makes sense logically, but not intuitively. A question I got stuck on:

Suppose we built the following machine in attempt to solve the halting problem. It takes our standard set of axioms (ZFC, let's say, or Peano arithmetic, or whatever) and first tries every one-page proof that machine M halts on input I. It then tries every one-page proof that machine M never halts on input I. Then it tries every two-page proof of each, and so on and so on.

It's quite plain that this wouldn't necessarily always work. By incompleteness, there are statements that can't be proven true or false; it makes sense that there might be Turing machines that are equivalent to these statements. The undecidability problem assures that indeed these do exist.

So, let's follow that through. [Begin standard proof.] We have built this function $f(a,b)$ to return $1$ if it finds a proof that program $a$ halts on input $b$, and $0$ if it finds a proof that $a$ doesn't halt. (We note that this function $f$ might never return, so it's not total computable.) We can make a function $g(a)$ that first calls $f(a,a)$, and returns $0$ if $f(a,a)=0$, and enters an infinite loop if $f(a,a)=1$.

If $f(g,g)$ terminated and returned 0, then $g(g)$ would terminate and return 0 -- but $f(g,g)$ terminating and returning 0 implies it found a proof of $g(g)$ not terminating, so this is impossible. If $f(g,g)$ terminated and returned 1, then $g(g)$ would never terminate -- but $f(g,g)$ returning 1 implies it found a proof of $g(g)$ terminating. [End standard proof.]

This pair of paradoxes is used in the standard proof to show that there is no function $f$ that always returns $0$ or $1$. There's no problem here, though, because we allow $f$ to not terminate -- and so indeed, it must never terminate, when given the inputs $g$ and $g$.

Here's where I'm confused. Because $f(g,g)$ never terminates, this implies that there is no disproof to be found, because it tries all of them. Suppose that $g(g)$ terminated at some point. Then by running simply it for that many steps, we can see that terminates, and this constitutes a perfectly valid proof.

Keep in mind that $f$ is a real program, and so is $g$. We know that for these concrete values (in some numbering system), $g(g)$ can't terminate, otherwise $f(g,g)$ would find the dumb proof of simply running it to that point.

The above constitutes a proof that $g(g)$ never terminates, and so the function $f(g,g)$ should find this proof, and use it to show that $g(g)$ doesn't terminate, but this is also a problem.

I'm sure there's something here I'm dramatically misunderstanding; I appreciate the time from anyone to answer.

So $f(M,I)$ is this machine that "takes our standard set of axioms (ZFC, let's say, or Peano arithmetic, or whatever) and first tries every one-page proof that machine M halts on input I"...

That's fine, but later on you say "The above constitutes a proof that $g(g)$ never terminates, and so the function $f(g,g)$ should find this proof."

That is not true, since you didn't write that proof as a formal proof in terms of "ZFC, let's say, or Peano arithmetic, or whatever", so there is no reason to expect $f(g,g)$ to find it.  You didn't even define $f(a,b)$ of $g(x)$ in terms that would translate into most such formal systems.

You assume that you would be able to specify a real formal system if you had to, with sufficient power to express $f$ and $g$ in concrete terms and prove what you say about them, but Godel's theorem says that's not necessarily so.

Furthermore, you say that $f$ and $g$ are real programs, but that is not true until this formal system is specified.  Because of this you have not proven what you set out to prove.  What you have proven is Godel's theorem -- any formal system that allows you to express your claim in terms of itself will either be inconsistent, or will not contain your proof.


Complexity of GF(2) and applications to cryptography If I have a system of N polynomial equations with N unknowns in GF(2):

What are some good methods to solve them?
What's the highest value of N that can be reasonable solved?

Now, my root interest isn't GF, it's crypto.  Here's my reasoning:

Any function from a n-dimensional binary vector to {0,1} can be represented as a GF(2) polynomial function of n variables.
Thus, for instance, any cipher from (Plaintext, Key) to Ciphertext can be represented as a series of equations (one for each bit in the ciphertext), each a GF(2) polynomial of (p-bits + k-bits) variables.
Thus, if we know P and C, and we can solve systems of GF(2) equations, we can determine K.

The (meta) algorithm you're looking for is the Gröbner basis algorithm. In the last decade, the approach that you mention, called algebraic attacks, has gained momentum in the cryptological community. One person who has been developing efficient Gröbner basis algorithms in the context of cryptography is Faugère. He has some links to relevant papers on his web page, including applications.

Since SAT can also be written as a (small) system of polynomial equations, you shouldn't expect a general algorithm to work always, or even on average. The hope is that some systems of polynomial equations are easier. You have to find these "easy" systems in order to apply this method in cryptology.


There is any notation for a language that is empty infinite? Assume that $L$ is a language, is there any established notation that means that $L$ is infinite or empty?

The usual way to describe these properties is by indicating the size of $L$, denoted by $|L|$.

Empty language, the size is zero, $|L|=0$
Finite language, $|L|=c$ or in general, the size in non-infinite, $|L|< \infty$
Infinite language, $|L|=\infty$.


Are process-safe mutexes shared between OSes? I understand you can use process wide mutexes, but does this still apply if you have an additional virtualized operating system provisioned?

For example, take two OSes: O1 and O2 where O2 is a virtualized OS provisioned on O1. Now take some code C that uses a process-wide mutex. Run C on O1 and O2. Assuming they have access to the same resource through some file sharing mechanism (e.g. guest additions.) Does the mutex still work?

For most implementations of a mutex it won't work, but in principle it depends on how the mutex is implemented.  If the mutex was implemented using files, perhaps it could be made to work.  Usually the mutex is managed by the operating system, and the operating system keeps track of the state of the mutex, so both processes have to be running in the same operating system to be able to share a mutex.


Examples of Context-sensitive grammars which produces non-indexed language Well known example of Context-sensitive grammar which produces language $\{a^nb^nc^n|n\geq 1\}$ is widely used in various papers. But actually, while this language is definitely context-sensitive, it is also belongs to smaller subset of CS-languages: it is indexed language, because it can be described with indexed grammar as well.

What I'm looking for, it is example of Context-sensitive grammar which produces non-indexed language. From this paper it is known that language $\{(ab^n)^n|n\geq 1\}$ is not indexed. But there is no described grammar for this language.

So could somebody describe CS-grammar for given non-indexed language example, or provide with any other example?

If you settle for a noncontracting (or monotonic) grammar instead:

$S\to DTA \mid ab$ $~~~~~$ the last $A$ is an end-marker for the last $ab^n$, $n=1$ separate.

$T\to DTa \mid Da$ $~~~~~$ number of $D$'s equals the number of $a$'s ($A$ counts as $a$)

$Da \to abD$ $~~~~~$ every $a$ gets an extra $b$

$Db \to bD$ $~~~~~$ $D$ moves over $b$'s

$DA \to Ab$ $~~~~~$ and $D$ disappears at the last block of $ab^n$

$A \to a$ $~~~~~$ finally end-marker $A$ is changed into $a$ (if we do this too soon, the $D$'s will not disappear, and the dirivation is not valid)

Example of building word $abbbabbbabbb$ ($n=3$) (added by @Andremoniy):

1) $S\Rightarrow DTA\Rightarrow DDTaA\Rightarrow DDDaaA$ - "inflate" string $n$ times;

2) $\Rightarrow DDabDaA\Rightarrow DabDbDaA\Rightarrow abDbDbDaA\Rightarrow abbDDbDaA\Rightarrow abbbDDDaA\Rightarrow \dots$ - we built 1st subword $abbb$, move on

3) $\Rightarrow abbbDDabDA\Rightarrow abbbDabDbDA\Rightarrow abbbabDbDbDA\Rightarrow abbbabbbDDDA\Rightarrow\dots$ - two subwords $abbbabbb$ are built, move on

4) $\Rightarrow abbbabbbDDAb\Rightarrow abbbabbbDAbb\Rightarrow abbbabbbAbbb\Rightarrow abbbabbbabbb$


Is an integer variable constant or logarithmic space? My lecturer says that a variable takes up one memory position in RAM. This is the slide in question:

But CLRS (Introduction to Algorithms by Cormen, end of page 23) says an integer is represented by $c\ lg\ n$.
Are both statements true? How can that be?

The random-access machine is a common model of computation, which is the model of choice when analyzing algorithms. In this model, memory consists of words of length $\Theta(\log n)$ bits, where $n$ is the length of the input (in bits). Therefore both your lecturer and CLRS are right.


On which stage (lexical analysis, syntax analysys, and so on) is most of the compilation time spent? I know that during compilation we need to undergo several stages like lexical analysis, syntax analysis and so on. Which of them takes the most time?

For a few compilers I've seen compilation times was reduced 3+ fold when optimization was disabled, so otherwise they spent most time on optimization passes.


How to generate a connected random network topology for a specific number of nodes? I'm trying to generate a random but realistic network topology so I can test the performance of some routing algorithms. I came across Waxman's model described in Routing of Multipoint Connections, which seems pretty simple:

Distribute $N$ nodes randomly across a plane (uniform in x and y).
For each pair of nodes, generate an edge between them with the probability $ P = \beta \exp \frac{-d}{L\alpha}$, where $d$ is the euclidean distance between the nodes, $L$ is the maximum distance between two nodes, and $\alpha$ and $\beta$ are parameters in the range $(0, 1]$.

I've implemented my current understanding of Waxman's algorithm as a simple web-based demo, which visualizes a generated topology from chosen parameters $\alpha$, $\beta$, and $N$.

However, I want to be able to generate a connected network topology for
a specific number of nodes. Since Waxman's algorithm generates edges probabilistically, I usually end up with disconnected nodes. How do I connect the rest of the nodes to the topology in a way consistent with Waxman's algorithm, i.e. simulates a real network topology?

There are plenty of ways to "finish" the topology by connecting the disconnected nodes, but I don't know which one is the most compatible with the already-generated edges. Waxman's paper doesn't seem to mention how disconnected nodes are treated.

I played with your demo a little bit and I suppose given a distribution of points, $\beta$ and $\alpha$ can be chosen properly so that the generated graph is connected with a high probability. A brute-force approach can be choosing the parameters using a binary search.


If P = NP, then is NP = FNP? I read

  FP = FNP iff P = NP

which makes sense.

But if P = NP, does it mean FNP = NP?

Intuitively, I think no because P = NP would mean that decision problems in NP would become decision problems in P. But I don't see how that would reduce search problems to decision problems.

No, it doesn't mean that FNP = NP.  NP is a class of decision problems; FNP is a class of function problems.  See the definition of FNP (e.g., on Wikipedia, or in any textbook).  Therefore, the elements of NP have a different type than the elements of FNP.

It's like asking whether the set of tart apples is equal to the set of seedless oranges; one is a set of apples, the other is a set of oranges, so they're certainly not equal, and you don't need to know anything about exactly which apples are tart or which oranges are seedless to know that.


Prove that $2^{(log(n)^{1/2})}$ is $O(n^a)$ Hopefully this is the right section. I need to prove that $2^{(log(n)^{1/2})}$ is $O(n^a)$. From the basic principle of Big-O notation, I know I need to find two numbers $c$ and $N$ so that $f(n) \le c\cdot g(n)$ for all values of $n \ge N$. In this case, $f(n)$ is $2^{(log(n)^{1/2})}$, and $g(n)$ is $n^a$.

The first problem in the set had me prove that $2^{n+a}$ is $O(2^n)$. For this problem, I had separated the $f(n)$ to $2^n \cdot 2^a$. I was guided by another user to set $c = 2^a$. This way, with $g(n) = 2^n$, $cg(n) = 2^a2^n$, which is obviously $\ge f(n)$, $2^{n+a}$, for all values of $n \ge 0$. This problem, however, I don't find as easy.

Could someone point me in the right direction? I've been trying to rearrange the problem and solve it for a while now.

$n^a = \exp(a \ln n) = \exp(a \ln n \frac{\ln 2}{\ln 2}) = 2^{\frac{a \ln n}{\ln 2}}$. Can you prove that if $h(n) = O(k(n))$ then $2^{h(n)} = O(2^{k(n)})$ ?


Polynomial Identity Testing $(\mathsf{PIT\text{}})$ in non commutative setting Let me define the problems first

Polynomial Identity Testing $(\mathsf{PIT\text{}})$

Given :  A polynomial $p$ over some field $\mathbb{F}$.

Decide : Are all coefficients of the monomials of $p$ are equal to zero ?

Polynomial Identity Testing $(\mathsf{PIT1\text{}})$

Polynomial identity testing defined in non commutative setting i.e. $x.y \neq y.x $

Given :  A polynomial $p$ over some field $\mathbb{F}$.

Decide : Are all coefficients of the monomials of $p$ are equal to zero?

Evaluates to Zero Everywhere $(\mathsf{EZE\text{}})$

Given :  A polynomial $p$ over some field $\mathbb{F}$.

Decide : Is it true that for every choice of numbers $a \in \mathbb{F}$, the value of $p(a)$ is the number $0$.

My question : Are $\mathsf{PIT\text{}}$ and $\mathsf{PIT1\text{}}$ equivalent?

Reference : http://www.cs.ubc.ca/~nickhar/W12/Lecture9Notes.pdf

PIT and PIT1 are not equivalent. For example, $xy-yx$ is the zero polynomial in the commutative setting but not in the non-commutative setting. You can get a non-commutative analog of EZE by considering large enough matrices, where large enough depends on the formal degree of the polynomial involved.

Suppose that $P$ is a multivariate polynomial in $x_1,\ldots,x_n$ which is not identically zero. We want to find a point where it is non-zero. The proof is by induction on $n$. If $n=0$ then $P$ is some non-zero constant, and there is nothing to prove. If $n>0$, write
$$ P = \sum_{i=0}^d Q_i x_n^i, $$
where the $Q_i$ are polynomials in $x_1,\ldots,x_{n-1}$, and $Q_d$ is not identically zero. The induction hypothesis shows that $Q_d(\alpha_1,\ldots,\alpha_{n-1}) \neq 0$ for some real $\alpha_1,\ldots,\alpha_{n-1}$. Making this substitution, we obtain a univariate polynomial $P'$ in $x_n$ which is not identically zero. If $|\alpha_n|$ is large enough, simple estimates show that $P'(\alpha_n) \neq 0$, and so $P(\alpha_1,\ldots,\alpha_n) \neq 0$.

Here are the simple estimates: if $P' = \sum_{i=0}^d c_i x^i$ and $|\alpha| \geq 1$ then
$$
|P'(\alpha)| \geq |c_d| |\alpha|^d - \sum_{i=0}^{d-1} |c_i| |\alpha|^i \geq
|\alpha|^{d-1} |c_d| \left(|\alpha| - \frac{\sum_{i=0}^{d-1} |c_i|}{|c_d|}\right).
$$
This is non-zero if $|\alpha| > 1+\sum_{i=0}^{d-1} |c_i|/|c_d|$.


Does the term "continuity" have a different meaning in maths and in CS? I ask this question because of some statements in the question "What is the 'continuity' as a term in computable analysis?" making me suspicious.
I'm engineer, not computer scientist, so I don't have the Turing machine but logic gates in mind when I'm thinking about algebraic operations performed with devices.
I read the answer to the question "Why are computable functions continuous?" and understood it the following way:

Because the device's input is of infinite length (a decimal number with an infinite number of digits after the decimal point), the device (e.g. Turing machine or computer) cannot read the entire number before writing the $n$-th digit of output.
Instead, the device can only have read $m(n)$ digits of the input when it writes the $n$-th digit of output.
If the first $n$ digits of the output of some function only depend on the first $m(n)$ digits of the input, the function is continuous.

However, if I understand this argumentation correctly, the word "continuous" in computation theory is not identical to the word "continuous" in mathematics:
Rounding towards zero would only require reading the input until the decimal point (so $m(n)=\text{const.}$); however, the mathematical function being calculated is not "continuous" according to the mathematical definition of that term.
We could also perform a digit-wise operation ($m(n)=n$) and exchange certain digits after the decimal point; for example replace all 4s by 9s and all 9s by 4s. As far as I understand, the function being calculated is not continuous on any interval of $\mathbb{R}$ (however, it would be right-continuous on $[0,\infty)$ and left-continuous on $(-\infty,0]$).
And if I didn't make a conceptual mistake and we use a balanced numeral system (like a Russian computer in the 1960s) instead of the decimal system, a similar algorithm (exchanging 0s and 1s instead of 4s and 9s) would even represent a mathematical function which is not even directional continuous on any interval of $\mathbb{R}$.
Questions:
Does the computability depend on the numeral system being used (as the example with the balanced numeral system suggests) or is the term "computable" even assuming a certain numeral system being used?
Is the observation correct that the term "continuous" does not have the same meaning in maths and CS?

If we were to use the decimal expansion to represent real numbers, your reasoning would work. But that gives us a very badly behaved notion of computability:
Proposition: Multiplication by 3 is not computable relative to the decimal representation.
Proof: Assume the input starts 0.3333333... At some point, our computation needs to start outputting something. The best choices are 0. and 1.. In the first case, we have screwed up if our input has a 4 as next digit we hadn't looked at; in the second case a 2 makes us wrong. Thus, we cannot output a guaranteed prefix of the solution.
Using a different base would yield a different notion of computability, but none of them are suitable. Some ways that all yield the same good notion of computability are:

Code a real $x$ as a sequence of rationals $(q_n)_{n \in \mathbb{N}}$ such that $|x - q_n| < 2^{-n}$.
Code a real via a signed digit representation, using $\{-1,0,1\}$.
Code a real $x$ as a sequence of rational intervals $(I_n)_{n \in \mathbb{N}}$ with $\bigcap_{n \in \mathbb{N}} I_n = \{x\}$

When we speak about computability of a function on the reals without specifying what kind of representation we are using, we mean one of these (or another equivalent one). This is just like we don't always point out using the Euclidean topology on the reals if we do, that is just the standard case. We can now state:
Theorem: The functions on the reals which are computable (wrt the standard representation) relative to some oracle are exactly the continuous functions (wrt the Euclidean topology).
Coming back to rounding, this shows that perfectly exact rounding cannot work. However, we can circumvene this by not restricting ourselves to functions. For example, the following task is computable:
Given a real number $x \in [0,1]$, output either $0$ or $1$. If $x < 0.501$, then $0$ is an acceptable solution and if $x > 0.499$, then $1$ is an acceptable solution.
If the input to the task above is from $[0.499,0.501]$, then the answer we get does not only depend on the real we are looking at, but on the particular code for that real that our algorithm reads. That can make reasoning about algorithms slightly more cumbersome, but we really can't avoid that.


Shared randomness does not increase capacity of a noisy channel - Why? Why is it the case that when Alice and Bob use a noisy channel for communication, the capacity of the channel does not increase even if they are allowed to share pre-distributed randomness?
This is mentioned in some notes (see paragraph before Section 4 of https://cds.cern.ch/record/613098/files/0304102.pdf) but I have not seen a proof or an intuitive argument for it yet. Any reference to where this is covered would also be appreciated!

Each value of the shared randomness corresponds to a communication protocol. So overall, we have a mixture of communication protocols, whose expected quality is good. There must therefore be one of these communication protocols – a setting of the shared randomness – which is as good.
As an example, we know that a random code achieves capacity. This means that some particular code achieves capacity. It might be hard to find that code, but we know that it exists.


Where/how did a $\log(n)$ factor disappear from well-known algorithms? Consider the binary search problem on a sorted array containing $n$ integers on
16 bits. Everybody agrees that the binary search needs $O(\log(n))$ time,
because it makes at worst $O(\log(n))$ steps. But: at each step it needs to
calculate a midpoint. The first midpoint is $[n/2]$. The next midpoint could
be $[n/2]+[n/4]$. If the searched number is placed in the second half of the
array, the midpoint at each step is no less than $[n/2]$. Each calculation of
a new midpoint involves at least a number with $O(\log(n))$ bits, hence each
midpoint calculation requires $O(\log(n))$. I obtain a more precise complexity
of $O(\log(n)^2)$. Where is the error?

The same problem could appear on countless algorithms that use arrays or
matrices. Take the most well-known dynamic programming algorithm for the
knapsack problem. Everybody agrees it takes $O(nW)$ time (e.g., the
wikipedia article on the knapsack problem), where $n$ is the number of items and
$W$ is the capacity. But at each step, it needs to compute a difference of
weights/capacities, which should account for an additional factor of
$O(\log(W))$. Where is the error?

Where/how does this $O(\log(n))$ complexity factor disappear? If we had needed
it, it would have appeared in many algorithms.

ps. A very similar problem arises in the questions asked here and here, thanks Ariel, Raphael and ryan for pointing this out.

You're not wrong, you're just using a different cost model.

Typically there are two:

  Uniform cost model - assigns a constant cost to every machine operation regardless of size of numbers.
  Logarithmic cost model - assigns a cost proportional to the number of bits involved for each machine operation.

Under uniform cost, a binary search takes constant operations to find the next index to search at, we get a recurrence relations like so:
$$\begin{align}
T(1) & = O(1)\\[0.5em]
T(n) & = T\left( \left\lfloor \frac{n}{2} \right\rfloor \right) + O(1)\\[0.5em]
& = \Theta(\log n)
\end{align}$$

Under logarithmic cost, we can assume it takes $f(n)$ operations to find the next midpoint and we get a recurrence like so:
$$\begin{align}
T(1) & = O(1)\\[0.5em]
T(n) & = T\left( \left\lfloor \frac{n}{2} \right\rfloor \right) + f(n)\\[0.5em]
\end{align}$$
For binary search, typically $f(n)$ will be no more than computing $\lfloor \frac{l + r}{2} \rfloor$ which would take $\log_2 n$ operations for the addition, and to divide by $2$ we could do a bit shift taking $\log_2 n$ operations (see here). Which brings us to:
$$\begin{align}
T(n) & = T\left( \left\lfloor \frac{n}{2} \right\rfloor \right) + \Theta(\log n)\\[0.5em]
& = \Theta(\log^2 n)
\end{align}$$
These logarithmic costs are just for addition and shifting though. If you were to do other $n$-bit operations then $f(n)$ could change. For example, $n$-bit multiplication and exponentiation could be larger than $\Omega(n)$ and you would have to adjust you complexity accordingly under logarithmic cost.


Does PETSc really give speedup? I searched linear solver library and found out PETSc library which considered to be powerful and useful library. PETSc consists implementations of various iterative methods with preconditioners and sparse matrix storing methods. All methods are realized sequentially and in parallel using MPI.

I was very glad for creaters of PETSc. I downloaded it and installed. However, when I start reading user's guide I encountered following text:

PETSc should not be used to attempt to provide a “parallel linear solver” in an otherwise sequential
code. Certainly all parts of a previously sequential code need not be parallelized but the matrix
generation portion must be parallelized to expect any kind of reasonable performance. Do not expect
to generate your matrix sequentially and then “use PETSc” to solve the linear system in parallel.

I was surprised! Did PETSc developers really parallelize only matrix generating part? What is a benefit of using PETSc as parallel solver if linear system solving part runs sequentially?

You misread the text.  The authors of PETSc are just telling you that you can't avoid Amdahl's law.

They have done their best to parallelize every aspect of the linear solver.  But a real program is not just a call to a linear solver.  First you generate a matrix and then you pass the matrix to the linear solver.  If your matrix generator is slow, your whole program will be slow.

For example, suppose your original program spends 1000 seconds generating the matrix $A$ and vector $b$ and then you call a linear solver.  Your old (sequential) linear solver took 1000 seconds to find $x$ such that $Ax = b$.  Now you replace your old sequential linear solver with PETSc.  Suppose the PETSc authors did such a good job that the PETSc parallel linear solver finds $x$ in just 1 second!  Now how long does it take your program to run?  1001 seconds.  You got less than 2x speedup!  You need to do some work on your matrix generation code if you want to get a better speedup.

Pretty much the authors of PETSc are just telling you that a parallelized linear solver library is not a magic bean.


Kolmogorov complexity vs purposefully inefficient Turing machines It's a theorem that, although the Kolmogorov complexity of a string is relative to the Turing machine you're working with, it differs by at most a constant (basically the amount of space it takes to write an interpreter for Turing machine A inside of Turing machine B).

My question is: how does this theorem deal with the issue of Turing machines with purposefully inefficient encodings?

For example, suppose we have a universal Turing machine $M_{terrible}$ that requires its input to be repeated five times. It starts by verifying that the input is in fact of the form x ++ x ++ x ++ x ++ x, then executes the universal Turing machine $N$ on just x. Shouldn't this force the Kolmogorov complexity of strings relative to $M_{terrible}$ to be 5 times larger than they are relative to $N$? Why doesn't this violate the theorem?

You are stating the theorem incorrectly. The theorem states that the Kolmogorov complexity is the same up to a constant for essentially optimal description languages, which are those in which you can describe running a Turing machine on an input $x$ using $|x| + O(1)$ bits. Given this definition, it is a simple matter of playing with definitions to see that all such description languages result in the same notion of Kolmogorov complexity, up to an additive constant.


Describing the Language of a grammar in set theoretic notation where the length of strings need to be remembered I am not well versed in this topic so please pardon any ambiguous notation.
I am trying to describe the language of this grammar in set-theoretic notation.

The Grammar is given by:

$ S \rightarrow ASA|B$

$ A \rightarrow a|b$

$ B \rightarrow BC|\epsilon$

$ C \rightarrow a|b|c$

I think I can accurately describe this language in english:

If $w=xyz$ is a string and $xyz$ are substrings of $w$ then

$|x| = |z|$, and $x$ and $z$ are made up of symbols from $\{a,b\}^*$.

Furthermore, $y$ is made up of symbols from $\{a,b,c\}^*$

Mores simply, the strings are made up of two ends that are the same $|length| \ge 0$ and made up of symbols $a,b$. And the middle part of the string is made up of any symbols from $a,b,c$ and also has a $|length| \ge 0$

How do I more formally and accurately describe the language of the grammar $L(G)$? Is it possible to do this in a set-theoretic notation?

Your grammar generates $\Sigma^*$, where $\Sigma = \{a,b,c\}$.


Is the given grammar LALR We are given the following grammar.

S-->AS/b

A-->SA/a

We have to tell if its LALR or not.

As we all know that LALR is only minimization of CLR, So first I constructed the CLR parsing table using canonical collection of LR(1) items.

In the table there was no conflict.But There is no minimization possible.Does that mean that the given grammar is LALR as there are no conflicts.

The grammar is always LALR, if no merging is possible and in this case LALR = CLR, but when merging is possible, we have to see that if conflicts come up and if they do come up, grammar is not LALR and if they don't,the grammar is LALR.


Calculating genus of graph How to calculate genus of arbitrary graph? I am interested in any algorithm, even it based on full search.

One way that always works and is relatively easy to turn into code is Edmond's rotational embedding scheme. Let $G$ be a connected graph with vertices $V(G)=\{v_1, v_1, \dotsc, v_p\}$. For every vertex $v\in V(G)$ choose a permutation $\pi_v$ of the vertices adjacent to $v$. Then the collection of permutations $\pi_{v_i}$ determine an embedding of $G$ in a orientable surface $S_n$ of genus $n$, and, conversely, every embedding of $G$ in $S_n$ is determined by some collection of permutations as described above.

For example, consider $K_4$ with vertices labeled $\{1, 2, 3, 4\}$ and permutations
$$\begin{align}
\pi_1 &= (2\ 4\ 3)\\
\pi_2 &= (1\ 3\ 4)\\
\pi_3 &= (1\ 2\ 4)\\
\pi_4 &= (3\ 1\ 2)
\end{align}$$

The permutations will correspond to the counterclockwise order in which the adjacent vertices are encountered in the embedding (hence the term rotation). The permutations give rise to permutations, $\pi$, of the directed edges, defined by $\pi((v_i, v_j)) = (v_j, \pi_j(v_i))$. In the example above, we'll have
$$\begin{align}
\pi((2, 1))&=(1, \pi_1(2)) = (1, 4)\\
\pi((1, 4))&=(4, \pi_4(1)) = (4, 2)\\
\pi((4, 2))&=(2, \pi_2(4)) = (2, 1)
\end{align}$$
and we're back where we started, having generated a 2-cell $(2, 1, 4)$. Starting the process with the directed edge $(1, 2)$ gives rise to a 2-cell $(1,2,3,4,1,3,2,4,3)$ and we stop here, having used all 12 directed edges in $K_4$. We know that for an orientable 2-cell embedding in $S_n$ of a graph with $p$ vertices, $q$ edges, $r$ faces we'll have
$$
p-q+r=2-2n
$$
in this case we have $p-q+r=4-6+2=0=2-2n$ so $n=1$, meaning that $K_4$ has genus no larger than 1.

Of course, as presented this is a terribly inefficient algorithm, since there will be factorially many permutations for each vertex. There are some tweaks that will speed this up and there are some more modern approaches/modifications one could use (Edmond's paper came out in 1960), but the upshot is still that there's no efficient way to compute the genus of a graph.


Difference between cordic algorithm and table based methods for elementary functions computation In this book both Table Based methods and Cordic iterations are explained. computationally speaking i suppose the Table based is usually faster, even though it probably requires more resource, while Cordic is probably slower, but probably less resource consuming (if my understanding is correct, it should be a specific instance of shift and adds algorithm). But are there other benefits/drawback in both approach? I suppose also the CORDIC doesn't suffer of the table maker dilemma, even though it in general requires a LUT.

CORDIC uses small table to work, it calculates one bit at the time and being shift and add algorithm it is preferable when there are no multipliers available. Whenever multipliers are present, table based methods or power series are faster. Also one point worth notting - the scalling factor is also needed which sometimes is argument to use BKM, but this one is slower than CORDIC.

CORDIC is still used in x87 FPU, but nowadays Chebyshev polynomials are preferred way to compute special functions (or transcendental, but not elementary - this is rather bad name) (also do not consider Taylor here, it is very slow and works for small angles).

Drawbacks in both methods are increase in number of iterations and tables provided. Good to know how they work and grasp a piece of history, but not practical in software and not preferrable in hardware.


Practical applications of Weighted Independent Set in path graph? Consider Weighted Independent Set in a path graph, i.e., a graph where all the vertices are in a single path.

Does this problem have practical applications?  What are some?  This problem is used in many CS courses as an intro to the dynamic programming paradigm, but I don't see any mention about whether this is useful practically or whether it is only mentioned for didactic purposes.

I don't think that the weighted independent set problem in paths has many applications.  However, as you point out yourself, it is a very good introduction to dynamic programming and to algorithmic graph theory;  This is one of very many problems that are NP-complete on general graphs but become simpler (or indeed trivial) on restricted input instances.

When you know, and understand, the algorithm for (weighted) independent set in paths, it is not too hard to generalize this to (weighted) independent set in trees and even to graphs of bounded pathwidth and treewidth.

I think that this problem on paths (maybe even on trees, but here I'd love to be corrected) is purely educational.  Indeed, I have hard times finding reasonable applications to Independent Set as well as Vertex Cover, Clique and Dominating Set.


Circuit satisfiability problem : SAT-C to SAT-2C I have the following language : $L=\{\langle C_1,C_2\rangle \text{ | } C_1 \text{ and } C_2 \text{ are two circuits that calculate different function}\}$. We can call this language SAT-2C.

Prove that $L$ is NP-complete.

1) Proving that $L \in$ NP is pretty simple : given the values of $C_1$, $C_2$, it is possible to verify if the result is true or false. The time required to do so is probably linear to the size of the circuits.

I'm stuck at step (2) of my proof :(

2) Since we know that SAT-C is a NP-Complete, we can try the following reduction : SAT-C $\le_p$ SAT-2C.

So if we have a circuit $\langle c \rangle \in  \text{SAT-C}$, there must be a function $f$ that turns it into two circuits (if we want to prove that the reduction is possible)

$f(c) \rightarrow (c_1,c_2)$.

For example, if our circuit is $(a \land b)$ (logical AND).

The first circuit could be the same as c --- $c_1 = c = (a \land b)$.

But what about the second circuit? How can $c_2$ calculate a different function than $c_1$ BUT at the same time, allow a reduction from the other way (SAT-2C to SAT-C)?

Any helps or suggestions would be greatly appreciated!

You can use a reduction from $\text{3-SAT}$.

$\text{3-SAT}$ is the language of $\text{CNF}$ formulas where each clause has at most three literals, and they are satisfiable, meaning - given a formula $\phi$ in the correct form, it is in $\text{3-SAT}$ iff there exists $x$ for which $\phi(x)=1$.

Now, you want to show that the language of two circuits that calculate two different functions is $\text{NPC}$, therefore, given a formula $\phi$ which is satisfiable, you want to create a reduction that transform this formula into two circuits, that calculate different functions.

First, transforming a $\text{3CNF}$ formula into a circuit can be done in polynomial time. So - you can construct one circuit. You now need to think of the other circuit. As Yuval Filmus mentioned, think of a circuit of constant size. What circuit will guarantee that if $\phi$ is satsfiable, than that circuit will calculate a different function than $\phi$, but if $\phi$ is not satisfiable, it will calculate the same function exactly?

Most of the answer is given, you are only left to think of that circuit. If you want, ask in the comments and I'll edit it in.


Why is bipartite graph matching hard? I am reading on how solving maximum flow (Ford-Fulkerson) can be also used to solve unweighted bipartite graph matching problem. I think I don't understand the essence of this problem, because to me it seems trivial.

The method of solving the problem says to convert the original bipartite graph into a network, by creating a Source and Sink vertices, directing all edges towards the Sink and setting all edges' capacity to 1. Then I should run Ford-Fulkerson. Fair enough.

My question is, can't I just do this linearly? (Obviously not, but I don't see why). The goal of the problem seems to be to find a maximum matching in a complete bipartite graph - i.e. the maximum number of edges between the two "sections" of the graph that do not share any vertices.

To illustrate, see this picture

In the first graph the maximum matching will be 2 - any of the two vertices on the right may only be connected to a single vertex on the left. Since the edges are unweighted, it doesn't really matter which?
Similarly in the second graph, the matching will again be just 2.

Can you tell me where am I thinking wrong? I don't understand where the complexity of the problem comes from.

And sorry if any of the terms were used incorrectly, I am not studying CS in English. Thanks

I am reading on how [...] to solve unweighted bipartite graph matching problem. [...] The goal of the problem seems to be to find a maximum matching in a complete bipartite graph

No, the goal of the problem is to find a maximum matching in any unweighted bipartite graph.


How do we prove that $L_E = \{ \langle A, B \rangle : L(A) = L(B) \}$ is neither regular nor context-free? Let $A$ and $B$ be two deterministic finite automata. How do we prove that $L_E = \{ \langle A, B \rangle : L(A) = L(B) \}$ is neither regular nor context-free?

Intuitively, I feel that $L_E$ should not be context-free because we must try each string $\in \Sigma^*$ (where $\Sigma$ is the alphabet) and check if the string $\in L(A)$ or $\in L(B)$. However, this reasoning sounds informal to me. How do I formalize this proof?

One possible way, is to use the pumping lemma, but one needs to be careful about the details. For simplicity let's discuss only the pumping lemma for regular languages (but I believe a similar method can be used when considering the CFL-pumping lemma).

Let's assume that $\langle A \rangle$ is a well-defined way to encode DFAs, that begins with describing the number of states, then list the transition for each state, etc.
Also assume that any string that is not "well formatted" under this encoding just describes a DFA that rejects all words.

Let $n$ be the pumping length.

Let $A=B$ be a $2^n$-state DFA that accepts all words. The encoding of $A$ begins with stating it has $2^n$ states, that is the first part is of length $\log(2^n)=n$ bits at least.

Now let's use the pumping lemma on $w=\langle A,B\rangle$ (which is longer than $n$, so the pumping lemma applies). We can split $w$ into $xyz$ such that $|xy|\le n$, that is, the part we pump "lies" in the part that describes the amount of states in $A$.
Now, we pump the word down. That is, consider the words $w'=xz$ which should be also in $L_E$ by the pumping Lemma.

However, we can interpret $w'$ as being $w'=\langle A',B\rangle$ where $A'$ is a malformed encoding (it begins with stating the DFA has less then $2^n$ states, but then it describes transitions of $2^n$ states, which is inconsistent with the claimed number of states).

Therefore, by our assumption $L(A')=\emptyset$ while $L(B)=\Sigma^*$. Thus, $\langle A',B\rangle \notin L_E$ and we reached a contradiction.


Worst case scenario in binary search tree retrieval Well, i have a binary search tree $T$ that is equilibrated by height witch has $2^d+c$ nodes ($c<2^d$).
What is the number of comparisons that will occur in the worst case scenario, if we ask whether $k\in V(T)$ and why does it arise?

Hint: If the tree has height $h$ then the worst number of comparisons is ...? If the tree is "equilibrated by height" (I guess balanced) and has $n$ nodes then its height is ...?


What is the space complexity of Dijkstra Algorithm? As per my understanding. The space complexity will be O(V). An array of V nodes will be created which in turn  be used to create the Min heap.

But this link is stating that It is O(V^2)? I don't understand how it can be O(V^2)?

I have search the same topic in the Book entitled Introduction_to_Algorithms by  Thomas H. Cormen  but still not able to find the answer.
I Don't understand what I am missing.

Dijkstra's algorithm can be implemented in many different ways, leading to resource usage. The page you link gives the resource usage the implementations in the specific library being described.

I can't think of a way of implementing Dijkstra to use $|V|^2$ space, but I would note two things.

$O(\cdot)$ only gives an upper bound. Even if the implementation actually uses space $O(|V|)$, it's not wrong to say that it uses $O(|V|^2)$ or even $O(2^{|V|})$, just as it's not wrong to say that I earn less than a billion dollars a year. However, it would be unusual to say $O(|V|^2)$ if it was easy to prove the stronger bound of $O(|V|)$ (I also earn less than a million dollars a year), and it is easy to prove $O(|V|)$ for most implementations of Dijkstra.
The page quotes the running time as $O(s|E|\log|E|+V)$, where $s$ is the number of sources being considered. It's easy to imagine space usage of $O(s|V|)$ so maybe they wrote $O(|V|^2)$ since $s\leq|V|$.  But that would also be strange, given that the quoted running time shows they're not afraid to use $s$.