BBM408 - Algorithm Analysis

Assignment 2 - Due 26 April 2022

Questions

Question 1

You are given a straight street with a bunch of homes on it. You have to place a fire hydrant somewhere on the street, such that the total distance between each home and this hydrant is minimal. Explain how you would select the location of the hydrant and argue your solutions running time with respect to the number of houses.

Example scenario:

1------2---3-----F----4---------------5----------6
\-------D1-------/
       \----D2---/
           \--D3-/
                 \-D4-/
                 \--------D5----------/
                 \-------------D6----------------/

D1+D2+D3+D4+D5+D6 must be minimal

Question 2

Consider a hotel that places visitors to rooms after hashing (simple uniform) their names and assigning them to the room with their hash result. For example, if your name is hashed to 117, then you have to stay in room 117. However, if the room is busy, you are placed on a waiting list for that room. Each visitor is expected to spend 1 to 5 days in the room, with a uniform distribution. Assuming there are $10$ rooms in the hotel, and $4$ visitors arrive every day, what is the expected waiting time for a newly arriving visitor on day $t+1$ ?

Question 3

Show that the notion of a randomly chosen binary search tree of n nodes, where each tree is equally likely to be chosen is different than the randomly built binary search tree covered in the lecture. (Hint: Show that they are different for n=3).

Question 4

a. Consider a stack of fixed capacity k, where we copy the stack contents to another stack for backup purposes every k operations. For example, if k is 5, after 4 push and 1 pop operations, we copy all stack contents to another stack (assume the stack is implemented using an array and you are just copying the array contents). If the stack is full, the next push operation is ignored, and if the stack is empty, the next pop operation is ignored. In both cases, the cost is assumed to be 0. Show that the cost of n stack operations is $O(n)$ .

b. Now consider a stack of size 2k and solve the problem, again. You still make a backup every k operations.

Answers

Question 1

The optimal location is determined by the median of the houses locations on the street. There are two potential cases:

There are an even number of houses: We place the hydrant on the lower median or upper median or in between. Then, moving the median left or right for X meters makes it get closer to n/2 houses X meters each, and farther from n/2 houses X meters each. Therefore, the total distance doesn't change. When you get past the lower or upper median, however, you start getting closer to $n/2 - 1$ houses and farther away from $n/2+1$ houses. Therefore, the total distance is changed by $(n/2-1)*(-X) + (n/2+1)*(+X)=2X$ , and gets away from the optimal.
There are an odd number of houses: The we place the hydrant in front of the median house. Then, moving in either way gets closer to $(n-1)/2$ houses and farther from $(n-1)/2+1$ houses. The total distance is affected by $(n-1)/2*(-X)+((n-1)/2+1)*(+X)=X$ , and the hdyrant gets away from the optimal location.

Question 2

Since there are 10 rooms in the hotel and 4 visitors are arriving each day, and the hasing is uniform, the expected visitor load per room per day is $4/10 = 2/5$ . Since each customer spends from 1 to 5 days, uniformly, the expected time spent per customer is $(1+5)/2=3$ . Hence, each day, each room is loaded with $2/5*3 = 6/5$ days of stay. At the end of each day, 1 days of stay is removed from each room, leaving an expected $6/5-1 = 1/5$ days load per room. After t days, the load accumulates to $t/5$ days of wait. So, on day $t+1$ the first customer is expected to wait for $t/5$ days before he gets in his/her room.

Question 3

For n=3, let's assume the keys are 1,2 and 3. With 3 keys, we have the following trees possible:

  A       B      C       D      E
  1       1      2       3      3
   \       \    / \     /      /
    2       3  1   3   1      2
     \     /            \    /  
      3   2              2  1

So, out of 5 possible trees, we can choose 1.

However, if the input is randomized, then,

1-2-3: A 1-3-2: B 2-1-3: C 2-3-1: C 3-1-2: D 3-2-1: E

For each permutation, we get the above trees. One can easily see that, the possibility of getting tree C is not 1/5 as in the previous case. It is actually 1/3 with randomly built BST.

Question 4

a. The actual cost of push, pop and copy are 1, 1, and k, at most. The fact that sometimes push and pop can be worth 0 cost, doesn't really change the following argumentation. We can assign the amortized costs of 2, 2 and 0 to these operations. The 2 on push is 1 for the actual push, 1 for the upcoming copy, the 2 on pop is 1 for the actual pop and 1 for the upcoming copy operation. This way, every k operations, we accumulate an additional k payment to be used for the copy operation (even when there are less items in the stack). Therefore the copy operation itself can be executed with no amortized cost. Considering n operations the amortized cost becomes O(n).

b. This time we will use amortized costs of 3,3, and 0. Now, the 1 of 3 is for the actual push, and 2 is reserved for the copy. Same with the pop operation. Therefore, every k operations, we accumulate 2k payment for the copy. And the overall running time is still O(n).