Algorithms and Data Structures  Spring 2024
Instructor:
Antonio Carzaniga
Assistants:
Thomas Bertini,
Michal Burgunder,
Koppány Encz,
Fabio Di Lauro, Claudio Milanesi
Lecture schedule: Tuesday 11:00–12:30, Thursday 11:00–12:30.
See the
course weekly schedule or
the
secondsemester Bachelor schedule for details and updates.
Instructors' Office Hours: by appointment
Assistants' Office Hours: by appointment
Objectives
Algorithms and data structures are fundamental to computer science.
They are the essence of computer programs. Also, the performance of
any software system depends on the efficiency of its algorithms and
data structures. Designing and analyzing algorithms is therefore
crucial for the development of software systems. More generally, the
study of algorithms provides insight into the nature of problems and
their possible solutions, independent of programming language,
programming paradigm, computer hardware, or any other implementation
aspect. The objective of this course is to provide students with the
knowledge and skills necessary to design and reason about algorithms,
and to understand some of the most fundamental algorithms and data
structures, their strengths and weaknesses, and their suitability in
common contexts.
Contents
The course will cover basic notions of complexity, including
asymptotic analysis of worstcase and average complexity, bigO,
littleo, omega, and theta notation, polynomial reductions, polytime
verification vs. solution, NP and P complexity classes; general
algorithm strategies such as brute force, greedy, divideandconquer,
and dynamic programming; common algorithms, including elementary
numeric computations, searching and sorting, elementary graph
algorithms, and string matching; basic data structures, including
stacks, queues, linked lists, and rooted trees; more advanced data
structures, including Btrees, heaps, hash tables, and structures
representing disjoint sets and dictionaries.
Policies
See
this page for assessment criteria and
general course policies.
Learning Material and Other Useful Links
Lectures and Related Material
Material such as presentation slides and example programs are
initially copied from last year's edition of the course, and then
updated as we cover the material in class.

An introduction to elementary, algorithmic programming in Python.
This topic will be covered over a series of lectures.

Course introduction: course organization and policies; Example of
the Fibonacci sequence: a bad algorithm and a good algorithm;
implementationindependent behaviors and algorithmic complexity.

Complexity under the RAM model. Asymptotic growth
of functions: bigO, Omega, and Theta notations.

Basic elements for the analysis of algorithms:
complexity and correctness of insertionsort; worst, best, and
averagecase complexity; loop invariants.

Divide and conquer strategy: binary search, merge,
merge sort, recursive multiplication, median and ksmallest
selection.

Quicksort. Heaps and heapsort.

Elementary data structures and hash tables.

Binary search trees. Randomized binary search trees.

Review or binary trees. Height of a BST in the
average case: simulation and visualization.

RedBlack trees: introduction.

BTrees. Data structures in secondary storage:
modeling disk access. Structure, search, and insertion in
Btrees. Relation with redblack trees.

Graphs: representation and elementary algorithms.

Minimal spanning trees; Disjoint sets.

Dijkstra's Algorithm.

Greedy algorithms: general strategy, activity
selection, Huffman codes.

Dynamic programming: examples, and general strategy.

Basic elements of complexity theory: polynomialtime
algorithms and problems; the P complexity class; the NP class;
polynomialtime reduction and NPcompleteness; satisfiability.