algorithm design and analysis

Q1: There are n neighborhoods in Indiana. You are given a map where neighborhoods are vertices and adjacent neighborhoods are connected by an edge (each neighborhood has at least one adjacent neighborhood). Suppose we would like to open some stores in Indiana, so that everyone can either go to a store in his/her neighborhood, or a store in an adjacent neighborhood. However, due to budget, we can only open at most n/2 stores.

* Design an algorithm that returns at most n/2 neighborhoods, such that if there is a store in these each one of these neighborhoods, everyone can find a store either in their neighborhood or in at least one of the adjacent neighborhoods.

* Will your algorithm always return an optimal solution, i.e., one that opens the smallest number of stores on a map? Give a proof or a counterexample.

Q2 : We are given a directed acyclic graph G. For simplicity, assume the vertices of G are {1, 2, , n} and G contains m edges. The m edges are given by m tuples of the form (i, j, c), where each tuple (i, j, c) defines a directed edge of value c from vertex i to vertex j. We assume all tuples (i, j, c) satisfy 1 i < j n and c > 0. The goal of the problem is to compute a path from 1 to n with the maximum total value. Design an O(m)-time algorithm for the problem.