<HTML>

<HEAD>

<title>Code from Programming Pearls</title>

</HEAD>

<BODY BGCOLOR=#ffffff>

<a href="index.html">

<img alt="book cover" ALIGN=right hspace=20 src="pp2e.jpg">

</a>

<P>

<h1>Code from

<br><font color="#a52a2a">Programming Pearls</font></h1>

<ul>

<a name="col01">

<li>Column 1: Programs for sorting integers

<br><a href="bitsort.c">bitsort.c</a> -- Sort with bit vectors.

<br><a href="sortints.cpp">sortints.cpp</a> -- Sort using C++ STL sets.

<br><a href="qsortints.c">qsortints.c</a> -- Sort with C library qsort.

<br><a href="bitsortgen.c">bitsortgen.c</a> -- Generate random integers for sorting.

<a name="col02">

<P><li>Column 2: Test and time algorithms

<br><a href="rotate.c">rotate.c</a> -- Three ways to rotate the elements of a vector.

<br>The next two program are used in a pipeline to compute all anagrams in a dictionary

<br><a href="sign.c">sign.c</a> -- Sign each word by its letters in sorted order.

<br><a href="squash.c">squash.c</a> -- Put each anagram class on a single line.

<a name="col05">

<P><li>Column 5: Scaffolding for testing and timing search functions

<br><a href="search.c">search.c</a> -- Linear and binary search.

<a name="col07">

<P><li>Column 7: Tiny experiment on C run times

<br><a href="timemod0.c">timemod0.c</a> -- Edit main to time one operation.

<a name="col08">

<P><li>Column 8: Compute the maximum-sum subsequence in an array

<br><a href="maxsum.c">maxsum.c</a> -- Time four algs: n³, n², n log n, n.

<a name="col09">

<P><li>Column 9: Code tuning programs

<br><a href="genbins.c">genbins.c</a> -- Profile this, then try a special-purpose allocator.

<br><a href="macfun.c">macfun.c</a> -- Time the cost of macros and functions.

<br>The column also uses rotate.c (Column 2), search.c (Column 5) and maxsum.c (Column 8).

<a name="col11">

<P><li>Column 11: Test and time sorting algorithms

<br><a href="sort.cpp">sort.cpp</a> -- Mostly C, but also C++ sort function.

<br><a href="SortAnim.java">SortAnim.java</a> -- Animate those sort functions in Java.

<a name="col12">

<P><li>Column 12: Generate a sorted list of random integers

<br><a href="sortedrand.cpp">sortedrand.cpp</a> -- Several algorithms for the task.

<a name="col13">

<P><li>Column 13: Set representations for the problem in Column 12

<br><a href="sets.cpp">sets.cpp</a> -- Several data structures for sets.

<br>genbins.c (Column 9) implements the bin data structure in C.

<a name="col14">

<P><li>Column 14: Heaps

<br><a href="priqueue.cpp">priqueue.cpp</a> -- Implement and test priority queues.

<br>The column also uses sort.c (Column 11) for heapsort.

<a name="col15">

<P><li>Column 15: Strings

<br><a href="wordlist.cpp">wordlist.cpp</a> -- List words in the file, using STL set.

<br><a href="wordfreq.cpp">wordfreq.cpp</a> -- List words in the file, with counts, using STL map.

<br><a href="wordfreq.c">wordfreq.c</a> -- Same as above, with hash table in C.

<br><a href="longdup.c">longdup.c</a> -- Find long repeated strings in input.

<br><a href="markov.c">markov.c</a> -- Generate random text from input.

<br><a href="markovhash.c">markovhash.c</a> -- Like markov.c, but with hashing.

<br><a href="markovlet.c">markovlet.c</a> -- Letter-level markov text, simple algorithm.

<P><li>Appendix 3: Cost Models

<br><a href="spacemod.cpp">spacemod.cpp</a> -- Space used by various records.

<br><a href="timemod.c">timemod.c</a> -- Table of times used by various C constructs.

</ul>

You may use this code for any purpose, as long as you

leave the copyright notice and book citation attached.

<p>

<FONT SIZE=1>Copyright &#169; 1999

<B>Lucent Technologies.</B> All rights reserved.</FONT>

<font size=-2>

Sat 31 Jul 1999

</BODY>

</HTML>