Pasquale FOGGIA | Algorithms and Data Structures

cod. 0612700006

ALGORITHMS AND DATA STRUCTURES

	0612700006
	DIPARTIMENTO DI INGEGNERIA DELL'INFORMAZIONE ED ELETTRICA E MATEMATICA APPLICATA

	COMPUTER ENGINEERING
	2015/2016

PERCORSO COMUNE Cohort 2014/2015

	OBBLIGATORIO
	YEAR OF COURSE 2
	YEAR OF DIDACTIC SYSTEM 2012
	PRIMO SEMESTRE

TEACHING UNITS

	SSD	CFU	HOURS	ACTIVITY	TYPE OF ACTIVITY
	ING-INF/05	9	90	LESSONS	COMPULSORY SUBJECTS, CHARACTERISTIC OF THE CLASS

PROFESSORS

	PASQUALE FOGGIA T Curriculum
	DIODATO FERRAIOLI Curriculum

	Objectives
	LEARNING RESULTS AND KNOWLEDGE TO BE ACQUIRED THE COURSE HAS THE GOAL TO PRESENT IN DETAIL THE ISSUES OF DESIGN AND IMPLEMENTATION OF ALGORITHMS, USING BOTH ITERATIVE AND RECURSIVE TECHNIQUES, AND EVALUATING THE EFFICIENCY OF THE OBTAINED PROGRAMS; THE COURSE ALSO PRESENTS THE FUNDAMENTAL DATA STRUCTURES SUCH AS STACKS, QUEUES, LISTS, TREES AND HASHTABLES, SHOWING THEIR IMPLEMENTATION IN THE C LANGUAGE. KNOWLEDGE AND UNDERSTANDING KNOWLEDGE OF THE FUNDAMENTAL ALGORITHMS AND DATA STRUCTURES. KNOWLEDGE OF THE ITERATIVE AND RECURSIVE PROGRAMMING PARADIGMS. COMPARISON OF ALGORITHMS WITH RESPECT TO THEIR MEMORY AND EXECUTION TIME. APPLIED KNOWLEDGE AND UNDERSTANDING ANALYSIS OF TYPICAL PROBLEMS AND IMPLEMENTATION OF APPLICATIONS USING STANDARD ALGORITHMS AND DATA STRUCTURES IN THE C LANGUAGE, WITH AN EVALUATION OF THEIR EFFICIENCY. IMPLEMENTATION OF SMALL-SCALE SOFTWARE PROJECTS USING BOTH INTEGRATED ENVIRONMENTS AND SEPARATE COMPILATION. JUDGEMENT AUTONOMY SELECTION OF THE ALGORITHMS AND DATA STRUCTURES APPROPRIATE FOR SUPPORTING AN APPLICATION ON THE BASIS OF ITS REQUIREMENTS. COMMUNICATION SKILLS DOCUMENTATION AND COMMUNICATION OF THE DESIGN CHOICES REGARDING ALGORITHMS AND DATA STRUCTURES, BOTH IN WRITTEN AND VERBAL FORM. ABILITY TO WORK IN SMALL GROUPS.

LEARNING RESULTS AND KNOWLEDGE TO BE ACQUIRED
THE COURSE HAS THE GOAL TO PRESENT IN DETAIL THE ISSUES OF DESIGN AND IMPLEMENTATION OF ALGORITHMS, USING BOTH ITERATIVE AND RECURSIVE TECHNIQUES, AND EVALUATING THE EFFICIENCY OF THE OBTAINED PROGRAMS; THE COURSE ALSO PRESENTS THE FUNDAMENTAL DATA STRUCTURES SUCH AS STACKS, QUEUES, LISTS, TREES AND HASHTABLES, SHOWING THEIR IMPLEMENTATION IN THE C LANGUAGE.

