Note: to do this homework, you should download Homework3.zip, then unzip it, edit the files, rezip, and submit that zipped file to Autolab.
Include your name, AndrewID, and section clearly on the top of each file in your assignment.
Place all your solutions in a single file ZIP file (extension.zip). Once again, start with Homework3.zip. No other file formats will be accepted. You need to start by downloading a ZIP file that contains a template (a file ending in .py) for each problem in this homework.
Show your work. Correct answers without supporting calculations will not receive full credit.
How to submit:
Your submission is not completed until you see that text!!!
We want to gauge how much time you are spending in each homework and how you are using your resources. So, please answer the following questions:
How much time did you spend on this homework assignment? Please report actual time on task, not counting Facebook excursions, a quick World of Warcraft expedition, or any other non-assignment time.
What resources did you use to complete your assignment? Please list all that apply.
What do these functions do? State what each of the following functions does in general, in just a few words of plain English. You must identify the general pattern, and should not state line-by-line what each step of the function does. Here is an example of the kind of answer we're looking for:
Note: these are not necessarily the best algorithms for solving these particular problems. Often, there are clearer and/or faster ways to achieve the same result.
Example
def mysteryExample(x,y):
# assume x and y are positive integers
while x >= y:
x -= y
return x
Answer: for positive integers (the assumed input), this function is equivalent to (x % y). For full credit, you would have to provide a small explanation why this is true. You would receive zero credit for the following answer: the function loops while x is greater than or equal to y, subtracting y from x on each iteration of the loop, and then returns the value of x. This is entirely correct on a "line-by-line" level, but we want you to think more generally in terms of the higher level algorithm that is being implemented and so no credit would be awarded for this answer.
Problem 1.A (3 points)
def mysteryA(x):
# assume x is a positive integer
c = 0
while (x > 0):
c += x % 10
x /= 10
return (c == 1)
Problem 1.B (3 points)
def mysteryB(f):
# assume f is a positive floating-point number
g = 1
b = 1
while (g < f):
if (abs(g*g-f) < abs(b*b-f)):
b = g
g += 0.001
return b
Problem 1.C (4 points)
def mysteryC(s1, s2):
# assume s1 and s2 are strings
m = 0
i = 0
while (i < min(len(s1), len(s2))):
if (s1[i] == s2[i]):
m += 1
i += 1
return m
A palindrome is a word, sentence, or sequence of characters (can be
digits)
that can be read the same way right-to-left or left-to-right. For
example, the English word "kayak" is a palindrome. Write a Python
function called isPalindrome that takes a string as a parameter, and returns True if that string is a palindrome, False otherwise.
You want to buy a new car, and you are thinking about two alternatives, car A and car B. You like both cars, and you are considering keeping whichever one you buy for many years to come. As a result, you want to evaluate the total cost of ownership of both cars over many years. Car A costs $15,000, whereas car B costs $18,000. Car A gets 25 miles per gallon, whereas car B gets 33 miles per gallon. You estimate that you will drive about 12,000 miles each year, and that gas price is going to be around $2.70 per gallon for the foreseeable future. The maintenance cost of a car can be estimated as follows: there is a fixed cost of $300 per year for each car, plus a variable cost proportional to the age of the car. For car A, the variable cost is 15% of the fixed maintenance cost per year; for car B it is 10% per year.
Write a Python function called compareCars
that takes an integer number of years as a parameter, and prints a
table with the total ownership cost of each car for each year, starting
from year 0 which represents the moment when you purchase the car.
Using the table generated by your function, which car would you buy if you plan on keeping it for 5 years? 10 years?
Write a Python function called squareRoot
that
takes a positive floating-point number as its input, and calculates the
square root of that number using binary search. The result should be a
floating point number, and its value should be accurate at least up to
the fifth decimal digit.
Write a Python function
called numberGuessingGame that takes two integer
numbers as parameters, and interactively plays the "high/low" number guessing
game with you. In this game you will think of a number, and the computer will
have to guess it. The input parameters represent upper and lower bounds (both
inclusive) of the number that you want the computer to guess.
Are you familiar with the "twenty questions" game? In this game, a player (the answerer) picks a subject without revealing it. The other player (the questioner) can ask questions for which the answer is either "yes" or "no." The goal of the questioner is to guess the subject based on the answers provided by the answerer, asking no more than 20 questions. You can learn more about this game at http://en.wikipedia.org/wiki/Twenty_Questions.
Here, we will focus on a smaller version of this game, which we will call the "four questions" game. As the name suggests, the questioner can ask no more than 4 yes/no questions. Additionally, the answerer can pick the subject to be guessed from a limited list of things. That list is known to the questioner as well.
This game can be modeled with a structure that computer scientists call decision tree. A decision tree explicitly represents all the choices that can be taken depending on the answers to questions. The questions themselves depend on previous answers.
For example, imagine that our goal is to guess a city from the following list: Atlanta, GA; Chicago, IL; Dallas, TX; Florence, Italy; London, England; Los Angeles, CA; Miami, FL; Ottawa, Canada; Rome, Italy; Shanghai, China; Sydney, Australia; Tokyo, Japan; Vancouver, Canada; Venice, Italy.
Figure 1 (download PDF) shows a decision tree that can identify a city from that list in 4 steps or less. An alternative representation of the same tree in plain text is provided here:
Is it in North America?
yes: Is it by the sea?
yes: Is it on the West Coast?
yes: Is it in Canada?
yes: The city you chose is Vancouver.
no: The city you chose is Los Angeles.
no: The city you chose is Miami.
no: Does it have cold winters?
yes: Is it by a lake?
yes: The city you chose is Chicago.
no: The city you chose is Ottawa.
no: Is it in Georgia?
yes: The city you chose is Atlanta.
no: The city you chose is Dallas.
no: Is it the capital of a country?
yes: Is it in Europe?
yes: Is it in England?
yes: The city you chose is London.
no: The city you chose is Rome.
no: The city you chose is Tokio.
no: Is it in Italy?
yes: Is it by the sea?
yes: The city you chose is Venice.
no: The city you chose is Florence.
no: Is it in China?
yes: The city you chose is Shanghai.
no: The city you chose is Sydney.
Notice how a particular question could be more or less appropriate depending on its position in the tree. To be mostly effective, a question should try to split up the set of cities roughly in half. In this way, the subsets of remaining cities to choose from get smaller and smaller very quickly on each step. Think about the opposite extreme: if we keep asking questions that single out only one city at a time, it may take up to 13 questions (the size of our list minus one) to finally get to the right city. For example, if we asked the question "Is it the capital of a country?" on the first subset of North American cities (Atlanta, Chicago, Dallas, Los Angeles, Miami, Ottawa, Vancouver), we would get a very uneven split, as Ottawa is the only capital in that set. Thus, that would not be a very informative question. On the other hand, the same question is very good when applied to the other subset (Florence, London, Rome, Shanghai, Sydney, Tokyo, Venice), because roughly half of those cities are indeed country capitals.
Your task. Implement a program in Python that can play the 4-questions game in the role of questioner. You, the human player, will be the answerer.
Part 1 (10 points). Implement the game using the list of cities as provided above, and the question structure as provided above.
Part 2 (10 points). Design a new instance of this game, using a list of subjects of your choice, and your own set of questions. The list of subjects should contain at least 12 items. You don't need to re-implement the game in Python, but you should write your list of subjects and the decision tree that your program is supposed to model. To type the decision tree, you should use a plain text format similar to the example provided above.
In week 1, we learned that binary search requires O(logN) steps. Now
that we have automated the algorithm, we can automatically check this
theory. Make a function, numberGuessingGameRangeCount, which is similar to your numberGuessingGame except that it is non-interactive (no input from the user). Instead, it should take three numbers, the low, the hi, and the actual answer, and it should return the number of guesses required to play the game given those values. Next, write a function, numberGuessingGameMaxCount, that takes only one value, the range max, which we will call N, and always uses 1 as the range min, and calls numberGuessingGameRangeCount
for every single value from 1 to N, finally returning the maximum count
that it found. Finally, using graph paper, plot two functions on the
same graph: the first function is numberGuessingGameMaxCount(N),
the second is log2(N). Be sure to get to fairly large values of N
(2**20, say). How do these two graphs compare? Do they prove our
theory, or just strongly support it, or in fact do they disprove it?
Explain.