Computer Science 15-110, Fall 2010
Class Notes:  Recitation 7

1. Midterm1 Review
2. Practice Tracing
3. Practice Mystery Methods
   
4. Practice Problems using Lists
1. Sieve of Eratosthenes
   
2. Matric (2d List) Addition
   

Recitation 7

1. Midterm1 Review
   We will review the solutions to midterm1 in recitation today.  We only have part of recitation to do this (plenty else to cover -- see below!).  If you need more time, please arrange for a 1-on-1 tutoring session with a CA or attend office hours.
   
   
2. Practice Tracing
   Trace this code by hand, then run it to confirm your prediction.
   
   ################################
   print "--- Trace 1 ---"
   import copy
   a = [4, 5, 6]
   b = a
   c = copy.deepcopy(a)
   a[0] = 1
   b[1] = 2
   c[2] = 3
   print a
   print b
   print c
   
   ################################
   print "--- Trace 2 ---"
   def f(a):
       a[0] = 42
   a = [1, 2, 3]
   b = f(a)
   print a
   print b
   
   ################################
   print "--- Trace 3 ---"
   def g(a):
       a = [42]
   a = [1, 2, 3]
   b = g(a)
   print a
   print b
   
   ################################
   print "--- Trace 4 ---"
   def h(a):
       return [42]
   a = [1, 2, 3]
   b = h(a)
   print a
   print b
   
   ################################
   print "--- Trace 5 ---"
   import copy
   def m(a):
       for i in range(1,len(a)):
           a[i] += a[i-1]
   def n(a):
       a = copy.deepcopy(a)
       m(a)
       return a
   a = [1, 2, 3, 4]
   b = m(a)
   c = n(a)
   print a
   print b
   print c
   
   
3. Practice Mystery Methods
   
   a)
   def mysteryA(a, b):
       # assume all elements in a and b are single-digit integers
       while (len(a) < len(b)):
           a.insert(0, 0)
       while (len(b) < len(a)):
           b.insert(0, 0)
       result = [0] * len(a)
       carry = 0
       for i in range(len(a)):
           place = len(a)-1-i
           sum = carry + a[place] + b[place]
           result[place] = sum%10
           carry = sum/10
       if (carry > 0):
           result.insert(0, carry)
       return result
   
   print mysteryA([1, 2], [3])
   print mysteryA([6, 3, 2], [8, 2, 9])
   
   b)
   def mysteryB(a):
       rows = len(a)
       cols = len(a[0])
       if (rows != cols):
         return False
       for row in range(rows):
           for col in range(cols):
               goal = (row == col) * 1 # 1 for True, 0 for False
               if (a[row][col] != goal):
                   return False
       return True
   
   
4. Practice Problems Using Lists
   All your solutions to these problems should use recursion, unless noted otherwise.
   
   
1. Sieve of Eratosthenes
   Using the Sieve of Eratosthenes, write a function, sieve(n), that returns a list containing all the prime numbers up to n (inclusive).  For example, sieve(10) would return the list [2, 3, 5, 7].
   
   Once you have tried this (and only then!), you may peek at this sample solution.
   
   Optional / Time permitting (if you have completed the Matrix Addition problem below:  here is a more complete example that uses the Sieve of Eratosthenes to compute the so-called prime counting function, pi(n).  The example does this two different ways:  using a classic "isPrime" function that checks every factor from 2 to sqrt(n), and then again using the sieve.  It times each approach.  The results show why the sieve is the way to go.  Check it out!  (If you don't have time to cover it in recitation, check it out on your own afterwards!)
   
   
2. Matrix (2d List) Addition
   Write a function, matrixAdd(m1, m2), that takes two matrices (2d lists) and returns their sum (using standard matrix addition).  If the matrices are not the same dimensions, your function should return None.
   
   Once you have tried this (and only then!), you may peek at this sample solution.
   

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