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 2022
- Offered
- 2023/24
- 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. Heapsort. Divide-et-impera. Representations and elementary traversal for graphs. Minimum spanning trees. Shortest path for single source. |
| 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 Instructional materials used during lectures are, usually, also made available on Unistudium. |
| Educational objectives | The course provides the basic algorithmic skills that are characteristic for the course of study. The main objective of the course is to provide students with the basis for understanding, evaluating, and proposing deterministic algorithms, similar to those studied in the course, but extended to new contexts. The main knowledge acquired will be: the ability to evaluate the efficiency of an algorithm; algorithms for sorting; use of data structures; algorithms for handling graphs. The main skill will be to apply the acquired knowledge to new contexts through the development of original algorithms (revisitations of the studied algorithms), whose efficiency and optimality will be derived. |
| Prerequisites | Elements of Calculus, Discrete Mathematics and a programming language. |
| Teaching methods | Lectures in class. |
| Other information | Attendance is expected. Nonetheless, all the arguments we deal with are widely discussed in the suggested textbooks. |
| Learning verification modality | There is a single exam for Modulo I and Modulo II of Algorithms and data structures. The test is written, but the student can ask a supplemental oral test. The written test requires solving exercises aimed at measuring the ability to apply acquired knowledge to new contexts. 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. The oral test is not mandatory if the written test is sufficient. The students that regularly attend the class can take two partial exams. The students can ask for a supplemental oral exam as well. In case the student intends to advance the examination in a year prior to the one scheduled in the study plan, it is recommended to attend the lecture series and to take the exam in the first useful call after the lectures are finished, thus respecting the semester of the teaching schedule. |
| 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.Several implementation of the Dijkstra algorithm. Algorithms for Minimum Spanning Tree. Mention shortest path among all the pairs of vertices. |
| Obiettivi Agenda 2030 per lo sviluppo sostenibile | This teaching contributes to the realization of the UN goals of the 2030 Agenda for Sustainable Development. |
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 | Insights for data structures. Algorithms for all pairs shortest path in weighted graphs. |
| 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 Instructional materials used during lectures are, usually, also made available on Unistudium. |
| Educational objectives | The course provides the basic algorithmic skills that are characteristic for the course of study. The main objective of the course is to provide students with the basis for understanding, evaluating, and proposing deterministic algorithms, similar to those studied in the course, but extended to new contexts. The main knowledge acquired will be: the ability to evaluate the efficiency of an algorithm; algorithms for sorting; use of data structures; algorithms for handling graphs. The main skill will be to apply the acquired knowledge to new contexts through the development of original algorithms (revisitations of the studied algorithms), whose efficiency and optimality will be derived. |
| 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) aimed at measuring the ability to apply acquired knowledge and understand its transfer to new contexts. In case the student intends to advance the examination in a year prior to the one scheduled in the study plan, it is recommended to attend the lecture series and to take the exam in the first useful call after the said lectures are finished, thus respecting the semester of the teaching schedule. |
| Extended program | The theoretical part is devoted to the study of basic and advanced data structures. In particular, heaps, mergeable heaps, binary search tree, balanced binary search tree, union-find data structures. Data structures for the multidimensional search are investigated if there is time. Study of different algorithms for all pairs shortest path problem in weighted graphs: Floyd-Warshall, Tropical Method, and Johnson. The lab hours focus on the topics of both Modulus 1 and Modulus 2. |
| Obiettivi Agenda 2030 per lo sviluppo sostenibile | This teaching contributes to the realization of the UN goals of the 2030 Agenda for Sustainable Development. |