The objective of the course is the introduction of the basic concepts for the design and analysis of algorithms and data structures. The course will illustrate the main data structures and will focus on some specific algorithms, also analyzing their computational complexity.
Expected learning outcomes
The student will know and will be able to use the main data structures and algorithms studied during the course. The student will also be able to propose adequate algorithmic solutions to simple problems, using the most appropriate data structures, and will be able to estimate the computational complexity of the proposed solution.
Lesson period: First semester
(In case of multiple editions, please check the period, as it may vary)
1. Introduction Basic concepts. Analysis of algorithms, space and time complexity of recursive and non-recursive algorithms. Asymptotic notations.
2. Abstract data types Lists, Stack, Code: definition and operations. Implementation (arrays, pointers) and advantages / disadvantages.
3. Sorting Problem. Insertion sort, heapsort, quicksort, mergesort: description and analysis of complexity.
4. Hashing Direct hashing. Hash functions. Collisions.
5. Trees Basic concepts and definitions. Visiting techniques (inorder, preorder, postorder). Search, insert, and delete operations. Implementation techniques. Binary search trees: definition, representation, operations. Red-black binary trees: definition, representation, operations.
6. Management of data on external memory Problems. B-trees: definition, properties and advantages. Execution of search, insertion and deletion operations. Merge and split operations.
7. Graphs. Oriented and non-oriented graphs: definitions and basic concepts. Implementation techniques. Minimum path in weighted graphs: problem and solutions. Visiting algorithms (BFS and DFS). Examples of DFS and BFS applications. Graph matching.
8. Recursion Definition of direct and indirect recursion. Tail recursion technique.
The exam consists of a written test that includes both theoretical questions and exercises. The written test, lasting two and a half hours, aims to verify the preparation and understanding of the subject. The evaluation, expressed in thirtieths, will take into account the correctness, completeness and clarity of the answers to the theoretical questions and the ability to reason and use the knowledge acquired for solving the exercises. The exam is closed book. The results of the written tests will be communicated through the publication of a pdf file on the Ariel website of the course.