Algorithms and Data Structures + Laboratory

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

Instructions and suggestions about program and examinations

 

 


Instructions and suggestions

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 project is published on the web. The examination consists in a discussion of the project and in an oral examination. There is no written test (even in case SIFA should report  "esame scritto" for the enrolment). The project text will contain indications about how and when to deliver the project and to stand the examination (usually a few days after delivering the project).

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 210 ≈ 1000 = 103.

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 20. In chapter 21, section 2 may be skipped while it is necessary to know  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.

 


References

[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

 


Project and how to deliver it

See the page  Laboratorio di Algoritmi e Strutture Dati

and contact Stefano Aguzzoli/Marco Frasca



 Last revision: 2010/12/14