Computer science | ALGORITHMS

cod. 0512100007

ALGORITHMS

	0512100007
	DIPARTIMENTO DI INFORMATICA

	COMPUTER SCIENCE
	2013/2014

CURRICULUM METODOLOGICO

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

TEACHING UNITS

SSD	CFU	HOURS	ACTIVITY	TYPE OF ACTIVITY
INF/01	6	48	LESSONS	COMPULSORY SUBJECTS, CHARACTERISTIC OF THE CLASS
INF/01	0	12	OTHER	COMPULSORY SUBJECTS, CHARACTERISTIC OF THE CLASS

	Objectives
	EDUCATIONAL OBJECTIVES: LEARNING OUTCOMES AND ACQUIRED COMPETENCIES EXPECTED (DUBLIN DESCRIPTORS) KNOWLEDGE AND UNDERSTANDING: THE MAIN GOALS ARE THE FOLLOWING: 1) TO PROVIDE THE STUDENT WITH METHODS AND KNOWLEDGE FOR THE DESIGN OF EFFICIENT ALGORITHMS; 2) TO PROVIDE 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 OF RESOURCES, ETC.). APPLYING KNOWLEDGE AND UNDERSTANDING: THE AIM IS TO MAKE THE STUDENT CAPABLE OF ABSTRACTING MODELS AND FORMAL ALGORITHMIC PROBLEMS FROM REAL COMPUTATIONAL PROBLEMS, AND DESIGNING EFFICIENT ALGORITHMIC SOLUTIONS. THIS WILL BE ACCOMPLISHED USING THE FOLLOWING TEACHING SCHEME. ANY COMPUTATIONAL PROBLEM WILL BE INTRODUCED FROM CONCRETE EXAMPLES. THE PRESENTATION OF EACH TOPIC WILL BE SPLIT IN FOUR PARTS: 1. DESCRIPTION OF THE REAL COMPUTATIONAL PROBLEM. 2. MODELING THE REAL PROBLEM BY MEAN OF AN ABSTRACT PROBLEM (IN THIS PHASE IT WILL BE USEFUL TO SHOW, WHEN POSSIBLE, THAT AN ABSTRACT FORMULATION MAY CORRESPOND TO SEVERAL REAL PROBLEMS). 3. SOLUTION OF AN ABSTRACT PROBLEM BY AN ALGORITHM OBTAINED THROUGH THE APPLICATION OF GENERAL ALGORITHM DESIGN TECHNIQUES INTRODUCED DURING THE CLASSES. 4. ANALYSIS OF RESOURCES USED FROM THE DESIGNED ALGORITHM. COMMUNICATION SKILLS: THE COURSE WILL ENCOURAGE THE DEVELOPMENT OF THE FOLLOWING SKILLS OF THE STUDENT: CAPABILITY OF PRESENT IN PRECISE AND FORMAL TERMS AN ABSTRACT MODEL FOR CONCRETE PROBLEMS, FOCUSING ON THEIR MAIN FEATURES AND DISCARDING THE INESSENTIAL ONES. MAKING JUDGEMENTS: STUDENTS ARE GUIDED TO LEARN, IN A CRITICAL WAY, EVERYTHING IS EXPLAINED IN THE CLASS, TO COMPARE THE DIFFERENT APPROACHES FOR THE SOLUTION OF ALGORITHMIC PROBLEMS, AND TO IDENTIFY AND PROPOSE INDEPENDENTLY THEIR MOST EFFICIENT SOLUTION.

EDUCATIONAL OBJECTIVES: LEARNING OUTCOMES AND ACQUIRED COMPETENCIES EXPECTED (DUBLIN DESCRIPTORS)

KNOWLEDGE AND UNDERSTANDING: THE MAIN GOALS ARE THE FOLLOWING: 1) TO PROVIDE THE STUDENT WITH METHODS AND KNOWLEDGE FOR THE DESIGN OF EFFICIENT ALGORITHMS; 2) TO PROVIDE 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 OF RESOURCES, ETC.).

APPLYING KNOWLEDGE AND UNDERSTANDING: THE AIM IS TO MAKE THE STUDENT CAPABLE OF ABSTRACTING MODELS AND FORMAL ALGORITHMIC PROBLEMS FROM REAL COMPUTATIONAL PROBLEMS, AND DESIGNING EFFICIENT ALGORITHMIC SOLUTIONS. THIS WILL BE ACCOMPLISHED USING THE FOLLOWING TEACHING SCHEME. ANY COMPUTATIONAL PROBLEM WILL BE INTRODUCED FROM CONCRETE EXAMPLES. THE PRESENTATION OF EACH TOPIC WILL BE SPLIT IN FOUR PARTS: 1. DESCRIPTION OF THE REAL COMPUTATIONAL PROBLEM. 2. MODELING THE REAL PROBLEM BY MEAN OF AN ABSTRACT PROBLEM (IN THIS PHASE IT WILL BE USEFUL TO SHOW, WHEN POSSIBLE, THAT AN ABSTRACT FORMULATION MAY CORRESPOND TO SEVERAL REAL PROBLEMS). 3. SOLUTION OF AN ABSTRACT PROBLEM BY AN ALGORITHM OBTAINED THROUGH THE APPLICATION OF GENERAL ALGORITHM DESIGN TECHNIQUES INTRODUCED DURING THE CLASSES. 4. ANALYSIS OF RESOURCES USED FROM THE DESIGNED ALGORITHM.

