Objectives of the course

The course deepens the knowledge and skills for advanced programming, considered as a problem solving tool.

The main goal is to guide the student from analysis to program design skills. Algorithmic solutions to “classical” problems are introduced, together with their theoretical foundations, and the implementations in C language. The student has the opportunity to analyze practical examples, describing solutions to complex problems, and the related algorithmic paradigms. Most of the knowledge and programming skills are experienced through practical exercises and laboratories.

Syllabus

• Static and dynamic data structures and their implementation in C
• Memory representation/allocation of data and runtime memory management
• Pointers (references to objects)
• Static memory al location, stack and dynamic allocation
• Dynamic arrays
• Linked data structures
• Strategies for data structure choice and design
• Discrete mathematics
• Sets, relations, functions
• Graphs and trees
• Abstract objects, collections of objects and ADTs
• Examples of modular composite data structures: e.g. arrays of lists, multi-lists
• Linked lists, stack, FIFO, generalized queues, priority queues, heaps
• Modular programs and modular implementation of algorithms and data structures
• The modular model implementation-interface-client
• C language implementation of a program based on multiple source and header files
• Introduction to program development tools: e.g. make, gdb, cvs
• Algorithm analysis
• Asymptotic analysis and worst-case complexity
• Recurrence equation
• Sorting algorithms: quadratic sorting (selection sort, insertion sort), linear sorting (counting sort), linearithmic sorting (quicksort, heapsort, mergesort)
• Recursion and recursive program
• Recursive reasoning
• Recursive mathematical functions
• Simple recursive procedures
• Backtrack and implementation of recursion
• Algorithmic paradigms
• Divide and conquer
• The greedy paradigm
• Problem solving
• Data structure and algorithm analysis and design strategies
• Research and optimization problems
• Binary Search trees
• Hash tables
• Graph algorithms
• Depth-first and breadth-first visits
• Applications of visits
• Shortest paths
• Minimum spanning trees

Bibliography

English references:

• R. Sedgewick
• “Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching”, 3rd Edition, 1998
• “Algorithms in C, Part 5: Graph Algorithms”, 3rd Edition, 2001

Addison-Wesley Professional

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, “Introduction to Algorithms”, McGraw-Hill

• Brian W. Kernighan, Dennis M. Ritchie “The C Programming Language”, Prentice Hall

Other references (in Italian):

• Nocco, Quer, “Guida alla programmazione in linguaggio C”, Clut
• Camurati, Quer, “Algoritmi e programmazione: Richiami di teoria con prove d'esame ed esercizi svolti", Seconda edizione, Clut

Italian versions of previous references:

• R. Sedgewick, “Algoritmi in C”, Addison-Wesley, terza edizione
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, “Introduzione agli algoritmi e strutture dati,” Seconda Edizione, McGraw-Hill
• Brian W. Kernighan, Dennis M. Ritchie, “Il linguaggio C – Principi di programmazione e manuale di riferimento,” Seconda Edizione, Pearson Education Italia