ALGORITMI E LABORATORIO M - Z

Academic Year 2019/2020 - 2° Year - Curriculum A and Curriculum B

Learning Objectives

• Algorithms

  Knowledge and understanding: students will acquire knowldege relative to the main methodologies for the design of efficient algorithms (incremental, recursion, dynamic programming, greedy algorithms), as well as the techniques for their computational analysis, both in the worst and in the average cases. Applying knowledge and understanding: students will acquire the ability to solve problems of low difficulty, requiring the design and analysis of elementary algorithmic solutions. Making judgements: students will be able to evaluate the quality of an algorithmic solution in terms of efficiency and reuse. Communication skills: students will acquire the necessary communication skills and expressive ability in communicate problems regarding the algorithmic studies, also to non-expert interlocutors. Learning skills: students will have the ability to adapt the knowledge acquired also in new contexts and to advance his/her knowledge through the consultation of specialist sources in the algorithmic field.

• LABORATORIO

  • Knowledge and understanding: we will focus on the implementation of the main data stuttures analyzed during the theoretical module of Algorithms
    Applying knowledge and understanding: we will focus on the implementation skills and on the algorithmic solutions design.
    Making judgements: the student will be able to judge the effectiveness of its implementation and of their project work.
    Learning skills: the student will be able to adapt to other contexts all solutions and algorithms.

Course Structure

• Algorithms

  Teaching will be carried out through lectures (for a total of 36 hours) during which the contents of the course will be presented, also through practical demonstrations. In addition, the students will have at his disposal a learning platform through which it will be possible to practice during their home-study and self-evaluate themselves on the contents of the course. The same platform provides a valid tool for the exam preparation.

• LABORATORIO

  Practical laboratory

Detailed Course Content

• Algorithms

  GENERAL DESCRIPTION

  The course presents the main design methodoligies (incremental, recursion, dynamic programming, greedy algorithms) and the techniques for their complexity analysis, both in the worst and average cases.

  DETAILED SYLLABUS

  Introduction Computational problems and algorithms: the sorting problem; Algorithms as technology; Incremental methodology VS Divide-and-Conquer methodology; Asymptotic notations and relationships among them Standard notations and common functions; Recurrences; The substitution method; The iterative method and the recursion tree; The master theorem; Sorting and order statistics; Heaps and their construction; Priority queues; Quicksort and its randomized version; Analysis of Quicksort in the worst- and average case; Lower bounds for sorting; Sorting in linear time: Counting-Sort, Radix-Sort, Bucket-Sort; Medians and order statistics; Hashing; Hash table; Hash functions (division method, multiplication method, universal hashing); Open addressing; Red-black trees; Rotations, insertions, deletions; Complexity analysis; Elements of dynamic programming; Optimal substructure, overlapping subproblems, reconstructing an optimal solution; Some case studies: assembly line scheduling, matrix-chain multiplication, longest common subsequence, editing distance; Elements of the greedy strategy Greedy-choice property, optimal substructure; Some case studies: the activity-selection problem, Huffman codes; Algorithms on strings: edit and hamming distance. Elementary algorithms on graphs: shortest path algorithms; Bellman-Ford algorithm; Dijkstra's algoritmi; All-Pairs-Shortest Paths

• LABORATORIO

  • The aim of Algorithms Laboratory is to provide the tools for the implementation of the algorithms and the data structures discussed in the Algorithms class. It will be done through the use of an object-oriented programming language. The C ++ language will be used as the main tool to present the implementations of data structures and algorithms.

Textbook Information

• Algorithms

  Algorithms T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to algorithms (Third Edition), The MIT Press, Cambridge - Massachusetts, 2009

• LABORATORIO

  T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to algorithms (Third Edition), The MIT Press, Cambridge - Massachusetts, 2009