Algorithms - Convert String to Graph (deciphering codewords)

(PART A)

A dictionary cipher substitutes each word in the dictionary by a string according to a codebook. Example codebook can be like below. We have a part of the codebook that allows us to translate some words but are missing the other part. A long cipher-text with n letters is provided. "jkjkuieuijuuyakjelkjkiekjaueajuseilloppyyaskjirrjkjauieukjkaiejjuyyajjuuyakjel" Our goal is to split the cipher text to highlight known words and parts that cannot be decoded. For instance, the messge above may be split as follows: "jkjkuieui + juuyakjel + kjkie + kjaue + ajusei + lloppyy + askjirr + jkjauieu + kjkaiejjuyyaj + juuyakjel" This split yields 6 known codewords (underlined) from the codebook and 34 characters that areciphered, i.e., not part of a known codeword. The cost of such a split is taken to be 6 + 2 * 34 = 74. Formally, we are given a codebook with codewords and a long cipher-text string with n characters. Our goal is to find a minimum cost split that splits the given cipher text into a set of known codewords and ciphered characters so that the cost (defined as number of code words + 2 * numberof ciphered characters) is minimized. Show how a given string can be converted in to a graph whose vertices are the positions in the string and edges encode cost. Show how you can add edges to the graph corresponding tocodewords and ciphered characters. A dictionary cipher substitutes each word in the dictionary by a string according to a codebook. Example codebook can be like below. We have a part of the codebook that allows us to translate some words but are missing the other part. A long cipher-text with n letters is provided. "jkjkuieuijuuyakjelkjkiekjaueajuseilloppyyaskjirrjkjauieukjkaiejjuyyajjuuyakjel" Our goal is to split the cipher text to highlight known words and parts that cannot be decoded. For instance, the messge above may be split as follows: "jkjkuieui + juuyakjel + kjkie + kjaue + ajusei + lloppyy + askjirr + jkjauieu + kjkaiejjuyyaj + juuyakjel" This split yields 6 known codewords (underlined) from the codebook and 34 characters that areciphered, i.e., not part of a known codeword. The cost of such a split is taken to be 6 + 2 * 34 = 74. Formally, we are given a codebook with codewords and a long cipher-text string with n characters. Our goal is to find a minimum cost split that splits the given cipher text into a set of known codewords and ciphered characters so that the cost (defined as number of code words + 2 * numberof ciphered characters) is minimized. Show how a given string can be converted in to a graph whose vertices are the positions in the string and edges encode cost. Show how you can add edges to the graph corresponding tocodewords and ciphered characters