Lab 0 2015

From 6.034 Wiki

Revision as of 21:50, 5 September 2006

__NUMBERS__

The purpose of this problem set is to familiarize you with this term's problem set system and to serve as a diagnostic for programming ability and facility with MIT Scheme. 6.034 uses MIT Scheme for all of its problem sets and you will be called on to understand the functioning of large systems, as well as to write significant pieces of code yourself.

While coding is not, in itself, a focus of this class, artificial intelligence is a hard subject full of subtleties. As such, it is important that you be able to focus on the problems you are solving, rather than the mechanical code necessary to implement the solution. If you struggle with the problems in this problem set, you will likely struggle with all subsequent problem sets as well, and 6.034 will be very difficult for you.

If Scheme doesn't come back to you by the end of this problem set, we recommend that you seek extra help through the Course 6/HKN tutoring program, which matches students who want help with students who've taken and done well in a class. The department pays the tutor, and the program comes highly recommended.

Scheme resources

Some resources to help you knock the rust off of your Scheme:

• Your trusty 6.001 book, Structure and Interpretation of Computer Programming, available online
• The standard Scheme documentation, which is called "R5RS"
• Course 6/HKN tutoring program

Problem set logistics

The first thing you need to do is set up a 6.034 section in your Athena files. From any Athena terminal, run these commands:

add 6.034
6.034-setup

This script creates a 6.034-psets directory in your Athena home directory, with a subdirectory for each problem set, and sets the permissions on them so that your TA can access the files in it. Changing these permissions may affect your grade.

In order to get credit for a problem set, you must copy the files containing any code you wrote into the appropriate directory. This is how you submit your solutions.

...

DrScheme

There are many versions of Scheme out there. 6.001 used different ones in different places. In order for the code in this class to work, though, we need to standardize on one version of Scheme.

This class will be done entirely using the DrScheme environment. You may have used DrScheme to do your projects in 6.001. In fact, DrScheme supports several dialects of the Scheme language, so the one you should pick is called "PLT Textual".

You should not use 6.001 Scheme or MIT Scheme to do the problem sets! If you do, you will get strange error messages, and the TAs will not be able to help you.

You run DrScheme on Athena like this:

add drscheme
drscheme &

You can also download it to run it on your own computer.

Answering questions

The main file of this problem set is called ps0.scm. Open that file in DrScheme. The file contains a lot of (define) statements that you need to fill in with your solutions.

The first thing to fill in is a multiple choice question. The answer should be extremely easy. Many problem sets will begin with some simple multiple choice questions to make sure you're on the right track.

Run the tester

Every problem set comes with a file called tester.scm. This file checks your answers to the problem set. For problems that ask you to provide a function, the tester will test your function with several different inputs and see if the output is correct. For multiple choice questions, the tester will tell you if your answer was right. Yes, that means that you never need to submit wrong answers to multiple choice questions.

• Open the file tester.scm in DrScheme and click "Run".
• It should output the results of a lot of tests in your DrScheme window. You should pass one test (your answer to the multiple choice question), and fail the others, because you haven't solved those problems yet.

You should run the tester early and often, and definitely make sure you pass all the tests before you submit a problem set. Think of it as being like the "Check" button from 6.001. It makes sure you're not losing points unnecessarily.

Scheme programming

Now it's time to write some Scheme.

Warm-up stretch

Write the following functions:

• (cube n), which takes in a number and returns its cube. For example, (cube 3) => 27.
• (factorial n), which takes in a non-negative integer n and returns n!, which is the product of the integers from 1 to n. (0! = 1 by definition.)
• (count-pattern pattern lst), which counts the number of times a certain pattern of symbols appears in a list, including overlaps. So (count-pattern '(a b) '(a b c e b a b f)) should return 2, and (count-pattern '(a b a) '(g a b a b a b a)) should return 3.

Expression depth

One way to measure the complexity of a mathematical expression is the depth of the expression describing it in Scheme. Write a program that finds the depth of an expression.

For example:

• (depth 'x)} => 0
• (depth '(expt x 2)) => 1
• (depth '(+ (expt x 2) (expt y 2))) => 2
• (depth '(/ (expt x 5) (expt (- (expt x 2) 1) (/ 5 2)))) => 4

Tree reference

Your job is to write a procedure that is analogous to list-ref, but for trees. This "tree-ref" procedure will take a tree and an index, and return the part of the tree (a leaf or a subtree) at that index. For trees, indices will have to be lists of integers. Consider the tree in Figure 1, represented by this Scheme list: (((1 2) 3) (4 (5 6)) 7 (8 9 10))

To select the element 9 out of it, we’d normally need to do something like (second (fourth tree)). Instead, we’d prefer to do (tree-ref tree (list 3 1)) (note that we’re using zero-based indexing, as in list-ref, and that the indices come in top-down order; so an index of (3 1) means you should take the fourth branch of the main tree, and then the second branch of that subtree). As another example, the element 6 could be selected by (tree-ref tree (list 1 1 1)).

Note that it’s okay for the result to be a subtree, rather than a leaf. So (tree-ref tree (list 0)) should return ((1 2) 3).

Matching

Survey