CMU 15-112: Fundamentals of Programming and Computer Science
- These exercises will help you prepare for writing-session5, which is on Fri 27-Sep, 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 Friday you must work alone, and without any notes or access to the web or other resources.
- To start:
- Do not use recursion this week.
- Do not hardcode the test cases in your solutions.
Important note: As with last week, and from now on, writing sessions will also contain very short (fill-in-the-blank or super-short code tracing) questions covering this week's course notes. Be sure to study the course notes and know them well before attending Friday's writing session! Also, be sure to look at the practice problems at the end of this page!
- removeRowAndCol (non-destructive and destructive)
Here we will write removeRowAndCol twice -- once non-destructively, and then again destructively. Note that neither of these versions may call nor essentially duplicate the other version. So in particular, your nondestructive version may not do this:
L = copy.deepcopy(L) doDestructiveVersion(L) return LInstead, do not use copy.deepcopy and directly construct the modified 2d list.
Both functions take a rectangular list L and two ints, row and col. In both cases, the goal is to obtain a version of the list that has the given row and given column removed. You may assume that row and col are both legal values (that is, they are non-negative integers that are smaller than the largest row and column, respectively). For example, the list shown to the left would lead to the result shown on the right when called with the row 1 and the column 2.
[ [ 2, 3, 4, 5], [ 8, 7, 6, 5], [ 0, 1, 2, 3] ]
[ [ 2, 3, 5], [ 0, 1, 3] ]
nondestructiveRemoveRowAndCol(L, row, col): the non-destructive version should return a new list, and should not modify the provided list at all.
destructiveRemoveRowAndCol(L, row, col): the destructive version should modify the original list, and should not return anything (that is, None).
Hint: writing test functions for non-destructive and destructive functions is a little different from writing ordinary test functions. Here is an example of a test case for a non-destructive function:
# This is a test case for a non-destructive function. # The input list and output list L = [ [ 2, 3, 4, 5], [ 8, 7, 6, 5], [ 0, 1, 2, 3] ] result = [ [ 2, 3, 5], [ 0, 1, 3] ] # Copy the input list so we can check it later import copy lCopy = copy.deepcopy(L) # The first assert is an ordinary test; the second is a non-destructive test assert(nondestructiveRemoveRowAndCol(L, 1, 2) == result) assert(L == lCopy) # input list should not be changed
And here is an example of a test case for a destructive function:
# This is a test case for a destructive function. # The input list and output list L = [ [ 2, 3, 4, 5], [ 8, 7, 6, 5], [ 0, 1, 2, 3] ] result = [ [ 2, 3, 5], [ 0, 1, 3] ] # The first test is an ordinary test; the second is a destructive test assert(destructiveRemoveRowAndCol(L, 1, 2) == None) assert(L == result) # input list should be changed
Write the function bestQuiz(a), which takes a rectangular 2d list of numbers that represents a gradebook, where each column represents a quiz, and each row represents a student, and each value represents that student's score on that quiz (except -1 indicates the student did not take the quiz). For example:
a = [ [ 88, 80, 91 ], [ 68, 100, -1 ] ]This list indicates that student0 scored 88 on quiz0, 80 on quiz1, and 91 on quiz2. Also, student1 scored 68 on quiz0, 100 on quiz1, and did not take quiz2. The function returns the quiz with the highest average. In this case, quiz0 average is 78, quiz1 average is 90, and quiz2 average is 91 (since we ignore the -1). Thus, quiz2 is the best, and so the function returns 2 in this case. You are not responsible for malformed input, except you should return None if there are no quizzes. Also, resolve ties in favor of the lower quiz number. Here is a test function for you:def testBestQuiz(): print('Testing bestQuiz()...', end='') a = [ [ 88, 80, 91 ], [ 68, 100, -1 ]] assert(bestQuiz(a) == 2) a = [ [ 88, 80, 80 ], [ 68, 100, 100 ]] assert(bestQuiz(a) == 1) a = [ [88, -1, -1 ], [68, -1, -1 ]] assert(bestQuiz(a) == 0) a = [ [-1, -1, -1 ], [-1, -1, -1 ]] assert(bestQuiz(a) == None) print('Passed!')
- matrixAdd(L, M)
Background: we can think of a 2d list in Python as a matrix in math. To add two matrices, L and M, they must have the same dimensions. Then, we loop over each row and col, and the result[row][col] is just the sum of L[row][col] and M[row][col]. For example:L = [ [1, 2, 3], [4, 5, 6] ] M = [ [21, 22, 23], [24, 25, 26]] N = [ [1+21, 2+22, 3+23], [4+24, 5+25, 6+26]] assert(matrixAdd(L, M) == N)With this in mind, write the function matrixAdd(L, M) that takes two rectangular 2d lists (that we will consider to be matrices) that you may assume only contain numbers, and returns a new 2d list that is the result of adding the two matrices. Return None if the two matrices cannot be added because they are of different dimensions.
Write the function isMostlyMagicSquare(a) that takes an 2d list of numbers, which you may assume is an NxN square with N>0, and returns True if it is "mostly magic" and False otherwise, where a square is "mostly magic" if:
- Each row, each column, and each of the 2 diagonals each sum to the same total.
Here is another mostly-magic square:
[ [ 42 ]]That square is 1x1 and each row, column, and diagonal sums to 42! And finally, here is a not-mostly-magic square:
[ [ 1, 2], [ 2, 1]]Each row and each column add to 3, but one diagonal adds to 2 and the other to 4.
- DataTable and DataColumn classes
This exercise converts a csv string (a multi-line string of comma-separated values) into a table, and then allows us to extract individual columns to do some data analysis (here, just taking the average for now).
Note: you may assume:
- the table is nonempty (so it has at least one row and at least one column)
- the table is rectangular (so each row has the same number of columns)
- the first row contains the column labels, which are strings
- the first column contains the row labels, which are strings
- all other columns contain data, which are ints, and legally formatted
- ignore empty rows, and ignore leading and trailing whitespace on any row
Here is an example of such data:csvData = ''' Name,Hw1,Hw2,Quiz1,Quiz2 Fred,94,88,82,92 Wilma,98,80,80,100 '''
With this in mind, write the class DataTable and also the class DataColumn so the following test function passes (without hardcoding any test cases):def testDataTableAndDataColumnClasses(): print('Testing DataTable and DataColumn classes...', end='') csvData = ''' Name,Hw1,Hw2,Quiz1,Quiz2 Fred,94,88,82,92 Wilma,98,80,80,100 ''' dataTable = DataTable(csvData) rows, cols = dataTable.getDims() assert((rows == 3) and (cols == 5)) column3 = dataTable.getColumn(3) assert(isinstance(column3, DataColumn)) assert(column3.label == 'Quiz1') assert(column3.data == [82, 80]) assert(almostEqual(column3.average(), 81)) column4 = dataTable.getColumn(4) assert(isinstance(column4, DataColumn)) assert(column4.label == 'Quiz2') assert(column4.data == [92, 100]) assert(almostEqual(column4.average(), 96)) print('Passed!')
- Short Answer Practice Problems
This week'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 the following correctly creates a 3x2 (3 rows, 2 columns) 2d list without any aliases? A) [  * 2 ] * 3 B) [  * 3 ] * 2 C) [ ( * 2) for i in range(3) ] D) [ ( * 3) for i in range(2) ] E) None of the above 2. If we had a non-ragged 3d list L (so "cubic" instead of "rectangular"), which of the following would return all 3 dimensions: A) len(L), len(L), len(L[0,0]) B) len(L), len(L), len(L) C) len(L), len(L), len(L[-1]) D) len(L), len(L), len(L) E) None of the above 3. Why should we use use copy.deepcopy instead of copy.copy on 2d lists? A) copy.copy has a bug and crashes on 2d lists B) copy.copy creates a shallow copy with aliases to the inner lists C) copy.copy is much slower than copy.deepcopy D) copy.copy works the same as copy.deepcopy on 2d lists E) None of the above 4. Why did we provide our own myDeepCopy in the notes? A) copy.deepcopy is very slow, ours is much faster B) copy.deepcopy is not available on some versions of Python C) copy.deepcopy will preserve existing aliases in a 2d list, ours will not D) copy.deepcopy is not a preferred way to copy a 2d list E) None of the above 5. Why did we provide our own print2dList in the notes? A) The builtin print2dList function works poorly in some cases B) There is no builtin print2dList function and just printing a 2d list makes it appear on a single line and also does not align the columns, and thus makes it hard to read. 6. What happens if we reverse the order of the 'for' loops in the standard way we loop over a 2d list L. That is, what if instead of this: for row in range(rows): for col in range(cols): we did this: for col in range(cols): for row in range(rows): A) We would skip some of the values in L B) We would visit all the values in row 0 first, then row 1, and so on C) We would visit all the values in col 0 first, then col 1, and so on D) This code will not run at all E) None of the above 7. Which of the following does NOT set M to a list of the values in column c of the 10x10 2d list L? A) M = [ L[i][c] for i in range(10) ] B) N, M = copy.deepcopy(L), [ ] while (N != [ ]): M.append(N.pop(0)[c]) C) M = [ ] for i in range(10): M += [ L[c][i] ] D) None of the above
- Code Tracing Practice Problems
Same note as above: This week'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 a = [] b = copy.copy(a) c = copy.deepcopy(a) b.append(2) c.append() print(a, b, c) # __________________________________ a = [[4,5]] * 2 b = copy.deepcopy(a) a = 6 print(a,b) # __________________________________ a = [[1,2],[3,4]] b = a[::-1] c = [r[::-1] for r in a] print(b, c) # __________________________________ a = [[1,2,3],[4,5,6]] for c in range(len(a)): for r in range(c): a[r][c] *= 10 print(a) # __________________________________ a = [[1,2],,[4,5,6]] b = [ ] for r in range(len(a)): b += [len(a[r])] print(b) # __________________________________ ct()