Dan Hirschberg
Professor Emeritus, Computer Science
Donald Bren School of Information and Computer Sciences
Donald Bren School of Information and Computer Sciences
Ph.D., Princeton, 1975
University of California, Irvine
4226 DBH
Mail Code: 3435
Irvine, CA 92697
4226 DBH
Mail Code: 3435
Irvine, CA 92697
Research Interests
Design and Complexity Analysis of Algorithms and Data Structures
Websites
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
"From discrepancy to majority", with D. Eppstein,
Algorithmica 80:4 (2018) 1278-1297.
Algorithmica 80:4 (2018) 1278-1297.
"Improved adaptive group testing algorithms with applications to multiple access channels and dead sensor diagnosis," with M.T. Goodrich,
Journal of Combinatorial Optimzation, 15:1 (2008) 95-121.
Journal of Combinatorial Optimzation, 15:1 (2008) 95-121.
"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).
"Lossless compression of chemical fingerprints using integer entropy codes," with P. Baldi, R. Benz, and S. Swamidass,
Journal of Chemical Information and Modeling, 47:6 (2007) 2098-2109.
Journal of Chemical Information and Modeling, 47:6 (2007) 2098-2109.
"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
https://faculty.uci.edu/profile/?facultyId=2339
https://faculty.uci.edu/profile/?facultyId=2339
Last updated
07/07/2022
07/07/2022