Teaching - Università Roma Tre

(objectives)

Code

20810078

Language

ITA

Type of certificate

Profit certificate

Credits

9

Scientific Disciplinary Sector Code

ING-INF/05

Contact Hours

81

Type of Activity

Core compulsory activities

Group: CANALE 1

Teacher	PATRIGNANI MAURIZIO (syllabus) 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. (reference books) 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
Dates of beginning and end of teaching activities	From to
Delivery mode	Traditional
Attendance	not mandatory
Evaluation methods	Written test Oral exam

Group: CANALE 2

Teacher	PATRIGNANI MAURIZIO (syllabus) 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 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. (reference books) 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
Dates of beginning and end of teaching activities	From to
Delivery mode	Traditional
Attendance	not mandatory
Evaluation methods	Written test Oral exam