Assignment 5 - Ass5 PDF

Preview

Summary

Ass5...

Description

Technische Universit¨at M¨ unchen Fakult¨ at f¨ ur Informatik Lehrstuhl f¨ur Algorithmen und Komplexit¨ at Prof. Dr. Susanne Albers Dr. Waldo G´alvez Sebastian Schubert

Winter Semester 2020/21 Assignment 5 December 7, 2020

Advanced Algorithms Note: Given the current enrollment, you are kindly requested to submit in groups of two. Solutions are to be submitted via Moodle before Monday, December 14, at 10:00.

Exercise 1 (Operations on Treaps – 10 points) 1. Sequentially insert the keys c, d, e, b, a with respective priorities 7, 3, 10, 1, 4 into an initially empty treap. For all the intermediate stages, e.g. after performing a rotation, illustrate the state of the treap and specify the operation that leads to this state. 2. Delete the root of the treap resulting from part 1. Again illustrate the treap prior to and after each rotation. 3. Merge the treap resulting from part 2 and the treap shown below. Illustrate all intermediate stages.

g(8)

i(9)

h(11)

j(13)

Exercise 2 (Rotations in Treaps – 10 points) The left spine of a binary search tree is the path from the root to the node with the smallest key. In other words, the left spine is the path from the root that consists of only left edges. Symmetrically, the right spine is the path from the root consisting only right edges. The length of a spine is the number of nodes it contains (including the root). 1. Consider a treap T immediately after inserting node x. Let C be the length of the right spine of the left subtree of x. Let D be the length of the left spine of the right subtree of x. Argue that the total number of rotations that were performed during the insertion of x is equal to C + D. 2. Show that for nodes x and y(6= x), y is in the right spine of the left subtree of x if and only if prio(x) < prio(y), key(x) > key(y), and for every z such that key (y) < key (z) < key (x), there is prio(z) > prio(y).

Exercise 3 (Distinct Min-cuts – 10 points) Consider the randomized min-cut algorithm (Contraction) presented in the class. We showed that, for any connected graph G with n vertices, the probability that the algorithm 2 . finds a specific min-cut C of G is at least n(n−1) 1. What can we say about the maximum number of distinct min-cuts that a connected graph G can have? 2. Give an example of a connected graph (with n vertices) with maximum number of distinct min-cuts. 3. Use the randomized edge contraction algorithm to find all the min-cuts in any connected graph G.

Exercise 4 (Min k-cut – 10 points) Given an unweighted and undirected graph G := (V, E), a 3-cut is a partition of V into three nonempty sets A, B, C. The size of the cut is the number of edges connecting vertices from different sets. Extend the randomized min cut algorithm presented in the class to give an algorithm to find a minimum 3-cut. Extend your answer to provide an algorithm for the case of minimum k-cuts for any constant integer k ≥ 3.

2...