ECTS - University of Pisa
Scheda programma d'esame
ALGORITHMS: THEORY AND PRACTICE
LINDA PAGLI
Academic year2016/17
CourseCOMPUTER SCIENCE
Code008AA
Credits12
PeriodSemester 1 & 2
LanguageItalian

ModulesAreaTypeHoursTeacher(s)
ALGORITMICA E LABORATORIOINF/01LEZIONI96
LINDA PAGLI unimap
Programma non disponibile nella lingua selezionata
Learning outcomes
Knowledge
The goal is to introduce (basic) algorithms and data structures to solve problems on sequences, lists, trees and graphs, in efficient time and/or space. We will also deal with techniques for evaluating the complexity of algorithms and problems. Finally, we will experiment these algorithmic techniques by implementing some of them using the C language.
Assessment criteria of knowledge
The student will be assessed on her/his demonstrated ability to discuss and put into practice the main topics presented during the course.

Methods:

  • Final oral exam
  • Final written exam
  • Final laboratory practical demonstration
Teaching methods

Delivery: face to face

Learning activities:

  • attending lectures
  • participation in discussions
  • individual study
  • Laboratory work

Attendance: Advised

Teaching methods:

  • Lectures
  • laboratory
Syllabus
Short introduction to computational issues: decidability and tractability (P, NP, NPC, EXP-TIME). Computational complexity: computation model, input and output size, decision tree, lower and upper bounds, worst and avarage case. Divide-et-impera; recurrence relations, fundamental theorem. Algorithms on static/dinamic sequences: search and sorting. Stable marrigies problem and maximum sum subsequence. Dynamic Programming: LCS, Partition and Backpack. Combination and permutation generation. Greedy: Huffman and Backpack. Self-adjusting data structures: MTF, Amortized and competitive analyis. Trees representation and visit. Dictionaries: AVL, hash tables, trie. Randomized data structures: Skip List. Randomized Algorithms: Quicksort, Karp-Rabin. Graphs: representation and visit (DFS e BFS), DAG and topological sorting, minimum spanning tree, shortest paths, strongly connected components.
Bibliography
Any of: T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms. MIT Press, third edition, 2009. P. Crescenzi, G. Gambosi, R. Grossi. Strutture di dati e algoritmi: progettazione, analisi e visualizzazione. Addison-Wesley, 2005. Further bibliography will be indicated.
Updated: 14/11/2016 17:27