# Quiz 2 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 2 -- 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: q2_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: `alternating_colors( graph, start )`

(TestProblem1)

`graph`

is a graph represented as a dictionary. Your task is to check
whether the graph can be colored using two colors with the constraint
that no two vertices that have an edge between them can have the same
color. `start`

is the vertex from which you should start coloring. You
can assume that all vertices in the graph are reachable from `start`

.

If the graph is not 2-colorable, your function should return an empty
dictionary `{}`

. If the graph is 2-colorable, your function should
return a dictionary of key:value pairs that represent a valid
2-coloring respecting the coloring constraint. Each key corresponds to
a vertex in the graph and each value is one of `'Red'`

or
`'Blue'`

. All vertices reachable from vertex `start`

should be
included as keys.

Examples of function invocation and return are given below the pictures of graphs.

```
alternating_colors({'A': ['B', 'F'],
'B': ['C', 'A'],
'C': ['D', 'B'],
'D': ['C', 'E'],
'E': ['D', 'F'],
'F': ['A', 'E']}, 'A')
```

could return
`{'A': 'Red', 'B': 'Blue', 'C': 'Red', 'D': 'Blue', 'E': 'Red', 'F': 'Blue'}`

or a different valid coloring with `'Red'`

and `'Blue'`

interchanged.

```
alternating_colors({'A': ['B', 'E'],
'B': ['C', 'A'],
'C': ['D', 'B'],
'D': ['C', 'E'],
'E': ['A', 'D']}, 'A')
```

should return `{}`

since there is no valid coloring.

```
alternating_colors({'A': ['B'],
'B': ['A', 'C'],
'C': ['B', 'D'],
'D': ['C', 'E', 'F'],
'E': ['D'],
'F': ['D', 'G', 'H', 'I'],
'G': ['F'],
'H': ['F'],
'I': ['F']}, 'A')
```

could return
```
{'A': 'Red', 'B': 'Blue', 'C': 'Red', 'D': 'Blue', 'E': 'Red', 'F': 'Red',
'G': 'Blue', 'H': 'Blue', 'I': 'Blue'}
```

or a different valid coloring with `'Red'`

and `'Blue'`

interchanged.

```
alternating_colors({'A': ['B'],
'B': ['A', 'C'],
'C': ['B', 'D'],
'D': ['C', 'E', 'F'],
'E': ['D'],
'F': ['D', 'G', 'H', 'I'],
'G': ['F', 'H'],
'H': ['F', 'G'],
'I': ['F']}, 'A')
```

should return `{}`

since there is no valid coloring.

### Problem 2: `check_BST( btree, start )`

(TestProblem2)

Assume that you are given a binary tree. Your task is to write a function to check whether it is a Binary Search Tree (BST). Recall that a BST has the following property: Each vertex has a value and the value of any vertex in the left subtree has to be less than the value of the vertex and the value of any vertex in the right subtree has to be greater than the value of the vertex. You can assume all values in any given tree are unique.

We will use the same dictionary representation for a binary tree or BST that we used in Lecture 5.

```
extree = {'root': [22, 'A', 'B'],
'A': [14, 'C', 'D'],
'B': [33, 'E', ''],
'C': [2, '', ''],
'D': [17, '', ''],
'E': [27, '', '']}
```

Examples:

`check_BST({'root': [22, '', '']}, 'root')`

should return `True`

.

`check_BST(extree, 'root')`

should return `True`

. `extree`

corresponds
to the example in the picture above.

```
check_BST({'root': [22, 'A', 'B'],
'A': [14, 'C', 'D'],
'B': [33, 'E', 'F'],
'C': [2, '', ''],
'D': [17, '', ''],
'E': [27, '', ''],
'F': [45, 'G', ''],
'G': [32, '', '']},
'root')
```

should return `False`

, since vertex `G`

with value 32 is in the right subtree
of the vertex `B`

, which has the value 33. The BST property needs to hold
recursively throughout the tree, and it does not as shown below.

Note that in order to receive full credit, your code should work on binary trees with arbitrary depth, not for just the test cases.

### Problem 3: `pipe_cutting`

(TestProblem3)

You are tasked with buying plumbing pipes for a construction project. Your foreman gives you a list of the varying lengths of pipe needed. The local hardware store sells pipes in one fixed length but has a saw for you to cut up the pipes in any way you choose. Your job is to figure out the minimum number of stock pipes required to satisfy the list of requests, in order to save money and minimize waste.

Please implement `pipe_cutting(requests, stock_length)`

where
`requests`

is a list of pipe lengths needed for the project
and `stock_length`

is the length of the pipes you can purchase at Home
Depot. `pipe_cutting`

should return an integer giving the minimum
number of purchased pipes needed to satisfy the list of requests.

You can assume that all elements in `requests`

are positive numbers
that are no longer than the stock pipe length. So, in the worst case, it
will take a number of stock pipes equal to the size of the request list.
You do not need to report the cutting/division in the optimal
solution, just report the minimum number of stock pipes needed.

There are different ways of solving this problem. We recommend, but do not require, a recursive approach for which the hint below will be useful.

Hint: For any particular request, the request might be satisfied by choosing a left-over pipe length or cutting from any left-over pipe lengths, or by choosing to buy a new pipe and cutting it to length.

EXAMPLES:

`pipe_cutting([],8) = 0`

`pipe_cutting([7],7) = 1`

`pipe_cutting([7,6,4],10) = 2`

// eg, cuts are`[7],[6,4]`

`pipe_cutting([4,3,4,1,7,8],10) = 3`

// eg, cuts are`[4,4,1],[3,7],[8]`