Instructor Notes

Advanced Recursion with Line Drawings Lab

Supplemental Material for Baldwin and Scragg, Algorithms and Data Structures: The Science of Computing; Charles River Media, 2004 (Now published by Cengage Learning)

Integrating the Lab into a Course

Instructors may use all of the exercises in the student directions in a single lab, or may pick a subset. In the former case, the lab will probably be slightly long for the two-hour nominal lab session.

Instructors who wish to customize the lab may consider using exercises15.16 and 15.17 from Algorithms and Data Structures: The Science of Computing as additional or substitute exercises.

Many students will be able to write the code for fractal Ts, bushes, and stars rather quickly. Thus a lab based solely on these exercises will probably be relatively short. However, the idea of replacing a line segment in a simple figure with a recursively more complicated figure (as in skylines or exercise 15.16’s Koch curves) can be hard for some students to grasp, and so including these exercises in the lab will probably make it take longer. Finding closed forms for the number of movePen messages that the algorithms send may also be hard for some students, particularly if they haven’t worked with geometric series before. It will be helpful for students to do these analyses during the lab session, where they can get help from, or discuss their work with, teaching staff.

Comments on Individual Exercises

Fractal Ts are very similar to other tree-like line drawings, in particular the “line-drawing trees” in the “Intermediate Recursion with Line Drawings” lab. For this reason, fractal Ts make a good warm-up exercise for this lab, but may not be very challenging to students who have seen similar algorithms.

Bushes are quite similar to the recursive trees described in chapter 15 of Algorithms and Data Structures: The Science of Computing. It also turns out that the code for bushes and stars is very similar, even though the definitions and figures look somewhat different.

Students often need help figuring out the geometry of skylines. In particular, students may have trouble figuring out the angle at which the pen should move from a displaced midpoint to the second end of the original baseline.