I was discussing parallel web page layout in class and mentioned that drawing text in parallel is quite difficult. That made me think: what about other text-related algorithms? So in this post I'll describe my five-hours' amusement: a parallel line-breaking algorithm. Defining the problem By line breaking I mean the task of figuring out which words each line of text contains. In a web browser, this is always done greedily. That is, let's suppose we've already measured each word in the line of...
