Stefano Berretti, Laura Carnevali, Enrico Vicario, "Fondamenti di Programmazione: linguaggio c, strutture dati e algoritmi elementari, c++", Società Editrice Esculapio, Bologna, 2017
Learning Objectives
- Knowledge and understanding of basic computer science concepts and main functionalities of a basic computer system
- Knowledge and understanding of general methods of studying a programming language, algorithmic approach to problem solving, and general methods of reasoning in the design of data structures and algorithms
- Knowledge and understanding of the c language
- Knowledge and understanding of the structure and principles of operation of a computer system, the relationship between the c language and its execution environment, and the process of compilation, assembly and linking
- Advanced ability to design and develop data structures and algorithms in the c language
- Ability to formalize the problem of complexity of an algorithm
- Ability to formalize the concept of correctness of an algorithm
- Ability to develop, debug and apply basic algorithms to cases of engineering interest to solve information or numerical problems
Prerequisites
The course is aimed at students who have logical reasoning skills, aptitude for deductive knowledge processes, attention and application to problems. Students who have experience in programming are initially facilitated. The course is however designed for students who have no knowledge of computer science.
Teaching Methods
Lessons are given by presenting the topics on the blackboard. The course includes 20 additional hours of tutoring lessons (classroom exercises).
Further information
Students are invited to view the course page on Moodle (https://e-l.unifi.it) for more information.
Type of Assessment
The exam consists of a written and an oral test aimed at assessing the theoretical and practical skills acquired on the course topics.
- The written test consists in solving c programming exercises and discussing some of the course topics. The written test is developed on paper. The available time is 1 hour. Consulting books and notes as well as using the calculator is not allowed. Text, solution and results of each written test are published on the course page before the next oral test.
- Only candidates who obtain an assessment of at least 15/30 in the written test are admitted to the oral test. To access the oral test, candidates must implement the solution of the proposed programming exercises by creating self-contained programs (using any development environment). During the oral test, these programs must be provided on a laptop (or on a USB memory device including sources and executables). The oral test starts with the discussion of this work and continues with an in-depth examination of the contents of the program.
Students who obtain an insufficient evaluation in a written or oral test can take the next written test.
Students who pass the written test have the possibility to take the oral test in the same appeal or in any of the next appeals.
Students who fail the oral test must repeat the written test.
Course program
1. Low level representation
- Data representation: positional coding; base conversion algorithms; unsigned integers; characters; signed integers; floating point values.
- Statements representation: assembly language and machine code (arithmetic instructions, memory usage, and control flow statements); execution on a processor; compiling, assembling, and linking.
2. High level representation
- Language definition: syntax; grammar; syntactic tree; the BNF metalanguage; semantics.
- The c programming language: data types, variables and constants; operators and expressions; pointers; arrays; statements; functions; data structures; standard library; system calls.
3. Data structures and elementary algorithms
- Lists: sequential lists; linked lists with indexes; linked lists with pointers.
- Iteration and recursion.
4. Elementary algorithms
- Computational cost and complexity.
- Search algorithms: sequential search; binary search; jump search.
- Sorting algorithms: sequential sort; bubble sort; merge sort; quick sort.
- Minimum complexity of a problem: the case of sorting.