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

This website is dedicated to free or low cost mathematical material that relates to the study of computer science. We add some entertaining diversions as well! In particular we speculate on the nature of galaxy-spanning civilizations, topics of interest to amateur geologists in San Diego and elsewhere, the Sumac plant family in San Diego (watch out for poison oak), and my favorite bodysurfing area: Torrey Pines State Natural Reserve.

Astronomy/Botany trip in Kofa

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). This course has been written with consideration for the needs of students in the various fields that use linear algebra.

Linear Algebra

Top-down Calculus - a concise course: This course was designed for a UCSD summer program to give high school math teachers extra training in calculus. Many had just begun to teach calculus and were nervous about doing so. One confided that she had fainted when asked a hard quetion. My task was to give them intuitive understanding and confidence. Key ideas are developed and put to use quickly (e.g., the chain-rule on page 11).

Top-down Calculus

Combinatorics for Computer Science: This material assumes an understanding of basic discrete mathematics (CSE 20, 21 at UCSD). The book is a record of topics covered in a course/seminar that lasted for over ten years in the Department of Mathematics, UCSD. It is designed as a series of topics to be introduced by me but presented by the students. Chapter 1 should be read first. After that the various topics are mostly independent. Many are conceptually useful for programming.

Algorithmic Combinatorics

Tensor Spaces - Seminar Resources: The subjects presented here were used to help first year graduate students learn the conceptual and notational skills for using multilinear algebra in various 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. A review of basic linear algebra is included.

Tensor Spaces Seminar

P vs. NP is discussed in Complexity of Algorithms, CSE 101, at UCSD. This course requires our lower division CSE 20, 21 sequence. Traditionally, the P vs. NP classroom lectures give various measures of problem difficulty, in part to help students understand why P vs. NP has defied solution. Here we suggest that a theorem called the Jump Free Theorem (Harvey Friedman) can be used to give an alternative measure of the difficulty of P vs. NP, one that allows for considerable student participation. The proof of the Jump Free Theorem is very advanced, showing that it is independent of the ZFC axioms of set theory. Its statement, however, can be understood at the CSE 20,21 level. Students can be made aware of the ZFC axioms of set theory and ZFC independence with minimal effort (Wikipedia is enouigh here). Establishing a connection between the Jump Free Theorem and the P vs.NP problem requires only CSE 101 level ideas. This connection has many variations the students can explore.

P vs. NP, ZFC, Lattices

Alien intelligent Life: We are faced with a torrent of potentially life changing technologies from computer science: artificial intelligence, virtual reality, androids, neuromorphic engineering, quantum computing, uploading biological life (including humans) to computers, making immortality a reality, making a reality out of the adventures of Star Trek, what to make of UFOs and alien invasions, etc. Here we take look of how alien civilizations capable of all of these things might evolve and how and why they might get in touch with us. Our approach is through story telling - a long tradition for humans.

Advanced Alien Civilizations

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 formations specific to that park are present, are indicated by red hyperlinks (e.g., Eocene). All other time intervals are indicated by black hyperlinks (e.g., Miocene). Links are to the websites of Palaeos, USGS, Wikipedia, etc.

Geology Present or Missing

Online Anza-Borrego geology overview: We give an overview of the geology of the Anza-Borrego Desert State Park, ABDSP. 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. The 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 was 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. Areas of interst involve group theory and combinatorics. efficient listing algorithms. asymptotic analysis. sorting networks. Recent research (click here) concerns ranking and random generation of combinatorial objects and ZFC independence in combinatorics (topic above). 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 (advisor Marvin Marcus). Professional: UCSD, Professor of Mathematics 1965-91; UCSD, Professor Computer Science and Engineering 1991-2004 (retired).

Bibliography

Torrey Pines Bodysurfing Paradise

TORREY PINES STATE NATURAL RESERVE