Quiz 2 Resubmit

The questions below are due on Monday November 06, 2017; 10:00:00 PM.


You are not logged in.

If you are a current student, please Log In for full access to the web site.
Note that this link will take you to an external site (https://oidc.mit.edu) to authenticate, and then you will be redirected back to this page.

6.009 Quiz 2 Resubmit -- Fall 2017

If your Quiz 2 doesn’t pass all the tests or you want to revise your earlier answers, we invite you to continue to work on the quiz over the weekend and resubmit using the submit form on this page. The deadline for resubmissions is Monday, November 6, at 10pm; resubmissions after the deadline will not be regraded.

In order to request a regrade for a question, you will have to submit corrected code that passes all the tests for the question and explain in Python comments your bug or the lack of functionality in your original solution. Also please indicate whether you believe this to be a large or a small change and explain your reasoning. That will help us award partial credit more efficiently and correctly. Over the following days, the staff will review your new code and award partial credit for any additional tests that you pass.

Example Large changes:

  • Changing data representation (that require code changes in multiple places)
  • Changes to control structure: e.g., add recursive case; add handling of return from recursion
  • Original code had "right idea"; new code completes the implementation of that original "idea". This is a large change.
  • Accumulation of multiple small changes for the problem

Example Small changes:

  • Fix to iteration range/termination line (e.g., to fix ending one element too soon)
  • An edit to a base case return value
  • An edit to a base case check
  • Changing nested list expressions to add/remove a level of list (e.g., return [[root]] instead of [root])

In general, if you are seeking credit for a "Small" change then you should seek to revise your code for submission making changes to the fewest lines of code that you can. If you wish to refactor your code for clarity (which we applaud!) you should do that on your own later, after resubmitting a minimally-changed version requesting "Small" change credit. (Of course, if you are making a "Large" change, you are welcome to refactor as that will not affect "Large" change credit.)

NOTE: test.py in quiz2.zip has been updated. Specifically, TestProblem2.test_06 has been updated to grant credit if all of test_01 through test_05 succeed in Problem 2. You can redownload the .zip file below, which contains all the files, including the revised test cases, etc., you need to complete the quiz resubmission using your own machine. When unzipped it will create its own directory with the quiz’s files. The instructions follow below. You’ll be editing quiz.py to add the code requested by the instructions.

Download: quiz2.zip (Revised 11/5 at 2:10pm)

Submission

When you have tested your code sufficiently on your own machine, submit your modified quiz.py below by clicking on "Choose File", then clicking the Submit button to send the file to the 6.009 server. To receive credit you must upload your code before the timer expires.

The server will run the tests and report back the results below but be aware that the server may be backlogged at the end of the quiz session. Once the server has indicated that your submission is queued to be checked, you're all set -- your submission has been accepted as on time and you don't need to wait for the results to be reported.

 No file selected

Instructions

This quiz assumes you have Python 3.5 (or a later version) installed on your machine.

This quiz is closed-book and closed-Internet -- you are only allowed to access the quiz page on the 6.009 website and the material provided in the .zip file. You are not allowed to access other information on your laptop or on the web. When you unzip the .zip file, you'll find library.pdf, which includes the chapters 1-4 of the Python Library Reference -- they cover the built-in functions (Chap. 2) and built-in data types (Chap. 4). Note that Python's built-in help function will provide a concise summary of built-in operations on data types (e.g., help(set)) or information about the arguments for the built-in functions (e.g., help(sorted)).

Proctors will be available to answer administrative questions and clarify specifications of coding problems, but they should not be relied on for coding help.

As in the labs, test.py can be used to test your code in quiz.py. Each of the three problems has a unit test: TestProblem1, TestProblem2, etc. Remember that you can run tests for a specific problem like so

python3 test.py TestProblem1

This quiz is worth 20 points, based on 20 test cases. Your score will be computed from the number of tests you pass. If you pass all the tests, you'll receive full credit. If you pass 15 of the 20 tests, you'll receive 75% of the credit for the quiz (i.e., 15 points). Note that to pass some of the tests in the time allotted, your solution may have to be reasonably efficient.

Please do not import any Python modules to use as part of your solutions -- quizzes with import statements (or their equivalent!) will be given grades of 0.

You do not have to include doctests or detailed comments in your code.

Having your code check for a specific input (called "hard coding") and then return a specific result is okay only for the base cases in recursion. Solutions that look for specific test case arguments other than base cases are disallowed and will receive no credit.


Problem 1. Inequal-a-tree: truth_for_all(tree)

An "inequal-a-tree" data structure is a binary tree where the leaves of the tree are integers, but the nodes are an 'inequality' indicator, either the string '>' (greater than) or '<' (less than), which makes the claim that all integers in the left branch of the inequal-a-tree satisfy the indicator with respect to all values in the right branch of the inequal-a-tree.

We will represent inequal-a-trees as a tuple, where the first element is the string '<' or '>'; the second element is the left branch of the inequal-a-tree and can be either an integer or another inequal-a-tree; and the third element is the right branch of the inequal-a-tree and again can be either an integer or another inequal-a-tree. Six example inequal-a-trees are shown below:

x1 = ('<', 1, 2)
x2 = ('<', 1, 1)
x3 = ('>', 1, 2)
x4 = ('<', ('>', 4, 3),
           ('>', ('>', 7, 5), 2))
x5 = ('<', ('>', 4, 3),
           ('>', ('>', 7, 6), 5))
x6 = ('>', ('>', 10, 5), 6)

Write a function true_for_all that takes an inequal-a-tree as an input and returns True or False, based on whether or not the inequal-a-tree relationships and values throughout the inequal-a-tree hold true, as claimed by the inequality indicators and values in that tree.

For the examples above:

true_for_all(x1) ==> True
true_for_all(x2) ==> False   # 1 is not < 1
true_for_all(x3) ==> False   # 1 is not > 2
true_for_all(x4) ==> False   # 3 is not < 2
true_for_all(x5) ==> True
true_for_all(x6) ==> False   # 5 is not > 6

Problem 2. assign_cities(L, N)

We wish to send a message to N different cities, numbered 1 through N. There are N carrier pigeons, each of whom has a set of cities that they are able to fly to. A legal assignment is one where 1) there's exactly one pigeon assigned to every city, and 2) no pigeon is assigned a city they aren't able to fly to.

