1)
o 
A: For instance, "a" does not produce neither "crab" nor "tree".

o
A: The relevant parameter when computing the hash function
in the Karp-Rabin algorithm is the LENGTH of the pattern.
Since |crab|=|tree| then the running time is identical.

2) BST
A:               (9)                      (7)
                /   \                    /   \
             (7)     (17)             (3)     (19)
            /       /    \                   /    \
         (3)    (11)      (19)           (11)      (21)
                              \         /    \
                               (21)  (9)      (17)

3)
A:
last(node h);

IF h==nul THEN RETURN nul;
move = h ;
WHILE move.next!==nul DO
  move = move.next ;
RETURN move ;
 
4) 
(a)
A: FALSE. Some instance can be solved but not all of them.
(b)
A: TRUE. By definition.
(c)
A: FALSE. Not quite, since some leaves may be missing on the last level.
(d)
A: FALSE. Of course not, why would we learn both otherwise.
(e)
A: FALSE. It is still possible that an efficient algorithm would be found.

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

o
A:
enqueue(Q,O:Objet)
WHILE !isempty(S1) DO
  tmp = POP(S1) ;
  PUSH(S2,tmp) ;
PUSH(S2,O) ;

dequeue(Q)
WHILE !isempty(S2) DO
  tmp = POP(S2) ;
  PUSH(S1,tmp) ;
POP(S1) ;

size(Q)
RETURN size(S1)+size(S2) ;

isempty(Q)
RETURN isempty(S1)&&isempty(S2) ;

front(Q)
WHILE !isempty(S2) DO
  tmp = POP(S2) ;
  PUSH(S1,tmp) ;
RETURN TOP(S1) ;

o
A:
First, you must understand how the stacks are used
to simulate the queue : to access the head of the queue
all the elements have to be in S1, and to access the
tail of the queue all the elements have to be in S2.

When K elements are in the queue, to do enqueue
and front, the algorithm must access both the tail and
head of the queue, thus must move all the K element
from one stack to the other.

In the worst-case, if executing N enqueue/front operations
then the K-th such operation requires K PUSH/POP operations.
Thus, N enqueue/front operations costs 1+2+...+N PUSH/POP operations,
that is O(N^2) PUSH/POP operations.

o
A:
I'll let you think about this one. It is for bonus points...