05OGDLP

A.A. 2022/23

Course Language

Inglese

Degree programme(s)

1st degree and Bachelor-level of the Bologna process in Electronic And Communications Engineering (Ingegneria Elettronica E Delle Comunicazioni) - Torino

Course structure

Teaching | Hours |
---|---|

Lezioni | 60 |

Esercitazioni in aula | 39 |

Esercitazioni in laboratorio | 21 |

Tutoraggio | 20 |

Lecturers

Teacher | Status | SSD | h.Les | h.Ex | h.Lab | h.Tut | Years teaching |
---|---|---|---|---|---|---|---|

Savino Alessandro | Professore Associato | ING-INF/05 | 60 | 16 | 0 | 0 | 3 |

Co-lectuers

Context

SSD | CFU | Activities | Area context |
---|---|---|---|

ING-INF/05 | 12 | B - Caratterizzanti | Ingegneria informatica |

2022/23

The course 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. The student will acquire adequate knowledge and skills in algorithms, data structures and their implementation in C to solve complex problems.
Algorithmic solutions to "classical" problems are introduced, together with their theoretical foundations, and the implementations in C language. Advanced aspects of C are considered, like pointers, dynamic memory allocation, modularity and Abstract Data Type implementation. 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.

The course deepens the knowledge and skills in advanced programming, considered a problem-solving tool. The main goal is to guide the student to evolve from more analytic to more design-oriented skills gradually. The student will acquire adequate knowledge and skills in algorithms, data structures, and their implementation in C to solve complex problems.
Algorithmic solutions to "classical" problems are introduced, together with their theoretical foundations and the implementations in the C language. C's advanced aspects are considered, like pointers, dynamic memory allocation, modularity, and Abstract Data Type (ADT) implementation. The student has the opportunity to analyze practical examples and describe 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 algorithms to solve basic problems such 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.

At the end of the course, the student will be able to:
- Know the paradigms of structured programming using C language
- Dynamically allocate memory, using raw pointers and dynamic data structures in C language.
- Evaluate the algorithm complexity and improve efficiency in execution time and memory allocation.
- Write standard algorithms to solve fundamental problems such as sorting, searching, etc.
- Manipulate complex data structures, such as linked lists, stacks, queues, trees, 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 the design of data structures and algorithms.

Due to the incremental nature of the course with respect to the first year class “Computer Science”, there are several strict prerequisite in terms of programming skill and programming language knowledge, with particular emphasis on the following topics:
- Elementary computer systems architecture (Von Neumann model).
- 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.

Due to the incremental nature of the course concerning the first-year class “Computer Science,” there are several strict prerequisites in terms of programming skills and programming language knowledge, with particular emphasis on the following topics:
- Elementary computer systems architecture (Von Neumann model).
- Basic programming skills, using conditional and iterative constructs, scalar and aggregate data, standard input/output, and text files.
- Basic programming resorting to Functions (with multiple parameters, return handling, etc.)
- Skills in elementary (algorithmic) problem-solving.

• Review of basic language construct and basic problem solving (12h)
• Algorithm analysis (3h)
o Asymptotic worst-case complexity analysis
o O, theta, omega notations
o Recurrence equations
• Sorting algorithms (6h)
o Iterative sorting (bubble sort, selection sort, insertion sort, shell sort, counting sort)
o Recursive sorting (mergesort, quicksort, heapsort)
• Static and dynamic data structures and their implementation in C (13h)
o Data representation in memory and runtime memory management
o Pointers (or references to objects)
o Static, on stack and dynamic memory allocation
o Linked structures
o Strategies for data structure selection
• Modularity and modular implementation of algorithms and data structures (10h)
o The implementation-interface-client model
o Implementation in C of programs with multiple source and header files
o Basic use of development and debug tools, like make, gdb, cvs
• Recursion and recursive programs (10h)
o The notion of recursion
o Mathematical recursive functions
o Simple recursive procedures
o Backtrack and implementation of recursion
• Discrete mathematics (2h)
o Sets, relations, functions
o Lists, graphs and trees
• Abstract objects, collections of objects and ADTs (8h)
o Modular examples of composed structures, like arrays of lists and multilists
o Linked lists, stacks, FIFO queues, generalized queues, priority queues, heaps
• Algorithmic paradigms (10h)
o Divide and conquer
o Greedy
• Problem solving (18h)
o Analysis and definition of strategies for data structures and algorithms
o Search and optimization problems
o Techniques to explore the state space based on combinatorics
• Data structures for symbol tables (8h)
o Binary search trees and extensions
o Hash tables
• Graph theory (18h)
o Graph representation
o Depth-first and breadth-first search and their applications
o Applications of visits
o Shortest paths
o Minimum spanning trees.

