Introduction

For general information about assignments in this course, see assignments

Path Compression

Here is recursive version of find with path compression from the slides.

def find(P, key):
  if P.parent[key] != key:
    P.parent[key] = P.find(P.parent[key])
  return P.parent[key]

Give a non-recursive version, still with path compression, and show that it preserves Property 1 for union-find, namely

For any $x \in [0..n-1]$ such that P.parent[x] != x, P.rank[x] < P.rank[P.parent[x]]

Break the Cycles

Prove the following MST algorithm is correct. You can use the cut property in your proof if you want, but it’s not clear it’s the best approach.

sort the edges according to their weights
for each edge e ∈ E, in decreasing order of weight :
    if e is part of a cycle of G:
        G = G − e (that is, remove e from G)
return G  

Hotels

(Based on an exercise in Dasgupta et al.)

You are driving across Canada, on the the Transcanada Highway. There are hotels at kilometer @@math:a_1 < a_2 < \dots < a_n@@. You need to choose a hotel to stop at every night, with the restriction that on the last night you have arrived at kilometer @@math:a_n@@. You have a strange car rental agreement that allows you to drive 500 km a day, but penalizes you @@math:(500-x)²/500@@ dollars if you travel more or less than that in a day.

• Describe a DAG of subproblems to solve.

• Give a memoized recursive 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.

Palindrome

(Based on an exercise from Jeff Erickson)

A string is palindromic if is exactly the same as its reversal, e.g. DEED, RACECAR, MURDEREDRUM. Describe and analyze a dynamic programming (without recursion) algorithm to find the length of the longest palindromic subsequence in a given string For example, the longest palindromic subsequence of MAHDYNAMICPROGRAMZLETMESHOWYOUTHEM is MHYMRORMYHM, so given that string as input, your algorithm should output the number 11.