Home Accessibility Courses Twitter The Mouth Facebook Resources Site Map About Us Contact
 
For 2023 (and 2024 ...) - we are now fully retired from IT training.
We have made many, many friends over 25 years of teaching about Python, Tcl, Perl, PHP, Lua, Java, C and C++ - and MySQL, Linux and Solaris/SunOS too. Our training notes are now very much out of date, but due to upward compatability most of our examples remain operational and even relevant ad you are welcome to make us if them "as seen" and at your own risk.

Lisa and I (Graham) now live in what was our training centre in Melksham - happy to meet with former delegates here - but do check ahead before coming round. We are far from inactive - rather, enjoying the times that we are retired but still healthy enough in mind and body to be active!

I am also active in many other area and still look after a lot of web sites - you can find an index ((here))
Least Common Ancestor - what is it, and a Least Common Ancestor algorithm implemented in Perl

Imagine you have a tree - a series of leaves which join together as you head towards the root into bigger and bigger branches. The "Least Common Ancestor" is the point at which the branches from two leaves you have chosen come together. In computing, such a tree structure is very common - files and folders / directories, and heirarcies of classes, being two common examples.

Over the past couple of days, I've received several requests through our enquiry page if it's possible to write a Least Common Ancestor program in Perl. It's rather odd to have received such a batch of questions, and I think that - somewhere in the world where our web site is used as a reference - this has been set as a class exercise. The easy answer is "Yes - you can write anything in Perl"; my longer answer the first time I was asked was "How much Perl do you know / can I help / do you even need to come and learn Perl on one of our Perl courses?". But I got no reply - not even an acknowldegement (and, by the way, for readers from non-English cultures, it's regarded as impolite to ask a question, have someone spend a lot of time writing and answer, and not even acknoledge the help / say "Thank you").

But ... I admit ... I was very interested in how easy the question was ... so when I woke this morning I set myself the challenge of writing a Least Common Ancestor program in Perl. The source code is [here]. Now - there are plenty of learned papers on efficient ways of doing this, with recursive code that looks very clever - but I came up with something much simpler.

1. Define all of the branch relationships in a hash
2. Generate two list of ancestor - one for the two start points you're interested in
3. Staring at the end of those lists, compare individual members until you find ones which are NOT common
... and the last common ancestor you found was also the LEAST common one.

The sample program worked with a single test case that I rushed through it; note that it needs further testing especially for special cases such as for leaves that have no common ancestor at all, and for leaves where one of the leaves actually given as an input is an ancestor of the other.

Should I have written the code? Should I pass on the URL of this item and the sample to my new enquirers and the original one? Well - I'm not going to start sending more emails to the first (rude?) chap / chapess. But this code is a useful example / algorithm I can make plenty of re-use of during demonstrations and courses. It illustrates topicalisation, named blocks of code (subs)i, hashes, lists, "here" documents, passing parameters by address, scoping of variable using "my" and much more. So it will be useful to other people who need it in a far wider area. If people who are looking for help with homework take a copy and hand it in (they should add my copyright notice to it, but probably wouldn't), then they only have themselves to blame when they end up learning little about Perl, and lots about how to steal other people's code. But - come to think of it - it's pretty efficient to re-use code provided that you do it legally!

(written 2010-11-11)

 
Associated topics are indexed as below, or enter http://melksh.am/nnnn for individual articles
Q110 - Object Orientation and General technical topics - Programming Algorithms
  [202] Searching for numbers - (2005-02-04)
  [227] Bellringing and Programming and Objects and Perl - (2005-02-25)
  [642] How similar are two words - (2006-03-11)
  [1157] Speed Networking - a great evening and how we arranged it - (2007-04-21)
  [1187] Updating a page strictly every minute (PHP, Perl) - (2007-05-14)
  [1391] Ordnance Survey Grid Reference to Latitude / Longitude - (2007-10-14)
  [1840] Validating Credit Card Numbers - (2008-10-14)
  [1949] Nuclear Physics comes to our web site - (2008-12-17)
  [2189] Matching disparate referencing systems (MediaWiki, PHP, also Tcl) - (2009-05-19)
  [2259] Grouping rows for a summary report - MySQL and PHP - (2009-06-27)
  [2509] A life lesson from the accuracy of numbers in Excel and Lua - (2009-11-21)
  [2586] And and Or illustrated by locks - (2010-01-17)
  [2617] Comparing floating point numbers - a word of caution and a solution - (2010-02-01)
  [2894] Sorting people by their names - (2010-07-29)
  [2951] Lots of way of converting 3 letter month abbreviations to numbers - (2010-09-10)
  [2993] Arrays v Lists - what is the difference, why use one or the other - (2010-10-10)
  [3072] Finding elements common to many lists / arrays - (2010-11-26)
  [3093] How many toilet rolls - hotel inventory and useage - (2010-12-18)
  [3102] AND and OR operators - what is the difference between logical and bitwise varieties? - (2010-12-24)
  [3451] Why would you want to use a Perl hash? - (2011-09-20)
  [3620] Finding the total, average, minimum and maximum in a program - (2012-02-22)
  [3662] Finding all the unique lines in a file, using Python or Perl - (2012-03-20)
  [4325] Learning to program - what are algorithms and design patterns? - (2014-11-22)
  [4401] Selecting RECENT and POPULAR news and trends for your web site users - (2015-01-19)
  [4402] Finding sum, minimum, maximum and average in Python (and Ruby) - (2015-01-19)
  [4410] A good example of recursion - a real use in Python - (2015-02-01)
  [4652] Testing new algorithms in PHP - (2016-02-20)
  [4656] Identifying the first and last records in a sequence - (2016-02-26)
  [4707] Some gems from an introduction to Python - (2016-10-29)