- Introduction to C language (~12h)
--- Fundamentals of the language
--- Basic data types and the architecture
--- Functions and parameters
--- The I/O system
--- Implementation in C of programs with multiple source and header files
--- Basic use of development and debug tools, like make, gdb, CVS
- Algorithm analysis (~3h)
--- Asymptotic worst-case complexity analysis
--- O, theta, omega notations
--- Recurrence equations
- Sorting algorithms (~6h)
--- Iterative sorting (bubble sort, selection sort, insertion sort, shell sort, counting sort)
--- Recursive sorting (mergesort, quicksort, heapsort)
- Static and dynamic data structures and their implementation in C (~13h)
--- Data representation in memory and runtime memory management
--- Pointers (or references to objects)
--- Static, on the stack, and dynamic memory allocation
--- Linked structures
--- Strategies for data structure selection
- Modularity and modular implementation of algorithms and data structures (~10h)
--- The implementation-interface-client model
- Recursion and recursive programs (~10h)
--- The notion of recursion
--- Mathematical recursive functions
--- Simple recursive procedures
--- Backtrack and implementation of recursion
- Abstract objects, collections of objects, and ADTs (~8h)
--- Modular examples of composed structures, like arrays of lists and multi lists
--- Linked lists, stacks, FIFO queues, generalized queues, priority queues
- Algorithmic paradigms (~10h)
--- Divide and conquer
--- Greedy
- Problem-solving (~18h)
--- Analysis and definition of strategies for data structures and algorithms
--- Search and optimization problems
--- Techniques to explore the state space based on combinatorics
- Data structures for symbol tables (~8h)
--- Binary search trees and extensions
- Graph theory (~20h)
--- Graph representation
--- Depth-first and breadth-first search and their applications
--- Applications of visits
--- Shortest paths
--- 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.
Lectures (100 hours overall) include practice lessons.
Lectures and practice are extended with 20 additional hours in laboratory to consolidate what the student has learned. Laboratories allow students to solve problems (writing, compiling and debugging C language programs on a personal computer) and applying all theory and practice aspects analyzed during the classroom lessons.

The class includes theory lectures, practice lessons, and laboratories.
There is no formal distinction between theory and practice as almost all course topics involve both aspects developed during the classroom lessons by the teacher.
Lectures (100 hours overall) include practice lessons.
Lectures and practice are extended with 20 additional hours in the laboratory to consolidate what the student has learned. Laboratories allow students to solve problems (writing, compiling, and debugging C language programs on a personal computer) and apply all theory and practice aspects analyzed during the classroom lessons.
Laboratories are mandatory.

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, during the class, we make explicit usage of the following books:
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, “Introduction to Algorithms”, McGraw-Hill.
• S. Quer, "Advanced Programming and Problem-Solving Strategies in C. Part II: Algorithms and Data Structures", 2nd Edition, 2018, CLUT
• S. Quer, "Advanced Programming and Problem-Solving Strategies in C. Part IV: Exam-Based Problems", 2nd eEdition, 2018, CLUT
Other sources are the followings:
• R. Sedgewick, “Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching” Addison-Wesley Professional.
• R. Sedgewick, “Algorithms in C, Part 5: Graph Algorithms”, Addison-Wesley Professional.
• P. Prinz, T. Crawford, "C in a Nutchell (The Definitive Reference)", O'Reilly.

Handouts and slides used during the classroom lessons are available on the teacher or course WEB site.
Among the printed material, during the class, we make explicit usage of the following books:
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, “Introduction to Algorithms,” McGraw-Hill.
• S. Quer, "Advanced Programming and Problem-Solving Strategies in C. Part II: Algorithms and Data Structures," 2nd Edition, 2018, CLUT
• S. Quer, "Advanced Programming and Problem-Solving Strategies in C. Part IV: Exam-Based Problems," 2nd edition, 2018, CLUT
Other sources are the following:
• R. Sedgewick, “Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching” Addison-Wesley Professional.
• R. Sedgewick, “Algorithms in C, Part 5: Graph Algorithms”, Addison-Wesley Professional.
• P. Prinz, T. Crawford, "C in a Nutchell (The Definitive Reference)," O'Reilly.

