# 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.

### 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)]`

.

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)]`

.

`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`

.

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.