# Tag Info

### can we computably list every primitive recursive function?

The primitive recursive functions can be defined in terms of the following five axioms: Constant function: $C_n^k$ is a $k$-ary function that always returns $n$ Successor function: $S$ is a 1-ary ...
• 16.1k

### "Entrance exam" homework assignment for 3rd-year algorithms?

I see three issues that are going to come up for you: Undergraduate courses in Canada do not have entrance exams. If you expect and encourage students to drop the course because they did not complete ...
• 141
Accepted

### "Entrance exam" homework assignment for 3rd-year algorithms?

I am a teacher in 2nd year in a generalist scientific formation for engineers, and I would expect my students to be able to do that in less than one hour after one semester, so I think this is ...
• 15.4k

### Pseudo random permutation of a very large number of elements

Assuming you want the entire permutation, or a significant portion of it, the following algorithm which I call RadixShuffle is an efficient and simple way to shuffle larger-than-memory (or even larger-...
• 13.4k

### Will CSR format store the all 0 column?

Most sparse matrix representations are not shape-preserving for all inputs. You have to store the shape of the matrix separately.
• 13.4k
Accepted

### can we computably list every primitive recursive function?

I'll build on Pål's answer to be a bit more explicit about how we can code PR functions using those operations. First of all, note that we can code any finite sequence of (positive) numbers into a ...
• 2,509

### Is Group Theory useful in Computer Science in areas other than cryptography?

Group theory is used all over the place in quantum computing. Some examples: The set of reversible quantum logic gates on $n$ qubits is the group $SU(2^n)$. Some important finite groups of quantum ...
• 131
Accepted

### Compute matrix inversion / multiplication using a black box

It was shown in 1969, by Strassen, that matrix multiplication and matrix inversion have the same computational complexity. Details can be found on Wikipedia.
• 15.4k

### "Entrance exam" homework assignment for 3rd-year algorithms?

8-Puzzle is a classic textbook problem that has been used both in many standard algorithm design books as well as in classical AI books such as Artificial Intelligence: A Modern Approach, by Russell ...
• 565
Accepted

### Tree algorithm - arrange integer array numbers to form largest number

I'd like to say good work on the soluton! It's a nice attempt you have converting it to a tree as well, and I think a tree can be used in some way. However, I think using specifically an N-ary tree, ...
• 155

### Weisfeiler-Leman Algorithm

No, because you don't actually get a mapping between graphs (at least not vertex-to-vertex mapping, but you do get a mapping between automorphism groups). As always with the Weisfeiler Leman graph ...
• 16.1k

### Algorithms for stacking gage blocks

If you are looking for the sum of the blocks to be below the target size, you are talking about the 0/1 Knapsack problem. In your case, it seems that all profits are unit values. Alternatively, if you ...
• 565

### Graph labyrinth solving sequence

Let $G_1, \dots, G_m$ be an enumeration of all strongly connected directed graphs on at most $n$ vertices in which every vertex has out-degree 2 (the corresponding edges labelled $a,b$). The algorithm ...
• 277k
1 vote

### Set partitions and integer partitions

It should help to see that if $(S_1, …, S_k)$ is a set partition for input $(X, n_1, …, n_k)$, then $(S_2, …, S_k)$ is a set partition for input $(X\setminus S_1, n_2, …, n_k)$. Now you just need to ...
• 15.4k
1 vote

### Is this depth search correct (DFS) Shouldn't one act according to the LIFO principle?

It depends on the order of the children. It is usually the case that children in rooted trees are browsed from left to right. Also, if the DFS is written recursively, then this is indeed the correct ...
• 15.4k
1 vote

### Efficient algorithm to compute the Heesch number of a shape

Look at this paper Casey Mann, and B. Charles Thomas (2016) Heesch Numbers of Edge-Marked Polyforms In this article, the results of a computerized search for edge-marked polyforms (tiles formed from ...
• 111
1 vote

### Assigning classes to nodes in a graph to minimise intra-class distance

For the hardness proof, you can look into graph coloring (or its variants). Here's a possible hint: Once you prove it is NP-hard, using ILP is not a bad idea. There are various techniques you can ...
• 565
1 vote

### What is the relationship among the various algorithms?

Here is a handy categorization from wikipedia and a list of few popular algorithmic topics.
• 565
1 vote

### Given a $n \times n$ matrix $M$ find a subset of d rows and d columns so that the sum of the elements in their intersection in maximized

It is NP-hard, by reduction from the maximum balanced biclique problem. Suppose you have a bipartite graph $G$, and the goal is to test whether there is a balanced biclique of size $d$. Let $M$ ...
• 159k
1 vote

### How to find largest caterpillar in a tree

Hint: the heaviest caterpillar that can be formed by a path starting at a node and moving strictly downward in the tree (its down-weight) is the down-weight of the heaviest non-leaf child if it ...
• 13.4k
1 vote

### What is the computational complexity of the following problem

What’s the solution for N = 12m + 2, 3, 5, 6, 7, 8, 10, 11? You can prove that no solution exists or find a solution in O(log N). You can find the smallest solution in O(log N log log N) or more ...
• 30k
1 vote

### Is this bayesian average calculation right?

There's nothing wrong with the formula. It's doing exactly what you told it to do. I suspect you might have a misunderstanding of how to apply the Bayesian average. By setting ...
• 159k
1 vote

### How to correctly learn algorithms?

A good text (even available for free) is Jeff Erickson's "Algorithms". No, there is no solution manual. Algorithms is a required subject in the ACM/IEEE recommendations, you'll find lots of ...
• 14k
1 vote

### DFS to assign guards to nodes in a tree structure

This looks like the dominating set problem, but in a tree. If the tree has two nodes or more, note that it is never interesting to put a guard in a leaf, because putting the guard in its parent will ...
• 15.4k

Only top scored, non community-wiki answers of a minimum length are eligible