Name(s) & ID(s):________________________________________________________

Name(s) & ID(s):_________________________________________________________

Assignment P4

CS 100 – Summer 1999

Due: Thursday July 29, 1999 at the beginning of class.
NOTE: YOU MUST WORK WITH A PARTNER ON THIS ASSIGNMENT.

Turn in your assignments according to the instructions given in the first day handout. Remember to include sample output when you turn in your program listings. Also turn in a disk with a runnable version of your code (the same as what you've printed). Remember that you will be graded on both style and correctness.

Problem 0 (5 Points) I have verified my grades up through the Prelim and P2 (posted on the door of 5141 Upson). ___________________________________________________ (both signatures)

Problem 1 (15 Points) (Algorithm Development and Sorting) -- A well-known algorithm called bubble sort proceeds by scanning the list from left to right, and whenever a pair of adjacent keys is found to be out of order, then those items are swapped. In the first pass, the largest key in the list will have "bubbled" to the end, but the earlier keys may still be out of order. Thus, the pass scanning for pairs out of order is put in a loop that first makes the scanning pass go all the way b.length (assuming your input was initially stored in array b) and at each iteration stops it one position sooner. Implement bubble sort and write a main method that demonstrates that it works.

Problem 2 (40 Points) (Sorting) -- Modify the algorithms for selection sort, insertion sort, bubble sort and quicksort to count:

the number of comparisons,
the number of exchanges, and
the number of times each loop is executed.

Write a program that will test your modified algorithms on a representative sample of input (part of this problem is to come up with such a representative sample) and then output to the user the information you gather in a meaningful format such as:

List length list properties # comps # exchanges # loops

Select

Insert

Bubble

Quick

Select

Insert

Bubble

Quick

. . .

It may be the case that you'll come up with a snazzier way to present your output. Go for it. Note: You should use more meaningful variable names and comments in your implementation of these algorithms than what were presented on the slides in class.

Problem 3 (40 Points) (Matlab)

Start up Matlab and do the following problems. Just type the appropriate commands in the command window. For each question, do the assignments and calculations in the order in which they are given. Do not type a semi-colon at the end of any lines unless we tell you to do so. That way the values of the variables and matrices you create will be displayed. Type a return at the end of each line.

What to Turn In: Follow the directions given and turn in a copy of the Matlab command window, any graphs you produce, and all the files you create. The printouts should only show the calculations requested in the assignment; please don't turn in your experiments, false starts, and other work. however, if you make a typo or other small error at some point, you don't need to start over. Just fix the error, and cross out anything you don't want the grader to look at.

Your answers should be in the right order. Please use either Matlab comments (beginning with a % sign) or legible hand-written annotations to number your answers. The command window printout should include the commands used to produce the various plots.

For more information on Matlab, be sure to check out the course website for a handout that provides some Matlab hints and experiments.

Print the powers of 4 from 1 to 10.
Create a vector (array) x that holds the values from 0 to 4*pi in increments of pi/2. Recall that the constant pi is predefined for you in Matlab.
Create another vector y that holds the sins of the values in x.
Consider the following two sets of numbers. The first represents the number of unique hits on a website for a given day, the second represents the number of unique hits plus the number of reloads:

48 64 38 47 29 38

60 73 45 62 43 44

Create two arrays: hits and total containing the number of unique hits and the number of total hits, respectively.
Calculate the means and the median of the two sets of data. Also calculate the number of days where the unique hit count was less than 50.
Produce a single graph showing the unique hits and the total hits for the week represented here. Assume the week starts on Monday. The unique hits should be drawn with a '+' at each data point and a line connecting the points, while the total hits should be drawn with a 'o' at each data point and a line connecting the points. Put appropriate titles and labels on the graph and print it. (Hint: type help plot for details about how to graph vectors; at the bottom are listed associated commands for adding labels and titles. You will need to use the hold command to put multiple plots together.)

Evaluate and plot the function 6x³ - 3x² - x + 1 for values of x from -1 to 1. Be sure to use enough values of x to produce a smooth graph (say, around 100 points, but experiment first). Put a suitable title on the graph, label the axes appropriately, and print it.
Create a 2-dimensional matrix M containing these values:

6 3 -2 5

3 0 4 -6

-5 2 7 -1

Print the second column of matrix M. Print the bottom row of matrix M.
Create a 1D matrix (row vector) whose elements are the sums of the columns of M. Create a 1D matrix (column vector) whose elements are the sums of the rows of M. Use the sum command.
Create a new matrix C that contains the second, first, and fourth columns of M, in that order. Use Matlab operations on M to create N; don't type in the elements again.
Create a new matrix D that has a new row of all ones inserted between the top and middle rows of M. Again, use Matlab operations instead of typing in the elements. You should use the ones command.

g) Create a new matlab function (.m file) called pos. The result of a function call pos(M) should be a matrix of ones and zeros the same size as M, with a one everywhere that m contained a positive integer. For example, if even is called on the M from problem 4, the result would be

1 1 0 1

1 1 1 0

0 1 1 0

Test your function on the following matrix:

5 -3 2 -1

4 1 -5 -6

-2 0 1 3