Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Chapter 1
Introduction
We shall see how they depend on the design of suitable data structures, and how
some structures and algorithms are more efficient than others for the same task
...

We will start by studying some key data structures, such as arrays, lists, queues,
stacks and trees, and then move on to explore their use in a range of different
searching and sorting algorithms
...

We will not restrict ourselves to implementing the various data structures and
algorithms in particular computer programming languages (e
...
, Java, C , OCaml),
but specify them in simple pseudocode that can easily be implemented in any
appropriate language
...
1 Algorithms as opposed to programs
An algorithm for a particular task can be defined as “a finite sequence of
instructions, each of which has a clear meaning and can be performed with a finite
amount of effort in a finite length of time”
...

Here we shall ignore most of those programming details and concentrate on the
design of algorithms rather than programs
...


Having said that, we will often find it useful to write down segments of actual
programs in order to clarify and test certain theoretical aspects of algorithms and
their data structures
...


These notes will primarily be concerned with developing algorithms that map easily
onto the imperative programming approach
...

This is called pseudocode, which comes in a variety of forms
...

1
...
What is it supposed to do?
2
...
How efficiently does it do it?

The details of these three aspects will usually be rather problem dependent
...
Sometimes that will be based on a particular
representation of the associated data, and sometimes it will be presented more
abstractly
...


For simple problems, it is often easy to see that a particular algorithm will always
work, i
...
that it satisfies its specification
...

In this case, we need to spend some effort verifying whether the algorithm is indeed
correct
...

However, since the number of different potential inputs for most algorithms is
infinite in theory, and huge in practice, more than just testing on particular cases is
needed to be sure that the algorithm satisfies its specification
...

Although we will discuss proofs in these notes, and useful relevant ideas like
invariants, we will usually only do so in a rather informal manner (though, of course,
we will attempt to be rigorous
...
Formal verification techniques are complex and will
normally be left till after the basic ideas of these notes have been studied
...
This will 6 usually depend on the problem instance size, the choice of data
representation, and the details of the algorithm
...

1
...
These notes look at numerous data structures ranging
from familiar arrays and lists to more complex structures such as trees, heaps and
graphs
...
We can do this by formulating abstract
mathematical models of particular classes of data structures or data types which
have common features
...
Typically, we specify how they are
built out of more primitive data types (e
...
, integers or strings), how to extract that
data from them, and some basic checks to control the flow of processing in
algorithms
...
These patterns provide a general structure for
algorithms, leaving the details to be added as required for problems
...
We shall see a
number of familiar design patterns throughout these notes
...
4 Textbooks and web-resources
The introductory material in these notes is important for understanding data
structures and algorithms
...
Books published 10 or 20 years ago are still good and
new books continue to be published every year
...

Wikipedia is a good source of fairly reliable information on all the relevant topics,
but it is important to remember that not everything is necessarily true
...

1
...
Basic data structures such as arrays, linked lists, stacks and
queues are used, as well as the advantages and disadvantages of abstract data
types
...
Three important data structures are trees,
hash tables, and graphs, and efficient algorithms are developed for manipulating
and performing useful operations on them
...




---