25.09.

2020
BOOLE’S ALGEBRA
Is a logical variable true or false value; result of a simple condition
Logical operators: AND, OR, NOT
Logical (literal) variables which can have a value of false or true

Truth tables
All possible input combinations and the results associated to each operation.

Logic sum Logic product

p q p OR q p q p OR q
0 0 0 0 0 0
0 1 1 0 1 1
1 0 1 1 0 1
1 1 1 1 1 1

Negation
p NOT p
0 1
0

Exercise
Complete the truth table for expression “NOT (((p OR q) AND (NOT q))
NOT (0 AND 1)
NOT 0 TRUE
00 NOT (O AND 1) = 0
01 NOT (1 AND 0) = 1
10 NOT (1 AND 1) = 0
11 NOT (1 AND 0) = 1

Two logical expressions are equivalent if they have the same table of truth.
Useful properties
- Commutative: “p OR q” <-> “q OR p”, “p AND q” <-> “q AND p”
- Associative: “p AND (q AND r)” <-> “(p AND q) And r”, “p OR (q OR r)” <-> “(p OR q) OR r”
- Distributive: “p AND (q OR s)” <-> “(p AND q) or (p AND r)”, “p OR (q AND s)” <-> “(p OR q) AND (p
OR s)”
- Identity: “p AND true” ⟺ p, “p OR false” ⟺ p
- Complement: “p AND (NOT p)” ⟺ false, “p OR(NOT(p))” ⟺ true
- Idempotence: “NOT(NOT(p))” ⟺ p
- DeMorgan’s Law: “NOT(p AND q)” ⟺ “NOT p OR NOT q”, “NOT(p OR q)” ⟺ NOT pANDNOTq

1
 INTRODUCTION IN C
C language
- High level programming language
- Developed in 1970 (C-ANSI standard)
- Popular and suitable for a wide range of application
- Most operating systems are still written in C (or C++)

C language is:
 imperative: set of instructions (order to computer)
 declarative: declare every variable
 structured: basic constructs for definition of sequence, selection and iteration
 sensitive: discriminate between upper- and lower-case characters

Structure of a C program
Program is a structured text file, that can be compiled (i.e. translated into machine language).
Learning its syntax and semantics to make it compilable (syntactic verification) and act as expected
(semantic verification)

First program:
Hello word!

#includes <stdio.h> GLOBAL DECLARATIVE PART

void main() {
LOCAL DECLARATIVE PART (EMPTY)
printif(“Hello World!”); EXECUTIVE PART (ALGORITHM)

}
Specifies the inclusion of the stdio library that allows you to use the input/output functions
Main indicates the start of the actual program
The program contains only one instruction which must end with ;

Comments: text between /* */

 Find a computer capable of running it

 The computer is able to process instructions only in machine language
 Find a way to transform C (high level language) into machine language (low level language)

The development of a program

Machine language Analysis of the
problem
- Few instructions
- Precise language
- Complete control of computer resources Definition of the
algorithm
High-level languages
- More comprehensible to humans
- Precis and synthetic language Coding (C language)
- Symbolic reference
- Close to our natural language
Compilation
(machine language)

Compiler: translation
2 Execution
The abstract machine
Program in C: machine that is a bit more abstract than the real calculator
Memory  cells  data: numbers, characters, strings
Approximations: no limit to the number of cells, no limit to the numerical values contained

Standard input: strin

Standard output: stdout

Organization of a program
Global declarative part:
- guidelines include specifying which libraries are used
- guidelines defined to define constants to be used in the program
- the definition on new types data
- the declaration of global variables
Local declarative part: the variables are declared
Executive part: are specified the instructions that implement the algorithm

Example
#includes <stdio.h> Global declarative part
#define PI 3.14 Directives include
void main() {
float r, a; Local declarative part
scanf(“%f”, &r); Executive part
a = r * r PI;
printf(“%f”, a);
}

Directives (special instructions addressed to the compiler) includes:

- Start with the # character and do not end with ;
- Indicates the intention to use an external library

main
- Keyword, indicates the start of the actual program
- Subsequent instruction will be those actually performed by the computer
- The instructions that make up the main program are enclosed in curly brackets {}

Declaration of a variable:
type_variable name_var;
We can also declare several variables of the same type by separating them with a comma
type_variable name_var1, name_var2;

Variable must be declared prior to any executable instruction. The name of a variable must be unique (i.e. it
must not have already been used) and must not be a reserved word.

The variable declaration indicates which and how a variable will be used by the program
- Defines the unique symbolic identifier (name)
- Defines the type, suitable for the variable
- Reserve a memory location of adequate size to contain the type
- Uniquely associates the memory address to the name
- Allows you to detect errors during compilation about misuse of the variable in the program
3
 - Variable = location in the main memory
- Before the execution: clear how much space the variable will require
- Accesses to the variable = access to the memory
- Program execution: the variables always have a well-defined value

Types of data
Macro-classes: built-in types (default); user-defined types

Char
- 8 bits (1 byte)
- Represents characters in ASCII
- In memory: numerical value from 0 to 255
- In the code: simple quotas
‘l’,’a’,’a’,’b’,’c’,’d’
- Special characters are represented by a specific sequence of two characters starting with \
‘\n’ : breakline
‘\t’ : tab

Int
- At least 16 bits (2 bytes), depends on the type of computer architecture
- Represent the relative integers
- Value in two complement’s form -32768 to + 32767
- Modern calculators: 32 bites (4 bytes), values from -2147483648 to +214783647

Float
- 32 bits (4 bytes)
- Represent the rationales in floating point
- Values expressed through mantissa and exponent, from -10E -38 to 10E+38

Double
- 64 bits (8 bytes)
- Rationales in floating point
- Represent the rationales in floating point
- Values expressed through mantissa and exponent, from -10E -38 to 10E+38

Constants: in the directives part

 Explicit: express values directly
24 constant type int
3,145 double constants
‘A’ constant type char
 Symbolic
Symbolic names to indicate prefixed values (greater readability)
Type implicitly expressed in the value
Must be previously declared

Declaring constant
- Associating a symbol to a value
- Constant never change during the execution
- To declare it #define directive
- Name of constant = macro

The compiler and macros

4
Compilation: macro reference = corresponding value
The constant is as if had not been declared, for this the compiler does not reserve
any memory location for a macro.

Executive part
Contains instructions: assignment (=)
input/output
control (conditional (if, else); iterative or cycles (while, do-while,
for); flow control (goto))
- Every one terminates with ;
- Multiple simple instructions can be grouped together with {} to determinate a block
- It is not necessary; after } as the block is already an instruction
- Block can be nested together

