Copyright © 2002 Katrin Becker 1998-2002 Last Modified July 2, 2002 02:57 PM
Cpsc 461: On-Line (Papers & course directory) Resources
Articles from Doctor Dobb's Journal:
VARIOUS TOPICS:
The Fastest Sorting Algorithm? Dr. Dobb's Journal April 2000 Sorting n integers in time proportional to n log log n By Stefan Nilsson

Margination and Project Gutenberg Dr. Dobb's Journal May 2000 Setting margins for electronic documents By William Fishburne

HASHING:

HASHING REHASHED Dr. Dobb's Journal April 1996
by Andrew Binstock Even tried and tested algorithms can be more efficient. Andrew presents one optimization, then examines the effect of high-performance hardware on hashing.

Replacing a Dictionary with a Square Root Dr. Dobb's Journal October 2001 By Tom Cargill

SHA: The Secure Hash Algorithm William Stallings

Generating Perfect Hash Functions Dr. Dobb's Journal February 2001 By Thomas Gettys

DATA FORENSICS:
File Recovery Techniques Dr. Dobb's Journal December 2000 Files wanted, dead or alive By Wietse Venema

Bring Out Your Dead Dr. Dobb's Journal January 2001 The ins and outs of data recovery By Dan Farmer

SAMPLE DATA:
Reservoir Sampling Dr. Dobb's Journal January 2001 By Paul F. Hultquist and William R. Mahoney

FILE FORMATS:
The JPEG 2000 Image Coding Standard Dr. Dobb's Journal April 2001 A powerful algorithm and data format By Diego Santa Cruz, Touradj Ebrahimi, and Charilaos Christopoulos

Audio Watermarking Dr. Dobb's Journal November 2001 Burying information in the data By Michael Arnold

Image Authentication for a Slippery New Age Knowing when images have been changed By Steve Walton

A 2-D DDA Algorithm for Fast Image Scaling Dr. Dobb's Journal April 1997 Right-sizing your graphic images By Dean Clark

SEARCHING:
Binary Search: Algorithm, Code, and Caching Dr. Dobb's Journal April 2000 By Jon Bentley

Fast String Searching With Suffix Trees Dr. Dobb's Journal August 1996 Mark R. Nelson

A Practical Suffix-Tree Implementation for String Searches Dr. Dobb's Journal July 2000 By Bogdan Dorohonceanu and Craig Nevill-Manning

Suffix Arrays Dr. Dobb's Journal April 2001 By Jon Bentley

Ternary Search Trees Dr. Dobb's Journal April 1998 by Jon Bentley and Robert Sedgewick When you have to store a set of strings, what data structure do you use? Jon and Robert suggest one place you can start is with ternary search trees, which combine the time efficiency of digital tries with the space efficiency of binary search trees.

The Fibonacci Heap
Dr. Dobb's Journal January 1997 by John Boyer Heaps are usually implemented via binary trees, with the property that for every subtree, the root is the minimum item. Here, John describes how to implement exceptionally fast "Fibonacci" heaps.

Other Papers:

B+Trees:
PDF [paper: proceedings of the 2000 ACM SIGMOD, May16-18, 2000] Jun Rao, Kenneth A. Ross, "Making B+-Trees Cache Conscious in Main Memory"

Cosequential Processing:
article: nyberg, barclay, cvetanovic,gray,lomat "PDF [paper: VLDB Journal, 4, 603-627 (1995) ] "AlphaSort: A Cache-Sensitive Parallel External Sort"

Course Directory Structure:
/home/profs/becker/Courses/461
Asst/ sample solutions, extra files, etc fo specifc assignments
BtreeExp/ on-line demo of B-Trees including insertions, deletions
Code/
sample code that may be of use
Coseq/
a cosequential processing simulation
Data/
data files of different sorts
DataComp/
Data Compression stuff
DocSys/
From a Previous Assignment
Examples/
demo programs of various descriptions
Hashing/
From a Previous Assignment
Misc/
MISCELLANEOUS
Previous/
From Previous Semesters - you don't have access to this
RecordFile/
From a Previous Assignment
SearchEngine/
From a Previous Assignment
Utility/
A small collection of programs and utilities that sometimes come in handy
./Asst:

./BtreeExp:
BTree.jar
BTreeApplet.html
BTreeApplet2.html
rundemo

./Code:

./Coseq:
mergetest

./Data:
./Data/TextFiles:
BinaryCorpus/ // binary files of various sorts
MiscCorpus/ // files of various sorts
NumberCorpus/ // text files containing digits
TextCorpus/ // text files of various sorts
TextFiles/
encycinfo.txt
encyclopedia.txt
names1.txt
names2.txt
names3.txt


./DataComp:

./DocSys:
U2
searchwords
wordgen.csh
wordlist
words.awk

Zero_Sum.txt

./Examples:
Coseq/
DataComp/
Hashing/
TextProc/
binin.cc
binout.cc
binout.txt
lzw-d.cc
lzw-e.cc
t.txt

./Examples/Coseq:
mergetest

./Examples/DataComp:
d
d1
d2
d3
d4
d5
lzw-d
lzw-d.cc
lzw-d2
lzw-d2.cc
lzw-e
lzw-e.cc
lzw-e2
lzw-e2.cc

./Examples/Hashing:
KEYS.dat
bti.cc
crt // demo program for Collision Resolution Techniques
crt.cc
crt2
crt2.cc
findkeys
findkeys.cc
keylist1.dat
keylist2.dat
keys11a
keys11a-cc
keys11b
keys11c
keys29
keys29-bti
keys29-dc
keys800
keys800-bm
keys800-co
keys800-lp
keys991.dat
search29
searchkeys
searchkeys.cc

./Examples/TextProc:
U2 // data file of "uninteresting words"
getfiles.awk
getwords.awk
makefilelist.awk
squish.awk
stripwords.awk
wordgen.csh
words.awk
words.gawk
words1.awk
words2.awk

.
./Hashing:
crt // demo program for Collision Resolution Techniques
crt.cc
findkeys
findkeys.cc
keys11a
keys29

./Misc:
convertall.csh
dton // Decimal - to any base converter
ntod // Any base to Decimal Converter

./RecordFile:
records.data1
records.mods1
records.mods2

./SearchEngine:

./Utility:
convertall.csh
squish.awk
stripwords.awk
wordgen.csh
words.awk
words1.awk
words2.awk


Copyright © 2002 Katrin Becker 1998-2002 Last Modified July 2, 2002 02:57 PM