Problem Set 1

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.

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 take it to Ms. Biron. She will mark it up for basic English problems. Schedule a meeting with her before the third lecture to get her one-on-one feedback. Then include a PDF version of the memo in the submission of problem set 3.

Problem 2 Your task is to implement a small fragment for an automatic driver for a dungeons-and-dragon-style game. The program reads a game configuration from the (Unix) standard input, and it writes its solution to the standard output. It computes the a the longest possible path for the player through an arrangement of rooms, according to a simple rule.

A game configuration specifies two pieces: an arrangement of rooms and a player’s name and location in the arrangement. A room comes with a name, a description, and a series of exits. Each exit specifies a cardinal direction (north, east, south, west) and the name of the room to which this direction leads.

The program walks the player through this arrangement of rooms by always taking the first possible exit from the current room. Its result is the list of names of the rooms the player visits before getting back to an already visited room.

In this grammar, the dots (...) denote a possibly empty sequence of XML elements. Hence, a Config may not specify any rooms, and a Room may not include any exits.

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).