Operators
Arithmetic operation: +, -, *, /, %
Assignment: =
Logical operator:

Assignment x = x+1;
It is an operator and is indicated with the symbol = (equal)
To the left of the operator there must always be a variable. On the right there can be a constant, a variable,
an expression.

Execution of assignments
1. Evaluation of the expression
The value of the variable that appear there is stored in the corresponding cells, and is read from there.
2. Storing the results
Expression result are stored in the variable to the left of the symbol =

Operators C Operations Precedence

() Parenthesis Evaluate first.
*, /, % Multiplication, Division, Module Evaluate for second.
+, - Addition, Subtraction Evaluated for third parties.
= Assignment Rate for last.

Input: printf()
Output: scanf()

Print on video
Printf(control string, items to be printed);
Is the identifier reserved for the control string (enclosed between double quotes “”) contains: alphanumeric
characters to print on screen; conversion and/or format characters (preceded by the % symbol), used to
interpret the values of the elements to be printed; print control characters, ASCII characters that do not
correspond to any printable symbol have print format effects.

Keyboard input
scanf(control string, list of variables);
Control string contains: conversion and/or format characters (preceded by the % symbol) used to interpret
the values of the elements read from the keyboard.
5
 -%d integer number
-%f number in floating point
-%c character
List of variable identifiers, the variables must be preceded by the symbol &, the list is ordered with respect
to the conversion characters.

