Algorithms and Data Structures (2007/2008)

  1. Home
  2. Teaching
  3. Bachelor's degree
  4. Bachelor's degree in Bioinformatics (until 2008-2009)
  5. Insegnamenti

Course Not running, not visible

Course code
4S00013
Credits
10
Coordinator
Alessandra Di Pierro
Course news Seminars related to the course
Teaching is organised as follows:
Unit Credits Academic sector Period Academic staff
Laboratorio 2 INF/01-INFORMATICS 1° Q, 2° Q Giuditta Franco
Teoria 8 INF/01-INFORMATICS 1° Q, 2° Q Alessandra Di Pierro

Learning outcomes

Module: Teoria
-------
In this course students will learn how to use a computer for solving real life problems via the design of suitable algorithms. Possible solutions are compared in terms of their efficiency. To this purpose the course includes the study of the mathematical methods for the analysis and the evaluation of the various algorithms. Abstract mathematical stuctures are used to represent the concrete data of a given problem; they play a fundamental role in the encoding of the concrete setting in the virtual world of computers.


Module: Laboratorio
-------
In the laboratory of Algorithms and Data Structures the expertise of students on object programming will be improved in order to implement advanced data structures and algorithms. Lectures will be focused on Java language, of which it is expected a knowledge at a basic level.

Syllabus

Module: Teoria
-------
-Computational problems: indecidability, tractability, computational model and computational complexity.

-Arrays and lists: binary search, recursion, linked lists.

-Exact string matching algorithms.

-Trees: recursive algorithms on binary trees, insertion and deletion, breadth-first visit and tree representations.

-Dictionaries: binary search trees, AVL trees.

-Algorithms for the construction of Suffix Trees.

-Graphs: problems on graphs, graph representations, shortest paths.

-Stacks and queues: implementation, breadth-first and depth-first search.

-Priority queues: heaps, implementation, building and sorting a heap.

-NP-completeness: Polynomial time, NP-completeness and reducibility, NP-complete problems, Cook-Levin theorem.


Module: Laboratorio
-------
Lecture 1: Use of interface mechanism. Example of application by implementation of ADT lists, codes, e piles.

Lecture 2: Use of comparable interface. Implementation of ordering algorithms by insertion (InsertionSort) and by decrementing (ShellSort).

Lecture 3: Techniques to compare implementation methods. Comparison between ordering algorithm implementations: QuickSort and MergeSort.

Lecture 4: Exact string matching algorithms.

Lecture 5: Implementation of a dynamic programming algorithm: search of maximum common subsequence (MaxSSC).

Lecture 6: Implementation of ADT Tree and binary search tree. Use of interface Iterator. Implementation of visit methods.

Lecture 7: Implementation of a greedy algorithm: Kruskal algorithm.

Lecture 8: Sketches on algorithms for construction of suffix trees.

Assessment methods and criteria

Module: Teoria
-------
Written test divided in two parts: Teoria and Laboratorio. The duration of the test is 3 hours: 2 hours for the theory part and 1 hour for the practical part. Candidates must score at least 18/30 for each part of the test. The overall final score is calculated as the weighted sum of the two individual scores with weights 4/5 for the theory part and 1/5 for the practical part.


Module: Laboratorio
-------
Written exam.

Reference books
Author Title Publisher Year ISBN Note
Crescenzi, P. - Gambosi, G. - Grossi, R. Strutture di Dati e Algoritmi Pearson Education Italia 2006 8871922735
Share