...
The examination includes two separate parts:
- A written test
- An oral evaluation.
The written test comprehends two parts:
• Exercises/questions on theoretical aspects to check the acquired knowledge.
• A programming part to check the acquired abilities and programming skills.
The theory section:
• Consists of 6 open questions or exercises on theory topics.
• Amounts up to 10 (or 12) points on the final mark.
• Has a minimum threshold of 6 points out of 12.
• Has to be delivered after 60 minutes from the beginning of the written test.
The programming section (lasting 120 minutes) is available in two different formats:
• A complete design and development of a program in C to solve a problem, the emphasis being on problem-solving and design skills. This standard programming part has a maximum value of 18 points and a minimum threshold of 9 points. This test implies the design of a unique "standard and complex" C program to check the candidate knowledge of the C language syntax, data structures, algorithms, and program designing (problem-solving) ability.
• A guided development of the solution to a problem, with less emphasis on design and problem-solving skills and more on the ability to use advanced C features (pointers, dynamic allocation, recursion) and on the knowledge of basic data structures and algorithms. This simplified programming part has a maximum value of 12 points and a minimum threshold of 6 points. This test is usually made-up by two o three "shorter and partial" C programs or C functions. 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). Both modes require the same approach to the subject.
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 3 working 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 written rules specified during the class.
More specifically, each student must:
• Make a copy of the program at the end of the written part (using carbon copy paper or camera).
• Verify the correctness of the program.
• Upload on the course web page within 3 working days: a report (max 3 pages) describing the solution (data structures, algorithm, etc.) and a copy of the working program, showing the changes with respect to the version handed in for ranking.
Detailed notes on how to prepare the required material and on how to upload it on the portal web page are posted on the theacher's web page. In case the above material is not uploaded, the written exam will not be ranked.
Notice that, to take the exam, it is mandatory to deliver a working program (more 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.
Students who failed the written test, i.e., have a 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.
Students with a written test mark larger than 15/30 and smaller than 18/30 must take the oral examination to pass the exam.
For all other students the oral examination is optional. This means that, from the one hand, these students have the discretion to ask for the oral examination to improve their final mark but, on the other one, that the teacher has the right to demand an oral examination to any student he may have evaluation doubts on. Notice, however, that the oral examination (in all cases) can adjust the written mark in both the positive and the negative direction, such that the final mark will range from fail to 30 with honor.
The oral examination checks the capacity of the student to explain his/her design choices, to use correct technical terms, and to describe algorithms. It consists in:
• Questions on all the topics of the course, the goal being to rank the grade of theoretical knowledge.
• Programs in C to evaluate skills related to the implementation and manipulation of data structures by means of advanced C programming constructs and to the implementation of variants of standard algorithms.
• Questions on uploaded laboratory exercises.

Gli studenti e le studentesse con disabilità o con Disturbi Specifici di Apprendimento (DSA), oltre alla segnalazione tramite procedura informatizzata, sono invitati a comunicare anche direttamente al/la docente titolare dell'insegnamento, con un preavviso non inferiore ad una settimana dall'avvio della sessione d'esame, gli strumenti compensativi concordati con l'Unità Special Needs, al fine di permettere al/la docente la declinazione più idonea in riferimento alla specifica tipologia di esame.

The examination is done through a written test lasting 120 minutes. The written test comprehends two parts:
1. Exercises/questions on theoretical aspects to check the acquired knowledge.
2. Exercises to check the acquired abilities and programming skills.
The theory section:
• Consists of up to 6 open questions or exercises on theory topics (depending on the time required by each exercise to complete).
• Amounts up to 12 points on the final mark.
• Has a minimum threshold of 6 points out of 12.
The programming section:
• Consists of up to 4 exercises on programming topics.
• Amounts up to 20 points on the final mark.
• Has a minimum threshold of 10 points out of 20.
• Includes problem-solving exercises (functions) and design skills (data structures). Each exercise might also cover the ability to use advanced C features (pointers, dynamic allocation, recursion) and the knowledge of basic data structures and algorithms.
No books or notes are allowed during the examination.
Laptops (except the one for taking the exam), tablets, cellular phones, etc., are strictly forbidden. All students breaking those rules will be reported to the disciplinary committee.
The optional oral examination is accessible only to students that have scored all minimums required for the two parts of the written exam. Students who failed the written test, i.e., have a mark smaller than 18/30, will need to re-take the entire exam. The optionality of the oral examination means that students have the discretion to ask for the oral examination to add a second level of examination, but the oral examination (in all cases) can adjust the written mark in both the positive and the negative direction, such that the final mark will range from failing to 30 with honor.
The oral examination checks the capacity of the student to explain their design choices, use correct technical terms, and describe algorithms. It consists in:
• Questions on all the course topics, the goal being to rank the grade of theoretical knowledge.
• Live programming questions to furtherly evaluate skills related to implementing and manipulating data structures through advanced C programming constructs and implementing variants of standard algorithms.
• Questions on laboratory exercises.

In addition to the message sent by the online system, students with disabilities or Specific Learning Disorders (SLD) are invited to directly inform the professor in charge of the course about the special arrangements for the exam that have been agreed with the Special Needs Unit. The professor has to be informed at least one week before the beginning of the examination session in order to provide students with the most suitable arrangements for each specific type of exam.

© Politecnico di Torino

Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY

Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY