Problem Set 1

Due Friday, January 22, 2016 at 1pm

Purpose The goal of this problem set is to demonstrate basic competence in the prerequisites of this course and the PhD program in general, namely, solid programming skills in any programming language.

The problem also sets up a problem domain with a domain-specific language (DSL). This time around you write an "interpreter" for a program in the language. Later you will learn how to check basic properties and how to model this DSL in the tools that the course provides.

Imagine writing this memo for a manager in a development lab.

Be concise. Use active voice and descriptive verbs. Avoid subjective adjectives; instead bring across your preference through the technical description. Keep in mind that the addressee may check up on the facts that you present to support your claim. (Also, see the advice on memo1 provided on the Writing page.)

To format the memo, use (1) an 11-point font, (2) 1.5in margins all around, (3) a header that specifies the paper title and the author(s) of the memo.

Deliverable Print your memo and put it in my mailbox in 202 WVH. I will mark it up for basic English problems. I will schedule times to meet with you on January 27th (3:45-5pm) to give you feedback. Then include a revised PDF version of the memo in the submission of problem set 3.

Problem 2 Your task is to design a program that performs a simplified flight search given data on airports and flights, along with a flight query. The program reads a flight-search configuration from the (Unix) standard input, and it writes its solution to the standard output. It produces a single flight plan from the origin to the destination, subject to some constraints (explained below).

A flight-search configuration specifies two pieces: data on airports, including all departing flights, and a flight query that includes an origin, a destination, and what airline to restrict the search to. An airport comes with an airport code (e.g., BOS), a name (e.g., Boston Logan), and a series of outgoing flights. Each flight specifies the two-character airline code (e.g., UA for United Airlines), the flight number, and the code for the airport to which the flight is headed.

The program produces a flight plan which is a list of flight segments that would get one from the specified origin to the destination using only flights on the specified airline. Each flight segment specifies the departure and arrival airport codes and the flight number (e.g., BOS ORD 139). The flight plan must not include any cycles. If airport PQR has multiple (direct) flights to airport XYZ run by the airline AL specified in the query, then the first of these should be chosen for the output flight plan. Furthermore, if airport PQR has (direct) flights on airline AL to different airports UVW, XYZ, etc., listed in that order, then a flight plan connecting through UVW should be given preference---but if one does not exist, then a flight plan connecting through XYZ, and so on.

In this grammar, the dots (...) denote a possibly empty sequence of XML elements. Hence, an FSConfig might not specify any airports, and an Airport might not include any flights.

This time, since there is no valid flight plan from the origin, ORD, to the destination, PDX, on the specified airline (UA), the program outputs: No flights found

Deliverable Email a tar.gz bundle to my CCS email address whose name combines the last names of the pair in alphabetical order. The tar bundle must contain a single directory—with the same name as the tar ball—with a README.txt file and an executable file 1.xyz (for your choice of extension).