ADVANCED ALGORITHMS AND DATA STRUCTURES

Diodato FERRAIOLI ADVANCED ALGORITHMS AND DATA STRUCTURES

0622900021
DIPARTIMENTO DI INGEGNERIA DELL'INFORMAZIONE ED ELETTRICA E MATEMATICA APPLICATA
EQF7
DIGITAL HEALTH AND BIOINFORMATIC ENGINEERING
2019/2020

OBBLIGATORIO
YEAR OF COURSE 1
YEAR OF DIDACTIC SYSTEM 2018
PRIMO SEMESTRE
CFUHOURSACTIVITY
540LESSONS
432EXERCISES
Objectives
LEARNING OBJECTIVES
THE COURSE PROVIDES METHODOLOGIES AND TOOLS FOR ANALYZING A PROBLEM, DESIGNING AN EFFICIENT SOLUTION. EVENTUALLY USING ADVANCED PROGRAMMING TECHNIQUES AND DATA STRUCTURES, AND IMPLEMENTING IT IN AN OBJECT-ORIENTED PROGRAMMING LANGUAGE.

STUDENTS WILL LEARN ADVANCED PROGRAMMING TECHNIQUES AND DATA STRUCTURES. THEY WILL LEARN THE IMPLEMENTATION OF THE MOST RELEVANT DATA STRUCTURES INCLUDED IN STANDARD LIBRARIES. THEY WILL LEARN TO UNDERSTAND TERMINOLOGY USED IN THE CONTEXT OF ALGORITHM DESIGN.

STUDENTS WILL LEARN TO USE PROPOSED PROGRAMMING TECHNIQUES AND ADVANCED DATA STRUCTURES TO SOLVE COMPLEX PROBLEMS. THEY WILL BE ABLE TO IMPLEMENT ALGORITHMS AND DATA STRUCTURES IN AN OBJECT-ORIENTED PROGRAMMING LANGUAGE USING THE FRAMEWORK OF PATTERN DESIGN.
Prerequisites
KNOWLEDGE OF BASIC DATA STRUCTURES AND FUNDAMENTALS OF PROGRAMMING AND ALGORITHM ANALYSIS IS REQUIRED FOR THE SUCCESSFUL ACHIEVEMENT OF COURSE OBJECTIVES.
FLUENCY IN OBJECT-ORIENTED PROGRAMMING IS RECOMMENDED.
Contents
PYTHON LANGUAGE
- DATA TYPES AND FUNCTIONS (2 LECTURE HOURS AND 4 PRACTICE HOURS)
- CLASSES, MODULES AND LIBRERIES (2 LECTURE HOURS AND 2 PRACTICE HOURS)

ADVANCED DATA STRUCTURES
- ABSTRACT DATA TYPES AND ELEMENTARY DATA STRUCTURES (2 LECTURE HOURS AND 2 PRACTICE HOURS)
- BINARY SEARCH TREE (2 LECTURE HOURS AND 2 PRACTICE HOURS)
- BALANCED BINARY SEARCH TREES (4 LECTURE HOURS AND 4 PRACTICE HOURS)
- PRIORITY QUEUES (2 LECTURE HOURS AND 2 PRACTICE HOURS)
- MAPS AND HASH TABLES (2 LECTURE HOURS AND 2 PRACTICE HOURS)
- B-TREES (2 LECTURE HOURS AND 1 PRACTICE HOURS)
- GRAPHS (8 LECTURE HOURS AND 6 PRACTICE HOURS)

