THEORY OF ALGORITHMS AND DATA STRUCTURES<br />
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
- 6
- 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
- Basic mathematics. 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
- If the sanitary situation will come back to normality, there will be 5 hours of class per week. In the version of this course for the Degree in Mathematics, there will be no lab. If the current sanitary emergency will last longer, we shall schedule a weekly telematic meeting, and students will follow the classes from the YouTube channel.
Learning assessment procedures
- The written exam is composed by 20 multiple-choice questions, with 4 alternatives each. Each correct answer scores 1.5/30. For each 5 mistakes or missed questions we count -1.5. The maximum possible mark on this exam is 30/30. Two additional points may be assigned with homeworks. The final grade is composed by the sum of all marks. The mark might be increased, by 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
- ************
*ATTENTION*: the handouts will be published on Google ClassRoom. Subscription is mandatory.
CODE: gmqon6n
************
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.
