Course Details for A.Y. 2015/2016

Course Objectives

The course is aimed at the acquisition of the fundamental concepts of computer science without neglecting the experimental aspects of the discipline and its immediate application. It begins with a description of the computer system in general and then focus on high-level programming techniques with the goal of developing in students the ability to design programs. The reference language will be C++, although the concepts presented in the course are language-independent and easily applicable in any imperative language like Pascal or Java. The course also deals with the study of fundamental algorithms such as sorting and searching algorithms together with the calculation of their running time.

Course Content

• 1 . Architecture of computer systems. Processes and processors. Problems, algorithms and programs. Programming languages. Computer architecture. Von Neumann model. Positional base-b numeral systems. Base conversions. Representation of negative numbers in sign-magnitude and two's complement. Representation of real numbers in floating-point. ASCII code. Boolean algebra and main logic functions. Dev-C + + Programming Environment.
• 2 . Programming elements. Development of algorithms. Concept of variable. Elementary operations: reading, writing, assignment, and comparison. Flowcharts. Pseudo-code. Control structure if-then-else. Cycles with pre-condition and post-condition. Control structures while-do and do-while. Algorithm design with cycles. Control over input data. Translation in C++. Basic constructs of C++. Structure of a program. Declaration and code sections. Declaration of variables. Classification of types. Simple types, internal representation and operations. Numeric and conditional expressions. Assignment statement. Compound statement. Binary selection. Standard functions of input/output. Loop statements (WHILE, DO-WHILE, FOR). Construction of nested loops. N-ary selection.
• 3 . Programming with structured types. Array type: definition and memory representation. Type declarations with typedef. Programs with vectors. Two-dimensional arrays. Programs with matrices. String type. Struct type. File Type. Primitives for sequential files.
• 4 . Programming with functions. Subroutines. Top-down design. Parameters. Declaration of functions. Global variables. Local variables. Formal and actual parameters. Passing parameters by reference and by value. Memory usage. Variables Life cycle. Visibility of variables. Masking of variables. Recursion.
• 5 . Efficiency of the programs. The function t (n). Cost model. Calculation of t(n) for iterative programs. Best case, worst case, and average case. Computational complexity. Asymptotic notation , , . Boundaries to the complexity of a problem. Calculation of t(n) for recursive programs. Solution of the recurrence for the factorial and Fibonacci numbers .
• 6 . Fundamental algorithms. Sequential search. Binary search. Insertion and deletion in a sorted array. SelectionSort. InsertionSort. Bubblesort. Mergesort. Quicksort : analysis of the complexity in the best case and worst case.
• 7 . Programming with pointers. Static and dynamic memory management. Pointer type. Working with pointers: assignment, new, delete, reference, dereference. Constant null. Use of pointers. Creating dynamic arrays. Similarity between arrays and pointers. Creating dynamic arrays. Linked structures in dynamic memory. Linked lists with pointers. Programs with linked lists .

Learning Outcomes (Dublin Descriptors)

On successful completion of this course, the student should

Prerequisites and Learning Activities

There are no compulsory computer science prerequisites, but a so-called informatics alphabetization would be helpful (such as being able of working with any commonly available personal computer with its windows-based operating system and being able of writing a text). Also helpful are basic notions of algebra and mathematical analysis since they are used during the course to design programs to solve simple mathematical problems.

Assessment Methods and Criteria

Computer programs to be written at home and uploaded online. Written test and oral exam.

Textbooks

• E. Clementini, Fondamenti di informatica: Programmazione strutturata in C++ , Carocci Editore. 2006.    

Internet Resources

Course page updates

• A.Y. 2012/2013
• A.Y. 2013/2014
• A.Y. 2014/2015
• A.Y. 2015/2016
• A.Y. 2016/2017
• A.Y. 2017/2018
• A.Y. 2018/2019
• A.Y. 2019/2020