All Questions
21
questions
2
votes
0
answers
76
views
the Ackermann function must be total and unique based on one specific list of rules
This is one following question based on one question I asked before.
In mcs.pdf, it has Problem 7.25 in p251(#259).
One version of the the Ackermann function $A:\mathbb{N}^2 \to \mathbb{N}$ is ...
- 416
0
votes
1
answer
84
views
partial function version of the Ackermann function must be total
In mcs.pdf, it has Problem 7.25. (I only solve somewhat important problems referred to in the chapter contents because I have learnt one Discrete Mathematics book before and read mcs to ensure no ...
- 416
-2
votes
2
answers
102
views
i need help with this recursive problem: $T(n) = nT(n-1) + 1$, $T(0) = 0$. [closed]
Now here I solved everything but I’m now stuck at the general form how am I gonna write the general form with the (pi) product summation ?
Hint there’s something related also with combination and ...
- 11
1
vote
0
answers
54
views
Time Complexity Calculation - Is my approach correct?
Give the running time in terms of n.
...
0
votes
1
answer
50
views
Struggling with a recursive expression
So I was looking into recursive expressions and recently dealt with this expression:
$$ f(i) = q \times (f(i-1)+1) + \bar{q} \times f(i-1) $$
where $q$ is a probability between $0$ and $1$ and $\bar{q}...
- 1,419
2
votes
2
answers
269
views
Understanding the definition of primitive recursion.
I'm a little (truthfully really) lost with the definition of primitive recursion. Here is the definition for primitive recursive functions that we have in our course (translated from German):
The ...
- 1,928
1
vote
0
answers
42
views
How to understand definition of $\Pi_k=co-\Sigma_k$ in infinite Kleene arithmetical heirarchy
Am reading a text about computability theory (or recursion theory), and according to the text, at each level $k$ of the Kleene arithmetical hierarchy, we have two sets, $\Sigma_k$ and $\Pi_k$, where $\...
- 735
0
votes
1
answer
60
views
Resolve recursive dependences using substitution method
Resolve recursive dependences using substitution method and prove it with mathematical induction:
...
- 153
1
vote
1
answer
204
views
Solving a recurrence with 2 recurrences
I am trying to solve the following recurrence:
$$T(n) = T\Big(\frac{n}{3}\Big) + T\Big(\frac{2n}{3}\Big) + O(n)$$
I do not want to use the Akra-Bazzi method nor draw out a recurrence tree. I do know ...
user137720
3
votes
1
answer
686
views
Is this the correct minimum number of coins needed to make change?
The Problem: On Venus, the Venusians use coins of these values [1, 6, 10, 19]. Use an algorithm to compute the minimum number of coins needed to make change for 42 on Venus. State which coins are used ...
- 1,884
0
votes
1
answer
64
views
How would you apply the Greedy technique in this situation/why wouldn't it work?
I am going over the Rod Cutting Problem
The author states "Selling a rod of length $i$ units earns $P$[i] dollars."
Here is the table $P$ for this problem
I'am currently going over this question ...
- 1,884
0
votes
1
answer
35
views
Why is $X_m$ and $Y_m$ not included in the shaded region(where median can lie)?
This problem is from Algorithms, problem 2
The Problem Given two sorted list of numbers $X$[1..$n$] and $Y$[1..n]. we need to come up with a O($\log n$) time algorithm to find the median of the 2$n$ ...
- 1,884
3
votes
1
answer
1k
views
How to show that recurrence $T(n) \in \Omega(n^{0.5})$ using proof by induction?
This is recurrence $T(n)$
$ T(n) =
\begin{cases}
c, & \text{if $n$ is 1} \\
2T(\lfloor(n/4)\rfloor) + 16, & \text{if $n$ is > 1}
\end{cases}$
This is my attempt to show that $T(n) \in \...
- 1,884
0
votes
2
answers
61
views
Does this recurrence relation run in $ \Theta(n) $?
This is the recurrence relation I am trying to solve:
\begin{align}
T(n) & = 2 \cdot T \left( \frac{n}{4} \right) + 16, \\
T(1) & = c.
\end{align}
I broke this down (i.e., solved this ...
- 1,884
5
votes
1
answer
2k
views
The Ackermann's function "grows faster" than any primitive recursive function
I am looking at the proof that the Ackermann's function is not primitive recursive.
At the part:
"We will prove that Ackermann's function is not primitive recursive by showing that it "grows ...
- 14k