Assignment: • Problem Set (not-for-grade, but still required): Textbook Exercises 15.1-3, 15.1-4, 15.3-2, 15.3-5 • Programming Assignment: As you know at this point, Dynamic Programming is a powerful technique that explores all possible cases to obtain a solution, yet achieves an exponential improvement in running time when compared with a simpler brute-force approach. A well-known example of Dynamic Programming usage is Text Justification, where we are given an array of words and a page width and we have to decide how to split the text so that it looks “nice” after justifying against margins. The purpose of this homework is to compare experimentally the result obtained justifying text with a greedy algorithm (as used by MS Word) against doing the same using LATEX rules and Dynamic Programming. Specifically, your assignment is the following. 1. (15 points) Implement a “badness” method that, given a width ? as a number of characters, an array W[0 . . . n-1] of strings, and two indices i and j such that 0 = i = n – 1 and 1 = j = n, computes the following function used by LATEX. badness(W, i, j, ?) = (? – `(W, i, j))3 if ? – `(W, i, j) = 0, 8 otherwise. Where `(W, i, j) is the total length in characters of the words from index i to j – 1 in the array W, taking into account that one space must be left in between each pair of consecutive words. 2. (40 points) Implement a “split” method that, given as parameters the width ? and the array W, returns a list L of the indices of the array where each line should start to minimize the aggregated badness (i.e. the sum of the badness of all lines in such split). The Dynamic Programming pseudocode to compute the minimum aggregated badness seen in class follows in Algorithms 1 and 2. You have to expand it to return the list of indices of the corresponding split.

 

Doing a similar assignment? Save your time and hire our Genuine Essay Writers to do your task. Get 15% Discount on your 1st order. Use code: FREE15