CSC 477/677 Assignment 4
Due date, November 3, 2005, 11:00 AM.
All assignments must be handwritten
(not typed or printed from a computer file)
in your own handwriting, on 8.5 by 11 inch paper. Write your name on
each sheet, and do not fold the pages or crimp the corners.
Turn the pages in to me or to the graduate assistant on the due date.
-
Starting with an empty tree, insert the letters L,F,B,M,G,V into an
AVL tree. Show the tree at each step.
-
Starting with an empty tree, insert the letters A,G,K,D,P,S,H,J into a
2-3 tree. Show the tree at each step.
-
We say that a string of letters is a "3-Scrabble" string if every
substring of length 3 is listed in the Family Scrabble Dictionary.
For example, "ONETAND" is a 3-scrabble string of length 7 from "O" to "D".
("ETA" is the name of a Greek letter.)
Assume that you are given the Family Scrabble Dictionary in an appropriate
data structure, such as a
trie
or a
Patricia tree.
Describe an efficient queue algorithm that
finds a shortest 3-Scrabble string from a given letter to a given letter,
if one exists.
-
Write the matrix representation of
this weighted directed graph, G.
(Here is a pdf version.)
Then, compute G* using (min,+) matrix multiplication.
Back to
Course Page