Algorithms and data structures
Knowledge of a procedural programming language together with the basics of computer architecture.
Course description and learning objectives:
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.
Final assessment
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-6 questions related to the topics of the course. With a positive result (in the range 18-30) a student may either register the vote or access to the oral exam which is organized in two phases:
• A discussion on the written test (the student may explain in details its answers so that the teacher can possibly reconsider the vote);
• An in-depth analysis of some topics of the course.
A brilliant oral exam may lead to a brilliant final vote also in case of a just enough written test.
• Problem formalization, complexity and asymptotic notations (6h)
• Computation models and cost criterions (6h)
• Main characteristics of procedural programming languages (2h)
• Basic data structures (array, matrix, list, stack, queue) (6h)
• Graphs and trees, representations and visiting algorithms (10h)
• Sorting: generalities and basic algorithms (4h)
• Algorithm design: divide et conquer (2h)
• Sorting: digital methods and advanced algorithms (6h)
• Heap and Heapsort (2h)
• Hash tables (4h)
• Binary search trees (6h)
• Balanced trees (2-3, 2-3-4, Red-Black) (8h)
• Partitions and Union-Find operations (2h)
• Optimization (4h)
• Dynamic programming (4h)
1)R. Sedgewick, K. Wayne, Algorithms, 4th Edition, Addison-Wesley Professional 2011
2) slides and lecture notes provided by the teacher through the e-learning platform.