$24
Question 1 – 15 points
Assume that we have the following balanced searched tree implementations:
1. 2-3 tree
2. 2-3-4 tree
3. Red-black tree
Starting with an empty balanced search tree, we would like to insert the following keys into the tree in the given order:
15 42 64 48 55 43 79 59 61
and then, delete the keys 48 79 59 (in the given order) from the tree. Note: while deleting an internal node, its inorder successor should be used as the substitute if needed.
Show the underlying tree for the 2-3 and 2-3-4 implementations after each insertion and deletion. Also show the underlying tree for the red-black implementation after each insertion (top-down). No deletion is required for the red-black tree.
Page 2
Fundamental Structures of Computer Science II
Question 2 – 15 points
Assume that we have a hash table with size 17 (index range is 0 : : : 16), and we use the mod operator as a hash function to map a given numeric key into this hash table. Draw the hash tables after the insertion of the keys
22 23 24 39 40 26 41 43 26
in the given order for each of the following methods:
1. open addressing with linear probing,
2. open addressing with quadratic probing,
3. separate chaining.
Question 3 – 70 points
The goal of this question is to perform some graph-related operations on Prof. Donald Knuth’s list of five-letter words in GraphBase (Donald E. Knuth, “The Stanford Graph-Base: A Platform for Combinatorial Computing,” ACM Press, New York, 1993). In this data set, each word is a vertex and two vertices are connected by an undirected edge if the corresponding words differ in only one letter. For example, roger and rover are connected but roger and pager are not.
You are asked to develop a program that allows users to do some operations on this word network. These operations should be implemented in a class named WordNetwork with all related code in the files named WordNetwork.h and WordNetwork.cpp (as well as any other files that contain any extra class that you wrote). The class definition and the descriptions of the required public functions are given below.
class W o r d N e t w o r k {
public :
W o r d N e t w o r k ( const string vertexFile , const string edgeFile ) ; ~ W o r d N e t w o r k () ;
void l i s t N e i g h b o r s ( const string word ) ;
void l i s t N e i g h b o r s ( const string word , const int distance ) ; void l i s t C o n n e c t e d C o m p o n e n t s () ;
void f i n d S h o r t e s t P a t h ( const string word1 , const string word2 ) ;
...
Page 3
Fundamental Structures of Computer Science II
private :
• define your data members here
• define private member functions here , if any
• you MUST use the adjacency matrix r e p r e s e n t a t i o n
};
WordNetwork( const string vertexFile, const string edgeFile ); The construc-tor loads the word network from the given text files containing the vertices and the edges. You are given a text file named vertexFile that contains each word in a separate line. There are 5757 words in this file. You are also given a separate file named edgeFile that contains the edge information. Each line includes an edge with the words separated by a comma. There are 14135 edges in this data set.
The constructor must load the network data from these files and construct an adjacency matrix representation for the graph. You MUST use the adjacency matrix representation in this assignment. (Otherwise, you will get no points from this question).
You MUST also design a hash table to implement the mapping from the words to unique integer indices. These integer indices (in the range from 0 to 5756) are used to refer to the vertices (i) and edges (i,j) internally in the code whereas the input and output use the actual words as in the examples below. The hash table takes a word (string) as input and gives its index (integer) as the output. The goal of the hash table is to perform this lookup efficiently. You MUST use the hash function (Hash Function 3) given on slide 40 of the lecture notes on hashing. You are free to choose the table size as you wish. The hash table MUST use separate chaining to store the data. The integer indices will correspond to the line numbers for the words given in the vertex file. For example, roger will be indexed as 0, cages will be indexed as 1, brung will be indexed as 2, and so on. You must use this hash table with the words given as the keys and the line numbers as the item data that will be used as the vertex indices.
void listNeighbors( const string word ); This function lists all words that are im-mediate neighbors of the input word. Each neighbor should be displayed on a sep-arate line as given in the following example:
Neighbors of roger:
roper
rover
rower
Page 4
Fundamental Structures of Computer Science II
Display a warning message if the word does not exist in the graph.
void listNeighbors( const string word, const int distance ); This function lists all words that can be reached from the input word with a distance given as the sec-ond input. The distance defines the number of letters that need to be changed to reach a word starting from the input word. For example, order is reachable from aided with a distance of 4 (aided ! added ! adder ! odder ! order). Display the resulting words on a separate line as in the previous function.
void listConnectedComponents(); This function lists all connected components in the given graph. The connected components should be identified clearly in the list. For example:
Connected component 1:
piece
niece
Connected component 2:
ideal
ideas
Connected component 3:
setup
getup
letup
Connected component 4:
rumor
humor
tutor
tumor
Connected component 5:
...
void findShortestPath( const string word1, const string word2 ); This func-tion displays the words along the shortest path from the first word to the second word. For example:
Shortest path from nodes to graph:
nodes
lodes
lores
Page 5
Fundamental Structures of Computer Science II
lords
loads
goads
grads
grade
grape
graph
Page 6