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

# Greedy Scheduling

Consider the problem of scheduling `n` jobs on a 3D printer. The turnaround time for a job is the total time from when it arrives to when it finishes printing. Suppose that all jobs arrive at the same time, and that we know the time that job `i` will take time `tᵢ` to print once started on the printer. Prove that scheduling the jobs in greedy order (i.e. shortest job first) minimizes the average turnaround time.

# Disjoint Sets

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.

# Dynamic Programming

(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.