This problem was probably the easiest one. One possible solution works as follows. Consider the input as a graph with vertices corresponding to the packages and edges corresponding to the dependencies. An edge leading from u to v denotes that u depends on v. Each vertex is colored white or black, white meaning the package is available. The out-degree of a vertex is the number of edges leaving it, e.g. the number of dependencies the corresponding package has. We may install a package iff the corresponding vertex is white and has out-degree 0.
While reading the input, we compute the out-degree and color for each vertex. Also for each vertex v we store a list D(v) containing all vertices u such that there is an edge from u to v in our graph. (E.g. a list of all packages depending on v.) We will simply simulate the installation process. If there is no white vertex with out-degree 0, we are done. Otherwise we pick any such vertex v, install the corresponding package and remove v from the graph. By removing v the out-degree of vertices in D(v) decreases by 1. In this way new installable packages may arise.
We will maintain all currently installable packages in a queue. In each step we pop a package from the queue, install it and decrease the corresponding out-degrees. If we decreased the out-degree of a white vertex to 0, we push it into the queue. The algorithm ends when there are no more packages in the queue.
Both time and space complexity of this algorithm are linear in the size of the given graph. Note that an optimal algorithm would use a hash table to store the names of the packages. However, the input files were small enough and so this approach wasn't necessary.