Let’s pursue algorithms with the view of an architect challenged by a major project who is encouraged to create a design that is captivating and memorable for the ages.
For practical “input” we seek compressed data structures providing efficient access to critical operands in formats allowing direct use by the most important operations.
For “output” we must generate visual presentations conveying results that capture audience attention and retention. Consider we must compete with the high budget commercials blanketing the multitude of streaming services.
For “well defined” we seek procedures expressible in a programming language that is efficiently compilable exploiting available computing engines.
For “finite” we must utilize details of the computing engine. For current electronic systems, we seek alternative approaches exploiting the hardware architecture of arithmetic at the binary level. For combinatorial problems the hardware realization of discrete structure operations can provide breakthroughs. Advice: The convenience of employing packages for subproblems is likely bested by AI designs.
We present numerous problems we have used challenging algorithm engineering students to demonstrate their own creative skills in fashioning new procedures. While many of these problems seem irrelevant, their somewhat hidden properties are shown to foster new approaches. In the classroom experience, these problems have identified the most innately creative students.
Examples we shall cover — involving manipulation of data structures, exploiting algorithms in hardware, and reverse engineering — arise from the following challenges, each with their own unique story:
-
Design a data structure for planar graphs that supports both these specifications:
- are two particular nodes adjacent?, resolved in constant time,
- provide access to all adjacencies of any given node, resolved in time linear in the number of adjacencies.
-
Design an algorithm linear in the number of references to a random number generator that supports placing millions or more random points on the surface of a sphere in competitively superior time using currently available arithmetic hardware operations.
-
Which year in the last thousand years has the longest Roman Numeral representation?
Speaker Biography
David W. Matula is professor emeritus of computer science at Southern Methodist University, arriving as Chair (1974-1979) and having served as a professor there since 1974. He received the Ph.D. (’66) in engineering science (Operations Research) from the University of California, Berkeley, following a B.S. (’59) in engineering physics from Washington University, St. Louis. He was named the inaugural Cruse C. and Marjorie F. Calahan Centennial Chair in Engineering in 2016.
His research focuses on the foundations and applications of algorithm engineering with specific emphasis on computer arithmetic and graph/network algorithms. Two-thirds of his publications focus on computer arithmetic and have appeared primarily in the IEEE and computer science literature. He co-authored the research-oriented text Finite Precision Number Systems and Arithmetic published by Cambridge Press, and also holds some 20 patents. His computer arithmetic research has been supported for several decades by federal, state, and corporate agencies, including NSF, Texas ATP, T.I., Cyrix, and the Semiconductor Research Corporation. Professor Matula’s publications on graph algorithms have appeared in a variety of mathematical and scientific journals including J. Chem. Physics, J. Am. Chem. Soc., Comp. and Biomedical Res., and Geographical Analysis.