Computer Science 15-112, Fall 2012
Class Notes:  Practice (through week 7)


2d-List and Sets/Dictionaries Problems
Do not use recursion
Make all your functions non-destructive unless explicitly indicated otherwise.

  1. See hw7a.
     
  2. isMagicSquare
    Write the function isMagicSquare(a) that takes a 2d list and returns True if it is a magic square and False otherwise.

  3. makeMagicSquare
    Write the function makeMagicSquare(n) that takes a positive odd integer n and returns an nxn magic square by following  De La Loubere's Method as described here.  If n is not a positive odd integer, return None.

  4. isLatinSquare
    Write the function isLatinSquare(a) that takes a 2d list and returns True if it is a Latin square and False otherwise.

  5. matrixAdd
    Write the function matrixAdd(m1, m2) that takes two 2d lists (that we will consider to be matrices, in the linear algebra sense) and returns a new 2d list that is the result of adding the two matrices.  Return None if the two matrices cannot be added for any reason.

  6. matrixMultiply
    Write the function matrixMultiply(m1, m2) that takes two 2d lists (that we will consider to be matrices, in the linear algebra sense) and returns a new 2d list that is the result of multiplying the two matrices.  Return None if the two matrices cannot be multiplied for any reason.

  7. removeRowAndCol
    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.

  8. destructiveRemoveRowAndCol
    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.  Thought question:
    In general, how might you have to change a test function when dealing with destructive function calls rather than non-destructive calls?
     

  9. isKnightsTour
    Background:  A "knight's tour" in chess is a sequence of legal knight moves such that the knight visits every square exactly once.  We can represent a (supposed) knight's tour as an NxN list of the integers from 1 to N2 listing the positions in order that the knight occupied on the tour.  If it is a legal knight's tour, then all the numbers from 1 to N2 will be included and each move from k to (k+1) will be a legal knight's move.  With this in mind, write the function isKnightsTour(board) that takes such a 2d list of integers and returns True if it represents a legal knight's tour and False otherwise.

  10. nQueensChecker
    Background:  The "N Queens" problem asks if we can place N queens on an NxN chessboard such that no two queens are attacking each other.  For most values of N, there are many ways to solve this problem.  Here, you will write the function nQueensChecker(board) that takes a 2d list of booleans where True indicates a queen is present and False indicates a blank cell, and returns True if this NxN board contains N queens all of which do not attack any others, and False otherwise.

  11. makeOthelloMove
    Background: read about the game of Othello (also known as Reversi).  Maybe even play it briefly (say, here).  We can represent an Othello board as an NxN list of values -- 'w' for white, 'b' for black, and the empty string for empty (of course).  If we number the rows from the top and columns from the left, write the function makeOthelloMove(board, row, col, player) that takes such a board, a row, a col, and a player ('w' or 'b'), and, if it is legal for the given player to place a piece at the given position, the function destructively modifies the board to reflect this move (flipping pieces as needed), and it returns the number of pieces flipped.  If the move is not legal, the function does not modify the board and returns 0.

  12. playCheckers
    Write the function playCheckers(N) that manages a 2-person NxN game of checkers.  You should display the board before each turn.  Ask the current player for their move.  If the move is illegal, say so, and ask for a legal move.  When you get a legal move, make the move and switch players.  Keep going until a player does not have a legal move, in which case they lose.  To make it more fun and more challenging, include handling kings properly.
     

  13. invertDictionary
    Write the function invertDictionary(d) that takes a dictionary d that maps keys to values and returns a dictionary of its inverse, that maps the original values back to their keys.  One complication:  there can be duplicate values in the original dictionary.  That is, there can be keys k1 and k2 such that (d[k1] == v) and (d[k2] == v) for the same value v.  In that case, what should inverseD[v] equal?  Answer:  map the original values back to the set of keys that originally mapped to them.  Thus, in this example, inverseD[v] maps to a set containing both s1 and s2.  Some thought questions:

    • What happens if the original dictionary d contains mutable values?

    • Is it always true that invertDictionary(invertDictionary(d)) == d?  Explain.
       

  14. sparseMatrixAdd
    A "sparse" matrix is mostly filled with 0's.  It may be quite large, with very few non-zero entries.  As such, it is very wasteful to represent it using a 2d list.  Instead, we can use a dictionary where we only store the non-zero values.  Write the function sparseMatrixAdd(m1, m2) that takes two sparse matrices represented in this way and returns a third sparse matrix that is the result of adding the two matrices.  Return None if the two matrices cannot be added for any reason.

  15. getPairSum
    Write the function getPairSum(a, target) that takes a list of numbers and a target value (also a number), and if there is a pair of numbers in the given list that add up to the given target number, returns that pair, and otherwise returns an empty list.  If there is more than one valid pair, you can return any of them. This can be done in O(n) time.   For example:
    getPairSum([1],1) == []
    getPairSum([5,2],7) == [5,2]
    getPairSum([10,-1,1,-8,3,1], 2) == [10,-8] (can also return [-1,3] or [1,1])
    getPairSum([10,-1,1,-8,3,1],10) == []


carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem