Università Roma Tre

PART 1: Generalities and tools.
Definitions of computational problem, algorithm, data structure.
Random Access Machine and pseudocode.
Asympthotic study of functions (O-grande, 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 pointes.
Strings.
Memory management: Heap and Stack.
Management of C projects: prototypes and implementations.
Recursion and memory.
Records and pointes.
Dynamic memory management.
File management.

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