Computer science | ALGORITHM DESIGN

cod. 0512100043

ALGORITHM DESIGN

	0512100043
	COMPUTER SCIENCE
	EQF6
	COMPUTER SCIENCE
	2021/2022

PERCORSO COMUNE

	OBBLIGATORIO
	YEAR OF COURSE 2
	YEAR OF DIDACTIC SYSTEM 2017
	SPRING SEMESTER

TEACHING UNITS

SSD	CFU	HOURS	ACTIVITY	TYPE OF ACTIVITY
INF/01	6	48	LESSONS	COMPULSORY SUBJECTS, CHARACTERISTIC OF THE CLASS
INF/01	3	24	LAB	COMPULSORY SUBJECTS, CHARACTERISTIC OF THE CLASS

	Objectives
	THE MAIN GOALS OF THE CLASS ARE THE FOLLOWING: - TO PROVIDE THE STUDENT WITH GENERAL METHODS AND KNOWLEDGE FOR THE DESIGN OF EFFICIENT ALGORITHMS - TO GIVE THE STUDENTS TOOLS FOR THE ANALYSIS OF RESOURCES (SPACE AND TIME) NEEDED BY THE ALGORITHMS - TO PROVIDE A CATALOGUE OF THE MOST KNOWN AND EFFICIENT ALGORITHMS FOR BASIC COMPUTATIONAL PROBLEMS (SORTING, SEARCHING, OPTIMIZATION, OPTIMIZATION OF RESOURCES, ETC.) SKILL TO APPLY KNOWLEDGE AND COMPREHENSION THE GOAL OF THE CLASS IS TO HELP THE STUDENTS IN DEVELOPING THE SKILL TO TRANSLATE REAL-WORLD PROBLEMS INTO ABSTRACT MODELS AND COMPUTATIONAL PROBLEMS, AND TO DESIGN EFFICIENT ALGORITHMIC SOLUTIONS.

THE MAIN GOALS OF THE CLASS ARE THE FOLLOWING:

- TO PROVIDE THE STUDENT WITH GENERAL METHODS AND KNOWLEDGE FOR THE DESIGN OF EFFICIENT ALGORITHMS
- TO GIVE THE STUDENTS TOOLS FOR THE ANALYSIS OF RESOURCES (SPACE AND TIME) NEEDED BY THE ALGORITHMS
- TO PROVIDE A CATALOGUE OF THE MOST KNOWN AND EFFICIENT ALGORITHMS FOR BASIC COMPUTATIONAL PROBLEMS (SORTING, SEARCHING, OPTIMIZATION, OPTIMIZATION OF RESOURCES, ETC.)

SKILL TO APPLY KNOWLEDGE AND COMPREHENSION

