FONDAMENTI DI PROGRAMMAZIONE A - EModule PROGRAMMAZIONE II
Academic Year 2023/2024 - Teacher: Vincenza CARCHIOLOExpected Learning Outcomes
This Programming II module of the Foundations of Programming course focuses on training students to be proficient in advanced programming in ANSI C, and to be capable of designing, evaluating, and implementing algorithms and data structures appropriate for problem solving, as well as communicating using the language of the field. The module also includes a brief introduction to complexity theory and its direct application to algorithms on linear data structures. In addition, problems and solutions on non-linear data structures are presented.
Knowledge and understanding
Students will acquire a solid knowledge and understanding of the fundamental linear and hierarchical data structures, including lists, queues, and binary search trees, as well as the computational complexity of operations on them and the search and sorting algorithms. They will be able to demonstrate a deep understanding of the concepts related to dynamic data structures, including pointers and their management.
- Knowledge of the main dynamic data structures and understanding of their mechanisms
- Knowledge of search and sorting techniques
- Knowledge of the basics of computational complexity
Applying knowledge and understanding
Students will be able to apply the knowledge acquired in the design and implementation of practical solutions, using the ANSI C language, using the data structures, algorithms covered in the course, and the tools available. Finally, they will be able to solve complex problems using these knowledge.
The course will promote the development of design skills, allowing students to design efficient and well-structured solutions that meet specific requirements. They will be able to effectively plan and implement the use of dynamic data structures in their projects.
- Ability to solve problems that use dynamic memory and dynamic data structures (such as lists, queues, and binary trees), write the solution algorithm and implement it using the ANSI C language
- Ability to analyze the code and correct errors during the development phases and realize a working application
- Advanced bug-finding (debugging) ability in the context of a development environment (IDE)
Learning skills
This teaching aims to provide students with the ability to effectively exploit the available resources, including the standard ANSI C library functions and integrated development environments with particular emphasis on error-finding tools such as the debugger. Students will learn to understand and manage memory resources (both mass and central) in an appropriate way, especially when using dynamic data structures.
Students will develop skills in the critical analysis of algorithm performance and the evaluation of computational complexity. They will be able to evaluate and compare solutions based on algorithms and data structures based on time and space criteria.
- The student is able to find the best solution to a problem, taking into account both effectiveness and efficiency, define the algorithm, code it and guarantee its operation
- Be able to use the knowledge and skills acquired to address complex problems in a methodological way
Communication skills
Students will develop communication skills through the clear and accurate description, using the most appropriate formal tools, of their software solutions and the ability to communicate effectively concepts related to data structures and algorithms with their colleagues and the instructor. They will be able to present their ideas and solutions in a clear and persuasive way.
The student acquires the knowledge of the computer language and technical terminology.
Course Structure
The course is primarily taught through lectures to acquire the basic theoretical knowledge and all the syntactic elements, and the performance of exercises, to be carried out also autonomously, proposed by the teacher to acquire the ability to solve problems, apply knowledge and use the development environments and methodologies.
The teacher also proposes individual exercises that consist of the solution of a problem that the student must face independently, which are subsequently corrected or discussed in class.
If the teaching is imparted in mixed or distance mode, the necessary changes may be introduced with respect to what was declared previously, in order to respect the program provided and reported in the syllabus.
Required Prerequisites
Attendance of Lessons
Attendance is not mandatory, albeit strongly recommended, to successfully pass the exam.
The student is required to attend at least 70% of the lectures of the course to be able to take the mid-term exam of the module.
If the teaching is imparted in mixed or distance mode, the requirements for participation in the mid-term exams may be modified.
Detailed Course Content
Brief introduction to complexity theory
- Efficiency of programs.
- Evaluation of the efficiency of an algorithm.
- The O and Ω notations for evaluating the complexity of a program
Search and sorting algorithms
- Search algorithms
- Sorting algorithms: selection sort, insertion sort, bubble sort, quick sort, and merge sort
Abstract data types (ADTs) and their implementation in C
- Introduction to abstract data types (ADTs)
- Linear and hierarchical abstract data types
- Problem solving through ADTs
- Translation of abstract data types into concrete data types (CDTs), through the use of the ANSI C language
- Writing ANSI C applications that exploit ADTs and their implementations
Linear data structures
- Lists and sorted lists
- Definition of the ADT
- Sequential, linked, and doubly linked representation
- Implementation with static and dynamic allocation
- Queues
- Definition of the ADT
- Sequential, linked, and doubly linked representation
- Implementation with static and dynamic allocation
- Stacks
- Definition of the ADT
- Sequential, linked, and doubly linked representation
- Implementation with static and dynamic allocation
Non-linear data structures
- Trees
- General concepts and definitions
- Definition of the ADT
- Binary trees and binary search trees
- General concepts and definitions
- Definition of the ADT
- Implementation of the main operations
- Dictionaries (Hash tables)
- General concepts and definitions
- Definition of the ADT
- Implementation of the main operations
- Graphs
- General concepts and definitions
- Definition of the AD
Course Planning
Subjects | Text References | |
---|---|---|
1 | Brief introduction to complexity theory | Handout |
2 | Search and sorting algorithms | Handout |
3 | Abstract data types (ADTs) and their implementation in C | Handout |
4 | Lists and sorted lists | Handout |
5 | Queue | Handout |
6 | Stack | Handout |
7 | Tree | Handout |
8 | Bynary tree and bynary search tree | Handout |
9 | Dictionary | Handout |
10 | Graph | Handout |
Learning Assessment
Learning Assessment Procedures
Mid-term exam
The module includes a mid-term exam, which consists of:
A computer application development task, lasting 60 to 90 minutes
An oral exam. Access to the oral exam is conditional on passing the computer application task.
Participation in the mid-term exam is conditional on:
Passing the first module
Attending at least 70% of the lectures for the module
The mid-term exam will be held at the end of the module.
Final exam for module 2
The final exam for module 2 consists of:
A computer application development task, lasting 60 to 90 minutes
An oral exam. Access to the oral exam is conditional on passing the computer application task
Course exam
The course exam consists of passing the final exams for module 1 and module 2
The exams for both modules can be taken in the same session