Homework 8 due Apr. 4 (hardcopy only, handwritten is fine) This homework has two parts. The first part is exercises from the textbook. The second part is a programming assignment. (The second part was originally part of the previous homework assignment, but it has now been deferred and is part of hw8. Please include both part _even_ if you already handed in the programming assignment earlier.) Both parts are due by Monday, April 4. Homework #8 is from Chapter 6. Exercises: 6.13, 6.16, 6.18, 6.19, 6.21, 6.22 === PART II: You must use dynamic programming to re-format the Gettysburg address of Abraham Lincoln to fit in lines of 20 columns. The Gettysburg address is a speech by President Abraham Lincoln after the Battle of Gettysburg, the largest battle of the American Civil War. You will need to produce two dynamic programming algorithms. For each of the two algorithms, you will need to report: A. Description of the algorithm B. Source code to run the algorithm (in a mainstream language: C/C++/Java) C. Output of running the program on the Gettysburg address. The output must: 1. print the re-formatted paragraph in 20 columns per line. 2. print the total penalty for that re-formatted paragraph. ALGORITHM 1: Minimize the number of space characters. A word is any sequence of non-space characters, including punctuation. There must be at least one space between any pair of adjacent words, unless there is a line break between the two words. Each line must begin with a non-space character and end with a non-space character. A penalty function is given by: sum ( max(s_i -1, 0) )^2 where s_i is the number of spaces at the end of the i-th word. If a word ends a line, we can count it as having zero spaces after the word. For example, "Now is the time for all good men to come to the aid of their country." becomes: 12345678901234567890 Now is the time for all good men to come to the aid of their country. with s_i = {2, 1, 1, 1, 0, 3, 3, 2, 0, 3, 3, 2, 0, 3, 2, 0} and penalty 1+4+4+1+4+4+1+4+1 = 24 [ This is not the best. There is a way to do it with 22 characters by putting "for" on the next line. ] ALGORITHM 2: Same idea as Algorithm 1, but on the last line, there is no penalty for the spaces at the end of the last line. 12345678901234567890 Now is the time for all good men to come to the aid of their country. with s_i = {2, 1, 1, 1, 0, 1, 1, 1, 1, 0, 2, 1, 1, 1, 0, 0} and penalty 1+1 = 2 ==== Here is the Gettysburg Address: Four score and seven years ago our fathers brought forth on this continent, a new nation, conceived in Liberty, and dedicated to the proposition that all men are created equal. Now we are engaged in a great civil war, testing whether that nation, or any nation so conceived and so dedicated, can long endure. We are met on a great battle-field of that war. We have come to dedicate a portion of that field, as a final resting place for those who here gave their lives that that nation might live. It is altogether fitting and proper that we should do this. But, in a larger sense, we can not dedicate -- we can not consecrate -- we can not hallow -- this ground. The brave men, living and dead, who struggled here, have consecrated it, far above our poor power to add or detract. The world will little note, nor long remember what we say here, but it can never forget what they did here. It is for us the living, rather, to be dedicated here to the unfinished work which they who fought here have thus far so nobly advanced. It is rather for us to be here dedicated to the great task remaining before us -- that from these honored dead we take increased devotion to that cause for which they gave the last full measure of devotion -- that we here highly resolve that these dead shall not have died in vain -- that this nation, under God, shall have a new birth of freedom -- and that government of the people, by the people, for the people, shall not perish from the earth. And here is the Gettysburg Address as a declaration in the C language. A similar statement will work for C++ and Java. char paragraph[] = "Four score and seven years ago our fathers brought forth on this " \ "continent, a new nation, conceived in Liberty, and dedicated to the " \ "proposition that all men are created equal. Now we are engaged in a " \ "great civil war, testing whether that nation, or any nation so conceived " \ "and so dedicated, can long endure. We are met on a great battle-field " \ "of that war. We have come to dedicate a portion of that field, as a " \ "final resting place for those who here gave their lives that that nation " \ "might live. It is altogether fitting and proper that we should do this. " \ "But, in a larger sense, we can not dedicate -- we can not consecrate -- " \ "we can not hallow -- this ground. The brave men, living and dead, who " \ "struggled here, have consecrated it, far above our poor power to add or " \ "detract. The world will little note, nor long remember what we say here, " \ "but it can never forget what they did here. It is for us the living, " \ "rather, to be dedicated here to the unfinished work which they who " \ "fought here have thus far so nobly advanced. It is rather for us to be " \ "here dedicated to the great task remaining before us -- that from these " \ "honored dead we take increased devotion to that cause for which they gave " \ "the last full measure of devotion -- that we here highly resolve that " \ "these dead shall not have died in vain -- that this nation, under God, " \ "shall have a new birth of freedom -- and that government of the people, " \ "by the people, for the people, shall not perish from the earth." ; If you like, you can append to the above statement this short C/C++ program: #include int main() { /* Null character at end of C string must be subtracted off. */ printf("Number of characters: %d\n", sizeof(paragraph) - 1) } Executing that program will show you that there are 1473 characters.