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 2017
- Offered
- 2018/19
- 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. Dynamic programming, divide-et-impera, Greedy algorithms. |
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. Advanced algorithms on graphs. Advanced design of algorithms. |
Prerequisites | Elements of Calculus, Discrete Mathematics and a programming language. |
Teaching methods | Lectures in class. |
Other information | Attendance is expected. |
Learning verification modality | Oral and/or written exam. Homework and tests in class can be quantified for the final exam. |
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. Heap:properties and algorithms. Priority queues: insertion and deletion. D-ary heaps. 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. Dynamic programming with applications. Greedy algorithms with applications. |
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 | Binary Trees. Bilanced Binary Trees. Hash Tables. Multidimensional search trees. |
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 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. The lab hours focus on the topics of both Modulus 1 and Modulus 2. |