DALMINE
Overview
Date/time interval
Syllabus
Course Objectives
The goal of the course is to study and learn how to solve algorithmic problems typically found in coding competitions. The focus is mainly on understanding how to use fundamental algorithms, data structures, and common approaches (or patterns) to produce solutions with low computational complexity. At the end of the course the student will be able to apply the acquired knowledge even outside of the specific coding competitions domain, and in general she will be able to produce solutions that perform well with problems with large input.
Course Prerequisites
There are no formal requirements. It is expected that the student is already familiar with programming and asymptotic notation.
Teaching Methods
Lectures with theoretical insights accompanied by interactive programming sessions and laboratory exercises. The teacher will introduce the student to a coding problem, then explain how to solve it efficiently, and finally will code the solution interactively.
A copy of all the material used by the teacher will be available on the university e-learning platform.
Assessment Methods
A written exam and a mandatory project.
The written exam is structured in 2/3 exercises that cover the first 6 modules of the program. The exam's objective is to verify that the student has learned the algorithms and concepts explained during the course. It is customary for an exercise to appear that requires the implementation of an algorithm studied in class and a coding interview-style exercise where the ability to apply the notions learned during the course is evaluated in order to solve an application problem. The time available is usually 1.5 or 2 hours.
The mandatory project is focused on the evaluation of the modules on evolutionary programming and search algorithms.
The scores obtained in the written exam and in the project both contribute to the definition of the final grade (in proportion to the number of hours dedicated to the modules).
Contents
The course is organized in units.
- Introduction to coding contests. The student will be introduced to competitive programming. The student will review the concept of computational complexity (time and space), used to determine the quality of a solution. The student will review the asymptotic notation.
- Choice of the programming language. The student will understand the advantages and drawbacks when using different programming languages in the domain of coding competitions. The student will review the fundamentals of Python programming. Dedicated problems will be used to study the differences between array, list and hashmap. Analysis and evaluation of dynamic resizing.
- Sorting. The student will implement the most used approaches to sort numbers. The student will understand the properties of each sorting method. The student will also learn how to combine different methods (i.e., hybrid approach) to sort numbers efficiently, even when there are tight constraints (e.g., limited memory).
- Data structures. The student will study and implement fundamental structures such as Stack, Queue (even with priority), Heap, Binary Tree (possibly with self-balancing), Graph, LRU Cache, Trie, Union-Find, Segment Tree, Sparse Table. A selected list of coding questions will be used to highlight the advantage of using each structure.
- Dynamic programming and recursion. The student will study how to use dynamic programming and recursion to solve algorithmic problems. The student will also study the problems associated with the two approaches.
- Solution of problems by category. The student will study and solve a selection of problems from common categories. When studying strings for example, the student will learn how to search for prefixes efficiently.
- Evolutionary and genetic programming. The student will study the principles and concepts common to evolutionary computation. We will study in detail evolutionary programming (concepts such as population, mutations, selection) and genetic programming (concepts such as genotype, crossover, fitness).
- Search Algorithms. Students will be introduced to the use of search algorithms, with a focus on basic and advanced techniques (metaheuristics), for the development of efficient software solutions in various application contexts.