## Description

Writing Assignment 2 CMPSC 465

INSTRUCTIONS:

1. You are suggested to use the provided latex template to write your solutions.

2. Submit your solution to Gradescope. Make sure only one of your group members submits. After

submitting, make sure to add your group members.

3. You may directly use the algorithms introduced in lectures.

Problem 1 (15 points).

Run the combine step of the divide-and-conquer algorithm for convex hull on the instance given below. You

are given (C1 = p5, p9, p10, p1, p3) and C2 = (p11, p4, p6, p2, p7, p8).

1. Find the lowest point p

∗

in C1 ∪C2.

2. Transform C1 into C

0

1

so that points in C

0

1

is sorted in increasing angle w.r.t. p

∗

.

3. Partition C2 into two lists C2a and C2b so that each list is sorted in increasing angle w.r.t. p

∗

.

4. Give list C

0

2

by merging C2a and C2b so that each points in C

0

2

is sorted in increasing angle w.r.t. p

∗

.

5. Give list C

0 by merging C

0

1

and C

0

2

so that each points in C

0

is sorted in increasing angle w.r.t. p

∗

.

6. Run Graham-Scan-Core algorithm to find convex hull of C

0

. Show stack operations at each step (to

deal with each point). For example, you need to write like ”For A: push A; pop B”, which indicates

when you process point A, push A into stack and also pop B out.

Problem 2 (12 points).

Run the DFS-based algorithms on the following graph. Note: whenever you have a choice of vertices to

explore, always pick the one that is alphabetically first (i.e., following the order v1, v2,···, v9).

1

Writing Assignment 2 CMPSC 465 Fall 2020 (Instructor: Mingfu Shao) Due: Sep. 27, 11:59pm

1. Run DFS (with timing) on this graph: give the pre and post numbers all vertices; give the postlist.

2. Draw the meta-graph of this graph.

3. Give a linearization of the meta-graph.

4. How many different linearization does the meta-graph have?

Problem 3 (10 points).

Let G = (V,E) be a DAG. Design an O(|V| + |E|) time algorithm to decide if there is only one possible

linearization for G. Prove that your algorithm is correct.

Problem 4 (10 points).

1. Given an undirected graph G = (V,E) and an edge e = (u, v) ∈ E, design a O(|V|+|E|) time algorithm

to determine whether there exists a cycle in G that contains e.

2. Given a directed graph G = (V,E) and an edge e = (u, v) ∈ E, design a O(|V|+|E|) time algorithm

to determine whether there exists a cycle in G that contains e.

Problem 5 (10 points).

A businessman owns n warehouses (n ≥ 3). In order to protect his products stored in these warehouses, he

wants to build a wall surrounding all these warehouses. The shape of the wall will be a convex polygon. You

are given n points P = {p1, p2,···, pn} on 2D plane, represented as their coordinates. Each point represents

a warehouse. Design an algorithm to find the minimal perimeter of such wall. Your algorithm should run in

O(nlogn) time.

Problem 6 (10 points).

There are n trains (X1,X2,···,Xn) moving in the same direction on parallel tracks. Train Xk moves at constant

speed vk, and at time t = 0, is at position sk. Train Xk will be awarded, if there exists a time period (t1,t2)

of any length, 0 ≤ t1 < t2, such that during this entire peroid Xk is in front of all other trains (it is fine if

Xk is behind some other train prior to t1, or Xk is surpassed by some other train after t2). Given vk and sk,

1 ≤ k ≤ n, design an O(nlogn) algorithm to list all trains that will be awarded.

2

Writing Assignment 2 CMPSC 465 Fall 2020 (Instructor: Mingfu Shao) Due: Sep. 27, 11:59pm

Problem 7 (10 points).

Assume that there are n different tasks to be done T1,T2,…Tn. And there are m different requirements, each

requirement is in the form that that one task Ti must be done before another task Tj

. Design an algorithm

to decide if there exists an order of tasks that satisfies all given requirements, and if it exists, find such an

order. Your algorithm should run in O(n+m) time.

Problem 8 (16 points).

You are given a directed graph G = (V,E), where V = {v1, v2,···, vn}. You can assume that each vertex is

reachable from itself.

1. For every vertex vi

, compute the value f(vi) defined as follows: f(vi) is the smallest j such that vi

is

reachable from vj

. Design an algorithm to calculate values f(v1),···, f(vn). Your algorithm should

run in O(|V|+|E|) time.

2. For every vertex vi

, compute the value g(vi) defined as follows: g(vi) is the smallest j such that vj

is

reachable from vi

. Design an algorithm to calculate values g(v1),···,g(vn). Your algorithm should

run in O(|V|+|E|) time.

3