Quiz 1 Resubmit

The questions below are due on Monday October 09, 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 1 Resubmit -- Fall 2017

If your Quiz 1 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, 10/9, 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.

You can use the files you downloaded for the in-class Quiz 1 or redownload the .zip file below, which contains all the files, test cases, etc., you need to complete the quiz 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: quiz1.zip

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

Each test case is worth one point for a total of 20 points. Your score will be computed from the number of tests you pass. If you pass all the tests for a problem, you'll receive full credit. If you pass 2 of the 5 tests, you'll receive 40% of the credit for the problem. 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. runs(L)

The procedure runs(L) examines the list L of numbers looking for sequences of consecutive numbers called runs. The output is a list, where each run of sequential numbers is combined into a sublist in the result. A run consists of two or more sequential numbers. If an element in L is not part of a run, it appears as-is in the result.

For this problem, you will only receive credit for a test case if it runs to completion in under 10 seconds on the server.

Examples:

  • runs([]) => []
  • runs([1, 3, 5]) => [1, 3, 5]
  • runs([1, 2, 4]) => [[1, 2], 4]
  • runs([1, 2, 4, 2, 2, 3, 4, 4, 5, 9]) => [[1, 2], 4, 2, [2, 3, 4], [4, 5], 9]

Problem 2. is_cousin(parent_db,A,B)

parent_db is a sequence of 2-element tuples of the form (1, 2) indicating that "person 1 is the parent of person 2". A person may have multiple parents, and parents may have multiple children.

Person A is the grandparent of person C if there exists a person B such that A is the parent of B and B is the parent of C.

People D and E are cousins if they share at least one grandparent but do not share any parents.

The procedure is_cousin(parent_db, A, B) should return a grandparent that A and B share if A and B are cousins or None if A and B are not cousins. You may assume that A and B are in the parent_db and that they both have some number of parents and grandparents.

For this problem, you will only receive credit for a test case if it runs to completion in under 10 seconds on the server.

Examples:

This is a graph showing the parent/child relationships encoded in parent_db below.

parent_db = [(1,10), (1,11), (2, 10), (2,12),
             (10,100), (10,101),
             (11,110), (11,111),
             (12,120),
             (120,1200)
            ]

is_cousin(parent_db, 100, 101) => None   # share parent
is_cousin(parent_db, 100, 120) => 2
is_cousin(parent_db, 1200, 120) => None  # 1200 is 1200's child
is_cousin(parent_db, 101, 110) => 1
is_cousin(parent_db, 111, 120) => None   # don't share grandparent

Problem 3. all_phrases(grammar, root)

A grammar is a collection of rules that describe the syntax of legal phrases in a language. We'll use a Python dictionary to describe the syntax rules, for example

{ "sentence": [["noun", "verb"], ["noun", "never", "verb"]],
  "noun":     [["pigs"], ["professors"]],
  "verb":     [["fly"], ["think"]]
}

The strings in the grammar are classified as either

  • nonterminals, strings that appear as keys in the grammar dictionary. In the grammar above, "sentence", "noun" and "verb" are nonterminals.

  • terminals, strings in the grammar that aren't nonterminals.

A phrase is a list of nonterminals and terminals.

The dictionary maps each nonterminal to a list of production rules that describe the possible ways the nonterminal can be expanded into a (sub)phrase. You may assume that each phrase in the production rules has a nonzero length. In the example grammar, the nonterminal "sentence" can be expanded into one of two phrases: ["noun", "verb"] or ["noun", "never", "verb"]

A phrase is legal if it's composed entirely of terminals and, starting with the given initial string, there's a sequence of productions that eventually yield the phrase. For example, if "sentence" is the root, ["pigs", "never", fly"] is legal since

"sentence" =>
["noun", "never", "verb"] =>
["pigs", "never", "verb"] =>
["pigs", "never", "fly"]

But ["think", "pigs"] or ["noun", "verb"] would not be legal phrases generated from "sentence".

Please write the procedure all_phrases(grammar, root), which should return a list of all possible legal phrases that can be produced by applying a sequence of productions to the initial nonterminal specified by root. The phrases may be in any order.

  • grammar is a dictionary describing the syntax of legal phrases.

  • root is a string specifying the starting point for the sequence of productions. If the string is a terminal, the returned list should contain a single one-word phrase consisting of the string. You may assume that root is one of the strings that appear in the grammar.

For this problem, you will only receive credit for a test case if it runs to completion in under 10 seconds on the server.

Examples:

grammar1 = {"noun": [["rock"], ["paper"], ["scissors"]]}

all_phrases(grammar1, "noun") => [["rock"], ["paper"], ["scissors"]]}
all_phrases(grammar1, "paper") => [["paper"]]

grammar2 = {
  "sentence": [["noun", "verb"], ["noun", "never", "verb"]],
  "noun":     [["pigs"], ["professors"]],
  "verb":     [["fly"], ["think"]]
}

all_phrases(grammar2, "sentence") =>
     [["pigs", "fly"], ["pigs", "think"],
      ["professors", "fly"], ["professors", "think"],
      ["pigs", "never", "fly"], ["pigs", "never", "think"],
      ["professors", "never", "fly"], ["professors", "never", "think"]]


all_phrases(grammar2, "noun") => [["pigs"], ["professors"]]

all_phrases(grammar2, "fly") => [["fly"]]