## Dan Hirschberg

Professor

Donald Bren School of Information and Computer Sciences

Donald Bren School of Information and Computer Sciences

Professor, Computer Science

Donald Bren School of Information and Computer Sciences

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

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

**URL**

**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.

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.

Publications

"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.

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.

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).

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.

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.

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.

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.

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.

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.

Computing Surveys, 19:3 (1987), pp. 261-297. Reprinted in Japanese BIT special issue in Computer Science (1989), pp. 165-195.

**Link to this profile**

**Last updated**

10/26/2007