This preview shows page 1-2-3 out of 10 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

6.001, Fall Semester, 2005—Project 1 1MASSACHVSETTS INSTITVTE OF TECHNOLOGYDepartment of Electrical Engineering and Computer Science6.001—Structure and Interpretation of Computer ProgramsFall Semester, 2005Project 1Issued: Monday, September 19thDue: Friday, September 30th, by 6:00PMCode: bostontravel.scmProgramming Assignment: Navigating Through BostonSince arriving in Boston, Louis Reasoner has been frustrated by his inability to navigate the streetsof Boston with any efficiency or consistency. “Too many one-way streets,” he grumbles, “andbesides, they never put street signs on the big streets, only on the teeny-tiny ones that dead-endafter a block.” To help find out where he is when he gets lost, Louis decides to build an automaticnavigator, but as usual, Louis needs a little help from his friends, especially you.Louis buys an altas of the city, represented by street segments.Eachsegmentisdescribedbytwoendpoints, measured in an appropriate unit (e.g. Mega-Smoots) in a coordinate frame centered atthe Great Dome and oriented to true north. In other words, an endpoint is a combination of an xand y coordinate, measured in some units, from some arbitrary origin. A segment consists of theportion of a street between consecutive intersections.Louis then outfits his car with an automated odometer which measures the distance traveled fromone intersection to another in Mega-Smoots, and a gyroscope which measures the angle turned atan intersection. Hence Louis’ onboard computer can report the (x, y) position of each intersectionhe reaches. Unfortunately, the coordinate system in which he measures his trip is different fromthe one in his atlas – it has unknown origin and rotation, since he is lost when he starts the trip.Thus, Louis is confronted with the following situation. He has an altas, composed of a set of streetsegments, each labeled by a street name, and the positions of the start point and end point ofthe segment, measured in one coordinate frame. He also has information about the actual streetsegments he has travelled, which might include a name (though not always) and which include thepositions of the start point and end point of the segments, but measured in a different coordinateframe.Louis’ plan is to match properties of the street segments he travels with the corresponding propertiesof segments from the atlas, in order to deduce exactly where he is in the city. The idea is that if hetravels far enough, there should only be one way to match his trajectory of segments against theatlas, and this will let him figure out where he is.One way to think about this is as a graph matching problem. That is, Louis has two sets of linesegments, one representing an atlas or map of the city, and one representing the roads he hastraveled. His goal is to figure out how to line up the two sets of lines so that they match – if hecan do that, he can then figure out where he is.6.001, Fall Semester, 2005—Project 1 2Data AbstractionsLouis begins by trying to make sense of his data. He calls the street segments on his atlas atlas-segments to distinguish them from the trip-segments that he actually travels. Each segment has a(perhaps non-unique) name, as well as two endpoints, and each point has an x and y coordinate.You will hear a lot about data abstractions, and constructors and selectors in lecture on Thursday,September 22nd. If you want to get started on the project before then, you might either readthe appropriate section of the textbook, or view the online lectures and lecture notes, or read thefollowing brief description.A data abstraction is just a way of gluing things together into a new thing that you can treatas an atomic unit. Associated with a data abstraction is a constructor –awayoftakingtwoor more parts and gluing them together; and some selectors – procedures that take one of theseabstractions and pull apart a desired piece. The most common data abstraction in Scheme is alist. It has a constructor, called list, which takes an arbitrary number of arguments, and createsan ordered sequence of those arguments. For example:(define my-test (list 12345))To get the parts back out of a list, we can use a built-in selector, called list-ref, for example:>(list-ref my-test 0)1>(list-ref my-test 3)4Note that what you might think of as the first element of the list is referenced as the zeroth element.Now, Louis begins by defining constructors for his abstractions:(define make-segment ; string, point, point -> segment(lambda (name start finish) (list name start finish)))(define make-point ; number,number -> point(lambda (x y) (list x y)))The notation in the comment is that a segment consists of three parts, a name (which will be oftype string, and two points; a point consists of two parts, an x and a y coordinate, each of whichis a number. We haven’t seen strings before, these are just sequences of characters, enclosed indouble quotes, such as"this is a string"Strings come with their own sets of procedures for comparison, for example, to compare two strings,one uses6.001, Fall Semester, 2005—Project 1 3>(define string-test "this is a string")>(string=? string-test "this is a string")#tExercise 1: Louis represents an atlas and a trip as lists of segments:(define make-atlas list) ; segment, ... -> list<segment>(define make-trip list) ; segment, ... -> list<segment>Note that the segments in a trip and an atlas appear in an arbitrary order. In particular, thesegments in a trip do not appear in the order in which Louis drove through them.Note that these definitions are provided for you in the file bostontravel.scm whichyou can download from the web site and save.Louis makes a simple test atlas, called trial-atlas-0, as follows:(define trial-atlas-segment-1(make-segment "beacon" (make-point 0 0) (make-point 0 2)))(define trial-atlas-segment-2(make-segment "cambridge" (make-point 0 2) (make-point 3 5)))(define trial-atlas-0(make-atlas trial-atlas-segment-1 trial-atlas-segment-2))Draw a box-and-pointer diagram for the list structure corresponding to trial-atlas-0.(Youdon’tactually have to turn this part in, but we strongly encourage you to do this problem, so you havea clear understanding of the data structures you are using.)Exercise 2: Given these constructors, we need to define appropriate selectors for each of thecomponents of the compound data items. Provide definitions for the selectors below:;;; Given a segment, we should be able to get its


View Full Document

MIT 6 001 - Study Guide

Documents in this Course
Quiz 1

Quiz 1

6 pages

Databases

Databases

12 pages

rec20

rec20

2 pages

Quiz II

Quiz II

15 pages

Streams

Streams

5 pages

Load more
Download Study Guide
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Study Guide and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Study Guide 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?