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: http://www.dia.uniroma3.it/~infovis/
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

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 "in itinere" (ongoing evaluation): 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. Attention please: during the COVID-19 lockdown periods the exam will be an oral test in accordance with Art.1 of Decreto Rettorale n°. 703 (5 May 2020). The oral test will be fundamental for passing the exam.

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: http://www.dia.uniroma3.it/~infovis/
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

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 "in itinere" (ongoing evaluation): 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. Attention please: during the COVID-19 lockdown periods the exam will be an oral test in accordance with Art.1 of Decreto Rettorale n°. 703 (5 May 2020). The oral test will be fundamental for passing the exam.