P251 - Perl Review
  [2242] So what is this thing called Perl that I keep harping on about? - (2009-06-15)
  [3007] Setting up a matrix of data (2D array) for processing in your program - (2010-10-21)
  [3407] Perl - a quick reminder and revision. Test yourself! - (2011-08-26)
  [3430] Sigils - the characters on the start of variable names in Perl, Ruby and Fortran - (2011-09-10)

P211 - Perl - Hashes
  [240] Conventional restraints removed - (2005-03-09)
  [386] What is a callback? - (2005-07-22)
  [738] (Perl) Callbacks - what are they? - (2006-05-30)
  [930] -> , >= and => in Perl - (2006-11-18)
  [968] Perl - a list or a hash? - (2006-12-06)
  [1334] Stable sorting - Tcl, Perl and others - (2007-09-06)
  [1705] Environment variables in Perl / use Env - (2008-07-11)
  [1826] Perl - Subs, Chop v Chomp, => v , - (2008-10-08)
  [1856] A few of my favourite things - (2008-10-26)
  [1917] Out of memory during array extend - Perl - (2008-12-02)
  [2833] Fresh Perl Teaching Examples - part 2 of 3 - (2010-06-27)
  [2836] Perl - the duplicate key problem explained, and solutions offered - (2010-06-28)
  [2915] Looking up a value by key - associative arrays / Hashes / Dictionaries - (2010-08-11)
  [2920] Sorting - naturally, or into a different order - (2010-08-14)
  [3106] Buckets - (2010-12-26)
  [3400] $ is atomic and % and @ are molecular - Perl - (2011-08-20)


Back to
Java - basic rules for arithmetic, variables and conversion
Previous and next
or
Horse's mouth home
Forward to
Gathering information - logging - with log4j. First steps.
Some other Articles
Java Beans, tag libraries and JSPs - what and why.
After Course Resources - do we publish sample answers. Example from Java Exceptions module.
Changing a Servlet - more that just editing and compiling
Gathering information - logging - with log4j. First steps.
Least Common Ancestor - what is it, and a Least Common Ancestor algorithm implemented in Perl
Java - basic rules for arithmetic, variables and conversion
Doing several things at the same time - Java threads
Fresh Paint - Java Arrays
Setting up individual variables, and arrays, in Java - some commented examples
Looking back and forward personally - 6 years each way
4759 posts, page by page
Link to page ... 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96 at 50 posts per page


This is a page archived from The Horse's Mouth at http://www.wellho.net/horse/ - the diary and writings of Graham Ellis. Every attempt was made to provide current information at the time the page was written, but things do move forward in our business - new software releases, price changes, new techniques. Please check back via our main site for current courses, prices, versions, etc - any mention of a price in "The Horse's Mouth" cannot be taken as an offer to supply at that price.

Link to Ezine home page (for reading).
Link to Blogging home page (to add comments).

You can Add a comment or ranking to this page

© WELL HOUSE CONSULTANTS LTD., 2024: 48 Spa Road • Melksham, Wiltshire • United Kingdom • SN12 7NY
PH: 01144 1225 708225 • EMAIL: info@wellho.net • WEB: http://www.wellho.net • SKYPE: wellho

PAGE: http://www.wellho.net/mouth/3042_Lea ... -Perl.html • PAGE BUILT: Sun Oct 11 16:07:41 2020 • BUILD SYSTEM: JelliaJamb