The objective is to implement algorithms for solving text formatting problems (Printing Neatly), and to provide an experimental study of their running time and the quality of the solutions found. This is a problem of neatly printing a paragraph with a mono-spaced font (all characters having same width) on a printer. The input text is a sequence of n words of lengths l1, l2, ....., ln, measured in characters. The idea is to print this paragraph neatly on a number of lines that hold a maximum of M characters each. The study of this problem is done by programming different algorithms and then, three types of alignments are explored, namely left, center and right. The following algorithms were used in this project:
- Dynamic programming
- Greedy approach
- Branch and Bound
- Divide and conquer
- Binary search
- Shortest path
- Brute force approach
The efficiency of every algorithm was studied by calculating a cost which is defined as the cube of empty spaces in a line. Then the algorithms were tested with different text paragraphs like:
- Case Study 1 : Low word count
- Case Study 2 : Random Paragraphs
- Case Study 3 : Fixed character paragraph
- Case Study 4 : Fixed word paragraph
Runtime, cost and quality of every algorithm was found for the final analysis.