03-12-2012, 01:36 PM
Data Structures and Algorithms
Data Structures.pdf (Size: 1.07 MB / Downloads: 36)
Introduction
Just as Mathematics is the “Queen and servant of science”, the material covered
by this course is fundamental to all aspects of computer science. Almost all the
courses given in the Computer Science Tripos and Diploma describe structures
and algorithms specialised towards the application being covered, whether it be
databases, compilation, graphics, operating systems, or whatever. These diverse
fields often use similar data structures, such as lists, hash tables, trees and graphs,
and often apply similar algorithms to perform basic tasks such as table lookup,
sorting, searching, or operations on graphs. It is the purpose of this course to give
a broad understanding of such commonly used data structures and their related
algorithms. As a byproduct, you will learn to reason about the correctness and
efficiency of programs.
It might seem that the study of simple problems and the presentation of
textbook-style code fragments to solve them would make this first simple course
an ultimately boring one. But this should not be the case for various reasons.
The course is driven by the idea that if you can analyse a problem well enough
you ought to be able to find the best way of solving it. That usually means the
most efficient procedure or representation possible. Note that this is the best
solution not just among all the ones that we can think of at present, but the best
from among all solutions that there ever could be, including ones that might be
extremely elaborate or difficult to program and still to be discovered. A way of
solving a problem will (generally) only be accepted if we can demonstrate that it
always works. This, of course, includes proving that the efficiency of the method
is as claimed.
Course content and textbooks
Even a cursory inspection of standard texts related to this course should be
daunting. There as some incredibly long books full of amazing detail, and there
can be pages of mathematical analysis and justification for even simple-looking
programs. This is in the nature of the subject. An enormous amount is known,
and proper precise explanations of it can get quite technical. Fortunately, this
lecture course does not have time to cover everything, so it will be built around
a collection of sample problems or case studies. The majority of these will be
ones that are covered well in all the textbooks, and which are chosen for their
practical importance as well as their intrinsic intellectual content. From year to
year some of the other topics will change, and this includes the possibility that
lectures will cover material not explicitly mentioned in these notes.
A range of text books will be listed here, and the different books suggested
all have quite different styles, even though they generally agree on what topics
to cover. It will make good sense to take the time to read sections of several of
them in a library before spending a lot of money on any – different books will
appeal to different readers. All the books mentioned are plausible candidates for
the long-term reference shelf that any computer scientist will keep: they are not
the sort of text that one studies just for one course or exam then forgets.
What is in these notes
The first thing to make clear is that these notes are not in any way a substitute for
having your own copy of one of the recommended textbooks. For this particular
course the standard texts are sufficiently good and sufficiently cheap that there
is no point in trying to duplicate them.
Instead these notes will provide skeleton coverage of the material used in
the course, and of some that although not used this year may be included next.
They may be useful places to jot references to the page numbers in the main texts
where full explanations of various points are given, and can help when organising
revision.
These notes are not a substitute for attending lectures or buying and reading
the textbooks. In places the notes contain little more than topic headings, while
even when they appear to document a complete algorithm they may gloss over
important details.
The lectures will not slavishly follow these notes, and for examination purposes
it can be supposed that questions will be set on what was either lectured
directly or was very obviously associated with the material as lectured, so that all
diligent students will have found it while doing the reading of textbooks properly
associated with taking a seriously technical course like this one.