Burt Rosenberg

Problem Set 4 _{Due: 11 October, 1994}^{Out: 29 September, 1994}

Goals

Practice in deletion in linked list, an introduction to the analysis of algorithms, and to heuristics in algorithm design.

Reading Assignment

Read chapters 13 and 14 in Condensed Pascal. Chapter 13, Analysis of Algorithms, places in a larger context the in class discussion of the unique words program’s quadratic run time. Chapter 14 discusses preconditions, postconditions and invariants.

Programming Assignment

The unique words program of Problem Set 3 scans the list of unique words for each new word encountered. The most common words occur soon after the beginning of the text, and hence are found near the end of the list. For this reason, the program runs slowly.

A heuristic is an algorithm which tends to work although cannot be guaranteed to work. The move-to-front heuristic tries to optimize the list of words, moving popular words to the front of the list. It does this automatically. Each time a word is matched on the list, it is removed from its current position and reinserted at the head of the list.

This algorithm is only a heuristic. It can be made to work poorly on diabolically designed data sets, but never worse than a factor of two compared to our old algorithm. On typical inputs, the common words will cluster at the front of the list, improving by a large factor the time required to find a majority of the words.