Exercise $1(15$ points$)$

Your first task is to implement compute$\_$ngrams, which will take a list of tokens, a value n indicating the n$-$gram length $($e$.$g$.,3$ for $3-$grams$),$ and return an n$-$gram dictionary. The keys in the returned dictionary should all be strings, whose values will be lists of one or more tuples. Note that even in the case of n$=2($which would be the minimum value$)$ the dictionary should map strings to lists of $1-$tuples $($i$.$e$.,$ instead of to lists of individual tokens$).$

Exercise $2(10$ points$)$

Next, you will implement gen$\_$passage, which will take an n$-$gram dictionary and a length for the passage to generate $($as a token count$).$

As described earlier, it will work as follows:

Select a random key from the dictionary and use it as the start token of the passage. It will also serve as the current token for the next step.

Select a random tuple from the list associated with the current token and append the sequence to the passage. The last token of the selected sequence will be the new current token.

If the current token is a key in the dictionary then simply repeat step $2,$ otherwise select another random key from the map as the current token and append it to the passage before repeating step $2.$