CS16, Fall 2009

lab05: ("lab five")
Selection sort on array of ints

Goals for this lab

By the time you have completed this lab, you should be able to:

Write a function to find the index of the maximum element of an array
Use that function to implement selection sort

Prior Skills/Knowledge Needed

The list of skills needed for this lab is essentially the same as that for lab04, so we won't repeat that list in detail.

The only other pre-requisite for this lab is that you should already have introduced to the basic ideas behind how selection sort works. (In Fall 2009, we did this via our field day exercise from 10/28, as well as homework H07.)

This is a pair programming lab!

Work with your assigned pair programming partner on this lab. If you do not have one, consult the TA for your lab and/or your instructor for advice prior to starting.

Pair programming is required for this lab, not optional.
Why? pair programming is a real-world skill that is highly valued by employers.
Feedback from companies that employ UCSB CS and CE grads. They tell us that they want our graduates to get more experience with working in pairs and in groups.
Most students find it helpful and enjoyable
- UCSB student that used pair programming in Spring 2009 in CS10 were surveyed, to ask what advantages of pair programming they experienced.
- 74% indicated "I was able to make better progress on assignments"
- 64% indicated "It helped me learn more"
- 60% indicated "It was more fun that working alone"
- 85% said yes when asked "Based on your personal experience, would you recommend that Pair Programming be used in future introductory programming courses at UCSB?"
There is also evidence in the scientific literature that it improves student learning, and helps you get better grades.

Watch the pair programming video from NC State to prepare

You can find the video "Fun with Pair Programming" at this link. It takes less than 10 minutes to watch it.

http://agile.csc.ncsu.edu/pairlearning/educators.php

How pair programming will work

What you'll do

Just as the in the video "Fun with Pair Programming", you and one other person will sit at a single terminal and write code.

The person at the keyboard is the driver
The person watching over her/his shoulder is the navigator

From the video, you should be familiar with the roles of "driver" and "navigator", and the need for switching roles often. If not, then watch the video.

How you'll be matched with a pair

If there is someone you want to work with, and who wants to work with you, that is fine. But you must attend the same lab section this week and next.
If you haven't already chosen someone to work with, your TA will help to match you up with someone in your lab section.
If there ends up being an odd number, there will be one group of three.

How your pair programming will be evaluated

You'll be asked to evaluate your pair partner, and your pair partner will also evaluate you. These are the questions you'll be asked. You may find it helpful to consider those before you begin work—you certainly want your pair partner to say good things about you.

(Previous experience with pair-programming in courses suggests that 95% of students do end up giving their pair good evaluations—make sure you are part of the 95%!)

1. Did your partner read the lab assignment and preparatory materials before coming to the scheduled lab? [For example, did he/she watch the pair programming video before coming to lab]
2. Did your partner do their fair share of the work?
3. Did your partner cooperatively follow the pair programming model
(rotating roles of driver and navigator)?
4. Did your partner make contributions to the completion of the lab assignment?
5. Did your partner cooperate?

Your pair partners evaluation will be counted as part of your grade for the course.

So please do work with your pair in a constructive way!

Also: know that the vast majority of your grade in this course is still based on individual work, not pair work—so while you do need to try to have the best pair experience possible, in the unlikely event that your experience does not go well, the impact on your grade is limited.

Step by Step Instructions

Step 0: Get your pair assignment from your TA

Your TA will tell you who are are assigned to—or you may get your assignment by email.

Please be patient—depending on who shows up, there may have to be some slight adjustments to pair assignments.

We will try to avoid the situation where someone has to work alone, or in a group of three, but if may be necessary depending on circumstances.

Step 1: Together with your pair partner, complete Homework Assignment H06

H06 is a one-page (back and front) homework assignment to make sure that you and your pair partner:

understand the basic ideas of pair programming
are compatible in terms of schedules

This second item is particularly important. The single biggest obstacle to pair programming—or for that matter and kind of group work in courses—is incompatible schedules. So, this will help us detect that situation up front, and try to resolve it.

If you don't have a copy of H06, you can find links to it on the main course website under "homework".

Turn this in during your assigned lab section. You only need to turn in one copy per pair, but it is best if you BOTH fill it out, and BOTH turn it in.

Step 2: Decide whose account you are going to work in

Note: DO NOT share passwords with each other. That is a violation of your account agreement, and can result in suspension of your computing privileges at UCSB.

Instead, what you should do is:

Decide whose account you are going to work in for today's work session
At the end of every work session, email your C program files (finished or not) to both yourself and your pair partner as an attachment (OR use the scp solution below)
That way, if your pair partner gets hit by a bus, you can continue working without him/her—you aren't 'out of luck'.

A better solution is to use scp to copy the work from person1's account into person2's account with the scp command—here's how:

When you are about to finish working for the day, have person2 log into their CSIL account.
Person2 cd's into their ~/cs16 directory
Person 2 types this command
scp -r person1@csil.cs.ucsb.edu:cs16/lab05 lab05.snapshot.date.time
- replace person1 with person1's CSIL username (e.g. jsmith)
- replace date.time with the date and time (e.g. Oct29.1pm)
- don't include any slashes or spaces in the date.time string—it must be a valid part of a filename.
After you type this command, you'll be prompted for a password. Person1 should type his/her password. Don't share the password, just have person1 type it in person2's window.'
If it works, there will now be a directory called lab05.snapshot.date.time in person2's directory that is a complete copy of the ~/cs16/lab05 directory from person1's account.
- Please read the "final thoughts" below so that you understand what the proper use of this process it—it is a powerful command, but it has the potential to be abused. With great power comes great responsibility.

Ultimately, you should BOTH submit your work via the turnin program, just to be safe

