First Cycle Degree (laurea) Programme in Computer Science
Prof.: Anna Bernasconi
Prof.: Linda Pagli
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.
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.
It is advised to take the following course "Discrete Mathematics and Linear Algebra" in the same semester.
face to face
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.
The student will be assessed on her/his demonstrated ability to discuss and put into practice the main topics presented during the course.
Per informazioni scrivete a firstname.lastname@example.org.