1. Daphna is dining daily at her favorite cafeteria, which serves salad, lasagna or pasta. While always craving for something prior to leaving the office, Daphna frequently changes her mind upon reaching the cafeteria. For example, if Daphna craved for a salad, there is a 70% chance she’ll have a salad, 20% lasagna and 10% pasta. In a similar manner, if Daphna craved for a lasagna or a pasta, the probabilities are (0.9, 0.05, 0.05) and (0.6, 0.3, 0.1) (preserving the (salad/lasagna/pasta) order), respectively. What Daphna craves for the next day depends on what she craved for previous day (and not on what she actually ate): after craving for a salad, there’s a 10% chance Daphna will crave for a salad the next day, 50% lasagna and 40% pasta. The transition probabilities from craving for lasagna and pasta are (0.9, 0.05, 0.05) and (0.7, 0.2, 0.1), respectively.
(a) Design an HMM describing Daphna’s eating behavior.
(b) Assume that the initial probabilities for (salad, lasagna, pasta) are (0.2,0.4,0.4). If in five consecutive days Daphna ate, in order, pasta, salad, lasagna, pasta and salad, what is the most probable sequence of daily cravings?
2. The Decoding problem can be formulated as a longest path problem in a directed acyclic graph. This motivates a question about a space-efficient version of the decoding algorithm. Does there exist a linear-space algorithm for the decoding problem?