שאלות ותשובות - Wet 2 Frequently Asked Questions - Wet 2 Вопросы и Ответы - Wet 2 أسئلة وأجوبة - Wet 2
Last Update: 15.1.2012
- 15.1: Added Implementation: 2
- 11.1: Added Implementation: 1
- 2.1: Added General Questions: 1,2,3,4,5
|
|
|
General Questions |
|
|
1. Do we have to give two different implementations, one for part A and one for part B? |
No.
Once you solve the assignment, you will see that the two parts are actually independent.
That is, to solve part B you will only have to add additional data structures that are (almost) independent of the implementation of part A.
If you solve part A correctly, your solution to part A will not violate any time complexity requirement of part B.
You will only need to add additional structures to support the TowersOfHeightBetween() function.
|
2. In AddCube(), what happens to a cube after it is added? | |
A new cube is not attached to any existing tower, it is added as an independent tower containg only itself.
|
3. What is the height from ground of a newly added cube? | |
After adding a cube, it is placed on the floor. HeightFromGround() should return 0.
|
4. In PutOnTop, do the cubes cubeUp and cubeDown have to be the lowest or topmost cubes in their towers? |
No. They can be any cube in the tower.
The function PutOnTop puts the tower containing cubeUp on the tower containing cubeDown, if possible.
|
5. Part B: Is the O(log n) requirement on PutOnTop, TowerHeight and HeightFromGround worst case or amortized? | |
In part B, all of the 3 functions stated must run in O(log n) worst case.
|
|
|
|
|
Implementation |
|
|
1. What should PutOnTop(cubeUp,cubeDown) return if cubeUp == cubeDown or if the blocks belong to the same tower? | |
In the cases specified above, the function should not do anything and return FAILURE.
|
2. What should TowersOfHeightBetween() return if (sectionB == false) and one of the parameters that were sent to the function were invalid? |
The function TowersOfHeightBetween() should return the following error codes according to this order:
- The function should first check whether the input is illegal (DS == NULL, num == NULL, min < 0, max < 0 or min > max) and if the input is illegal, return INVALID_INPUT.
- Then, the function should check if (sectionB == false). If so, the function should return FAILURE.
- If any other failure (besides allocation errors) occurs after that, the function should return FAILURE.
- Otherwise, the function should return SUCCESS.
As some of you asked, notice that (min == 0) or (max == 0) are considered legal inputs.
The output of the function for inputs (min = 0,max = 10) and (min = 1, max = 10), for example, should be the same.
If an allocation error occurs at any point, the function should immediately return ALLOCATION_ERROR, disregarding the previous order of error codes.
There is no need to correct your data structures once an allocation error occurs.
You may assume that the code will halt once an allocation error happens.
|
|
