Vittorio FUCCELLA | PROGRAMMING AND DATA STRUCTURES

cod. 0512100052

PROGRAMMING AND DATA STRUCTURES

	0512100052
	DIPARTIMENTO DI INFORMATICA
	EQF6
	COMPUTER SCIENCE
	2020/2021

PERCORSO COMUNE

	OBBLIGATORIO
	YEAR OF COURSE 1
	YEAR OF DIDACTIC SYSTEM 2017
	SECONDO SEMESTRE

TEACHING UNITS

SSD	CFU	HOURS	ACTIVITY	TYPE OF ACTIVITY
INF/01	6	48	LESSONS	BASIC COMPULSORY SUBJECTS
INF/01	3	24	LAB	BASIC COMPULSORY SUBJECTS

PROFESSORS

	VITTORIO FUCCELLA T Curriculum
	MARCO ROMANO Curriculum

	Objectives
	KNOWLEDGE AND UNDERSTANDING KNOWLEDGE OF BASIC ALGORITHMS AND DATA STRUCTURES. ITERATIVE AND RECURSIVE PROGRAMMING TECHNIQUES AND KNOWLEDGE OF STATIC AND DYNAMIC DATA STRUCTURES. APPLYING KNOWLEDGE AND UNDERSTANDING •TO ANALYSE PROBLEMS AND IMPLEMENT APPLICATIONS THAT SOLVE THEM BY DESIGNING AND IMPLEMENTING ALGORITHMS AND DATA STRUCTURES IN C LANGUAGE. IMPLEMENTATION OF SMALL SOFTWARE PROJECTS IN C; •TO SELECT ALGORITHMS AND DATA STRUCTURES SUITABLE TO IMPLEMENT AN APPLICATION BASED ON ITS REQUIREMENTS; •TO FIND SUITABLE ITERATIVE OR RECURSIVE SOLUTIONS IN ORDER TO HANDLE A SPECIFIC PROGRAMMING PROBLEM; •TO COMMUNICATE INFORMATION, IDEAS, PROBLEMS, EXPLANATIONS ABOUT SIMPLE PROGRAMMING PROBLEMS USING STANDARD ALGORITHMS AND DATA STRUCTURES.

KNOWLEDGE AND UNDERSTANDING
KNOWLEDGE OF BASIC ALGORITHMS AND DATA STRUCTURES. ITERATIVE AND RECURSIVE PROGRAMMING TECHNIQUES AND KNOWLEDGE OF STATIC AND DYNAMIC DATA STRUCTURES.

