- Docente: Luciano Margara
- Credits: 12
- Language: Italian
- Moduli: Luciano Margara (Modulo 1) Moreno Marzolla (Modulo 2)
- Teaching Mode: In-person learning (entirely or partially) (Modulo 1); In-person learning (entirely or partially) (Modulo 2)
- Campus: Cesena
- Corso: First cycle degree programme (L) in Computer Science and Engineering (cod. 6673)
Learning outcomes
At the end of the course the student: - knows the basic algorithms and data structures; - knows how to compute computational costs; - Knows the classes P and NP; he can dvise fficient algorithms for solving simple computational problems; he can estimate the order of magnitude of the cost of a given algorithm; he can analyze the complexity of a problem; he knows techniques for analyze the correctness and the efficiency of an algorithm; he is able to write and to present a project for solving a computational problem.
Course contents
- basic notion of discrete mathematics for analyzing order of magnitude - Sorting - Median and selection - Elementary data structures: stacks, queues, graphs - Search algorithms on graphs - basic algorithms on graphs - Classes P and NP - NP hard Problems
Readings/Bibliography
- T. Cormen, C. Leiserson, R. Rivest. Introduction to algorithms. MIT Press.
Teaching methods
Lectures in class
Assessment methods
Written exam is mandatory and oral exam is optional. Students may always choose to take the optional oral exam, and the instructor may require it whenever deemed appropriate for an accurate assessment of learning.
To access the written exam, students must first complete and pass (without a numerical grade) a practical laboratory assignment given during the course and to be completed at home. Details regarding the execution and submission of practical assignments are available on Virtuale.
Attendance at lectures does not affect the final grade and is not mandatory to take the exams.
The written exam consists of solving between two and four exercises. The final grade will be the sum of the scores obtained in each exercise. For each exercise, the maximum possible score will be explicitly stated. If the total score exceeds 30, the student will be awarded honors (cum laude). The duration of the written test varies from two to three hours, depending on the difficulty of the exercises. During the written exam, the use of any printed material (books, notes, handouts) is allowed. Access to the web via electronic devices is not permitted. Registration through AlmaEsami within the indicated deadlines is required to take the written exam.
The purpose of the practical assignment, written exam, and possible oral exam is to assess the student’s ability to design efficient algorithms to solve simple computational problems, to estimate the computational cost of algorithms in asymptotic terms, to analyze the computational complexity of basic computational problems, and to evaluate the efficiency and correctness of an algorithm. The grading scale is proportional to the skills demonstrated during the assessments and ranges from 0 to 30 with honors. A student who obtains a grade below 18 will not pass the exam, while a student who obtains a grade above 17 has the right to refuse it and retake the exam in a subsequent session.
Teaching tools
- Slides and books
Office hours
See the website of Luciano Margara
See the website of Moreno Marzolla