Data_Structures_and_Algorithms_2001_Richards.pdf

(1095 KB) Pobierz
Data Structures and Algorithms
CST IB, CST II(General) and Diploma
Martin Richards
mr@cl.cam.ac.uk
October 2001
Computer Laboratory
University of Cambridge
(Version October 11, 2001)
1
Acknowledgements
These notes are closely based on those originally written by Arthur Norman in
1994, and combined with some details from Roger Needham’s notes of 1997.
1
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.
Most problems, even the simplest, have a remarkable number of candidate
solutions. Often slight changes in the assumptions may render different methods
attractive. An effective computer scientist needs to have a good awareness of the
range of possiblities that can arise, and a feel of when it will be worth checking
text-books to see if there is a good standard solution to apply.
Almost all the data structures and algorithms that go with them presented
here are of real practical value, and in a great many cases a programmer who failed
to used them would risk inventing dramatically worse solutions to the problems
addressed, or, of course in rare cases, finding a new and yet better solution —
but be unaware of what has just been achieved!
Several techniques covered in this course are delicate, in the sense that sloppy
explanations of them will miss important details, and sloppy coding will lead
2
2 COURSE CONTENT AND TEXTBOOKS
to code with subtle bugs. Beware! A final feature of this course is that a fair
number of the ideas it presents are really ingenious. Often, in retrospect, they
are not difficult to understand or justify, but one might very reasonably be left
with the strong feeling of “I wish I had thought of that” and an admiration for
the cunning and insight of the originator.
The subject is a young one and many of the the algorithms I will be covering
had not been discovered when I attended a similar course as a Diploma student
in 1962. New algorithms and improvements are still being found and there is a
good chance that some of you will find fame (if not fortune) from inventiveness
in this area. Good luck! But first you need to learn the basics.
2
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.
Corman, Leiserson and Rivest, “Introduction to Algorithms”.
A
heavyweight book at 1028 pages long, and naturally covers a little more
material at slightly greater deapth than the other texts listed here. It in-
cludes careful mathematical treatment of the algorithms that it discusses,
and would be a natuaral candidate for a reference shelf. Despite its bulk and
precision this book is written in a fairly friendly and non-daunting style,
and so against all expectations raised by its length it is my first choice
suggestion. The paperback edition is even acceptably cheap.
Sedgewick, “Algorithms”
(various editions) is a repectable and less daunting
book. As well as a general version, Sedgewick’s book comes in variants
3
which give sample implementations of the algorithms that it discusses in
various concrete programming languages. I suspect that you will probably
do as well to get the version not tied to any particular language, but its up
to you. I normally use the version based on C.
Aho, Hopcroft and Ullman, “Data, Structures and Algorithms”.
An-
other good book by well-established authors.
Knuth, “The Art of Computer Programming, vols 1-3”.
When you look
at the date of publication of this series, and then observe that it is still in
print, you will understand that it is a classic. Even though the presentation
is now outdated (eg. many procedures are described by giving programs
for them written in a specially invented imaginary assembly language called
MIX), and despite advances that have been made since the latest editions
this is still a major resource. Many algorithms are documented in the form
of exercises at the end of chapters, so that the reader must either follow
through to the original author’s description of what they did, or to follow
Knuth’s hints and re-create the algorithm anew. The whole of volume 3
(not an especially slender tome) is devoted just to sorting and searching,
thus giving some insight into how much rich detail can be mined from such
apparently simple problems.
Manber, “Introduction to Algorithms”
is strong on motivation, case sudies
and exercises.
Salomon, “Data Compression”
is published by Springer and gives a good
introduction to many data compression methods including the Burrows-
Wheeler algorithm.
Your attention is also drawn to
Graham, Knuth and Patashnik “Con-
crete Mathematics”.
It provides a lot of very useful background and could well
be a great help for those who want to polish up their understanding of the mathe-
matical tools used in this course. It is also an entertaining book for those who are
already comfortable with these techniques, and is generally recommended as a
“good thing”. It is especially useful to those on the Diploma course who have had
less opportunity to lead up to this course through ones on Discrete Mathematics.
The URL
http://hissa.ncsl.nist.gov/~black/CRCDict
by Paul Black is
a potentially useful dictionary-like page about data structures and algorithms.
3
Related lecture courses
This course assumes some knowledge (but not very much detailed knowledge)
of programming in traditional “procedural” language. Some familiarity with the
C language would be useful, but being able to program in Java is sufficient.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin