Daniel G. Brown
David R. Cheriton School of Computer Science
University of Waterloo
Ph.D. (Computer Science), Cornell, 2000
S.B. (Mathematics with Computer Science), MIT, 1995
Me, with chickenpox spots, February 2007. Not pleasant.
An ever-growing set of astonishingly
adorable photos of River, our new puppy, who came home in August, 2021
Many cute photos of our previous
who died in January 2018 after a life full of wagging and snuggling
A formal photo of me from early 2005, which I
really liked; I don't look much like this anymore
A photo from when I was in grad school. People sometimes
are surprised that this photo is here, but I think it's fun to
remember where we come from.
I perform research on bioinformatics, music information retrieval and computational
You may find my CV in .pdf
or HTML versions here. My Google
Scholar page lists my publications. The summaries below don't link
to papers, but they should all be in my Scholar record; if it's
confusing, let me know.
- Phylogenetics: QTree and LSHtree are two very fast algorithms for
phylogenetic tree reconstruction that I designed with Jakub
QTree uses a complex search structure and a neat random
walk approach to add new taxa to a growing tree,
with O(n log n) runtime in a quartet
LSHtree adds new taxa to a growing tree by using hashing to
approximately locate the taxon, and then doing quartet queries to place
the taxon. It offers the first sub-quadratic runtime for an algorithm
that reconstructs trees in a Markov model of evolution.
As part of proving one of the theorems in the first QTree paper, I
needed a tail inequality for negative bionomial random variables. I
couldn't find any good links for "negative binomial Chernoff", so I
spent forever proving something that should've been
obvious. Now you don't need to. (And yes,
this is sort-of in the Dubhashi/Panconesi book, but not with the
emphasis it might have had.)
- Robustness to outliers: Margareta Ackerman and David Loker and I
adapted some of their theoretical work on clustering to look at what
kinds of properties various phylogenetic algorithms satisfy.
- Sequence correction: I have done two separate projects in this
Pollux is a sequence-correction method for
large sets of second-generation sequence reads, developed by Eric
Marinier and Brendan McConkey and me.
an alarmingly heavily-cited, very fast algorithm for fixing overlapping reads
sequenced from, for example, ribosomal genes. Because the method is so
fast, and because
Andre Masella's code is very
solid, it is easily incorporated without
pain into other pipelines for metagenomic analysis.
- I have also worked on alignment, gene finding, haplotype inference,
motif finding, HMM decoding, HIV subtype detection, kinship discovery,
and a host of other bioinformatics problems. If it's NP-hard
and a sequence or tree problem, there's a good chance I have studied
why it's easy to solve in practice, and I might have developed a
surprisingly fast algorithm for it.
- Music and lyrics
- RhymeAnalyzer: My former MMath student Hussein Hirjee and I
developed an algorithm for detecting rhymes in rap music lyrics.
They're interesting because they tend to be long, internal, and
imperfect. The program is on SourceForge; Hussein has finished
his MD (yes, really) at the University of Western Ontario, and is now a
resident in psychiatry in Toronto.
- Rhyme complexity: Abhishek Singhi noticed that the RhymeAnalyzer
can be used to predict which songs are successful. Gratifyingly, the
more successful songs have more complex rhyme patterns, according to
- Alignment: With a group in France, I adapted BLAST-style
bioinformatics seeding of alignment to the cover song detection
problem. With a group in the Netherlands, we are also exploring use of
multiple alignment in this same domain.
- We've also studied some cross-cultural aspects of music lyrics and
their understanding, and also whether poetry and lyrics differ.
- Computational creativity
- Computational creativity is the study of computer programs that
create artifacts that, if created by a human, would be perceived to be
creative artifacts. Most of my work in this area has been with my
recently-graduated PhD student Carolyn Lamb (co-supervised with
Charlie Clarke), who
studied how to make computer programs that make poetry, and what it means
to make a good computer poet. Among the outcomes of that work are a
quite detailed tutorial of different ways to understand creativity and
how that impacts on the ways of evaluating it, and several papers on news
poets of different sorts that we built.
- Problem gambling
- Largely because of my concerns about casino gambling, I've recently
affiliated with the
Gambling Research Lab at Waterloo. We're doing a lot of work on
trying to get good information about how slot machines work into players'
hands, currently culminating in a project to (essentially) put calorie
labels on slot machines. We have also studied a variety of other
gambling methods, like scratch tickets and bingo.
These are the courses I have taught at UW:
- Introduction to
Computer Science 2 (CS 116), a course I
developed and co-ordinated, and taught in its initial offering in
- Computational techniques in biological sequence analysis (CS 482/682), a course I developed
and co-ordinate, which I have taught eight times.
- Designing Functional Programs (CS 135)
- Algorithms (CS 341)
- Theory of computation (CS 360), which I have taught five times.
- Algorithmic methods in phylogenetics (CS 798)
- Markov Chains, Mixing Times and Concentration (CS 798)
- Advanced topics in bioinformatics: large-scale sequence analysis (CS 882)
Regrettably, I haven't taught much in the past several years; see the
next section for the primary reason why I haven't.
I have a bad habit of saying "yes", which has resulted in my serving in a
number of administrative roles. Recently, I have explored the experience
of saying "no". I recommend it.
For the 2020-2021 pandemic year, I served as president of the Faculty Association (FAUW).
Prior to being FAUW president, I was treasurer for
four years. I was also FAUW's board member at the Ontario
Confederation of Universiy Faculty Associations (OCUFA), which is a bit
ironic considering that six years ago, I was Waterloo's Academic
Colleague to the Council of Ontario Universities. I similarly served as
FAUW's representative to the Canadian Association of University Teachers (CAUT).
From July to December of 2018, I served as Acting Director of the School,
chairing numerous School committees, interacting with external groups and
funders, representing CS within the university and Math Faculty, and
providing direction to staff and (sometimes) to faculty.
For over four years, in three chunks between July 2013 and August 2019, I served as
Director of Undergraduate Studies for CS. As
DUS, I chaired the curriculum committee and was responsible for
undergraduate operations. I also directed the undergraduate staff,
working closely with their manager, Fenglian Qiu.
From July, 2011 to June, 2013, I was Associate Director of the School,
which means that I acted as Director
when the School's Director, David Taylor,
was away, and also meant that I chaired a variety of School committees.
From July 2006 to June 2009, I was the School's Director of First-Year
Studies. As a role without much portfolio, this mostly meant I served in
several School and Faculty committees, with a particular eye on first-year curricula.
From February 2013 until June 2014, I was Waterloo's Academic Colleague to the Council of Ontario
Universities, which means I met most of the university presidents in
Ontario, more than any other thing.
From 2008 to 2014, I served
on the University Senate and (in various years) its Finance and Executive
Committees. As FAUW president, I again served on Senate and Senate Executive, ex officio.
From 2010 to 2014, and for the first half of 2016 and of 2018, I was a member of the Faculty
Association's Status of Women and Equity Committee, recently renamed
the Equity Committee; I was also
the representative from FAUW or from SWEC to a number of diversity-related
committees on campus.
I've decided to put these on their own page. You can find out more about
me as a person here.
And finally, I am not the bestselling author Dan Brown, nor are we
related. I don't like his writing. We have corresponded in the past, but
that was long ago. Please don't send me fan mail or threats.
David R. Cheriton School of Computer Science
University of Waterloo
200 University Ave., W.
Waterloo, ON N2L 3G1, Canada
voice: 519-888-4567 x36278
last updated 2 july 2016