CMU 15-112: Fundamentals of Programming and Computer Science
Day 1: Practice
- Do not use strings, loops, lists, or recursion this week.
- Do not hardcode the test cases in your solutions.
Code Tracing
What will this code print? Figure it out by hand, then run the code to confirm. Then slightly edit the code and try again.
- Trace #1 of 3:
import math
def p(x): print(x, end=' ') # prints and stays on same line
p(3 - 1 + 2 * 6 // 5)
p(3 - 1 + 2 * 6 / 5)
p(2**4/10 + 2**4//10)
p(max(8/3,math.ceil(8/3)))
print()
- Trace #2 of 3:
def p(x): print(x, end=' ') # prints and stays on same line
def f(x, y):
if (x > y):
if (x > 2*y): p('A')
else: p('B')
else:
p('C')
def g(x, y):
if (abs(x%10 - y%10) < 2): p('D')
elif (x%10 > y%10): p('E')
else:
if (x//10 == y//10): p('F')
else: p('G')
f(4,2)
f(2,3)
f(5,2)
print()
g(11,14)
g(11,24)
g(207,6)
g(207,5)
print()
- Trace #3 of 3:
def f(x): return 4*x + 2
def g(x): return f(x//2 + 1)
def h(x):
print(f(x-3))
x -= 1
print(g(x)+x)
x %= 4
return g(f(x) % 4) // 2
print(1 + h(6))
Reasoning Over Code
Find parameter(s) to the following functions so that they
return True. Figure it out by hand, then run the code to confirm.
There may be more than one correct answer for each function, and
you can provide any one of them.
- RC #1 of 2:
def rc1(n):
if ((n < 0) or (n > 99)): return False
d1 = n%10
d2 = n//10
m = 10*d1 + d2
return ((m < n) and (n < 12))
- RC #2 of 2:
def rc2(n):
if ((n <= 0) or (n > 99)): return False
if (n//2*2 != n): return False
if (n//5*5 != n): return False
return (n//7*7 == n)
Free Response (Problem-Solving)
- circlesIntersect(x1, y1, r1, x2, y2, r2)
Write the function circlesIntersect(x1, y1, r1, x2, y2, r2) that takes 6 numbers (ints or floats) -- x1, y1, r1, x2, y2, r2 -- that describe the
circle centered at (x1,y1) with radius r1, and the circle centered at (x2,y2) with radius r2, and returns True if the two circles intersect and
False otherwise.
- getInRange(x, bound1, bound2)
Write the function getInRange(x, bound1, bound2) which takes 3 int or
float values -- x, bound1, and bound2, where bound1 is not necessarily less than bound2. If x is between the two bounds, just return it unmodified. Otherwise, if x is less than the lower bound, return the lower bound, or if x is greater than the upper bound, return the upper bound.
For example:
- getInRange(1, 3, 5) returns 3 (the lower bound, since 1 lies to the left of the range [3,5])
- getInRange(4, 3, 5) returns 4 (the original value, since 4 is in the range [3,5])
- getInRange(6, 3, 5) returns 5 (the upper bound, since 6 lies to the right of the range [3,5])
- getInRange(6, 5, 3) also returns 5 (the upper bound, since 6 lies to the right of the range [3,5])
- eggCartons(eggs)
Write the function eggCartons(eggs) that takes a non-negative integer number of eggs, and returns the smallest integer number of
cartons required to hold that many eggs, where a carton may hold up to 12 eggs.
- pascalsTriangleValue(row, col)
Write the function pascalsTriangleValue(row, col) that takes
int values row and col, and returns the value in the given row and column of Pascal's Triangle where the triangle starts at row 0, and each row starts at column 0. If either row or col are not legal values, return None, instead of crashing. Hint: math.factorial may be helpful!
- isFactor(f, n)
Write the function isFactor(f, n) that takes two int values f and n, and returns True if f is a factor of n, and False otherwise. Note that
every integer is a factor of 0.
- isMultiple(m,n)
Write the function isMultiple that takes two int values m and n and returns True if m is a multiple of n and False otherwise. Note that 0
is a multiple of every integer other than itself. Also, you should
make constructive use of the isFactor function you just wrote above.
- distance(x1, y1, x2, y2)
Write the function distance(x1, y1, x2, y2) that takes four int or float values x1, y1, x2, y2 that represent the two points (x1, y1) and (x2, y2), and returns the distance between those points as a float.
- isLegalTriangle(s1, s2, s3)
Write the function isLegalTriangle(s1, s2, s3) that takes three int or float values representing the lengths of the sides of a triangle, and
returns True if such a triangle exists and False otherwise. Note from the triangle inequality that the sum of each two sides must be
greater than the third side, and further note that all sides of a legal triangle must be positive. Hint: how can you determine the longest side,
and how might that help?
- triangleArea(s1, s2, s3)
Write the function triangleArea(s1, s2, s3) that takes 3 floats and
returns the area of the triangle that has those lengths of its side.
If no such triangle exists, return 0. Hint: you will probably wish to
use Heron's Formula.
- triangleAreaByCoordinates(x1, y1, x2, y2, x3, y3)
Write the function triangleAreaByCoordinates(x1, y1, x2, y2, x3, y3) that takes 6 int or float values that represent the three points (x1,y1),
(x2,y2), and (x3,y3), and returns as a float the area of the triangle formed by those three points. Hint: you should make constructive use
of the triangleArea function you just wrote above.
- lineIntersection(m1, b1, m2, b2)
Write the function lineIntersection(m1, b1, m2, b2) that takes four int or float values representing the 2 lines:
y = m1*x + b1
y = m2*x + b2
This function returns the x value of the point of intersection of
the two lines. If the lines are parallel, or identical, the function should return None.
- threeLinesArea(m1, b1, m2, b2, m3, b3)
Write the function threeLinesArea(m1, b1, m2, b2, m3, b3) that takes six int or float values representing the 3 lines:
y = m1*x + b1
y = m2*x + b2
y = m3*x + b3
First find where each pair of lines intersects, then return the area of the triangle formed by connecting these three points of intersection. If no such triangle exists (if any two of the lines are parallel), return 0.
To do this, use three helper functions: one to find where two lines intersect (which you will call three times), a second to find the distance between two points, and a third to find the area of a triangle given its side lengths.
- nthFibonacciNumber(n)
Background: The Fibonacci numbers are defined by F(n) = F(n-1) + F(n-2). There are different conventions on whether 0 is a Fibonacci
number, and whether counting starts at n=0 or at n=1. Here, we will assume that 0 is not a Fibonacci number, and that counting starts at
n=0, so F(0)=F(1)=1, and F(2)=2. With this in mind, write the function nthFibonacciNumber(n) that takes a non-negative int n and returns the nth
Fibonacci number. Some test cases are provided for you. You can use
Binet's Fibonacci Number Formula which (amazingly) uses the
golden ratio to compute this result, though you may have to make some small change to account for the assumptions noted above.
- isEvenPositiveInt(x)
Write the function isEvenPositiveInt(x) that takes
an arbitrary value x, return True if it is an integer, and it is positive, and it is even (all 3 must be True), or False otherwise. Do not crash if the value is not an integer. So, isEvenPositiveInt("yikes!") returns False (rather than crashing), and isEvenPositiveInt(123456) returns True.
- nearestBusStop(street)
Write the function nearestBusStop(street) that takes a non-negative int street number, and returns the nearest bus stop to the given street, where buses stop every 8th street, including street 0, and ties go to the lower street, so the nearest bus stop to 12th street is 8th street, and the nearest bus stop to 13 street is 16th street.