FOUNDATIONS OF COMPUTER SCIENCE Cp - I

The course introduces the knowledge of the principles of information technology and procedural programming.

The course has the primary objective of providing the student with the knowledge of the main data structures, the basic algorithms and the rudiments of computational complexity.

Further, the course provides the student with the techniques and tools for the development of application programs using the ANSI-C programming language, with particular emphasis on "problem solving" and error discovering mechanisms.

Lectures are arranged into elementary teaching units (UDE) according to the skills that have to be developed.

The main teaching methods are as follows:

• Lectures, aimed at providing the basic theoretical knowledge and all the language syntactic elements;
• Exercises, proposed and solved by the teacher, aimed at improving student’s “problem solving” skills, and introducing the use of IDEs;

Further, the teacher assigns individual activities to students to be solved independently and to be discussed in the classroom.

Module 1

• Information processing and algorithms - Algorithms and programs - A graphic notation for algorithms representation - Programming languages - Programs design.
• Information representation: Numerical systems - Numerical systems conversion - Binary number system - Binary number operations - overflow and underflow - Integers representation - Numbers with sign representations - Fixed-point and floating-point representation - Characters representation - Boole's Algebra, Logical Functions, Logical Expression, Applications of Boolean algebra.
• Computer organization overview: Structure of a computer: main memory, central unit, instruction set architecture.
• Basics on computer systems: basic software: Translation and program execution - programming environment - Programming languages: imperative languages - Compilers, Linkers, Implementation briefs: Preprocessor - Comments - Libraries and header files.

Module 2

• C language foundamental elements: C syntax - Structure of a C program - Compiling a program - Types of data and representations - Main data types - Identifiers - Variables - Access modifiers - Constants - Operators - Control structures - Selection instructions - Iteration rnstructions - Jump instructions - Expression instructions - Block statement.
• Arrays, strings and pointers: One-dimensional arrays - Array as a pointer - Arrays as a function argument - Strings - String arrays - Multidimensional arrays - Pointer variables - Operators and expressions with pointers - Function pointers - Dynamic memory allocation.
• Arrays, strings and pointers: One-dimensional arrays - Array pointers - Arrays as a function argument - Strings - String arrays - Multidimensional arrays - Pointer variables - Operators and expressions with pointers - Array pointers - Function pointers - Dynamic allocation.
• Functions: Function visibility rules - Function arguments - Main arguments - Return statement - Return values from a function - Recursion - Identifiers declarations and field of action - Parameter binding techniques - side effects and function implementation.
• User-defined structures, unions and types: Structures - Arrays of structures - Structures as arguments of functions - Pointers to structures - Arrays and structures within other structures - Union - Enumerations - Sizeof - Tipedef.
• I/O from file and console: Read and write characters and console strings - Console-formatted I/O - Channels - File.

Module 3

• Dynamic memory allocation.
• Computational Complexity: Program Efficiency, Notations O and W, Program complexity evaluation, Recurrence relationships.
• Sorting algorithms: Sorting algorithm classes - sorting by selection (selection sort) - insertion algorithms (insertion sort) - bubble sort exchange algorithms, quick sort, merge sort.
• Abstract data types: Lists, Queues, Stacks, Binary Trees.

• [BeGu] Bellini, Guidi. Linguaggio C. Guida alla programmazione. McGraw-Hill
• [Pel] Pellegrino Principe. C guida alla programmazione. Apogeo
• [Be] Belagurusamy. Programming in ANSI C. McGraw-Hill