Homework D

This homework is due 2011-12-15, at 13.15. Drop it off by Mikael Goldmann's mailbox at Lindstedtsvägen 3.

The solutions must be printed, not handwritten. Solutions handed in late are not accepted and will not be graded.

Please remember that solutions need to be in English.

Important notes

Some of the problems in this homework set deal with amortized analysis. This is not covered in the course notes, so hand outs were given in class. These handouts are available outside the CSC student expedition on Osquars backe 2.

When asked for algorithms, describe in sufficient detail to make them precise, either in words or pseudo code, but not in an actual programming language as syntax and declarations of types and variables tend to obscure the actual algorithm. Make a convincing argument that your algorithm is correct and analyze its complexity. If you use known algorithms as part of your solution, do give a reference and state the complexity.

Problem 1 (5 pts)

The handout covering amortized analysis discusses amortized analysis of of a dynamic table growing and shrinking. Analyze the amortized complexity of a series of inserts and deletes assuming

• The table starts empty (num = 0) and with (size = 0).
• If the table is of size zero and an element is added it grows to size 1.
• If a table of size s ≥ 1 is full and an element is added, the table is grown to size 2n, elements are relocated and the new element is added.
• If, after removal, a table of size s ≥ 1 has less than s/3 elements is shrunk to size ^⌈2s/3^⌉, and the elements are relocated.
• The cost of adding or deleting an element is 1 (except if the table grows or shrinks)
• The cost of growing or shrinking the table is equal to the number of elements moved as a result of relocation.

Use the potential function Φ = |2num - size| and determine the amortized cost of insertions and deletions.

Problem 2 (5 pts)

Let makeSet, union, and findSet be the three operations of the union-find data structure implemented using a disjoint-set forest with union by rank and path compression Draw a picture of the data structure that results from running the following code (draw it at the indicated points in time). Include the ranks of the elements in your picture. In case the sets containing i and j have the same rank, the union(i, j) operation, then the root of i's tree becomes the root of the union.

for (i = 1; i <= 16; i++)
    makeSet(i)
for (i = 1; i <= 15; i += 2)
    union(i, i+1)
for (i = 5; i <= 13; i += 4)
    union(i, i+2)
# draw the datastructure at this point in time
union(3, 15)
union(10, 8)
union(16, 2)
union(13, 9)
# draw the datastructure at this point in time

Don't forget the path compressions!

Hint: You can do a limited check at the end by verifying that there are 4 elements that have 9 as parent in the final configuration.

Problem 3 (5 pts)

In class we analyzed disjoint-set forest with union by rank with path compression. In the analysis we used without proof that for any element, its rank never exceeds log₂n. Prove this. More precisely, show that in a sequence of m operation where n operations are makeSet no element gets rank more than log₂n.

It may be helpful to prove that if x is a root and its rank is k, then it is the root of a tree with at least 2^k elements.

Problem 4 (5 pts)

As there are a number of couch potatoes at KTH CSC, it has been decided that professors should be assigned to classrooms in such a way that they have to walk as far as possible to get to class, but how should one find such an assignment efficiently? This is a simplified version of that problem.

There are n professors and 2n classrooms. The input is a table t[1..n,1..2*n] where t[p, c] is the distance from the office of professor p to classroom c.

Design an efficient algorithm that finds a way to assign each professor to a classroom so that each professor gets a classroom and no classroom is used by more than one professor, and maximize the sum of the distances the professors need to walk if they all walk from their offices to their classrooms.

Your algorithm should run in time polynomial in n, and you may analyze it using unit cost (as opposed to bit cost). For full credit, its complexity should be noticeably better than O(n⁴).

Problem 5 (5 pts)

This problem is the same as Problem 4, except that we have a different target function. This time you should maximize the minimum distance a professor needs to walk to get from her office to the her classroom. In other words, if D is the shortest distance that any professor needs to walk to get to her classroom, then find a classroom assignment tha makes D as large as possible.

Your algorithm should run in time polynomial in n, and you may analyze it using unit cost (as opposed to bit cost). For full credit, its complexity should be noticeably better than O(n⁴).