CS 494/594 Homework Assignment #1

Due Date: Tuesday, Sept. 12 (Beginning of Class)

[3Pts] Assume f is a function that maps from the set of integers {0,1,...,255} to the ISO 8859-1 Latin 1 character repertoire.
a. What is f(252)?
b. If f(a)= ó, what is a?
[3Pts] Assuming valid HTML 2.0, write a grep-style regular expression that will match any heading element (e.g., H1, H2, etc.). You may assume the element is contained within a single line. Make sure you match the entire heading. Do not use the grep -i option.
[3Pts] Assuming valid HTML 2.0, write a Perl statement that will match an anchor element in the current value of $_ and assign the value of the HREF attribute to a variable named url.
[3Pts] Draw a state diagram for either a DFA or an NFA for the following regular expression:

abc[0-9](de|fg)*[x-z]
[3Pts] In a B-tree of order m, every internal node except the root has between ceiling(m/2) and m children. The root has between 2 and m children. All leaves are at the same level. To search a B-tree index, one must traverse a path from the root to a leaf node. We wish to minimize the amount of time needed to search the B-tree index for a value. If the index has N entries, then a B-tree of order m=N+1 would have only one level. Give at least two reasons why this choice for m would be undesirable.
[3Pts] Give a binary string that produces a suffix tree with worst case height and show the suffix tree.
[2Pts] BONUS QUESTION. Is the set of all valid HTML 2.0 documents a regular language? Why or why not?