APPLYING KNOWLEDGE AND UNDERSTANDING
•TO ANALYSE PROBLEMS AND IMPLEMENT APPLICATIONS THAT SOLVE THEM BY DESIGNING AND IMPLEMENTING ALGORITHMS AND DATA STRUCTURES IN C LANGUAGE. IMPLEMENTATION OF SMALL SOFTWARE PROJECTS IN C;
•TO SELECT ALGORITHMS AND DATA STRUCTURES SUITABLE TO IMPLEMENT AN APPLICATION BASED ON ITS REQUIREMENTS;
•TO FIND SUITABLE ITERATIVE OR RECURSIVE SOLUTIONS IN ORDER TO HANDLE A SPECIFIC PROGRAMMING PROBLEM;
•TO COMMUNICATE INFORMATION, IDEAS, PROBLEMS, EXPLANATIONS ABOUT SIMPLE PROGRAMMING PROBLEMS USING STANDARD ALGORITHMS AND DATA STRUCTURES.

	Prerequisites
	BASIC KNOWLEDGE ABOUT PROCEDURAL PROGRAMMING IN C PROVIDED BY PROGRAMMING I COURSE.

	Contents
	1.ADVANCED PROGRAMMING IN C: SELF-REFERENTIAL STRUCTURES; DYNAMIC STRUCTURES (LISTS, TREES) - (3 HOURS OF THEORY, 1 HOUR OF LABORATORY); 2.GENERAL INFORMATION ABOUT MEMORY MODELS, STATIC AND DYNAMIC MEMORY, STACK AND ACTIVATION RECORDS, NAMES AND ENVIRONMENT, STATIC AND DYNAMIC SCOPE RULES (3 HOURS OF THEORY); 3.POINTERS AND DYNAMIC MEMORY ALLOCATION (2 HOURS OF THEORY, 2 HOURS OF LABORATORY); 4.ABSTRACTIONS AND MODULES: ABSTRACTION TYPES, INTERFACE AND IMPLEMENTATION OF A MODULE, REALIZATION OF MODULES IN C (3 HOURS OF THEORY, 2 HOURS OF LABORATORY); 5.RECURSION: GENERAL ASPECTS AND DEFINITIONS, RECURSION AND ITERATION, MANAGEMENT OF THE EXECUTION OF RECURSIVE PROGRAMS (3 HOURS OF THEORY, 2 HOURS OF LABORATORY); 6.ITERATIVE AND RECURSIVE ALGORITHMS ON ARRAYS, SORTING ALGORITHMS (6 HOURS OF THEORY, 3 HOURS OF LABORATORY); 7.CONSIDERATIONS ON COMPUTATIONAL COMPLEXITY (2 HOURS OF THEORY, 1 HOUR OF LABORATORY); 8.ABSTRACT DATA TYPES (ADTS): SYNTACTIC AND SEMANTIC SPECIFICATION, PROJECT AND REALIZATION (2 HOURS OF THEORY, 2 HOURS OF LABORATORY); 9.LISTS: GENERAL ASPECTS, VARIANTS, AND ADT SPECIFICATION, DEFINITION OF THE DATA STRUCTURE AND ALTERNATIVE IMPLEMENTATIONS BASED ON ARRAYS AND POINTER STRUCTURES, SPECIFICATION AND IMPLEMENTATION OF OPERATORS (ITERATIVE AND RECURSIVE VERSIONS), ALGORITHMS ON LISTS AND APPLICATIONS (8 HOURS OF THEORY, 4 HOURS OF LABORATORY); 10.STACK AND QUEUE: SPECIFICATION OF THE ADTS, STACK AND QUEUE OPERATORS, ALTERNATIVE IMPLEMENTATIONS OF DATA STRUCTURES, STACK AND QUEUE APPLICATIONS (4 HOURS OF THEORY, 2 HOURS OF LABORATORY); 11.BINARY TREES AND TREES: GENERAL, SPECIFIC ASPECTS OF ADTS, DEFINITION OF DATA STRUCTURE AND BASE OPERATORS, VISITING ALGORITHMS AND OTHER TREE ALGORITHMS (ITERATIVE AND RECURSIVE VERSIONS), APPLICATIONS OF TREE AND BINARY TREES (4 HOURS OF THEORY, 2 HOURS OF LABORATORY); 12.SORTED SETS AND BINARY SEARCH TREE: SPECIFICATION AND IMPLEMENTATION OF THE ADT, CREATE, INSERT, DELETE, AND SEARCH OPERATORS, VISIT ALGORITHMS, BINARY SEARCH TREE BALANCING, BINARY SEARCH TREE APPLICATIONS (4 HOURS OF THEORY, 2 HOURS OF LABORATORY); 13.INTRODUCTION TO PRIORITY QUEUES AND HEAPS (2 HOURS OF THEORY); 14.HASH SETS AND HASH TABLES: GENERAL ASPECTS, SPECIFICATIONS AND ADT IMPLEMENTATION, HASH FUNCTIONS, CREATING, INSERTING, DELETING AND SEARCHING OPERATORS, COLLISION MANAGEMENT WITH LINKED LISTS AND OPEN ADDRESSING, HASH TABLE APPLICATIONS (2 HOURS OF THEORY, 1 HOUR OF LABORATORY).

Contents

