All Questions
7 questions
0
votes
1
answer
60
views
Convert nested recursive algorithm (Ackermann's function) to iterative algorithm
I came across a practice problem:
I already wrote out the pseudocode for this, really easily too, just made the calls to the function as mention in the problem statement. But I was really struggling ...
- 315
43
votes
7
answers
7k
views
Theoretically can the Ackermann function be optimized?
I am wondering if there can be a version of Ackermann function with better time complexity than the standard variation.
This is not a homework and I am just curious. I know the Ackermann function ...
- 3,834
8
votes
1
answer
501
views
Understanding Grossman & Zeitman's algorithm for computing the Ackermann function?
I've read the paper An inherently iterative computation of Ackermann's function, published by Grossman & Zeitman in which they present an algorithm which optimizes Ackermann's function.
We know ...
- 147
1
vote
1
answer
546
views
How can I optimize Ackermann Function?
I am required to find an optimization for the Ackermann function and explain the problem with the Ackermann problem itself. However, I'm not really sure where I should start. I understand that ...
- 147
3
votes
1
answer
2k
views
How to write Ackermann Function iteratively?
I wrote a recursive version of Ackermann Function, and it worked properly:
int ackermann_r(int m, int n) {
if(m == 0) {
return n + 1;
} else if(n == 0) {
return ackermann_r(m -...
- 83
4
votes
2
answers
2k
views
It is possible to compute recursive ackermann(m,n) function with args m>=4 and n>=1 in python without exceeding max recursion depth?
It is possible to compute total computable recursive function ackermann(m,n) with arguments m>=4 and n>=1 in python without exceeding max recursion depth?
def ackermann(m,n):
if m == 0:
...
- 181
6
votes
1
answer
10k
views
Why is the Inverse Ackermann function used to describe complexity of Kruskal's algorithm?
In a class for analysis of algorithms, we are presented with this pseudocode for Kruskal's algorithm:
He then states the following, for disjoint-set forests:
A sequence of m MAKE-SET, UNION, and ...
- 141