ALGORITMI E LABORATORIO

Academic Year 2017/2018 - 2° Year
Teaching Staff Credit Value: 9
Taught classes: 36 hours
Laboratories: 36 hours
Term / Semester:

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.

  • Algorithms Lab

    Conoscenza e capacità di comprensione (knowledge and understanding): we will focus on the implementation of the main data stuttures analyzed during the theoretical module of Algorithms
    Capacità di applicare conoscenza e comprensione (applying knowledge and understanding): we will focus on the implementation skills and on the algorithmic solutions design.
    Autonomia di giudizio (making judgements): The student will be able to judge the effectiveness of its implementation and of their project work.
    Capacità di apprendimento (learning skills): the student will be able to adapt to other contexts all solutions and algorithms.


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: Insertion-Sort (correctness and complexity)
    Divide-and-Conquer methodology: Merge-Sort (complexity)
    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

    Elementary graph algorithms
    Breadth-first search
    Depth-first search (edges classification)
    Topological sorting
    Strongly connected components

  • Algorithms Lab

    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

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