PROGRAMMING TECHNIQUES
- GREEDY PROGRAMMING (4 LECTURE HOURS AND 4 PRACTICE HOURS)
- EXHAUSTIVE SEARCH AND DYNAMIC PROGRAMMING (6 LECTURE HOURS AND 4 PRACTICE HOURS)
- APPROXIMATION ALGORITHMS (2 LECTURE HOURS)
- GENETIC ALGORITHMS (2 LECTURE HOURS AND 1 PRACTICE HOURS)
Teaching Methods
THE COURSE CONSISTS IN LECTURES, GUIDED EXERCISES AND LABS.
DURING THE LECTURES ALGORITHMS AND DATA STRUCTURES ARE PRESENTED AND THEIR APPLICATIONS TO REAL-LIFE PROBLEMS ARE DISCUSSED.
IN THE LABS STUDENTS ARE REQUIRED TO IMPLEMENT DATA STRUCTURES AND ALGORITHMS PRESENTED IN THE LECTURES.
IN THE GUIDED EXERCISES STUDENTS ARE DIVIDED IN GROUPS AND EACH GROUP IS ASSIGNED PROJECT-WORKS TO DEVELOP DURING THE WHOLE COURSE. THE PROJECT INCLUDES ALL THE MATERIAL OF THE COURSE AND IT IS FINALIZED TO THE ACQUISITION OF THE CAPACITY TO SOLVE A PROGRAMMING PROBLEM, DESIGNING AND IMPLEMENTING A PROGRAM USING ADVANCED DATA STRUCTURES AND PROGRAMMING TECHNIQUES. THE PROJECT-WORK IS ALSO USED TO DEVELOP THE ABILITY OF WORKING IN A TEAM.
Verification of learning
THE FINAL EXAM IS DESIGNED TO EVALUATE AS A WHOLE THE KNOWLEDGE AND UNDERSTANDING OF THE CONCEPTS PRESENTED IN THE COURSE, AND THE ABILITY TO APPLY SUCH KNOWLEDGE IN DESIGNING ALGORITHMS AND IMPLEMENTING THEM IN AN OBJECT-ORIENTED PROGRAMMING LANGUAGE TO SOLVE NON TRIVIAL COMBINATORIAL PROBLEMS.

THE EXAM CONSISTS OF THE DISCUSSION OF THE PROJECT REALIZED DURING THE COURSE, WHOSE AIM IS TO ASSESS THE ABILITY OF APPLYING KNOWLEDGE OF THE DATA STRUCTURES AND PROGRAMMING TECHNIQUES PROPOSED IN CLASS AND REALIZE EFFICIENT IMPLEMENTATIONS, AND A WRITTEN TEST, CONSISTING OF THREE EXERCISES, WHOSE AIM IS TO ASSESS THE ACQUIRED KNOWLEDGE ON ADVANCED DATA STRUCTURES AND PROGRAMMING TECHNIQUES AND ABILITY TO UNDERSTANDING.

IN THE FINAL EVALUATION, EXPRESSED IN THIRTIES, THE EVALUATION OF THE PROJECT WILL ACCOUNTS FOR 60% WHILE THE TEST ACCOUNTS FOR THE REMAINING 40%. THE CUM LAUDE MAY BE GIVEN TO STUDENTS WHO DEMONSTRATE THAT THEY CAN APPLY THE KNOWLEDGE AUTONOMOUSLY EVEN IN CONTEXTS OTHER THAN THOSE PROPOSED IN THE COURSE.
Texts
M.T. GOODRICH, M. TAMASSIA, M.H. GOLDWASSER, “DATA STRUCTURES & ALGORITHMS IN PYTHON”,
WILEY 2013

OTHE MATERIAL WILL BE MADE AVAILABLE ON THE COMPANION WEB SITE.

LETTURE CONSIGLIATE:
KLEINBERG, TARDOS, "ALGORITHM DESIGN", PRENCTICE HALL, 2005.
T.H. CORMEN, C.E. LEISERSON, R.L. RIVEST, C. STEIN, “INTRODUZIONE AGLI ALGORITMI E STRUTTURE DATI”, SECONDA EDIZIONE, MCGRAW-HILL, 2005.
M. VENTO, P. FOGGIA, “ALGORITMI E STRUTTURE DATI”, MCGRAW-HILL.
P. MORIN, ”OPEN DATA STRUCTURES", (HTTP://WWW.OPENDATASTRCTURES.ORG).
C. DEMETRESCU, I. FINOCCHI, G. ITALIANO, “ALGORITMI E STRUTTURE DATI”, MCGRAW HILL, 2008.
More Information
THE COURSE LANGUAGE IS ENGLISH

THE COURSE HAS A COMPANION WEB SITE PUBLISHED IN THE DIEM E-LEARNING PLATFORM (HTTP://ELEARNING.DIEM.UNISA.IT - CLASS DI RETI DI CALCOLATORI OF THE CDS IN INGEGNERIA INFORMATICA) THAT CAN BE ACCESSED BY ALL THE ENGINEERING STUDENTS FROM UNISA. ON THE SITE YOU CAN FIND ANNOUNCEMENTS, NEWS, A FORUM FOR DISCUSSIONS RELATED TO THE COURSE, DIDACTIC MATERIAL, SLIDES, EXERCISES AND EXAMS, LECTURE PLAN AND A SURVEY OF THE ARGUMENTS OF EACH LECTURE. TO ACCESS THE SITE YOU NEED TO REGISTER.
  BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2021-02-19]