Provide Python 3.7-compatible implementations of either one or two HMM algorithms so as to be able to demonstrate how these algorithms work. The first algorithm should be the Forward Algorithm, which takes a sequence of observations and uses that information to repeatedly estimate the a-posteriori probability distribution over the set of possible states.

The optional second algorithm ("Viterbi") should take a sequence of observations and use it to determine the most likely state sequence.

Applications: Choose an application domain in which to demonstrate your software. For this domain, either find or create reasonable-looking data that you can use for your algorithms. Design a suitable state space for each application, and develop a reasonable transition model and a reasonable emission model.

Here is a list of suggested application domains:

1. speech recognition
2. music recognition
3. location tracking
4. microbiological sequence recognition

Output formats: The ideal form of output for your program is a kind of annotated trellis diagram. This diagram shows a sequence of stages and the belief function associated with each stage. Such a diagram could be produced either with graphics (e.g., with Tkinter or the Python svgwrite module) on the screen or by printing out the sequence of belief functions in a sort of vertical format using print statements.

Here is an example of a trellis diagram for an application of HMMs to part-of-speech tagging in natural language processing

Example of a trellis diagram. This comes from www.endtoend.ai.

Test examples: Part of the testing, debugging, and demonstration of your code should focus on a simple test HMM that makes it obvious whether your algorithms are working correctly or not. We leave it to you to design such a test case, but the lead TA for this project option may choose to give you a specific test case.