The labs in CSC172 follow a pair programming paradigm. Every
student is encouraged (but not
strictly required) to have a lab partner. Labs will typically have an
even number of components. The
two partners in a pair programming environment take turns at the
keyboard. This paradigm facilitates
code improvement through collaborative efforts, and exercises the
programmers cognitive ability to
understand and discuss concepts fundamental to computer
programming. The use of pair programming
is optional in CSC172. It is not a requirement. You can learn more
about the pair programming
paradigm, its history, methods, practical benefits, philosophical
underpinnings, and scientific validation
Every student must hand in his own work, but every student must list
the name of the lab partner (if
any) on all labs.
This lab has
parts. You and your partner(s) should switch off
typing each part, as explained by your
lab TA. As one person types the lab, the other should be watching over
the code and offering
suggestions. Each part should be in addition to the previous parts, so
do not erase any previous work
when you switch.
The textbook should present examples of the code necessary to complete
this lab. However,
collaboration is allowed. You and your lab partner may discuss the lab
with other pairs in the lab. It is
acceptable to write code on the white board for the benefit of other
lab pairs, but you are not allowed to
electronically copy and/or transfer files between groups.
Quicksort++ (4 parts)
This is Exercise 7.26 of Weiss. Use the quicksort code from the book
(figs 7.2, 7.13 - 7.15, attached as an appendix). You are to remove one of
the recursive calls by
- rewriting the code so that the second recursive call is
unconditionally the last line in quicksort. Do that by reversing the
if/else and returning after the call to insertion sort.
- performing a test so that the smaller subarray is processed by the
first recursive call and the larger subarray is processed by the
second recursive call.
- removing the tail recursion by writing a while loop and
altering left or right as necessary.
- Demonstrate your quicksort works on several examples that span
the range of possible issues.
Experiments (2 parts)
This is Exercise 7.49 of Weiss. Use your quicksort to experiment with
combinations of pivot-finding and cut-offs. Namely, try pivoting on
first, middle, random, median of 3, and median of 5 elements. Try
cutting off the quicksort and switching to insertion sort at values
from 0 to 20. Split up the work evenly. Present your findings elegantly.
Hand in the source code from this lab at the appropriate location on
the blackboard system at
my.rochester.edu. You should hand in a single compressed/archived
(i.e. zipped) file that contains
the following.) You will need to include the images of your plotted
- A README that includes your contact information, your partner's
name, a brief explanation of
the lab (A one paragraph synopsis. Include information identifying
what class and lab number
your files represent.).
Several JAVA source code files representing the work accomplished
for this lab. All source
code files should contain author and partner identification in the
comments at the top of the file.
A plain text file named OUTPUT that includes author information at
the beginning and shows
the compile and run steps of your code. The best way to generate this
file is to cut and paste
from the command line. Also present your experimental results here.
Each section (1-6) accou'nts for 15% of the lab grade (total 90%)
(README file counts for 10%)
Appendix -- Code
This page is maintained by
Last update: 10/13/12