Università degli Studi di Urbino Carlo Bo / Portale Web di Ateneo


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

Didactics, Attendance, Course Books and Assessment

Didactics

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.

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

Condividi


Questo contenuto ha risposto alla tua domanda?


Il tuo feedback è importante

Raccontaci la tua esperienza e aiutaci a migliorare questa pagina.

Se sei vittima di violenza o stalking chiama il 1522

Il 1522 è un servizio pubblico promosso dalla Presidenza del Consiglio dei Ministri – Dipartimento per le Pari Opportunità. Il numero, gratuito è attivo 24 h su 24, accoglie con operatrici specializzate le richieste di aiuto e sostegno delle vittime di violenza e stalking.

Posta elettronica certificata

amministrazione@uniurb.legalmail.it

Social

Performance della pagina

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

Top