Professor

Ph.D., UC Berkeley, 1980

My primary interests
involve the efficiency of algorithms, particularly
for problems in combinatorial optimization and graph theory.
These algorithms have been applied to study data
security, stable matching, network flow, matroid optimization,
string/pattern matching problems, molecular sequence analysis, and optimization problems
in population-scale genomics. Currently, I am
focused on string and combinatorial problems that arise in
computational biology and bioinformatics. I served as chair of the computer science
department at UCD from July 2000 until August 2004, and was the
founding Editor-in-Chief of
The IEEE/ACM Transactions of Computational Biology and Bioinformatics until January 2009.

Introduction to The IEEE/ACM Transactions of Computational Biology and Bioinformatics

For a longer
biosketch, see short biosketch

Office: 2125 Kemper Hall (Engineering II)

Phone: (530) 752-7131

E-mail: gusfield@cs.ucdavis.edu

*Please Note: the correct URL for this page is: *http://wwwcsif.cs.ucdavis.edu/~gusfield*
NOT : *http://wwwcsif.cs.ucdavis.edu/gusfield* (note the missing
~) Please bookmark this page for later reference.*

**Godel for Goldilocks -- A variant of Godel's First Incompleteness Theorem**

This is written for the first lecture of an undergraduate course on the Theory of Computation. It only requires knowing what integers, functions, and computer programs are. It is a no frills, no paradox, no analogy, no weird logic notation, to-the-point, proof.

Godel's first incompleteness theorem, Lecture Video 1 About one hour and 15 minutes.

Godel's first incompleteness theorem, Lecture Video 2 About 25 minutes.

The most important algorithm that most computer scientists have never studied. Four video Lectures on the Fast Fourier Transform Algorithm (FFT), and the Discrete Fourier Transform (DFT) that it computes. These are designed for undergraduates. The needed background is: a little high-school trigonometry, familiarity with complex numbers, familiarity with divide-and-conquer algorithms and their time-analyses, and familiarity with recursive programs and algorithms.

The Fast Fourier Transform (FFT)

First Lecture on FFT

22 Minutes. Introduction to the topic via the problem of evaluating a polynomial at n chosen points in O(n log n) time; introduction to a divide-and-conquer approach; the first part of the recursion needed for the solution.

Second Lecture on FFT

57 Minutes. The video here skips a review that was part of the second lecture, and begins where the first lecture ends. It derives the second part of the recusion needed for the divide-and-conquer solution, introducing the use of complex numbers defined on the unit circle.

Third Lecture on FFT

1 hour and 41 minutes. Summary of the whole divide-and-conquer algorithm; naming of the Discrete Fourier Transform (DFT); some standard terminology; explicit connection of the divide-and-conquer algorithm to the Fast Fourier Transform; Introduction of the problem of finding the product of two polynomials; recasting the DFT as a matrix-by-vector multiplication; introduction to the inverse DFT and inverse FFT.

Fourth Lecture on FFT

40 Minutes. The punch line; Solving the inverse problem by FFT; spoiler alert -- the inverse FFT algorithm is a fantasy - its the same as the forward algorithm, but you have to permute the output; summary of the solution using the FFT three times; convolution; class dismissed.

Graduate Algorithms Course Lecture Videos:These are lecture videos for CS 222A taken between fall 2007 and spring 2015. Some of the lectures are supplementary, and were not given in the actual class. This is the required graduate course at UC Davis Computer Science on Design and Analysis of Efficient Computer Algorithms.

Undergraduate Algorithms Course Lecture Videos:These are lecture videos for CS 122A taken in fall 2010. This is the required undergraduate course at UC Davis Computer Science on Design and Analysis of Efficient Computer Algorithms.

The webpage for ECS 122 in Winter 2013 is www.cs.ucdavis.edu/~gusfield/cs122w13

ECS 122 Winter 2013, Design and Analysis of Algorithms

FOR CS 122A FALL 2015 First video on memoization in the matrix chain multiplication problem Lecture for CS 122A Fall 2015. The video has some frames that don't capture the whole board, but if you listen to what I say as I am writing, you will understand what you don't see. The video might take a few minutes to download.

Second video on memoization in the matrix chain multiplication problem Lecture for CS 122A Fall 2015. The video has some frames that don't capture the whole board, but if you listen to what I say as I am writing, you will understand what you don't see. The video might take a few minutes to download.

The webpage for ECS 225 in Winter 2012 is www.cs.ucdavis.edu/~gusfield/cs225w12

ECS 225 Winter 2012, Graph Theory and Algorithms

The webpage for ECS 120 in Fall 2011 is www.cs.ucdavis.edu/~gusfield/cs120f11

ECS 120 Fall 2011, Theory of Computation

The webpage for ECS 224 in Fall 2011 www.cs.ucdavis.edu/~gusfield/cs224f11

ECS 224 Fall 2011, Algorithms for Strings and Computational Biology

Fall 2009 - The website for the class ECS 224, String Algorithms and Computational Biology Algorithms, is www.cs.ucdavis.edu/~gusfield/cs224f09

ECS 224 Fall 2009

Since Spring 2000 I have been teaching an undergraduate course CS 124

Theory and Practice of Bioinformatics. See The Expanded Syllabus for CS124 for more information.

The current (Spring 2008) class webpage .

Bioinformatics Course Lecture Videos:Lecture Videos for Fundamental Algorithms in Bioinformatics

These are lecture videos for CS 124 mostly taken in 2002 (with editing and some new material in 2014). For the topics covered, they are still surprisingly current. Clicking will open a menu for the lectures. Synopses of the lectures can be found at: Synopses of Bioinformatics Lecture Videos

## Some Recent Publications

For selected recent publications: recent publicationsSome Errata for Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology can be found in Errata.

## Some Recent Talks

For powerpoint of some recent talks: some recent talks

## Software developed at UC Davis in my group

The software developed here covers a range of topics in computational biology and sequence analysis, and often accompanies papers published on the methodologies behind the software. Available software

February, 2015