Coursera: algs4partII-001. Неделя 5.

[svetasmirnova]

Часть 1. Regular Expressions

1. The set of states that the NFA could be in after reading defined character sequence. Тут нужно перечислить, в которые можно попасть. Например, для выражения ((a*b)*) после прочтения a можно попасть только в b, а после прочтения b можно попасть и в конец выражения, и вернуться к скобке перед a и оттуда в a или в b.
2. Edges in the epsilon-transition digraph. Тут всё просто, но после нескольких пропущенных пришлось рисовать на бумажке.

Часть 2. Data Compression.

 

1. Huffman trie. Здесь было непонятно как построить trie, если все ноды повторяются уникальное количество раз, например: 1, 2, 3, 4, 5. Понимания добавила картинка из Wikipedia. Вкратце смысл такой: 1 и 2 составляют первую пару с суммой 3, 3 и 4 - вторую с суммой 7, но так как 5 < 7, то 5 образует пару с (1 и 2).
2. Expanding LZW. Здесь у меня возникла сложность с добавлением в словарь более, чем двухбуквенных последовательностей, особенно если они шли в паре с двухбуквенными. Какую вырать и какой по счёту? Наверное, опять-таки лучшее объяснение в Wikipedia
3. LZW compression. Те же проблемы, что и в предыдущем пункте, то же решение.