"""CS 61A HW 04 Name: Login: TA: Section: """ from functools import reduce def str_interval(x): """Return a string representation of interval x. >>> str_interval(make_interval(-1, 2)) '-1 to 2' """ return '{0} to {1}'.format(lower_bound(x), upper_bound(x)) def add_interval(x, y): """Return an interval that contains the sum of any value in interval x and any value in interval y. >>> str_interval(add_interval(make_interval(-1, 2), make_interval(4, 8))) '3 to 10' """ lower = lower_bound(x) + lower_bound(y) upper = upper_bound(x) + upper_bound(y) return make_interval(lower, upper) def mul_interval(x, y): """Return the interval that contains the product of any value in x and any value in y. >>> str_interval(mul_interval(make_interval(-1, 2), make_interval(4, 8))) '-8 to 16' """ p1 = lower_bound(x) * lower_bound(y) p2 = lower_bound(x) * upper_bound(y) p3 = upper_bound(x) * lower_bound(y) p4 = upper_bound(x) * upper_bound(y) return make_interval(min(p1, p2, p3, p4), max(p1, p2, p3, p4)) #### Q1 def make_interval(a, b): """Construct an interval ADT, spanning from a to b.""" "*** YOUR CODE HERE ***" def lower_bound(x): """Return the lower bound of the interval x.""" "*** YOUR CODE HERE ***" def upper_bound(x): """Return the upper bound of the interval x.""" "*** YOUR CODE HERE ***" #### Q2 def sum_intervals(seq): """Returns the sum of all of intervals in the sequence seq. >>> a = make_interval(-1, 2) >>> b = make_interval(-4, 3) >>> c = make_interval(-4, -3) >>> str_interval(sum_intervals((a, b, c))) '-9 to 2' """ "*** YOUR CODE HERE ***" #### Q3 def div_interval(x, y): """Return the interval that contains the quotient of any value in x divided by any value in y. Division is implemented as the multiplication of x by the reciprocal of y. >>> str_interval(div_interval(make_interval(-1, 2), make_interval(4, 8))) '-0.25 to 0.5' """ "*** YOUR CODE HERE ***" reciprocal_y = make_interval(1/upper_bound(y), 1/lower_bound(y)) return mul_interval(x, reciprocal_y) #### Q4 def sub_interval(x, y): """Return the interval that contains the difference of any value in x minus any value in y. "*** YOUR CODE HERE ***" """ "*** YOUR CODE HERE ***" #### Q5 def make_center_width(c, w): """Construct an interval from center and width.""" return make_interval(c - w, c + w) def center(x): """Return the center of interval x.""" return (upper_bound(x) + lower_bound(x)) / 2 def width(x): """Return the width of interval x.""" return (upper_bound(x) - lower_bound(x)) / 2 def make_center_percent(c, p): """Construct an interval from center and percentage tolerance. Percentage is given where 100 would mean 100% of tolerance. >>> str_interval(make_center_percent(3, 50)) '1.5 to 4.5' >>> str_interval(make_center_percent(3, 100)) '0.0 to 6.0' """ "*** YOUR CODE HERE ***" def percent(x): """Return the percentage tolerance of the interval x.""" "*** YOUR CODE HERE ***" #### Q6 def quadratic(x, a, b, c): """Return the interval of all results f(t) where t is a value from the interval x and f(t) = a * t * t + b * t + c. This is the less accurate version which treats each instance of t as a different value from the interval. See the extra for experts question for exploring why this is not _really_ correct and to write a more precise version. >>> str_interval(quadratic(make_interval(0, 2), -2, 3, -1)) '-9 to 5' >>> str_interval(quadratic(make_interval(1, 3), 2, -3, 1)) '-6 to 16' """ "*** YOUR CODE HERE ***" #### Q7 def one(n): return n one_running_time = "Theta(YOUR ANSWER HERE)" def two(n): if n > 10 or n < 0: return n return two(n+1) two_running_time = "Theta(YOUR ANSWER HERE)" def three(n): if n <= 0: return 0 elif n % 2 == 0: return 2 + three(n/2) else: return 1 + three(n-1) three_running_time = "Theta(YOUR ANSWER HERE)" def four(n): if n == 0: return 0 else: return two(n) + four(n-1) four_running_time = "Theta(YOUR ANSWER HERE)" def five(n): if n == 0: return 0 else: return three(n) + five(n-1) five_running_time = "Theta(YOUR ANSWER HERE)" def six(n): total = 0 while n >= 0: total = total + four(n) n = n-1 return total six_running_time = "Theta(YOUR ANSWER HERE)" #### Extra for Experts #### Q8 def par1(r1, r2): return div_interval(mul_interval(r1, r2), add_interval(r1, r2)) def par2(r1, r2): one = make_interval(1, 1) rep_r1 = div_interval(one, r1) rep_r2 = div_interval(one, r2) return div_interval(one, add_interval(rep_r1, rep_r2)) def demonstrate_lem_prob(): """Returns False when comparing the two different versions of par Lem wrote using intervals int1 and int2. You are encouraged to try other expressions to get better insight as to what's going on. >>> demonstrate_lem_prob() False """ def eq_interval(x, y): """Checks if the intervals x and y are the same.""" lower_same = lower_bound(x) == lower_bound(y) upper_same = upper_bound(x) == upper_bound(y) return lower_same and upper_same int1, int2 = "*** YOUR CODE", " HERE ***" return eq_interval(par1(int1, int2), par2(int1, int2)) #### Q9 explanation = """*** EXPLAIN HERE***""" #### Q10 def accurate_quadratic(x, a, b, c): """Calculate the interval of values that can result from applying the quadratic function f(t) = a * t * t + b * t + c to any value from the interval x. >>> str_interval(accurate_quadratic(make_interval(0, 2), -2, 3, -1)) '-3 to 0.125' >>> str_interval(accurate_quadratic(make_interval(1, 3), 2, -3, 1)) '0 to 10' """ "*** YOUR CODE HERE ***" #### Q11 def polynomial(x, c): """Return the interval that is the range the polynomial defined by coefficients c, for domain interval x. >>> str_interval(polynomial(make_interval(0, 2), (-1, 2, -2))) '-5 to -0.5' >>> str_interval(polynomial(make_interval(1, 3), (1, -3, 2))) '0 to 10' >>> r = polynomial(make_interval(0.5, 2.25), (10, 24, -6, -8, 3)) >>> round(lower_bound(r), 5) 18.0 >>> round(upper_bound(r), 5) 23.0 """ "*** YOUR CODE HERE ***"