DESIGN AND ANALYSIS OF ALGORITHMS

International Teaching DESIGN AND ANALYSIS OF ALGORITHMS

0622700081
DIPARTIMENTO DI INGEGNERIA DELL'INFORMAZIONE ED ELETTRICA E MATEMATICA APPLICATA
EQF7
COMPUTER ENGINEERING
2021/2022



OBBLIGATORIO
YEAR OF COURSE 1
YEAR OF DIDACTIC SYSTEM 2017
PRIMO SEMESTRE
CFUHOURSACTIVITY
540LESSONS
18EXERCISES
324LAB


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.

KNOWLEDGE AND UNDERSTANDING
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.

APPLYING KNOWLEDGE AND UNDERSTANDING
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 (LECTURE/PRACTICE/LABORATORY HOURS 6/0/0)
- DATA TYPES (2 LECTURE HOURS)
- FUNCTIONS AND CLASSES (3 LECTURE HOURS)
- MODULES AND LIBRERIES (1 LECTURE HOURS)

ALGORITHMS AND DATA STRUCTURES (LECTURE/PRACTICE/LABORATORY HOURS 28/21/0)
- ABSTRACT DATA TYPES, ELEMENTARY DATA STRUCTURES AND BINARY SEARCH TREES (4 LECTURE HOURS AND 3 PRACTICE HOURS)
- BALANCED BINARY SEARCH TREES AND B-TREES (5 LECTURE HOURS AND 5 PRACTICE HOURS)
- PRIORITY QUEUES (2 LECTURE HOURS AND 2 PRACTICE HOURS)
- MAPS AND HASH TABLES (2 LECTURE HOURS AND 2 PRACTICE HOURS)
- DATA STRUCTURES AND ALGORITHMS IN STRINGS (2 LECTURE HOURS AND 2 PRACTICE HOURS)
- GRAPHS (10 LECTURE HOURS AND 6 PRACTICE HOURS)
- NETWORK FLOW (3 LECTURE HOURS AND 1 PRACTICE HOURS)

PROGRAMMING TECHNIQUES (LECTURE/PRACTICE/LABORATORY HOURS 9/8/0)
- GREEDY PROGRAMMING (2 LECTURE HOURS AND 3 PRACTICE HOURS)
- EXHAUSTIVE SEARCH AND DYNAMIC PROGRAMMING (3 LECTURE HOURS AND 3 PRACTICE HOURS)
- APPROXIMATION ALGORITHMS (2 LECTURE HOURS)
- LOCAL SEARCH ALGORITHMS (2 LECTURE HOURS AND 2 PRACTICE HOURS)

TOTAL LECTURE/PRACTICE/LABORATORY HOURS 43/29/0
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

THE TEACHING MATERIAL IS AVAILABLE ON THE UNIVERSITY E-LEARNING PLATFORM (HTTP://ELEARNING.UNISA.IT) ACCESSIBLE TO STUDENTS USING THEIR OWN UNIVERSITY CREDENTIALS.

SUGGESTED READINGS:
KLEINBERG, TARDOS, "ALGORITHM DESIGN", PRENTICE 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 IS HELD IN ENGLISH
  BETA VERSION Data source ESSE3