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
- 2022/2023
- 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
- hash tables
- 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, visits, topological sort, cycle detection, minimum spanning trees, minimum paths
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 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, definitions, course structure, exams. (1 hour)
2.Order of growth of functions, solving recurrences. (8 hours)
3.Elementary data strucures: stacks, queues, priority queues. (6 hours)
4.Sorting problem: elementary algorithms, non-elementary algorithms, linear sorting algorithms, limits for sorting with comparisons. (18 hours)
5.Data structures not based on trees: lists, hash tables, disjoint sets structures. (8 hours)
6.Data structures based on trees: binary search trees, red-black trees, B trees.(18 hours)
7.Graphs: visits, topological sort, strongly connected components, minimum spanning trees, shortest paths. (18 hours)
8.Computability and complexity, existence of non-computable functions, the classes P and NP. (8 hours) Didactic methods
- standard classes for both theory and practices. In addition, students have the possibility of watching all recorded classes (academic year: 20/21) on the professor's YouTube page.
Learning assessment procedures
- The written exam is composed multiple-choice questions, sometimes with the requirement of adding comments and show the work. It is mandatory to turn in at least one of the proposed lab exercises to be admitted to take the final exam. The 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
- ************
*ATTENTION*: the handouts will be published on Google ClassRoom. Subscription is mandatory.
************
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.
