Algorithms and data structures
- Overview
- Assessment methods
- Learning objectives
- Contents
- Bibliography
- Teaching methods
- Contacts/Info
The knowledge of a procedural programming language is compulsory (as well as the knowledge of the basics of computer architecture).
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 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).
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 lectures deal 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.
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.