2. Professors
  3. Teaching

PROGRAMMING AND DATA STRUCTURES

Gemma Catolino PROGRAMMING AND DATA STRUCTURES

0512100052
COMPUTER SCIENCE
EQF6
COMPUTER SCIENCE
2024/2025

OBBLIGATORIO
YEAR OF COURSE 1
YEAR OF DIDACTIC SYSTEM 2017
SPRING SEMESTER
CFUHOURSACTIVITY
648LESSONS
324LAB


GEMMA CATOLINO T Curriculum
CARMEN BISOGNI Curriculum
Objectives
THE MAIN OBJECTIVES OF THE COURSE ARE:
1. IN-DEPTH KNOWLEDGE OF FUNDAMENTAL CONCEPTS REGARDING DATA STRUCTURES: STUDENTS WILL BE ABLE TO UNDERSTAND AND ANALYZE DATA STRUCTURES IN TERMS OF BOTH SYNTACTIC AND SEMANTIC SPECIFICATION AND DESIGN AND IMPLEMENTATION, TO EVALUATE THEIR PERFORMANCE IN TERMS OF TIME AND SPACE, AS WELL AS TO UNDERSTAND THE DIFFERENCES AMONG THOSE STRUCTURES AND TO CHOOSE THE MOST SUITABLE ONE TO SOLVE A GIVEN PROBLEM. FUNDAMENTAL DATA STRUCTURES SUCH AS LISTS, STACKS, QUEUES, TREES AND GRAPHS WILL BE COVERED.
2. KNOWLEDGE OF FUNDAMENTAL ALGORITHMS: DURING THE COURSE, STUDENTS WILL BE EXPOSED TO A WIDE RANGE OF ALGORITHMS, INCLUDING SORTING ALGORITHMS, SEARCH ALGORITHMS AND ALGORITHMS FOR THE REALIZATION OF THE MAIN OPERATORS OF THE DATA STRUCTURES MENTIONED IN THE PREVIOUS POINT. STUDENTS WILL BE ABLE TO APPLY THIS KNOWLEDGE TO SOLVE A VARIETY OF COMPUTATIONAL PROBLEMS.
3. KNOWLEDGE OF ITERATIVE AND RECURSIVE PROGRAMMING TECHNIQUES: STUDENTS WILL LEARN ITERATIVE AND RECURSIVE PROGRAMMING TECHNIQUES AND WILL BE ABLE TO APPLY THEM TO SOLVE COMPLEX PROBLEMS.

KNOWLEDGE AND UNDERSTANDING
1.STUDENTS WILL BE ABLE TO UNDERSTAND THE FUNDAMENTAL PRINCIPLES OF DATA STRUCTURES.
2.STUDENTS WILL BE ABLE TO IDENTIFY PRACTICAL APPLICATIONS OF DATA STRUCTURES IN DIFFERENT COMPUTING CONTEXTS.
3.STUDENTS WILL BE ABLE TO ANALYZE THE EFFICIENCY OF DATA STRUCTURES IN TERMS OF TEMPORAL AND SPATIAL COMPLEXITY.
4.STUDENTS WILL BE ABLE TO DISTINGUISH AMONG DIFFERENT TYPES OF DATA STRUCTURES AND THEIR SPECIFIC USES.

APPLYING KNOWLEDGDE AND UNDERSTANDING
1.STUDENTS WILL BE ABLE TO IMPLEMENT FUNDAMENTAL DATA STRUCTURES USING THE C LANGUAGE.
2.STUDENTS WILL BE ABLE TO SOLVE COMPUTATIONAL PROBLEMS BY APPLYING ITERATIVE AND RECURSIVE PROGRAMMING TECHNIQUES.
3.STUDENTS WILL BE ABLE TO DEVELOP AND USE APPROPRIATE DATA STRUCTURES TO OPTIMIZE SOFTWARE SOLUTIONS.
4.STUDENTS WILL BE ABLE TO DESIGN CUSTOMIZED SOLUTIONS TO MEET SPECIFIC SOFTWARE PROJECT REQUIREMENTS.

MAKING JUDGEMENTS
1.STUDENTS WILL BE ABLE TO CRITICALLY EVALUATE THE CHOICE OF DATA STRUCTURES FOR SPECIFIC PERFORMANCE NEEDS.
2.STUDENTS WILL BE ABLE TO CHOOSE BETWEEN STATIC AND DYNAMIC IMPLEMENTATIONS OF DATA STRUCTURES BASED ON THE CONTEXT OF USE.
3.STUDENTS WILL BE ABLE TO ANALYZE AND MODIFY EXISTING DATA STRUCTURES TO IMPROVE THEIR EFFICIENCY.

COMMUNICATION SKILLS
1.STUDENTS WILL BE ABLE TO CLEARLY AND CONCISELY EXPLAIN THE FUNCTIONALITY AND IMPLEMENTATION CHOICES OF DATA STRUCTURES USED IN VARIOUS PROGRAMMING PROJECTS.
2.STUDENTS WILL BE ABLE TO ADEQUATELY DOCUMENT CODE AND PROGRAMMING SOLUTIONS.
3.STUDENTS WILL BE ABLE TO PRESENT THE RESULTS OF PROGRAMMING PROJECTS, ILLUSTRATING THE TECHNICAL DECISIONS MADE AND DISCUSSING THE IMPLICATIONS OF DATA STRUCTURE CHOICES.

LEARNING SKILLS
1.STUDENTS WILL BE ABLE TO INDEPENDENTLY DEEPEN THEIR UNDERSTANDING OF DATA STRUCTURES AND PROGRAMMING TECHNIQUES THROUGH SELF-STUDY AND RESEARCH.
2.STUDENTS WILL BE ABLE TO ADAPT TO TECHNOLOGICAL EVOLUTIONS IN THE FIELD OF DATA STRUCTURES AND PROGRAMMING METHODOLOGIES.
3.STUDENTS WILL BE ABLE TO CRITICALLY ANALYZE AND REFLECT ON THE EFFECTIVENESS OF IMPLEMENTED PROGRAMMING SOLUTIONS, IDENTIFYING POTENTIAL IMPROVEMENTS.
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).
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 AN OPTIONAL PRELIMINARY TEST, A PRACTICE OR WRITTEN TEST AND AN ORAL DISCUSSION. THE OPTIONAL PRELIMINARY TEST LASTS ABOUT 15 MINUTES AND SERVES TO EVALUATE THE MINIMUM KNOWLEDGE REQUIREMENTS TO BE ABLE TO FACE THE TEST WRITTEN OR PRACTICAL.
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” 4/ED, ADDISON - WESLEY
More Information
REGULARLY WORKING ON THE EXERCISES SUGGESTED BY THE TEACHER IS THE MOST EFFECTIVE WAY FOR THE STUDENT TO PREPARE FOR THE EXAM.

CONTACTS: Gemma Catolino gcatolino@unisa.it
  BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2024-10-07]