A printed copy of all this information will be provided with the final exam.
You should study this code and make sure you understand it. You are welcome to consult Python documentation and try the code out on a computer. The first three files listed here all get used by the fourth file.
SkipList.py contains the SkipList class we developed. I have not made any changes at all.
Queue.py contains a Queue class. You should already be familiar with the concept of a queue, but you haven't seen this particular representation before.
singleSource.py contains BellmanFord and Dijkstra procedures. These are essentially the same as the ones we developed in class, but have been slightly modified to change the format of the input parameters and result values.
sortVertices.py contains four different procedures, sortVertices1 through sortVertices4. Although these procedures are new to you, several of them are based on algorithms you've seen.
You may assume that any calls to these procedures will comply with the restrictions listed in the procedures' documentation strings.
Additionally, you may assume that the vertices belong to some simple, immutable type such as strings or integers. In particular, they are hashable, that is, legal to use as keys in dictionaries and sets. In addition, they are comparable, that is, legal to compare using operators such as <.
In analyzing the running time of Python procedures on the final, you may assume that operations that work on a single element of a list, dictionary, or set take constant time. This includes appending to a list, popping from a list, inserting into a dictionary or set, retrieving from a dictionary, testing for set membership, and each individual step of iteration through the contents of a list, dictionary, or set.
The len operation on lists, dictionaries, and sets also takes constant time.
Reversing a list takes time proportional to the length of the list.
Sorting a list takes time proportional to nlg n, where n is the length of the list.
If you see any other operation used in the provided code and aren't sure whether it would take constant time, please ask.