Quiz 1 Practice Quiz
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.
When you have tested your code sufficiently on your own machine, submit your
quiz.py by clicking on "Choose File", then clicking the
button to send the file to the 6.009 server. The server will run the tests and
report back the results below.
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
function will provide a concise summary of built-in operations on data
help(set)) or information about the arguments for the
built-in functions (e.g.,
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
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.
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 + ilist = ilist. In contrast, for
ilist=[1,1,2], the answer is (1,1) because we can use ilist +
ilist = ilist. Also, note that the list may have more than one
triple, but you should only return one.
(4,5) or (5,4).
(30,70) or (70,30)or
(20,50) or (50,20)or
(20,30) or (30,20).
Note: Using a triply-nested for loop will likely time out on the server.
maximum_subsequence( ilist, is_circular=False )
Given a list of integers
ilist and the boolean
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.
(2,4)because the maximum subsequence is
[2,-1,3] = 4. Note that is_circular is False in the invocation.
(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_circularhad been False, the answer would be
(0,3)because the maximum subsequence that does not wrap around is
[4,-3,5,1] = 7.
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). Return the path as a list of coordinate tuples (row,
column). If there is no path, return None.
find_path([[0,1,0],[0,1,0],[0,1,0]]) should return
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.