## 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. The programming language adopted in the course is the C language.

Curriculum

teacher profile | teaching materials

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.

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/

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 homeworks on a moodle server (https://moodle1.ing.uniroma3.it/) consisting of writing C language functions. Moodle compiles the uploaded code and automatically verifies its correctness with suitable test data. Students who answered the homeworks have a portion of the grade during the course. The final grade is obtained by adding the result of a written test and of a oral test.

teacher profile | teaching materials

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.

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/

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 homeworks on a moodle server (https://moodle1.ing.uniroma3.it/) consisting of writing C language functions. Moodle compiles the uploaded code and automatically verifies its correctness with suitable test data. Students who answered the homeworks have a portion of the grade during the course. The final grade is obtained by adding the result of a written test and of a oral test.