*Teachers**: M. Torelli, S. Aguzzoli,
M. Frasca*

** **

It
is necessary to ** enrol** for the exam, using the SIFA system, not
later than a week before the exam date (SOCRATES/ERASMUS students should
contact the teachers). Difficulties about the enrolment should be solved by the
Student Secretary (via Comelico).

The
published ** exam date** is that of the day in which

The
exam must be concluded in the same session of the project: it is not allowed to
deliver the project in a session and to stand the discussion and the oral test
in another session.

In the following we report some *general
suggestions* and the *main topics* dealt with during the 2009/2010 lectures.

First of all, revise *logarithms and powers*
(§3.2 in [2]): it is
of primary importance to be able to approximately compute binary logarithms, e.
g.,

log_{ }_{2}
1.000.000. This computation is useful to determine how many bits are required
to address 1MB of storage, or how big the *stack for Quicksort
*should be. Start from 2^{10 }≈ 1000 = 10^{3}.

It
is essential to understand important concepts – however, it is not easy to
characterize *important *concepts: lectures should help for that! It is
necessary to *understand* proofs and programs, while it is not necessary
to *memorize* proofs and programs.

The
first 18 chapters of [2] have been dealt with almost entirely, but for
the first 3 sections of chapter 5, whose subject is dealt with in other
courses. Several sections of the Appendix VIII are to be used as *reference*:
one has to know results there to understand the analysis of some algorithms.
Sections B.4, B.5 and C.1 (graphs, trees, strings, binomial coefficients) are
important, as well as the so called "birthday paradox" – §5.4.1. For
definitions of *RAM* and *RASP* *machines *and *uniform vs.
logarithmic costs* it is opportune to consult [1] or [5]. The proof of § 4.4 is not required, but theorem 4.1
must be known. Results in
*exercises* 4.4-2 and 4.4-3 are useful. The student must
know *Fibonacci* *numbers *and their *recurrence relation* (cf.
end of § 3.2).

Sections
6.3 and 6.5 are important, but often apparently ignored by students. For an
alternative proof that *a heap can be built in linear time*, cf. a short
paper in English [6]. For the
analysis of the
average case of Quicksort (§7.4.2) the result alone
is required, while the remarks in problems 7-4 (particularly point c: in case
consult [3]) and 7-5
are important. In chapter 8, the *conditions* permitting sorting in *linear*
time should be clear.

In
chapter 9, *worst-case linear-time selection* (§ 9.3) is not required, but
the *result *is useful. In chapter 10 do not forget §10.4. In chapter 11,
the proofs of theorems 11.2, 11.6 and 11.8 are not required, neither is §
11.3.3. Section 12.1 is obviously important: be careful with the definition of
binary search tree! In section 12.4 only the introduction and the result of
theorem 12.4 are required. The results of problems 12-2 and 12-4 should be
known.

*Red-black trees* (chapter 13) are an efficient implementation of 2-3-4 trees, as
explained in [3]:
studying *B-trees (*chapter 18) immediately
after may help. Section 13.4 may be omitted as well as chapter 14.

We
have only dealt with the first three sections of chapter 15. The correctness
proof of Huffman’s algorithm is not required. Section16.4 and theorem 16.11 are
important: for the theorem, the version in [5], §12.3, is more complete and perhaps clearer. Sections
17.3 and table contraction (§17.4.2) may be skipped, but not table expansion.
You may skip chapters 19 and *Ackermann’s*
*function *(cf. [4]) and its use in the complexity
analysis of the *union-find algorithm* (but the proof may be skipped).

In chapters 22 and 23 only the fundamental
notions are required (how to represent graphs, breadth-first and depth-first
search, what is a minimum spanning tree and how to determine it).

We only hinted at P, NP and
NP-complete problems (cf. introduction to chapter 34). In the introduction to
chapter 35 the student will find the notions of *approximation algorithms*
and *ratio bound* and in §35.1 the *approximate vertex-cover *algorithm.

[1] A.V. Aho, J.E. Hopcroft, J.D. Ullman, *The
design and analysis of computer algorithms*, Addison-Wesley, 1974.

[2]
T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, *Introduction to
Algorithms*, Third Edition, MIT press, 2009 (or *Introduzione** agli algoritmi e strutture dati 3/ed*,
McGraw-Hill Italia, 2010)

[3] R. Sedgewick,
*Algorithms in C/C++*, Addison-Wesley, 1993.

[4] A.J. Kfoury, R.N.
Moll, M.A. Arbib, *A programming approach to
computability*, Springer, 1982.

[5] A. Bertoni, M. Goldwurm, *Progetto e analisi di algoritmi (Dispense del
corso)* http://homes.dsi.unimi.it/~goldwurm/algo/

[6]
M. Torelli, *Appunti
per il corso di Algoritmi e strutture dati*

See the page
*Laboratorio
di Algoritmi e Strutture Dati*

and contact Stefano Aguzzoli/Marco Frasca

Last revision:
2010/12/14