CS Seminar Series: David W. Matula

Description

David W. Matula, professor emeritus of computer science at Southern Methodist University, will give a seminar talk titled "The Architecture of Algorithms" for the Department of Computer Science.

All in-person events at Johns Hopkins must follow university COVID-19 policies. See current guidelines online. This is a hybrid event; please attend the event virtually by using the Zoom link (email mwade12@jhu.edu for the passcode).

Abstract:

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: (1) are two particular nodes adjacent?, resolved in constant time, (2) 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?