assign_cities(L,N) takes an N-element list L of sets where L[j] is the set of cities that pigeon j is able to fly to. N is the number of cities.

assign_cities should return None if there is no legal assignment, otherwise it should return an N-element list whose jth element is the number of the city assigned to pigeon j.

Examples:

  • assign_cities([{3}, {1}, {2}], 3) ==> [3, 1, 2]
  • assign_cities([{1,2,3}, {1,2,3}, {1,2,3}], 3) ==> [1, 2, 3]
  • assign_cities([{1,2,3}, {1,2}, {1}], 3) ==> [3, 2 ,1]
  • assign_cities([{1,2}, {1,2}, {1,2}], 3) ==> None
  • assign_cities([set(), {1,2,3}, {2,3}], 3) ==> None

Problem 3. circularly linked lists - CLLN class

Infinite Data Structures, Inc. is developing their newest data structure, and needs your help. Their novel idea is a "circularly linked list" where each node has a value (called val) and a next node pointer, but also has a prev pointer to the previous node. Importantly, there is no first or last node in the circularly-linked list: what would ordinarily be thought of as the first and last nodes also link to each other, completing the circularly linked list.

The company has only partially completed their implementation: you are asked to complete the methods for the circularly-linked list node (CLLN) class that implements this idea, consistent with the docstring/doctest specifications in quiz.py.

Some examples are considered below to convey the idea. A circularly linked list consisting of one node only might be as pictured in Fig. 1, where the next pointer is shown as a solid blue arrow, and the prev pointer is a dashed blue arrow.

single node with value 77

Such a node might be created using the interaction below. A __repr__ method is already implemented that shows a string representation of an entire circularly linked list, <CLLN 77> as below. A __str__ method is also available, that provides a printed representation of the identify of an individual CLLN node, e.g., <CLLN-id-52932960>.

>>> x = CLLN(77)
>>> x
<CLLN 77>
>>> print(x)
<CLLN-id-52932960>

A more interesting example is shown in Fig. 2, where again next pointers are shown in solid blue, and prev pointers are shown in dashed blue. In this case, the circularly linked list consists of four nodes. We have two pointers, x and y, to different nodes within this circularly linked list. If we show the list with respect to these different nodes, the resulting view will be different:

>>> x = CLLN(1)
>>> y = x.after(2).after(3).after(4)
>>> x
<CLLN 1 2 3 4>
>>> y
<CLLN 4 1 2 3>

four nodes linked with next and prev pointers

Following are some examples of a (working) implementation, to give a sense of the methods of the CLLN class:

>>> x = CLLN(77)
>>> y = x.after(99)
>>> x
<CLLN 77 99>
>>> y
<CLLN 99 77>
>>> y.after(100).after(101)
<CLLN 101 77 99 100>
>>> x
<CLLN 77 99 100 101>
>>> x.prev
<CLLN 101 77 99 100>

We can remove a node from a CLLN:

>>> x = CLLN(1)
>>> x.after(2).after(3).after(4)
>>> x
<CLLN 1 2 3 4>
>>> gone = x.next.remove()
>>> x
<CLLN 1 3 4>
>>> gone
<CLLN 2>

We can map a function over the values in a CLLN, producing a new CLLN with the result of the function applied to the corresponding value in the original CLLN.

>>> x = CLLN(1)
>>> x.after(2).after(3)
>>> x
<CLLN 1 2 3>
>>> x.map(lambda v: v*v)
<CLLN 1 4 9>
>>> x
<CLLN 1 2 3>

Finally, we can get a reversed version of a CLLN, which is a new circularly linked list with elements from self in reversed order:

>>> x = CLLN(1)
>>> x.after(2).after(3).after(4)
>>> y = x.reversed()
>>> y
<CLLN 4 3 2 1>
>>> x
<CLLN 1 2 3 4>

Several methods of CLLN have already been written and are provided to you in quiz.py; it will be very helpful to you to understand and potentially use some of those methods as you complete this problem. Your task is to complete the implementation of the CLLN class, including to implement the following methods consistent with the docstring/doctest specifications for each of these methods in quiz.py.

  • CLLN.after(self, val)
  • CLLN.remove(self)
  • CLLN.__len__(self)
  • CLLN.map(self, f)
  • CLLN.reversed(self)

Debugging note: Your score for this problem will be based on passing tests in test.py. However, you can also run "python3 quiz.py" to run quiz.py as a script to run the doctests in the CLLN class to aid in your debugging.