CSC 160 Homework 8

Assigned Nov. 15, slightly modified Nov. 18, due Dec. 1

What to turn in and how

You need to turn in your source code (the contents of a definitions window), your test runs (the contents of an interactions window after you've executed the definitions), and your error log. If you don't turn in all three of those things, you'll lose points.

You may keep the error log in a text file and e-mail it in, or you may instead use the PSP on-line forms.

For the source code and test runs, you may save each one to a file and e-mail it to me, or you may use the "handin" button in DrScheme. If you don't have a "handin" button (it'll look like a hand holding a pen), see the directions for installing it.

For all the programming assignments, be sure to follow the design recipe. For functions whose only effect is to draw a picture on a canvas, test them yourself one by one by typing function-calls into the interactions window, but don't bother turning in the interactions file; I'll just test them myself in the same way.

This assignment is to be done in pairs, just like previous homeworks, but with a different partner.

The assignment

• Develop a function count-positives that takes in a list of numbers, and returns how many of the numbers are larger than 0.

• Develop a function convert-reversed that takes in a list of numbers representing the digits of a decimal number (ones place first, then tens place, and so on) and returns the number. This is similar to the convert-3-digits-reversed function from homework 2, but instead of taking in three digits, it now takes one argument which is an arbitrary-length list of digits. For example,

  (convert-reversed (cons 3 (cons 0 (cons 5 (cons 4 (cons 1 empty)))))) "should be" 14503
  

  Note: The reason the digits are in reverse order is that it's actually easier to write the function that way. For extra credit, write a convert function that does the same thing, with the digits given in the usual order.

• Develop a function cube-each that takes a list of numbers and returns a list of their cubes, in the same order. For example,

  (cube-each (cons 3 (cons 5 (cons 2 empty)))) "should be" (cons 27 (cons 125 (cons 8 empty)))
  

• Develop a function plot-points that takes in a list of posns and draws a little dot on the screen at each location. The function should return true, like most of the graphics functions we've seen.

• Develop a function keep-in-circle that takes in a posn (the "center"), a number (the "radius"), and a list of posns, and returns a list of those posns in the list that are within the specified radius of the center. Hint: re-use previously-defined functions!

• Develop a function rename-dolls which takes a list of strings and replaces every "doll" with "action figure". For example,

  (rename-dolls (cons "bat" (cons "doll" (cons "ball" (cons "doll" empty)))))
  "should be"
  (cons "bat" (cons "action figure" (cons "ball" (cons "action figure" empty))))
  

  Then develop a more general function substitute which takes two strings (old and new) and a list of strings, and replaces the old string with the new one everywhere in the list. For example,

  (substitute "cat" "dog" (cons "cat" (cons "snake" (cons "dog" (cons "cat" (cons "parrot" empty))))))
  "should be"
  (cons "dog" (cons "snake" (cons "dog" (cons "cat" (cons "parrot" empty)))))
  

  Then write a simpler version of rename-dolls by using substitute.

• Type the following struct definition into your definitions window:

  (define-struct employee [name salary id])
  

  (Recall that I used this definition to write total-salary in class. Review this function and its examples before going on.) We'll be working with lists of employees; call this the "employee-list" data type.

  Write several examples of employee lists. (There will be no "should be"'s, because you're not doing anything to the lists.)
  Then write templates function-for-employee-list and function-returning-employee-list and comment them out.

  Then, with the aid of these templates, develop the following functions:

  • any-over-100K?, which takes a list of employees and tells whether any of them have a salary over $100,000.
  • names-over-100K, which takes a list of employees and returns a list of the names of those with salaries over $100,000.
  • fire-high-salaries, which takes a number and a list of employees and returns a new list of employees, leaving out the ones who earned over the specified amount.
  • give-raises, which takes a number (e.g. 0.10 for a 10% raise) and a list of employees and returns a new list of employees, in which every employee gets that much of a raise. For example,

    (give-raises 0.10 (cons (make-employee "Joe" 40000 3) (cons (make-employee "Jane" 45000 5) empty))) 
    "should be"
    (cons (make-employee "Joe" 44000 3) (cons (make-employee "Jane" 49500 5) empty))
    

    Hint: I recommend writing an auxiliary function give-raise, which takes a number and one employee, and returns a new employee just like the old one but earning that percentage more.

• Recall the candidate structure you defined in homework 6. We'll be working with lists of candidates; call this the "candidate-list" data type.

  Write several examples of candidate lists. (There will be no "should be"'s, because you're not doing anything to the lists.)
  Then write templates function-for-candidate-list and function-returning-candidate-list and comment them out.

  Then, with the aid of these templates, develop the following functions:

  • add-vote-for, which takes in a string (the name of a candidate) and a list of candidate structures, and returns a new list of candidate structures with one more vote recorded for that candidate. Note: the named candidate may not already be in the list at all; handle this case by creating a candidate structure with that name and one vote. Hint: You may want to write an auxiliary function that works on a single candidate.

  • count-all-votes, which takes in a list of strings representing votes (e.g.

    (cons "anne" (cons "bob" (cons "anne" (cons "charlie" (cons "charlie" (cons "anne" empty))))))
    

    and returns a list of candidate structures, each with the correct number of votes. For example, the above list should produce

    (cons (make-candidate "anne" 3) (cons (make-candidate "bob" 1) (cons (make-candidate "charlie" 2) empty)))
    

    Note: I don't care about the order of the candidates, only that each one has the right number of votes, so if your function returned

    (cons (make-candidate "bob" 1) (cons (make-candidate "charlie" 2) (cons (make-candidate "anne" 3) empty))),

    that would be OK.

  • Develop a function winner that takes in a list of candidate structures and returns the name of the winner. You may assume that the list is non-empty.

    Hint: You'll probably need an auxiliary function. I see two approaches: one uses an auxiliary function that looks up a given name in a list of candidates, and the other uses an auxiliary function just like winner except that it returns a whole candidate rather than just the name. You may use either of these approaches, or any other approach as long as it works.

    Extra credit: return the string "tie" if there is no single winner.

  • Develop a function election that takes in a list of strings (representing the votes cast by individual voters) and returns a string, the winner of the election. You may assume that there is at least one vote, and that there are no ties for first place. (If you did the extra-credit version of "winner", you can drop the latter assumption.)

Grading standards

Error log:       /30

General skills:

Total:         /580