Differences between revisions 14 and 24 (spanning 10 versions)
⇤ ← Revision 14 as of 2019-07-14 18:09:01 →
Size: 1766
Editor: AlbertNymeyer
Comment:
← Revision 24 as of 2019-07-15 08:40:44 → ⇥
Size: 1680
Editor: AlbertNymeyer
Comment:
Deletions are marked like this. Additions are marked like this.
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'' 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''
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
 * ''cab→can→cane→dane→date→mate→mite→site→size'', length 9
Line 18: Line 15:
/*
Line 19: Line 17:
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. 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.
Line 29: Line 27:
 * there is no punctuation or digits in the input
Line 33: Line 32:
 * Call your source program ''ladder.c'' (for submission purposes).
  * In ''ladder.c'' include the statement		  * Call your source program ''ladders.c'' (for submission purposes).
  * In ''ladders.c'' include the statement
Line 39: Line 38:
 */

Contents

  1. Assignment 2: Ordered Word Ladders

Assignment 2: Ordered Word Ladders

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

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 

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.

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 

         1   #include "complexity.h"
   2
      This header file should contain the complexity analysis as a comment (hence use simple text). Obviously this header file should be submitted as well.

Assignment2 (last edited 2019-07-31 22:35:13 by AlbertNymeyer)