COMMUNICATION SKILLS: THE COURSE WILL ENCOURAGE THE DEVELOPMENT OF THE FOLLOWING SKILLS OF THE STUDENT: CAPABILITY OF PRESENT IN PRECISE AND FORMAL TERMS AN ABSTRACT MODEL FOR CONCRETE PROBLEMS, FOCUSING ON THEIR MAIN FEATURES AND DISCARDING THE INESSENTIAL ONES.

MAKING JUDGEMENTS: STUDENTS ARE GUIDED TO LEARN, IN A CRITICAL WAY, EVERYTHING IS EXPLAINED IN THE CLASS, TO COMPARE THE DIFFERENT APPROACHES FOR THE SOLUTION OF ALGORITHMIC PROBLEMS, AND TO IDENTIFY AND PROPOSE INDEPENDENTLY THEIR MOST EFFICIENT SOLUTION.

	Prerequisites
	THE STUDENT SHOULD HAVE ACQUIRED THE ABILITY TO DEVELOP LOGICAL REASONING. IT SHOULD ALSO HAVE LEARNED AND MASTERED THE BASIC CONCEPTS OF AN INTRODUCTORY COURSE IN PROGRAMMING.

	Contents
	COURSE CONTENT (48 HOURS) 1.INTRODUCTION TO THE ASYMPTOTIC ANALYSIS OF ALGORITHMS. 2.THE ALGORITHM DESIGN TECHNIQUE OF DIVIDE-AND-CONQUER WITH RELATED APPLICATION EXAMPLES: MERGESORT, QUICKSORT; RECURRENCES; INTEGER MULTIPLICATION AND MATRIX MULTIPLICATION. 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.

Contents

COURSE CONTENT (48 HOURS)

1.INTRODUCTION TO THE ASYMPTOTIC ANALYSIS OF ALGORITHMS.
2.THE ALGORITHM DESIGN TECHNIQUE OF DIVIDE-AND-CONQUER WITH RELATED APPLICATION EXAMPLES: MERGESORT, QUICKSORT; RECURRENCES; INTEGER MULTIPLICATION AND MATRIX MULTIPLICATION.
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.

	Teaching Methods
	TEACHING METHODS THE COURSE INCLUDES A PART OF THEORETICAL LECTURES AIMED TO THE LEARNING OF THE BASIC TECHNIQUES FOR THE DESIGN AND ANALYSIS OF ALGORITHMS, AND A PART OF LESSON EXERCISES IN WHICH IT WILL BE EXPLAINED, WITH PLENTY OF EXAMPLES, HOW THE THEORETICAL KNOWLEDGE GAINED MAY BE USED TO SOLVE ALGORITHMIC PROBLEMS OF PRACTICAL INTEREST.

	Verification of learning
	ASSESSMENT METHODS THE MONITORING AND EVALUATION OF THE LEVEL OF STUDENT LEARNING WILL BE THROUGH A FINAL EXAM, CONSISTING OF A WRITTEN TEST FOLLOWED BY AN ORAL TEST. THE WRITTEN TEST MAY BE REPLACED BY TWO INTERVENING TRIALS. THE WRITTEN TESTS WILL BE ESPECIALLY DESIGNED TO TEST THE LEVEL OF ACQUISITION BY THE STUDENT OF THE ABILITY TO APPLY THE METHODOLOGIES FOR THE DESIGN AND ANALYSIS OF ALGORITHMS TO SIMPLE ALGORITHMIC PROBLEMS.

Verification of learning

ASSESSMENT METHODS
THE MONITORING AND EVALUATION OF THE LEVEL OF STUDENT LEARNING WILL BE THROUGH A FINAL EXAM, CONSISTING OF A WRITTEN TEST FOLLOWED BY AN ORAL TEST. THE WRITTEN TEST MAY BE REPLACED BY TWO INTERVENING TRIALS. THE WRITTEN TESTS WILL BE ESPECIALLY DESIGNED TO TEST THE LEVEL OF ACQUISITION BY THE STUDENT OF THE ABILITY TO APPLY THE METHODOLOGIES FOR THE DESIGN AND ANALYSIS OF ALGORITHMS TO SIMPLE ALGORITHMIC PROBLEMS.

	Texts
	TEXTBOOKS: KLEINBERG, TARDOS. ALGORITHM DESIGN. PEARSON ADDISON WESLEY. ADDITIONAL TEACHING MATERIAL (EXERCISES, TESTS FOR SELF-ASSESSMENT) WILL BE MADE AVAILABLE TO THE TEACHERS' PERSONAL WEB SITES).