-2
$\begingroup$

Can some body explain me how to apply memoization technique to achieve linear time complexity for bellow.

http://www.geeksforgeeks.org/dynamic-programming-set-18-word-wrap/

$\endgroup$

closed as off-topic by Kaveh, András Salamon, R B, Jeffε, David Eppstein Aug 3 '14 at 7:10

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Kaveh, András Salamon, R B, Jeffε, David Eppstein
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ What makes you think it’s even possible? $\endgroup$ – Emil Jeřábek supports Monica Jul 10 '14 at 12:17
  • $\begingroup$ It's certainly possible to use memoization, but you won't achieve linear time, the space requirements will be significant, and it's unclear that you'll get any benefit from memoization unless the same word lengths occur. $\endgroup$ – Rob Jul 10 '14 at 14:48
6
$\begingroup$

The linear time algorithms for this sort of problem are based on the SMAWK algorithm rather than more straightforward dynamic programming / memoization. I have an implementation of a linear-time line-breaking algorithm (possibly not exactly the one you want, but likely similar) in the Wrap.py module of my collection of Python algorithm implementations (you'll also need SMAWK.py).

$\endgroup$
  • $\begingroup$ is this solution is with motorization? pastebin.com/th13B9tt I cannot understand how to find k $\endgroup$ – Eshan Sudharaka Jul 10 '14 at 21:19
  • $\begingroup$ I don't understand your question. What is motorization? And what k do you want to find? $\endgroup$ – David Eppstein Jul 11 '14 at 6:06
  • $\begingroup$ Actually I want is to writing a recursive algorithm for word wrap problem and then extending the recursive algorithm to design a more efficient algorithm using memoization. As I understood recursive algorithms should call it self to solve the sub problem. But here it does not call same function. $\endgroup$ – Eshan Sudharaka Jul 11 '14 at 8:52
  • 3
    $\begingroup$ See Rob's comment above. You can do this, but you're very unlikely to get linear time that way. Why is the algorithm's architecture more important than its performance to you? $\endgroup$ – David Eppstein Jul 11 '14 at 16:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.