KNOWLEDGE AND UNDERSTANDING
KNOWLEDGE OF THE FUNDAMENTAL ALGORITHMS AND DATA STRUCTURES. KNOWLEDGE OF THE ITERATIVE AND RECURSIVE PROGRAMMING PARADIGMS. COMPARISON OF ALGORITHMS WITH RESPECT TO THEIR MEMORY AND EXECUTION TIME.

APPLIED KNOWLEDGE AND UNDERSTANDING
ANALYSIS OF TYPICAL PROBLEMS AND IMPLEMENTATION OF APPLICATIONS USING STANDARD ALGORITHMS AND DATA STRUCTURES IN THE C LANGUAGE, WITH AN EVALUATION OF THEIR EFFICIENCY. IMPLEMENTATION OF SMALL-SCALE SOFTWARE PROJECTS USING BOTH INTEGRATED ENVIRONMENTS AND SEPARATE COMPILATION.

JUDGEMENT AUTONOMY
SELECTION OF THE ALGORITHMS AND DATA STRUCTURES APPROPRIATE FOR SUPPORTING AN APPLICATION ON THE BASIS OF ITS REQUIREMENTS.

COMMUNICATION SKILLS
DOCUMENTATION AND COMMUNICATION OF THE DESIGN CHOICES REGARDING ALGORITHMS AND DATA STRUCTURES, BOTH IN WRITTEN AND VERBAL FORM. ABILITY TO WORK IN SMALL GROUPS.

	Prerequisites
	THE COURSE REQUIRES PREVIOUS KNOWLEDGE ABOUT THE C PROGRAMMING LANGUAGE.

	Contents
	COMPLEMENTS OF C LANGUAGE: POINTERS, ARRAYS AND POINTER ARITHMETIC. STRUCTURES. RECURSION: GENERAL DEFINITIONS. MATHEMATICAL INDUCTION. DIVIDE ET IMPERA. NOTEWORTHY RECURSIVE ALGORITHMS: HANOI TOWER, QUICKSORT, MERGESORT. COMPUTATIONAL COMPLEXITY: DEFINITIONS; THE RAM MODEL; NOTATIONS (BIG O, OMEGA, THETA); COMPLEXITY EVALUATION; RECURENCE RELATIONS, NOTABLE CASES AND THEIR SOLUTIONS; AMORTIZED ANALYSIS. DYNAMIC LISTS: GENERAL ASPECTS, DATA STRUCTURE, BASIC ALGORITHMS (BOTH ITERATIVE AND RECURSIVE): CREATION, INSERTION, SEARCH, DELETION, VISIT, OTHER ALGORITHMS. BINARY TREES: GENERAL ASPECTS, DATA STRUCTURE, BASIC ALGORITHMS (BOTH ITERATIVE AND RECURSIVE): CREATION, INSERTION, SEARCH, DELETION, VISIT, OTHER ALGORITHMS. HASHTABLES: GENERAL ASPECTS, DATA STRUCTURE, BASIC ALGORITHMS (BOTH ITERATIVE AND RECURSIVE): CREATION, INSERTION, SEARCH, DELETION, VISIT, OTHER ALGORITHMS. CASE TOOLS: INTEGRATED DEVELOPMENT ENVIRONMENT; DEBUGGING AND TESTING; SEPARATE COMPILATION; LIBRARIES; MAKEFILES. RUN-TIME SUPPORT: GENERAL ASPECTS ON MEMORY ALLOCATION; STATIC AND DYNAMIC ALLOCATION, PROGRAM STACK AND ACTIVATION RECORDS; NAMES AND ENVIRONMENTS, STATIC AND DYNAMIC SCOPING.

Contents

COMPLEMENTS OF C LANGUAGE: POINTERS, ARRAYS AND POINTER ARITHMETIC. STRUCTURES.

RECURSION: GENERAL DEFINITIONS. MATHEMATICAL INDUCTION. DIVIDE ET IMPERA. NOTEWORTHY RECURSIVE ALGORITHMS: HANOI TOWER, QUICKSORT, MERGESORT.

