2016 Lab 0

From 6.034 Wiki

(Difference between revisions)
Jump to: navigation, search
(Built-in data types: links for how to use sorted, etc)
m (Getting the Submit Key)
(24 intermediate revisions not shown.)
Line 1: Line 1:
-
* '''Due''': Tuesday, September 13, at '''10:00PM'''
+
__TOC__
-
* '''Lab File''': http://web.mit.edu/6.034/www/labs/lab0/lab0.zip
+
This lab is due by Tuesday, September 13 at '''10:00pm'''.
-
* '''Grader''' : https://ai6034.mit.edu/labs
+
 +
To work on this lab, you will need to get the code:
 +
* You can view the files at: http://web.mit.edu/6.034/www/labs/lab0/
 +
* Download it as a ZIP file: http://web.mit.edu/6.034/www/labs/lab0/lab0.zip
 +
* Or, on Athena, use Git to clone the files from <tt>/mit/6.034/www/labs/lab0/</tt> (see detailed instructions below)
 +
Your answers for this lab will go in the main file <tt>lab0.py</tt>.
'''Note:''' As with all labs, you will need to have a [https://ai6034.mit.edu/labs key file] in order to submit.
'''Note:''' As with all labs, you will need to have a [https://ai6034.mit.edu/labs key file] in order to submit.
-
__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 diagnose your programming
term's lab system and to diagnose your programming
Line 39: Line 42:
-
== Python ==
+
= Python =
There are a number of versions of Python available.  6.034 uses 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.'''
There are a number of versions of Python available.  6.034 uses 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.'''
Line 61: Line 64:
</code>
</code>
-
=== Getting the lab code ===
+
== Getting the lab code ==
-
;If you are working on Athena
+
=== If you are working on Athena ===
-
:The code for the labs is in the 6.034 locker. You can get lab 0 like this:
+
First, create a directory for your 6.034 labs and navigate to it. For example:
 +
mkdir ~/6.034-labs/
 +
cd ~/6.034-labs/
-
<code>
+
Now, you can use Git to clone the lab code directly from the 6.034 Athena locker:
-
  attach 6.034
+
git clone /mit/6.034/www/labs/lab0
-
  mkdir -p ~/6.034-labs/lab0/
+
 
-
  cp -R /mit/6.034/www/labs/lab0/* ~/6.034-labs/lab0/
+
This will create a lab0 directory containing all the files you need for Lab 0.  You can edit the code in this directory (for example, ~/6.034-labs/lab0/).
-
</code>
+
 
-
:Then, you can edit the code in your ~/6.034-labs/lab0 directory.  
+
<!-- old Athena instructions
-
:You can ssh into linux.mit.edu to work on Athena from a different computer (thank you SIPB)
+
You can get lab 0 like this:
-
;If you are working on another computer with Python
+
 
-
:Create a folder for the lab.
+
attach 6.034
-
:Download this file and extract it: http://web.mit.edu/6.034/www/labs/lab0/lab0.zip
+
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.  
 +
-->
 +
You can also ssh into athena.dialup.mit.edu to work on Athena from a different computer.
 +
 
 +
Using Git has a couple advantages:
 +
* Local version control: You can use Git to keep a local record of the changes you've made as you work on your lab, which makes it easy to revert to a previous implementation.  You can learn more about using Git [http://gitref.org/basic/ here] (good for getting started) or from the [https://git-scm.com/doc official Git documentation].  Using Git is not a requirement for 6.034, but you may find it helpful for tracking your files.
 +
* Easy updates: If we need to release an update to the lab code, you can run a simple "git pull" command to get the update instead of having to manually download the updated files.
 +
 
 +
=== If you are working on another computer with Python ===
 +
 
 +
==== Method 1: Git (recommended) ====
 +
 
 +
If you have Git, or want to install Git, you can clone the lab code from the 6.034 Athena locker.  This method has a couple advantages:
 +
* Local version control: You can use Git to keep a local record of the changes you've made as you work on your lab, which makes it easy to revert to a previous implementation.  You can learn more about using Git [http://gitref.org/basic/ here] (good for getting started) or from the [https://git-scm.com/doc official Git documentation].  Using Git is not a requirement for 6.034, but you may find it helpful for tracking your files.
 +
* Easy updates: If we need to release an update to the lab code, you can run a simple "git pull" command to get the update instead of having to manually download the updated files.
 +
 
 +
On a command line, navigate to the folder in which you want to put all your 6.034 labs.  Then, type this command to clone the lab0 code, replacing "username" with your Athena username:
 +
git clone username@athena.dialup.mit.edu:/mit/6.034/www/labs/lab0
 +
 
 +
It will ask for your Athena password.  After the files download, you will have a new directory called "lab0" containing the files for Lab 0.
 +
 
 +
==== Method 2: Download the files from a browser ====
 +
Create a folder for the lab, then 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/
You can also view the code without downloading it: http://web.mit.edu/6.034/www/labs/lab0/
-
=== 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.  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".
+
In order to submit your labs, you must download a "key.py" file and place it in the same directory as your labs (e.g. ~/6.034-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 [http://ca.mit.edu MIT Certificate] before going to this page. If the page doesn't 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.
+
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. (If you do not have a valid certificate, https://ai6034.mit.edu/labs will load but will display an error message telling you something is wrong with your certificate.) If the page doesn't 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 ==
The main file of this lab is called <code>lab0.py</code>. Open that file in IDLE (or your preferred Python editor). The file contains a lot of incomplete statements for you to fill in with your solutions.
The main file of this lab is called <code>lab0.py</code>. Open that file in IDLE (or your preferred Python editor). The file contains a lot of incomplete statements for you to fill in with your solutions.
The first item 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.
The first item 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 ===
+
== Running the tester ==
Every lab comes with a file called <code>tester.py</code>. 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.
Every lab comes with a file called <code>tester.py</code>. 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.
Line 100: Line 130:
Your grade online will never decrease, so you should submit your code online 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 also makes it easy for the staff to look at it and help you.
Your grade online will never decrease, so you should submit your code online 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 also makes it easy for the staff to look at it and help you.
-
==== Using IDLE ====
+
=== 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.
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.
Line 112: Line 142:
In fact, it will run the submission and online test just as soon as it completes offline tests, saving you a few keystrokes.
In fact, it will run the submission and online test just as soon as it completes offline tests, saving you a few keystrokes.
-
==== Using the command line ====
+
=== 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 <code>cd</code> to the directory containing the files for Lab 0. Then, run:
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:
Line 124: Line 154:
to submit your code and run the online tester.
to submit your code and run the online tester.
-
== Python programming ==
+
= Python programming =
Now it's time to write some Python!
Now it's time to write some Python!
(Note: The programming part of Lab 0 is optional; for full credit, you only need to fill in the survey questions and submit your code online.  However, we highly recommend completing the programming part, as it will be good practice for future labs!)
(Note: The programming part of Lab 0 is optional; for full credit, you only need to fill in the survey questions and submit your code online.  However, we highly recommend completing the programming part, as it will be good practice for future labs!)
-
=== Warm-up: Exponentiation ===
+
== Warm-up: Exponentiation ==
Using <tt>**</tt> or <tt>math.pow()</tt>, write a function that takes in a number <tt>x</tt> and returns its cube.  For example, cube(3) -> 27.
Using <tt>**</tt> or <tt>math.pow()</tt>, write a function that takes in a number <tt>x</tt> and returns its cube.  For example, cube(3) -> 27.
  def cube(x):
  def cube(x):
Line 137: Line 167:
-->
-->
-
=== Recursion ===
+
== Recursion ==
-
Using recursion, write a function that takes in a positive integer <tt>n</tt> and returns the nth Fibonacci number:
+
The nth Fibonacci number, F<sub>n</sub>, is defined recursively as
 +
:F<sub>n</sub> = F<sub>n-1</sub> + F<sub>n-2</sub>
 +
starting from F<sub>1</sub> = F<sub>2</sub> = 1, so that the sequence starts: 1, 1, 2, 3, 5, 8, ... 
 +
 
 +
Using recursion, write a function that takes in a positive integer <tt>n</tt> and returns the <tt>n</tt>th Fibonacci number:  
 +
 
  def fibonacci(n):
  def fibonacci(n):
-
We recommend writing your functions so that they raise nice clean errors instead of failing silently or messily when the input is invalid. For example, it would be nice if <tt>fibonacci</tt> 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.
+
We recommend writing your functions so that they raise nice clean errors instead of failing silently or messily when the input is invalid. For example, it would be nice if <tt>fibonacci</tt> rejected negative inputs right away; otherwise, you might loop forever. You can signal an error like this:
 +
raise Exception("fibonacci: input must not be negative")
 +
Or, better yet, you can signal a specific error type:
 +
  raise ValueError("fibonacci: 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.
 +
 
 +
=== Expressions as nested lists ===
 +
 
 +
Let's try a more interesting application of recursion.  One way to measure the complexity of a mathematical expression is the depth of the expression describing it in Python lists using prefix notation.  Prefix notation (as opposed to infix notation) just means that the operator comes first, followed by all of its operands (arguments).  Although we won't be using prefix notation much in 6.034, you may encounter it in more advanced AI classes that use languages such as Lisp (Scheme, Clojure, etc) and PDDL.  Expressions represented in prefix notation can also be much easier to parse, which is why we will use it in this problem.
 +
 
 +
For example,
 +
 
 +
:x<sup>2</sup> + y<sup>2</sup> (infix notation)
 +
 
 +
is equivalent to
 +
 
 +
:<tt>['+', ['expt', 'x', 2], ['expt', 'y', 2]]</tt> (prefix notation, with <tt>'expt'</tt> representing exponentiation)
 +
 
 +
Each operator can have one or more arguments; for example, the operator <tt>'+'</tt> can be used to sum many numbers: <tt>['+', 10, 20, 30, 40]</tt>.
 +
 
 +
For this problem, we will define the ''expression depth'' of an expression based on the number of nested operations:
 +
* The expression depth of a variable or number (such as <tt>'x'</tt>) is 0.
 +
* The expression depth of an operation depends on the expression depths of all of its children (arguments). In particular, it’s one more than the '''maximum''' of the expression depths of its children.  If you think of the expression as a tree, the expression depth is the height of the tree.
-
Let's try a more interesting application of recursion.  One way to measure the complexity of a mathematical expression is the depth of the expression describing it in Python lists or tuples.  Using recursion, write a function that finds the depth of an expression:
+
Using recursion, write a function that finds the depth of an expression:
  def expression_depth(expr):
  def expression_depth(expr):
Line 150: Line 207:
For example:
For example:
* <tt>expression_depth('x')</tt> -> <tt>0</tt>
* <tt>expression_depth('x')</tt> -> <tt>0</tt>
-
* <tt>expression_depth(('expt', 'x', 2))</tt> -> <tt>1</tt>
+
* <tt>expression_depth(['expt', 'x', 2])</tt> -> <tt>1</tt>
* <tt>expression_depth(['+', ['expt', 'x', 2], ['expt', 'y', 2]])</tt> -> <tt>2</tt>
* <tt>expression_depth(['+', ['expt', 'x', 2], ['expt', 'y', 2]])</tt> -> <tt>2</tt>
-
* <tt>expression_depth(('/', ('expt', 'x', 5), ('expt', ('-', ('expt', 'x', 2), 1), ('/', 5, 2))))</tt> -> <tt>4</tt>
+
* <tt>expression_depth(['/', ['expt', 'x', 5], ['expt', ['-', ['expt', 'x', 2], 1], ['+', 5, 2, 3, 'w', 4]]])</tt> -> <tt>4</tt>
-
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:
+
Note that you can use the built-in Python function <tt>isinstance()</tt> to determine whether a variable points to a list.  <tt>isinstance()</tt> takes two arguments: the variable to test, and the type (or tuple of types) to compare it to.  For example:
<code><pre>
<code><pre>
>>> x = [1, 2, 3]
>>> x = [1, 2, 3]
>>> y = "hi!"
>>> y = "hi!"
-
>>> isinstance(x, (list, tuple))
+
>>> isinstance(x, list)
True
True
-
>>> isinstance(y, (list, tuple))
+
>>> isinstance(y, list)
False
False
</pre></code>
</pre></code>
-
=== Built-in data types ===
+
== Built-in data types ==
-
Here, we're going to practice working with strings, sets, lists, and tuples, and using the Python keywords <tt>len</tt> and <tt>sorted</tt>.  If you're unfamiliar with any of these, you can learn more about them using the <tt>help</tt> command (e.g. <tt>help(len)</tt>) or by searching the documentation at [https://wiki.python.org/moin/ https://wiki.python.org/moin/].
+
Here, we're going to practice working with strings, sets, lists, and tuples, and using the Python keywords <tt>len</tt> and <tt>sorted</tt>.  If you're unfamiliar with any of these, you can learn more about them using the <tt>help</tt> command (e.g. <tt>help(len)</tt>) or by searching the documentation at https://wiki.python.org/moin/.
Without using the keywords <tt>for</tt> or <tt>while</tt>, write a function <tt>compute_string_properties</tt> that takes in a string of lowercase letters and returns a tuple containing the following three elements:
Without using the keywords <tt>for</tt> or <tt>while</tt>, write a function <tt>compute_string_properties</tt> that takes in a string of lowercase letters and returns a tuple containing the following three elements:
Line 174: Line 231:
:2. The number of distinct characters in the string (using a set)
:2. The number of distinct characters in the string (using a set)
-
  def analyze_string(string):
+
  def compute_string_properties(string):
For example:
For example:
Line 194: Line 251:
If you want a challenge, you can try to write a one-line implementation using a dictionary comprehension.
If you want a challenge, you can try to write a one-line implementation using a dictionary comprehension.
-
=== Functions that return functions ===
+
== Functions that return functions ==
-
In Python, a function can return any type of object: an int, a list, a user-defined object, ... or even another function!  By defining your function to be returned inside the main function <tt>create_multiplier_function</tt>, implement <tt>create_multiplier_function</tt> to take in a multiplier m (a number and return a function that multiples its input by m.
+
In Python, a function can return any type of object: an int, a list, a user-defined object, ...or even another function!  By defining your function to be returned inside the main function <tt>create_multiplier_function</tt>, implement <tt>create_multiplier_function</tt> to take in a multiplier <tt>m</tt> (a number and return a function that multiples its input by <tt>m</tt>.
  def create_multiplier_function(m):
  def create_multiplier_function(m):
Line 206: Line 263:
  -50
  -50
-
=== Objects and APIs ===
+
== Objects and APIs ==
Many 6.034 labs include an API for a staff-defined object class.  The API is a generally a section on the wiki that briefly describes the attributes and functions in the object class.  We provide the API as an abstraction so that you don't need to learn the implementation details.
Many 6.034 labs include an API for a staff-defined object class.  The API is a generally a section on the wiki that briefly describes the attributes and functions in the object class.  We provide the API as an abstraction so that you don't need to learn the implementation details.
Here's an example:
Here's an example:
-
<b><tt>Point</tt> API</b>
+
<b>Point API</b>
A <tt>Point</tt> object represents a point in the 2D Cartesian plane. It has an X coordinate and a Y coordinate, each of which you can access and modify:
A <tt>Point</tt> object represents a point in the 2D Cartesian plane. It has an X coordinate and a Y coordinate, each of which you can access and modify:
-
* <b><tt>point</b>.getX()</tt>: returns current X value
+
* <tt><b>point</b>.getX()</tt>: returns current X value
-
* <b><tt>point</b>.getY()</tt>: returns current Y value
+
* <tt><b>point</b>.getY()</tt>: returns current Y value
-
* <b><tt>point</b>.setX(x)</tt>: sets the X value to x, then returns the point
+
* <tt><b>point</b>.setX(x)</tt>: sets the X value to x, then returns the point
-
* <b><tt>point</b>.setY(y)</tt>: sets the Y value to y, then returns the point
+
* <tt><b>point</b>.setY(y)</tt>: sets the Y value to y, then returns the point
-
(where <b><tt>point</tt></b> is a <tt>Point</tt> instance)
+
(where <tt><b>point</b></tt> is a <tt>Point</tt> instance)
You can also use the following (these are defined for most 6.034 object classes):
You can also use the following (these are defined for most 6.034 object classes):
* <tt>point.copy()</tt>, to return a deep copy of the point (that is, a copy that has all the same attributes as the original point)
* <tt>point.copy()</tt>, to return a deep copy of the point (that is, a copy that has all the same attributes as the original point)
-
* <tt>==</tt>, to check whether two points have the same coordinates
+
* <tt>==</tt> , to check whether two points have the same coordinates
* <tt>print</tt>, to print out a human-readable version of a <tt>Point</tt>
* <tt>print</tt>, to print out a human-readable version of a <tt>Point</tt>
-
==== Copying and modifying objects ====
+
=== Copying and modifying objects ===
In some 6.034 labs, you'll need to make copies of an object (such as a <tt>Point</tt>) and modify each copy separately.  Here, you'll implement a function <tt>get_neighbors</tt> that takes in a 2D point (represented as a <tt>Point</tt> object).  In the function, use the <tt>.copy()</tt> method to create and return a list of the input point's four neighbors: the four points that neighbor the input point in the four coordinate directions.  By using the <tt>.copy()</tt> method, you can avoid modifying the original point or manually constructing new points.
In some 6.034 labs, you'll need to make copies of an object (such as a <tt>Point</tt>) and modify each copy separately.  Here, you'll implement a function <tt>get_neighbors</tt> that takes in a 2D point (represented as a <tt>Point</tt> object).  In the function, use the <tt>.copy()</tt> method to create and return a list of the input point's four neighbors: the four points that neighbor the input point in the four coordinate directions.  By using the <tt>.copy()</tt> method, you can avoid modifying the original point or manually constructing new points.
Line 239: Line 296:
''Debugging hint'': If your answer looks the same as the expected answer but the tests aren't passing, make sure you're not creating new <tt>Point</tt>s or modifying the original! The tester checks for this!
''Debugging hint'': If your answer looks the same as the expected answer but the tests aren't passing, make sure you're not creating new <tt>Point</tt>s or modifying the original! The tester checks for this!
-
==== Using the "key" argument ====
+
=== Using the "key" argument ===
You've used <tt>sorted</tt>, and you're probably already familiar with using <tt>min</tt> and <tt>max</tt> to find the smallest or largest element of a list.  The <tt>key</tt> argument is a powerful tool for sorting objects based on a specific attribute (such as a point's Y coordinate) and finding the "smallest" or "largest" object based on a specific attribute.
You've used <tt>sorted</tt>, and you're probably already familiar with using <tt>min</tt> and <tt>max</tt> to find the smallest or largest element of a list.  The <tt>key</tt> argument is a powerful tool for sorting objects based on a specific attribute (such as a point's Y coordinate) and finding the "smallest" or "largest" object based on a specific attribute.
Line 254: Line 311:
  def sort_points_by_Y(list_of_points):
  def sort_points_by_Y(list_of_points):
-
 
Second, use <tt>max</tt> with the <tt>key</tt> argument to write a function that takes in a list of 2D points (represented as <tt>Point</tt> objects) and returns the point that is furthest to the right (that is, the point with the largest X coordinate), again without modifying the original list.  You may assume that no two points have the same X coordinate.  This can be done without sorting the list.
Second, use <tt>max</tt> with the <tt>key</tt> argument to write a function that takes in a list of 2D points (represented as <tt>Point</tt> objects) and returns the point that is furthest to the right (that is, the point with the largest X coordinate), again without modifying the original list.  You may assume that no two points have the same X coordinate.  This can be done without sorting the list.
Line 260: Line 316:
  def furthest_right_point(list_of_points):
  def furthest_right_point(list_of_points):
-
== Survey ==
+
= Survey =
-
todo add prog. exp; double-check with lab Qs
+
We are always working to improve the class, so most labs will have at least one survey question at the end to help us with this.
-
 
+
-
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 (as long as you answer the ones that are required).  
+
Please answer these questions at the bottom of your <tt>lab0.py</tt> file:
Please answer these questions at the bottom of your <tt>lab0.py</tt> file:
 +
 +
* <tt>PROGRAMMING_EXPERIENCE</tt>: How much programming experience do you have, in any language?
 +
::A. No experience (never programmed before this semester)
 +
::B. Beginner (just started learning to program, e.g. took one programming class)
 +
::C. Intermediate (have written programs for a couple classes/projects)
 +
::D. Proficient (have been programming for multiple years, or wrote programs for many classes/projects)
 +
::E. Expert (could teach a class on programming, either in a specific language or in general)
* <tt>PYTHON_EXPERIENCE</tt>: How much experience do you have with Python?
* <tt>PYTHON_EXPERIENCE</tt>: How much experience do you have with Python?
-
:: A. No experience (never used Python before this semester)
+
::A. No experience (never used Python before this semester)
-
:: B. Beginner (just started learning, e.g. took 6.0001)
+
::B. Beginner (just started learning, e.g. took 6.0001)
-
:: C. Intermediate (have used Python in a couple classes/projects)
+
::C. Intermediate (have used Python in a couple classes/projects)
-
:: D. Proficient (have used Python for multiple years or in many classes/projects)
+
::D. Proficient (have used Python for multiple years or in many classes/projects)
-
:: E. Expert (could teach a class on Python)
+
::E. Expert (could teach a class on Python)
* <tt>NAME</tt>: What is your name? (string)
* <tt>NAME</tt>: What is your name? (string)
Line 283: Line 344:
* (optional) <tt>SUGGESTIONS</tt>: What specific changes would you recommend, if any, to improve this lab for future years? (string)
* (optional) <tt>SUGGESTIONS</tt>: What specific changes would you recommend, if any, to improve this lab for future years? (string)
-
== When you're done ==
+
= 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.
+
Remember to run the tester!  The tester will automatically upload your code to the 6.034 server for grading and collection
 +
 
 +
Because the coding section of Lab 0 is optional, the online tester will only run three tests.  For future labs, the online tests will also test the functions you write.
-
== FAQ ==
+
= 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.
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].
+
If you have a question or a bug report, send an e-mail to [mailto:6.034-2016-staff@mit.edu 6.034-2016-staff@mit.edu].
Line 300: Line 363:
Q: When I submit to the online tester, it hangs for a while and/or eventually prints a stack trace ending in '''httplib.BadStatusLine: ' ' '''
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: If you're using Windows, review the [[#Python|Python section]] and make sure you're using a compatible version of Python.  If that doesn't solve the problem, contact a TA.
+
A: If you're using Windows, review the [[#Python|Python section]] and make sure you're using a compatible version of Python.  If you're not using Windows, or if that doesn't solve the problem, contact a TA.

Revision as of 01:07, 8 September 2016

Contents

This lab is due by Tuesday, September 13 at 10:00pm.

To work on this lab, you will need to get the code:

Your answers for this lab will go in the main file lab0.py.

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


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. 6.034 uses 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

First, create a directory for your 6.034 labs and navigate to it. For example:

mkdir ~/6.034-labs/
cd ~/6.034-labs/

Now, you can use Git to clone the lab code directly from the 6.034 Athena locker:

git clone /mit/6.034/www/labs/lab0

This will create a lab0 directory containing all the files you need for Lab 0. You can edit the code in this directory (for example, ~/6.034-labs/lab0/).

You can also ssh into athena.dialup.mit.edu to work on Athena from a different computer.

Using Git has a couple advantages:

  • Local version control: You can use Git to keep a local record of the changes you've made as you work on your lab, which makes it easy to revert to a previous implementation. You can learn more about using Git here (good for getting started) or from the official Git documentation. Using Git is not a requirement for 6.034, but you may find it helpful for tracking your files.
  • Easy updates: If we need to release an update to the lab code, you can run a simple "git pull" command to get the update instead of having to manually download the updated files.

If you are working on another computer with Python

Method 1: Git (recommended)

If you have Git, or want to install Git, you can clone the lab code from the 6.034 Athena locker. This method has a couple advantages:

  • Local version control: You can use Git to keep a local record of the changes you've made as you work on your lab, which makes it easy to revert to a previous implementation. You can learn more about using Git here (good for getting started) or from the official Git documentation. Using Git is not a requirement for 6.034, but you may find it helpful for tracking your files.
  • Easy updates: If we need to release an update to the lab code, you can run a simple "git pull" command to get the update instead of having to manually download the updated files.

On a command line, navigate to the folder in which you want to put all your 6.034 labs. Then, type this command to clone the lab0 code, replacing "username" with your Athena username:

git clone username@athena.dialup.mit.edu:/mit/6.034/www/labs/lab0

It will ask for your Athena password. After the files download, you will have a new directory called "lab0" containing the files for Lab 0.

Method 2: Download the files from a browser

Create a folder for the lab, then 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 (e.g. ~/6.034-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. (If you do not have a valid certificate, https://ai6034.mit.edu/labs will load but will display an error message telling you something is wrong with your certificate.) If the page doesn't 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 (or your preferred Python editor). The file contains a lot of incomplete statements for you to fill in with your solutions.

The first item 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.

Running 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" or "local" mode (the default), and "online" or "submit" mode. The offline tester runs some basic, self-contained internal tests on your code. The online tester runs more tests, some of which may be randomly generated, and uploads your code to the 6.034 grader for grading.

You can run both testers 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 (out of 5) on a lab if it passes all the tests. If your code fails a test, your grade will be 4 or below.

Your grade online will never decrease, so you should submit your code online 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 also makes it easy for the staff to look at it and help you.

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 you want to submit to the online tester, you can run

 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 it completes offline tests, saving you a few keystrokes.

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.

Python programming

Now it's time to write some Python!

(Note: The programming part of Lab 0 is optional; for full credit, you only need to fill in the survey questions and submit your code online. However, we highly recommend completing the programming part, as it will be good practice for future labs!)

Warm-up: Exponentiation

Using ** or math.pow(), write a function that takes in a number x and returns its cube. For example, cube(3) -> 27.

def cube(x):

Recursion

The nth Fibonacci number, Fn, is defined recursively as

Fn = Fn-1 + Fn-2

starting from F1 = F2 = 1, so that the sequence starts: 1, 1, 2, 3, 5, 8, ...

Using recursion, write a function that takes in a positive integer n and returns the nth Fibonacci number:

def fibonacci(n):

We recommend writing your functions so that they raise nice clean errors instead of failing silently or messily when the input is invalid. For example, it would be nice if fibonacci rejected negative inputs right away; otherwise, you might loop forever. You can signal an error like this:

raise Exception("fibonacci: input must not be negative")

Or, better yet, you can signal a specific error type:

raise ValueError("fibonacci: 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.

Expressions as nested lists

Let's try a more interesting application of recursion. One way to measure the complexity of a mathematical expression is the depth of the expression describing it in Python lists using prefix notation. Prefix notation (as opposed to infix notation) just means that the operator comes first, followed by all of its operands (arguments). Although we won't be using prefix notation much in 6.034, you may encounter it in more advanced AI classes that use languages such as Lisp (Scheme, Clojure, etc) and PDDL. Expressions represented in prefix notation can also be much easier to parse, which is why we will use it in this problem.

For example,

x2 + y2 (infix notation)

is equivalent to

['+', ['expt', 'x', 2], ['expt', 'y', 2]] (prefix notation, with 'expt' representing exponentiation)

Each operator can have one or more arguments; for example, the operator '+' can be used to sum many numbers: ['+', 10, 20, 30, 40].


For this problem, we will define the expression depth of an expression based on the number of nested operations:

  • The expression depth of a variable or number (such as 'x') is 0.
  • The expression depth of an operation depends on the expression depths of all of its children (arguments). In particular, it’s one more than the maximum of the expression depths of its children. If you think of the expression as a tree, the expression depth is the height of the tree.

Using recursion, write a function that finds the depth of an expression:

def expression_depth(expr):

For example:

  • expression_depth('x') -> 0
  • expression_depth(['expt', 'x', 2]) -> 1
  • expression_depth(['+', ['expt', 'x', 2], ['expt', 'y', 2]]) -> 2
  • expression_depth(['/', ['expt', 'x', 5], ['expt', ['-', ['expt', 'x', 2], 1], ['+', 5, 2, 3, 'w', 4]]]) -> 4

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

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

Built-in data types

Here, we're going to practice working with strings, sets, lists, and tuples, and using the Python keywords len and sorted. If you're unfamiliar with any of these, you can learn more about them using the help command (e.g. help(len)) or by searching the documentation at https://wiki.python.org/moin/.

Without using the keywords for or while, write a function compute_string_properties that takes in a string of lowercase letters and returns a tuple containing the following three elements:

0. The length of the string (using len)
1. A list of all the characters in the string (including duplicates, if any), sorted in REVERSE alphabetical order (using sorted with the reverse argument)
2. The number of distinct characters in the string (using a set)
def compute_string_properties(string):

For example:

  • compute_string_properties("hello") -> (5, ['o', 'l', 'l', 'h', 'e'], 4)
  • compute_string_properties("zebrafishes") -> (11, ['z', 's', 's', 'r', 'i', 'h', 'f', 'e', 'e', 'b', 'a'], 9)

If you have any questions about this (or any other problem), feel free to come to office hours! We'll be happy to help you figure it out. For Lab 0, we will also release an answer key demonstrating some useful shortcuts.


Next, we're going to practice using a dictionary.

Using a for loop, write a function tally_letters that takes in a string of lowercase letters and returns a dictionary mapping each letter to the number of times it occurs in the string:

def tally_letters(string):

For example:

  • tally_letters("hello") -> {'h': 1, 'e': 1, 'l': 2, 'o': 1}

If you want a challenge, you can try to write a one-line implementation using a dictionary comprehension.

Functions that return functions

In Python, a function can return any type of object: an int, a list, a user-defined object, ...or even another function! By defining your function to be returned inside the main function create_multiplier_function, implement create_multiplier_function to take in a multiplier m (a number and return a function that multiples its input by m.

def create_multiplier_function(m):

For example, after you implement this, you should be able to do the following:

>>> my_multiplier_fn = create_multiplier_function(5)  # define a function my_multiplier_fn that multiplies its input by 5
>>> my_multiplier_fn(3)
15
>>> my_multiplier_fn(-10)
-50

Objects and APIs

Many 6.034 labs include an API for a staff-defined object class. The API is a generally a section on the wiki that briefly describes the attributes and functions in the object class. We provide the API as an abstraction so that you don't need to learn the implementation details.

Here's an example:

Point API

A Point object represents a point in the 2D Cartesian plane. It has an X coordinate and a Y coordinate, each of which you can access and modify:

  • point.getX(): returns current X value
  • point.getY(): returns current Y value
  • point.setX(x): sets the X value to x, then returns the point
  • point.setY(y): sets the Y value to y, then returns the point

(where point is a Point instance)

You can also use the following (these are defined for most 6.034 object classes):

  • point.copy(), to return a deep copy of the point (that is, a copy that has all the same attributes as the original point)
  • == , to check whether two points have the same coordinates
  • print, to print out a human-readable version of a Point

Copying and modifying objects

In some 6.034 labs, you'll need to make copies of an object (such as a Point) and modify each copy separately. Here, you'll implement a function get_neighbors that takes in a 2D point (represented as a Point object). In the function, use the .copy() method to create and return a list of the input point's four neighbors: the four points that neighbor the input point in the four coordinate directions. By using the .copy() method, you can avoid modifying the original point or manually constructing new points.

def get_neighbors(point):

For example:

  • get_neighbors(Point(7,20)) -> [Point(6, 20), Point(8, 20), Point(7, 19), Point(7, 21)]

Note: In general, the order of elements in a Python list matters, but for this problem you may return the four neighbors in any order.

Debugging hint: If your answer looks the same as the expected answer but the tests aren't passing, make sure you're not creating new Points or modifying the original! The tester checks for this!

Using the "key" argument

You've used sorted, and you're probably already familiar with using min and max to find the smallest or largest element of a list. The key argument is a powerful tool for sorting objects based on a specific attribute (such as a point's Y coordinate) and finding the "smallest" or "largest" object based on a specific attribute.

The key argument takes a sorting function. For example, you could use sorted with key to sort a list of tuples in ascending order by their second elements:

>>> my_list = [(3, 100, 10000), (1, 999), (2, 50)]
>>> my_sorting_function = lambda tup: tup[1]  # [1] is the second element
>>> sorted(my_list, key=my_sorting_function)
[(2, 50), (3, 100, 10000), (1, 999)]
>>> my_list
[(3, 100, 10000), (1, 999), (2, 50)]  # unchanged

First, use sorted with the key argument to write a function that takes in a list of 2D points (represented as Point objects), then creates and returns a list of the points sorted in increasing order based on their Y coordinates, without modifying the original list. You may assume that no two points have the same Y coordinate.

def sort_points_by_Y(list_of_points):

Second, use max with the key argument to write a function that takes in a list of 2D points (represented as Point objects) and returns the point that is furthest to the right (that is, the point with the largest X coordinate), again without modifying the original list. You may assume that no two points have the same X coordinate. This can be done without sorting the list.

def furthest_right_point(list_of_points):

Survey

We are always working to improve the class, so most labs will have at least one survey question at the end to help us with this.

Please answer these questions at the bottom of your lab0.py file:

  • PROGRAMMING_EXPERIENCE: How much programming experience do you have, in any language?
A. No experience (never programmed before this semester)
B. Beginner (just started learning to program, e.g. took one programming class)
C. Intermediate (have written programs for a couple classes/projects)
D. Proficient (have been programming for multiple years, or wrote programs for many classes/projects)
E. Expert (could teach a class on programming, either in a specific language or in general)
  • PYTHON_EXPERIENCE: How much experience do you have with Python?
A. No experience (never used Python before this semester)
B. Beginner (just started learning, e.g. took 6.0001)
C. Intermediate (have used Python in a couple classes/projects)
D. Proficient (have used Python for multiple years or in many classes/projects)
E. Expert (could teach a class on Python)
  • NAME: What is your name? (string)
  • COLLABORATORS: Other than 6.034 staff, whom did you work with on this lab? (string, or empty string if you worked alone)
  • HOW_MANY_HOURS_THIS_LAB_TOOK: Approximately how many hours did you spend on this lab? (number or string)
  • (optional) SUGGESTIONS: What specific changes would you recommend, if any, to improve this lab for future years? (string)

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.

Because the coding section of Lab 0 is optional, the online tester will only run three tests. For future labs, the online tests will also test the functions you write.

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-2016-staff@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: If you're using Windows, review the Python section and make sure you're using a compatible version of Python. If you're not using Windows, or if that doesn't solve the problem, contact a TA.

Personal tools