From aff0f61f1bb313ca717c02334eacfc2dbdfb51cb Mon Sep 17 00:00:00 2001 From: Chris Barker Date: Sat, 18 Dec 2010 14:08:57 -0500 Subject: [PATCH] edits --- assignment10.mdwn | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) diff --git a/assignment10.mdwn b/assignment10.mdwn index ad6ebb14..c1a84d3b 100644 --- a/assignment10.mdwn +++ b/assignment10.mdwn @@ -9,6 +9,25 @@ > it with. + As Ken Shan points out, this is an instance of the algorithm + for converting name/year citations (like 'v. Montague 1970') + to numerals corresponding to their ('v. [24]'). Except that + bibliograpic numerals don't start with zero. + + Give some thought to efficiency: there are straightforward + solutions that involve traversing the tree once (in order to, + say, construct a suitable mapping from leafs to ints), then + traversing it again to do the conversion. Can you find a + solution that traverses the tree exactly once, replacing each + leaf as soon as you see it? + + Consider a variation in which you must replace each leaf with + is number of occurrences in the tree. Is there any way to do + that with a single traversal? + + You can assume that the tree is leaf-labeled (no labels on the + internal nodes), and that the leafs are, say, chars. + Here is [a hint](/hints/assignment_10_hint). -- 2.11.0