Unit ALGORITHMS AND DATA STRUCTURES WITH LAB
- Course
- Informatics
- Study-unit Code
- 55100615
- Curriculum
- In all curricula
- Teacher
- Maria Cristina Pinotti
- CFU
- 15
- Course Regulation
- Coorte 2020
- Offered
- 2021/22
- Type of study-unit
- Obbligatorio (Required)
- Type of learning activities
- Attività formativa integrata
ALGORITHMS AND DATA STRUCTURES WITH LAB - I MODULE
Code | 55100609 |
---|---|
CFU | 9 |
Teacher | Maria Cristina Pinotti |
Teachers |
|
Hours |
|
Learning activities | Caratterizzante |
Area | Discipline informatiche |
Academic discipline | INF/01 |
Type of study-unit | Obbligatorio (Required) |
Language of instruction | Italian |
Contents | Design and analysis of algorithms. Sorting algorithms with/out comparisons. Data structures: heaps, hash tables, trees. Representations and elementary operations on graphs. Minimum spanning trees. Shortest path for single source and for each pair of vertices. |
Reference texts | T. H. CORMEN, C. E. LEISERSON, R. L. RIVEST, C. STEIN Introduction to algorithms, McGraw-Hill, 2010, ISBN-13: 978-0262533058 M. T. GOODRICH, R. TAMASSIA, Algorithm Design and Applications, Wiley, December 2014, ©2015, ISBN : 978-1-119-02861-1 Panos Louridas, Real-World Algorithms: A Beginner's Guide (MIT Press), ISBN: 9780262035705 |
Educational objectives | Abilities in evaluating the efficiency of algorithms. Knowledge of foundations of algorithms and data structures. Medium algorithms on graphs. |
Prerequisites | Elements of Calculus, Discrete Mathematics and a programming language. |
Teaching methods | Lectures in class. |
Other information | Attendance is expected. |
Learning verification modality | Written and oral tests (only oral during the pandemic) The written test requires solving four exercises (usually, 8 points each). The oral examination covers all course content program and consists both in questions about the theory and in the solution of exercises. Its length is about 20-25 minutes. The final grade is based on both grades in the written and oral examinations (different rule during the pandemic) The students that regularly attend the class can take three partial exams. In any case, there is a final oral exam to allow the students to regain results that were not completely positive or in general to improve on their overall performance. |
Extended program | Mathematical Foundations. Principles for evaluating algorithms: correctness, space and time complexity in the worst and average case. Divite-et-impera. Recurrences. Master Theorem for solving basic recurrences. Sorting algoritms: InsertionSort, QuickSort, MergeSort, HeapSort, CountingSort, RadixSort. Lower bound techniques. Lowerbound for sorting based on comparisons.Selection in linear time. Graphs: representation, depth first search and breadth first search. Directed and undirected graphs. Directed acyclic graph. Topological order.Algorithms for Minimum Spanning Tree, for the shortest paths problem. Several implementation of the Dijkstra algorithm. |
ALGORITHMS AND DATA STRUCTURES - II MODULE
Code | 55107606 |
---|---|
CFU | 6 |
Teacher | Maria Cristina Pinotti |
Teachers |
|
Hours |
|
Learning activities | Caratterizzante |
Area | Discipline informatiche |
Academic discipline | INF/01 |
Type of study-unit | Obbligatorio (Required) |
Language of instruction | Italian |
Contents | Heap D-Ary Heap Binary Trees. Bilanced Binary Trees. Hash Tables. Strutture Dati Union Find The data structures are used and applied for the algorithms studied in Module I. |
Reference texts | T. H. CORMEN, C. E. LEISERSON, R. L. RIVEST, C. STEIN Introduction to algorithms and data structures (third edition), McGraw-Hill, 2010, ISBN: 978-88-386-6515-8 M. T. GOODRICH, R. TAMASSIA, Algorithm Design and Applications, Wiley, December 2014, ©2015, ISBN : 978-1-119-02861-1 |
Educational objectives | Knowledge an role of the data structures. |
Prerequisites | Elements of Calculus, Discrete Mathematics and Programming Languages. |
Teaching methods | Lectures in class and lab activities. |
Other information | Modulo 1 and 2 of Algorithms and Data Structures with Lab. are completely integrated. Modulo 2 cannot be attended independently of Modulo 1. The theoretical part is dedicated to data structures. The lab covers all the arguments of the class in 'Algorithms and Data Strucures'. |
Learning verification modality | Oral and/or Written exam (integrated with Module 1). |
Extended program | The theoretical part is devoted to the study of basic and advanced data structures. In particular, heaps, d-heaps, binary search tree, balanced binary search tree, union-find data structures. Data structures for the multidimensional search are investigated if there is time. The lab hours focus on the topics of both Modulus 1 and Modulus 2. |