Quiz 3 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 3 -- 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
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.,
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 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.
Database Search (tests 1-12)
This question consists of three parts. You are given a database of scheduling information about a set of classes over a semester. We make the following assumptions about the schedule:
A class meets at most once on any given day.
Meetings last exactly 1 hour.
Meetings can only begin on the hour at 09:00, 10:00, ..., 16:00.
The semester consists of 15 weeks: Week
"2", ..., Week
All meetings occur in one of the following buildings:
Each day in the semester is identified by its
WEEK_NUMBER and its
DAY_OF_WEEK, e.g. the 5th Friday.
The database consists of two parts, the
default_db database and
default_db contains the original schedule
that is now outdated.
default_db is a list of weekly
entries. Each entry is itself a list of strings: a class name, a time
of day, a day of the week, and a building location. The time is the
hour at which the meeting starts, according to a 24-hour clock. These
meetings were originally scheduled to occur every week.
The following is a small example
default_db that contains three weekly entries.
[ ["6.009", "15", "Monday", "W36"], ["6.009", "14", "Friday", "Koch"], ["6.01", "10", "Tuesday", "Stata"], ]
update_db database contains updates to the original
schedule. There are two types of updates: ADDs and DELETEs. We
update_db as a list of updates. Each update is itself a
list of strings: an update type, a class name, a time, a day of the
week, a building location, and a week number. Unlike the weekly
default_db, each update in
update_db only gives
information for a specific day. Each ADD update refers to a meeting
that does not already exist in
default_db. Each DELETE update refers
to a meeting that exists in
Extending the example above, the following is an
contains two updates.
[ ["ADD", "6.009", "12", "Thursday", "Walker", "15"], ["DELETE", "6.009", "15", "Monday", "W36", "15"] ]
After updating the original schedule in
we see that our schedule should consist of the following meetings:
"W36"on every week except Week
In the following parts, you will implement methods to retrieve
information about the schedule. They require an implementation of the
build_rep() processes the two databases and
returns new representations of the information. The output of
build_rep() is passed into the other methods. You can choose
whatever representation you think will work best for the methods of
Parts A, B and C.
update_db databases will be provided as
build_rep(), but not the other methods. For your
convenience, you can look through raw text versions of the databases
resourcces/database/ folder. It might be useful to search these files
when debugging. We do not recommend printing the entire databases at
once, since they are quite large.
Part A: Tests (1-3)
For Part A you will implement the
get_near_classes() method to the
buildings, a list of buildings as strings
rep, the representation of
A list, in no particular order, of all classes that meet only in
the list of buildings given by
Using the above example,
get_near_classes(["Walker"], rep)should return
get_near_classes(["Walker", "W36", "Stata"], rep)should return
get_near_classes(["Walker", "W36", "Koch", "Stata"], rep)could return
["6.009", "6.01"]or the same set of classes in a different order.
Part B: Tests (4-8)
For Part B you will implement the
earliest_meeting() method which
retrieves the time of the earliest meeting in a given building on a
given day of the week across all weeks.
building, a string such as
day_of_week, a string such as
rep, the representation of
An integer earliest time (hour, such as
9), the earliest meeting
given by the combined database of classes, occurring on any week
day_of_week. If no meetings take place on
day_of_week in that building on any week, return
Using the tiny database in the example above,
earliest_meeting("Stata", "Tuesday", default_db, update_db) should
earliest_meeting("Stata", "Monday", default_db,
update_db) should return
Part C: Tests (9-12)
For Part C you will implement the
have_conflicts() method to the
class_list, a list of classes as strings
rep, the representation of
A Boolean (
False) indicating whether any two classes in
class_list conflict. Two classes conflict when they meet on the same
day of the week during the same week at the same time.
Using the above example,
have_conflicts(["6.009", "6.01"], rep) should return
k-Label Poker (tests 13-20)
In a deck of normal playing cards, each card has two labels, a rank
(1,2,...,K) and a suit (diamonds, spades, clubs, hearts), so
(K,spades) and (4,diamonds) are both possible cards. In our version of
poker, each card has
k different labels, where each label is a
positive integer 1,…,
L. Therefore, if
k = 4 and
L = 5, then
(1,1,1,2) and (2,1,5,1) are both valid cards.
k-label poker with hands of size
n. Repeat cards within a hand are
not allowed. In our version of poker, a straight happens if all of the
labels in the hand form a nondecreasing sequence. For example, if
L = 5, and
n = 3, then the hand
[(1,1), (1,2), (3,5)] would
be a valid straight since the sequence 1,1,1,2,3,5 is nondecreasing
[(3,5), (3,1), (2,2)] would not. Note that
(3,5)] is a different hand (and is not a straight) from
(1,2), (3,5)] (which is a straight).
Note that this problem has a very special definition of a straight that is different from the usual poker straight (if you happen to play poker). This specialness includes two unusual aspects: first, the labels for any given card in the hand must be non-descending; and second, the labels aggregated (in order) across all (ordered) cards in the hand must also be non-descending.
count_straights(k, L, n), where
k is the number
of labels for a given card,
L is the maximum integer label for any
n is the length of hand. Your function should return the
number of possible straights in hands of size
n where each card has
k labels of maximum value
L. Cards cannot be repeated in a
Performance hint: You will pass most of the tests with a brute-force search that generates all the hands and counts the number of straights, but may time out on some tests. It is not necessary to generate all possible hands to count straights, but if you find that difficult to reason about or code, try the brute-force method.
count_straights(2, 3, 4)
The possible cards are (1,1), (1,2), (1,3), ..., (3, 3).
We are considering hands of length 4. In this case, 5 straights are possible:
[(1,1), (1,2), (2,2), (2,3)] [(1,1), (1,2), (2,2), (3,3)] [(1,1), (1,2), (2,3), (3,3)] [(1,1), (2,2), (2,3), (3,3)] [(1,2), (2,2), (2,3), (3,3)]
count_straights(3, 5, 2)
The possible cards are (1,1,1), (1,1,2), (1,1,3), ..., (5,5,5).
We are considering hands of length 2. In this case, 205 straights are possible:
[(1,1,1), (1,1,2)] [(1,1,1), (1,1,3)] ... [(1,2,3), (4,4,5)] [(1,2,3), (4,5,5)] ... [(4,5,5), (5,5,5)]