@evinda nearly any nontrivial problem/ algorithm would probably work as a counterexample. a nice algorithm in this area, try fibonacci sequence. what can you say about memoization & recursion vs bottom-up in general? eg for fibonacci? do any of those terms mean anything to you?
see your participation in Mathematics... are you in undergraduate CS?
@vzn Hello :) I am an undergraduate student in applied mathematics. What's with you? :)
If we want to calculate the Fibonacci sequence fib(n) with memoization and recursion, we woud call this, and it would call fib(n)=fib(n-1)+fib(n-2), which would call fib(n-1)=fib(n-2)+fib(n-3) and so on, which would call fib(2)=fib(1)+fib(0)=1+0=1. Then it would finally resolve fib(3)=fib(2)+fib(1), but it doesn't need to recalculate fib(2), because we cached it, then it will resolve f(4)=f(3)+f(2), but it doesn't need to recalculate fib(3) and so on...
@evinda From what I know, Time complexity and space complexity would be same. But in case of fibonacci you can optimise dynamic programming solution by caching only last two elements while iterating and that will reduce the space complexity to constant and same time complexity as before.
Hello!! I am asked to state the two versions of the Knapsack problem and their differences. Could I formulate it as followed??
The Knapsack problem is the following:
There are $n$ items, where the ith item has a benefit of $v_i$ and it has weight $w_i$. We want to pick some items so that we maximize the total benefit while keeping the total weight of $W$.
The difference between the integer and the fractional version of the Knapsack problem is the following:
At the integer version we want to pick each item either fully or we don't pick it. At the fractional version we can take a part of …
I know that Physically based rendering means we try to simulate how light actually works in real world and global illumination is bouncing back of light when it strikes a surface. But what's actual difference between them and how are they related?
I have to determine if the proposition "Polynomial: good, exponential: bad" is right and justify my answer. Could I say the following? Suppose that we have input of size n and we want to run an algorithm to get an information about the input. Since (n^a) subset of O(b^m), a,b,m,n in N, the exponential algorithm will require more time to terminate, and so the proposition is right.
There are two versions of the Knapsack problem, the integer and the fractional one.
With what type of programming can these two versions be solved??
Which of the two versions has the optimal substructure property ??
Which of the two versions has the greedy choice property ??
Why in computer science any complexity which is at most polynomial is considered efficient?
For any practical application(a), algorithms with complexity $n^{\log n}$ are way faster than algorithms that run in time, say, $n^{80}$, but the first is considered inefficient while the latter is effici...
I want to write a O(n*lg k) time algorithm in order to merge k sorted lists into one sorted list, where n is the total number of the elements in all the input lists.
I tried the following: We create an array with k elements, where A[i] is the firstunused element of the ith list.We create a k-sized heap and we put in the heap the first elements of the k lists. Then we repeat the following steps, while the heap isn't empty. 1. Minheapify 2. Delete the root of the heap and put it in the output list.
I know that Physically based rendering means we try to simulate how light actually works in real world and global illumination is bouncing back of light when it strikes a surface. But what's actual difference between them and how are they related?
There are two versions of the Knapsack problem, the integer and the fractional one.
With what type of programming can these two versions be solved??
Which of the two versions has the optimal substructure property ??
Which of the two versions has the greedy choice property ??