COMPUTATIONAL COMPLEXITY: DEFINITIONS; THE RAM MODEL; NOTATIONS (BIG O, OMEGA, THETA); COMPLEXITY EVALUATION; RECURENCE RELATIONS, NOTABLE CASES AND THEIR SOLUTIONS; AMORTIZED ANALYSIS.

DYNAMIC LISTS: GENERAL ASPECTS, DATA STRUCTURE, BASIC ALGORITHMS (BOTH ITERATIVE AND RECURSIVE): CREATION,
INSERTION, SEARCH, DELETION, VISIT, OTHER ALGORITHMS.

BINARY TREES: GENERAL ASPECTS, DATA STRUCTURE, BASIC ALGORITHMS (BOTH ITERATIVE AND RECURSIVE): CREATION,
INSERTION, SEARCH, DELETION, VISIT, OTHER ALGORITHMS.

HASHTABLES: GENERAL ASPECTS, DATA STRUCTURE, BASIC ALGORITHMS (BOTH ITERATIVE AND RECURSIVE): CREATION,
INSERTION, SEARCH, DELETION, VISIT, OTHER ALGORITHMS.

CASE TOOLS: INTEGRATED DEVELOPMENT ENVIRONMENT; DEBUGGING AND TESTING; SEPARATE COMPILATION; LIBRARIES; MAKEFILES.

RUN-TIME SUPPORT: GENERAL ASPECTS ON MEMORY ALLOCATION; STATIC AND DYNAMIC ALLOCATION, PROGRAM STACK AND ACTIVATION RECORDS; NAMES AND ENVIRONMENTS, STATIC AND DYNAMIC SCOPING.

	Teaching Methods
	THE COURSE INCLUDES THEORY LESSONS, EXERCISES AND LABORATORY ACTIVITIES. IN THE EXERCISES, THE TEACHER WILL PROPOSE AND DESCRIBE ALGORITHMIC PROBLEMS AND THEIR SOLUTION USING THE C LANGUAGE. IN THE LABORATORY ACTIVITIES, THE STUDENTS WILL DEVELOP THE SOLUTION TO A PROBLEM SPECIFIED BY THE TEACHER. THE LABORATORY ACTIVITIES ALSO INCLUDE THE REALIZATION OF GROUP PROJECTS MADE BY 3-4 STUDENTS TEAMS. DURING THE COURSE, THE STUDENTS WILL UNDERGO TWO PRACTICAL TESTS SUBJECT TO EVALUATION BY THE TEACHER; THE TESTS WILL RECEIVE A SCORE AND A LIST OF INDICATIONS ABOUT THE ERRORS MADE BY THE STUDENT. THE TESTS WILL BE CONSIDERED AS PASSED IF BOTH OF THEM REACH A SUFFICIENT SCORE.

Teaching Methods

