Exam 1: Scheme and Color Basics

Topics: Algorithmic thinking, ambiguity, parts of an algorithm

PearCo has been developing a new tool to help you better understand your library of mp3s. (Yes, they assume that people still gather libraries of mp3s rather than using streaming media.) One task that they have been considering is how to provide information on how many different mp3s someone has within a certain genre. (Yes, they know that people seem to gather multiple mp3s of the same song, although they are not sure how or why.)

For each song, they know the title, artist, album, genre, and time. For example,

Venus in Furs,The Velvet Underground,The Velvet Underground and Nico,Proto-Punk,5:15
Gloria,Them,Their Greatest Hits,Rock,2:39
Roadrunner,The Modern Lovers,The Original Modern Lovers,Proto-Punk,4:05
Venus in Furs,The Velvet Underground,The Velvet Underground and Nico,Proto-Punk,5:15
I Can See For Miles,The Who,Meaty Beaty Big and Bouncy,Rock,4:06

As they work on designing an algorithm for the problem, they've decided to focus on a simpler problem: They ask their team to design an algorithm that counts the total number of unique proto-punk songs in the library.

Jordan suggests the following algorithm.

Taylor suggests the following algorithm.

As you may have noted, both algorithms are somewhat ambiguous in that they do not indicate what it means that two songs are “the same”.

a. Identify other places in which the algorithms are somewhat ambiguous and suggest how to make them less ambiguous while achieving the apparent goals of the designer.

b. Identify instances of the use of (i) parameters, (ii) variables, (iii) repetition, (iv) conditionals, (v) sequencing, and (vi) subroutines in these algorithms. (You only need to identify one example of each.)

c. Assume that “the same” means “have the same song title”. Is Jordan's algorithm correct? If not, provide a case in which it will not work. If so, provide a short argument that it does work.

d. Assume that “the same” means “have the same song title”. Is Taylor's algorithm correct? If not, provide a case in which it will not work. If so, provide a short argument that it does work.

e. Assume that “the same” means “the artist, title, album, genre, and time are the same”. Is Jordan's algorithm correct? If not, provide a case in which it will not work. If so, provide a short argument that it does work.

f. Assume that “the same” means “the artist, title, album, genre, and time are the same”. Is Taylor's algorithm correct? If not, provide a case in which it will not work. If so, provide a short argument that it does work.

g. Write an unambiguous algorithm that you are confident will work under both interpretations of “the same”.

Citation: This problem is based on a sample problem for the new AP Computer Science Principles examination.

Topics: Arithmetic operators, code reading, documentation

Sometimes students (and professors) come up with difficult-to-read solutions to arithmetic problems, like the one below.

(define z (lambda 
(w x y) (- 
        (+ w y (* 2 x)) 
    (min w x y) x (max w x y))))

a. Add carriage returns and indent the code so that it is formatted clearly.

b. Rename the procedure and the parameters so that they will make sense to the reader.

c. Write 6P-style documentation for the code.

d. Explain how the code achieves its purpose.

Topics: Algorithmic thinking, arithmetic operators, lambda

Write, but do not document, a procedure (index-of-smallest val1 val2 val3), that takes three positive integers as parameters and returns:

> (index-of-smallest 100 50 0)
3
> (index-of-smallest 100 0 50)
2
> (index-of-smallest 50 100 0)
3
> (index-of-smallest 0 100 50)
1
> (index-of-smallest 0 50 100)
1
> (index-of-smallest 50 0 100)
2

You may not use conditionals (e.g., if) in writing index-of-smallest.

Topics: IRGB colors, color transformations, writing procedures with lambda, writing procedures with section and compose.

Consider the following procedure documentation.

;;; Procedure:
;;;   irgb-bound
;;; Parameters:
;;;   color, an integer-encoded RGB color
;;; Purpose:
;;;   Bound the components of color.
;;; Produces:
;;;   bounded, an integer-encoded RGB color
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   If (irgb-red color) < 64, (irgb-red bounded) = 64.
;;;   If (irgb-red color) > 192, (irgb-red bounded) = 192.
;;;   If 64 <= (irgb-red color) <= 192, (irgb-red bounded) = (irgb-red color).
;;;   If (irgb-green color) < 64, (irgb-green bounded) = 64.
;;;   If (irgb-green color) > 192, (irgb-green bounded) = 192.
;;;   If 64 <= (irgb-green color) <= 192, (irgb-green bounded) = (irgb-green color).
;;;   If (irgb-blue color) < 64, (irgb-blue bounded) = 64.
;;;   If (irgb-blue color) > 192, (irgb-blue bounded) = 192.
;;;   If 64 <= (irgb-blue color) <= 192, (irgb-blue bounded) = (irgb-blue color).

a. Implement irgb-bound using lambda but without using section or compose. You may write helper procedures provided you follow the same guidelines for the helper procedures. Call this version irgb-bound-a.

b. Implement irgb-bound without using lambda, max, or min. You will likely need to use section, compose, or both. You may write helper procedures provided you follow the same guidelines for the helper procedures. Call this version irgb-bound-b.

Topics: RGB Colors, transformations, lambda

Recall that the HSV representation of color (hue, saturation, and value) is an alternative to the RGB representation we typically use in this class. One advantage of HSV is that it more naturally captures the notion of complementary colors. The hue of a color is a number between zero (inclusive) and 360 (exclusive) that is analogous to an angle on a color wheel. Given a color, you can choose other colors with the same saturation and value but different hues evenly spaced around the color wheel to produce a color palette.

Write and document a procedure (color-palette color) that takes an integer-encoded RGB parameter color. This procedure then produces a palette of three colors using the color-swatch function. The palette should include the color provided as a parameter, along with two other colors spaced evenly around the color wheel from the parameter.

(image-show (color-palette (color-name->irgb "steelblue")))
(image-show (color-palette (color-name->irgb "tan")))
(image-show (color-palette (color-name->irgb "peachpuff")))

Topics: Integer-encoded RGB colors, color transformations, code reading, documentation

Consider the following interesting color transformation.

(define t
(lambda (color
  string
  number)
        (irgb-add (irgb (* color (irgb-red string))
                  (* color (irgb-green string))
                  (* color (irgb-blue string)))
                  (irgb (* (- 1 color 
                        )(irgb-red number))
                  (* (- 1 
                  color) (irgb-green number))
                  (* (- 1
                  color) (irgb-blue number))))))

a. Add carriage returns and indent the code so that it is formatted clearly.

b. Rename the procedure and the parameters so that they will make sense to the reader.

c. Write 6P-style documentation for the code.

d. Explain how the code achieves its purpose.