ITEC 380 2014fall ibarland

home—lectures—recipe—exams—hws—D2L—breeze (snow day)

hw-ec-sort
sorting by design recipe
extra-credit review/practice problem

The following program is a basic review on following the design-recipe, specific to lists. I'll give 15pts of extra-credit (homework) points. As you complete it, think about how the same design-recipe steps guide you when writing code for other types of data (e.g. Exprs).

Write a function to sort a list, using the design recipe.

• Sort a list of numbers into increasing order¹.
• You may use Racket or Java.
  If using Java, use the classes SList, EmptyList, and ConsList as provided below.
• Follow each step of the-design-recipe—the design recipe: final version — in particular, include the data definition for a list-of-number, and the template for processing a list-of-number.
  For the inventory-with-values (step 6), use the list (list 7 4 2 9 8)² as your example-input (as well as one test-case). That is: write down what each pertinent piece³ of the template evaluates to, for this particular input.

  Remember, the only non-rote thinking is: “what is the general rule I want, to combine the particular pieces given to me by the template?”. The inventory-with-values gives you a concrete example to help you, when you try to formulate that rule in the following step.

• In deciding how to combine the pieces of the template to get the overall answer, you'll find there is a natural helper function you wish you had. Although it is not built-in to racket or Java, this helper does follow directly from the design recipe. So: complete your sort function by wishfully calling the not-yet-written helper, and then write the helper function again following each step of the design recipe.

  Hint: for the helper's inventory-with-values, use 7 and (list 2 4 8 9) as your example-inputs.

• What standard sorting-algorithm is this? (Hint: if you used a descriptive name for your helper-function, you'll have already figured out the answer to this one.) Add a comment at the top of your file, with this answer.
• (5pts additional): Write this same algorithm in Prolog. Just include the Prolog program in a comment at the top of your file.
• Submit this problem on D2L by the end of finals week (Dec.11 17:00), though of course it's most effective to practice the design recipe before the exam.

 1  abstract class SList {
 2    }
 3    
 4  
 5  
 6  class EmptyList extends SList {
 7    // No fields.
 8    
 9    // Java's default constructor does what we want, so we won't provide one.
10  
11    @Override
12    public String toString() { return "new EmptyList()"; }
13    }
14   
15  
16  class ConsList extends SList {
17    int n;
18    SList rest;
19    
20    
21    // Provide the boilerplate constructor:
22    ConsList( int _n, SList _rest ) {
23        this.n = _n;
24        this.rest = _rest;
25      }
26      
27    @Override
28    public String toString() {
29        return "new ConsList( " + this.n + ", " + this.rest.toString() + ")";
30      }
31    }
32  

home—lectures—recipe—exams—hws—D2L—breeze (snow day)

©2014, Ian Barland, Radford University Last modified 2014.Dec.07 (Sun)

Please mail any suggestions (incl. typos, broken links) to ibarlandradford.edu