Final Exam Info for MCS-375: Algorithms (Fall 2011)

A printed copy of all this information will be provided with the final exam.

Code to be familiar with

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.

Assumptions you may make about procedure parameters

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 <.

Python cost model

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.