Course Unit Profile

<--- Back to Course Diagram

Basic Information

Course Unit Title: ALGORITHMS: THEORY AND PRACTICE

Course Unit Code: 008AA

Level of course unit

First Cycle Degree (laurea) Programme in Computer Science

Year of study

First year

Semester when the course is delivered

Second semester

Number of ECTS credits allocated: 12

Name of Lecturer(s):

Prof.: Anna Bernasconi
Email: anna.bernasconi@unipi.it

Prof.: Linda Pagli
Email: linda.pagli@unipi.it

Language of instruction

Italian

General Information

Learning outcomes

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.





Course contents

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.





Specific Information

Prerequisites, co-requisites, as a prerequisite for further study

Prerequisites

None.

Co-requisites

It is advised to take the following course "Discrete Mathematics and Linear Algebra" in the same semester.

Prerequisite for

None.

Mode of delivery

Delivery

face to face

Attendance

Advised

Teaching methods

Learning activities

Recommended or required reading

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.





Assessment methods and criteria

Assessment methods

Assessment criteria

The student will be assessed on her/his demonstrated ability to discuss and put into practice the main topics presented during the course.

Work placement

No

<--- Back to Course Diagram