1 COUNTING VOWELS
Assume s is a string of lower case characters.Write a program that counts up the number of vowels contained in the string s. Valid vowels are: 'a', 'e', 'i', 'o', and 'u'. For example, if s = 'azcbobobegghakl', your program should print:
Number of vowels: 5
For problems such as these, do not include raw_input statements or define the variable s in any way. Our automated testing will provide a value of s for you - so the code you submit in the following box should assume s is already defined. If you are confused by this instruction, please review L4 Problems 10 and 11 before you begin this problem set.
def isVowel(char):
v = "aeiouAEIOU"
if char in v:
return True
return False
cnt = 0
for e in s:
if(isVowel(e)):
cnt = cnt + 1
print "Number of vowels: " + str(cnt)2
COUNTING BOBS
Assume s is a string of lower case characters.
Write a program that prints the number of times the string 'bob' occurs in s. For example, if s = 'azcbobobegghakl', then your program should print
Number of times bob occurs is: 2
For problems such as these, do not include raw_input statements or define the variable s in any way. Our automated testing will provide a value of s for you - so the code you submit in the following box should assume s is already defined. If you are confused by this instruction, please review L4 Problems 10 and 11 before you begin this problem set.
#s = 'azcbobobegghakl'
cnt = 0
st = 0
ed = 3
while(ed <= len(s)):
c = s[st:ed]
if(c == 'bob'):
cnt = cnt + 1
st = st + 1
ed = ed + 1
print "Number of times bob occurs is: " + str(cnt)3
ALPHABETICAL SUBSTRINGS
Assume s is a string of lower case characters.
Write a program that prints the longest substring of s in which the letters occur in alphabetical order. For example, if s = 'azcbobobegghakl', then your program should print
Longest substring in alphabetical order is: beggh
In the case of ties, print the first substring. For example, if s = 'abcbcd', then your program should print
Longest substring in alphabetical order is: abc
For problems such as these, do not include raw_input statements or define the variable s in any way. Our automated testing will provide a value of s for you - so the code you submit in the following box should assume s is already defined. If you are confused by this instruction, please review L4 Problems 10 and 11 before you begin this problem set.
Note: This problem is fairly challenging. We encourage you to work smart. If you've spent more than a few hours on this problem, we suggest that you move on to a different part of the course. If you have time, come back to this problem after you've had a break and cleared your head.
#s = 'zyxwvutsrqponmlkjihgfedcba'
ans = ''
i = 0
cnt = 0
n = 0
t = s[0]
while(i < len(s)-1):
if(s[i] < s[i+1] or s[i] == s[i+1]):
t = t + s[i+1]
cnt = cnt + 1
else:
t = s[i+1]
cnt = 0
if(cnt > n):
ans = t
n = cnt
i = i + 1
if(n == 0):
ans = s[0]
print "Longest substring in alphabetical order is: " + str(ans)4
PROBLEM 2: PAYING DEBT OFF IN A YEAR
Now write a program that calculates the minimum fixed monthly payment needed in order pay off a credit card balance within 12 months. By a fixed monthly payment, we mean a single number which does not change each month, but instead is a constant amount that will be paid each month.
In this problem, we will not be dealing with a minimum monthly payment rate.
The following variables contain values as described below:
-
balance- the outstanding balance on the credit card -
annualInterestRate- annual interest rate as a decimal
The program should print out one line: the lowest monthly payment that will pay off all debt in under 1 year, for example:
Lowest Payment: 180
Assume that the interest is compounded monthly according to the balance at the end of the month (after the payment for that month is made). The monthly payment must be a multiple of $10 and is the same for all months. Notice that it is possible for the balance to become negative using this payment scheme, which is okay. A summary of the required math is found below:
Monthly interest rate = (Annual interest rate) / 12.0
Monthly unpaid balance = (Previous balance) - (Minimum monthly payment)
Updated balance each month = (Monthly unpaid balance) + (Monthly interest rate x Monthly unpaid balance)
Test Cases to Test Your Code With. Be sure to test these on your own machine - and that you get the same output! - before running your code on this webpage!
The code you paste into the following box should not specify the values for the variables balance or annualInterestRate - our test code will define those values before testing your submission.
# Paste your code into this box
t = balance
monthlyInterestRate = annualInterestRate / 12
monthlyPayment = 0
unpaidPayment = 0
flag = 0
for e in range(100):
balance = t
monthlyPayment = (e+1) * 10
for f in range(12):
unpaidPayment = balance - monthlyPayment
balance = unpaidPayment + unpaidPayment * monthlyInterestRate
if unpaidPayment <= 0:
flag = 1
if flag == 1 :
break
print "Result Your Code Should Generate:"
print "-------------------"
print "Lowest Payment: " + str(monthlyPayment)5
PROBLEM 3: USING BISECTION SEARCH TO MAKE THE PROGRAM FASTER
You'll notice that in Problem 2, your monthly payment had to be a multiple of $10. Why did we make it that way? You can try running your code locally so that the payment can be any dollar and cent amount (in other words, the monthly payment is a multiple of $0.01). Does your code still work? It should, but you may notice that your code runs more slowly, especially in cases with very large balances and interest rates. (Note: when your code is running on our servers, there are limits on the amount of computing time each submission is allowed, so your observations from running this experiment on the grading system might be limited to an error message complaining about too much time taken.)
Well then, how can we calculate a more accurate fixed monthly payment than we did in Problem 2 without running into the problem of slow code? We can make this program run faster using a technique introduced in lecture - bisection search!
The following variables contain values as described below:
-
balance- the outstanding balance on the credit card -
annualInterestRate- annual interest rate as a decimal
To recap the problem: we are searching for the smallest monthly payment such that we can pay off the entire balance within a year. What is a reasonable lower bound for this payment value? $0 is the obvious anwer, but you can do better than that. If there was no interest, the debt can be paid off by monthly payments of one-twelfth of the original balance, so we must pay at least this much every month. One-twelfth of the original balance is a good lower bound.
What is a good upper bound? Imagine that instead of paying monthly, we paid off the entire balance at the end of the year. What we ultimately pay must be greater than what we would've paid in monthly installments, because the interest was compounded on the balance we didn't pay off each month. So a good upper bound for the monthly payment would be one-twelfth of the balance, after having its interest compounded monthly for an entire year.
In short:
Monthly interest rate = (Annual interest rate) / 12.0
Monthly payment lower bound = Balance / 12
Monthly payment upper bound = (Balance x (1 + Monthly interest rate)12) / 12.0
Write a program that uses these bounds and bisection search (for more info check out the Wikipedia page on bisection search) to find the smallest monthly payment to the cent(no more multiples of $10) such that we can pay off the debt within a year. Try it out with large inputs, and notice how fast it is (try the same large inputs in your solution to Problem 2 to compare!). Produce the same return value as you did in Problem 2.
Note that if you do not use bisection search, your code will not run - your code only has 30 seconds to run on our servers.
Test Cases to Test Your Code With. Be sure to test these on your own machine - and that you get the same output! - before running your code on this webpage!
The code you paste into the following box should not specify the values for the variables balance or annualInterestRate - our test code will define those values before testing your submission.
# Paste your code into this box
monthlyInterestRate = annualInterestRate / 12.0
monthlyPaymentLowerBound = balance / 12
monthlyPayMentUpperBound = (balance * (1 + monthlyInterestRate)**12 ) / 12.0
t = balance
flag = 1
unpaidPayment = t
while flag:
unpaidPayment = t
monthlyPayment = (monthlyPaymentLowerBound + monthlyPayMentUpperBound) / 2
for e in range(12):
unpaidPayment = unpaidPayment - monthlyPayment
unpaidPayment = unpaidPayment * (1+monthlyInterestRate)
if e == 11:
if abs(unpaidPayment) <= 0.01:
flag = 0
elif unpaidPayment > 0.01:
monthlyPaymentLowerBound = monthlyPayment
elif unpaidPayment < 0.01:
monthlyPayMentUpperBound = monthlyPayment
print "Result Your Code Should Generate:"
print "-------------------"
print "Lowest Payment: " + str(round(monthlyPayment,2))
