Algorithims

words.dat is just a file with 5757 5 letter words.

1. Consider the 5-letter words in the text file words.dat that was posted for Homework 4. Define an undirected graph whose vertex set is exactly the set of words in this file. The edges of this graph connect every pair of words w and u' if and only if w and u' differ in exactly one letter. For example, the words above and abode would be connected by an edge, since they differ only in the 4th letter. Let us call this the word graph. Write a program t of the word graph. To build an adjacency list representation that provides efficient access, first read the words from the file into an array W of size 5,757. Since the words appear in the file in sorted order, they can be placed in W in sorted order without much effort. Now build a second array, called A, such that for any word w, if w appears in slot i in array W, then slot i in the array A points to the list of the neighbors of w in the word graph. Now add two functions neighbors and degree to your program. Each function should take as arguments the arrays A and W and a word w. The neighbors function should return an array of all the neighbors of w in the word graph and the degree function should return the number of neighbors of w in the word graph. In order for these functions to be efficient, you should use binary search to figure out which slot in W the word w appears in. hat reads from words.dat and constructs an adjacency list representation Now use your code to answer the following questions: (a) What is the highest degree in the word graph? (b) Which are the words that have this highest degree? (c) Which are the words that have degree 0 in the word graph? (d) What is the total number of edges in the word graph? 1. Consider the 5-letter words in the text file words.dat that was posted for Homework 4. Define an undirected graph whose vertex set is exactly the set of words in this file. The edges of this graph connect every pair of words w and u' if and only if w and u' differ in exactly one letter. For example, the words above and abode would be connected by an edge, since they differ only in the 4th letter. Let us call this the word graph. Write a program t of the word graph. To build an adjacency list representation that provides efficient access, first read the words from the file into an array W of size 5,757. Since the words appear in the file in sorted order, they can be placed in W in sorted order without much effort. Now build a second array, called A, such that for any word w, if w appears in slot i in array W, then slot i in the array A points to the list of the neighbors of w in the word graph. Now add two functions neighbors and degree to your program. Each function should take as arguments the arrays A and W and a word w. The neighbors function should return an array of all the neighbors of w in the word graph and the degree function should return the number of neighbors of w in the word graph. In order for these functions to be efficient, you should use binary search to figure out which slot in W the word w appears in. hat reads from words.dat and constructs an adjacency list representation Now use your code to answer the following questions: (a) What is the highest degree in the word graph? (b) Which are the words that have this highest degree? (c) Which are the words that have degree 0 in the word graph? (d) What is the total number of edges in the word graph