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 programming language adopted in the course is the C language.
The programming language adopted in the course is the C language.
Curriculum
teacher profile teaching materials
Definitions of computational problem, algorithm, data structure.
Random Access Machine and pseudocode.
Asymptotic study of functions (big-O, Omega, and Theta notations).
Asymptotic 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 pointers.
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.
Asymptotic study of functions (big-O, Omega, and Theta notations).
Asymptotic 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 pointers.
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.
Reference Bibliography
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.Type of delivery of the course
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.Attendance
The slides are verbose enough to allow students to pass the exam even if it is not possible for them to attend all lessons.Type of evaluation
Ongoing assessment: During the course, students will be asked to complete homework assignments on Moodle consisting of theoretical questions and functions to be written in the C programming language. Several intermediate tests will be held in the lab during the course, featuring exercises similar to those assigned online as homework. These intermediate tests fully replace the final exam. Final exam: The final exam, both for the theoretical part and the development of algorithmic solutions, will be conducted on Moodle. Grading criteria: Student assessment is based on the Dublin Descriptors and takes into account the level of knowledge, understanding, and critical processing of the topics covered in the course. Students who demonstrate that they have acquired the fundamental concepts and are able to apply them in simple contexts will receive a passing grade. Average grades will be awarded to those who, in addition to mastering the basics, show the ability to analyze and independently elaborate on more complex concepts. The highest grades are reserved for students who demonstrate in-depth understanding, synthesis skills, critical thinking, and autonomy in solving problems, including new ones or those not explicitly addressed during the course. teacher profile teaching materials
Definitions of computational problem, algorithm, data structure.
Random Access Machine and pseudocode.
Asymptotic study of functions (big-O, Omega, and Theta notations).
Asymptotic 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 pointers.
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.
Asymptotic study of functions (big-O, Omega, and Theta notations).
Asymptotic 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 pointers.
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.
Reference Bibliography
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.Type of delivery of the course
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.Attendance
The slides are verbose enough to allow students to pass the exam even if it is not possible for them to attend all lessons.Type of evaluation
Ongoing assessment: During the course, students will be asked to complete homework assignments on Moodle consisting of theoretical questions and functions to be written in the C programming language. Several intermediate tests will be held in the lab during the course, featuring exercises similar to those assigned online as homework. These intermediate tests fully replace the final exam. Final exam: The final exam, both for the theoretical part and the development of algorithmic solutions, will be conducted on Moodle. Grading criteria: Student assessment is based on the Dublin Descriptors and takes into account the level of knowledge, understanding, and critical processing of the topics covered in the course. Students who demonstrate that they have acquired the fundamental concepts and are able to apply them in simple contexts will receive a passing grade. Average grades will be awarded to those who, in addition to mastering the basics, show the ability to analyze and independently elaborate on more complex concepts. The highest grades are reserved for students who demonstrate in-depth understanding, synthesis skills, critical thinking, and autonomy in solving problems, including new ones or those not explicitly addressed during the course. teacher profile teaching materials
Definitions of computational problem, algorithm, data structure.
Random Access Machine and pseudocode.
Asymptotic study of functions (big-O, Omega, and Theta notations).
Asymptotic 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 pointers.
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.
Asymptotic study of functions (big-O, Omega, and Theta notations).
Asymptotic 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 pointers.
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.
Reference Bibliography
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.Type of delivery of the course
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.Attendance
The slides are verbose enough to allow students to pass the exam even if it is not possible for them to attend all lessons.Type of evaluation
Ongoing assessment: During the course, students will be asked to complete homework assignments on Moodle consisting of theoretical questions and functions to be written in the C programming language. Several intermediate tests will be held in the lab during the course, featuring exercises similar to those assigned online as homework. These intermediate tests fully replace the final exam. Final exam: The final exam, both for the theoretical part and the development of algorithmic solutions, will be conducted on Moodle. Grading criteria: Student assessment is based on the Dublin Descriptors and takes into account the level of knowledge, understanding, and critical processing of the topics covered in the course. Students who demonstrate that they have acquired the fundamental concepts and are able to apply them in simple contexts will receive a passing grade. Average grades will be awarded to those who, in addition to mastering the basics, show the ability to analyze and independently elaborate on more complex concepts. The highest grades are reserved for students who demonstrate in-depth understanding, synthesis skills, critical thinking, and autonomy in solving problems, including new ones or those not explicitly addressed during the course. teacher profile teaching materials
Definitions of computational problem, algorithm, data structure.
Random Access Machine and pseudocode.
Asymptotic study of functions (big-O, Omega, and Theta notations).
Asymptotic 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 pointers.
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.
Asymptotic study of functions (big-O, Omega, and Theta notations).
Asymptotic 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 pointers.
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.
Reference Bibliography
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.Type of delivery of the course
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.Attendance
The slides are verbose enough to allow students to pass the exam even if it is not possible for them to attend all lessons.Type of evaluation
Ongoing assessment: During the course, students will be asked to complete homework assignments on Moodle consisting of theoretical questions and functions to be written in the C programming language. Several intermediate tests will be held in the lab during the course, featuring exercises similar to those assigned online as homework. These intermediate tests fully replace the final exam. Final exam: The final exam, both for the theoretical part and the development of algorithmic solutions, will be conducted on Moodle. Grading criteria: Student assessment is based on the Dublin Descriptors and takes into account the level of knowledge, understanding, and critical processing of the topics covered in the course. Students who demonstrate that they have acquired the fundamental concepts and are able to apply them in simple contexts will receive a passing grade. Average grades will be awarded to those who, in addition to mastering the basics, show the ability to analyze and independently elaborate on more complex concepts. The highest grades are reserved for students who demonstrate in-depth understanding, synthesis skills, critical thinking, and autonomy in solving problems, including new ones or those not explicitly addressed during the course.