Algorithms 1

Course objectives

General goals: This course introduces students to basic methods for algorithm design and analysis. They will study well-known algorithms that solve fundamental problems such as sorting or searching, together with the simplest tools to analyze them from an efficiency point of view. Specific goals The course aims to make the basic algorithms and fundamental data structures correctly used. In particular, the main algorithms for solving search and sorting problems will be addressed. The most important data structures will then be studied: unordered and ordered arrays, simple and double lists, dictionaries, trees. Finally, the tools for calculating the computational cost of algorithms will be provided. Knowledge and understanding: At the end of the course, students will know the basic methodologies for the design and analysis of iterative and recursive algorithms, elementary data structures, the main sorting algorithms and the most basic implementations of dictionaries. Applying knowledge and understanding: At the end of the course, students will be familiar with the main basic data structures, particularly those implementing dictionaries. They will be able to explain the algorithms and analyze their complexity, highlighting how performance depends on the data structure used. They will be able to design new data structures and related algorithms, reworking existing ones; will be able to explain the main sorting algorithms, illustrating the underlying project strategies and the related complexity analyses; they will be able to compare the asymptotic behavior of the execution times of the studied algorithms; they will be able to design recursive solutions to problems and asymptotically analyze the resulting algorithms. Critical and judgmental abilities: The student will have the basis for analyzing the quality of an algorithm and of the related data structures, both from the point of view of the effective resolution of the problem and from that of the computational efficiency with which the problem is solved. Communication skills: The student will acquire the ability to present his knowledge in a clear and organized way, which will be verified through the questions presented in the written tests and during the oral exam. The student will be able to express an algorithmic idea rigorously at a high level, in pseudocode. Learning ability: The knowledge acquired will allow the student to tackle the study of algorithmic techniques and more advanced data structures.

Channel 1
TIZIANA CALAMONERI Lecturers' profile

Program - Frequency - Exams

Course program
1. Introduction Concepts of algorithma, data structures, efficiency, and computational cost; RAM model; uniform and logarithmic cost measures. 2. The Search Problem Sequential search in a disordered vector; best-, worst-, and average-case computational cost Dichotomous or binary search in an ordered vector (iterative version) best-, worst-, and average-case computational cost 3. Introduction to Recursion Recursive Functions Iterative and Recursive Versions of Algorithms: Examples Calculating the Computational Cost of Recursive Functions Using Recurrence Equations Substitution Method Iterative Method Tree Method Main Theorem (Optional Proof) 4. The Sorting Problem Lower Bound on the Computational Cost of Comparison Sorting Algorithms; Proof Merger Function and Merge Sort; Overview of the Divide-and-Conquer Technique Linear-Time Sorting: Counting Sort and Bucket Sort Quick Sort and Its Computational Cost in the Worst, Best, and Average Cases Heap and Heap Sort 5. Fundamental Data Structures Dynamic Sets and Operations on Them Unordered and Ordered Vector Stack and Queue, Insertion and Extraction Functions, Circular Queue Simple and Doubly-Bulleted List Priority Queue Tree Definition as an Acyclic Connected Graph Tree Characterization Theorem and Proof Rooted Trees, Binary Trees, Ordered Trees, Complete Binary Trees Relationships between the Number of Internal Nodes, the Number of Leaves, and the Height of a Complete Binary Tree In-Memory Representation of a Binary Tree Positional Representation Pointer Representation Parent Vector Pre-, Post-, and In-Order Search and Computational Cost Calculation Using a Recurrence Equation 6. Dictionaries Direct Addressing Hash Tables Collisions Collision Resolution by Concatenation (Overflow Lists and Load Factor) Average Computational Cost Collision Resolution with Open Addressing Various Scan Types (Linear, Quadratic, and Hashing) (double) Average-case computational cost Binary search trees Definition Search algorithm and its computational cost Maximum, minimum, successor, and predecessor search algorithms and their computational cost Insertion algorithm and its computational cost Deletion algorithm and its computational cost The balancing problem for bounding computational cost AVL trees and the height-bounding theorem B-trees
Prerequisites
Indispensable prerequisites for attending the lessons of the Introduction to Algorithms course are the basic notions of calculus and the foundations of any modern high-level programming language, for example, those that are provided in the courses of Calculus first module and the first course of Programming, both compulsory for everyone and placed in the first semester of the first year of the course.
Books
T. H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to algorithms, The MIT Press It will be the teachers' responsibility to publish didactic material, related to the lessons and exercises (in the form of teacher's notes) on the platform of Unitelma. The material for this year can be found here: https://twiki.di.uniroma1.it/twiki/view/Intro_algo/AD/Dispense
Teaching mode
Remote teaching mode. Beside the recorded lectures, there is a support activity by the teacher and a "tutoring" activity in which exercises are proposed to students, in agreement with them about the topics. Attending lectures is not compulsory.
Frequency
attending lessons is not compulsory but strongly encouraged.
Exam mode
The exam assesses learning through a written test and an oral exam. The written exam is very streamlined and consists of short theoretical questions and the solution of problems similar to those covered in the exercises. The oral exam, which is open to those who achieve a passing grade in the written exam, consists of a discussion of the most relevant theoretical topics covered in the course and the development of algorithmic solutions to proposed problems. To pass the exam, students must achieve a grade of at least 18/30. Students must demonstrate sufficient knowledge of the topics covered in all sections of the program. To achieve a grade of 30/30 with honors, students must demonstrate excellent knowledge of all the topics covered in the course and be able to connect them in a logical and coherent manner.
Lesson mode
The course mode is traditional; in addition to the usual lectures and exercises, when available, students will be supported by a tutor to complete (independently or in groups) the exercises provided by the teacher. Attendance is not mandatory.
Channel 2
ANGELO MONTI Lecturers' profile

Program - Frequency - Exams

Prerequisites
The prerequisites of the course consist in the foundations of any modern high-level programming language, which are for instance provided in the course of programming, compulsory for all students and placed at the first semester of the first year of the degree in Computer Science.
Books
T. H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to algorithms, The MIT Press It will be the teachers' responsibility to distribute didactic material, related to the lessons and exercises (in the form of teacher's notes).
Exam mode
The exam aims at evaluating what students have learned through a *compulsory written test * (consisting in answering to theoretical questions and in solving problems of the same type as those carried out in the exercises) and an *optional oral exam* (consisting in the discussion of the most relevant topics illustrated in the course). The written test will last about two hours and can be replaced by two intermediate tests, both lasting two hours, the first of which will take place at about mid-course and the second one immediately after the end of the course. The first intermediate test will focus mainly on the topics illustrated in the first half of the course (simple recursive algorithms, resolution of recurrence equations, naif sorting algorithms), the second one on the topics explained in the second half of the course (algorithms for the solution of problems on sorting, linked lists and trees). To pass the exam, students need to achieve a grade of not less than 18/30. Students must demonstrate that they have acquired sufficient knowledge of the topics of both parts of the program. To achieve a score of 30/30 cum laude, students must instead demonstrate that they have acquired excellent knowledge of all the topics covered during the course and be able to link them in a logical and coherent manner.
Lesson mode
Traditional teaching mode. Beside the frontal teaching, there is a "tutoring" activity in which exercises are proposed to students, in agreement with them about the topics.
  • Lesson code10620599
  • Academic year2025/2026
  • CourseComputer Science
  • CurriculumCurriculum unico
  • Year1st year
  • Semester2nd semester
  • SSDINF/01
  • CFU6
  • Subject areaFormazione informatica