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 1010 rooms in the hotel, and 44 visitors arrive every day, what is the expected waiting time for a newly arriving visitor on day t+1t+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)O(n).

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