8 Placement 3🔗

8.1 Language🔗

For the following assignment, you must use Racket’s Beginning Student with List Abbreviations language. Go to the Language menu, select Choose Language, and pick the language from the Teaching Languages section.

8.2 A Big Change🔗

From this assignment onward, for the rest of the placement and the course, there’s an important change. Henceforth, you will be graded on the quality and correctness of your code and on the quality and correctness of your tests. Both are important. If you didn’t pay enough attention to writing tests earlier, you should certainly start doing so now.

Part of the process of assessing tests will use an auto-grader. The way we will do this is explained below: How We Test Tests. This means it is especially important to write your tests using check-expect (not as comments) and to follow the instructions given (otherwise the auto-grader will not work, and you may lose credit).

8.3 Library🔗

In Placement 2 you defined the function is-in?. This is built into Racket with the name member. You may use member from now on. Note that member uses equal? to perform its comparisons.

We will also be using characters, which are the atomic elements of strings. Characters are written with a #\ prefix: e.g., #\c, #\s. You can turn strings into lists of characters and vice versa using string->list and list->string.

From now on, for the rest of the placement and the course: in every assignment, you can use any functions defined in that and any previous assignment, as well as libraries permitted in that and previous assignments, unless indicated otherwise—but no other. There may well be built-in functions that do exactly what the assignment asks for, but unless the assignment is expressly about your ability to search, we want you to demonstrate to us that you can write it with the resources we’ve asked you to use.

Some functions in this assignment would benefit from creating a helper function to handle a complex sub-task.

8.4 Reading🔗

In HtDP 2/e, read Part 1, specifically chapter 5.1-5.6, and Part 2, specifically chapter 10.1. You can read past it if you feel the need as you’re doing the assignment.

If you find something unfamiliar, recall that we skipped reading Part 1 so you may need to peek in there to look up something.

8.5 Programming Tasks🔗

Define the following functions.

Note: You must copy the structure definitions given below exactly, to the letter.

