Algorithms - Lab 4, Problem 1

Introduction

This is a hand-in written by Group 7 (FIRE) for the Algorithms course (TIN092) at Chalmers University of Technology.

Group 7 consists of:

  • Mazdak Farrokhzad

    • 901011-0279

    • twingoow@gmail.com

    • Program: IT

  • Niclas Alexandersson

    • 920203-0111

    • nicale@student.chalmers.se

    • Program: IT

a) As few classrooms as possible

The number of rooms required to schedule a number of lectures is equal to the largest number of lectures which occur at the same time. It is trivial to see that this is the lower bound for the answer; if there are \(k\) lectures which occur at the same time, then there must also be at least \(k\) rooms available in order to be able to schedule them all in separate rooms. Intuitively, if we see time as a line with different levels, and each of the levels represent a room, and then go from left to right trying to place legtures as “far down” as possible, the only reason for placing a lecture at level \(m\) would be if it conflicted with lectures on all the \(m-1\) levels below. Therefore, the upper bound will also be the largest number of lectures colliding at the same time.

We therefore write an algorithm that given a set of lectures, returns the largest number of simultaneously colliding lectures. The algorithm goes through all lectures in start time order, and compares them against the set of lectures which the previous lecture collided with, to see if they also collide with these. The algorithm then returns the size of the largest set of colliding lectures encountered.

def efficient_lsp(courses): courses <- sorted(courses, key=lambda c: c.start()) collisions <- priority_queue(sorted: key=lambda c: c.finish()) maxcol <- 0 for i in courses: while len(collisions) > 0 and !collides(i, collisions.peekFirst()): collisions.removeFirst() collisions.add(i) maxcol <- max(maxcol, len(collisions)) return maxcol

[H]

[1] \(collisions.removeFirst()\) \(collisions.add(i)\)

We assume that we have access to a priority queue with operations \(peekFirst() \in \ordo{1}\), \(removeFirst() \in \ordo{\log{n}}\), and \(add() \in \ordo{\log{n}}\). This can be achieved through using a heap.

To calculate the complexity of the above algorithm, we must realise that the body of the inner loop will only execute a total number of times equal to the total number of elements placed in the collisions queue. Since no element is placed in the collisions queue more than once, this means that this number cannot be greater than \(n\), and since the last element is always added after the loop condition is checked the last time, we get that in fact, it cannot be greater than \(n-1\). The loop condition of the inner loop will be evaluated the number of times that the inner loop body is run, plus one more per iteration of the outer loop. This gives us the complexity function:

\[\begin{aligned} T(n) &= c_0 + n\log{n} + (n-1) (c_1 + \log{n}) + n (c_1 + c_2 + \log{n})\\ &= 3n\log{n} + n (2c_1 + c_2) - \log{n} + c_0 - c_1\\ &\in \ordo{n\log{n}}\end{aligned}\]