• This will be a non-autograded lab.  There will not be a CA-led grading session for this lab.
• This lab requires a minimum of 1.5 hours of group meetings (more is acceptable, but less is not).  You must meet in a group for this entire time with at least 1 other, and at most 5 other, students from this course (so group sizes may range from 2 to 6 students, with the ideal being 4 students).  Also, you may only work with one group (no bouncing between groups).
• If you do not know how to form a group, go to office hours (sooner is better) and the CA's will help students form into groups (who may then leave the cluster, depending on how crowded it is, and perhaps do their lab on the 3rd floor or in some other more spacious area).
• All the work for this lab must be done collaboratively.  No single-student submissions will be accepted!
• If at all possible, you should complete the lab in a single group meeting.  Reconvening groups is notoriously difficult (and then what do you do if all-but-one attend?).
• Each group will elect a single group member to be their secretary.  This person will record attendance, take notes, and make a single submission for the entire group.  The submission should be emailed to the secretary's CA, and cc'ed to everyone else in the group (don't worry about sending it to their CA's, just send it to the secretary's CA).
• To receive credit, this email must be sent by 10pm on Wednesday night.  The email must be in plaintext with no attachments, and must clearly answer the questions below in the order given.
• Your grade will be 80% participation, and 20% correctness.

1. Logistics
   1. Group Members
      List the names, andrew id's, and sections of all group members.  Be sure to also cc them when you email this report to you CA.
   2. Start and End Times
      List the day, location, and start and end times of your group meeting.  And while you are strongly urged to finish in a single group meeting, if your group needed more than one meeting to fulfill the requirement, list all the meeting times and durations.
   3. Full Attendance
      Certify, on the honor code, that everyone in the group fully attended the entire group meetings.  This is the only way the group can get credit for this lab.  If someone comes late, you'll have to restart the meeting at that time!
       
2. Selectionsort and Mergesort
   1. As a group, watch these videos on selectionsort and mergesort (you do not need to watch the whole thing, just long enough to be sure you understand how each sort works).  Also, work with xSortLab (as a group!) for both selectionsort and mergesort to further confirm that you all understand how each sort works.  What to submit?  Just a confirmation that you did this step.
   2. As a group, re-derive the worst-case big-oh runtime for both selectionsort and mergesort.  Submit short "proofs" (in plaintext) of each of these.  Be sure you all understand the math.  Discuss amongst yourselves as needed.
       
3. Big-Oh
   For each of the following, indicate the (worst-case) big-oh runtime, along with either an English explanation or a mathematical "proof" (some handwaving allowed, so don't get too technical or detailed; we're looking for the big ideas).  Be sure, again, that everyone on the team understands!
   1. Finding an element in a sorted list (say, looking up a name in a traditional phone book)
   2. Finding an element in an unsorted list (say, looking up a phone number, that is, a reverse lookup, in a traditional phone book)
   3. Guessing an integer between 0 and N (where you are told if you are too low, too high, or just right)
   4. Placing a marble on each square that a randomly-placed knight attacks in an NxN chessboard.  (Note: you know where the knight is, you do not have to search for it.)
   5. Placing a marble on each square that a randomly-placed queen attacks in an NxN chessboard.  (Same note, this time for the queen.)
   6. Placing a marble on each black square on an NxN chessboard.
   7. Playing "subset sum", a fun game where you get a list of N numbers and try to find a subset that sums to 0.   There is no better way known than to just try every possible subset in turn (yuck!).  So, to rephrase this problem:  how many subsets are there for a list with N elements?
   8. Running each of the following functions (assume n>0, x>0, and ignore cases when they might crash):

      def f0(n):
          count = 0
          for x in xrange(n):
              for y in xrange(1, n):
                  count += 1
          return count
      
      def f1(n):
          count = 0
          for x in xrange(n):
              for y in xrange(1, x):  # note ranges to x, not n
                  count += 1
          return count
      
      def f2(n):
          count = 0
          for x in xrange(1,n/2, 2):
              for y in xrange(1, x/2):
                  count += 1
          return count
      
      def f3(n):
          count = 0
          for x in xrange(1,n):
              for y in xrange(1, n, n/100):
                  count += 1
          return count
      
      def f4(n):
          count = n**2 # note: not setting count = 0
          while (n > 0):
              count += 1
              n /= 2
          return count
      
      def f5(n):
          count = 0
          for x in xrange(1, n):
              count += f4(n)
          return count
      
      def f6(n):
          return f1(f2(n))

   9. For an O(n²) algorithm, if we multiply the input by k, we multiply the runtime by about k².  This ratio becomes more and more accurate as n grows larger.  Let's see that in action.  Try running the following code (using the functions from the previous problem):

      n = 250
      print 1.0*f0(2*n)/f0(n)
      print 1.0*f6(2*n)/f6(n)

      Try all the different functions from the previous problem, and not just f0 and f6.  You may need to adjust the values of n to get meaningful results.  The O(n²) functions should converge on 4, the others on values larger or smaller depending on their function families.  Do these results match the big-oh families from your previous answers?
       

4. Review
   As a group, work through different code tracing and (especially) mystery functions listed in the second part of the practice notes from last week.  In your writeup, include the problems you solved along with their solutions.  Get as far as you can, but work as a group.

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