6 votes

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 ...
Pål GD's user avatar
  • 16.1k
4 votes

"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 ...
Zack Wolske's user avatar
4 votes
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 ...
Nathaniel's user avatar
  • 15.4k
4 votes

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-...
orlp's user avatar
  • 13.4k
3 votes

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.
orlp's user avatar
  • 13.4k
3 votes
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 ...
Steven Stadnicki's user avatar
3 votes

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 ...
shashvat's user avatar
  • 131
3 votes
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.
Nathaniel's user avatar
  • 15.4k
2 votes

"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 ...
codeR's user avatar
  • 565
2 votes
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, ...
Minko_Minkov's user avatar
2 votes

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 ...
Pål GD's user avatar
  • 16.1k
2 votes

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 ...
codeR's user avatar
  • 565
2 votes

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 ...
Yuval Filmus's user avatar
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 ...
Nathaniel's user avatar
  • 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 ...
Nathaniel's user avatar
  • 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 ...
Ivan Z's user avatar
  • 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 ...
codeR's user avatar
  • 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.
codeR's user avatar
  • 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$ ...
D.W.'s user avatar
  • 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 ...
orlp's user avatar
  • 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 ...
gnasher729's user avatar
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 ...
D.W.'s user avatar
  • 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 ...
vonbrand's user avatar
  • 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 ...
Nathaniel's user avatar
  • 15.4k

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