3 ms·
I spent a year and a half as an undergraduate converting a custom C edit distance implementation into Java for a computer assisted language instruction system.
by keefe 18y ago
I spent a year and a half as an undergraduate converting a custom C edit distance implementation into Java for a computer assisted language instruction system. This is a really nice article discussing the topic. I think the interesting facet of dynamic programming is how it shows the dynamic between space and time. In his creative book on algorithms, Udi Manber gives a nice description of a general approach to designing algorithms with dynamic programming.
- ovi256 18y agoA year and a half ? How many SLOCs was that ?
- keefe 18y agoI haven't a clue this was like 99-01, it wasn't just edit distance algorithm but also all the UI code surrounding it and optimizing things for learning a foreign language. Basically it was a quiz program in (e.g.) German which compared the student's answer to the proper answer and then generated suggestions when appropriate. We did a lot of tweaking of that code, iterating through versions starting with an attempt to just port some C code and onward - I was pretty green at that time and it wasn't a full time job, so it's not like implementing edit distance took you know, 70 man weeks...