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, students 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 students 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: students 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: students 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.

Students are strongly encouraged to pass the Programming 1 exam.

Lectures, classroom and laboratory exercises

1/2 of the lessons of the course are classroom lessons and 1/2 are in the laboratory.

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.
Students with physical disabilities, Learning Disabilities or Special Education Needs can request
specific services and tools via the Staff Sviluppo e Coordinamento Carriere e Servizi alle Studentesse
e agli Studenti, consulting the University webpage: https://www.uniupo.it/en/services/services-
students-physical-or-learning-disabilities
Students with disabilities, learning disabilities or special education needs, once they have contacted
the University Staff, can refer to the tutor in charge of the course to define the examination
modalities, concerning academic aspects.

Laboratory examination: Moodle quiz to test basic knowledge and lab development of code containing iterative and recursive functions in C. At the instructor's discretion, the exam may also be 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