THE GOAL OF THE CLASS IS TO HELP THE STUDENTS IN DEVELOPING THE SKILL TO TRANSLATE REAL-WORLD PROBLEMS INTO ABSTRACT MODELS AND COMPUTATIONAL PROBLEMS, AND TO DESIGN EFFICIENT ALGORITHMIC SOLUTIONS.

	Prerequisites
	STUDENTS SHOULD HAVE ACQUIRED THE NOTIONS OF MATHEMATICS AS TAUGHT IN THE PREVIOUS ACADEMIC YEARS AND THE ABILITY TO DEVELOP LOGICAL REASONING. THEY SHOULD ALSO HAVE LEARNED THE BASIC CONCEPTS OF AN INTRODUCTORY CLASS IN DATA STRUCTURES.

	Contents
	THEORETICAL LESSONS: 48 HOURS EXERCISE LESSONS: 24 HOURS 11. INTRODUCTION TO THE BIG-O, OMEGA, AND THETA NOTATIONS, AND THEIR APPLICATIONS TO THE ANALYSIS OF ALGORITHMS (4 HOURS OF THEORETICAL LESSONS + 2 OF EXERCISE LESSONS). 2. RECURRENCE RELATIONS FOR THE ANALYSIS OF RECURSIVE ALGORITHMS AND METHODS FOR THEIR SOLUTIONS (2 HOURS OF THEORETICAL LESSONS + 2 OF EXERCISE LESSONS). 3. THE DIVIDE AND CONQUER TECHNIQUE FOR THE DESIGN OF ALGORITHMS, AND EXAMPLES OF ITS APPLICATIONS (10 HOURS OF THEORETICAL LESSONS + 4 OF EXERCISE LESSONS). 4. DYNAMIC PROGRAMMING AND EXAMPLES OF ITS APPLICATIONS (10 HOURS OF THEORETICAL LESSONS + 4 OF EXERCISE LESSONS). 5. GREEDY ALGORITHMS AND EXAMPLES OF ITS APPLICATIONS (10 HOURS OF THEORETICAL LESSONS + 4 OF EXERCISE LESSONS) 6. GRAPHS AND GRAPHS ALGORITHMS, BREADTH FIRST SEARCH AND DEPTH FIRST SEARCH ON GRAPHS AND THEIR APPLICATIONS, DIRECTED ACYCLIC GRAPHS AND TOPOLOGICAL SORTING, SHORTEST PATHS IN EDGE-WEIGHTED GRAPHS AND ALGORITHMS FOR THEIR COMPUTATION, MINIMUM COST SPANNING TREES IN EDGE-WEIGHTED GRAPHS AND ALGORITHMS FOR THEIR COMPUTATION (8 HOURS OF THEORETICAL LESSONS + 6 OF EXERCISE LESSONS). 7. INTELLIGENT EXHAUSTIVE SEARCH: BACKTRACKING AND BRANCH-AND- BOUND AND EXAMPLES OF APPLICATIONS (4 HOURS OF THEORETICAL LESSONS + 2 OF EXERCISE LESSONS).

Contents

THEORETICAL LESSONS: 48 HOURS
EXERCISE LESSONS: 24 HOURS
11. INTRODUCTION TO THE BIG-O, OMEGA, AND THETA NOTATIONS, AND THEIR APPLICATIONS TO THE ANALYSIS OF ALGORITHMS (4 HOURS OF THEORETICAL LESSONS + 2 OF EXERCISE LESSONS).
2. RECURRENCE RELATIONS FOR THE ANALYSIS OF RECURSIVE ALGORITHMS AND METHODS FOR THEIR SOLUTIONS (2 HOURS OF THEORETICAL LESSONS + 2 OF EXERCISE LESSONS).
3. THE DIVIDE AND CONQUER TECHNIQUE FOR THE DESIGN OF ALGORITHMS, AND EXAMPLES OF ITS APPLICATIONS (10 HOURS OF THEORETICAL LESSONS + 4 OF EXERCISE LESSONS).
4. DYNAMIC PROGRAMMING AND EXAMPLES OF ITS APPLICATIONS (10 HOURS OF THEORETICAL LESSONS + 4 OF EXERCISE LESSONS).
5. GREEDY ALGORITHMS AND EXAMPLES OF ITS APPLICATIONS (10 HOURS OF THEORETICAL LESSONS + 4 OF EXERCISE LESSONS)
6. GRAPHS AND GRAPHS ALGORITHMS, BREADTH FIRST SEARCH AND DEPTH FIRST SEARCH ON GRAPHS AND THEIR APPLICATIONS, DIRECTED ACYCLIC GRAPHS AND
TOPOLOGICAL SORTING, SHORTEST PATHS IN EDGE-WEIGHTED GRAPHS AND ALGORITHMS FOR THEIR COMPUTATION, MINIMUM COST SPANNING TREES IN EDGE-WEIGHTED GRAPHS AND ALGORITHMS FOR THEIR COMPUTATION (8 HOURS OF THEORETICAL LESSONS + 6 OF EXERCISE LESSONS).
7. INTELLIGENT EXHAUSTIVE SEARCH: BACKTRACKING AND BRANCH-AND- BOUND AND EXAMPLES OF APPLICATIONS (4 HOURS OF THEORETICAL LESSONS + 2 OF EXERCISE LESSONS).

	Teaching Methods
	THIS CLASS INCLUDES THEORETICAL LECTURES (48 HOURS) WITH THE GOAL OF LEARNING THE BASIC TECHNIQUES FOR THE DESIGN AND ANALYSIS OF ALGORITHMS, AND EXCERCISES-BASED LECTURES (24 HOURS) 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. STUDENTS ARE ADVISED TO ATTEND CLASSES THOUGH THEY ARE NOT OBLIGED TO.

