Fabio Narducci | ROGRAMMING AND DATA STRUCTURES

cod. 0512100052

ROGRAMMING AND DATA STRUCTURES

	0512100052
	DIPARTIMENTO DI INFORMATICA
	EQF6
	COMPUTER SCIENCE
	2019/2020

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

	MAURIZIO TUCCI T Curriculum
	FABIO NARDUCCI 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) (3H LESSON, 1H LAB); 2. GENERAL INFORMATION ABOUT MEMORY MODELS, STATIC AND DYNAMIC MEMORY, STACK AND ACTIVATION RECORDS, NAMES AND ENVIRONMENT, STATIC AND DYNAMIC SCOPE RULES (3H LESSON); 3. POINTERS AND DYNAMIC MEMORY ALLOCATION (2H LESSON, 2H LAB); 4. ABSTRACTIONS AND MODULES: ABSTRACTION TYPES, INTERFACE AND IMPLEMENTATION OF A MODULE, REALIZATION OF MODULES IN C (3H LESSON, 2H LAB); 5. RECURSION: GENERAL ASPECTS AND DEFINITIONS, RECURSION AND ITERATION, MANAGEMENT OF THE EXECUTION OF RECURSIVE PROGRAMS (3H LESSON, 2H LAB); 6. ITERATIVE AND RECURSIVE ALGORITHMS ON ARRAYS, SORTING ALGORITHMS (6H LESSON, 3H LAB); 7. CONSIDERATIONS ON COMPUTATIONAL COMPLEXITY (2H LESSON, 1H LAB); 8. ABSTRACT DATA TYPES (ADTS): SYNTACTIC AND SEMANTIC SPECIFICATION, DESIGN, AND IMPLEMENTATION (2H LESSON, 2H LAB); 9. LISTS: GENERAL ASPECTS, VARIANTS, AND ADT SPECIFIC, 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 (8H LESSON, 4H LAB); 10. STACK AND QUEUE: SPECIFICATION OF THE ADTS, STACK AND QUEUE OPERATORS, ALTERNATIVE IMPLEMENTATIONS OF DATA STRUCTURES, STACK AND QUEUE APPLICATIONS (4H LESSON, 2H LAB); 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 (4H LESSON, 2H LAB); 12. ORDERED 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 (4H LESSON, 2H LAB); 13. INTRODUCTION TO PRIORITY QUEUES AND HEAPS (2H LESSON); 14. SETS, TABLES, AND HASH TABLES: GENERAL ASPECTS, ADT SPECIFICATIONS AND IMPLEMENTATION, HASH FUNCTIONS, CREATING, INSERTING, DELETING AND SEARCHING OPERATORS, COLLISION MANAGEMENT WITH LINKED LISTS AND OPEN ADDRESSING, HASH TABLE APPLICATIONS (2H LESSON, 1H LAB).

Contents

1. ADVANCED PROGRAMMING IN C: SELF-REFERENTIAL STRUCTURES; DYNAMIC STRUCTURES (LISTS, TREES) (3H LESSON, 1H LAB);
2. GENERAL INFORMATION ABOUT MEMORY MODELS, STATIC AND DYNAMIC MEMORY, STACK AND ACTIVATION RECORDS, NAMES AND ENVIRONMENT, STATIC AND DYNAMIC SCOPE RULES (3H LESSON);
3. POINTERS AND DYNAMIC MEMORY ALLOCATION (2H LESSON, 2H LAB);
4. ABSTRACTIONS AND MODULES: ABSTRACTION TYPES, INTERFACE AND IMPLEMENTATION OF A MODULE, REALIZATION OF MODULES IN C (3H LESSON, 2H LAB);
5. RECURSION: GENERAL ASPECTS AND DEFINITIONS, RECURSION AND ITERATION, MANAGEMENT OF THE EXECUTION OF RECURSIVE PROGRAMS (3H LESSON, 2H LAB);
6. ITERATIVE AND RECURSIVE ALGORITHMS ON ARRAYS, SORTING ALGORITHMS (6H LESSON, 3H LAB);
7. CONSIDERATIONS ON COMPUTATIONAL COMPLEXITY (2H LESSON, 1H LAB);
8. ABSTRACT DATA TYPES (ADTS): SYNTACTIC AND SEMANTIC SPECIFICATION, DESIGN, AND IMPLEMENTATION (2H LESSON, 2H LAB);
9. LISTS: GENERAL ASPECTS, VARIANTS, AND ADT SPECIFIC, 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 (8H LESSON, 4H LAB);
10. STACK AND QUEUE: SPECIFICATION OF THE ADTS, STACK AND QUEUE OPERATORS, ALTERNATIVE IMPLEMENTATIONS OF DATA STRUCTURES, STACK AND QUEUE APPLICATIONS (4H LESSON, 2H LAB);
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 (4H LESSON, 2H LAB);
12. ORDERED 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 (4H LESSON, 2H LAB);
13. INTRODUCTION TO PRIORITY QUEUES AND HEAPS (2H LESSON);
14. SETS, TABLES, AND HASH TABLES: GENERAL ASPECTS, ADT SPECIFICATIONS AND IMPLEMENTATION, HASH FUNCTIONS, CREATING, INSERTING, DELETING AND SEARCHING OPERATORS, COLLISION MANAGEMENT WITH LINKED LISTS AND OPEN ADDRESSING, HASH TABLE APPLICATIONS (2H LESSON, 1H LAB).

	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 THE RANGE [0..30]. 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 OF 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 THE RANGE [0..30]. 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 OF 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. RECOMMENDED TEXTBOOK: ROBERT SEDGEWICK, “ALGORITHM IN C” 3/ED, ADDISON - WESLEY

	More Information
	E-LEARNING PLATFORM: HTTP://ELEARNING.INFORMATICA.UNISA.IT/EL-PLATFORM/ CONTACTS: MAUTUC@UNISA.IT

BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2021-02-19]

Fabio Narducci | ROGRAMMING AND DATA STRUCTURES