- Teacher: Rossano Venturini
- CFU: 9
- Period: Second semester
- Language: English
- Classroom: here (code: dqwq6aj)
- Lectures schedule: Tuesday 14:15-16:00 (Aula Fib C), Thursday 14:15-16:00 (Aula Fib C), and Friday 9:00-10:45 (Aula Fib A1).
- Question time: After lectures or by appointment
The course introduces basic data structures and algorithmic techniques that allow students to solve computational problems on the most important data types, such as sequences, sets, trees, and graphs.
The lectures will be complemented by an intensive activity in laboratory. Students will experiment with algorithms and data structures by writing their own implementations or by using third-party libraries.
The goal of the class is to enable students to design and implement efficient algorithms, choosing the most appropriate solutions in their future projects.
-
Introduction and basic definitions: algorithm, problem, instance.
-
Computational complexity analysis of algorithms.
-
Sorting: Mergesort, Quicksort and Heapsort.
-
Searching: Binary Search, Binary Search Tree, Trie, and Hashing.
-
Algorithms on Trees: representation and traversals.
-
Algorithms on Graphs: representation, traversals, and most important problems.
-
External memory model: sorting and searching.
| Type | Date | Room | Note |
|---|---|---|---|
| Lab | 27/10/2022 11:00 | Google Meet | Please send your solutions to me by 24/10/2022. Important: Please Cut&Paste your solutions to this Jupyter Notebook and send me just this file with your name and surname on its filename. Please read the very important note below. |
Very important! You are allowed to discuss verbally solutions (e.g., a strategy to solve a problem) with other students, BUT you have to implement all the solutions by yourself. Thus, sharing implementations or implementing a solutions with others is strictly forbidden.
- Introduction to Algorithms, 3rd Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, The MIT Press, 2009 (Amazon) [CCLR]
- Algorithms, 4th Edition, Robert Sedgewick, Kevin Wayne, Addison-Wesley Professional, 2011 (Amazon) [RS]
- Algorithms, Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, McGraw-Hill, 2006. (Amazon) [DPZ]
| Date | Lecture | References | Material |
|---|---|---|---|
| 15/02/2022 | Introduction to analysis of algorithms. | CCLR Sect. 2.1 | Notes next 3 lectures |
| 17/02/2022 | Insertion Sort: Correctness and analysis. | CCLR Sect. 2.2 | VisuAlgo Sorting |
| 18/02/2022 | Selection Sort: Correctness and analysis. | Selection Sort vs Insertion Sort and VisuAlgo Sorting | |
| 22/02/2022 | Divide and Conquer. Merge Sort. | CCLR Sect. 2.3 | VisuAlgo Sorting and Notes next 3 lectures |
| 24/02/2022 | Divide and Conquer. Merge Sort. (contd) | CCLR Sect. 2.3 | VisuAlgo Sorting |
| 25/02/2022 | Laboratory: Basics sorting | Jupyter Notebook Mandatory exercises | |
| 01/03/2022 | Exercises with recurrences. Binary search. | CCLR Sect 3.1 | |
| 03/03/2022 | QuickSort. Best and worst cases. No average time analysis. | CCLR Sects 7.1, 7.2, and 7.3. | VisuAlgo Sorting and Notes next 2 lectures |
| 04/03/2022 | Laboratory: MergeSort and QuickSort. | Jupyter Notebook Mandatory exercises | |
| 08/03/2022 | QuickSort. Best and worst cases. No average time analysis. Asymptotic notation. | CCLR Sects 7.1, 7.2, and 7.3. | |
| 10/03/2022 | Lower Bound for sorting in the comparison model. | CCLR Sect. 8.1 | Notes |
| 11/03/2022 | Laboratory: Applications of sorting (I). | Jupyter Notebook Mandatory exercises | |
| 15/03/2022 | Sorting in linear time: Counting Sort. | CCLR Sect. 8.2 | VisuAlgo Sorting. Notes next 2 lectures |
| 17/03/2022 | Sorting in linear time: Radix Sort. | CCLR Sect. 8.3. | VisuAlgo Sorting |
| 18/03/2022 | Dictionary problem with Hashing. | CCLR Sect. 11.1, 11.2, and 11.4 (no analysis) | Notes next 2 lectures |
| 22/03/2022 | Dictionary problem with Hashing. | CCLR Sect. 11.1, 11.2, and 11.4 (no analysis) | |
| 24/03/2022 | Python best practices. | ||
| 25/03/2022 | Laboratory: Hashing. Python best practices. | Jupyter Notebook Mandatory exercises | |
| 29/03/2022 | Python best practices. | ||
| 31/03/2022 | Python best practices. | ||
| 01/04/2022 | Laboratory: Hashing: Applications. | Jupyter Notebook Mandatory exercises | |
| 04/04/2022 | QuickSelect. Priority queues: Heap. | CCLR Sect. 9.1, 9.2 and CCLR Ch. 6 | Notes next 3 lectures |
| 07/04/2022 | Priority queues: Heap. | CCLR Ch. 6 | VisuAlgo Heap |
| 08/04/2022 | Laboratory: Applications of sorting (II). | Jupyter Notebook Mandatory exercises | |
| 12/04/2022 | Priority queues: Heap. | CCLR Ch. 6 | VisuAlgo Heap |
| 14/04/2022 | Binary Search tree. | CCLR Sect. 12.1, 12.2, and 12.3 | Visualgo BST |
| 21/04/2022 | Binary Search tree. | CCLR Sect. 12.1, 12.2, and 12.3 | Visualgo BST |
| 22/04/2022 | Laboratory: Binary Search Tree. | Jupyter Notebook Mandatory exercises | |
| 26/04/2022 | Exercises: Visits of a tree. | Notes next 2 lectures | |
| 28/04/2022 | Exercises: Visits of a tree. | ||
| 03/05/2022 | Graphs: representations and BFS. | CCLR Sect. 22.1 and 22.2 (no proofs) | Notes next 2 lectures |
| 05/05/2022 | Graphs: DFS. | CCLR Sect. 22.3 (no proofs) | Graph representations and BFS/DFS |
| 06/05/2022 | Laboratory: Questions | ||
| 10/05/2022 | Exercises | Notes | |
| 12/05/2022 | Exercises | Notes | |
| 13/05/2022 | Laboratory: Graphs. | Jupyter Notebook Mandatory exercises |