Lab 0 2015

From 6.034 Wiki

Revision as of 16:08, 31 August 2008

__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 Python. 6.034 uses Python 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 Python 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:

• Any of the many good Python handbooks out there, such as those recommended on Main_Page
• The standard Python documentation, at [1] (the Library Reference and the Language Reference are particularly useful, if you know what you're looking for)
• Course 6/HKN tutoring program

Python

There are a number of versions of Python available. This course will use standard Python ("CPython") from http://www.python.org/. If you are running Python on your own computer, you should download and install Python 2.5 from http://www.python.org/download/ .

You can run the Python interpreter on Athena like this:

 add python
 idle &

You can, of course, edit Python files in a plain-text editor, and run them on Athena like this:

 add python
 python "[name-of-file]"

Note that "idle" does not currently run on Solaris Athena machines; the current Athena Solaris version of Python is too old to support it. In general, we recommend that you use Linux Athena when possible. We will support Solaris machines, but you'll probably have a better experience running on your own personal computer or on Linux Athena machines.

Getting the problem set code

If you are working on Athena

The code for the problem sets is in the 6.034 locker. You can get problem set 0 like this:

 mkdir -p ~/6.034-psets/lab0/
 cp -R /mit/6.034/psets-f07/lab0/* ~/6.034-psets/lab0/

Then, you can edit the code in your ~/6.034-psets/lab0 directory. That way, you won't need to do anything to submit the code - it will already be in the right place.

If you are working on another computer with Python

Create a folder for the problem set.

Download this file and extract it: http://web.mit.edu/6.034/psets-f07/lab0/lab0.zip

You can also view the code without downloading it: http://web.mit.edu/6.034/psets-f07/lab0/

Answering questions

The main file of this problem set is called lab0.py. Open that file in IDLE. The file contains a lot of incomplete 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.py. 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.py in IDLE and click "Run >> Python Shell".
• It should output the results of a lot of tests in your IDLE Shell 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.01. 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.)

We suggest that you should write your functions so that they raise nice clean errors instead of dying messily when the input is invalid. For example, it would be nice if factorial rejected negative inputs right away; otherwise, you might loop forever. You can signal an error like this: (error "factorial: input must not be negative")

Error handlng doesn't affect your problem set grade, but on later problems it might save you some angst when you're trying to track down a bug.

• 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

Note that you can use the built-in Python "isinstance()" function to determine whether a variable points to a list of some sort. "isinstance()" takes two arguments: the variable to test, and the type (or list of types) to compare it to. For example:

>>> x = [1, 2, 3]
>>> y = "hi!"
>>> isinstance(x, (list, tuple))
True
>>> isinstance(y, (list, tuple))
False

Tree reference

Your job is to write a procedure that is analogous to list referencing, 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 Python tuple: (((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 tree[3][1]. Instead, we’d prefer to do tree-ref(tree, (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, (1, 1, 1)).

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

Distribution

Throughout the semester, you will need to understand, manipulate, and extend complex algorithms implemented in Python. You may also want to write more functions than we provide in the skeleton file for a problem set.

In this problem, you will write a function def distribute(lst) that applies arithmetic distribution to a mathematical expression. For example, it would take something like 5*(3+4) and rewrite it as 5*3+5*4.

The function will take a list of the form:

[5, '*', ['x', '+', 4]]

It will return a list of the form:

[5, '*', 3, '+', 5, '*', 4]

Your code should return a list that evaluates to the same value as the input list. It should also deal correctly with nested expressions like the following:

[5, *, [3, '-', [4, '+', 2] * ['x', + 5]]]

should become something like:

[5, '*', 3, '-', 5, '*', 4, '*', 'x', '-', 5, '*', 4, '*', 5, '-', 5, '*', 2, '*', 'x', '-', 5, '*', 2, '*', 5]

You do not have to simplify expressions if you don't want to, although you may if you so choose.

The only operators that will be used are '+', '-', and '*', representing addition, subtraction, and multiplication, respectively. Everything else is a variable or a number.

Survey

We are always working to improve the class. Most problem sets will have at least one survey question at the end to help us with this. Your answers to these questions are purely informational, and will have no impact on your grade.

Please fill in the answers to the following questions in the definitions at the end of lab0.py:

• When did you take 6.01?
• How many hours did 6.01 projects take you?
• How well do you feel you learned the material in 6.01?
• How many hours did this problem set take you?

When you're done

Remember to run the tester! The tester will automatically upload your code to the 6.034 server for grading and collection.

Questions?

If you have questions about the problem set, e-mail Rob Speer (rspeer@mit).