# Quiz 1

The questions below are due on Wednesday March 06, 2019; 09:30:00 PM.

You are not logged in.

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.
Submissions to the quiz are no longer allowed. If there was an extenuating circumstance that prevented you from submitting on time, please send e-mail to devadas@mit.edu within 15 minutes of the end of your quiz, containing your code and an explanation of the issue. Otherwise, if you are looking to complete a resubmission, please go to the Resubmission Page. Resubmissions will be accepted starting Friday 8AM, and are due Sunday 10PM.

# 6.009 Quiz 1 -- Spring 2019

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.

### 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. You may not discuss the quiz with other students -- even after you complete the quiz and/or complete any regrade submission -- until regrades have been completed for all students and final quiz grades assigned (at the end of next week), because many students will still be working on regrades or other/conflict offerings of the quiz.

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


This quiz is worth 15 points; these points will ultimately translate to an equivalent grade for the quiz per the published 6.009 grading policy. Your quiz points score will be based primarily on performance of your last code submitted during the quiz, tested against some number of test cases for each problem. However, points will also be lost in other circumstances:

• You must not not import any Python modules to use as part of your solutions -- quizzes with import statements (or their equivalents!) will be given grades of 0.

• Having your code check for a specific input (called "hardcoding") and then return a specific result is okay only for the base cases in iteration or recursion. Problem solutions that look for specific test case arguments other than base cases are disallowed and will receive no credit.

• You do not have to include doctests or detailed comments in your code: we will not deduct any points for lack of comments, but we encourage commenting as general good practice.

Aside from these special point deductions above, your quiz score will be based on the number of points your last submitted code earns across all problems on the quiz. For each problem, if you pass all of the tests for that problem, you will receive the full base points for the problem (e.g., 5 points if the problem is a 5-point problem). If you pass 8 of 10 test cases for the problem, you'll receive 80% of the base credit for that problem; thus, for a problem worth 5 points, your points for that problem would be 4.0. The number of points each problem is worth is indicated at the start of the problem description below. Note also that to pass some of the tests within the server timeout allotted, your solution may have to be reasonably efficient.

For your own debugging, you are welcome to add test cases of your own to test.py (but note that any tests you add will not be run on the server).

Note that in order to pass some of the test cases, your code will need to be efficient enough to run to completion within the specified timeout (15 seconds on the server to run all test cases in each problem).

Note about maximizing partial credit: Remember that we offer a resubmission process, which will open on Friday at 8 AM, which is your chance to finish any questions that you are unable to complete now. Resubmission grades are determined by how complete your code turned in now looks. Therefore, consider leaving incomplete solutions, pseudocode, or even just comments in English, even if one of your functions passes no tests.

### Problem 1. get_mode(data) (5 points)

Given a list of numbers between 0 and 99 (inclusive) named data, return the statistical mode of this list. The statistical mode is defined to be the value that appears most often. If there are multiple values that appear most often, then return the highest of those values. The input is guaranteed to be a nonempty list of numbers between 0 and 99 (inclusive).

Examples:

1. If data = [3, 76, 42, 3], the correct answer would be 3 because that number occurs twice.

2. If data = [1, 94, 36, 1, 36], the correct answer would be 36 because although 36 and 1 both appear twice, 36 has a greater value than 1.

### Problem 2. find_anagram_groups(words, N) (5 points)

Write a function find_anagram_groups(words, N) that, given a list of lowercase words containing letters a-z, searches through the list until it finds N words that are anagrams of each other. These words form an anagram group of size N. The function should return the smallest index i such that words[:i+1] contains an anagram group of size N. If there is no anagram group of size N (or larger), the function should return None.

Two words are anagrams if one can be produced from the other by reordering letters. For example, "list", "silt", and "slit" are anagrams of each other, and "sit" is not.

Examples:

1. find_anagram_groups(["list", "silt", "list"], 3) returns 2
2. find_anagram_groups(["crate", "word", "filler", "react", "trace"], 2) returns 3
3. find_anagram_groups(["cat", "act", "tab", "bat", "ten"], 3) returns None
4. find_anagram_groups(["petal", "tale", "late", "plate"], 2) returns 2

### Problem 3. find_duplicates(stream) (5 points)

Given a stream of data (a Python container) that contains nested containers and strings, return a set of all duplicate strings present in the data structure. If there are no duplicate strings, return an empty set. For the purposes of this problem, we will assume that Python containers are limited to the following data structures: lists, tuples, sets, and dictionaries. In the case of dictionaries, we'll be interested in looking for duplicates in both the keys and values.

(Hint: Consider what type of data structure each container might hold. In the case of dictionaries, for example, what are the possible data structures for keys? For values?)

(Second hint: The Python function isinstance will likely come in handy to test the data type of a value. It is used like isinstance(x, str) [to test if x is a string]. Other relevant type constants are list, dict, tuple, and set.)

For the purposes of this problem you may assume that the characters in a string will only be the lowercase letters a-z. Please note that you are free to add any helper functions or optional arguments to find_duplicates, in order to make your solution more concise.

Examples:

1. If stream = ["a", "b", "c", "a"], then find_duplicates should return: {"a"}
2. If stream = {"a": "b", "c": ["d", "e"]}, then find_duplicates should return: set()
3. If stream = (["one"], {"two", ("three", ("one", ("two",)))}), then find_duplicates should return: {"one", "two"}