This course is mandatory for the Bachelor Degree in Computer Engineering. It is held at the first semester of the second year
The class deepens the knowledge and skills in advanced programming, considered as a problem solving tool.
The main goal is to guide the student to gradually evolve from more analytic to more design-oriented 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.

At the end of the course the student will be able to:
- Dynamically allocate memory, using pointers and dynamic data structures in C language
- Evaluate algorithm complexity and improve efficiency in terms of execution time and/or memory allocation
- Write standard algorithm to solve basic problems cush as sorting, searching, etc.
- Manipulate complex data structures, such as linked lists, stacks, queues, heaps, trees, hash tables and graphs
- Write modular programs in C language adopting several programming paradigms such as recursive programming, greedy approaches, dynamic programming and memorization
- Exploit tools for program development and problem solving, based on design of data structures and algorithms.

There are severely strict prerequisite in terms of programming skill and programming language knowledge due to the incremental nature of the class in this area. Particular emphasis has to be put on:
- 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 input/output, text files and functions
- Skills on elementary (algorithmic) problem solving.

- Algorithm analysis, asymptotic analysis and worst-case complexity
- Sorting algorithms: quadratic sorting (selection-sort, insertion-sort and exchange-sort), linear sorting (counting-sort), linearithmic sorting (merge-sort, quick-sort and heap-sort)
- Static and dynamic data structures and their implementation in C
o Memory representation and allocation of data and runtime memory management
o Pointers (references to objects)
o Linked data structures, such as stack, queue and lists
o Strategies for data structure choice and design
- Modular programs and modular implementation of algorithms and data structures
o C language implementation of a program based on multiple source and header files
- Recursion
o Recursive programs and recursive reasoning
o Backtrack and implementation of recursion
- Discrete mathematics
o Sets, relations, functions
o Graphs and trees
- Abstract objects, collections of objects and ADTs
o Examples of modular composite data structures: e.g. arrays of lists, multi-lists, '
o Linked lists, stack, FIFO, generalized queues, priority queues, heaps
- Algorithmic paradigms
o Divide and conquer
o The greedy paradigm
o Dynamic programming and recursion with memoization
- Problem solving
o Data structure and algorithm analysis and design strategies
o Research and optimization problems
- Data structures for symbol tables
o Binary Search trees
o Hash tables
- Graph algorithms
o Depth-first and breadth-first visits
o Applications of visits
o Shortest paths
o Minimum spanning trees

The class can be divided into theory lectures, practice lessons and laboratories.
There is no formal distinction between theory and practice as almost all course topics involve theory and practice aspects developed during the classroom lessons by the teacher.
Laboratories (about 20 hours overall) allow students to solve complex problems (writing, compiling and debugging C language programs on a personal computer) and applying all theory and practice aspects analyzed during the classroom lessons.

Handouts and slides used during the classroom lessons are available on the teacher or course WEB site.
The World Wide Web is also an excellent source of material for almost all topics introduced in the class (see Wikipedia, for example).
Among the printed material we remember the following books in their original English versions:
- R. Sedgewick
o “Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching”
o “Algorithms in C, Part 5: Graph Algorithms”
Addison-Wesley Professional
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, “Introduction to Algorithms”, McGraw-Hill
and the corresponding Italian versions with two other references on the C language
- 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”, 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”, Pearson Education Italia

The examination includes two separate parts:
- A written test
- An oral evaluation.

The written test comprehends two parts:
• A theory section which:
o Consists of open questions or exercises on theory topics.
o Amounts up to 10 (or 12) points on the final mark.
o Has a minimum threshold of 5 points out of 10 (or 6 out of 12).
o Has to be delivered after 45-60 minutes from the beginning of the written test.
• A programming section to check programming skills in C language. For this part of the examination, it is possible to select between two different alternatives:
o A standard programming part with a maximum value of 18 points and a minimum threshold of 9 points. This test implies the design of a “standard” “complex” C program to check the candidate knowledge of the C language syntax, data structures, algorithms, and program designing (problem-solving) ability.
o A simplified programming part with a maximum value of 12 points and a minimum threshold of 6 points. This test is usually made-up by two o three “shorter” “partial” C programs. Those exercises are aimed to check the knowledge of the candidate in terms of C language syntax, data structures, and algorithms but they are less demanding from the designing. i.e., problem-solving, point of view than the “standard” part.
The two parts can be selected by the candidate in alternative (mixing is not allowed).
The theory and programming written tests have to be taken during the same session.
No books or notes are allowed during the examination.
Laptop, cellular phones, etc. are forbidden.

After the written test, all students have some days to correct their program (programs) and check-it (them) out to carry out an auto-evaluation. If the student finally decides to take the exam, he/she has to deliver the final working (complete and debugged version of the) program (programs) to the teacher, following the rules given during the written test. No correction will be done (i.e., the examination will not be taken) without delivering the final (working) version of the program (programs).
Notice that, to take the exam, it is mandatory to deliver a working program (two working programs if the simplified version of the programming part has been selected), even if the evaluation is made on the written text delivered during the test and not on the program written at home.
To be able to implement at home the program developed during the written test, students are invited to take with them a photo camera (or a cell-phone with camera) or some copy-paper.

The oral examination is the final part of the exam and it is mandatory to all students with a written test mark larger than 15/30.
Students that failed the written test (mark smaller than 15/30) are invited not to take the oral examination and to re-take the entire exam during the next examination session.
The oral examination includes questions on all topics analyzed during the class (theory aspects and programming topics).
This oral evaluation can adjust the final mark ranging from fail to 30 with laude.