Urgent Please Help!!!

CSCI 1913: Introduction to Algorithms, Data Structures, and Program Development

0. Introduction.

In this assignment, you will write a Python program that is given example words, and generates random words that resemble them. For example, after being given the last names of all U.S. presidents, the program generated the names BumpRoe, Cartoon, Forthis, Fovenay, Gaylton, Haneram, Hansoro, Madiela, Ninasoo, Relayle, Ronburd, and Wanhumo (among others). Perhaps these are the names of future presidents. It is claimed that the names of some companies and commercial products were produced by programs similar to this one.

1. Theory.

For this project, you need an algorithm that generates random integers. You also need an algorithm that records example words, and another algorithm that uses the random integers and example words to generate random words.

Random integers. No algorithm can generate truly random integers, but it can generate pseudo-random integers that seem random, even though theyre not. Python has its own random number generator, but for this project you must implement your own. The Park-Miller algorithm (named for its inventors) is a simple way to generate a sequence of pseudo-random integers. It works like this. Let N be an integer called the seed. The seed is the first term of the sequence, and must be between 1 and 2 2. Starting from N, later terms N, N ..., are produced by the following equation.

N_k+1 = (7⁵ N_k) % (2³¹ 1)

Here 7 is 16807, and 2 is 2147483648. The operator multiplies two integers, and the operator % returns the remainder after dividing one integer by another. You will always get the same sequence of integers for a given seed. For example, if you start with the seed 101, then you get a sequence whose first few terms are 1697507, 612712738, 678900201, 695061696, 1738368639, 246698238, 1613847356, and 1214050682. You can use these to test if your random number generator works correctly. Some of these integers may be large, but you can make them smaller by using the % operator again. If N is an integer from the sequence, then N % M gives you an integer between 0 and M 1. For example, if you need a pseudo-random integer from 0 to 9, then you write N % 10. You can use this to choose a random element from a sequence. If S is a sequence, then the Python expression S[N % len(S)] returns a randomly-chosen element of S.

Recording example words. Heres how to record example words. A letter is 'A' through 'Z', and 'a' through 'z'. Suppose that first is a string of letters, and is initially empty. As its name suggests, first will hold the first letter of each example word. Also suppose that follow is a dictionary, also initially empty, whose keys are letters, and whose values are strings of letters. The dictionary follow will hold strings of letters that can follow other letters. If youre given the example word 'Trump', then you add 'T' to first, because 'T' is the first letter of the word. You also add 'r' to the string in follow that is the value of the key 'T', because 'r' follows 'T'. Similarly, you add 'u' to the string that is the value of the key 'r', because 'u' follows 'r'. You add 'm' to the string that is the value of the key 'u', because 'm' follows 'u'. Finally, you add 'p' to the string that is the value of the key 'm' because 'p' follows 'm'. After many example words, first will record the first letters of each one, and follow will record how letters follow one another in the example words. Letters may appear more than once in the string first, and in the strings from follow. A letter that appears many times is more likely to be chosen at random than one which appears few times.

Generating random words. Heres how to use first and follow to generate a random word, one letter at a time. You get the first letter of the word by randomly choosing it from first. Next, you look up the first letter in follow, obtaining a string of possible letters. You get the second letter by randomly choosing it from that string. Then, you look up the second letter in follow, obtaining another string. You get the third letter by randomly choosing it from that string. You continue like this, choosing letters from strings, and concatenating them together, until youve constructed the entire word. The number of times a letter appears in a string records how often that letter appeared in the example words. As a result, if you choose a letter at random from a string, then it is more likely to be chosen if it appeared often. Also, follow records how letters followed other letters in the example words. This lets you generate words that are roughly similar to the ones that were given as examples. One potential problem remains. While youre generating a random word, you may find that there is no string in follow for some letter. If this happens, then you choose a letter at random from first instead, and continue generating the word as before. The Python-2 expression follow.has_key(l) tests if there is a string in follow for the letter l. The Python-3 equivalent is l in follow. There may be other ways to make these tests.

