Lab 0 2015

From 6.034 Wiki

(Difference between revisions)
Jump to: navigation, search
(simplified instructions)
(Python: note about Windows incompatibility)
(47 intermediate revisions not shown.)
Line 1: Line 1:
-
* '''Released''': Thursday, September 10
+
* '''Due''': Tuesday, September 15, at '''10:00PM'''
-
* '''Due''': Friday, September 18
+
* '''Lab File''': http://web.mit.edu/6.034/www/labs/lab0/lab0.zip
 +
* '''Grader''' : https://ai6034.mit.edu/labs
 +
 
 +
 
 +
 
 +
'''Note:''' As with all labs, you will need to have a [https://ai6034.mit.edu/labs key file] in order to submit.
 +
 
__TOC__
__TOC__
The purpose of this lab is to familiarize you with this
The purpose of this lab is to familiarize you with this
-
term's lab system and to serve as a diagnostic for programming
+
term's lab system and to diagnose your programming
ability and facility with Python. 6.034 uses Python for  
ability and facility with Python. 6.034 uses Python for  
all of its labs, and you will be called on to understand the
all of its labs, and you will be called on to understand the
Line 26: Line 32:
* Any of the many good Python handbooks out there, such as:
* Any of the many good Python handbooks out there, such as:
-
** [http://diveintopython.org Dive Into Python], for experienced programmers
+
** [http://diveintopython.net Dive Into Python], for experienced programmers
** O'Reilly's [http://proquest.safaribooksonline.com/9780596513986/ Learning Python]
** O'Reilly's [http://proquest.safaribooksonline.com/9780596513986/ Learning Python]
** [http://www.greenteapress.com/thinkpython/ Think Python], for beginning programmers
** [http://www.greenteapress.com/thinkpython/ Think Python], for beginning programmers
* The standard Python documentation, at [http://docs.python.org/] (the Library Reference and the Language Reference are particularly useful, if you know what you're looking for)
* The standard Python documentation, at [http://docs.python.org/] (the Library Reference and the Language Reference are particularly useful, if you know what you're looking for)
-
* [http://hkn.mit.edu/tutor.php Course 6/HKN tutoring program]
+
* [https://hkn.mit.edu/tutoring Course 6/HKN tutoring program]
== Python ==
== 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/ . All the lab code will require at least version 2.3.
+
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,  Python 2.6, or Python 2.7 from http://www.python.org/download/ . All the lab code will require at least version 2.3.  '''Please note that our code is not designed to work with Python 3.'''
 +
 
 +
<b>If you are using Windows:</b> When run on Windows, Python versions 2.6.5 through 2.7.3 seem to be incompatible with our server.  The recommended solution is to install a version of Python >= 2.7.4 or <= 2.6.4.  For example, Python 2.7.10 works well on Windows.
Mac OS X comes with Python 2.3 pre-installed, but the version you can download from python.org has better support for external libraries and a better version of IDLE.
Mac OS X comes with Python 2.3 pre-installed, but the version you can download from python.org has better support for external libraries and a better version of IDLE.
Line 52: Line 60:
   python filename.py
   python filename.py
</code>
</code>
-
 
-
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 lab code ===
=== Getting the lab code ===
Line 66: Line 72:
</code>
</code>
:Then, you can edit the code in your ~/6.034-labs/lab0 directory. That way, you won't need to do anything to submit the code - it will already be in the right place.
:Then, you can edit the code in your ~/6.034-labs/lab0 directory. That way, you won't need to do anything to submit the code - it will already be in the right place.
 +
:You can ssh into linux.mit.edu to work on Athena from a different computer (thank you SIPB)
;If you are working on another computer with Python
;If you are working on another computer with Python
:Create a folder for the lab.
:Create a folder for the lab.
Line 74: Line 81:
=== Getting the Submit Key ===
=== Getting the Submit Key ===
-
In order to submit your labs, you must download a "key.py" file and place it in the same directory as your labs.  The "key.py" file contains login information used by the tester to identify you personally to the testing server.
+
In order to submit your labs, you must download a "key.py" file and place it in the same directory as your labs.  The "key.py" file contains login information used by the tester to identify you personally to the testing server.  You can continue using the same key throughout the semester unless you change your Athena password, in which case you may need to download a new "key.py".
-
You can download a key from https://6.034.scripts.mit.edu:444/fall09/tester/ .  Make sure that you have an up-to-date [http://ca.mit.edu MIT Certificate] before going to this page.  Note that the page doesn't currently work in Apple's Safari Web browser (because of a bug in Safari regarding certificates); use Firefox instead, or download the file on Athena.
+
You can download a key from https://ai6034.mit.edu/labs .  Make sure that you have an up-to-date [http://ca.mit.edu MIT Certificate] before going to this page.  Note that the page doesn't currently work in Apple's Safari Web browser (because of a bug in Safari regarding certificates); use Firefox/Chrome instead, or download the file on Athena.
=== Answering questions ===
=== Answering questions ===
Line 91: Line 98:
You can run the online tester as many times as you want. If your code fails a test, you can submit it and try again. Because you always have the opportunity to fix your bugs, you can only get a 5 on a problem set if it passes all the tests. If your code fails a test, your grade will be 4 or below.
You can run the online tester as many times as you want. If your code fails a test, you can submit it and try again. Because you always have the opportunity to fix your bugs, you can only get a 5 on a problem set if it passes all the tests. If your code fails a test, your grade will be 4 or below.
-
==== Using the command line ====
+
==== Using IDLE ====
-
Working from a command line is probably the easiest way to run the tester. Open your operating system's Terminal or Command Prompt, and <code>cd</code> to the directory containing the files for Lab 0. Then, run:
+
-
<pre>python tester.py</pre>
+
If you are using IDLE, or if you do not have easy access to a command line (as on Windows), IDLE can run the tester.
-
to run the offline tester, and
+
Open the <tt>tester.py</tt> file and run it using Run Module or F5.  This will run the offline tests for you.  When the offline tests pass (or when you're up against a deadline, or when you have questions for the staff) you can
-
<pre>python tester.py submit</pre>
+
  test_online()
-
to run the online tester and submit your code.
+
to submit your code and run the online tests.
-
You should run the tester early and often. Think of it as being like the "Check" button from 6.01. It makes sure you're not losing points unnecessarily.
+
In fact, it will run the submission and online test just as soon as you pass the offline tests, saving you a few keystrokes.
-
==== Using IDLE ====
+
You should run the tester (and submit!) early and often. Think of it as being like the "Check" button from 6.01. It makes sure you're not losing points unnecessarily.  Submitting your code makes it easy for the staff to look at it and help you.
-
You might find it difficult to run Python from the command line on your system (especially on Windows). In that case, you can also use IDLE to run the tester.
+
==== Using the command line ====
-
Your best bet is to open the <tt>tester.py</tt> file and run it using Run Module or F5.  This will run the offline tests for you. When the offline tests pass you can
+
If you realize just how much emacs and/or the command line rock, then you can open your operating system's Terminal or Command Prompt, and <code>cd</code> to the directory containing the files for Lab 0. Then, run:
-
  test_online()
+
<pre>python tester.py</pre>
-
to submit your code and run the online tests.
+
to run the offline tester, and
 +
 
 +
<pre>python tester.py submit</pre>
 +
 
 +
to submit your code and run the online tester.
-
In fact, there is a new <tt>[http://web.mit.edu/6.034/www/labs/lab0/tester.py tester.py]</tt>, and if you download this one, it will run the submission and online test just as soon as you pass the offline tests, saving you a few keystrokes.
+
You should run the tester (and submit!) early and often. Think of it as being like the "Check" button from 6.01. It makes sure you're not losing points unnecessarily.  Submitting your code makes it easy for the staff to look at it and help you.
== Python programming ==
== Python programming ==
Line 125: Line 135:
::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: <code>raise Exception, "factorial: input must not be negative"</code>
::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: <code>raise Exception, "factorial: input must not be negative"</code>
::Error handling doesn't affect your lab grade, but on later problems it might save you some angst when you're trying to track down a bug.
::Error handling doesn't affect your lab grade, but on later problems it might save you some angst when you're trying to track down a bug.
-
* <tt>count-pattern(pattern lst)</tt>, which counts the number of times a certain pattern of symbols appears in a list, including overlaps. So <tt>count-pattern( ('a', 'b'), ('a', 'b', 'c', 'e', 'b', 'a', 'b', 'f'))</tt> should return 2, and <tt>count-pattern(('a', 'b', 'a'), ('g', 'a', 'b', 'a', 'b', 'a', 'b', 'a'))</tt> should return 3.
+
* <tt>count_pattern(pattern lst)</tt>, which counts the number of times a certain pattern of symbols appears in a list, including overlaps. So <tt>count_pattern( ('a', 'b'), ('a', 'b', 'c', 'e', 'b', 'a', 'b', 'f'))</tt> should return 2, and <tt>count_pattern(('a', 'b', 'a'), ('g', 'a', 'b', 'a', 'b', 'a', 'b', 'a'))</tt> should return 3.
=== Expression depth ===
=== Expression depth ===
One way to measure the complexity of a mathematical expression is the
One way to measure the complexity of a mathematical expression is the
-
depth of the expression describing it in Python lists. Write a program that
+
depth of the expression describing it in Python lists or tuples. Write a program that
finds the depth of an expression.
finds the depth of an expression.
Line 135: Line 145:
* <tt>depth('x') => 0</tt>
* <tt>depth('x') => 0</tt>
* <tt>depth(('expt', 'x', 2)) => 1</tt>
* <tt>depth(('expt', 'x', 2)) => 1</tt>
-
* <tt>depth(('+', ('expt', 'x', 2), ('expt', 'y', 2))) => 2</tt>
+
* <tt>depth(['+', ['expt', 'x', 2], ['expt', 'y', 2]]) => 2</tt>
* <tt>depth(('/', ('expt', 'x', 5), ('expt', ('-', ('expt', 'x', 2), 1), ('/', 5, 2)))) => 4</tt>
* <tt>depth(('/', ('expt', 'x', 5), ('expt', ('-', ('expt', 'x', 2), 1), ('/', 5, 2)))) => 4</tt>
Line 168: Line 178:
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 lab.
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 lab.
-
In this problem, you will complete a simple computer algebra system that reduces nested expressions made of sums and products into a single sum of products. For example, it turns the expression <code>(2 * (x + 1) * (y + 3))</code> into <code>((2 * x * y) + (2 * x * 3) + (2 * 1 * y) + (2 * 1 * 3))</code>. You could choose to simplify further, such as to ((2 * x * y) + (6 * x) + (2 * y) + 6)), but it is not necessary.
+
In this problem, you will complete a simple computer algebra system that reduces nested expressions made of sums and products into a <b>single sum of products</b>. For example, it turns the expression <code>(2 * (x + 1) * (y + 3))</code> into <code>((2 * x * y) + (2 * x * 3) + (2 * 1 * y) + (2 * 1 * 3))</code>. You could choose to simplify further, such as to ((2 * x * y) + (6 * x) + (2 * y) + 6)), but it is not necessary.
This procedure would be one small part of a symbolic math system, such as the integrator presented in Monday's lecture. You may want to keep in mind the principle of reducing a complex problem to a simpler one.
This procedure would be one small part of a symbolic math system, such as the integrator presented in Monday's lecture. You may want to keep in mind the principle of reducing a complex problem to a simpler one.
Line 205: Line 215:
Remember to run the tester!  The tester will automatically upload your code to the 6.034 server for grading and collection.
Remember to run the tester!  The tester will automatically upload your code to the 6.034 server for grading and collection.
-
== Questions? Issues? ==
+
== FAQ ==
 +
 
 +
It's quite possible that this lab -- or, in particular, the grader system -- will have issues that need to be fixed or things that need to be clarified.
 +
 
 +
If you have a question or a bug report, send an e-mail to [mailto:6.034-2015-support@mit.edu 6.034-2015-support@mit.edu].
 +
 
 +
 
 +
Q: When I submit to the online tester, it says I passed all the tests, but it shows my grade as 0.00.
-
It's quite likely that this lab -- or, in particular, the grader system -- will have issues that need to be fixed or things that need to be clarified. After all, we have never done this in Python before, and we have also never had a grader with instant feedback before.
+
A: Try downloading a new key.py file.
-
If you have a question or a bug report, send an e-mail to [mailto:6.034-tas@mit.edu 6.034-tas@mit.edu].
 
-
=== Errata ===
+
Q: When I submit to the online tester, it hangs for a while and/or eventually prints a stack trace ending in '''httplib.BadStatusLine: ' ' '''
-
On Question 1 in Section 1, answer option 2 should read "Python v2.5 or Python v2.6".
+
A: We're investigating this; for now the best workaround is to ssh into Athena (or physically transfer your files over to an Athena computer if that's easier for you) and submit from there.  To help us fix this problem if you encounter it, please email jmn@ with your operating system, Python version, and what program you're using to run tester.py.

Revision as of 20:14, 13 July 2016


Note: As with all labs, you will need to have a key file in order to submit.


Contents

The purpose of this lab is to familiarize you with this term's lab system and to diagnose your programming ability and facility with Python. 6.034 uses Python for all of its labs, 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 lab, 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.

Python resources

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


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, Python 2.6, or Python 2.7 from http://www.python.org/download/ . All the lab code will require at least version 2.3. Please note that our code is not designed to work with Python 3.

If you are using Windows: When run on Windows, Python versions 2.6.5 through 2.7.3 seem to be incompatible with our server. The recommended solution is to install a version of Python >= 2.7.4 or <= 2.6.4. For example, Python 2.7.10 works well on Windows.

Mac OS X comes with Python 2.3 pre-installed, but the version you can download from python.org has better support for external libraries and a better version of IDLE.

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 filename.py

Getting the lab code

If you are working on Athena
The code for the labs is in the 6.034 locker. You can get lab 0 like this:

 attach 6.034
 mkdir -p ~/6.034-labs/lab0/
 cp -R /mit/6.034/www/labs/lab0/* ~/6.034-labs/lab0/

Then, you can edit the code in your ~/6.034-labs/lab0 directory. That way, you won't need to do anything to submit the code - it will already be in the right place.
You can ssh into linux.mit.edu to work on Athena from a different computer (thank you SIPB)
If you are working on another computer with Python
Create a folder for the lab.
Download this file and extract it: http://web.mit.edu/6.034/www/labs/lab0/lab0.zip

You can also view the code without downloading it: http://web.mit.edu/6.034/www/labs/lab0/

Getting the Submit Key

In order to submit your labs, you must download a "key.py" file and place it in the same directory as your labs. The "key.py" file contains login information used by the tester to identify you personally to the testing server. You can continue using the same key throughout the semester unless you change your Athena password, in which case you may need to download a new "key.py".

You can download a key from https://ai6034.mit.edu/labs . Make sure that you have an up-to-date MIT Certificate before going to this page. Note that the page doesn't currently work in Apple's Safari Web browser (because of a bug in Safari regarding certificates); use Firefox/Chrome instead, or download the file on Athena.

Answering questions

The main file of this lab 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 labs will begin with some simple multiple choice questions to make sure you're on the right track.

Run the tester

Every lab comes with a file called tester.py. This file checks your answers to the lab. 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.

The tester has two modes: "offline" mode (the default), and "online" or "submit" mode. The former runs some basic, self-contained internal tests on your code. It can be run as many times as you would like. The latter runs some more tests, some of which may be randomly generated, and uploads your code to the 6.034 grader for grading.

You can run the online tester as many times as you want. If your code fails a test, you can submit it and try again. Because you always have the opportunity to fix your bugs, you can only get a 5 on a problem set if it passes all the tests. If your code fails a test, your grade will be 4 or below.

Using IDLE

If you are using IDLE, or if you do not have easy access to a command line (as on Windows), IDLE can run the tester.

Open the tester.py file and run it using Run Module or F5. This will run the offline tests for you. When the offline tests pass (or when you're up against a deadline, or when you have questions for the staff) you can

 test_online()

to submit your code and run the online tests.

In fact, it will run the submission and online test just as soon as you pass the offline tests, saving you a few keystrokes.

You should run the tester (and submit!) early and often. Think of it as being like the "Check" button from 6.01. It makes sure you're not losing points unnecessarily. Submitting your code makes it easy for the staff to look at it and help you.

Using the command line

If you realize just how much emacs and/or the command line rock, then you can open your operating system's Terminal or Command Prompt, and cd to the directory containing the files for Lab 0. Then, run:

python tester.py

to run the offline tester, and

python tester.py submit

to submit your code and run the online tester.

You should run the tester (and submit!) early and often. Think of it as being like the "Check" button from 6.01. It makes sure you're not losing points unnecessarily. Submitting your code makes it easy for the staff to look at it and help you.

Python programming

Now it's time to write some Python.

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: raise Exception, "factorial: input must not be negative"
Error handling doesn't affect your lab 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 Python lists or tuples. 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

float

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

Symbolic algebra

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

In this problem, you will complete a simple computer algebra system that reduces nested expressions made of sums and products into a single sum of products. For example, it turns the expression (2 * (x + 1) * (y + 3)) into ((2 * x * y) + (2 * x * 3) + (2 * 1 * y) + (2 * 1 * 3)). You could choose to simplify further, such as to ((2 * x * y) + (6 * x) + (2 * y) + 6)), but it is not necessary.

This procedure would be one small part of a symbolic math system, such as the integrator presented in Monday's lecture. You may want to keep in mind the principle of reducing a complex problem to a simpler one.

An algebraic expression can be simplified in this way by repeatedly applying the associative law and the distributive law.

Associative law
((a + b) + c) = (a + (b + c)) = (a + b + c)
((a * b) * c) = (a * (b * c)) = (a * b * c)
Distributive law
((a + b) * (c + d)) = ((a * c) + (a * d) + (b * c) + (b * d))

The code for this part of the lab is in algebra.py. It defines an abstract Expression class, Sum and Product expressions, and a method called Expression.simplify(). This method starts by applying the associative law for you, but it will fail to perform the distributive law. For that it delegates to a function called do_multiply that you need to write. Read the documentation in the code for more details.

This exercise is meant to get you familiar with Python and using it to solve an interesting problem. It is intended to be algorithmically straightforward. You should try to reason out the logic that you need for this function on your own. If you're having trouble expressing that logic in Python, though, don't hesitate to ask a TA.

Some hints for solving the problem:

  • How do you use recursion to make sure that your result is thoroughly simplified?
  • In which case should you not recursively call simplify()?

Survey

We are always working to improve the class. Most labs 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 lab 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.

FAQ

It's quite possible that this lab -- or, in particular, the grader system -- will have issues that need to be fixed or things that need to be clarified.

If you have a question or a bug report, send an e-mail to 6.034-2015-support@mit.edu.


Q: When I submit to the online tester, it says I passed all the tests, but it shows my grade as 0.00.

A: Try downloading a new key.py file.


Q: When I submit to the online tester, it hangs for a while and/or eventually prints a stack trace ending in httplib.BadStatusLine: ' '

A: We're investigating this; for now the best workaround is to ssh into Athena (or physically transfer your files over to an Athena computer if that's easier for you) and submit from there. To help us fix this problem if you encounter it, please email jmn@ with your operating system, Python version, and what program you're using to run tester.py.

Personal tools