 |
.. (לתיקייה המכילה) | |
Last Update: 29.12.2011
- 19.12: Added 1.
- 22.12: Added 2,3.
- 26.12: Added 4,5,6.
- 29.12: Added 7.
- 31.12: Added 8.
- 19.12: Added 1.
- 22.12: Added 2,3.
- 26.12: Added 4,5,6.
- 29.12: Added 7.
- 31.12: Added 8.
1: Do we have to prove O(1) amortized time per operation in question 3, part b using BOTH the potential method and accounting method, like 3a? | |
| No, you do not need to prove 3b with both methods. You can use either method. You are only required to prove bounds using all the methods in 3a. |
2: We have a midterm. Can you postpone the deadline? | |
|
Please read the late submissions section in the course information sheet (can be found under Syllabus). The due date of the assignment is 2.1.2012, 14:00. All the late submissions (justified or not) will be counted from this time. |
3: In question 1-B: can we disprove by showing an example on an AVL tree? | |
|
An AVL tree (as a tree) is indeed a binary search tree. As a data structure it is not a binary search tree but an extension of one: The add/remove operations on an AVL tree are not identical to these operation on a regular binary search tree. If you want to disprove, you'll have to find an example for a regular binary search tree (the add/remove operations are the basic ones we learned- without any rotations). |
4: In question 3-A: What does it mean the amortized time complexity of EnQ and DeQ TOGETHER? | |
|
We defined amortized time as: "Let F be a set of commands. We say that the amortized time of F is O(g(n)) if every m sized series of commands from F takes a total time of O(m*g(n)) " In this question F = {EnQ,DeQ}. |
5: In Question 3-A: | |
|
No. You are not allowed to use anything but the data structure Stack and it's given commands. You are not allowed to use arrays, pointers, integers and any other variable that is not a Stack. |
6: In question 2-C: Can you explain what S in the function Delete-Old() stands for ? | |
|
When Delete-Old() is called, S is: sum(d(p)) {foreach page p which is currently in the Data-Structure} If a page was removed, it will not be included in the "calculation" of S for the next Delete-Old commands (unless it will be inserted again). |
7: In question 3-B: what is the running time of splitting a node/borrowing a node/merging two nodes? | |
|
You may assume that the running time of all three actions is 1 (that is, t_i = 1 for these three actions). We can arbitrarily define t_i=1 because if the maximum t_i is some constant c, then the same proof with the potential function phi=(2*n_4+n_2)*c will work. |
8: In question 2-C: Should we delete only nodes that were leaves when the delete-old function was called or do we need to also delete nodes that became leaves during the process of the function? | |
| Only nodes that were leaves when the delete-old function was called will be candidates for deletion in this call. |