CMU 15-112: Fundamentals of Programming and Computer Science
- These exercises will help you prepare for writing-session4, which is on Thu 6-Feb, and which will contain a randomly-chosen subset of exercises from among these.
- Unlike the hw, you may work collaboratively on these practice exercises.
- That said, during the actual writing session on Thursday you must work alone, and without any notes or access to the web or other resources.
- To start:
- Do not use recursion in this unit.
- Do not hardcode the test cases in your solutions.
Important note: Starting this unit, writing sessions will also contain very short (fill-in-the-blank, multiple choice, and super-short code tracing) questions covering this unit's course notes. Be sure to study the course notes and know them well before attending Thursday's writing session! Also, be sure to look at the practice problems at the end of this file!
Write the function alternatingSum(a) that takes a list of numbers and returns the alternating sum (where the sign alternates from positive to negative or vice versa). For example, alternatingSum([5,3,8,4]) returns 6 (that is, 5-3+8-4). If the list is empty, return 0.
Write the non-destructive function median(a) that takes a list of ints or floats and returns the median value, which is the value of the middle element, or the average of the two middle elements if there is no single middle element. If the list is empty, return None.
Write the function isSorted(a) that takes a list of numbers and returns True if the list is sorted (either smallest-first or largest-first) and False otherwise. Your function must only consider each value in the list once, so in particular you may not sort the list.
Write the function smallestDifference(a) that takes a list of integers and returns the smallest absolute difference between any two integers in the list. If the list is empty, return -1. For example:
assert(smallestDifference([19,2,83,6,27]) == 4)The two closest numbers in that list are 2 and 6, and their difference is 4.
First, you can read about look-and-say numbers here. Then, write the function lookAndSay(a) that takes a list of numbers and returns a list of numbers that results from "reading off" the initial list using the look-and-say method, using tuples for each (count, value) pair. For example:
lookAndSay() ==  lookAndSay([1,1,1]) == [(3,1)] lookAndSay([-1,2,7]) == [(1,-1),(1,2),(1,7)] lookAndSay([3,3,8,-10,-10,-10]) == [(2,3),(1,8),(3,-10)] lookAndSay([3,3,8,3,3,3,3]) == [(2,3),(1,8),(4,3)]
Write the function inverseLookAndSay(a) that does the inverse of the previous problem, so that, in general:
inverseLookAndSay(lookAndSay(a)) == aOr, in particular:
inverseLookAndSay([(2,3),(1,8),(3,-10)]) == [3,3,8,-10,-10,-10]
Write the function nondestructiveRemoveRepeats(L), which takes a list L and nondestructively returns a new list in which any repeating elements in L are removed. For example:
assert(nondestructiveRemoveRepeats([1, 3, 5, 3, 3, 2, 1, 7, 5]) == [1, 3, 5, 2, 7])Also:
L = [1, 3, 5, 3, 3, 2, 1, 7, 5] assert(nondestructiveRemoveRepeats(L) == [1, 3, 5, 2, 7]) assert(L == [1, 3, 5, 3, 3, 2, 1, 7, 5]) # nondestructive!Note that the values in the resulting list occur in the order they appear in the original list, but each occurs only once in the result. Also, since this is a nondestructive function, it returns the resulting list.
Write the function destructiveRemoveRepeats(L), which implements the same function destructively. Thus, this function should directly modify the provided list to not have any repeating elements. Since this is a destructive function, it should not return any value at all (so, implicitly, it should return None). For example:
L = [1, 3, 5, 3, 3, 2, 1, 7, 5] destructiveRemoveRepeats(L) assert(L == [1, 3, 5, 2, 7]) # destructive!
- VoteTally class
Write the VoteTally class so the following test function passes (and do not hardcode anything, so any reasonably similar uses of the VoteTally class would also work properly):
def testVoteTallyClass(): print('Testing VoteTally class...', end='') # When we create a VoteTally, we provide a list of # candidates whose votes we are tallying: vt1 = VoteTally(['Fred', 'Wilma', 'Betty']) # We can then add votes for the candidates vt1.addVotes(5, 'Fred') vt1.addVotes(3, 'Wilma') vt1.addVotes(2, 'Fred') # If we add votes to a non-candidate, we do so gracefully: assert(vt1.addVotes(3, 'Bam-Bam') == 'No such candidate as Bam-Bam') # And we can get the total tally of votes for each candidate assert(vt1.getVotes('Fred') == 7) assert(vt1.getVotes('Wilma') == 3) assert(vt1.getVotes('Betty') == 0) # And we can gracefully handle non-candidates assert(vt1.getVotes('Barney') == 'No such candidate as Barney') # And we can also get the overall total assert(vt1.getVotes('Total') == 10) # Here is a second VoteTally with some (but not all) of the same candidates vt2 = VoteTally(['Fred', 'Barney', 'Betty']) vt2.addVotes(5, 'Fred') vt2.addVotes(2, 'Betty') vt2.addVotes(8, 'Betty') assert(vt2.getVotes('Fred') == 5) assert(vt2.getVotes('Wilma') == 'No such candidate as Wilma') assert(vt2.getVotes('Betty') == 10) assert(vt2.getVotes('Barney') == 0) assert(vt2.getVotes('Total') == 15) # We can combine two VoteTally objects to create a third # VoteTally object, which includes all the candidates from either # tally, and combines their totals: vt3 = vt1.addVoteTally(vt2) assert(vt1.candidates == ['Fred', 'Wilma', 'Betty']) # unchanged assert(vt2.candidates == ['Fred', 'Barney', 'Betty']) # ditto # but the new VoteTally is created with a list of candidates # in the same order as they appear first in vt1 then vt2, # but with no duplicates assert(vt3.candidates == ['Fred', 'Wilma', 'Betty', 'Barney']) assert(vt3.getVotes('Fred') == 12) assert(vt3.getVotes('Wilma') == 3) assert(vt3.getVotes('Betty') == 10) assert(vt3.getVotes('Barney') == 0) assert(vt3.getVotes('Pebbles') == 'No such candidate as Pebbles') assert(vt3.getVotes('Total') == 25) print('Passed!')
- Short Answer Practice Problems
Note that this unit's writing session will start with a physical sheet of paper containing some subset of these questions, or questions nearly identical to these questions.
1. Which of these does not set M to a copy of L? a) M = copy.copy(L) b) M = L[:] c) M = L + [ ] d) M = L e) M = list(L) 2. If a function f(L) does not return a value (so technically it returns None), which is more likely: a) f(L) is destructive b) f(L) is non-destructive 3. Assuming L is a list and s is a string, which of the following methods does not exist: a) L.index(v) b) L.find(v) c) s.index(c) d) s.find(c) 4. What is the difference between L.append(v) and L.extend(v)? a) There is no difference b) L.append adds one value and L.extend adds a list of values c) L.append adds to the end of L and L.extends adds to the start of L d) There is no such thing as L.extend 5. Fill in the blank so that M is equal to L, only with the value 5 nondestructively inserted at index 3 (so L is unchanged). You may assume len(L)>3: M = _________________________________________________ 6. Which kind of loop should we use if we are adding and/or removing values from a list L while looping over it? a) for v in L b) while i < len(L) 7. What is the difference between L.sort() and sorted(L)? a) L.sort() is faster than sorted(L) b) L.sort() is destructive and sorted(L) is non-destructive c) L.sort() is non-desructive and sorted(L) is destructive d) Nothing -- they do the same thing. 8. What is the key difference between a tuple and a list? a) Tuples can only contain exactly 2 values, lists can contain any number of values b) Tuples are mutable, lists are not c) Tuples are immutable, lists are not d) Tuples can only contain numbers, lists can contain any type of value 9. Fill in the blank so that T refers to a singleton (length 1) tuple containing just the value 42: T = _____________________________________ 10. Fill in the blank with a list comprehension so that M contains the list of the squares of the values in L, which you may assume is a list of integers: M = ____________________________________
- Code Tracing Practice Problems
Same note as above: this unit's writing session will start with a physical sheet of paper containing some subset of these questions, or questions nearly identical to these questions.
import copy def ct(): # fill in each space to the right of each print statement # with the value it prints print([3,2,1] > [3,2]) # __________________________________ a =  b = a c = copy.copy(a) a +=  a = a +  print(a, b, c) # __________________________________ a = [2,3,5,3,2] a.remove(2) v = a.pop(2) print(a, v) # __________________________________ L = list(range(1,7,2)) M = [v**2 for v in L] N = [v*10 for v in M if v < 10] print(L, M, N) # __________________________________ L = ['A', 'BC', 'D'] print('xy'.join(L)) # __________________________________ ct()