Description

Assignment 5
There will likely be time in class to discuss these problems in small groups and I highly encourage you to collaborate with one another outside of class. However, you must write up your own solutions independently of one another. Feel free to communicate via Discord and to post questions on the appropriate forum in Blackboard. Do not post solutions. Also, please include a list of the people you work with at the top of your submission.
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.
(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
• 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.
• 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