Extending the List Class Lab

Site Index

This lab expects somewhat more sophistication of students than earlier labs for Algorithms and Data Structures: The Science of Computing. Some of the problems students have to solve are more complex, students need to create correctness proofs and performance analyses as well as algorithms and code, and the performance analyses must be phrased as asymptotic times, not concrete operation counts. These factors make the lab both algorithmically challenging and time-consuming.

Algorithmic Issues

Algorithms and Data Structures: The Science of Computing defines a list as a recursive structure, which makes recursion a natural control structure for list algorithms. We thus expect most students to write recursive algorithms to solve the problems in this lab. However, students who have read chapters 8 and 9 of the text will be prepared to design and analyze iterative algorithms if they wish. Instructors who specifically wish to exercise recursion rather than iteration, or vice versa, in this lab should make that requirement clear to students at the start of the lab.

When solved recursively, the problems in this lab expose students to several things that have not been prominent earlier in Algorithms and Data Structures: The Science of Computing. This exposure broadens students’ ability to design and analyze recursive algorithms, but instructors should be prepared for questions arising from it, and should be aware of it as they select exercises to do. For example…

• Some of the algorithms will have execution times not previously encountered in purely recursive algorithms, and the analyses will thus involve recurrence relations of a form new to students. Specifically, checking a list for duplicates has Θ(n²) execution time if students use brute-force searches to identify duplicates, and Θ(n logn) if students sort the list before checking for duplicates. Similarly, many students compute a list’s length within the algorithm for extracting the n^th element, in order to verify that n is no greater than the length — this leads to worst-case execution time that is quadratic in the list’s length.
• Some of the execution time costs of the algorithms may be hidden in “primitive” messages. In particular, if students use find within their duplicate-finding algorithm, their performance analysis needs to take into account the fact that find runs in Θ(n) time, not constant time like most other List messages.
• Several of the algorithms have multiple quantities that change during recursion. This can lead to confusion about which one to use as an induction variable in correctness proofs, or as the parameter in recurrence relations. (In general, any of the changing quantities can be used, as long as students are careful to use only one within any given proof or derivation.) In particular, the n^th element algorithm will probably change both the list’s length and n with each recursive message, and the list equality exercise will change the length of both lists.
• Many algorithms will have multiple base cases. The algorithms that compare elements of a list (checking order and checking for duplicates) handle both empty lists and lists of one element as a base case, because such lists are trivially in order or duplicate-free. The algorithm for extracting every other element of a list also needs to treat empty lists and lists of one element as base cases, but as separate ones — the empty list is the smallest even-length list, and yields an empty result, while one element is the smallest odd-length list and yields a one-element result. Algorithm designs, correctness proofs, and recurrence relations will all have to reflect these multiple base cases. The recurrence relations will generally be such that one of the base cases does not fit the closed form resulting from the other base case and the recursive part — treat this base case as a special case, i.e., give a closed form valid for all parameter values except that one base case.

Time Requirements

Because each exercise involves designing and coding an algorithm, writing a correctness proof, and deriving an asymptotic execution time, this lab is time-consuming both for students and for whoever grades the solutions.

Few instructors will assign all the exercises in a single lab session. Instead, most instructors will probably pick a subset of the exercises for their students to do. Depending on the duration of the lab sessions, and the sophistication of the students, subsets containing between two and four of the exercises are reasonable.

The Equality Testing Problem

The message that tests lists for equality is almost the equals message that every Java class should handle. The only difference is that Java’s equals must accept any object as its parameter, whereas the one in this lab only has to accept a List. We specified our message in this way so that students would not have to know how to discover an object’s class in order to solve the exercise. For students who already know how to do this, however, modifying the exercise to write a fully Java-compliant equals method provides good experience writing code to a robust, real-world, specification.

Copyright © 2004 Charles River Media. All rights reserved.

Revised Aug. 9, 2005 by Doug Baldwin

Site Index