Ateneo - UPO

Management of dynamic data structures.
Iteration.
Recursion.
Classical sorting algorithms
Abstract data types: Heap and stack

Paul Deitel, Harvey Deitel “Il linguaggio C. Fondamenti e tecniche di programmazione”. Pearson Italia, 2013

Brian W. Kernighan, Dennis M. Ritchie "Il linguaggio C. Principi di programmazione e manuale di riferimento" Pearson Italia

Allowing students to acquire advanced programming concepts, deepening the concept of iterative programming and introducing the concept of recursion.
Allowing the performance evaluation of an iterative and / or recursive algorithm through the concept of asymptotic complexity.
Acquire the concept of dynamic memory management through the use of the C language, and its application for the use of advanced data structures such as linked lists, queues and stacks.
Understand the functioning and complexity of two of the main recursive sorting algorithms (quicksort and mergesort).

The student must have passed Programming 1

Lectures, classroom and laboratory exercises

The activity in the laboratory requires an active and individual participation of the students, who thus develop practical skills (the ability to carry out a program). Active participation allows a verification of the way in which the arguments are received.

Written exam/laboratory examination: 6 Questions. Two questions aimed at assessing theoretical knowledge: one question on the theoretical topics covered during the course, and one exercise on the simulation of an algorithm using the activation records. 4 exercises developed within a unique program to test the skills and knowledge about iterative and recursive programming, the use of linked lists, dynamic memory management. To pass the test, the student must achieve a score greater or equal to the 60% of the maximum attainable score for both parts (written and laboratory tests).

- pointers in C and their use for the realization of lists
- interactive functions on the lists:
- management of a single list
- management of multiple lists
- recursion:
- definition and basic concepts
- simulation of recursive function by means of activation records
- a complex example: the towers of Hanoi
- recursive functions on lists:
- management of a single list
- management of multiple lists
- recursive sorting functions:
- QuickSort
- MergeSort
- Abstract data types:
- Stack
- Queue

At the end of the course, students must be able, given a programming problem (to manage the dynamic list structure), to identify a solution algorithm both iteration and recursion, implement it in C language, execute it on the computer.

Knowledge and understanding: iteration programming, recursion programming, dynamic list structure.

Ability to apply knowledge and understanding: given a problem inherent in the dynamic list structure,
- define an iterative algorithm that transforms the input data into the output data, following the programming constructs;
- define a recursive algorithm that transforms the input data into the output data, following the programming constructs;
- write to the computer the source program that implements the algorithm, using a programming language (C);
- compile, run and test this program on the computer.

Autonomy of judgment: the student must be able to define and implement an algorithm independently to solve a problem inherent in the management of dynamic structures in the programming language (C), to evaluate their complexity, and to compile and execute the program.

Communication skills: the student must be able to define an algorithm both in iteration and in recursion, and must know how to present its cost expressed as complexity in time and space.

Learning skills: the student must be able to learn how to define an algorithm starting from the problem both in iteration and in recursion, evaluate its costs (complexity in time and space) and how to implement this algorithm in C.