## CS13002 Programming and Data Structures | ## Section: 4/D, Spring 2005 |

## Assignment 6

This exercise is based on string manipulation and handling of two-dimensional arrays. You are given a text file. Your problem is to adjust the spaces in each line in such a way that the resulting text is justified (both at the left and at the right). Here is our proposal of an algorithm that you should use in order to solve the problem.

- First read the input file and store the lines in a two-dimensional character array with each line stored in a single row of the array.
- The text is divided into paragraphs. Two consecutive paragraphs are separated by a blank line.
- The last line in a paragraph is
notto be justified. Also a blank line is not to be justified.- Finally suppose that you have a non-blank line which is not the last line of a paragraph. If the length of this line is already larger than the target width, then do not perform any processing of this line. Otherwise, increase the sizes of the inter-word gaps so that the resulting line has a width equal to the target width.
Assume that

lendenotes the initial length of the line and that the line initially containsnspnumber of inter-word spaces. You have to add a total ofextra = target_width - lennumber of additional spaces in the line. In order that the insertion leads to (aesthetically) good-looking paragraphs, it is necessary to distribute the

extranew spaces more or less uniformly among thenspinter-word gaps. Letq = extra / nsp (integer division).First insert q additional spaces in

eachof thenspgaps. Ifextrais not an integral multiple ofnsp, this still leaves us withr = extra - q * nspspaces to be inserted. If the line has an odd number in the current paragraph, add another single space in each of the first

rgaps. On the other hand, if the line has an even number in the current paragraph, add a single space in each of the lastrgaps.Here is an example. Consider the following line:

Deciding the truth of a statement in a formal system was called thewhich has a length of 67. Assume that the target width is 75. You have to add 8 extra spaces to the line. The line contains 12 inter-word gaps. If the line has an odd number in the paragraph, then the leftmost 8 inter-word gaps should be increased from one space to two spaces, else the rightmost 8 gaps need be so increased. In the former case, the line would look like

Deciding the truth of a statement in a formal system was called theand in the latter case it would look like

Deciding the truth of a statement in a formal system was called theIf we started with a smaller line like

Deciding the truth of a statement in a formal system was calledthat needs 75-63=12 spaces to be added among 11 gaps, the line after justification would look like

Deciding the truth of a statement in a formal system was calledor

Deciding the truth of a statement in a formal system was calleddepending on its position in the paragraph.- Replace each row of your two-dimensional array by its justified version using the above rules.
- Print the resulting justified text line-by-line.
- Take the target width to be 75. There is a total of 230 lines in this file and each line has a width no bigger than 75.
The following should be the output of your program for the fourth paragraph of the input file.

The design of the first commercially available mechanical calculator is attributed to Leibnitz (1671) (the same bloke who invented calculus). It was completed in 1694 and Leibnitz demonstrated, for the first time, that binary arithmetic was superior to decimal arithmetic as it simplifies machine construction. Leibnitz's machine could add, subtract, multiply, divide and even find square root. Leibnitz's machine was a full adder (you'll learn about a full adder in your Digital Hardware Design course), in which the carry was saved in the form of the position of a lever. A working model of this machine was exhibited at the Royal Society of London in 1794, but it was somewhat unreliable. It was commercially available in 1820.