CSC 160
Homework 5

Assigned June 16, due June 22

For all the programming assignments, be sure to follow the design recipe. Write your function contract, examples, and function definition in the Definitions Window, save it to a file, and send me this file. Also test your program: since you've already included examples in the Definitions window, you should be able to hit the Execute button and see all the results (along with what you said they "should be"). Save the resulting Interactions window to a text file and send me this file too. Be sure to choose meaningful names for functions and parameters, and watch for opportunities to re-use functions you, I, or the textbook have already written.

Also turn in a log of how many errors of different kinds you encountered in the assignment, with brief comments describing each one ("mismatched parentheses" is self-explanatory, but more complex errors might need more description). You may do this using the PSP forms, or simply by keeping track in a text file or on paper and turning it in.

I recommend using list notation rather than nested-cons notation for your examples.

• Do exercise 12.4.2.

  Hint: You must read all of section 12.4 leading up to this problem before tackling it; otherwise you'll misunderstand the question, solve the wrong problem, and get no credit.
  Another hint: You'll need at least two auxiliary functions.

---

For the remaining problems, you'll need to set DrScheme to the "Intermediate Student with Lambda" language level.

---

• Review the sort function discussed in class on June 14.

  Develop a similar function sort-posns-by-x which takes a non-empty list of posns and returns a list of the same posns in increasing order by x-coordinate.

• Develop a generalized function general-sort which takes a non-empty list of X's (where X is any data type) and a function (let's call it precedes?) with the contract "X X -> boolean", and returns a list of the same X's, shuffled so that the first element "precedes" the second, which "precedes" the third, etc. For example,

    (general-sort (list 5 2 4 6 3) <) "should be" (list 2 3 4 5 6) 
    (general-sort (list 5 2 4 6 3) >) "should be" (list 6 5 4 3 2)
    

• Re-write sort (which works on numbers, remember?) using general-sort. Your new definition should fit on one or two reasonably short lines.

  Re-write sort-posns-by-x using general-sort. Your new definition should fit on at most four reasonably short lines.
  Hint: One way to do this is to define a function left-of? locally inside sort-posns-by-x. A shorter way is using lambda.

• Write a function sort-candidates which takes a list of candidates and sorts them so the one with the most votes comes first, and the one with the fewest votes last. Your new definition should fit on at most four reasonably short lines.

• Write a function ranked-election which takes a list of strings (representing the votes cast by individual voters) and returns an ordered list of all the candidates, from most votes to fewest votes. Your new definition should fit on two or three reasonably short lines.

• Re-write give-10%-raises (from homework 4) using map. Your new definition should fit on two or three reasonably short lines.

• Develop a function count-if which takes two parameters: a function with contract "X -> boolean" and a list of X's (where X is any data type). The count-if function should return a number telling how many of the X's in the list pass the test. For example,

  (count-if positive? (list 3 0 -2 5 -1 4)) "should be" 3

  Re-write count-over-100k (from homework 4) using count-if. Your new definition should fit on three or four reasonably short lines.

• Develop a function do-twice that takes a function with contract "X -> X", and returns a function with contract "X -> X" which applies the given function twice. For example,

  (define add2 (do-twice add1))
  (add2 3) "should be" 5
  

  What is (do-twice sqr)?

  Generalize this to a function iterate that takes a natural number and a function with contract "X -> X", and returns a function with contract "X -> X" which applies the given function the specified number of times. For example, (iterate 2 f) should be equivalent to (do-twice f), and

  (define add5 (iterate 5 add1))
  (add5 3) "should be" 8
  

  What is (iterate 3 sqr)? (iterate 5 sqr)? (iterate 3 (iterate 3 sqr))? (iterate 3 do-twice)?

• Essay assignment (2-5 pages)

  Discuss the usefulness of this course for your future career as a high school math teacher. What concepts, techniques, tools, or problems (if any) from this course would be helpful in a high school math course, and how would you use them? What aspects (if any) of the course would not be applicable to a high school math course, and why not? List some concepts and techniques that caused you trouble when you encountered them, and suggest ways you could help a high school student with those difficulties.

Grading standards

Essay:       /200

Error log:       /45

General skills:

Total:         /700