.. (לתיקייה המכילה) | ||
Last Update: 20.05.2012
- 20.05: Added #6
- 16.05: Added #5.
- 15.05: Added #3 and #4.
- 12.05: Added #2.
- 11.05: Added #1.
- 06.05: Opened FAQ
- 20.05: Added #6
- 16.05: Added #5.
- 15.05: Added #3 and #4.
- 12.05: Added #2.
- 11.05: Added #1.
- 06.05: Opened FAQ
1. In Q.2 Seif B , do we have a pointer to the minimal and maximal elements or only their values? | |
Only their values. |
2. In Q.6 it was written that no bound is given on some input values, hence they cannot be stored in an INT type variable , how do we deal with that ? | |
You are implementing a theoretical data structure and there is no meaning asking whether the input is small enough to be stored in an INT typed variable. Please make sure you understand the difference between theory and practice. You can assume, as you did in some previous courses that adding two numbers can be done in constant time. |
3. Question 2c: Can we make any assumption about the trees T_1,...,T_k? | |
Yes. As announced, you may assume that for every height h, there are at most 2 trees T_i,T_j of height h. |
4. In Q.1-a-gimel , does "n" refer to number of leaves in the 2-3 tree or the number of nodes ? | |
In this question you will get the same result when n denotes either number of leaves or number of vertices in the graph. Yet,consider n as the number of vertices in the 2-3 tree |
5. In Q.4 seif B in the given potential function , does n stands for the size of the array or the number of elements in the data structure ? | |
As a convention , n usually stands for the number of elements in the data structure. So does it this time. |
6. In question 4b, we're a little confused by the potential definition, and how we're supposed to take the change of n into account. Can you help? | |
Sure. Call the size of blocks after organizing the array k. That is, you have k blocks, with k elements each and k free cells each. Therefore the size of the array is 2k^2 and we have 2k^2 >= n >= k^2. In other words, sqrt(n/2)<=k<=sqrt(n). Using the above, if you take the potential to be some constant c times the potential we gave in the hint, you should be able to show an amortized cost of O(sqrt(n)) using the potential method. Another possible potential function, easier to analyse, is c*sqrt(n)*maximum(number elements in block - k). Notice that after reorganizing your array, the potential drops down to zero. Good Luck! |