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.

Expected skills

• Knowledge of techniques for memory allocation and usage of pointer
• Programming skills in C language, using pointers and dynamic data structures
• Knowledge og basic notions about complexity analysis
• Knowledge of sorting algorithms
• Skills to evaluate algorithm complexity and improve efficiency in terms of execution time and/or memory allocation
• Knowledge of complex data structures and ADTs (linked lists, queues, heaps, trees, hash tables and graphs) and related algorithms
• Knowledge of simple strategies for mudular programs in C
• Knowledge of paradigms of recursive and programming, greedy approaches, dynamic programming and memorization
• Skills to exploit tools for program development
• Skills of problem solving, based on design of data structures and algorithms
• Skills on recursive programming techniques

Prerequisites

• Knowledge of elementary computer systems (Von Neumann model) architecture
• Knowledge of C language syntax, basic data types and constructs
• Basic programming skill in C language, using conditional and iterative constructs, scalar and aggregate data, standard I/O, text files and functions
• Skills on elementary (algorithmic) problem solving.

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

Laboratories and/or exercises

• Practice
• Pointers and dynamic memory allocation
• Modular programs and program development tools
• Recursive programming
• Problem solving and algorithmic paradigms
• Application examples from gaming theory: 8 queens, Hanoi tower, ruler, labyrinth
• Data structures and ADTs
• Laboratory practice
• Pointers and dynamic memory al location: dynamic arrays and matrices, linked lists
• Modular programs and progeam development tools: make, gdb, cvs
• Recursive programming with backtrack
• Problem solving and algorithmic paradigms
• Data structuresm ADTs and symbol tables: stack and FIFO, BSTs, hash tables
• Graph algorithms

Bibliography

• 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

Italian versions:

• 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
• Nocco, Quer, “Guida alla programmazione in linguaggio C”, Clut
• Brian W. Kernighan, Dennis M. Ritchie, “Il linguaggio C – Principi di programmazione e manuale di riferimento,” Seconda Edizione, Pearson Education Italia