Algorithms and data structures
- Overview
- Assessment methods
- Learning objectives
- Contents
- Full programme
- Teaching methods
- Contacts/Info
The knowledge of a programming language and of the main elements of a computer architecture is highly recommended. More precisely, it is necessary for the student to know how to write a simple program in Java (the language used in the course). The knowledge and skills necessary for a profitable learning of this teaching are given in the fundamental courses of the first year of Programming and of Computer Architecture.
The objective of the exam is to verify the acquisition of the knowledge and skills described in the "Educational goals" section, assessing the level of knowledge and the ability to put into practice the design techniques seen in class.
The exam consists of a written test to be held in the classroom, followed by an oral test in case of a positive outcome. The written test - of an approximate duration of 120 minutes - includes a series of 5 questions related to the topics covered in class (6 points available for each question). A positive outcome (assessed in thirtieths) allows the access to the oral exam. The oral exam consists of a joint vision of the written test. The student is informed about the correction criteria and called to provide any clarifications, thus allowing the teacher to verify the correctness of the assigned grade, making changes if necessary. The final mark is given by the sum of the marks obtained in the written (weight 90%) and oral (weight 10%) exams.
The knowledge of the specific domain terminology is implicitly tested, as questions and problem specification use this terminology.
The course aims to make students able to apply basic knowledge about the main data structures and the main associated algorithms. To this end, students will learn the basic techniques for designing and analysing algorithms, together with the ability to solve the most classic problems related to data processing.
Eventually, students will be able:
1. to understand the importance of the main features of an abstract model of computation, as well as the importance of the complexity of an algorithm from a practical point of view;
2. to determine the algorithms and the data structures that are most suited in a given applicative context;
3. to know and to apply the main algorithm design techniques.
Furthermore, the student will achieve the capability of an autonomous analysis of complexity issues related to the design of efficient algorithms, as well as a knowledge of the terminology in use in the context of algorithm design and analysis.
Lectures deal with the following topics:
Models of computation and complexity (14 h, educational goal 1)
- Modeling the problem, complexity of algorithms, asymptotic notations (6h)
- Models of computation (RAM, RASP) and cost criteria (6h)
- Characteristics of procedural languages (2h)
Basic algorithms and elementary data structures (20 h, educational goal 2)
- elementary data structures (arrays, matrices, lists, stacks, queues) (6h)
- graphs and trees, representation and traversal algorithms (10h)
- the sorting problem: general aspects and elementary algorithms (4h)
Advanced algorithms and data structures (28 h, educational goal 2)
- digital sorting and advanced sorting algorithms (6h)
- Heap e Heapsort (2h)
- Hash tables (4h)
- Binary search trees (6h)
- Balanced trees (2-3, 2-3-4, red-black) (8h)
- Partitions (Union and Find) (2h)
Design techniques (10 h, educational goal 3)
- Divide and conquer (2h)
- dynamic programming (4h)
- greedy algorithms (4h)
Topics will be addressed using the Java programming language as a reference. Nevertheless, many of the topics covered in the course are of general validity, and the proposed techniques are also applicable with different languages.
Problems and algorithms: correctness and efficiency. Time and space complexity. Worst case, Best case and Average case complexity. Relationship between algorithm complexity and hardware speed.
The asymptotic notations. Properties of asymptotic notations.
The RAM machine, architecture and instruction set. State of the RAM machine, value of the operands and operational semantics of instructions. Computation and semantics. Uniform cost criterion. Logarithmic cost criterion. The RASP machine. RAM-RASP simulation. Church-Turing's Thesis and Extended Church's Thesis.
The language AG and the complexity of its commands. Subroutines and rules for passing parameters. Pointers.
Elementary data structures: arrays and their implementation on a RAM machine. Multi-dimensional arrays (Matrices). Storage maps. Records and their implementation.
The list data structure. List: derived operations. Representation of lists through parallel vectors. Search for an item in a list. Implementation of lists using records and pointers. A simple dynamic memory manager. Circular lists: the Josephus's problem. Restricted lists: stacks and queues. Complexity of operations on stacks and queues.
Graphs: basic definitions. Connected components of a graph. Representation of graphs. Trees: basic definitions. Rooted trees, k-trees. Ordered rooted trees, binary trees and tree representation. Mathematical properties of trees. Complete trees and geometric series. Crossing of graphs: in breadth and in depth visits. Trees traversal. Tail recursion elimination. Preorder, inorder and postorder iterative procedures.
The sorting problem: basic definitions. Number of inversions in a sequence. A lower bound for the sorting problem. Elementary sorting methods: selection sort, insertion sort, bubble sort (non-adaptive and adaptive version). Complexity of elementary ordering methods: particular cases.
Digital sorting: distribution counting. Lexicographic ordering and Bucketsort.
Two-way merge (arrays and lists).
"Divide and conquer" algorithms and recurrence equations. Mergesort (top-down) and related complexity analysis. Iterative mergesort (bottom-up). Comparison between recursive and iterative mergesort trees. Quicksort: partitioning and recursive base version. Quicksort complexity analysis. Iterative quicksort and advanced versions.
Priority Queue (Heap). Construction of a heap: top-down and bottom-up methods. Complexity analysis of heap operations. Heapsort: complexity and properties.
Heterogeneous algebras.
Tables and hash functions, modular hash. Collisions, static hash with separate chaining, static hash with open addressing. Dynamic hash.
Binary Search Trees (BST). Operations on BST. Rotation and root insertion. Complexity of operations on BST.
2-3 Trees: properties and complexity of operations.
2-3-4 Trees: definition and properties. Insertion and deletion.
Red-black trees. Relationship between 2-3-4 trees and red-black trees. The decomposition of full nodes in RB trees. Insertion and deletion in RB trees.
The heterogeneous algebra Partitions of A and the Union and Find operations.
Optimization problems. Independence systems and greedy algorithms. Matroids (Rado's theorem). Minimum Spanning Tree: Kruskal's and Prim's algorithms (with complexity analysis).
Shortest paths in a graph (from a source node): the Dijkstra's algorithm.
Dynamic programming: general scheme. The problem of multiplying n matrices and the solution by means of a recurrence equation. Transitive closure of a graph, shortest paths in a weighted graph.
Lectures (72 hours). Each lecture presents both theoretical and practical issues, as well as examples. The educational material is available in advance. The student is invited to be present in the classroom after having read the lesson material. The lesson will be carried out in such a way as to increase interaction, discussion and consequently learning.
The teacher receives by appointment, upon request by e-mail to name.surname@uninsubria.it. The teacher responds only to e-mails signed and coming from the students.uninsubria.it domain.