CSCI411 - Advanced Algorithms - Complexity - Assignment 5 - Solved

Written Problems
1.    (Adapted from exercise 6.2 from Sanjoy Dasgupta, et al., Algorithms, McGraw Hill, 2008) You are going on a long trip. You start on the road at mile post 0. Along the way there are n hotels, at mile posts a1 < a2 < ··· < an, where each ai is measured from the starting point. The only places you are allowed to stop are at these hotels, but you can choose which of the hotels you stop at. You must stop at the final hotel (at distance an), which is your destination.

You’d ideally like to travel 200 miles a day, but this may not be possible (depending on the spacing of the hotels). If you travel x miles during a day, the penalty for that day is (200−x)2. You want to plan your trip so as to minimize the total penalty - that is, the sum, over all travel days, of the daily penalties.

(a)    (15 pts) Describe the optimal substructure of this problem. In particular, define the minimum total penalty in terms of penalties for shorter trips. Justify your answer.

(b)    (10 pts) Let the sequence of hotel locations be A = [a1,a2,...,an]. Write pseudocode for a function hotelSequence(A) which returns the minimum total penalty.

(c)    (5 pts) Analyze the asymptotic run time of your algorithm.

2.    Given an undirected graph G = (V,E), a vertex cover of G is a subset of vertices C ⊆ V such that, for every edge {u,v} ∈ E, either u ∈ C or v ∈ C. It turns out that, while finding a vertex cover of minimum size is difficult for general graphs, it can be done efficiently for trees using dynamic programming.

(a)    (25 pts) Describe the optimal substructure of this problem. In particular, given a tree T = (V,E), define the size of a minimum vertex cover in terms of smaller trees. Justify your answer.

(b)    (15 pts) Write pseudocode for a function treeVC(T) which returns a minimum vertex cover of T.

(c)    (5 pts) Analyze the asymptotic run time of your algorithm.

Coding Problem
(25 pts) Write a C++ implementation of the pseudocode you developed for problem (1b) and submit to Blackboard and to turnin as assignment 5.cpp. You may find the skeleton code in assignment 5 skeleton.cpp on Blackboard helpful.

•    Input will come from cin

–    The first line will include two integers, n and m, separated by a space.

∗ 4 ≤ n ≤ 1000 is the total number of hotels.

∗ 10 ≤ m ≤ 1000 is the ideal number of miles traveled per day. In question 1, m = 200.

–    n lines follow.

–    Each line contains the distance of a particular hotel from the starting point.

–    You may assume that these distances are in sorted order.

•    Print output to cout

–    Your output should consist of two lines.

–    The first line should be a space separated list of integers between 1 and n indicating the hotels visited. These should be in ascending order.

–    The second line should be the minimum total penalty associated with the hotels visited.

Examples
Example 1:

Input:

4 200

200

400

600

800

Expected output:

1 2 3 4

0

Example 2:

Input: 4 200

190

210

390

590

Expected output:

1 3 4

100

Example 3:

Input: 11 10

0

1

2

3

4

5

6

7

8

9

10

Expected output:

11

0