ITEC 380 2017fall ibarland

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

challenge
challenge/extra-credit exercises

The following problems can be completed for extra-credit (in the homework category). Due: Wednesday 23:59 of the last week of classes. (You are encouraged to complete and submit work much earlier, to avoid the time-crunch). However, they will not be graded until the end of finals week. You are encouraged to come by office hours with questions, and/or ask on the D2L discussion board.

Challenge problems are not meant to replace missing assignments: the regular homeworks are crafted to cover the topics that are the primary goal of the course. Challenge problems, on the other hand, may take existing topics further than we have time for in class, or they might cover topics that were covered only peripherally in class. They typically require a level-of-understanding gained by completing the regular homeworks.

1. (5pts) Re-do the Java AncTree functions from lecture, but instead of using the types AncTree/Unknown/Child, to represent the data, use Optional<Child>/Optional<Child>.empty()/Optional<Child>(non-empty). Compare and contrast this solution to the original, provided Java code, and to the provided racket code for anc-trees.

higher-order-functions (number-oriented)

2. (5pts) From 2htdp, exercise 455: write slope (a.k.a. “derivative”). (You'll need to read the preceding paragraphs.)
3. (10pts) From 2htdp, exercises 460 and 461: write integrate-dc and then integrate-adaptive. (You'll need to read the preceding paragraphs.)
4. In lecture, we wrote call-twice. But we can take things further:
   1. (4pts) generalize call-twice to apply-k-times. (You'll follow the template for a natnum, of course.)
   2. (1pt) Then re-factor call-twice so that it just calls applyapply-k-twice.
   3. (0pts) Write add, which performs addition for natnums only by repeatedly applying add1.
   4. (0pts) Write mul, which performs multiplication by repeatedly applying add.

      Hint: To multiply m and n: make a function which takes any number and adds m to it; then, iterate that function n times. Apply that iterated-function to the number you want to start adding-m from.

   5. (0pts) Write pow, which performs raising-to-a-power by repeatedly applying mul.
   6. (5pts for this and the prevous three) Write stackedpow, which repeatedly by repeatedly applying pow.
   7. (10pts) super-challenge: generalize the above sequence by writing a function inceptionize which:
      • given add1 and 2 would return mul;
      • given add1 and 3 would return pow;
      • and so on. for any function α→α and any natnum.
   Of course, follow the design recipe for each function: In particular, be careful about the signatures. Three test cases will suffice for each of the above (0,1,many).

higher-order-functions (utility)

5. We already wrote my-filter. It had been mentioned that filter, map, and foldr are built-in. Let's write (variations of) the latter two:
   1. (5pts) Write map-and-preserve/flat, which is similar to map but it also keeps the original values: (map-and-preserve sqrt (list 16 9 25)) returns (list 16 4 9 3 25 5).
   2. (0pts, but see next) The above function feels a bit wrong: rather than return a list of even length (where the list-elements are implicitly paired), we should return a list of pairs — that is, a list-of-(lists-of-length-two). Write map-and-preserve which does this; it's code should still follow the template for lists.
   3. (5pts) Finally, refactor map-and-preserve so that it doesn't use the list-template, but instead calls the (built-in) map, along with an anonymous function.
      (Just comment-out your previous working version. You don't need to touch your test-cases of course, since we're just re-factoring.)
   You may do these in racket or in Java.

6. (5pts) Recall how the template for lists has two “...”s in it: one to fill in for the base-case, and one to fill in for the rule-of-how-to-combine-first-with-result-of-recursive-call. For example, to add a list we use 0 and +; for checking if a list contains 93 we use #false and (λ (frst in-rest?) (or (= frst 93) in-rest?)). (This is a function which takes in a number and a boolean, that's all.)

   If you think about it, the list-processing-template is repeated code; we should write a single general-purpose function, and then ust call that function, instead of repeating code. That's what the function foldr is— (foldr + 0 (list 9 16 25)) adds all the numbers (returning 50); (foldr (λ (f rr) (or (= f 99) rr)) #false (list 92 93 94)) searches the list for 93 (returning #true).

   Indeed, the code for foldr is the essence of the list-prodessing template:

   (define (foldr combine base lst) (cond [(empty? lst) base] [(cons? lst) (combine (first lst) (foldr combine base (rest lst)))]))

   Write map-n-foldr, which is like foldr, but it first applies another function to each element. For example: (map-n-foldr sqrt + 0 (list 9 16 25)) returns √9+√16+√25 = 3+4+5 = 12.
   Do not call map nor foldr in your solution (calling each of those is easy, but traverses the list twice, unnecessarily); your implementation should only traverse the list once.

non-structrual (“generative”) recursion

7. (10pts) From 2htdp, exercises 521–524: Missionaries and Cannibals. (You'll need to read the preceding paragraphs.)
   You don't need to include the requested drawing-function render-mc.
   For full challenge-credit, use map and filter appropriately.

n-ary trees

8. (10pts) From 2htdp, exercises 330-331 (or, 332-333): representing a file system. Note that there are two data-definitions (both straightforward union-types), so you'll need templates for both of those.
9. (20pts) Parse & process JSON: Write parse! and toString for JSON (similar to what those methods did for S0). Then, write:
   • count-numbers: how many NUMBERs occur, in the JSON tree?
   • contains-value?, which takes two JSON-values, and returns whether the second occurs inside the first.

     To compare items: In racket, use equal?, since that built-in works for strings, numbers, lists, any structs you define, and even vectors. In Java, you'll need to be sure to override equals in the boilerplate way we've seen (e.g. in S0's class BinOp).

   Here is the full grammar for JSON. For this exercise, we'll simpify things slightly:

   • for Strings, we won't allow spaces, nor punctuation beyond the initial/final quote-marks. This means our parser can just use a single call to pop! or next. Since the quote-marks are required, looking at the first (two) character(s) can distinguish between a string, or the special tokens 'true', etc..
   • numbers can be just as in S0 — so don't worry about JSON's restictions on no-leading-zeroes or the exponent notation.
   You may use scanner.rkt, Java's built-in java.util.Scanner, and/or class UtilIan.

   As usual, follow the entire design recipe (incl. data-definition (which will be very similar to the grammar), examples of data before you start writing any functions, function test-cases before you start writing any function-code, etc.).

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

©2017, Ian Barland, Radford University Last modified 2017.Dec.07 (Thu)

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