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
  • Maria Cristina Pinotti
Hours
  • 78 ore - Maria Cristina Pinotti
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
  • Maria Cristina Pinotti
Hours
  • 42 ore - Maria Cristina Pinotti
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.
Condividi su