Teaching Methods

THIS CLASS INCLUDES THEORETICAL LECTURES (48 HOURS) WITH THE GOAL OF LEARNING THE BASIC TECHNIQUES FOR THE DESIGN AND ANALYSIS OF ALGORITHMS, AND EXCERCISES-BASED LECTURES (24 HOURS) 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.
STUDENTS ARE ADVISED TO ATTEND CLASSES THOUGH THEY ARE NOT OBLIGED TO.

	Verification of learning
	THE FINAL GRADE IS EXPRESSED WITH A GRADE X OUT-OF-THIRTY. THE EXAM CONSISTS OF A WRITTEN TEST AND AN ORAL EXAM. THE WRITTEN TEST MAY BE REPLACED BY A MIDTERM EXAM AND A FINAL. THE WRITTEN TEST TIME RANGES FROM 90 TO 120 MINUTES. IT TAKES PLACE BEFORE THE ORAL TEST AND IT IS CONSIDERED PASSED WITH THE ACHIEVEMENT OF THE PRE-ESTABLISHED MINIMUM SCORE. WRITTEN TESTS WILL BE SPECIALLY DESIGNED TO VERIFY THE ACQUISITION BY THE STUDENT OF THE ABILITY TO APPLY ALGORITHMIC DESIGN AND ANALYSIS METHODOLOGIES TO SIMPLE CONCRETE PROBLEMS. THE ORAL TEST CONSISTS OF QUESTIONS AND DISCUSSION ON THE METHODOLOGIES STUDIED DURING THE COURSE. IT IS MAINLY INTENDED TO ASSESS THE LEVEL OF KNOWLEDGE AND UNDERSTANDING REACHED BY THE STUDENT. AS A RULE, THE FINAL GRADE IS THE ARITHMETIC AVERAGE OF THE WRITTEN AND ORAL TESTS EVALUATIONS.

Verification of learning

THE FINAL GRADE IS EXPRESSED WITH A GRADE X OUT-OF-THIRTY. THE EXAM CONSISTS OF A WRITTEN TEST AND AN ORAL EXAM. THE WRITTEN TEST MAY BE REPLACED BY A MIDTERM EXAM AND A FINAL. THE WRITTEN TEST TIME RANGES FROM 90 TO 120 MINUTES. IT TAKES PLACE BEFORE THE ORAL TEST AND IT IS CONSIDERED PASSED WITH THE ACHIEVEMENT OF THE PRE-ESTABLISHED MINIMUM SCORE. WRITTEN TESTS WILL BE SPECIALLY DESIGNED TO VERIFY THE ACQUISITION BY THE STUDENT OF THE ABILITY TO APPLY ALGORITHMIC DESIGN AND ANALYSIS METHODOLOGIES TO SIMPLE CONCRETE PROBLEMS. THE ORAL TEST CONSISTS OF QUESTIONS AND DISCUSSION ON THE METHODOLOGIES STUDIED DURING THE COURSE. IT IS MAINLY INTENDED TO ASSESS THE LEVEL OF KNOWLEDGE AND UNDERSTANDING REACHED BY THE STUDENT. AS A RULE, THE FINAL GRADE IS THE ARITHMETIC AVERAGE OF THE WRITTEN AND ORAL TESTS EVALUATIONS.

	Texts
	TEXTBOOKS: KLEINBERG, TARDOS. ALGORITHM DESIGN. PEARSON ADDISON WESLEY. S. DASGUPTA, C.H. PAPADIMITRIOU, AND U.V. VAZIRANI. ALGORITHMS. MCGRAW-HILL FURTHER COURSE MATERIAL ALONG WITH THE NECESSARY SUPPORT TO STUDY AND TO PREPARE FOR THE EXAM IS PROVIDED THROUGH THE LECTURERS' WEB PAGES AND THROUGH THE E-LEARNING PLATFORM AT THE FOLLOWING URL: HTTP://ELEARNING.INFORMATICA.UNISA.IT/ .