Problem set week 4

The idea with this problem set is that you should practice on the following things:

Exercises:

Implement (preferably using pseudo code) a program which checks if a text file contains both some word w and its mirror image reverse(w) (e.g. both ropa and apor). Use a hash table. Analyse the program's time complexity under two assumptions:
- A perfect hash function.
- A hash function which is as bad as possible.
Do not blindly assume that hash functions compute in constant time.
Directed unweighted graphs can be represented textually as follows:
```
node1 node2 apa
node2
apa node2 apa
```
Every line starts with a node identifier, followed by the node identifiers of all direct successors of the node.

Implement (preferably using pseudo code) a program which parses such a file and constructs a representation of the graph in memory. Be explicit about how you represent the graphs. Make sure that finding a direct successor of a node does not involve looking up a string in a map.

You can assume that the files do not contain errors (such as syntax errors or undeclared node identifiers), and that the graphs are well-formed (no duplicated edges).
Assume that there is an algorithm which, in linear time, can decide whether a graph contains a Hamiltonian cycle. Design an algorithm which decides whether a graph contains a Hamiltonian path, prove that it is correct, and analyse its time complexity.