Homework 5 Solution

Consider the problem of printing a paragraph with a mono-spaced font (all characters having the same width) on a printer. The input text is a sequence of n words of lengths l1, l2, ..., ln, measured in characters. We want to print this paragraph neatly on a number of lines that hold a maximum of M characters each. If a given line contains words i through j, where i j, and we leave



exactly one space between words, the number of extra space characters at the end of the line is

j
M j + i k=i lk, which must be non-negative so that the words fit on the line. We wish to minimize the sum, over all lines except the last, of the cube of sum of the numbers of extra space characters at the ends of lines. Give an algorithm to print a paragraph of n words on a printer in a way that minimizes the above sum. Analyze the running time and space requirements of your algorithm.




The longest ascending subsequence problem is defined as follows. Given an array A[1..n] of natural numbers, find the length of the longest ascending subsequence of A. (A subsequence is a list A[i1], A[i2], ..., A[im] for some 1 i1 < i2 < ... < im n. The value m is called the length of the subsequence. Such a subsequence is called ascending if A[i1] A[i2] < ... < A[im]. For simplicity assume all the values in the array are distinct.



Design a divide-and-conquer algorithm for solving the longest ascending subsequence prob-lem in time O(n2). (Hint: Solve a tougher problem. For each position in the array find the cardinality of the longest sequence that ends up with it, and the longest sequence that starts with it. Notice that n2 + 2(n=2)2 + 4(n=4)2 + . . . is O(n2).)



Design a dynamic programming algorithm in time O(n log n). (Hint: Assume you have a data structure in which insert(value) and find(value) is O(log n) operations where the latter operation returns the highest value that was inserted less or equal to value.)



In parallel computing, to solve a problem, processors communicate with others round by round. In each round, processors can concurrently read or exclusively write(CREW) on shared memory, i.e., multiple processors can read a shared memory cell, but only one can write to a given cell at a time. Given a weighted undirected graph G = (V, E), where jV j = n and edge weight are distinct. There are jEj processors and each processor Pi has the input of a unique edge Ei = fu, vg and its weight w(Ei ). Every shared memory cell can hold O(log n) bits. To solve the minimum spanning tree of G, because every processor has only partial information of G, it needs to communicate with others and then decide whether its input edge is in the MST or not. Design an algorithm to solve MST in O(n log n) rounds. Values in the input to the problem are of size O(log n) bits. A cell can hold at most constant number of such values, i.e., the whole description of G cannot be written in a single cell. The output is each processor determines whether its edge is in the MST or not. (Hint: Notice that in this setting if we have a polynomial of n number of processor each holding a value then the minimum value can be found in O(log n) time. To use this assumption you have to show how to do it.)



After class on Wednesday a student asked me why not use the “obvious” greedy algorithm to solve the Knapsack problem. What will the obvious greedy algorithm be? Give a counter example to show that Knapsack is not amenable to a greedy solution (In Dynamic programming we do not fill the Knapsack incrementally making commitments as we go. We either know the whole



1



solution or not. We cannot determine a partial solution that we know can be extended.). Show that nevertheless if the Hiker is in a hurry and she fills the Knapsack using the greedy algorithm then the value she carries is greater equal than half of the optimal value.













Express your algorithm in a well-structured manner. Use pseudo code and the textbook has good examples to follow. Avoid using a long continuous piece of text to describe your algorithm. Start each problem on a NEW page. Unless specified, you should justify the time complexity of your algorithm and why it works. For grading, we will take into account both the correctness and the clarity. Your answers are supposed to be in a simple and understandable manner and sloppy answers are expected to receiver fewer points.



Homework assignments are due on Gradescope. Email attachments or paper submissions are NOT acceptable.



Raw photo is NOT acceptable. Upload your homework as a PDF scan by using a scanner or mobile scanner app. Match each problem with your answer on Gradescope. Use dark pen or pencil and your handwriting should be clear and legible.



We recommend using LATEX, LYX or other word processing software for writing the homework. This is NOT a requirement but it helps us to grade and give feedback.


















































































































2