2. Professors
  3. Teaching

ALGORITHM DESIGN

Ugo VACCARO ALGORITHM DESIGN

0512100043
DIPARTIMENTO DI INFORMATICA
EQF6
COMPUTER SCIENCE
2016/2017



OBBLIGATORIO
YEAR OF COURSE 2
YEAR OF DIDACTIC SYSTEM 2015
SECONDO SEMESTRE
CFUHOURSACTIVITY
648LESSONS


UGO VACCARO T Curriculum
Objectives
THE MAIN GOALS OF THIS CLASS ARE THE FOLLOWING: 1) TO PROVIDE THE STUDENT WITH GENERAL METHODS AND BASIC KNOWLEDGE FOR THE DESIGN OF EFFICIENT ALGORITHMS; 2) TO GIVE THE STUDENTS TOOLS FOR THE ANALYSIS OF RESOURCES (SPACE AND TIME) NEEDED BY THE ALGORITHMS; 3) TO PROVIDE A CATALOGUE OF THE MOST KNOWN AND EFFICIENT ALGORITHMS FOR BASIC COMPUTATIONAL PROBLEMS (SORTING, SEARCHING, OPTIMIZATION ON GRAPHS AND SEQUENCES, OPTIMIZATION OF RESOURCES, ETC.).


APPLYING KNOWLEDGE AND UNDERSTANDING: THE AIM OF THIS CLASS IS TO
MAKE THE STUDENT CAPABLE OF ABSTRACTING MODELS AND FORMAL ALGORITHMIC PROBLEMS FROM REAL-LIFE COMPUTATIONAL PROBLEMS, AND DESIGNING EFFICIENT ALGORITHMIC SOLUTIONS FOR THEM.
Prerequisites
STUDENTS SHOULD HAVE ACQUIRED THE NOTIONS OF MATHEMATICS AS TAUGHT IN PREVIOUS ACADEMIC YEARS AND THE ABILITY TO DEVELOP LOGICAL REASONING. THEY SHOULD ALSO HAVE LEARNED AND MASTERED THE BASIC CONCEPTS OF AN INTRODUCTORY CLASS IN ALGORITHMS AND DATA STRUCTURES.
Contents
1. INTRODUCTION TO THE ASYMPTOTIC ANALYSIS OF ALGORITHMS.

2. THE ALGORITHM DESIGN TECHNIQUE OF DIVIDE-AND-
CONQUER WITH RELATED APPLICATION EXAMPLES: MERGESORT, QUICKSORT; RECURRENCES.

3. THE ALGORITHM DESIGN TECHNIQUE OF DYNAMIC
PROGRAMMING WITH RELATED APPLICATION EXAMPLES:
COMPUTATION OF FIBONACCI NUMBERS, COMBINATIONS;
OPTIMIZATION PROBLEMS: SCHEDULING OF RESOURCES,
INTEGER KNAPSACK PROBLEM, PROBLEMS ON STRINGS,
SHORTEST PATHS IN GRAPHS.

4. THE GREEDY ALGORITHM DESIGN TECHNIQUE WITH RELATED APPLICATION EXAMPLES: SCHEDULING OF INTERVALS; SCHEDULING WITH DEADLINES; DATA COMPRESSION AND HUFFMAN CODES.

5. ALGORITHMS ON GRAPHS. CONNECTIVITY AND VISITS OF
GRAPHS; DAG AND TOPOLOGICAL ORDERING; SHORTEST PATHS
(DIJKSTRA ALGORITHM). MINIMUM SPANNING TREES (PRIM
AND KRUSKAL ALGORITHMS).

6. COMPUTATION OF NETWORK FLOW AND ITS APPLICATION.

7. INTELLIGENT EXHAUSISTIVE SEARCH: BACKTRACKING AND
BRANCH-AND- BOUND
Teaching Methods
THIS CLASS INCLUDES THEORETICAL LECTURES WITH THE GOAL OF LEARNING THE BASIC TECHNIQUES FOR THE DESIGN AND ANALYSIS OF ALGORITHMS, AND EXCERCISES-BASED LECTURES, IN WHICH IT WILL BE EXPLAINED, WITH PLENTY OF EXAMPLES, HOW THE ACQUIRED THEORETICAL KNOWLEDGE MAY BE USED TO SOLVE ALGORITHMIC PROBLEMS OF PRACTICAL INTEREST.
Verification of learning
THE EVALUATION OF THE LEARNING LEVEL OF STUDENTS WILL BE DONE BY MEANS OF A FINAL EXAM, CONSISTING OF A WRITTEN TEST FOLLOWED BY AN ORAL TEST. THE WRITTEN TEST MAY BE REPLACED BY TWO MID-TERMS EXAMS. THE WRITTEN TESTS WILL BE ESPECIALLY DESIGNED TO EVALUATE THE STUDENTS’ CAPABILITIES TO APPLY THE METHODOLOGIES FOR THE DESIGN AND ANALYSIS OF ALGORITHMS TO SIMPLE REAL-LIFE PROBLEMS.
Texts
TEXTBOOKS:
KLEINBERG, TARDOS. ALGORITHM DESIGN. PEARSON ADDISON
WESLEY.

S. DASGUPTA, C. H. PAPADIMITRIOU, AND U. V. VAZIRANI. ALGORITHMS. MCGRAW-HILL.

ADDITIONAL TEACHING MATERIAL (EXERCISES, TESTS FOR SELF- ASSESSMENT) WILL BE MADE AVAILABLE TROUGH THE TEACHERS’ PERSONAL WEB SITES).
More Information
ATTENDING LESSONS AND EXERCITATIONS IS ADVISED. IT IS REASONABLE TO ASSUME THAT AN AVERAGE OF TWO HOURS OF INDIVIDUAL STUDY ARE REQUIRED FOR EACH HOUR OF CLASS LESSON
  BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2019-03-11]