Ateneo - UPO

Management of dynamic data structures. Iteration. Recursion. Classical sorting algorithms

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

At the end of the course, the student must be able, given a programming problem (to handle dynamic list structure), to identify a solving algorithm both iteratively and in recursion, implement it in C language, and execute it on the computer. Knowledge and understanding: programming in iteration, programming in recursion, the dynamic list structure. Ability to apply knowledge and understanding: given a dynamic list structure problem, - define an iterative algorithm that transforms input data into output data, following programming constructs; - define a recursive algorithm that transforms input data into output data, following programming constructs; - write the source programme implementing the algorithm to the computer, using a programming language (C); - compile, execute and test this programme on the computer. Autonomy of judgement: autonomously, the student must be able to define and implement an algorithm to solve a problem concerning the handling of dynamic structures in the programming language (C), to evaluate its complexity, and to compile and execute the program. Communication skills: the student must be able to define an algorithm in both iteration and recursion, and must know how to present its cost expressed as complexity in time and space. Learning ability: the student must be able to learn how to define an algorithm from the problem in both iteration and recursion, evaluate its cost (complexity in time and space) and how to implement such an algorithm in C.

The student must have passed Progammazione 1

Lectures, classroom and laboratory exercises

The laboratory activity requires active and individual participation of the students, who thereby develop practical skills (the ability to carry out a programme). Active participation allows a check on how topics are received.

- Written examination: Exercises aimed at testing skills and knowledge inherent to iterative and recursive programming; - laboratory examination: laboratory development of iterative and recursive functions in C language. At the discretion of the professor, the examination may also be in the form of an oral.

- pointers in C and their use for list-making - interactive functions on lists: - management of a single list - management of several lists - recursion: - definition and basic concepts - simulation of recursive functions using activation records - a complex example: the towers of Hanoi - recursive functions on lists - management of a single list - management of several lists - recursive sorting functions: - QuickSort - MergeSort

Knowledge of recursion, struct, sorting algorithms (recursive/iterative), loading lists and data structures from files, space/time complexity analysis on recursive/iterative list algorithms