Encouraging truck - rough roads ahead!


S. Gill Williamson, Professor Emeritus

Research Area: Algorithmic Combinatorics

gill.williamson AT gmail.com or gill AT cs.ucsd.edu

Web Gill Home

Discrete Math (Lower Division);

Foundations of Combinatorics (Upper Division);


Linear / Multilinear Algebra;

Top-down Calculus ;

Algorithmic Combinatorics;

Tensor Spaces Seminar ;

Lattice Exit Models

SETI: Synthetic Intelligence;

Astronomy/Botany trip in Kofa

Geology Present or Missing;

Geology of Anza-Borrego;

Geology of Oregon;

Sumac plant family ;

Torrey Pines State Natural Reserve;

Bender-Williamson Online Lecture Series: a free, downloadable two quarter or two semester course in discrete mathematics (pdf files). This material was taught by the authors and other faculty to lower division students in mathematics and computer science at the University of California, San Diego. All exercises and many variations of them have been worked on homework and exams by our students.

Discrete Math Courses

Foundations of Combinatorics with Applications: This upper division or beginning graduate course in combinatorics is broken down into basic units in order to make it more flexible as a supplementary text or reference. Numerous exercises with a solutions manual are provided. All files are free, downloadable pdf files. A link to the Dover edition that contains all of this material is provided.

Foundations Combinatorics

A Comprehensive Introduction to Linear Algebra, Broida and Williamson, Addison Wesley 1989, is a book written for upper division undergraduates in mathematics and related fields. We have taken the original MS Word pdf chapter files and converted them to Adobe Acrobat pdf files optimized for web viewing (Creative Commons CC0, 1.0). Material in multilinear algebra is being added to this page, including background material.

Linear/Multilinear Algebra

Top-down Calculus - a concise course: This one-quarter or one-semester calculus course was designed as a part of a UCSD summer program to give high school math teachers extra training in calculus. Key ideas are developed and put to use quickly (e.g., the chain-rule on page 11). This text has been used successfully for UCSD summer school students. All material is free, downlable pdf files.

Top-down Calculus

Combinatorics for Computer Science by S. Gill Williamson (Computer Science Press, 1985): This beginning graduate level course in algorithmic combinatorics focuses on the use of geometric and algebraic structures to compare and classify combinatorial algorithms. The geometric concepts, in particular, are useful in both complexity analysis and practical programming. Topics are in chapter units that are downloadable pdf files. Choose those that relate to your interests.

Algorithmic Combinatorics

Tensor Spaces - Seminar Resources: Provided here are the background materials to help first year graduate students learn the mathematical and notational skills for using multilinear algebra in various mathematical areas (e.g., analysis of algorithms, complexity theory, circuit design, signal processing, big data analytics). This material focuses on the tensor products of vector spaces.

Tensor Spaces Seminar

To Topics (top)

Lattice exit models: We discuss a class of graph theory/ combinatorial problems which we call "lattice exit models." At one level, these problems provide undergraduate level exercises in labeling the vertices and edges of graphs (e.g., depth first search). At another level (theorems about large scale regularities of labels) they provide concrete geometric examples of ZFC independence. We explore some connections beween lattice exit models and the classical subset sum problem. In addition, we engage in some fanciful and entertaining speculaton about analogies between lattic exit models and such concepts as the multiverse in cosmology and the landscape in string theory.

Lattice Exit Models

"Synthetic intelligence" in our discussion refers to civilizations of highly intelligent robots that are artifacts of biologically evolved technological civilizations. I have written some fiction: The Avatars Remember Nothing (short story) and The Observers (short novel) on this subject. Vernor Vinge comments, "S.Gill Williamson's story The Observers is a radical but plausible take on what advanced extra-terrestrail intelligence might really look like. Hint: They're not your grandmother's little green men." -- Vernor Vinge, computer scientist, futurist and science fiction author. For a discussion of synthetic intelligence as it relates to SETI see the referenced articles by Seth Shostak.

SETI: Synthetic Intelligence

Geology Formations Present or Missing: Free field-guide pdf charts with hyperlinks to geological information are given for selected state and national parks. Geological time intervals in the earth's history where park formations are present are indicated by red hyperlinks (e.g., Eocene). These links are to specfic park-related information when possible. Time intervals where formations are missing are indicated by black hyperlinks (e.g., Miocene) to Palaeos, USGS, Wikipedia, etc.

Geology Present or Missing

Online Anza-Borrego geology overview: We give an online overview of the geology of the Anza-Borrego Desert State Park. A reference grid for ABDSP has been added to the SIO Earthguide Map of the San Diego region. This reference grid is also shown over a map of ABDSP which indicates roads and access points for viewing the various geological formations. A field-guide pdf summary chart is provided.

Geology of Anza-Borrego

An overview of the geology of the state of Oregon: This online overview of the geology of the State of Oregon was prepared for a 2009 road trip through western Oregon with a group of friends. USGS Map i 595 (1969) was downloaded and a rough map of the roads and towns of Oregon was drawn over the geology map. The relevant legends for geology were added. A field-guide pdf chart is provided.

Geology of Oregon

Anacardiaceae - Sumac Plant Family: As a docent volunteer at our local park, Torrey Pines SNR, I am charged with explaining the park's natural history. I have prepared this brief training site to introduce visitors to the most evident botanical traits of the Sumac family genera in our area. A compact pocket field guide can be printed out. At a minimum, you should learn how to avoid poison oak!

Sumac plant family

To Topics (top)

Research: A sample of my research interests is here. Items 1, 2, 4 and 6 involve group theory and combinatorics. Items 5, 8, 14 and 15 concern efficient listing algorithms. Item 10 is asymptotic analysis. Items 12 and 13 concern sorting networks. Recent research (click here) concerns ranking and random generation of combinatorial objects. Math geneaology is here. Education: Santa Barbara High School 1953-56; Caltech 1956-60, BS Math; Stanford 1960-62, MS Statistics; Univ. Calif. Santa Barbara 1962-65, Ph.D. Mathematics. Professional: UCSD, Professor of Mathematics 1965-91; UCSD, Professor Computer Science and Engineering 1991-2004 (retired).


Torrey Pines Bodysurfing Paradise


Hlogotop Hheaderon