Data Structures and Algorithms of Physics of Data
A.Y. 2026/2027
Learning objectives
The course aims at introducing mathematical and programming basis and main tools and techniques for efficient algorithm design.
Particular emphasis is taken, in the analysis of data structures which turn out to be fundamental in the construction of sophisticated
algorithms applying in scientific realms. Mathematical tools are introduced, for performance and efficiency algorithm analysis. Main
design techniques are introduced, illustrating the construction of some relevant and well-known algorithms. Finally, elements of parallel
and distributed computing are proposed.
Particular emphasis is taken, in the analysis of data structures which turn out to be fundamental in the construction of sophisticated
algorithms applying in scientific realms. Mathematical tools are introduced, for performance and efficiency algorithm analysis. Main
design techniques are introduced, illustrating the construction of some relevant and well-known algorithms. Finally, elements of parallel
and distributed computing are proposed.
Expected learning outcomes
The student will be able to tackle typical problems related to data analysis, designing sophisticated efficient algorithms. To this aim,
she/he will be able to apply the design techniques overviewed along the course, as well as properly use main data structures. Such
skills will be possibly put in practice by developing C++ or Python software.
she/he will be able to apply the design techniques overviewed along the course, as well as properly use main data structures. Such
skills will be possibly put in practice by developing C++ or Python software.
Lesson period: First semester
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
Single course
This course can be attended as a single course.
Course syllabus and organization
Single session
Responsible
Lesson period
First semester
Course syllabus
Theory lectures program:
1. What is Informatics: hardware and theoretical means for information processing.
. 2. Algorithm: definition, examples: Euclid and simple numerical algorithms.
3. From algorithms to programs: executors and programming languages.
4. Numerical information representation (of text, sound, pictures): information digitalization.
5. Binary and exadecimal representation (digitalization).
6. Binary representation of integers.
7. Overflow.
8. Floating point representation: significand, exponent.
9. Measure of information: bit, byte, words, multiples.
10. Computer architecture: von Neumann machine.
11. CPU, RAM, BUS, main devices.
12. Machine language and assembly, low level programming, disadvantages
13. High level programming, languages and compilers
14. Software life cycle: design, compilation, linking, loading, execution. Possible errors and debugging
15. Structured programming and Boehm-Jacopini theorem. The control structures
16. Selection forms, examples
17. Variables, types and operations
18. Forms of iteration, examples: management of data streams and numerical tests
19. The first C ++ program. The output cout stream
20. The types in C ++, main features and operations. Integer types, floating point types, characters and bool
21. Variable declarations, asssignment through expressions and input operations. The stream cin
22. The string type. C-strings, their structure, management and main functions
23. The control structures in C ++. Selection, various forms and nested if
24. The bool type for conditions, main characteristics and Boolean operators. The conditional operator.
25. Iteration in C ++, possible forms. The for loop. The break statement
26. One-dimensional arrays in C ++, main features, functionality and operations on arrays
27. Array and memory allocation, array start address. Two-dimensional arrays, examples
28. The concept of struct
29. File management in C ++. Main features of the fstream library. Opening, manipulation and closing of streams on file
30. Output manipulators, the iomanip library
31. Dynamic arrays, characteristics, definition and use. Loading data from files to dynamic arrays
32. Functions in C ++. Modular top-down program development. Form of a function that returns values and voids
33. Passing of parameters, by value and reference, meaning. Modular shape of the source and prototypes
34. Memory management, activation records, stacks, heaps, stack overflow errors
35. Recursive C ++ functions, inductive definitions of functions, their implementation through recursion
36. Stack dynamics during recursion. Iterative vs. performance recursive
37. Notes on the worst case complexity of the algorithms
38. Search in an array. Linear and binary solution, implementations and performance analysis
39. The sorting problem, lower limits to complexity in time. Selection sort, implementation and complexity in quadratic time
40. Mergesort, specification and implication.Evaluation of complexity in time of mergesort by recurrence equation, optimal time
41. The pointers, meaning, definition and use. Pointers to structures and objects
42. Dynamic variables and pointers, dynamic arrays, new statement. Memory leak and delete statement
43. Pointer operations, pointer arithmetic. Using pointers to scroll through arrays, shallow and deep copy of arrays
44. Traditional arrays as constant pointers, difference with dynamic arrays. Arrays returned by functions, arrays on stacks and on heaps
45. The main parameters, command line acquisition. Implementations of simple operating system commands
Program of laboratory exercises
1. Operating systems, Linux and the file system
2. The use of the Linux terminal, main commands
3. The programming environment, editors, compilers
4. First programs in C ++
5. Selection and cycles in C ++
6. Array and struct
7. C ++ functions and passing of parameters
8. Creation of function libraries. Implementation of libraries, header files.
9. Object file creation and linking
10. Using the make command and structure of a makefile
11. Use of files in C ++: data formatting.
1. What is Informatics: hardware and theoretical means for information processing.
. 2. Algorithm: definition, examples: Euclid and simple numerical algorithms.
3. From algorithms to programs: executors and programming languages.
4. Numerical information representation (of text, sound, pictures): information digitalization.
5. Binary and exadecimal representation (digitalization).
6. Binary representation of integers.
7. Overflow.
8. Floating point representation: significand, exponent.
9. Measure of information: bit, byte, words, multiples.
10. Computer architecture: von Neumann machine.
11. CPU, RAM, BUS, main devices.
12. Machine language and assembly, low level programming, disadvantages
13. High level programming, languages and compilers
14. Software life cycle: design, compilation, linking, loading, execution. Possible errors and debugging
15. Structured programming and Boehm-Jacopini theorem. The control structures
16. Selection forms, examples
17. Variables, types and operations
18. Forms of iteration, examples: management of data streams and numerical tests
19. The first C ++ program. The output cout stream
20. The types in C ++, main features and operations. Integer types, floating point types, characters and bool
21. Variable declarations, asssignment through expressions and input operations. The stream cin
22. The string type. C-strings, their structure, management and main functions
23. The control structures in C ++. Selection, various forms and nested if
24. The bool type for conditions, main characteristics and Boolean operators. The conditional operator.
25. Iteration in C ++, possible forms. The for loop. The break statement
26. One-dimensional arrays in C ++, main features, functionality and operations on arrays
27. Array and memory allocation, array start address. Two-dimensional arrays, examples
28. The concept of struct
29. File management in C ++. Main features of the fstream library. Opening, manipulation and closing of streams on file
30. Output manipulators, the iomanip library
31. Dynamic arrays, characteristics, definition and use. Loading data from files to dynamic arrays
32. Functions in C ++. Modular top-down program development. Form of a function that returns values and voids
33. Passing of parameters, by value and reference, meaning. Modular shape of the source and prototypes
34. Memory management, activation records, stacks, heaps, stack overflow errors
35. Recursive C ++ functions, inductive definitions of functions, their implementation through recursion
36. Stack dynamics during recursion. Iterative vs. performance recursive
37. Notes on the worst case complexity of the algorithms
38. Search in an array. Linear and binary solution, implementations and performance analysis
39. The sorting problem, lower limits to complexity in time. Selection sort, implementation and complexity in quadratic time
40. Mergesort, specification and implication.Evaluation of complexity in time of mergesort by recurrence equation, optimal time
41. The pointers, meaning, definition and use. Pointers to structures and objects
42. Dynamic variables and pointers, dynamic arrays, new statement. Memory leak and delete statement
43. Pointer operations, pointer arithmetic. Using pointers to scroll through arrays, shallow and deep copy of arrays
44. Traditional arrays as constant pointers, difference with dynamic arrays. Arrays returned by functions, arrays on stacks and on heaps
45. The main parameters, command line acquisition. Implementations of simple operating system commands
Program of laboratory exercises
1. Operating systems, Linux and the file system
2. The use of the Linux terminal, main commands
3. The programming environment, editors, compilers
4. First programs in C ++
5. Selection and cycles in C ++
6. Array and struct
7. C ++ functions and passing of parameters
8. Creation of function libraries. Implementation of libraries, header files.
9. Object file creation and linking
10. Using the make command and structure of a makefile
11. Use of files in C ++: data formatting.
Prerequisites for admission
None
Teaching methods
Theory lessons: 2 hours per week.
-Introduction of formal concepts, discussion of algorithms, semantics of the language constructs.
Lab: 3 hours per week.
-introduction and demonstration of new language constructs, discussion and correction of assigned exercises, individual work on assigned exercises.
-Introduction of formal concepts, discussion of algorithms, semantics of the language constructs.
Lab: 3 hours per week.
-introduction and demonstration of new language constructs, discussion and correction of assigned exercises, individual work on assigned exercises.
Teaching Resources
D.S. Malik: Introduction to C++ Programming. Course Technology, 2009.
L.J. Aguilar: Fondamenti di programmazione in C++. Algoritmi, strutture dati e oggetti. McGraw-Hill, 2008.
L.J. Aguilar: Fondamenti di programmazione in C++. Algoritmi, strutture dati e oggetti. McGraw-Hill, 2008.
Assessment methods and Criteria
The exam consists of a written test and a laboratory test. Each test is evaluated independently and in the case of a positive evaluation (greater than or equal to 18) of both tests, the two marks contribute to forming the final mark, given by the arithmetic average of the two marks, rounded up to the next integer.
The written test takes place without the use of texts and /or notes and focuses on the fundamental conceptual rules of C ++ and on the development of the simple algorithms.
The laboratory test involves the development of C ++ algorithms relating to topics explicitly covered in the course and /or in the courses carried out in parallel (analysis, mechanics and statistics), during the test the student can consult bibliographic material and personal folder which he completed during the laboratory sessions (and completed independently).
The written test takes place without the use of texts and /or notes and focuses on the fundamental conceptual rules of C ++ and on the development of the simple algorithms.
The laboratory test involves the development of C ++ algorithms relating to topics explicitly covered in the course and /or in the courses carried out in parallel (analysis, mechanics and statistics), during the test the student can consult bibliographic material and personal folder which he completed during the laboratory sessions (and completed independently).
PHYS-01/A - Experimental Physics of Fundamental Interactions and Applications - University credits: 3
PHYS-06/A - Physics for Life Sciences, Environment, and Cultural Heritage - University credits: 3
PHYS-06/A - Physics for Life Sciences, Environment, and Cultural Heritage - University credits: 3
Lessons: 42 hours
Professor:
Tamascelli Dario
Professor(s)
Reception:
Tuesday, 9am-10am or by appointment (ask via e-mail)
Room C12, 5th floor LITA Building, Physics Department, via Celoria 16.