Teaching
2500 F '12
 
Assignments
The Hand In
Set 1
Set 2
Set 3
Set 3h
Set 4
Set 4h
Set 5
Set 5h
Set 6
Set 6h
Set 7
Set 7h
Set 8
Set 9
Set 8h
Set 10
Set 9h
Set 11
Set 12
Set 10h

Problem Set 6

Due date: 10/16 @ 11:59pm

Programming Language: Begnning Student Language with List Abbreviations


NOTE: This assignment is due the Tuesday night, after the exam.

This problem set continues the study of self-referential unions. Some of the problems cover functions that process two arguments from classes with complex (self-referential) data definitions. You must follow the design recipe. The graders will look for data definitions, contracts, purpose statements, examples/tests, and properly organized function definitions. For the latter, you must design templates. You do not need to include the templates with your homework, however. If you do, comment them out.


Problem A1:

Here is a data definition:

;; A family-tree-node is one of: 
;; - empty 
;; - (make-child father mother name date hair-color) 
;; where father and mother are family-tree-nodes, 
;; name and hair-color are symbols, and date is a number.
Use the above data definition to solve the following problems:
  1. Develop the function count-older that consumes a family-tree-node and a year and returns the number of people in the tree that were born that year or earlier.
  2. Develop the function search-tree-older that consumes a family-tree-node and a number and produces a list of all of the people in the tree born in that year or earlier.
  3. Develop the function red-haired-ancestors? that determines whether a family-tree-node contains an ancestor with red hair on the father's side and an ancestor with red hair on the mother's side.
  4. Develop the function update-father that consumes two family-tree-nodes and produces a family-tree-node that updates the father of the first tree to be the second tree.

Problem A2:

Cartesian coordinates:

  1. Develop the function make-points, which combines a list of x-positions and a list of y-positions into a list of posns. Assume the lists are of equal length.
  2. Develop the function make-1stQpoints, which consumes a list of x-positions and a list of y-positions and produces a list of posns that fall in the first quadrant. Assume the lists are of equal length.

Problem A3:

XML is a modern language (really, a family of languages) for encoding data. It uses "named parentheses" to group structured data, and strings for everything else. [Well, it contains a few more things than that, but this is good enough for now.] Here is an example:


     <div>
       <p><b>Problem A1</b>:</p>
  
       <blockquote>
         <p>

           XML is a modern language (really, a
           <i>family</i> of languages) for encoding
           data. It uses "<i>named parentheses</i>" to
           group structured data and strings for everything
           else. [Well, it contains a few more things than that, but
           this is good enough for now.] Here is an example:

         </p> 

         <p> Yes, this example is weird, because it is 
           self-referential but, hey, you should be used to
           this by now.  
         </p>
       </blockquote>
     </div>
Yes, this example is weird, because it is self-referential but, hey, you should be used to this by now.

You should have noticed that the example is not a complete representation of Problem A1. It misses this paragraph and it misses something in the middle. Nevertheless, it is a good example of the kind of XML you will encounter in the real world.

There are many ways to represent XML data in DrRacket. Here is one of them:

     ;; An Xexpr is one of: 
     ;;  - (cons Symbol LoXexpr)
     ;;  - String 

     ;; An LoXexpr is one of: 
     ;;  - empty 
     ;;  - (cons Xexpr LoXexpr)
  
Interpretation: An Xexpr represents a bracketed pair of "named parentheses" and whatever is in between, e.g.,
     <p>
        hello <em>world </em>
     </p>
  
becomes:
     (cons 'p
           (cons "hello "
                 (cons (cons 'em (cons "world " empty))
                       empty)))
  
Or equivalently...
   (list 'p "hello " (list 'em "world "))
  
See DrRacket documentation or the HtDP introduction to the list operator.

(Yes, S-expressions are more compact than XML and 50 years older than XML, but people don't like parentheses. They're so ugly and unreadable...)

In this context solve the following problems:

  1. Translate the XML example from above into an Xexpr.
  2. Design a function that counts the number of symbols in an Xexpr.
  3. Design a function that counts the number of characters in an Xexpr.


last updated on Sun Dec 2 14:52:34 EST 2012generated with Racket