5 Pages
Unlock Document

Computer Science
CS 135
Sebastian Siebel- Achenbach

CS 135 Winter 2013 Ashkan, Champaign Assignment: 5 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 specific 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 find 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, defined as (define-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 defined for you and used to create two lists. The first, 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 find it useful for experimenting. To access these definitions in DrRacket, you need to do the fol- lowing: 1. Download the file 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 file namelist.rkt from the course website. Save it in the same directory as names.txt. 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 first two names in the list. (require ”namelist.rkt”) (first name-list) (first (rest name-list)) You will not submit namelist.rkt nor names.txt. We already have copies; you won’t be changing yours. All of the required functions will be submitted in a single file, 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 definition and template for a Namelist, a list of Nameinfo structures. 2. Write the function find-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 first-n. It consumes a list and a natural number, n, and produces the first n items from the list. If there are fewer than n items on the list evaluate (error ”Insufficient 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 find 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 time! 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 by #nnewline. (c) Two functions you may find useful, especially in your testing, are list!string and string!list. The first 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 specified by the assign- ment header), your solution will look like (define (bar-graph lon) (list!string (helper lon))). For your helper function, consider ”one step closer to the base case” of the l
More Less

Related notes for CS 135

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.