|
Size: 1068
Comment:
|
Size: 981
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| #acl All: | #acl All:read |
| Line 5: | Line 5: |
| = Assignment 2: Word Ladder = | = Assignment 2: Ordered Word Ladders = |
| Line 7: | Line 7: |
| A ''word ladder'' is a sequence of words * which are in alphabetic order * each word in the sequence differs from its predecessor by * changing one letter, e.g. ''born→barn'' * adding or removing one letter, e.g. ''band→brand'' |
An ''ordered word ladder'' ('owl') is an alphabetically-ordered sequence of words where each word in the sequence differs from its predecessor by one action: 1. changing one letter, e.g. ''barn→born'' 1. adding or removing one letter, e.g. ''band→brand'' and ''bran→ran'' |
| Line 13: | Line 11: |
| The following are examples of word ladders of different length (that could each easily be made longer): * ''big→bit→bat→boat'', length 4 * ''cold→cord→word→ward→warm'', length 5 * ''line→fine→five→dive→live→like→lake→take→bake→cake→came→fame'', length 12 |
The following are examples of word ladders of different length: * ''ban→bar→boar→boat→goat'', length 5 * ''an→can→cane→dane→date→mate→mite→site→size'', length 9 |
| Line 18: | Line 15: |
| {{{ Your assignment is to write a program that computes the longest word chain(s) that can be built from a set of words given on ''stdin''. The output of your program is the maximum length of all the word chains that can be built from the input words, together with all the word chains that have this length. |
At the heart of the assignment is a function that compares 2 arbitrary null-terminated strings and returns ''true'' if the strings satisfy one of the 2 conditions above, and ''false'' otherwise. This function has signature: {{{#!cplusplus bool differByOne(char *, char *) }}} Write such a function and of course test it. |
| Line 21: | Line 22: |
| You should also a complexity analysis (of time) using ''Big-oh'' notation. }}} |
Details of the assignment will follow shortly. |
Contents
Assignment 2: Ordered Word Ladders
An ordered word ladder ('owl') is an alphabetically-ordered sequence of words where each word in the sequence differs from its predecessor by one action:
changing one letter, e.g. barn→born
adding or removing one letter, e.g. band→brand and bran→ran
The following are examples of word ladders of different length:
ban→bar→boar→boat→goat, length 5
an→can→cane→dane→date→mate→mite→site→size, length 9
At the heart of the assignment is a function that compares 2 arbitrary null-terminated strings and returns true if the strings satisfy one of the 2 conditions above, and false otherwise. This function has signature:
1 bool differByOne(char *, char *)
Write such a function and of course test it.
Details of the assignment will follow shortly.