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 |
||||||||||||||||||
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. |
||||
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. |
||||
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! |
||||
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). |
||||