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

ModulesAreaTypeHoursTeacher(s)
ALGORITMICA E LABORATORIOINF/01LEZIONI96
PAOLO FERRAGINA unimap
ANDREA MARINO unimap
GIOVANNA ROSONE unimap
ROSSANO VENTURINI unimap
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
Skills

Design basic algorithms and data structures, solve basic problems on sequences, trees and graphs, be able to analyze the complexity of algorithms and problems.
Assessment criteria of skills

Oral and written exam plus a programming test in C language
Behaviors

Students will be able to appreciate the differences in designing iterative or recursive algorithms and which algorithmic design choices may positively or negatively impact in their efficiency. 
Assessment criteria of behaviors

Via the written and oral exam.
Prerequisites

Basics of Maths.
Co-requisites

Basic programming skills
Teaching methods

Delivery: face to face

Learning activities:

  • attending lectures
  • participation in discussions
  • individual study
  • Laboratory work for C programming

Attendance: Advised

Teaching methods:

  • Lectures
  • laboratory

 

Details on the home page of the course.
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: Knapsack and its variations. Trees representation and visit. Dictionaries: 2-3 trees, hash tables, trie. Randomized Algorithms: Quicksort, QuickSelect. Graphs: representation and visit (DFS e BFS), DAG and topological sorting.
Bibliography

T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms. MIT Press, third edition, 2009.

Further bibliography will be indicated.
Pagina web del corso

http://didawiki.di.unipi.it/doku.php/informatica/all-a/start
Class web page

http://didawiki.di.unipi.it/doku.php/informatica/all-a/start
Updated: 06/07/2017 10:19