1.ADVANCED PROGRAMMING IN C: SELF-REFERENTIAL STRUCTURES; DYNAMIC STRUCTURES (LISTS, TREES) - (3 HOURS OF THEORY, 1 HOUR OF LABORATORY);
2.GENERAL INFORMATION ABOUT MEMORY MODELS, STATIC AND DYNAMIC MEMORY, STACK AND ACTIVATION RECORDS, NAMES AND ENVIRONMENT, STATIC AND DYNAMIC SCOPE RULES (3 HOURS OF THEORY);
3.POINTERS AND DYNAMIC MEMORY ALLOCATION (2 HOURS OF THEORY, 2 HOURS OF LABORATORY);
4.ABSTRACTIONS AND MODULES: ABSTRACTION TYPES, INTERFACE AND IMPLEMENTATION OF A MODULE, REALIZATION OF MODULES IN C (3 HOURS OF THEORY, 2 HOURS OF LABORATORY);
5.RECURSION: GENERAL ASPECTS AND DEFINITIONS, RECURSION AND ITERATION, MANAGEMENT OF THE EXECUTION OF RECURSIVE PROGRAMS (3 HOURS OF THEORY, 2 HOURS OF LABORATORY);
6.ITERATIVE AND RECURSIVE ALGORITHMS ON ARRAYS, SORTING ALGORITHMS (6 HOURS OF THEORY, 3 HOURS OF LABORATORY);
7.CONSIDERATIONS ON COMPUTATIONAL COMPLEXITY (2 HOURS OF THEORY, 1 HOUR OF LABORATORY);
8.ABSTRACT DATA TYPES (ADTS): SYNTACTIC AND SEMANTIC SPECIFICATION, PROJECT AND REALIZATION (2 HOURS OF THEORY, 2 HOURS OF LABORATORY);
9.LISTS: GENERAL ASPECTS, VARIANTS, AND ADT SPECIFICATION, DEFINITION OF THE DATA STRUCTURE AND ALTERNATIVE IMPLEMENTATIONS BASED ON ARRAYS AND POINTER STRUCTURES, SPECIFICATION AND IMPLEMENTATION OF OPERATORS (ITERATIVE AND RECURSIVE VERSIONS), ALGORITHMS ON LISTS AND APPLICATIONS (8 HOURS OF THEORY, 4 HOURS OF LABORATORY);
10.STACK AND QUEUE: SPECIFICATION OF THE ADTS, STACK AND QUEUE OPERATORS, ALTERNATIVE IMPLEMENTATIONS OF DATA STRUCTURES, STACK AND QUEUE APPLICATIONS (4 HOURS OF THEORY, 2 HOURS OF LABORATORY);
11.BINARY TREES AND TREES: GENERAL, SPECIFIC ASPECTS OF ADTS, DEFINITION OF DATA STRUCTURE AND BASE OPERATORS, VISITING ALGORITHMS AND OTHER TREE ALGORITHMS (ITERATIVE AND RECURSIVE VERSIONS), APPLICATIONS OF TREE AND BINARY TREES (4 HOURS OF THEORY, 2 HOURS OF LABORATORY);
12.SORTED SETS AND BINARY SEARCH TREE: SPECIFICATION AND IMPLEMENTATION OF THE ADT, CREATE, INSERT, DELETE, AND SEARCH OPERATORS, VISIT ALGORITHMS, BINARY SEARCH TREE BALANCING, BINARY SEARCH TREE APPLICATIONS (4 HOURS OF THEORY, 2 HOURS OF LABORATORY);
13.INTRODUCTION TO PRIORITY QUEUES AND HEAPS (2 HOURS OF THEORY);
14.HASH SETS AND HASH TABLES: GENERAL ASPECTS, SPECIFICATIONS AND ADT IMPLEMENTATION, HASH FUNCTIONS, CREATING, INSERTING, DELETING AND SEARCHING OPERATORS, COLLISION MANAGEMENT WITH LINKED LISTS AND OPEN ADDRESSING, HASH TABLE APPLICATIONS (2 HOURS OF THEORY, 1 HOUR OF LABORATORY).

	Teaching Methods
	TEACHING INCLUDES BOTH FRONTAL LESSONS (6 CFU / 48 HOURS) AND LABORATORY LESSONS (3 CFU / 24 HOURS). THE LAB LESSONS WILL BE ENRICHED BY CASE STUDIES WITH PROGRAMS DEVELOPED IN CLASS WITH THE HELP OF THE TEACHER.

	Verification of learning
	THE ACHIEVEMENT OF THE COURSE OBJECTIVES IS CERTIFIED BY PASSING AN EVALUATION EXAM WITH SCORE IN THIRTIETHS. THE EXAM CONSISTS OF A PRACTICE OR WRITTEN TEST AND AN ORAL DISCUSSION. THE WRITTEN TEST OR LABORATORY PRACTICE IS PRELIMINARY TO THE ORAL TEST AND HAS A DURATION LESS THAN 120 MINUTES. THE TEST IS USED TO EVALUATE THE STUDENT'S ABILITY TO PRACTICE THE COURSE'S NOTIONS THROUGH THE RESOLUTION OF SPECIFIC EXERCISES, CONSISTING IN SPECIFYING AND IMPLEMENTING C-LANGUAGE PROGRAMS USING BASIC ALGORITHMS AND BASIC DATA STRUCTURES (STACK, QUEUES, LISTS, TREES, HASH TABLES). THE WRITTEN TEST OR LABORATORY PRACTICE IS PASSED IF A GRADE OF AT LEAST 18/30 IS OBTAINED, WHICH CORRESPONDS TO DEMONSTRATE THE ABILITY OF IDENTIFYING THE SUITABLE DATA STRUCTURES FOR THE RESOLUTION OF THE PROBLEM AND IMPLEMENTING THEM WITH THE C LANGUAGE. DURING THE COURSE, IT IS POSSIBLE TO CARRY OUT TWO PARTIAL TESTS, AFTER HALF OF THE LESSONS AND AT THE END OF THE SEMESTER, RESPECTIVELY. EACH TEST IS CARRIED OUT WITH THE SAME METHODS, OBJECTIVES AND EVALUATION OF THE PRACTICAL TEST. THE EVALUATION OF THE TWO TESTS WILL BE EXPRESSED IN THIRTIETHS AND THE FINAL SCORE WILL BE GIVEN BY THE WEIGHTED AVERAGE OF THE TWO TESTS. IF THE FINAL SCORE IS ABOVE 18/30 THE STUDENT CAN BE CONSIDERED EXEMPTED FROM THE WRITTEN/PRACTICAL TEST. THE EXEMPTION WILL BE VALID EXCLUSIVELY FOR THE EXAMINATION SESSION FOLLOWING THAT OF THE TEACHING. THE ORAL TEST CONSISTS OF AN INTERVIEW WITH QUESTIONS ON THE THEORETICAL AND METHODOLOGICAL CONTENTS OF THE TEACHING PROGRAM AIMING TO ASSESS THE LEVEL OF KNOWLEDGE AND UNDERSTANDING ACQUIRED BY THE STUDENT AS WELL AS TO VERIFY THE EXPOSURE CAPACITY. BOTH PRACTICE TEST AND ORAL TEST EQUALLY CONTRIBUTE TO THE FINAL SCORE.

