1) Consider the following patterns: "crab" and "tree". 

o Give a regular expression that produces neither of these expressions.

o Explain why the time required by the Karp-Rabin algorithm
to compute the "hash" of both patterns would be the same.


2) BST

Consider the following list of numbers : { 3, 19, 17, 11, 7, 9, 21 }.
Give two distinct ways of putting these elements in a binary search tree.

3) Consider the following (Java) definition of a node

Class node
{
Object content;
node next;
}

Let h be an object of type node, the head of a linked list of nodes.

Give the pseudo-code description of an algorithm "last(node h)" that finds
the last node in the list.
 
4) For each statement, say if it is true or false.

Right = +2pts,    Wrong = -1pt,    Blank = 0pt.


(a) The Post Correspondance Problem (described in class) can never be solved.

(b) A tree is always acyclic.

(c) A heap is always a complete binary tree.

(d) DFS is always better than BFS.

(e) NP-complete problems are provably infeasible.


5) Suppose you are given two stacks S1 and S2.

o Find an algorithm (in pseudo-code) to implement the operations of a queue Q
using nothing else than a fixed number of extra int variables
(no array, no queue, no other stack) and stack operations on S1 and S2.

o Estimate the worst-case running time of your algorithm and express this
time function using the Big-O notation.

o Argue that this would be impossible with a single stack S instead.