u n i g e . i t - Informatica a Genova

Corsi di Laurea in Informatica - Computer Science Degrees

DIBRIS - Valle Puggia

  • Full Screen
  • Wide Screen
  • Narrow Screen
  • Increase font size
  • Default font size
  • Decrease font size

80306 - Advanced Algorithms and Data Structures (2015/2016) Stampa

Course syllabus

Analysis and design methodologies: asymptotic notations and correctness/complexity of recursive algorithms (review), correctness of iterative algorithms, analysis of randomized algorithms, amortized analysis, dynamic programming and greedy algorithms.
Sorting: elementary algorithms and mergesort (review), quicksort, heapsort, lower bound, sorting in linear time.
Advanced data structures: heap, union-find structures
Graphs: definitions, representation, visits, topological sorting, strongly connected components, shortest paths (Djikstra algorithm), minimum spanning tree (Prim and Kruskal algorithms).
NP-completeness: complexity classes, NP-complete problems, approximation algorithms.




Elena Zucca

Other teachers

Paola Magillo

Teaching style

In presence

Lesson timetable

Monday: 9:00 - 11:00, room 710
Wednesday: 11:00 - 13:00, room 710
Thursday: 14:00 - 16:00, room 710



Course hour allocation

This course consists of 72 hours of lectures.