# Computer science | ALGORITHM DESIGN

## Computer science ALGORITHM DESIGN

 0512100043 COMPUTER SCIENCE EQF6 COMPUTER SCIENCE 2021/2022

 OBBLIGATORIO YEAR OF COURSE 2 YEAR OF DIDACTIC SYSTEM 2017 SECONDO SEMESTRE
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

 MARCELLA ANSELMO T
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 DATA STRUCTURES.
Contents
LESSON HOURS: 48
EXERCISE HOURS: 24

1. INTRODUCTION TO THE ASYMPTOTIC NOTATIONS BIGOH, OMEGA, THETA AND THEIR APPLICATIONS TO THE ANALYSIS OF ALGORITHMS. (4 HOURS OF LESSONS AND 2 HOURS OF EXERCISES)
2. RECURRENCE RELATIONS FOR THE ANALYSIS OF RECURSIVE ALGORITHMS, AND METHODS FOR THEIR SOLUTIONS. (2 HOURS OF LESSONS AND 2 HOURS OF EXERCISES)
3. THE DIVIDE AND CONQUER TECHNIQUE FOR THE DESIGN OF ALGORITHMS, AND EXAMPLES OF APPLICATIONS. (10 HOURS OF LESSONS AND 4 HOURS OF EXERCISES)
4. THE DYNAMIC PROGRAMMING TECHNIQUE FOR THE DESIGN OF ALGORITHMS, AND EXAMPLES OF APPLICATIONS. (10 HOURS OF LESSONS AND 4 HOURS OF EXERCISES)
5. THE GREEDY TECHNIQUE FOR THE DESIGN OF ALGORITHMS, AND EXAMPLES OF APPLICATIONS. (10 HOURS OF LESSONS AND 4 HOURS OF EXERCISES)
6. GRAPHS AND GRAPHS ALGORITHMS. BREADTH FIRST AND DEPTH FIRST SEARCH ON GRAPHS AND THEIR APPLICATIONS. DIRECTED ACYCLIC GRAPHS AND TOPOLOGICAL SORTING. MINIMUM COST 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 LESSONS AND 6 HOURS OF EXERCISES)
7. INTELLIGENT EXHAUSTIVE SEARCH: BACKTRACKING AND BRANCH-AND- BOUND AND EXAMPLES OF APPLICATIONS. (4 HOURS OF LESSONS AND 2 HOURS OF EXERCISES)
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 EXERCISES-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 EXAM. 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 ARE PROVIDED THROUGH THE LECTURERS' WEB PAGES AND THROUGH THE E-LEARNING PLATFORM AT THE FOLLOWING URL HTTP://ELEARNING.INFORMATICA.UNISA.IT/.
ADDITIONAL TEACHING MATERIAL (EXERCISES, TESTS FOR SELF-ASSESSMENT) WILL BE MADE AVAILABLE THROUGH THE TEACHERS PERSONAL WEB SITES).