## 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

Written test: is a 2 hour test consisting of the asymptotical analysis of a pseudocode program (in terms of big-O, Omega and Theta) and of the writing of a C-language function (and, possibly, of some of its subroutines). Oral test: is colloquium lasting half-an-hour at most and held in a date agreed upon with the teacher. It starts with the disussion of the evaluation of the written test (whose ranking is known to the student beforehand) and may contain theory questions and, possibly, also the request of writing C language and pseudocode functions. Evaluation during the course: students are invited to solve weekly homeworks on a moodle server (https://moodle1.ing.uniroma3.it/) consisting of writing a C language function. Students can try the same homework several times without penalties, until their answer is correct (moodle compiles the uploaded code and automatically verifies its correctness with suitable test data). The final grade is obtained by averaging the grades of the written test and of the oral test. Students who correctly answered all the homeworks add one point to the final grade (a non-integer grade is rounded up to an integer value, the maximum grade is 30/30). Students who achieve the grade of 31/30 obtain 30/30 summa cum laude. A precondition to take advantage of the extra-point given by the homeworks is to complete the exam no later than March of the same Academic Year in which the homeworks are done. Students that only made a portion of the homeworks only get the correspondent fraction of the extra point.

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

Written test: is a 2 hour test consisting of the asymptotical analysis of a pseudocode program (in terms of big-O, Omega and Theta) and of the writing of a C-language function (and, possibly, of some of its subroutines). Oral test: is colloquium lasting half-an-hour at most and held in a date agreed upon with the teacher. It starts with the disussion of the evaluation of the written test (whose ranking is known to the student beforehand) and may contain theory questions and, possibly, also the request of writing C language and pseudocode functions. Evaluation during the course: students are invited to solve weekly homeworks on a moodle server (https://moodle1.ing.uniroma3.it/) consisting of writing a C language function. Students can try the same homework several times without penalties, until their answer is correct (moodle compiles the uploaded code and automatically verifies its correctness with suitable test data). The final grade is obtained by averaging the grades of the written test and of the oral test. Students who correctly answered all the homeworks add one point to the final grade (a non-integer grade is rounded up to an integer value, the maximum grade is 30/30). Students who achieve the grade of 31/30 obtain 30/30 summa cum laude. A precondition to take advantage of the extra-point given by the homeworks is to complete the exam no later than March of the same Academic Year in which the homeworks are done. Students that only made a portion of the homeworks only get the correspondent fraction of the extra point.