P1

For the activity selection problem describe a greedy algorithm using earliest-end-time in sufficient detail that you can analyze the algorithm in terms of n, the number of activities in A. This means you actually need to specify data structures for storing the information, and you need to describe how you plan to find the activity with earliest-end-time. Give an analysis of your algorithm's worst-case running time (big O is good enough).

You may assume that all start and end times are non-negative, and the start time for an activity is strictly less than its end time. You may also assume that the end time for one activity may equal the start time of the next and not be considered as overlapping.

P2

Suppose I want to find a minimum weight path from vertex u to vertex v in a weighted, directed graph. I might propose a greedy algorithm that starts with u as the "current" vertex, then greedliy chooses the smallest weight edge out of the current vertex, making the vertex at the end of that edge the new "current" vertex, and updating the problem by removing all other edges out of the old "current" vertex and into the new "current" vertex. Prove that this greedy algorithm does not always yield optimum (i.e. minimum weight) paths.