Algorithms and data structures

Degree course: 
Corso di First cycle degree in COMPUTER SCIENCE
Academic year when starting the degree: 
Academic year in which the course will be held: 
Course type: 
Compulsory subjects, characteristic of the class
Second semester
Standard lectures hours: 
Detail of lecture’s hours: 
Lesson (72 hours)

The knowledge of a procedural programming language is compulsory (as well as the knowledge of the basics of computer architecture).

Final Examination: 

Written test and oral exam. During the course there will be two partial tests that allow a student to be exempted from the (full) written test. The written test (two hours) consists of 5 questions related to the topics of the course (6 points for each question). With a positive result (in the range 18-30) a student can access to the oral exam which consists of a brief discussion on the written test (the student may explain in details its answers so that the teacher can possibly reconsider the vote).

Voto Finale

The course provides the basics of data structures and algorithms design. The main techniques for the design and the analysis of algorithms will be learned, together with the capability of developing programs for classical computing problems.
Knowledge transfer of theoretical results is also considered.

The expected learning outcomes comprise the ability to choose the most suited algorithm or data structure for a given problem, as well as to construct suitable models through problem abstraction.

Furthermore, the student will acquire the ability to deepen his or her knowledge.

The acquisition of the different knowledge and skills expected will proceed in parallel throughout the lectures, dealing with the following topics:

1) Problem formalization, complexity and asymptotic notations (6h)
2) Computation models and cost criterions (6h)
3) Basics of procedural programming languages (2h)
4) Basic data structures (array, matrix, list, stack, queue) (6h)
5) Graphs and trees, representations and visiting algorithms (10h)
6) Sorting: generalities and basic algorithms (4h)
7) Algorithm design: divide et conquer (2h)
8) Sorting: digital methods and advanced algorithms (6h)
9) Heap and Heapsort (2h)
10) Hash tables (4h)
11) Binary search trees (6h)
12) Balanced trees (2-3, 2-3-4, Red-Black) (8h)
13) Partitions and Union-Find operations (2h)
14) Optimization (4h)
15) Dynamic programming (4h)

In addition to slides and lecture notes (provided through the e-learning system), the reference book is:

R. Sedgewick, K. Wayne, Algorithms, 4th Edition, Addison-Wesley Professional 2011.

For an alternative and in depth analysis of all the topics we refer also to
Thomas H. Cormen - Charles E. Leiserson - Ronald L. Rivest - Clifford Stein, Introduction to Algorithms, McGraw Hill education, 2009

The course comprises only lectures (72 hours). Each lecture presents both theoretical and practical aspects, as well as examples. Slides for most of the topics are provided in advance through the e-learning site. Attendance is highly reccomended.

The teacher is available for explanations upon appointment (to be fixed via e-mail) or at the end of the lecture.