Hardcopy submission, which must be identical to electronic submission, may only be handed in at class on the due date, or directly to your TA. Do not place in folder, except between 3:00 and 5:00 on the due date. Please be careful not to let other people see your solution.
Reading: Chapter 7, and Sections 6.1, 12.2, and 17.1, and pages 631 ("Divide-and-conquer strategies") through 635, first paragraph only -- this will describe merge sort.
In addition to the recursive function that each of these assignments requires you to write, you must test the function by calling it from the main function. For example, to test the quicksort function, write a main function that has the user enter numbers into the array, sorts them, and then prints them out.
Informally, the algorithm is to:
However, you also need a base case so it doesn't recurse forever. One way to prevent this behavior is to set a maximum recursion depth. To do so, add as a 7th parameter an integer that decreases by one at each recursive call. The function should check whether this number is too small to do any further recursion.
If you do not remember what Sierpinsky's triangle looks like from class, run the program ~es66/lib/programs/sirpinsky. This takes a moment to run, but it should refresh your memory.
Write a boolean function that answers the question, "Is this string a palindrome?"
The recursive algorithm is:
Before calling the palindrome function, there should be a seperate function called to get rid of all the spaces. You don't have to handle punctuation marks.
Note: Comparing two individual characters can be done with ==.
Here is the pseudo-code algorithm for quick sort. Note that this algorithm cannot handle a list with duplicates (i.e., the same number appearing more than once). You can optionally make a modification to handle this, which would require another base case.
/* Sort the first n values of List */
Quicksort(int List[], int n)
{
int Small[MAXVALS], Big[MAXVALS]; /* These must be local variables */
/* MAXVALS is a constant */
if n is 0 or 1, there is nothing to do (base case)
else {
k = random value in List /* First pick a random location, then
* get the value at that location */
Put all values from List that are smaller than k in a different
array, Small.
Put all values from List that are greater than or equal to k in a
different array, Big.
/* Recursively sort the two arrays: */
Quicksort(Small, size_of_Small); /* Careful, since size < MAXVALS */
Quicksort(Big, size_of_Big);
Append Small and Big together into List. That is, use one or two
loops to put the elements of Small into the List array, and then
add on the elements of Big.
}
}
Each value of n is a different eighth-note. There are four measures, so compute the values of base(n), tenor(n) and alto(n) for the first 32 values of n (0 through 31). These four measures repeat forever. It is a really annoying melody that will be stuck in your head for twelve days.
You can write a program to produce the right values, or you can do it by hand. Below are recursively defined math functions (not C code).
First, the base and tenor part numbers represent half steps, where 0 is middle C. Therefore, -3 is A and 5 is F. 3 is E flat.
foundation(0) = 0
foundation(n) = 5 + foundation(n-1)
m(n) = foundation(RoundDownToInteger(n/8))
base(n) = (( m(n) + 6 ) % 12) - 6
c(0) = 0
c(n) = 2 + c(n - 1)
t(n) = c(n) % 6
tenor(n) = if RoundDownToInteger(n/8) is even, t(n % 8) + base(n)
else base(n)
Second, the alto part numbers are not half steps, but rather are positions
along a major scale, relative to the value of the base(n) note.
This is a major scale starting at the basenote and going up -- the base
note is the tonic of the scale, like the key you are in changes according
to the base note. By the way, the base note is either 0 or 1 -- I think
it is 1 but I forget -- try it both ways to see which sounds better.
q(0,i,j,x) = x
q(n,i,j,x) = if (j==0), q(n-1, i+1, i+1, (-1)x)
else q(n-1,i,j-1,x)
arrow(n) = q(n,0,0,-1)
a(0) = 2
a(n) = a(n - 1) + arrow(n - 1)
alto(n) = if RoundDownToInteger(n/8) is odd, a(n % 8)
else 5
Show your work. You get one point for producing the sequence of notes, or you can get two points for performing (voice, whistle, or playing a tape of) the correct tune in class on the day it is due.
Good luck, may the Force be with you, and don't forget to wear ear plugs.