Programma

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.

Testi Adottati

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.

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

Evaluation "in itinere" (ongoing evaluation): students are invited to solve homeworks on a Moodle server consisting of writing C language functions. Moodle compiles the uploaded code and automatically verifies its correctness with suitable test data. Several tests in the laboratory, consisting of exercises analogous to those provided online, will provide a grading for the students. 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). The written test is preceded by a laboratory test to verify the the students have a minimum knowledge of C language and of the base concepts of the course. Students who made the ongoing evaluation have a portion of the grade during the course. The final grade is obtained by adding the result of a written test.