Computer science | University of Parma

Professor
Academic discipline: Informatica (INF/01)
Field: Discipline informatiche
Type of training activity: Characterising

76 hours
of face-to-face activities

9 credits

hub:

course unit
in - - -

lectures timetable unavailable

exam calls

Learning objectives

The goal of the course is to familiarize students with algorithms, data struc-
tures and with the techniques needed for analyzing their eﬃciency.

Prerequisites

- - -

Course unit content

This course presents an introduction to the most important data structures and
to the techniques for designing efficient computer algorithms. General topics
include asymptotics, solving recurrence, algorithm design, analysis of algorithms
and data structures.

Full programme

• Undecidability, intractability of computational problems.
• Computational complexity: models of computation, analysis of algorithms.
• Divide and conquer technique, recurrence relations, the main Lemma.
• Basic data structures: linked lists, stacks, queues, trees.
• Comparison-based sorting algorithms: Insertionsort, Mergesort, Quick-
sort, Heapsort.
• Lower bounds for sorting and searching.
• Sorting in linear time.
• Median and order statistics.
• Introduction to dynamic programming and Greedy technique.
• Binary trees, binary search trees, AVL trees, B-trees.
• Hash tables.
• Graphs, BFS,DFS, DAG, topological sort, strong components.
• Union-ﬁnd, MST, Kruskal’s algorithm, Prim’s algorithm.
• Dijkstra’s algorithm, Bellman-Ford algorithm.

Bibliography

• T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms,
McGraw-Hill;
• C. Demetrescu, I. Finocchi, G.F. Italiano, Algoritmi e strutture dati,
McGraw-Hill;
• R. Sedgwick, Algorithms in C++, Princeton University.

Teaching methods

Lessons, exercises and Lab.

Assessment methods and criteria

Written and oral exam.

Other information