• valid-words :: List-of-strings List-of-chars -> List-of-strings

  Consumes a list of words (represented as strings) and a list of letters (represented as characters). Produces the list of the same words, in the same order, that contain only those letters. (Imagine a game where you have to assemble words with just the letters you have.)

  For this assignment, ignore multiplicity: i.e., a word may contain more instances of a letter than the number of times the letter was present in the second parameter. Also, letters should be case-sensitive (e.g., #\A does not appear in "cat").

• external-senders :: List-of-email-server -> List-of-external-report

  An email address is composed of two parts: a username and a domain. The username helps to identify the account that sent the email. The domain helps to identify the sender’s (email) organization. For example, in the email address jane.doe@company.abc, jane.doe is the username and company.abc is the domain.

  In many organizations, there are different security restrictions for emails which originate “in-house” (from the company domain) versus externally. Organizations want to keep track of who is sending mail to their email server, and tend to monitor external senders more closely as vectors for potential attack. Often this responsibility is outsourced to large email hosting providers, who have to do this for many domains at once. At any moment, the email hosting provider needs to know which emails in each server are coming from external senders to flag them for potential further protective action.

  Thus, an email hosting service has a list of email-servers. Each email-server is associated with one domain (a company it’s servicing). There are several emails in each email-server, waiting to be processed. We represent these with the following contracts:

  ;; sender-username :: String

  ;; sender-domain :: String

  (define-struct email [sender-username sender-domain])

  ;; domain :: String

  ;; emails :: List-of-email

  (define-struct email-server [domain emails])

  ;; excluded-domain :: String

  ;; emails :: List-of-email

  (define-struct external-report [excluded-domain emails])

  (We know that these data structures should have several other fields, such as the body of the email message, but we explicitly ignore them here to reduce the testing burden.)

  Design a function external-senders that consumes a list of email-servers and produces a list of external-reports. Each external-report corresponds to an email-server in the input. Its emails field contains only those emails that are not from the domain being serviced by that sender. The output should contain a report for each server in the input, even if that server has no external emails. All emails in each report should be in the same order as in the corresponding server in the input.

• unique :: List-of-any -> List-of-any

  Given a list of values, produces a list of the same values in the same order excluding duplicates. If a value is present more than once, its first instance stays and the remainder are discarded. Use equal? for comparison.

• after-loan :: List-of-canada-penguin -> List-of-canada-penguin

  An American zoo requests a short-term loan of healthy Gentoo and King penguins from a Canadian zoo. A healthy Gentoo penguin weighs between 9.9lb and 19lb (inclusive), and a healthy King penguin weighs between 21lb and 40lb (inclusive).

  The Canadian zoo stores all penguin data in the following datatype:

  ;; name :: String

  ;; species :: String

  ;; weight-in-kg :: Number

  (define-struct canada-penguin [name species weight-in-kg])

  You can assume that species is only ever "Gentoo" or "King" for these particular penguins.

  The Canadians compute which penguins are a healthy weight and send only those penguins to the American zoo. When the Americans return the penguins a month later, the Canadians find that all of the loaned penguins have gained 2lbs due to a rich American diet.

  Design the function after-loan that consumes a list of Canadian penguins and produces a list of loaned penguins with their new weights (in kgs) after their stay at the American zoo. All penguins in the output list should be in the same order as they appear in the input list.

  Please use the conversion factor 2.2 to convert kg to lbs and the inverse of that to convert in the opposite direction. Please don’t use other numbers, because our test cases will depend on these values.

• fix-shelves :: List-of-Shelf -> List-of-Shelf

  Most bookstores sort the books on their shelves by the author’s last name. Unfortunately, some bookstore patrons do not preserve this order when browsing books, and simply place books back wherever they fit.

  Assume that bookstores keep all authors whose last name starts with the same letter on the same shelf, and those shelves are labeled with that letter. A record of which authors are on a given shelf would be represented as:

  ;; letter :: Char

  ;; authors :: List-of-String

  (define-struct shelf [letter authors])

  You can assume letter will be a lowercase English character. authors is a list of the authors’ last names. Assume that authors’ last names consist only of lowercase English letters. (We will have much more to say about names during the semester!)

  Design the function fix-shelves, which consumes a list of Shelf values and produces a list of those Shelf records where there is at least one author who doesn’t belong on that shelf. The output Shelf records should only contain the authors who don’t belong on that shelf. Shelf records and the authors within those records should be in the same order in the output as they appear in the input. Do not generate empty Shelf records; this generates needlessly long reports, which annoys the employees.

8.6 Math Tasks🔗

We are handing out these problems to get a better sense of the mathematical maturity of the student population. Unlike in the previous assignment (Placement 2), we do not expect you to necessarily be able to solve these problems. Please give them your best shot. If you don’t know how to do them, just say so.

Your admission into the class will not depend on your ability to successfuly do these problems: even if you say you don’t know how to do them, it will have no impact. Therefore, there is no value to getting help from others, cheating, etc. Indeed, it would be counterproductive if you did, because it would give us a false sense of the class’s abilities. So please don’t do that.

Please feel free to approximate your answers: e.g., round up to the nearest integer (number or %age). Do show your work!

1. An AI system is trained to detect photos of lions. The system does not err when the photo actually has a lion, but 5% of photos in which a lion does not appear is detected as having a lion. The algorithm is executed on a set of photos in which 1 out of every 1000 photos actually has a lion. If the AI says a photo has a lion, what is the probability that it actually does have a lion?

2. An AI system trained to detect a leaf disease in photos of tomato bushes. The system does not err when the photo shows a diseased bush, but 11 out of 100 healthy bushes is also detected as diseased. The disease affects 4 out of every 1000 bushes. If the AI says a photo of a bush is diseased, what is the probability that it really is diseased?

Remember: it’s okay to say you don’t know! It won’t hurt your placement. But do give them a try unless you really have no idea, in which case, it’s fine to say so!

Please remind yoursel of the other instructions about writing up math from Placement 2.

8.7 How We Test Tests🔗

It’s important for you to understand how we test your tests.

What’s the job of a test suite (i.e., set of tests)? It’s to find errors in a program. (Examples help you understand the problem before you start writing code, tests help you catch errors in the program as and after you write it.) In short, test suites are like sorting hats, putting programs in a “good” or “bad” bin.If you are a mathy person, you might call a test suite a classifier.

So here’s how we will test your test suites. We construct a collection of implementations for the problem. One is known to be correct (because we built it that way); we call this a wheat. The rest are known to be incorrect (because we intentionally introduced errors); we call each of these a chaff. Your test suite’s job is to separate the wheat from the chaff (if you haven’t seen that phrase before, read up). That is, we will run your test suite against the wheat and chaffs (which are all programs, just like the one you wrote) and see what happens:This table is not strictly correct. During the semester, we’ll see that a correct wheat may fail for a very interesting reason. But that won’t happen during summer placement.

The quality of your test suite is then a measure of whether you passed the wheat and how many chaffs you caught. Of course, we can make the latter arbitrarily hard. For instance, we could define a chaff that always works correctly except when the given list has, say, exactly 1729 elements. We won’t do things like that, both because it’s cruel and because real implementations are very rarely buggy in this way. Instead, our chaffs will correspond to typical mistakes that students make.

In short, we will be running your test suite against our implementations. Therefore, it is very important that when you turn in your test suite (see details below), it not be accompanied by your implementation: otherwise, when we try to load ours, DrRacket will complain.

8.8 Turnin🔗

For the math portion, there will be a separate turnin section on Gradescope. Gradescope accepts only images or PDF files. Call this file p3-math; the filename would have a suffix that reflects the file type.

From now on, for the rest of placement and most of the semester, you will turn in multiple code-related files.

One file, named p3-code.rkt, contains the functions named above (it can contain any other helper definitions you like as well). The functions must be named exactly as above and must take parameters exactly as above.

In addition, make a copy of just the test cases for each of the required functions and put them in distinct files, named as follows:

Failure to follow any of these instructions may result in zero credit.

You will upload your work using Gradescope.