## Introduction

See the general rules about assignments in this course.

**DUE**: 2016-11-14, 16:30 in the assignment box.

## Questions

**1** Consider the following alternative implimentation of the
disjoint-sets data structure.

```
makeset ( j )
w[j] ← 1
parent[j] ← j
end
find(key)
if parent[key]≠key then
key ← find(parent [key])
end if
return key
end function
union ( x, y )
x ← find(x)
y ← find(y)
if w[x] > w[y] then
parent[y] ← x
w[x] ← w[x] + w[y]
else
parent[x] ← y
w[y] ← w[x] + w[y]
end
end
```

Prove that after any sequence of makeset and union operations, `find(x)`

takes `O(log₂ n)`

time.

**2** (Based on an exercise in Dasgupta et al.)

You are driving across Canada, on the the Transcanada Highway. There
are hotels at kilometer `a₁ < a₂ < … < aₙ`

. You need to choose a
hotel to stop at every night, with the restriction that on the last
night you have arrived at kilometer `aₙ`

. You have a strange car
rental agreement that allows you to drive 500 km a day, but penalizes
you `(500-x)²/500`

dollars if you travel more or less than that in a
day. Give an efficient algorithm to determine the sequence of hotels
that minimizes the total penalties, assuming that only you travel
forward each day.

Explain your algorithm's correctness, and analyse its time complexity.