COMP3027/COMP3927 Tutorial questions The University of Sydney 2019 Semester 1 Tutorial 5 School of Computer Science
Tutorial
This tutorial will be mostly reviewing greedy and divide-and-conquer algorithms. Please make sure you do Problem 4 as it will be important for next week’s lecture.
Problem 1
Suppose we are to schedule print jobs on a printer. Each job j has an associated weight wj > 0 (representing how important the job is) and a processing time tj (representing how long the job takes). A schedule σ is an ordering of the jobs that tell the printer how to process the jobs. Let Cjσ be the completion time of job j under the schedule σ.
Design a greedy algorithm that computes a schedule σ minimizing the sum of weighted completion times, that is, minimizing j wjCjσ.
Problem 2
Consider the following algorithm for the MST problem:
Algorithm 1 Reverse-MST
1: 2: 3: 4: 5: 6: 7: 8: 9:
10:
functionReverse-MST(G,w)
sort edges in decreasing weight w T←E fore∈E[inthisorder]do
if T − e is connected then T←T−e
end if end for
return T end function
Prove its correctness and analyze its time complexity. To simplify things, you can assume the weights are different.
Problem 3
A computer network can be modeled as an undirected graph G = (V, E) where vertices represent computers and edges represent physical links between computers. The maximum transmission rate or bandwidth varies from link to link; let b(e) be the bandwidth of edge e ∈ E. The bandwidth of a path P is defined as the minimum bandwidth of edges in the path, i.e., b(P ) = mine∈P b(e).
Suppose we number the vertices in V = {v1, v2, . . . , vn}. Let B ∈ Rn×n a matrix where Bij is the maximum bandwidth between vi and vj. Give an algorithm for computing B. Your algorithm should run in O(n3) time.
Problem 4
Recall the optimal time investment window problem from Lecture 1. In this problem, we are given an array
1
A of n integers (each integer can be positive, zero, or negative). A time window is an interval [i,j] and its return is the sum of elements of the array with indices between i and j (inclusive), i.e. the return of [i,j] is i≤k≤j A[k]. Note that a time window with i = j is allowed; in this case, its return is A[i].
Give a divide-and-conquer algorithm that finds a time window with maximum return and runs in time O(n log n).
Problem 5
(Exercise 6, Chapter 5 from textbook Algorithm Design) Let T be a complete binary tree with n vertices. Each vertex v has a distinct weight w(v). A vertex is a local minima if its weight is less than the weight of its neighbors. Give a divide-and-conquer algorithm that finds a local minima in time O(log n).
Problem 6
(Due to Jeff Erickson.) For this problem, a subtree of a binary tree means any connected subgraph. A binary tree is complete if every internal node has two children, and every leaf has exactly the same depth. Describe and analyze a recursive algorithm to compute the largest complete subtree of a given binary tree. Your algorithm should return both the root and the depth of this subtree. See Figure 1 for an example.
Figure 1: The largest complete subtree of this binary tree has depth 3.
Problem 7
Describe an algorithm to insert and delete points from a kd-tree. You do not have to rebalance the structure.
Problem 8
Describe an algorithm to insert and delete points from a range-tree. You do not have to rebalance the structure.
Problem 9
[Optional] Consider the following algorithm for the MST problem:
2
Algorithm 2 Improving-MST
1: 2: 3: 4: 5: 6: 7: 8: 9:
10:
functionImproving-MST(G,w) T ← some spanning tree of G fore∈E[inanyorder]do
T←T+e
C ← unique cycle in T f ← heaviest edge in C T←T−f
end for
return T end function
Prove its correctness and analyze its time complexity. To simplify things, you can assume the weights are different.
Problem 10
[Optional] (Due to Jeff Erickson.) Let T be a binary tree with n vertices. Deleting any vertex v splits T into at most three subtrees, containing the left child of v (if any), the right child of v (if any), and the parent of v (if any). We call v a central vertex if each of these smaller trees has at most n/2 vertices. See Figure 2 for an example.
1. Show that every tree has a central vertex.
2. Give an algorithm that finds a central vertex of v in O(n) time.
Figure 2: Deleting a central vertex in a 34-node binary tree, leaving subtrees with 14, 7, and 12 nodes.
3