Algorithms and data structures
- Overview
- Assessment methods
- Learning objectives
- Contents
- Bibliography
- 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 knowledge of the specific domain terminology is implicitly tested, as questions and problem specification use this terminology. Similarly, the capability of an autonomous analysis of complexity issues is detected through questions that require reasoned choices of algorithms and data structures depending on the context.
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 design and the analysis of algorithms.
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.
In addition to slides and lecture notes distributed via the e-learning platform, the reference texts are:
• R. Sedgewick, K. Wayne, Algorithms, 4th Edition, Addison-Wesley Professional 2011;
• Thomas H. Cormen - Charles E. Leiserson - Ronald L. Rivest - Clifford Stein, Introduction to algorithms, 3rd Edition (The MIT Press), 2013
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.