11929 - Algorithms and Data Structures (CL.B)

Learning outcomes

Upon completion of the course, the student knows:

- algorithms for solving basic computational problems on elementary data structures;

- basic techniques for calculating the computational cost of algorithms;

- the P, NP, and NP-hard computational complexity classes.

In particular, the student is able to:

- design efficient algorithms for solving simple computational problems;

- estimate in order of magnitude the computational cost of algorithms;

- analyze the computational complexity of basic computational problems;

- assess the efficiency and correctness of an algorithm;

- design and develop a solution for basic computational problems.

Course contents

- basic notion of discrete mathematics for analyzing order of magnitude

- Sorting

- Median and selection

- Elementary data structures: stacks, queues, graphs

- greedy algorithms

- elements of dynamic programming

- Search algorithms on graphs

- basic algorithms on graphs

- Classes P and NP

- NP hard Problems

- elements of linear programming

Readings/Bibliography

T. Cormen, C. Leiserson, R. Rivest. Introduction to algorithms. MIT Press.

Teaching methods

Lectures and in-class exercises.

----------------------------- From university guidelines:

Useful prerequisites for getting the most out of the learning experience: basic knowledge of mathematics, programming, and computer architecture

The course is not monodisciplinary but is divided into modules: one theoretical and one applied.

The content covered in the exercises and labs—which are part of the course—demonstrates practical applications of the theoretical concepts introduced in the main module.

The textbook is required.

Teaching methods: lectures, case studies, in-class and lab exercises; in-person.

Recommendation in cases where the course includes labs (even if only computer labs):

All students who, for study or research purposes, frequent the locations listed above are considered equivalent to workers with regard to their safety, and as such must be trained on the correct procedures to follow when engaging in activities involving specific risks.

Guidelines for computer labs: “Given the nature of the activities and the teaching methods used, attendance at this training activity requires that all students first complete Modules 1 and 2 of the safety training for study environments via e-learning.”

 

Assessment methods

Written exam and optional oral exam. Project.

The assessment consists of two components: a project and a written exam (with an optional oral exam). The project must be submitted and approved before the written exam; it does not count toward the final grade but is required for registration for the written exam.

Attendance at lectures is strongly recommended but not mandatory.

The written exam, lasting 1.5 hours, consists of three exercises: a multiple-choice quiz and a theoretical question assessing knowledge (knowing), and an exercise assessing skills (know-how), as outlined in the “Knowledge and Skills to Be Acquired”

Calculators, dictionaries, reference materials, etc., are not permitted during exams.

Active participation in class will be rewarded.

----------------------------- From university guidelines:

Methods of assessment and evaluation of learning:

The assessment consists of two components: a project and a written exam. Optional oral exam.

How each exam contributes to the final grade: the project determines whether the student passes, while the written exam determines the grade.

Knowledge and skills to be acquired: understanding and ability to apply the concepts introduced in the course.

The order of these exams: project first, then written exam.

Indicate whether midterm exams are planned: no.

Indicate whether the exam requires assignments to be submitted before the exam date: submission and approval of the project must occur before the written exam.

Specify whether the exam results in a grade or a pass/fail: the project results in a pass/fail.

Specify the grading criteria for the exam(s) and the corresponding grading scale: three exercises, each graded on a scale of 0 to 10.

The maximum score achievable by providing all correct and complete answers is 30 with honors.

The exam is considered passed with a minimum score of 18/30.

For written exams, also indicate the duration and format: 90 minutes, both open-ended and closed-ended questions, and the solution to a problem or case study.

Indicate whether or not tools are permitted during the exams: no tools are permitted during the written exam.

Any specific instructions for registering for the exam: none.

For students with learning disabilities (DSA) or disabilities: Students with learning disabilities (DSA) or temporary or permanent disabilities are advised to contact the relevant university office in a timely manner (https://site.unibo.it/studenti-con-disabilita-e-dsa/it); the office will be responsible for proposing any accommodations to the students concerned; these must, however, be submitted 15 days in advance for approval by the instructor, who will assess their appropriateness, including in relation to the course’s learning objectives.

Regarding the use of generative Artificial Intelligence (AI) during exams: laptops, phones, or other computing devices are not permitted, and therefore AI is also prohibited.

Optional oral exam: The purpose of the oral exam is to assess the student’s ability to apply their knowledge and make the necessary logical and deductive connections. Final grade scale: ranging from a failing grade in the event of very serious gaps in knowledge to +3 above the written exam grade.

Teaching tools

Lecture notes and handouts related to the textbook. They are not a substitute for the book itself.

Office hours

See the website of Vittorio Maniezzo

See the website of