28.09.2020
clang file.c -0 file  translate
./nomefile  to execute the program

Scan function
scanf (f = formatted) is used to obtain a value from the user. The function reads from the standard input
(the keyboard)
scanf( “%d”, &a);
Format control string
Type of data that
%d conversion specifier indicates that the data should be an integer
% is treated by scanf as specia character that begins a conversion specifier

Address operator & + variable name

Tells scanf the location in memory at which the variable integer1 is stored

Compatibility between types

The data types of the variables involved in an operation must be identical (or at least compatible).
Compiler: check the compatibility, in some situation: automatic conversion rules between types (cast)

Assignment operations:
• The value to the right of the operator will be converted to the type of the variable on the left
• The type conversion is painless if the data type on the right is lower than the type of the variable on
the left of the operator, according to the following hierarchy:
char < int < float

Arithmetic operations:
• The smaller type value is converted to the bigger type

The conversion of a float value into an int value results in the loss of the fractional part.
You can also force the conversion of a value from one type to another by the cast operator ()
Specify in round brackets the type to convert to in front of the name of the variable/constant.

Char type
Is represented thought a numeric encoding based on integer (1 byte)
c = 1 the value 1 is assigned to c
c = “1” the character encoding 1 is assigned to c(49)

Errors
- Syntactical error
Instructions do not follow the syntactical rules of C
Compiler reports errors and does not generate the executable
- Semantic error
The algorithm does not solve the problem

6
 Compiler can not notice such errors

CONTROL STRUCTURES
Bohm and Jacopini’s theorem
All programs could be written in terms of only three control structures, namely
sequence structure selection structure iteration structure

single-
selection while

Double- do… while

selection
for
Multiple-
selection

Single: select or ignores a single action if

Double: select between two different action if…Else
Multiple: select among many different actions if…Else
if…Else

29.09.2020

The if selection statement

