Dan Hirschberg

picture of Dan  Hirschberg

Donald Bren School of Information and Computer Sciences
Professor, Computer Science
Donald Bren School of Information and Computer Sciences
Professor, Electrical Engineering and Computer Science
The Henry Samueli School of Engineering

Ph.D., Princeton, 1975

Phone: (949) 824-6480
Fax: (949) 824-4056
Email: dhirschb@uci.edu

University of California, Irvine
4226 DBH
Mail Code: 3435
Irvine, CA 92697
Research Interests
Design and Complexity Analysis of Algorithms and Data Structures
Research Abstract
Dr. Hirschberg's research has centered in the fields of data structures and the design and analysis of algorithms. Most of his work has concentrated on five areas: common subsequence problems, algorithms using a parallel processor, design of efficient data structures, breakpoint problems and data compression.

Several of the algorithms developed by Dr. Hirschberg formed the basis for many or all subsequent algorithms for those problems. These seminal algorithms include solving the longest common subsequence problem using only linear space, solving the connected components problem on a parallel computer in polylogarithmic time, and asynchronously electing a leader on a ring of n processors using O(n log n) messages.

Dr. Hirschberg's research in the area of data compression has resulted in the development of a simple O(nL)-time algorithm that determines an optimum prefix-free binary code for a weighted alphabet of size n, under the restriction that code strings cannot be longer than L. He has also focused on the case in which an encoder transmits a coded text file to a decoder that has constrained memory resources and developed several algorithms that provide compression performance comparable to state-of-the-art techniques while using significantly less memory.
"Lossless compression of chemical fingerprints using integer entropy codes," with P. Baldi, R. Benz, and S. Swamidass,
Journal of Chemical Information and Modeling, to appear.
"Improved adaptive group testing algorithms with applications to multiple access channels and dead sensor diagnosis," with M.T. Goodrich,
Journal of Combinatorial Optimzation, to appear.
"The minimum size required of a solitaire army," with G.I. Bell and P. Guerro-Garcia,
Integers: Electronic Journal of Combinatorial Number Theory 7, #G07 (2007).
"Improved combinatorial group testing algorithms for real-world problem sizes," with D. Eppstein and M.T. Goodrich,
SIAM Journal on Computing 36, 5 (2007), pp. 1360-1375.
"Serial computations of Levenshtein distances,"
in Pattern Matching Algorithms, A. Apostolico and Z. Galil (Eds.), Oxford University Press, 1997, pp. 123-141.
"Choosing subsets with maximum weighted average," with D. Eppstein,
Journal of Algorithms 24 (1997), pp. 177-193.
"A Fast Algorithm for Optimal Length-limited Codes," with L. L. Larmore,
Journal ACM 37, 3 (1990), pp. 464-473.
"Efficient Decoding of Prefix Codes," with D. A. Leweler,
Communications of the ACM 33, 4 (1990), pp. 449-459.
"Data Compression," with D. A. Lelewer,
Computing Surveys, 19:3 (1987), pp. 261-297. Reprinted in Japanese BIT special issue in Computer Science (1989), pp. 165-195.
Last updated