# CS代考程序代写 algorithm COMP3027/COMP3927 Tutorial questions The University of Sydney 2019 Semester 1 Tutorial 5 School of Computer Science

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