- Teacher: Rossano Venturini
- CFU: 9
- Period: Second semester
- Language: English
- Classroom: here
- Lectures schedule: Monday 9-11, Thursday 16-18, and Friday 11-13 (Google Meet).
- 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 |
|---|---|---|
| Lab | XX/XX/2021 XX:30 | XX |
| Theory | XX/XX/2021 XX:30 | XX |
- 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/2021 | Laboratory: Introduction. Python Basics. | Jupyter notebooks on our Google Classroom | |
| 18/02/2021 | Laboratory: Python Basics and Data Structures. | Jupyter notebooks on our Google Classroom | |
| 19/02/2021 | Laboratory: Python Basics and Data Structures. | Jupyter notebooks on our Google Classroom | |
| 22/02/2021 | Laboratory: Advanced Python. | Jupyter notebooks on our Google Classroom | |
| 25/02/2021 | Laboratory: Advanced Python. | Jupyter notebooks on our Google Classroom | |
| 26/02/2021 | Laboratory: Exercises. | ||
| 01/03/2021 | Introduction to analysis of algorithms. | CCLR Sect. 2.1 | Notes next 3 lectures |
| 04/03/2021 | Insertion Sort: Correctness and analysis. | CCLR Sect. 2.2 | VisuAlgo Sorting |
| 05/03/2021 | Selection Sort: Correctness and analysis. | Selection Sort vs Insertion Sort and VisuAlgo Sorting | |
| 08/03/2021 | Divide and Conquer. Merge Sort. | CCLR Sect. 2.3 | VisuAlgo Sorting Notes next 2 lectures |
| 11/03/2021 | Divide and Conquer. Merge Sort. | CCLR Sect. 2.3 | |
| 12/03/2021 | Asymptotic notation. | CCLR Sect 3.1 | Notes next 2 lectures |
| 15/03/2021 | Laboratory: Basics sorting | Jupyter Notebook Mandatory exercises | |
| 18/03/2021 | Exercises. Binary search. | CCLR Sect 3.1 | |
| 19/03/2021 | QuickSort. Best and worst cases. No average time analysis. | CCLR Sects 7.1, 7.2, and 7.3. | VisuAlgo Sorting Notes |
| 22/03/2021 | Laboratory: MergeSort and QuickSort. | Jupyter Notebook Mandatory exercises | |
| 25/03/2021 | Lower Bound for sorting in the comparison model. Lower bound for searching a key in a sorted array. | CCLR Sect. 8.1 | |
| 26/03/2021 | Sorting in linear time: Counting Sort and Radix Sort. | CCLR Sects. 8.2 and 8.3 | VisuAlgo Sorting |