Verification of learning

THE ACHIEVEMENT OF THE COURSE OBJECTIVES IS CERTIFIED BY PASSING AN EVALUATION EXAM WITH SCORE IN THIRTIETHS. THE EXAM CONSISTS OF A PRACTICE OR WRITTEN TEST AND AN ORAL DISCUSSION.
THE WRITTEN TEST OR LABORATORY PRACTICE IS PRELIMINARY TO THE ORAL TEST AND HAS A DURATION LESS THAN 120 MINUTES. THE TEST IS USED TO EVALUATE THE STUDENT'S ABILITY TO PRACTICE THE COURSE'S NOTIONS THROUGH THE RESOLUTION OF SPECIFIC EXERCISES, CONSISTING IN SPECIFYING AND IMPLEMENTING C-LANGUAGE PROGRAMS USING BASIC ALGORITHMS AND BASIC DATA STRUCTURES (STACK, QUEUES, LISTS, TREES, HASH TABLES).
THE WRITTEN TEST OR LABORATORY PRACTICE IS PASSED IF A GRADE OF AT LEAST 18/30 IS OBTAINED, WHICH CORRESPONDS TO DEMONSTRATE THE ABILITY OF IDENTIFYING THE SUITABLE DATA STRUCTURES FOR THE RESOLUTION OF THE PROBLEM AND IMPLEMENTING THEM WITH THE C LANGUAGE.
DURING THE COURSE, IT IS POSSIBLE TO CARRY OUT TWO PARTIAL TESTS, AFTER HALF OF THE LESSONS AND AT THE END OF THE SEMESTER, RESPECTIVELY. EACH TEST IS CARRIED OUT WITH THE SAME METHODS, OBJECTIVES AND EVALUATION OF THE PRACTICAL TEST. THE EVALUATION OF THE TWO TESTS WILL BE EXPRESSED IN THIRTIETHS AND THE FINAL SCORE WILL BE GIVEN BY THE WEIGHTED AVERAGE OF THE TWO TESTS. IF THE FINAL SCORE IS ABOVE 18/30 THE STUDENT CAN BE CONSIDERED EXEMPTED FROM THE WRITTEN/PRACTICAL TEST. THE EXEMPTION WILL BE VALID EXCLUSIVELY FOR THE EXAMINATION SESSION FOLLOWING THAT OF THE TEACHING.
THE ORAL TEST CONSISTS OF AN INTERVIEW WITH QUESTIONS ON THE THEORETICAL AND METHODOLOGICAL CONTENTS OF THE TEACHING PROGRAM AIMING TO ASSESS THE LEVEL OF KNOWLEDGE AND UNDERSTANDING ACQUIRED BY THE STUDENT AS WELL AS TO VERIFY THE EXPOSURE CAPACITY.
BOTH PRACTICE TEST AND ORAL TEST EQUALLY CONTRIBUTE TO THE FINAL SCORE.

	Texts
	LEARNING MATERIAL (HANDOUTS, SLIDES, EXERCISES) IS AVAILABLE ON-LINE TO THE STUDENTS. THE FOLLOWING BOOK IS NECESSARY FOR THE INDIVIDUAL STUDY. RECOMMENDED TEXTBOOKS: ROBERT SEDGEWICK, “ALGORITHM IN C” 3/ED, ADDISON - WESLEY

	More Information
	E-LEARNING PLATFORM: HTTP://ELEARNING.INFORMATICA.UNISA.IT/EL-PLATFORM/ CONTACTS: VITTORIO FUCCELLA VFUCCELLA@UNISA.IT MARCO ROMANO MARROMANO@UNISA.IT

BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2022-05-23]

Vittorio FUCCELLA | PROGRAMMING AND DATA STRUCTURES