UNB/ CS/ David Bremner/ teaching/ cs3383/ assignments/ CS3383 Assignment 7

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.