Assignment 7

Due on Friday 2nd May

You should submit solutions to this h/w via the cms system by 11pm on Friday. Full credit may be obtained by doing question 4 plus any two of questions 1, 2 and 3. (I recommend that you think about the one you might choose to omit submitting, though you're encouraged to save time by not doing all three of them fully!) Since question 4 is the only one requiring a working program, this will carry twice the weight of each of the other questions to reflect the additional time swallowed by programming.

Question 1: Threaded trees, and min-max heap

  • Do question 4.50 (page 165) from the textbook.
  • Do parts a, b, and c of question 6.18 (page 240) from the textbook. (You might like to think about parts d and e.)

Question 2: Multiplying sparse polynomials, and sorting fractions

  • Do question 5.11 (page 195) from the textbook (use a chained hash table for the merging), but answer this by stating your proposed algorithm carefully -- no completed running Java program is needed for this homework.
  • Do question 7.37 (page 288) from the textbook.

Question 3: Graph algorithms

Do questions 9.11 (page 375), 9.15 (page 376) and 9.13 (page 375).

Question 4: GUI and midi interaction

Enhance question 3 from hw6 by allowing any note of any of the two or three concurrent tunes to be randomly detuned (instead of restricting the detuning to only one voice), although if there are three voices then only detune at most one voice at any one time). If you had an awkward interface last time, or the 'held note' approach you took was 'inelegant', then try to clean that up this time. Finally, you should add a graph drawing window (in the sense of graphs of functions, not nodes and edges!) to show Lissajous figures; in the case of just two voices then you only need one graph, in the case of three voices you'll need to display three graphs (voice 1 vs voice 2, voice 1 vs voice 3, and voice 2 vs voice 3). Rather than attempt to draw these graphs based on the 'actual' sound of the simulated midi instrument, you should take the vastly simpler approach of using the fundamental frequencies of these notes, and assuming pure sine wave sounds, draw graphs of one sine wave (voice 1) vs another (voice 2). Assume that A = 440 Hz (note 69), and that the non-pitch-bent steps are 2^(1/12) (eg from A to A#).