|
Size: 1671
Comment:
|
Size: 950
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 7: | Line 7: |
| An ''ordered word ladder'' is an alphabetically-ordered sequence of words where each word in the sequence differs from its predecessor by: * changing one letter, e.g. ''barn→born'' * 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: 1. changing one letter, e.g. ''barn→born'' 1. adding or removing one letter, e.g. ''heart→hear'', and ''band→brand'' |
| Line 15: | Line 15: |
| {{{ Your assignment is to write a program that computes the longest word ladder(s) that can be built from a set of words given on stdin. The output of your program is the maximum length ordered word ladder, together with all the ordered word ladders that have this length. |
At the heart of the assignment is a function that compares 2 strings and returns ''true'' if the strings satisfy one of the 2 conditions above, and ''false'' otherwise. This function could have the signature: {{{#!cplusplus bool areOwl(char *, char *) }}} Write such a function and of course test it. |
| Line 18: | Line 22: |
| You should also a complexity analysis (of time) using Big-oh notation. }}} The following conditions apply to the input: * it may be empty * the words are alphabetically ordered, and must be lower case (''a-z'') * no word is more than 19 letters * there will be no more than 1000 words * there is no punctuation or digits in the input Some comments about the programming: * There are no restrictions on using arrays. * You should use ADTs, in particular stack, queue and graph ADTs, if possible. * Call your source program ''ladders.c'' (for submission purposes). * In ''ladders.c'' include the statement {{{#!cplusplus #include "complexity.h" }}} This header file should contain the complexity analysis as a comment (hence use simple text). Obviously this header file should be submitted as well. |
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:
changing one letter, e.g. barn→born
adding or removing one letter, e.g. heart→hear, and band→brand
The following are examples of word ladders of different length:
ban→bar→boar→boat→goat, length 5
cab→can→cane→dane→date→mate→mite→site→size, length 9
At the heart of the assignment is a function that compares 2 strings and returns true if the strings satisfy one of the 2 conditions above, and false otherwise. This function could have the signature:
1 bool areOwl(char *, char *)
Write such a function and of course test it.
Details of the assignment will follow shortly.