CS 261, Spring 2013, Homework 6, Due Thursday, May 23

1. (a) Find four strings whose compressed trie forms a complete binary
tree with four leaves.

(b) Is it possible for the suffix tree of a string to form a complete
binary tree with four leaves? If yes, provide an example; if no, explain
why not.


2. Let n be any integer, and let string s (including its string termination symbol $) have n symbols in it: exactly n-1 copies of the symbol "a" followed by the $. For instance, for n=5 the string s would be aaaa$. How many leaves does the suffix tree of s have, as a function of n? How many non-leaf nodes does it have?


3. Suppose you are given a string s, over a given alphabet, and have
constructed the suffix tree for s. Describe a linear-time algorithm for
using the suffix tree to construct a string of minimum length over the
same alphabet that is not a contiguous substring of s.

E.g., if the alphabet is {A,T,C,G} and s is AATACAGTTCTGCCGGA, then s
contains all 16 different length-two strings, but it is missing some
length-three strings, such as AAA, and your algorithm should output one
of the missing strings.