Due: Friday, July 21 at 6pm (submit through Canvas)

In this assignment, there is a common task for all (designing data), and a choice of one of two sets of programming problems: one on writing programs over to-do items and one on writing programs over flights. The flights assignment is more challenging. Pick whichever set is more appropriate for your progress with the material. You don’t get extra points for trying the challenge problems: my goal is simply to provide a more challenging option for those who are ready for it (and you won’t adversely affect your grade by trying those problems if you are ready for them). Feel free to ask me if you are trying to decide which problems to attempt.

1 Designing Data (Everyone)

The answers to this part go in a file named data.arr.

For the two problems in this section, you are not writing any functions. You are simply defining data structures (tables, lists, data blocks, etc) to capture the requested information. For each, provide:

• A text (in comments) summary of your data structuring choices including specific types (i.e., a table with a column name (a string), year (a number), etc).

• A text justification of your choices, particularly around spots where you could have chosen something different.

• A single example of your data, written in code. For the library problem, for example, create library data with 2-3 books and 2-3 library members. This example could be used in a where or check block if you were asked to write a function for the library. This step illustrates your choices and makes sure we can interpret your types and decisions with a concrete example.

  In order to do this step, you will need to include any data blocks needed for your example. Pyret should be able to run/load your example as code.

There is no single right answer to these (though some answers are better than others). The goal here is to let us assess how you are thinking about data at this point in the course). Both problems are about data that you have some experience with—think about the kinds of operations or functions that one might want to do with that data and let that influence your data choices.

• A new to-do application lets you create and manage your to-do items. Each item has a description, a due-date, and optional tags (i.e., work, home, shopping, etc).

• A library maintains information on books, including which books they own, who has them checked out, and who is waiting for books that are checked out. Each book has a title, author, and a call number (location within the library). Library members have names and id numbers.

  How you associate books with members is entirely up to you: for example, you could indicate which members have which books, which books are with which members, a combination, etc. What matters is that you come up with a design and explain your choices.

2 Option 1 (Standard): Programming With To-Do Items

The answers to this part go in a file named todo.arr.

Do these problems using the data structure that you designed for the previous part, if possible. If you find the data structure you wrote for part 1 doesn’t work for these problems, make a new data structure for part 2 and explain why what you had in part 1 didn’t work out as you had hoped.

The problems use the phrase "collection of to-do items" so as not to bias your choice of data structure.

• Write a function add-item that takes a description, due-date, optional tags, and a current collection of to-do items and produces a new collection of to-do items that includes the new item.

  Your function should check whether the given due-date is valid (ie, corresponds to a valid month and day within that month). If the date is not valid, raise an error instead of adding the item. Ignore leap years when considering valid dates.

• Write a function finish-item that takes a to-do item description and a collection of to-do items and removes the item with the given description from the collection.

• Write a function overdue that takes a collection of to-do items and a date and returns a collection of those items that were due before the given date. Use the same type for the date parameter as you do to store the due date in your items.

3 Option 2 (Challenging): Programming With Flights

The answers to this part go in a file named flights.arr.

An airline maintains information on flights as a list of flight-values defined with the following data blocks:

Using these data blocks, write the following two functions:

• A function is-valid-route which takes a starting city (string), ending city (string) a list of city names (strings) representing a possible route from the starting to the ending city, and a list of FlightInfo data (the airline schedule). The function produces a boolean indicating whether the given list of cities is a valid route based on the flight schedule.

  For example, for a call

  is-valid-route("Providence", "Orlando",

  [list: "Providence", "Chicago", "Orlando"],

  all-flights)

  There would need to be a flight (in all-flights) from Providence to Chicago and a flight from Chicago to Orlando, such that the first flight arrives in Chicago before the second flight leaves. Don’t worry about layover/connection times. For this assignment, it would be fine if the second flight left a minute after the first flight landed.

  There is no limit on the number of cities in a route, as long as the times work out.

• A function find-route which takes a starting city (string), ending city (string), and a list of FlightInfo data and produces a list of FlightInfo representing a valid route from the starting to the ending cities. While the previous problem captured a route just with names, this one captures the route with the specific flights (assuming one might make a reservation based on this information).

  The route you produce does NOT have to be the shortest route. It simply has to be a valid route. If there is no valid route between the two cities, return the empty list.

The flights problems are a non-trivial jump over the problems we have tried so far. If you try those:

• Follow the templates.

• Think about tasks and create helper functions. There are multiple subtasks involved in finding routes. You will almost certainly need multiple functions to get this code clean.

• Don’t be shy about asking for help. These problems are intended to stretch you a bit, because some of you are ready for that stretch. Sketch out a design of the functions you need, and feel free to email me asking whether you are on the right track as needed.

For the data-design problems, we are looking for whether you make reasonable choices and give appropriate justifications for them. These exercises count towards the "data structures" theme of the course.

For the programming problems (either set), we will look at your examples/tests, code structure, and code presentation. We expect you to follow the list template when appropriate (unless you are using a built-in list iterator like map or filter, which you are welcome to use if you wish). We expect you to create helper functions to create a clean and maintainable solution.

Your examples/tests will be graded separately from your code, with those points counting towards the "testing" theme of the course. We’re looking to see a set of tests that reflect "interesting" cases of the data (that would catch possible typos, boundaries, etc).

Remember to include the collaboration statement.

If you want to check whether your file has the same names as our grading scripts will look for, insert the appropriate check block at the bottom of your file (you do NOT need to satisfy the check block for the problem set that you did not do).

Create a directory named data-hwk. Inside the directory, put a single Pyret file named data.arr and either todo.arr or flights.arr, depending on which set of problems you did. Submit a zip of the data-hwk directory.

Make sure you follow these directory and file names exactly, or we won’t be able to grade your work.