To show the organization of the course that includes this module, follow this link 
Course organization
The course covers basic concepts for the formulation and algorithmic solution of complex problems. Problems are formulated and solved in terms of abstract mathematical structures (lists, queues, graphs, ...). Algorithms are evaluated and compared based on the quantities of the requested resources. The course also focuses on the role of data structures in the formulation and evaluation of new algorithms.
The course consists of 64 hours of front lectures, includiong 20 hours of recitation sections where studens must solve guided problems.
Specific arguments include
Complexity: asymptotic notation, resolution ofrecurrence equations, amortized analysis.
Selection and sorting: insertion sort, merge sort, heap sort, quick sort, randomized quick sort. Complexity of sorting algorithms, lower bounds on comparison based algorithms. Sorting in linear time, counting sort, radix sort, bucket sort. Selection, minimum, maximum, randomized select, linear time select.
Data structures: queues, stacks, lists, heaps, binary search trees, RB-trees, binomial heaps, disjoint sets. Extension of a data structure.
Graphs: definition and representation, breadth first search, depth first search, topological sorting, connected components, minimum spanning trees (Prim and Kruskal), shortest paths (Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson), maximum flow (Ford-Fulkerson, Karp), maximal matching on bipartite graphs.
The exam for the "theory" module consists of a written test of two hours containing three problems of increasing difficulty that evaluate knowledge as well as capacity of reasoning. Lhe written test is passed with a grade of at least 18/30. The student may bring a sheet of paper, A4 format, hand-written on both sides. On each side the student must write name and id number.
© 2024 | Verona University
******** CSS e script comuni siti DOL - frase 9957 ********p>
