1. Design a stack that has a min() method (in addition to push and pop) that can retrieve the minimum in O(1) time. (25) 2. Given a Linked List, provide a O(n) (n is the number of nodes in the list) algorithm that can detect whether the linked list has a loop, and find the node that starts it (node x in the following picture)? (25) 3. The following image is a snapshot of a very tiny part of WordNet (the original tree is many times bigger than this). The nodes of the tree have a -is-a relationship with their parent. (hatch-back is a motorcar). Design an algorithm that given a tree T and two nodes (u,v), finds the first type that can describe both, that is, the closest node to a and b that “ a is-a v” and “ b is-a v”. For example, given compact and truck, it should return What is the complexity of the algorithm? (25) 4. Design an algorithm that given a graph and two nodes (a and b), returns a path from a to b, or null if no such path exists. (25)