THE COURSE INCLUDES THEORY LESSONS, EXERCISES AND LABORATORY ACTIVITIES. IN THE EXERCISES, THE TEACHER WILL PROPOSE AND DESCRIBE ALGORITHMIC PROBLEMS AND THEIR SOLUTION USING THE C LANGUAGE. IN THE LABORATORY ACTIVITIES, THE STUDENTS WILL DEVELOP THE SOLUTION TO A PROBLEM SPECIFIED BY THE TEACHER. THE LABORATORY ACTIVITIES ALSO INCLUDE THE REALIZATION OF GROUP PROJECTS MADE BY 3-4 STUDENTS TEAMS.
DURING THE COURSE, THE STUDENTS WILL UNDERGO TWO PRACTICAL TESTS SUBJECT TO EVALUATION BY THE TEACHER; THE TESTS WILL RECEIVE A SCORE AND A LIST OF INDICATIONS ABOUT THE ERRORS MADE BY THE STUDENT. THE TESTS WILL BE CONSIDERED AS PASSED IF BOTH OF THEM REACH A SUFFICIENT SCORE.

	Verification of learning
	THE EXAM AIMS AT EVALUATING: THE KNOWLEDGE AND UNDERSTANDING OF THE CONCEPTS PRESENTED IN THE COURSE; THE ABILITY TO APPLY THIS KNOWLEDGE FOR SOLVING PROBLEMS INVOLVING FUNDAMENTAL ALGORITHMS AND DATA STRUCTURES, EVALUATING THEIR EFFICIENCY; THE JUDGEMENT AUTONOMY; THE COMMINICATION SKILLS; THE LEARNING ABILITY. THE EXAM CONSISTS OF A PRACTICAL TEST AND AN ORAL DISCUSSION. THE PRACTICAL TEST IS MADE USING A COMPUTER. IN ORDER TO PASS THE TEST, THE STUDENT MUST SHOW THE ABILITY TO SOLVE AN ASSIGNED PROBLEM WITHOUT SIGNIFICANT ERRORS. ONLY STUDENTS PASSING THE PRACTICAL TEST ARE ADMITTED TO THE ORAL DISCUSSION. THE ORAL DISCUSSION WILL INVOLVE ALL THE ARGUMENTS PRESENTED IN THE COURSE, AND WILL EVALUATE THE KNOWLEDGE OF THE STUDENT AND THE COMMUNICATION SKILLS. THE FINAL SCORING WILL BE ASSIGNED BY WEIGHTING 60% THE PRACTICAL TEST AND 40% THE ORAL DISCUSSION. THE "CUM LAUDE" SCORE CAN BE ASSIGNED TO STUDENTS THAT DEMONSTRATE AN EXCELLENT ABILITY TO ANALYZE AND DESIGN THE ALGORITHMS AND DATA STRUCTURES.

Verification of learning

THE EXAM AIMS AT EVALUATING: THE KNOWLEDGE AND UNDERSTANDING OF THE CONCEPTS PRESENTED IN THE COURSE; THE ABILITY TO APPLY THIS KNOWLEDGE FOR SOLVING PROBLEMS INVOLVING FUNDAMENTAL ALGORITHMS AND DATA STRUCTURES, EVALUATING THEIR EFFICIENCY; THE JUDGEMENT AUTONOMY; THE COMMINICATION SKILLS; THE LEARNING ABILITY.
THE EXAM CONSISTS OF A PRACTICAL TEST AND AN ORAL DISCUSSION. THE PRACTICAL TEST IS MADE USING A COMPUTER. IN ORDER TO PASS THE TEST, THE STUDENT MUST SHOW THE ABILITY TO SOLVE AN ASSIGNED PROBLEM WITHOUT SIGNIFICANT ERRORS. ONLY STUDENTS PASSING THE PRACTICAL TEST ARE ADMITTED TO THE ORAL DISCUSSION.
THE ORAL DISCUSSION WILL INVOLVE ALL THE ARGUMENTS PRESENTED IN THE COURSE, AND WILL EVALUATE THE KNOWLEDGE OF THE STUDENT AND THE COMMUNICATION SKILLS.
THE FINAL SCORING WILL BE ASSIGNED BY WEIGHTING 60% THE PRACTICAL TEST AND 40% THE ORAL DISCUSSION. THE "CUM LAUDE" SCORE CAN BE ASSIGNED TO STUDENTS THAT DEMONSTRATE AN EXCELLENT ABILITY TO ANALYZE AND DESIGN THE ALGORITHMS AND DATA STRUCTURES.

	Texts
	M. VENTO, P. FOGGIA, “ALGORITMI E STRUTTURE DATI”, MCGRAW-HILL. LECTURE NOTES, EXAMPLES AND EXERCISES ARE AVAILABLE ON LINE. ADDITIONAL BOOKS: T.H. CORMEN, C.E. LEISERSON, R.R. RIVEST, C. STEIN, “INTRODUZIONE AGLI ALGORITMI E STRUTTURE DATI 2/ED”, MCGRAW-HILL.

	More Information
	THE COURSE WILL BE HELD IN ITALIAN.

BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2016-09-30]

Pasquale FOGGIA | Algorithms and Data Structures