Quiz 1 Practice Quiz

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 Practice Quiz 1 -- Fall 2017

Please download 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: q1_practice.zip

Submission

When you have tested your code sufficiently on your own machine, submit your modified quiz.py by clicking on "Choose File", then clicking the Submit button to send the file to the 6.009 server. The server will run the tests and report back the results below.

 No file selected

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: find_triple( ilist )

Find a triple of integers x, y, z in the list ilist such that x + y = z. Return the tuple (x, y). If the triple does not exist, return None. Note that x, y and z should be different elements of the list. For instance, for ilist=[1,5,2] the answer is None because we cannot use ilist[0] + ilist[0] = ilist[2]. In contrast, for ilist=[1,1,2], the answer is (1,1) because we can use ilist[0] + ilist[1] = ilist[2]. Also, note that the list may have more than one triple, but you should only return one.

Examples:

  • find_triple([4,5,9]) should return (4,5) or (5,4).
  • find_triple([20,40,100,50,30,70]) should return (30,70) or (70,30) or (20,50) or (50,20) or (20,30) or (30,20).
  • find_triple([6,11,7,2,3]) should return None.

Note: Using a triply-nested for loop will likely time out on the server.


Problem 2: maximum_subsequence( ilist, is_circular=False )

Given a list of integers ilist and the boolean is_circular, return a tuple of the start and end indices of the maximum subsequence in the list where the maximum subsequence is defined as the maximum sum of continuous integers in the list. If is_circular is True, imagine the list is circular. That is, after the end index comes the start index.

Examples:

  • max_subsequence([1,-5,2,-1,3]) should return (2,4) because the maximum subsequence is [2,-1,3] = 4. Note that is_circular is False in the invocation.
  • max_subsequence([1,-2,-3,4,5,7,-6]) should return (3,5) because the maximum subsequence is [4,5,7] = 16.
  • max_subsequence([4,-3,5,1,-8,3,1], True) should return (5,3) because the maximum subsequence is [3,1,4,-3,5,1] = 11. Notice that the elements correspond to indices 5, 6, 0, 1, 2 and 3. For this example, if is_circular had been False, the answer would be (0,3) because the maximum subsequence that does not wrap around is [4,-3,5,1] = 7.

Problem 3: find_path( grid )

grid is a two dimensional m by n grid, represented as a list of lists, with a 0 or a 1 in each cell. Find a path of ones starting at the top row (row 0) and ending at the bottom row (row n-1), where a valid move from cell (r,c) can go to: (r+1,c-1), (r+1,c) or (r+1,c+1). Return the path as a list of coordinate tuples (row, column). If there is no path, return None.

Examples:

find_path([[0,1,0],[0,1,0],[0,1,0]]) should return [(0,1),(1,1),(2,1)].

alt text

alt text

Examples:

  • find_path([[0,1,0,1],[1,0,0,1],[0,1,0,1],[0,0,1,0],[0,1,0,0]]) should return [(0,1),(1,0),(2,1),(3,2),(4,1)] or [(0,3),(1,3),(2,3),(3,2),(4,1)].

alt text

alt text

  • find_path([[0,1,0,1,0],[1,0,0,1,0],[0,1,0,0,0],[0,0,1,0,0],[0,0,0,0,1]]) should return None.

alt text

Note: In order to receive full credit, your code should be general enough to be used with arbitrary m and n, not just the test cases provided.