if(<condition> {
<if block>
}
Exercise
Suppose the passing grade on an exam is 18. Draw a flowchart that prints “Congratulation!” when the
condition: “The student’s grade is greater or equal to 18” is true.

#include <stdio.h>      
      
int main() {
  int grade;             /*We have to initialize the variable*/
  printf("Please insert the grade\n");  /*n stands for a new line*/
  scanf("%d",&grade);        /*%d for an integer number,&+address
of the variable*/
  if(grade >= 18) { 
7
    printf("Congratulations!");
  }
  return 0;
}

The if… else selection statement

if(<condition> {
<if block>
}
else{
<else block>
}

We can write other instructions inside both blocks <block if> and <else block>.
If we nest several <if block> and don’t put brackets, the first <else block> will correspond to the last if, the
second other to the penultimate if and so on…

Exercise
Suppose the passing grade on an exam is 18. Draw a flowchart that prints “Congratulation!” when the
condition: “The student’s grade is greater or equal to 18” is true, and when it’s false it print “Failed :( “.
#include <stdio.h>      
int main() {
  int grade;             /*We have to initialize the variable*/
  printf("Please insert the grade\n");  /*n stands for a new line*/
  scanf("%d",&grade);        /*%d for an integer number,&+address
of the variable*/
  if(grade >= 18) { 
    printf("Congratulations!"); /*Use identation to distinghuish at glance the statement inside blocks*/
  }else{
    printf("Failed:(\n");
  }
  return 0;
}

Logical condition
False = 0
True = any integer other than 0
Relational operators: = = != > < <= >=
return 0 (false) or 1 (true)
Logical operators: !, &&, | |
return 0 (false) or 1 (true)

 Precedence of operators
Associativity
() From left to right
!- (cast) From right to left
*/% From left to right
+- From left to right
> < <= >= From left to right
== != From left to right
8
 && From left to right
|| From left to right
= From right to left
, From left to right

Exercise
Write a program that acquires an integer that represents a grade and print «D» if the grade is less than 10,
«C» if the grade is between 10 and 17 extremes included, «B» if it is between 18 and 24 extremes included,
«A» if greater than 24.

#include <stdio.h>

int main() {
int grade;      
printf("Please insert the grade\n");
scanf("%d",&grade);     
if(grade < 10) {
printf("D \n");
}else if(grade >= 10 && grade <=17) {
printf("C \n");
}else if(grade >= 18 && grade <=24) {
printf("B \n");
}else{
printf("A \n");
}
return 0;
}

Common error:
- condition must always be enclosed in brackets ()
- the if instruction should not end with the ;

While
while(<condition>){
<block>
}

- Iteration statement that allows you to specify that an action is to be repeated while some condition remains
true
- The statement(s) contained in the while iteration statement constitute the body of the while.
- The condition will become false (when n becomes negative). The iteration terminates, and the first
statement after iteration structure is executed.
 Initialization: all variables must be declared and initialized before the evaluation of the cycle condition
 Guard: a logical condition that determines the permanence into the cycle must be properly defined
 Update: at least one of the variables that used inside the guard must be modified inside the cycle

9
Program

#include <stdio.h>
int main()
{
int n, f;
printf("Enter a non negative number\n", n);
scanf("%d", &n);
printf("You have entered %d\n", n);
if (n < 0){
printf("Error, you have entered anegative number!\n");
return 1;
}
f = 1;
while(n>=0){
   f = f*n;
   n = n-1;
}
printf("The factorial is %d\n",f);
}

Exercise
Draw a flowchart of an algorithm that acquire a positive number and visualize all integers from 0 to the
acquired value.

Code the algorithm using while iteration.

#include <stdio.h>

int main() {
  int n;
int c;  
c = 0;
  scanf("%d", &n);
  while(c <= n){
    printf("%d\n",c);
  c = c+1;

10
  }
return 0;
}

Exercise
A class of ten students took a quiz. The grades (integers in the range 0 to 100) for this quiz are available to
you. Determine the class average on the quiz.

#include <stdio.h>
int main()
{
float sum,average;
int g,cnt, n; /*g is the grade and cnt is the counter*/

cnt=0; /*Set counter to 0*/

sum=0;
average = 0;
n = 10; /*Numbers of students*/

/*First instruction out of the while*/

printf("Insert the grade");
scanf("%d",&g);
sum=sum+g;  /*Add the grade to the total sum*/
cnt++; /*Add one to the counter*/

while(cnt < n)  /*Insert the grade and add it to the sum until all the students
have inserted their own grade*/

{
printf("Insert the grade");
scanf("%d",&g);
sum=sum+g;
cnt++;
}
average=sum/10; /*Calculate the average*/
printf("The average is:%f",average);
return 0;
}

11
 05.10.2020
Do- while syntax
do{ <block>
} while (<condition>);
<instruction>
It executes the block until the while condition is verified.

For
for (initialization; test; modifythe control variable) {
<instructionblock>}
<instruction>
…

for (c=0; c<=n; c=c+1)

{printf("%d", c);
}

Initialization
Loop Continuation test
Increment of control variable
Block of instruction to be performed iteratively
C is the control variable

Increment expression
- i++ (increment)t
- variable++ (access to the variable, increment it)
- ++variable(increment it, access)
- i- (decrement)

ARRAY
data_type array_name[size_of_the_array]

Associate to the same object a collection of value.

= is a contiguous memory location of fixed size that all have the same type (simple type or compound)
Array name: only letters, digits and underscores
Position number in [] = index or subscript, must be integer or an integer expression
Fixed: length must be known at compilation time

12
 - Every element is denoted by the subscript index (position inside the array)
- Index between 0 and DIM-1

Elements can be initialized when the array is defined by following definition with an equal sign and braces
{} contained a comma separated list of array initializer.

Vet = memory address of the first element

Memory location is allocated to contiguous addresses. Overall space occupied in memory = space needed
for each data type multiplied by the dimension of the array

Array dimension
Not possible to access to an element that is greater than its dimension

Operations in array
Every element = a variable of the type used in the declaration
 You can use all the admissible operations for that type of data

Copy of array
for (size_t i = 0; i < DIM; i++)
a[i] = b[i];

An array of array(matix)
int m[DIM1][DIM2];

Variable m = array of DIM2 elements, each element being an array of DIM1 elements.

16.10.2020
Char array
To memorize string, array do not utilize all positions but only an initial sub-part.
Where the string ends: ‘\0’ (additional position for the null character)

Intput/Output
scanf(“%s”, str) //Not preceded by &
To read a string and store in int str.
 Terminated by a space, tab or return
 Automatically hangs the null character at the end of the read character sequence

printf(“%s”,str) //Operator on individual elements, not on the entire array

Fgets
Captures from the keyboard a string terminated by a ‘\n’ that can contain spaces.
‘\n’ is retained.
char str[DIM +1];
fgets(str, DIM+1, stdin);
Saves the string entered in the str array.

13
Functions to handle string
#include <string.h> library: number of functions for string manipulation

stringcpy() Copies a string from one array to another

strcar()  concatenates two strings
strcmp()  compares two strings to determine whether they are equal or not (return to 0 only if the two
strings are equal)

20.10.2020
STRUCTURE
Built-in and derived data type
Primary: char; int; float; double
Derived: array(homogeneous information of fixed size), structure (heterogeneous info)

Limits of the built-in data type

x-y coordinates of the vertices of a triangle  2 floating variables for each point
arrays
Not just one value to a label but a set of different values.

Structure
To declare variables that by means of a single identifier (tag) groups together heterogeneous info
Prefixed set of non-homogeneous fields (name, type)

Declaration
Structure type declaration + Structure type variable declaration
New type of structure: put in the part of global statements. Not take up any memory space.
Declared variable will occupy a space corresponding to the declared types.
Structure type:
struct name_type1{
type_field1 name_field1;
type_field2 name_field2;
type_field3 name_field3;
};
Tag
Fields/members of the struct: unique names

Structure variable:
struct name_type1 name_variable;
Can be variables of primitive types or aggregates (arrays)

Declaration of struct-alternative
Structure type:
typedef struct {

14
 type_field1 name_field1;
type_field2 name_field2;
type_field_name3;
} name_type2;

Structure variable:
struct name_type2 name_variable;

Initializing structure
Can be initialized using initializer list as with arrays.
Follow the variable name in the definition with an equal sign and a braces-enclosed, comma separated list of
initializers.
Initializers < members in the structure  remaining members automatically initialized to 0 (or NULL)

Also: assigning a structure variable of the same type

assigning values to the individual members of the structure

Access to the fields of a structure

name_var.name_field1

Valid operation on a structure

- Assigning struct variables to struct variables of the same type
- Taking the address (&) of a struct variable
- Accessing the members of a struct variable
- Using the size of operator to determine the size of a struct variable

Operation between structures

Operators that can be used for the individual fields are all the legal operators for that type of fields (global
operators can be used)
NOT == Comparison: field by field

Type definition and array

typedef type_elem type_array [DIM];

 new name type type_array

is an array of DIM elements of type_elem type
Usually put in the part of the global statements, does not take up any memory space (the declared variable
will occupy a space corresponding to the declared type)

FUNCTIONS
Group of instruction repeated in different parts within the same program  define only once and give it a
name

Subprograms

15
is the set of instructions with a name, defined only once and activable within the program or another
function as many times as desired

- Already defined: pow, cos, printf, scanf…

- Can be used as black box
- Can be collected in libraries

Why?  Abstraction and legibility: enucleate parts of code, functional operation

 Analysis of the problem: the problem can be break down in subproblems address by funct.
 Testing: checking the correctness of the solution (verify the correctness of the individual
subprograms and then of the entire program)
 Code compactness and efficiency: repeating sequence of instructions in several parts
 Modifiability: only one change applies to all subprograms activations
 Reuse: subprograms not too specific can be collected in libraries (different programs)

Functions and procedures

Two types of sub-programs:
- functions (receive input value and return an output value)
- procedures (receive some incoming data, perform a task that cannot conceptually be associated
with a function)

Different in: definition and invocation

IN C THERE ARE ONLY FUNCTIONS!

Declaration and definition of functions

 Declaration: name and types of inputs and outputs
 Definition: instructions that make up the function and what the function does

Declaration of a function prototype

<type_result> <function_name> (<parameter_list>);

Defines: the type of returned value

the name of the function
the type of parameters and parameter names
Declaration of a procedure prototype
You must specify that it will not return any value.
void <function_name> (<parameter_list>);

Definition of a function
Must be put after the main (same structure), must be equal to the prototype, parameters names cannot be
omitted!

Parameters
 Symbolic reference (identifiers) to objects used within the function
 Used by function as if they were locally declared variables
 Initial value of formal parameters is defined when the function us called using the current
parameters (parameters passing)
16
Return
return <expression>;
The last executed instruction of a function, indicates: the value returned, the point where the control returns
to the caller
If it returns a type:
- must be at least one return instruction
- may be multiple return instructions but alternative to each others
- function can return a basic type or structure
- cannot return arrays

Call to a function
= an operation that must be inserted in the body of the main or other function
= indicates the point where the part of the code inside the function body id to be executed
<variable> = <function_name> (par1, par2, …);

Invoking a function without return value (void) or ignoring the return value
<function_name> (par1, par2,…);

Both cases:
- par1, par2 are the current parameters that must correspond by order and type the formal
parameters
- current parameters can be variables, constant or expressions defined in the calling environment
(values at the time of the call are copied into the formal parameters)
- you can specify parameters of basic type and struct type (NOT ARRAY!)

There are always a caller (the main invoking the function) and the function invoked
Caller: able to provide the current (specific) value on which perform the operations defined in the function
Called function: able to provide the caller with the processing result

Parameters
Associating the current parameters to the formal parameters.
 Passage by value
 Passage by address

Scope
 Functions: a mechanism has been introduced to define small “sub-programs” able to solve “sub-
problems”
 Defined their variables and the channel of communication with the calling code
 Support this: management of variable identifiers and memory during execution
 Scope of an identifiers: specifies the part of the program where that identifier can be used
 Global environment: set of identifiers (global declarative part); visibility rules (all program and the
main)
 Local environment of a function (and main): set of identifiers in the local declarative part and
identifiers defined in the header (formal parameters); visibility rules (only inside the function and
main)

17
  The struct: § The fields of the structure
§ Visibility rules: visible only as part of the structure

POINTERS
Enable programs to accomplish pass-by-reference, to pass functions between functions, and to create and
manipulate dynamic data structures.
Are variables whose values are memory address.
Contains an address of a variable that contain specific value  indirectly reference a value.
Declare a pointer:
int * p;
p is a pointer to int (right to left)
* to declare pointer variables

Initialization: to NULL = point nothing (NULL = symbolic constant defined in <stdeff.h>)

to 0
to an address
& operator: address operator is a unary operator that returns the address of its operand p= &y;
* operator: referred to as the indirection operator or referencing operators (return to the value of the object to
which its operand points) *p = ?;

Actual parameters: values that are passed to the function when it is invoked
Formal parameters: variables defined by the function that receives values when the function is called

Passing arguments to the functions

 Pass by value (all arguments in C): different memory for each function call
 Pass by reference: when calling a function with arguments that should be modified, the addresses
of the arguments are passed

Activation record
Variables of a function stored in contiguous cell of memory.
18
Function is invoked: a portion of the memory called activation record is reserved to that function.
is created when the function is invoked
is cleared when the function terminates its
execution
Portion of memory that contains the activation record = stack. Last element inserted = the first one to be
extracted (LIFO).

Function is called:
- space memory is reserved at the top of the call stack
- this is cleared when the function ends
Activation record contains:
- scope of the function
- data necessary to handle the execution of the function

Passing an array
void invertArray(int[], int)

Using a pointer: void invertArray(int*, int);

19