Ideally, it should only be necessary for one of you to submit, provided you put both of your names on the submission.
In practice, we've seen this sometimes results in problems where Joe thinks Bob was going to submit and Bob thinks Joe was going to submit.
So, it is just better if both Joe AND Bob submit the work for grading!

The TA can match up your submission and avoid grading the work twice.

Some final thoughts on this step:

In this class pair programming is permitted on some assignments.
The scp command above could be used to copy code from one account to another on assignments where you are not permitted to work together—but that would be wrong.
So don't do that.

Step 3: Log on to CSIL and create a directory ~/cs16/lab05 on one of your accounts.

If you've forgotten how, consult steps 1 and 2 from lab01.

Step 4: Copying some programs from my directory

The files for this weeks lab can be found here:

http://www.cs.ucsb.edu/~pconrad/cs16/09F/labs/lab05/files

And here:

~pconrad/public_html/cs16/09F/labs/lab05/files/*

You can use the same techniques described in lab04 to copy those into your ~/cs16/lab05 directory. Consult the instructions for lab04 if you don't remember how to do this.

Step 5: Finishing two programs

The object of this lab is finish the programs indexOfMaxWithTests.c and selectionSortWithTests.c, each of which uses the principle of test-driven development that we first worked with in lab02.

The basic procedures is the same as the one you did in lab02 and lab04, so I won't described it again in detail—here's the short explanation.

Start with indexOfMaxWithTests.c

compile the program with "make" and run it
note that all the tests are failing, because there is stub code for the indexOfMax function
replace the code for indexOfMax with some valid code
see the tests pass

You also need to look for any lines with @@@ on them and follow the instructions there.

For indexOfMaxWithTests.c, this includes

adding your name(s) to the header comment
- For pair programming assignments, include both names of the folks in your pair—or all three names if you are a trio.
adding in some extra tests that are currently commented out—these are incomplete, so you have to finish them by hand-calculating the expected value.

Then, repeat this for selectionSortWithTests.c

You will note that selectionSortWithTests.c also contains the function indexOfMax().

For now, you'll have to hand copy the code from your indexOfMaxWithTests.c program into your selectionSortWithTests.c program.
I hope you find this sort of annoying—because if you do, it will motivate you do learn a better way of doing this!
In a future lab, we'll learn how we can factor this out into its own file, so that we don't have to copy code from one program to another after we've already tested it. That will require a bit of extra learning, but in the long run it will save us work. Doing that extra bit of work this week will help you appreciate that point, I hope!

Once both indexOfMaxWithTests.c and selectionSortWithTests.c pass their tests, you are ready for the final check, and for scripting and submitting.

Step 6: Scripting your assignment

The steps for scripting your assignment are similar to those you did for lab04, so I'm not repeating the instructions in detail here. Consult the lab04 description, and do the same sequence of steps, except do it for the two programs you created this week.

If you have any questions about the process, you may consult your TA or instructor—but my hope is that you will find it straightforward.

Your script file should be located in your ~/cs16/lab05 directory and should be called lab05.txt

Use this command to list out the contents of that file:

cat lab05.txt

If it looks ok, you are ready to submit!

Step 7. Submit your assignment using the turnin program on CSIL

To submit your assignment, you need to be in the ~/cs16 directory—one level higher than the previous step (use cd ..)

When you are in inside your cs16 directory, you are ready for the turnin step.

Type the following at the prompt:

turnin lab05@cs16 lab05

If you need detailed information about how turnin works, consult the instructions in lab00 through lab02.

Evaluation and Grading (250 pts total)

Mechanics:
- 10 points: successfully submitting the contents of your lab05 directory
- 20 points: lab05 directory contains required C programs and lab05.txt (a transcript file)
- 20 points: submission is on time and follows submission instructions (i.e. is done via turnin by the Due Date.)
- 20 points: each C file contains a header comment on first line with name "cs16 lab05" and date and name(s) of students submitting the work.
- 20 points all @@@ comments are removed.
- 10 points: transcript file contains everything asked for in the instructions
Programming Tasks (points for correctness and style)
- 50 points—filling in body of indexOfMax function
  - 35 points: filling in the body of indexOfMax (replacing the stub with correct code)
  - 15 points: adding in the extra tests for the d array
- 100 points—filling in body of selectionSort function
  - 10 points: copying code over from indexOfMaxWithTests.c for indexOfMax function
  - 50 points: correctly implementing selectionSort
  - 20 points: correctly reusing the indexOfMax function as part of your selectionSort function.
  - 20 points: adding in the extra tests for the d array in testSelectionSort().

Due Date

You should try to complete this assignment by the end of your discussion section in which it was assigned, i.e. before 8:50am on Thursday 10/22/2009 or before 10:50am, 11:50am, or 12:50pm on Friday 10/23/2009 (depending on which section you are enrolled in.)

If you are unable to complete it by the end of your discussion section you may continue to work on it through the week. During homework H06, you and your pair partner(s) worked out times you could get together through the week, so take advantage of those if needed. Please do your best to have it completed and turnin command finished by 10pm on Wednesday November 4.

If that is not possible—e.g. because you need another chance to meet with your pair partner and the TA, then you may finish it during the following lab on Nov 5, and Nov 6. There is no late penalty for submitting during lab on Nov 5 or 6, but you will be behind, because a new lab will be assigned next week.

So do your best to finish before 10pm November 4th.

Late assignments will only be accepted (with 20 point penalty) up until the time the TA doing the grading is finished with grading and posting a particular assignment. There is no specific guarantee as to the length of that period of time.

After that, a zero will be recorded, and the only option is to make up the points via extra credit.

Copyright 2009, Phillip T. Conrad, CS Dept, UC Santa Barbara. Permission to copy for non-commercial, non-profit, educational purposes granted, provided appropriate credit is given; all other rights reserved.