## ALGORITHMS AND DATA STRUCTURES ALGORITMI E STRUTTURE DATI

#### Algorithms and Data Structures Algoritmi e Strutture Dati

A.Y. Credits
2012/2013 12
Lecturer Email Office hours for students
Valerio Freschi Monday, from 11 am to 1 pm

### Assigned to the Degree Course

Date Time Classroom / Location

### Learning Objectives

The aim of the course is to illustrate the main techniques for algorithms design and to describe and analyze the most known basic algorithms together with respective used data structures, with particular focus on computational complexity facets.

### Program

01. Introduction to algorithms and data structures:
01.01 Algorithms and their typologies
01.02 Correctness of an algorithm with respect to a problem
01.03 Complexity of an algorithm with respect to resource usage
01.04 Data structures and their typologies

02. Classes of problems:
02.01 Decidable and undecidable problems
02.02 Tractable and intractable problems
02.03 Cook theorem
02.04 NP-completeness

03. Complexity of the algorithms:
03.01 Notations to express the asymptotic complexity
03.02 Computing the complexity of non-recursive algorithms
03.03 Computing the complexity of recursive algorithms

04. Array algorithms:
04.01 Arrays: basic definitions and classical problems
04.02 Traversal algorithm for arrays
04.03 Linear search algorithm for arrays
04.04 Binary search algorithm for sorted arrays
04.05 Comparison criteria for sorting algorithms for arrays
04.06 Insertsort
04.07 Selectsort
04.08 Bubblesort
04.09 Mergesort
04.10 Quicksort
04.11 Heapsort
04.12 Priority queues based on binary heaps

05. List algorithms:
05.01 Lists: basic definitions and classical problems
05.02 Traversal, search, insertion and removal algorithms for lists
05.03 Insertion and removal algorithms for queues
05.04 Insertion and removal algorithms for stacks

06. Tree algorithms:
06.01 Trees: basic definitions and classical problems
06.02 Traversal and search algorithms for binary trees
06.03 Search, insertion and removal algorithms for binary search trees
06.04 Balancing criteria for binary search trees
06.05 Search, insertion and removal algorithms for red-black binary search trees

07. Graph algorithms:
07.01 Graphs: basic definitions and classical problems
07.02 Traversal and search algorithms for graphs
07.03 Topological sorting algorithm for direct acyclic graphs
07.04 Strongly connected component algorithm for graphs
07.05 Kruskal algorithm
07.06 Prim algorithm
07.07 Properties of the shortest path
07.08 Bellman-Ford algorithm
07.09 Dijkstra algorithm
07.10 Floyd-Warshall algorithm

08. String algorithms:
08.01 Strings: basic definitions and classical problems
08.02 String matching naive algorithm
08.03 Edit distance computation algorithm
08.04 Longest common subsequence algorithm

09. Selection and order statistics:
09.01 Basic definitions and problems
09.02 Heapselect
09.03 Randomized selection
09.04 Deterministic selection

10. Algorithmic techniques:
10.01 Divide-and-conquer technique
10.02 Dynamic programming
10.03 Greedy technique
10.04 Backtracking technique

11. Laboratory activity:
11.01 C language fundamentals: recall, editing, compilation, debugging
11.02 Pseudorandom number generators: rand and srand functions
11.03 Algorithms complexity experimental evaluation: timing and counters
11.04 Experimental comparison of sorting algorithms for arrays
11.05 Experimental comparison of search algorithms for binary trees
11.06 Implementation of graph algorithms: breadth-first and depth-first traversal algorithms, Dijkstra algorithm
11.07 Implementation of string algorithms: Edit Distance and LC

### Bridging Courses

Calculus, Procedural and Logic Programming

### Teaching, Attendance, Course Books and Assessment

Teaching

Theory lectures and laboratory exercises, both face-to face and on-line

Attendance

Although recommended, course attendance is not mandatory.

Course books

Cormen, Leiserson, Rivest, Stein, "Introduzione agli Algoritmi e alle Strutture Dati", McGraw-Hill, 2005.
(Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms", MIT Press, 2001.)
Demetrescu, Finocchi, Italiano, "Algoritmi e Strutture Dati", McGraw-Hill, 2004.
Crescenzi, Gambosi, Grossi, "Strutture di Dati e Algoritmi", Pearson/Addison-Wesley, 2006.
Sedgewick, "Algoritmi in C", Pearson/Prentice Hall, 2002.
(Sedgewick, "Algorithms in C", Addison-Wesley, 1997.)

Assessment

Individual project, written exam, and oral exam.

Disability and Specific Learning Disorders (SLD)

Students who have registered their disability certification or SLD certification with the Inclusion and Right to Study Office can request to use conceptual maps (for keywords) during exams.

To this end, it is necessary to send the maps, two weeks before the exam date, to the course instructor, who will verify their compliance with the university guidelines and may request modifications.

### Notes

The course is offered both face-to-face and on-line within the Laurea Degree Program in Applied Computer Science.

 « back Last update: 08/08/2012

#### Il tuo feedback è importante

Raccontaci la tua esperienza e aiutaci a migliorare questa pagina.

#### Il tuo 5x1000 per sostenere le attività di ricerca

L'Università di Urbino destina tutte le risorse che deriveranno da questa iniziativa alla ricerca scientifica ed al sostegno di giovani ricercatori.

15 22

#### Se sei vittima di violenza o stalking chiama il 1522, scarica l'app o chatta su www.1522.eu

Il numero, gratuito è attivo 24 h su 24, accoglie con operatrici specializzate le richieste di aiuto e sostegno delle vittime di violenza e stalking.

#### In contatto

Comunicati Stampa
Rassegna Stampa

#### Social

Università degli Studi di Urbino Carlo Bo
Via Aurelio Saffi, 2 – 61029 Urbino PU – IT
Partita IVA 00448830414 – Codice Fiscale 82002850418
2024 © Tutti i diritti sono riservati

Top