CS 202 Homework #4 – Balanced Search Trees, Hashing an

Starting from:

~~$30~~

$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 diﬀer 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 eﬃciently. 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