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. During the course students are introduced to the C language.
Curriculum
Canali
teacher profile teaching materials
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.
INTRODUCTION TO ALGORITHMS (THIRD EDITION) MIT PRESS, 2009
B.W.KERNIGHAM, D.M.RITCHIE
THE C PROGRAMMING LANGUAGE (SECOND EDITION)
PRENTICE HALL, 1988
Programme
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.
Core Documentation
T.H.CORMEN, C.E.LEISERSON, R.L.RIVEST, C.STEININTRODUCTION TO ALGORITHMS (THIRD EDITION) MIT PRESS, 2009
B.W.KERNIGHAM, D.M.RITCHIE
THE C PROGRAMMING LANGUAGE (SECOND EDITION)
PRENTICE HALL, 1988
Type of evaluation
Written test Oral examCanali
teacher profile teaching materials
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.
INTRODUCTION TO ALGORITHMS (THIRD EDITION) MIT PRESS, 2009
B.W.KERNIGHAM, D.M.RITCHIE
THE C PROGRAMMING LANGUAGE (SECOND EDITION)
PRENTICE HALL, 1988
Programme
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.
Core Documentation
T.H.CORMEN, C.E.LEISERSON, R.L.RIVEST, C.STEININTRODUCTION TO ALGORITHMS (THIRD EDITION) MIT PRESS, 2009
B.W.KERNIGHAM, D.M.RITCHIE
THE C PROGRAMMING LANGUAGE (SECOND EDITION)
PRENTICE HALL, 1988
Type of evaluation
Written test Oral exam