Algorithms and data structures
- Overview
- Assessment methods
- Learning objectives
- Contents
- Bibliography
- Teaching methods
- Contacts/Info
The ability to program in a "sequential" environment is required; specifically, the student must master programming in Java (the language used in the course) as well as the basic elements related to the architecture of a computer. The knowledge and skills necessary for a successful learning of this teaching are imparted in the fundamental courses of the first year of Computer Programming and Architecture.
The objective of the exam is to ascertain the acquisition of the knowledge and skills described in the "Learning objectives" section.
The exam consists of a written test and an oral test (in the case of a positive result of the written test). The written test - lasting approximately 120 minutes - includes 5 questions relating to the topics covered in the lesson (6 points available for each question). The positive result (18/30 points) of the written test allows access to the oral test. The oral test consists of a joint vision of the written test in which the student is informed about the correction criteria and called to provide any clarifications, thus allowing the teacher to verify the correctness of the mark assigned, making changes if necessary.
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 is divided into 48 hours of lectures and 24 hours of exercises.
Office hours
Arrange an appointment by e-mail.