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. The course adopts the C language for
laboratories and for final evaluation.
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. The course adopts the C language for
laboratories and for final evaluation.
Curriculum
teacher profile teaching materials
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.
PART 3: Algorithmic paradigms.
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.
In order to download the slides the usual userid-password pair of Roma Tre University is sufficient.
Programme
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.
PART 3: Algorithmic paradigms.
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.
Core Documentation
Slides provided by the teacher and downloadable day by day from the course website: https://moodle1.ing.uniroma3.it/In order to download the slides the usual userid-password pair of Roma Tre University is sufficient.
Type of delivery of the course
Traditional lectures in presence. Weekly homework to be handled online composed by functions to be implemented in C language.Attendance
Lecture slides are at disposal for those who can not attend some lectures.Type of evaluation
The evaluation mainly consists of a written exam lasting two hours (theory questions and a function to be implemented in C language). The evaluation of the written exam may be followed by an oral discussion of the result, even with questions spanning all topics of the course. The homeworks possibly handled during the course give a maximum of two points to be added to the final grade. teacher profile teaching materials
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.
PART 3: Algorithmic paradigms.
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.
In order to download the slides the usual userid-password pair of Roma Tre University is sufficient.
Mutuazione: 20810078 ALGORITMI E STRUTTURE DI DATI in Ingegneria informatica L-8 A - Z PATRIGNANI MAURIZIO
Programme
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.
PART 3: Algorithmic paradigms.
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.
Core Documentation
Slides provided by the teacher and downloadable day by day from the course website: https://moodle1.ing.uniroma3.it/In order to download the slides the usual userid-password pair of Roma Tre University is sufficient.
Type of delivery of the course
Traditional lectures in presence. Weekly homework to be handled online composed by functions to be implemented in C language.Attendance
Lecture slides are at disposal for those who can not attend some lectures.Type of evaluation
The evaluation mainly consists of a written exam lasting two hours (theory questions and a function to be implemented in C language). The evaluation of the written exam may be followed by an oral discussion of the result, even with questions spanning all topics of the course. The homeworks possibly handled during the course give a maximum of two points to be added to the final grade.