2. Professors
  3. Teaching

ALGORITHMS

Ugo VACCARO ALGORITHMS

0512100007
DIPARTIMENTO DI INFORMATICA
COMPUTER SCIENCE
2014/2015



OBBLIGATORIO
YEAR OF COURSE 2
YEAR OF DIDACTIC SYSTEM 2008
PRIMO SEMESTRE
CFUHOURSACTIVITY
648LESSONS


UGO VACCARO T Curriculum
Objectives
THE MAIN OBJECTIVES OF THE COURSE ARE THE FOLLOWING: 1) TO OFFER STUDENTS METHODS AND KNOWLEDGE FOR THE DESIGN OF EFFICIENT ALGORITHMS;
2)TO OFFER STUDENTS METHODS FOR THE ANALYSIS OF RESOURCES (TIME AND MEMORY) USED BY ALGORITHMS; 3) TO OFFER STUDENTS A CATALOG
OF THE MOST EFFICIENT ALGORITHMS FOR THE MOST BASIC COMPUTATIONAL PROBLEMS (SORTING, SEARCHING, RESOURCE OPTIMIZATION, ETC.)



CABILITY TO APPLY KNOWLEDGE AND UNDERSTANDING:
THE COURSE AIMS TO EDUCATE THE STUDENT TO DESIGN ABSTRACT MODELS AND FORMAL ALGORITHMIC PROBLEMS FROM
REAL-LIFE COMPUTATIONAL PROBLEMS, AND TO DESIGN FOR THEM EFFICIENT ALGORITHMIC SOLUTIONS.
THIS GOAL WILL BE REACHED BY MEANS OF THE FOLLOWING TEACHING METHOD: EACH ALGORITMIC
PROBLEMS STUDIED IN THE COURSE WILL BE INTRODUCED BY MEANS OF REAL-LFE EXAMPLES, MOREOVER EACH
TOPI OF THE COURSE WILL BE INTRODUCED FOLLOWING FOUR BASIC STEPS:
A) DESCRIPTION OF THE REAL-LIFE PROBLEM
B)ELABORATION OF A FORMAL MODEL OF THE REAL-LIFE PROBLEM (IN THIS STEP,
IT WILL BE USEFUL, IF POSSIBLE) TO SHOW THAT A SAME ABSTRACT MODEL MAY CORRESPOND TO SEVERAL
REAL-LIFE PROBLEMS)
C) SOLUTION OF THE ABSTRACT PROBLEM BY MEANS OF AN ALGORITHM DESIGNED
THROUGH THE APPLICATIONS OF ONE (OR SEVERAL) OF THE TECHNIQUES FOR THE DESIGN
OF ALGORITHM STUDIED IN THE COURSE
D) ANALYSIS OF THE RESOURCE UTILIZED BY THE ALGORITHM

AUTONOMOUS JUDGEMENT:
STUDENTS ARE GUIDED TO LEARN IN A CRITICAL WAY ALL MATERIAL THAT IS EXPLAINED IN THEIR CLASS,
TO COMPARE THE DIFFERENT APPROACHES FOR THE SOLUTION OF PROBLEMS, AND TO IDENTIFY AND PROPOSE, IN AUTONOMOUS WAY,
THE MOST EFFICIENT SOLUTION.

COMMUNICATION SKILLS:
THE COURSE WILL HELP THE DEVELOPMENT OF THE FOLLOWING SKILLS IN STUDENTS:
CAPABILITY TO EXPOSE WITH PRECISE AND FORMAL MODELS CLASSES OF PRACTICAL PROBLEMS,
BY IDENTIFYING THE KEY CHARACTERISTICS OF THEM AND DISCARDING THE INESSENTIALS.

LEARNING CAPABILITIES
THE STUDENT WILL BE ABLE TO PERFORM IN AUTONOMOUS FASHION
THE IN-DEPTH STUDY OF ALGORITHMICH TECHNIQUES TO SOLVE PROBLEMS OF RELEVANT INTEREST.
THE COURSE WILL PROVIDE STUDENTS THE TOOLS NEEDED TO UPDATE THEIR KNOWLEDGE EVEN
AFTER THE CONCLUSION OF OF THE COURSE (LIFE LONG LEARNING). THE STUDENT WILL BE ABLE TO READ
ALGORITHMIC TECHNIQUES TO SOLVE PROBLEMS, EVEN SPECIALIZED ONES, AND UNDERSTANDING THEIR BASIC MEANING.
Prerequisites
STUDENTS ARE REQUIRED TO HAVE ALREADY DEVELOPPED BASIC CAPABILITIES OF FORMAL DEDUCTIVE REASONING. STUDENTS ARE ALSO REQUIRED TO MASTER THE BASIC CONCEPTS OF AN INTRODUCTIVE COURSE IN PROGRAMMING
Contents
1. INTRODUCTION TO THE ANALYSIS OF ALGORITHMS

2. DIVIDE AND CONQUER AND ITS: APPLICATIONS:
MERGESORT, QUICKSORT, RECURRENCES, INTEGER AND MATRIX MULTIPLICATIONS

3. DYNAMIC PROGRAMMING TECHNIQUE AND SIMPLE APPLICATIONS: COMPUTATION OF FIBONACCI NUMBER AND COMBINATIONS. APPLICATIONS OF DYNAMIC PROGRAMMING
TO COMBINATIORIAL OPTIMIZATION: RESOURCE SCHEDULING, INTEGER KNAPSACK, PROBLEMS ON STRINGS.

4. GREEDY TECHNIQUE AND ITS APPLICATIONS: INTERVAL SCHEDULING, SCHEDULING WITH DEADLINE, DATA COMPRESSION AND HUFFMAN CODING.

5. ALGORITHMS ON GRAPHS: CONNECTIVITY AND GRAPH EXPLORATIONS, DAG TOPOLOGICAL SORTING, SHORTEST PATHS, MINIMUM SPANNING TREES.

6. FLOW COMPUTATION AND APPLICATIONS.
Teaching Methods
THE COURSE HAS BOTH LECTURES AIMED AT TEACHING BASIC TECHNIQUES FOR THE DESIGN AND ANALYSIS OF ALGORITHMS AND PRACTICE LECTURES AIMED AT ILLUSTRATING, WITH PLENTY OF EXAMPLES, HOW THE ACQUIRED TECHNIQUES CAN
BE APPLIED TO SOLVE ALGORITHMIC PROBLEMS OF PRACTICAL RELEVANCE.
Verification of learning
THERE WILL BE A FINAL EXAM, CONSISTING IN A WRITTEN TEST AND A ORAL COLLOQUIUM. THE FINAL WRITTEN EXAMS MAY BE REPLACED BY A MIDTERM EXAM AND A FINAL EXAM. TEST WILL BE ESPECIALLY DESIGNED TO MEASURE THE STUDENT CAPABILITIES OF APPLYING THE TECHNIQUES ILLUSTRATED DURING THE COURSE TO THE DESIGN AND ANALYSIS OF ALGORITHMS FOR SIMPLE PROBLEMS.
Texts
KLEINBERG, TARDOS. ALGORITHM DESIGN. PEARSON ADDISON
WESLEY.
More Information
AT THE LINK HTTP://WWW.DI.UNISA.IT/~UV/ALGO/ALGO.HTML STUDENTS WILL FIND ADDITIONA USEFUL MATERIAL FOR THE EXAM
  BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2016-09-30]