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 2021
- Offered
- 2022/23
- 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 Instructional materials used during lectures are, usually, also made available on Unistudium. |
| Educational objectives | The course provides the basic, characterizing algorithmic skills for the CdS. The main objective of the teaching is to provide students with the basis for understanding, evaluating, and proposing techniques (algorithms), based on precise, deterministic procedures, structured in elementary and finite steps, that solve classes of problems. The main knowledge acquired will be: ability to evaluate the efficiency of an algorithm; in-depth knowledge of basic algorithms; knowledge and use of data structures; and knowledge of algorithms for handling graphs (exploration and minimal paths). The main skills (i.e., the ability to apply the acquired knowledge) will be: analyze the behavior in time and space of already proposed algorithms; recognize the applicability of studied algorithms; and develop original algorithms for new classes of problems. |
| 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. Written and oral tests (only oral during the pandemic) The written test requires solving at most four exercises (usually, 8 points each) aimed at measuring the ability to apply acquired knowledge and understand its transfer 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 (different rule during the pandemic) The oral test is not mandatory if the written test is sufficient. The students that regularly attend the class can take two partial exams. There is also 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. 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 | 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. |
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, Meldable heaps (Leftist Trees) Binary Trees. Bilanced Binary Trees. Hash Tables. Strutture Dati Union Find The data structures are used and applied to 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 Instructional materials used during lectures are, usually, also made available on Unistudium. |
| Educational objectives | The course provides the basic, characterizing algorithmic skills for the CdS. The main objective of the teaching is to provide students with the basis for understanding the data organization. The main knowledge acquired will be: knowledge of basic data structures, which operations characteize them, and the operation time complexity. The main skills (i.e., the ability to apply the acquired knowledge) will be: recognize the data structure useful in a certain context. |
| 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). The test as a whole makes it possible to ascertain both the capacity for knowledge and understanding, the ability to apply the acquired skills, as well as the ability to exposition, 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. The lab hours focus on the topics of both Modulus 1 and Modulus 2. |