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 2019
Offered
2020/21
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
  • 63 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. Advanced 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. The written test requires solving four exercises (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 lenght is about 20-25 minutes. The final grade is based on both grades
in the written and oral examinations.

The students that regularly attend the class can take two 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.
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.

ALGORITHMS AND DATA STRUCTURES - II MODULE

Code 55107606
CFU 6
Teacher Maria Cristina Pinotti
Teachers
  • Maria Cristina Pinotti
Hours
  • 57 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 Binary Trees.
Bilanced Binary Trees.
Hash Tables.
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.
Condividi su