CMU 15-112 Fall 2015 Quiz5 Practice
(Due never)



  1. Code Tracing
  2. The Worked Examples Using 1d Lists
    1. The Locker Problem
    2. Anagrams
    3. The Sieve of Eratosthenes
    4. The Prime Counting Function
    5. Sorting (selection, bubble, merge, builtin sorts)
  3. removeRowAndCol(A, row, col)
  4. destructiveRemoveRowAndCol(A, row, col)
  5. wordSearchWithIntegerWildCards(board, word)
  6. bestQuiz(a)

  1. Code Tracing
    See here.

  2. The Worked Examples Using 1d Lists
    This week's quiz may include any of the worked examples from last week's worked examples. Specifically:
    1. The Locker Problem
    2. Anagrams
    3. The Sieve of Eratosthenes
    4. The Prime Counting Function
    5. Sorting (selection, bubble, merge, builtin sorts)

  3. removeRowAndCol(A, row, col)
    Write the function removeRowAndCol(A, row, col) that takes a 2d list A, a row index and a col index, and non-destructively returns a new 2d list with the given row and column removed. So, if:
        A = [ [ 2, 3, 4, 5],
              [ 8, 7, 6, 5],
              [ 0, 1, 2, 3]
            ]
    
    Then removeRowAndCol(A, 1, 2) returns:
            [ [ 2, 3, 5],
              [ 0, 1, 3]
            ]
    
    Also, A remains unchanged.
    def removeRowAndCol(A, row, col): return 42 # place your answer here! def testRemoveRowAndCol(): print("Testing removeRowAndCol()...", end="") a = [ [ 2, 3, 4, 5], [ 8, 7, 6, 5], [ 0, 1, 2, 3]] assert(removeRowAndCol(a, 1, 2) == [[2, 3, 5], [0, 1, 3]]) assert(a == [ [ 2, 3, 4, 5],[ 8, 7, 6, 5],[ 0, 1, 2, 3]]) assert(removeRowAndCol(a, 0, 0) == [[7, 6, 5], [1, 2, 3]]) assert(a == [ [ 2, 3, 4, 5],[ 8, 7, 6, 5],[ 0, 1, 2, 3]]) print("Passed!") testRemoveRowAndCol()

  4. destructiveRemoveRowAndCol(A, row, col)
    Rewrite the previous function so it is destructive. In this case, the return value is None and instead the 2d list A is destructively modified to remove the given row and column.
    def destructiveRemoveRowAndCol(A, row, col): return 42 # place your answer here! def testDestructiveRemoveRowAndCol(): print("Testing removeRowAndCol()...", end="") a = [ [ 2, 3, 4, 5], [ 8, 7, 6, 5], [ 0, 1, 2, 3]] assert(destructiveRemoveRowAndCol(a, 1, 2) == None) assert(a == [[2, 3, 5], [0, 1, 3]]) a = [ [ 2, 3, 4, 5], [ 8, 7, 6, 5], [ 0, 1, 2, 3]] assert(destructiveRemoveRowAndCol(a, 0, 0) == None) assert(a == [[7, 6, 5], [1, 2, 3]]) print("Passed!") testDestructiveRemoveRowAndCol()

  5. wordSearchWithIntegerWildCards(board, word)
    Here we will modify wordSearch so that we can include positive integers in the board, like so (see board[1][1]):
        board = [ [ 'p', 'i', 'g' ],
                  [ 's',   2, 'c' ],
                ]
    
    When matching a word, a positive integer on the board matches exactly that many letters in the word. So the board above contains the word "cow" starting from [1,2] heading left, since the 2 matches "ow". It also contains the word "cows" for the same reason. But it does not contain the word "co", since the 2 must match exactly 2 letters. To make this work, of the three functions in our wordSearch solution, the outer two do not have to change, but the innermost one does. Rewrite the innermost function here so that it works as described. Among other parameters, your function should take a direction as a non-negative int (rather than a tuple), and it should return True if the word is in the wordSearch and False otherwise.
    def wordSearch(board, word): return 42 # place your answer here! def testWordSearch(): print("Testing wordSearch()...", end="") board = [ [ 'p', 'i', 'g' ], [ 's', 2, 'c' ] ] assert(wordSearch(board, "cow") == True) assert(wordSearch(board, "cows") == True) assert(wordSearch(board, "coat") == False) assert(wordSearch(board, "pig") == True) assert(wordSearch(board, "z") == False) assert(wordSearch(board, "zz") == True) print("Passed!") testWordSearch() # with integer wildcards!

  6. bestQuiz(a)
    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.
    def bestQuiz(a): return 42 # place your answer here! 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!") testBestQuiz()