Tuesday, December 18, 2012
The
second
2012
Derick
Wood
Graduate
Scholarship
has
been
awarded
to
Vinayak
Pathak. Pathak
is
a
PhD
student
at
the
School
who
is
studying
for
his
PhD
with
Prof.
Anna
Lubiw. He
previously
earned
his
MMath
degree
under
the
supervision
of
Prof.
Timothy
Chan.
Vinayak
has
been
studying
a
fundamental
problem
about
the
structure
of
binary
search
trees,
which
are
a
basic
way
of
representing
information
held
in
a
sorted
order. Specifically,
he
is
studying
the
minimum
number
of
operations
called
rotations
that
transform
one
binary
search
tree
into
another. With
his
advisor
Anna
Lubiw,
he
has
shown
a
connection
to
computational
geometry,
and
proved
that
two generalizations
of
the
problem
in
this
domain
are
NP-complete.
The
Scholarship
honours
Professor
Derick
Wood,
who
taught
at
Waterloo
from
1982
to
1992,
and
wrote
two
textbooks,
"Theory
of
Computation"
and
"Data
Structures,
Algorithms,
and
Performance.