2. Implementation.

You must write two Python classes. Do not try to use only one class, because that will not work. Do not try to make one class a subclass of the other one, because the two classes do different things. The first class must be called Random, and it must implement the Park-Miller random number generator discussed in section 1. The class Random must have the following methods.

__init__(self, seed)

(5 points.) Initialize an instance of Random with the integer seed. Assume that seed is in the proper range for the Park-Miller algorithm to work.

next(self, range)

(5 points.) Generate the next random number in the sequence. Use it to return a nonnegative integer greater than or equal to 0, but strictly less than the integer range. Return that random number. Assume that range is an integer greater than 0. You can write this in only two lines.

choose(self, characters)

(5 points.) Choose a character from the string characters at random, using an index obtained by calling next. Return that character. You may assume that characters is not empty. You can write this in only one line.

The second class must be called Words, and it must implement the random word generation algorithm discussed in section 1. The class Words must have the following methods.

__init__(self, seed)

(5 points.) Create private variables first, follow, and random. The variable first must be an empty string. The variable follow must be an empty dictionary. The variable random must be an instance of Random, whose seed is the integer seed. You may assume that seed is in the proper range for the Park-Miller algorithm to work.

add(self, word)

(10 points.) Add the string word as a new example, using first and follow as described in section 1. You may assume that word is made up entirely of letters, and that it has at least one letter. Return None.

make(self, size)

(10 points.) Create a new example word using first, follow, and random as described in section 1. The word must be a string with exactly size letters. Return that string. You may assume that size is an integer greater than or equal to 0.

For efficiency, first must be a string, and the keys and values of follow must also be strings. My code for Random is about half a page of code, and its methods have one to three lines each. My code for Words is about one page. Python can be very concise! If you find yourself writing much more code than this, then you do not understand this assignment, and you should ask for help.

3. Example.

The random names from part 0 were generated by the following fragment of Python code. First, a new instance of the class Words is created, called prez. Then prez is given the last names of all U.S. presidents. Some names appear more than once because a single president served for two non-consecutive terms, or because two presidents had the same last name.

prez = Words(101) prez.add('Washington') prez.add('Adams') prez.add('Jefferson') prez.add('Madison') prez.add('Monroe') prez.add('Adams') prez.add('Jackson') prez.add('Vanburen') prez.add('Harrison') prez.add('Tyler') prez.add('Polk') prez.add('Taylor') prez.add('Fillmore') prez.add('Pierce') prez.add('Buchanan') prez.add('Lincoln') prez.add('Johnson') prez.add('Grant') prez.add('Hayes') prez.add('Garfield') prez.add('Arthur') prez.add('Cleveland') prez.add('Harrison') prez.add('Cleveland') prez.add('Mckinley') prez.add('Roosevelt') prez.add('Taft') prez.add('Wilson') prez.add('Harding') prez.add('Coolidge') prez.add('Hoover') prez.add('Roosevelt') prez.add('Truman') prez.add('Eisenhower') prez.add('Kennedy') prez.add('Johnson') prez.add('Nixon') prez.add('Ford') prez.add('Carter') prez.add('Reagan') prez.add('Bush') prez.add('Clinton') prez.add('Bush') prez.add('Obama') prez.add('Trump')

After this, each call to prez.make(7) returns a new seven-letter word, roughly similar to the names that prez was given. For example, when I used a loop to generate the first 30 random names, heres what I got.

Grurumo Jonsone Hansoro Cldisoe Fovenay Fisooos Clnnhin Taruson Tayeylo Adgeama Madiela Roshnbu Obayeay Ponhuso Monconc Mcesens Haringe Cosovel Lingten Jarrixo Jonarfi Adinhum Ponlele Polnlel Ninasoo Clannga Relayle HampCan Jonhuse Kesolin

Some look more like English words than others. The longer the words, the less they look like English. There are many ways to write this program. Your program may generate different words from these, but still be correct.