CS 135 Winter 2013
Due: Tuesday, February 26, 2013 at 9:00pm
Language level: Beginning Student
Allowed recursion: Pure structural
Files to submit: a05.rkt, a05bonus.rkt
Warmup exercises: HtDP 10.1.4, 10.1.5, 11.2.1, 11.2.2, 11.4.3, 11.5.1, 11.5.2, 11.5.3
Practise exercises: HtDP 10.1.6, 10.1.8, 10.2.4, 10.2.6, 10.2.9, 11.4.5, 11.4.7
The US Social Security administration publishes the 1,000 most popular male baby names and
the 1,000 most popular female baby names for each decade since 1890. See http://www.
socialsecurity.gov/OACT/babynames/ for more information.
You may search for speciﬁc names and see graphs of that name’s popularity through time at http:
//www.student.cs.uwaterloo.ca/ cs135/assn˜/a05/nameSurfer/. Use it to
explore! For example, the name “Rock” has a spike right about the time Rock Hudson was a
popular movie star. “Abdullah” appears very late in the American data. “Kelsey” shows a meteoric
rise in popularity in the 1980’s data. “Adolf” (as in Hitler) was already a dead name by 1920.
One might ﬁnd it surprising that “Adolph”, practically the same name, did not take a plunge in
popularity right after World War II.
The goal of this assignment is to produce the “guts” of a similar application.
Data on each name is recorded using the Nameinfo data type, deﬁned as (deﬁne-struct nameinfo
(name decade rank gender)) where
▯ name is a String
▯ decade is a Natural number that is one of 1890, 1900, 1910, ... 2000. It indicates the decade
for which the information applies
▯ rank is an Int in [1, 1000] indicating the popularity of name in the given decade where 1 is
the most popular name for the decade and 1,000 is the least popular name
▯ gender is one of f’Male, ’Femaleg and indicates the gender of the babies given the name.
The nameinfo structure has already been deﬁned for you and used to create two lists. The ﬁrst,
name-list, contains all 24,000 data points from the Social Security Administration data. The sec-
ond, short-name-list, contains only the names beginning with ”A” (2,057 data points). You may
ﬁnd it useful for experimenting. To access these deﬁnitions in DrRacket, you need to do the fol-
1. Download the ﬁle names.txt from the course website. Save it in the same directory where
your a05 Scheme programs will be saved.
CS 135 — Winter 2013 Assignment 5 1 2. Download the ﬁle namelist.rkt from the course website. Save it in the same directory
3. In your Scheme program, include the line (require ”namelist.rkt”) at the beginning of your
program. For example, save the following in a05-demo.rkt. It should display the ﬁrst
two names in the list.
(ﬁrst (rest name-list))
You will not submit namelist.rkt nor names.txt. We already have copies; you won’t be
All of the required functions will be submitted in a single ﬁle, a05.rkt, because they build on
each other for the last several problems. A syntax error in one will make all of them unmarkable.
For this reason you must use the public test to ensure your code can be tested. Do not change
your submitted code without reviewing the public test to verify that it (still) works correctly.
Here are the assignment questions you need to submit.
1. Write a full data deﬁnition and template for a Namelist, a list of Nameinfo structures.
2. Write the function ﬁnd-rank. It consumes a Namelist, a name, one of f’Male, ’Femaleg,
and a decade. It produces the name’s popularity ranking for the given decade and gender.
Produce false if the ranking can’t be found.
3. Write the function collect-name. It consumes a Namelist, a name, and a gender. It produces
a Namelist composed of all the Nameinfos in the given list that match the given name and
gender. Order does not made.
4. Write the function ﬁrst-n. It consumes a list and a natural number, n, and produces the ﬁrst
n items from the list. If there are fewer than n items on the list evaluate (error ”Insufﬁcient
items”). You should be able to do this without counting the number of items ahead of time.
5. Review the sort function on slide 06-29. It uses the insert function on slide 06-31. Adapt
these two functions to sort a Namelist in increasing order by name (you will ﬁnd the predicate
String useful). If the names are the same, place females before males. If the name and
gender are the same, sort in increasing order by decade. Call the functions name-sort and
name-insert. Warning: if you try sorting the entire name-list you will be waiting for a long
6. Write the function bar-graph. It consumes a list of natural numbers and returns a string such
that each number n in the list results in a sequence of n “*” characters. Each such ‘bar’
should be separated from the next by a newline character (“nn”). For example, (bar-graph
(cons 5 (cons 10 (cons 3 empty)))) should produce ”*****nn**********nn***nn”.
CS 135 — Winter 2013 Assignment 5 2 Notes for bar-graph:
(a) You may not use string functions, in particular make-string or string-append. You may
not use append, either (we haven’t discussed it in class).
(b) An asterisk is represented in scheme by #n▯ and the newline character is represented
(c) Two functions you may ﬁnd useful, especially in your testing, are list!string and
string!list. The ﬁrst function converts a list of characters into a string; the second
converts a string into a list of characters. For example, both of the following tests pass:
(check-expect (list!string (cons #n▯ (cons #n▯ (cons #n▯ empty)))) ”▯▯▯”)
(check-expect (cons #n▯ (cons #n▯ (cons #n▯ empty))) (string!list ”▯▯▯”))
(d) Assuming you restrict yourself to pure structural recursion (as speciﬁed by the assign-
ment header), your solution will look like (deﬁne (bar-graph lon) (list!string (helper
lon))). For your helper function, consider ”one step closer to the base case” of the l