## 20810078 - Algorithms and Data Structures

Provide knowledge on basic data structures (stacks, queues, lists, trees, graphs) and fundamental algorithms for their management. Acquire the formal tools for a rigorous evaluation of the computational complexity of algorithms and problems. A further objective of the course is the acquisition of familiarity with the main algorithmic approaches (divide and conquer, greedy, incremental) and the recursive and iterative programming paradigms. During the course students are introduced to the C language.

PATRIGNANI MAURIZIO

teacher profile | materiale didattico

Programma

PART 1: Generalities and tools.
Definitions of computational problem, algorithm, data structure.
Random Access Machine and pseudocode.
Asympthotic study of functions (big-O, Omega, and Theta notations).
Asympthotic complexity of algorithms and problems.
Ammortized complexity.
Worst/average/best case analysis.
Recursion and recursion equalities.
Theorems for the analysis of recursion equalities.

PART 2: Abstract data types.
Abstract data types and their representations.
Already known examples: sets, stacks, queues, lists, etc.
Management of dynamic data structures.
Trees: binary trees; arbitrary degree trees; traversals of trees; binary search trees; red-black trees.
Hash tables.
Graphs: representations with adjacency matrix and adjacency lists. DFS and BFS. Graphs and connectivity. Connected components. Minimum-lengths paths.

Greedy algorithms (example: selection sort).
Iterative algorithms (example: insertion sort).
Divide et impera algorithms (examples: merge-sort and quick-sort).

PART 4: The course requires (and sometimes recalls) the following notions of C Language.
Imperative programming.
Elementary data types.
Functions.
Arrays and pointers.
Strings.
Memory management: Heap and Stack.
Management of C projects: prototypes and implementations.
Recursion and memory.
Records and pointes.
Dynamic memory management.

Slides provided by the teacher and downloadable day by day from the course website: http://www.dia.uniroma3.it/~infovis/

Bibliografia Di Riferimento

The following books are suggested to those students that cannot attend the lessons: T.H.CORMEN, C.E.LEISERSON, R.L.RIVEST, C.STEIN INTRODUCTION TO ALGORITHMS (THIRD EDITION) MIT PRESS, 2009 B.W.KERNIGHAM, D.M.RITCHIE THE C PROGRAMMING LANGUAGE (SECOND EDITION) PRENTICE HALL, 1988 Any introductory book to C language can be considered equivalent to the book above.

Modalità Erogazione

Lectures with slides projected. The teacher will solve excercises in C language in the class writing code (with suggestions from the students), compiling, linking and executing programs.

Modalità Frequenza

The slides are verbose enough to allow students to pass the exam even if it is not possible for them to attend all lessons.

Modalità Valutazione

PATRIGNANI MAURIZIO

teacher profile | materiale didattico

Mutuazione: 20810078 ALGORITMI E STRUTTURE DI DATI in Ingegneria informatica L-8 A - Z PATRIGNANI MAURIZIO

Programma

PART 1: Generalities and tools.
Definitions of computational problem, algorithm, data structure.
Random Access Machine and pseudocode.
Asympthotic study of functions (big-O, Omega, and Theta notations).
Asympthotic complexity of algorithms and problems.
Ammortized complexity.
Worst/average/best case analysis.
Recursion and recursion equalities.
Theorems for the analysis of recursion equalities.

PART 2: Abstract data types.
Abstract data types and their representations.
Already known examples: sets, stacks, queues, lists, etc.
Management of dynamic data structures.
Trees: binary trees; arbitrary degree trees; traversals of trees; binary search trees; red-black trees.
Hash tables.
Graphs: representations with adjacency matrix and adjacency lists. DFS and BFS. Graphs and connectivity. Connected components. Minimum-lengths paths.

Greedy algorithms (example: selection sort).
Iterative algorithms (example: insertion sort).
Divide et impera algorithms (examples: merge-sort and quick-sort).

PART 4: The course requires (and sometimes recalls) the following notions of C Language.
Imperative programming.
Elementary data types.
Functions.
Arrays and pointers.
Strings.
Memory management: Heap and Stack.
Management of C projects: prototypes and implementations.
Recursion and memory.
Records and pointes.
Dynamic memory management.

Slides provided by the teacher and downloadable day by day from the course website: http://www.dia.uniroma3.it/~infovis/

Bibliografia Di Riferimento

The following books are suggested to those students that cannot attend the lessons: T.H.CORMEN, C.E.LEISERSON, R.L.RIVEST, C.STEIN INTRODUCTION TO ALGORITHMS (THIRD EDITION) MIT PRESS, 2009 B.W.KERNIGHAM, D.M.RITCHIE THE C PROGRAMMING LANGUAGE (SECOND EDITION) PRENTICE HALL, 1988 Any introductory book to C language can be considered equivalent to the book above.

Modalità Erogazione

Lectures with slides projected. The teacher will solve excercises in C language in the class writing code (with suggestions from the students), compiling, linking and executing programs.

Modalità Frequenza

The slides are verbose enough to allow students to pass the exam even if it is not possible for them to attend all lessons.

Modalità Valutazione