28004 - Foundations of Informatics T-1

Course Unit Page

Academic Year 2018/2019

Learning outcomes

Acquisition of principles, methodologies and tools for designing algorithms that solve problems of a medium difficulty. Ability to apply such knowledge in the development of algorithms and computer programs, using a high-level programing language.

Course contents

Prerequisites: no prerequisites are required to attend this course. Indeed, the student is gradually introduced to the principles and methods of imperative programming, and in particular towards structured and procedural programming styles. The basic and fundamental notions required to understand the course contents are provided within the course itself, and no assumption is made about previous knowledge. Previous experience and knowledge about programming languages might be of some help.


Contents
:

  • Introduction to modern elaboration systems: brief history of informatics, introduction to the von Neumann architecture and to the modern hardware devices, basic concepts of operating systems.
  • Introduction to the concept of algorithm, Turing's specific and universal machines, problems solutions and (non) computable functions, high- and low-level programming languages, syntax definition by means of EBNF grammars.
  • Introduction to the C language: values, types, constants, variables, operators and expressions, pointers, arrays and strings, structures.
  • Structural and procedural programming in C: control instructions, functions, procedures.
  • Input and output in C: I/O primitives, I/O based on the stream abstraction, access to files.
  • Principles and basic methodologies for designing and developing algorithms: solving small-scale problems, iteration and recursion, programs structured in many modules in the C language.
  • Runtime structure of C programs: runtime representation of programs, activation records and functions.
  • Dynamic allocation of memory for scalar types, structures and array; memory managing and memory leaking issues in C.
  • Ordering algorithms: Naive Sort, Bubble Sort, Insert Sort, Merge Sort, and Quick Sort.
  • Introduction to Abstract Data Types (ADT): type definition and operations (constructors, selectors, predicates, functions and transformators). Some fundamentals ADT: lists, queues, stacks.

Readings/Bibliography

C language and programming: when available, the english versions of these textbooks are recommended
- H. Deitel, P. Deitel. "Il Linguaggio C - Fondamenti e Tecniche di Programmazione", Ottava edizione o precedenti Pearson, 2016.
- A. Kelley, I. Pohl. "C: Didattica e Programmazione", Pearson Education, 2004, Quarta Edizione o precedenti.
- A. Bellini, A. Guidi. "Linguaggio C: Guida alla Programmazione", Mc Graw-Hill, 2013, Quinta Edizione o precedenti.


Informatics in general:
- S. Ceri, D. Mandrioli, L. Sbattella. "Informatica: Arte e Mestiere", Mc Graw-Hill, 2004.

Teaching methods

The course is organized in two related modules:

  • Module 1, whose lessons are given in classrooms, provides notions on principles, methods and tools in informatics. The lessons are supported by slides projected by the teacher's laptop, and a copy can be freely downloaded from the course web site before each lesson.
  • Module 2, whose lessons are given in the Engineering School labs, aims to allow the student to "put into practice" the notions acquired in Module 1. To this end, the teacher proposes exercises, case studies and real problems. In turn, the students are encouraged to immediately solve the problems by using the PCs available in the labs, under the supervision of the teacher. The lessons are supported by slides projected by the teacher (slides available on the course web site before each lesson).
Classrooms and labs are interspersed each other, so that the introduction of a concept or an element of the language together with some examples is followed by a lab lesson, where the student is asked to use the acquired knowledge to solve problems using "programming in-the-small" techniques in C. For this reason, a content introduced within the Module 1 is usually tackled one week later within Module 2, so that the student is given enough time to acquire the new notions.

Summing up, the two modules are strictly related each other, since they provide two different viewpoints on the same topics: the acquisition of the course contents is fully achieved only if both the viewpoints and their aspects have been deeply explored by the student.

Assessment methods

The achievement of the learning goals is verified by the student itself, by means of the exercises proposed during the labs, and at the end of the course, by means of a final exam.

The final exam replicates the structuring of the course into two modules. The student is required to pass two different tests, a written one and a programming test:

  • The written test (one hour duration) is held in the classroom, and it concerns few small exercises and/or open questions about the course contents. The marks of this test sum up to 12 points, with a minimum threshold of 7/12 points; below the threshold the test is considered as "failed". During the written test it is strictly forbidden to consult textbooks, personal notes or any other external source.
  • The lab test (two hours durations) in the laboratories, and consists in solving a small problem by designing and developing a program in C. The test is done directly at the PC, and at the end the student is required to submit (through a simple web-based system) the source files of the program. The marks sum up to 20 points, with a minimum threshold of 11/20; below this threshold the test is considered as "failed". Dureing the test the student can conuls any textbook, perosnal notes and other personal material; moreover, the student can access all the materials provided in the course web site, including the course slides.


The final mark is given by the sum of the points achieved in the two tests, if successfully passed. The marks obtained by the sum must be considered on a maximum of 30; if the marks should exceed the 30 points, the final mark will be "30 with honor / 30". When deemed necessary, the teachers will ask the student to pass a further oral exam, with the aim of confirming the final mark.

The student can ask for a further oral exam, to increment the marks (max two points). In such case, questions of the (non mandatory) interview will be about all the topics and contents introduced within the course.

The student can take the two tests in any order, and within one or more exam sessions, indifferently. E.g., it is possible to take one test in January, and the other in June. However, given the deep relation between the modules and between the test, the student is strongly suggested to take both the tests within the same session.

The student can take the tests many times, either because previous tests were failed, or because the marks were not satisfactory. When a student submit the test to the teacher, the results obtained in the previous tests are voided, and only the more recent marks (for each test) will be taken into consideration.

Teaching tools

Teaching materials: all the slides used during the lessons (in classrooms as well in labs) are available in electronic format and can be accessed/downloaded at the course web site:
http://lia.deis.unibo.it/Courses/FondT1-1819-INF/
The teacher takes care to publish and update the slides, and to make them available few days before each lesson.
A comprehensive list of text books and manuals is available on the course web site, and is reported on the course slides as well.
Suggestions for further readings and exercises are made available through the web site. Moreover, the texts of all the final exams of previous years are available, and the students are encouraged to use them to improve their preparation.

Other tools: during the lab lessons PCs with professional developing software environments are installed and available, so that the students can practice the proposed tasks. These professional softwares, listed on the web site, are freely available for the students and can be downloaded and installed on personal PCs.

Links to further information

http://lia.disi.unibo.it/Courses/FondT1-1819-INF/

Office hours

See the website of Paola Mello

See the website of Federico Chesani