DATA STRUCTURES AND ALGORITHMS
Academic year and teacher
If you can't find the course description that you're looking for in the above list,
please see the following instructions >>
- Versione italiana
- Academic year
- 2016/2017
- Teacher
- GUIDO SCIAVICCO
- Credits
- 10
- Didactic period
- Primo Semestre
- SSD
- INF/01
Training objectives
- The course introduces the main methodologies for the specification, analysis and design of algorithms and static and dynamic data structures.
Topics (Knowledge):
- introduction to algorithms' analysis
- big O, big Omega, big Theta notation for functions' order of growth
- recursive algorithms, recurrences and solving methods
- sorting algorithms (InsertionSort,SelectionSort,Mergesort,Quicksort,HeapSort)
- sorting in linear time (es.: CountingSort)
- elementary data structures such as lists and queues
- binary search trees and their operations
- balanced trees (Red-Black trees) and their operations
- B trees and their operations
- graphs, direct and indirect graphs, weighted and non-weighted graphs
- graph visits, breadth and depth first
- topological sort
- minimum paths on weighted graphs
- string matching
By the end of the course, the student will be able to (Abilities):
- Analize an algorithm to solve a problem in terms of its complexity, and compare different solutions
- Recognize a sorting problem and choose or design the best algorithm to solve it
- Design and analyze an elementary or non elementary data structure to support an algorithm, offering suitable access methods and analyzing their complexity
- Design and analyze a tree-type data structure, offering suitable access methods and analyzing their complexity
- Design and analyze a graph-type data structure, offering suitable access methods and analyzing their complexity
- Recognize and solve the pattern matching problem. Prerequisites
- Elementary mathematics and basic programming skills, including the management of pointers.
Having successfully passed the exam of the course of Programming. Course programme
- 1 - Presentation
Essential definitions
The sorting problem with simple agorithms
Searching on sorted sets
The sorting problem with MergeSort
2 - The Divide and Conquer scheme
Orders of growth
Solving recurrences
3 - The heap data structure
The sorting problem with HeapSort
Priority queues and applications
QuickSort
The sorting problem in linear time
4 -
Introduction to data structures
Stack, Queues and Lists
Hash tables and conflicts
Complexity of access to an Hash table
5 -
Binary search trees and basic operations on them
Red Black Binary search trees and basic operations on them
6 - B-trees and basic operations on them
Introduction to graphs and breadth first search
7.(7 hours)
Depth first search visit of a graph
Direct aciclic graphs and topological sort
Strongly connected components of a direct graph
Building the components graph
8- Advanced data structures: disjoint sets
Minimum spanning trees
Kruskal algorithm for minimum spanning trees
Prim algorithm for minimum spanning trees
9- Shortest paths with single source on direct weighted graphs
Belmann-Ford algorithm
Shortest paths with single source on direct aciclic weighted graphs
Dijkstra algorithm
10-
The problem of pattern matching
A simple algorithm for patter matching
Rabin-Karp algorithm
DFA algorithm Didactic methods
- Lectures and exercises.
Weekly classes are composed by 5 hours of theoretical lecture and 2 hours of lab activities.
During lab session exercises will be proposed to be solved by students, which will be evaluated at precise moments comunicated during class. Learning assessment procedures
- The written exam is composed by 20 multiple-choice questions, with 4 alternatives each. Each correct answer scores 1.2/30. For each 4 mistakes or missed questions we count -1.2. The maximum possible mark on this exam is 24/30.
The part of the course that deals with lab and implementations is evaluated in countinous form during lab classes. The grade relative to the lab is from 0 to 6, with a minimum grade to be reached to be admitted to the exam is 3.
Final grade is composed by the sum of the mark on the written exam and the laboratory activities.
The mark might be increased, to a maximum of 3/30, by an oral exam decided by the teacher.
Test questions - with precisely one correct answer of 4 possible options, range over the entire program and aim to establish if the students possess a knowledge of the type:
- basic, with questions of pure knowledge
- applicative, with questions relative to algorithms' execution, their behaviour, possible variations, and their use
- deeper understanding, with questions concerning solutions to more complex problems or problems that require some intuition. Reference texts
- 1)Introduction to Algorithms, 3rd edition
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
ISBN: 9788838665158. Pub Date: June 2010. Pages: 1030.
2)The Algorithm Design Manual, 2nd edition
Steven Skiena
ISBN: 9781848000698. Pub Date: 2012.
Suggested the original version not translated to Italian.
3)Handouts given by the professor.
