ROGRAMMING AND DATA STRUCTURES

Computer science ROGRAMMING AND DATA STRUCTURES

0512100052
DIPARTIMENTO DI INFORMATICA
EQF6
COMPUTER SCIENCE
2017/2018

OBBLIGATORIO
YEAR OF COURSE 1
YEAR OF DIDACTIC SYSTEM 2017
SECONDO SEMESTRE
CFUHOURSACTIVITY
648LESSONS
324LAB


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.
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
LEARNING ASSESSMENT IS BASED ON AN EXAM WITH GRADES ON A SCALE OF 30. THE EXAM CONSISTS OF A WRITTEN OR LABORATORY PRACTICE TEST AND AN ORAL EXAMINATION.

THE WRITTEN OR LABORATORY PRACTICE TEST IS PRELIMINARY TO THE ORAL EXAMINATION AND HAS A DURATION OF AT LEAST 120 MINUTES. THE TEST AIMS AT VERIFYING THE CAPABILITY OF THE STUDENT TO CORRECTLY APPLY THE KNOWLEDGE GAINED DURING THE COURSE THROUGH THE RESOLUTION OF SPECIFIC EXERCISES, CONSISTING OF SPECIFYING AND IMPLEMENTING PROGRAMS USING ALGORITHMS AND DATA STRUCTURES (STACK, QUEUES, LISTS, TREES, HASH TABLES). THE WRITTEN OR LABORATORY PRACTICE TEST IS PASSED WITH A GRADE OF 18/30. STUDENTS PASSING TWO MIDTERM TESTS DURING THE CLASS ARE EXEMPTED BY THE WRITTEN OR LABORATORY PRACTICE TEST.

THE ORAL EXAMINATION IS BASED ON QUESTIONS AND DISCUSSION ON THE THEORETICAL AND METHODOLOGICAL TOPICS OF THE COURSE AND AIMS AT ASSESSING THE LEVEL OF KNOWLEDGE AND UNDERSTANDING ACHIEVED BY THE STUDENT AS WELL AS AT VERIFYING THE PRESENTATION CAPABILITY THROUGH THE USE OF THE CORRECT TERMINOLOGY AND THE AUTONOMOUS ORGANISATION OF THE PRESENTATION.
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: 2019-05-14]