## CS 2 (Winter 2021)Project 05: Markov Text Generation

This project focuses on implementing various data structures (hashtable, BST) and algorithms. These will be used to create a Markov Model.

# Goals and Outcomes

In this project, you will build a Markov Model using various data structures.

By the end of this project, you will…

• have implemented a hashtable and binary search tree
• have written a word suggester which predicts what the next word might be given some number of previous words

# Connection to Lecture

This project covers lecture08 (trees) and lecture12/lecture13 (hash tables). You will likely find the code from these lectures to be very useful in this project.

# Overview and Implementation Strategy

This week, the test “grade-levels” are a little weird. Instead of having what would normally be C-B-A, we have B-A-A+. You should think of the A+ level as “extra credit”. The B tests are incredibly important to the learning outcomes of the course which is why they’re rated “B” instead of “C”.

In previous projects, you wrote several “list-like” data structures (the IDeques) and one IDictionary implementation (the trie). This time, you will continue our mission of implementing all the data structures ourselves by writing several more IDictionary implementations. This time, we will use the data structures to back Markov text generation, which “mimics” the style of a provided corpus.

# NGram: A client of your data structures

Data structures store…data. Different data structures require the presence of different operations.

• A dictionary made out of a list requires equality testing on the key type.
• A dictionary made out of a hash table requires equality testing and hashcode calculation on the key type.
• A dictionary made out of a tree requires equality testing and comparison on the key type.

In Java, we implement these operations directly in the class that represents the key type. For this project, we will mostly use the NGram type. An NGram is a list of $$n$$ words appearing in order in a text. Before implementing your data structures, it is imperative that equality, hashcode, and comparisons all work. Otherwise, you will run into weird errors with the tests that are not due to your data structures.

# MoveToFrontDictionary: Another Dictionary

In this part, you will implement MoveToFrontDictionary, a new type of Dictionary.

MoveToFrontDictionary is a type of linked list where new items are inserted at the front of the list, and an existing item gets moved to the front whenever it is referenced. Although it has $$\mathcal{O}(n)$$ worst-case time operations, it has a very good amortized analysis. We will not discuss this data structure in class. MoveToFrontDictionary should only rely on equality testing of keys.

# ChainingHashDictionary: Another Another Dictionary

In this part, you will implement ChainingHashDictionary. Your hash table must use separate chaining–not probing. Furthermore, you must make the type of chain generic. In particular, you should be able to use any dictionary implementation as the type inside the buckets. To do this, you should take in a Supplier<IDictionary<K, V>> in the constructor and call chain.get() whenever you want to create a chain.

Your ChainingHashDictionary should rehash as appropriate (use an appropriate load factor as discussed in class), and its capacity should always be a prime number. Your ChainingHashDictionary should be able to work with the provided corpora which means there shouldn’t be a hard cap on how much it can grow; though, it doesn’t have to use primes past 400000. Recall that all Hash Tables rely on a reasonable definition of hash function as well as equality testing.

At some point, you will want to test various types of chains in your ChainingHashDictionary. It is confusing to do this initially; so, we have provided some examples in the MarkovTextGenerator class.

# BSTDictionary: Another Another Another Dictionary

In this part, you will implement BSTDictionary. put, get, and containsKey should have average $$\mathcal{O}(\lg(n))$$ behavior, as discussed in class.

remove is pretty tricky. You should look at the slides we posted that describe how it should work.

remove MUST be written recursively to recieve any credit.

Recall that all binary search trees rely on a reasonable definition of comparison, in Java, this is the compareTo method.

# AVLTreeDictionary: Another Another Another Another Dictionary

Warning: This part is difficult, and it will count as “A+” tests (which will only add 3% to your final grade on the project).

In this part, you will implement the put method of AVLTreeDictionary. Most of the methods in AVLTreeDictionary are inherited from BSTDictionary, except put and remove. We do not think remove is instructive enough to ask you to write it though. Be careful to not duplicate code. Additionally, if your rotation code is repetitive, you will not get credit for this part (even if the tests pass).

# NGrams and Generating Text

An NGram is a list of $$n$$ words appearing in order in a text. They are often used in textual analysis to see how frequent patterns are. We have written a library which uses one of your IDictionarys to generate text that sounds like the author of an original text. You can check it out by running MarkovTextGenerator. We recommend using the reddit.corpus corpus which can be downloaded here.