View syllabus
COMPETITIVE PROGRAMMING AND CONTESTS
ROSSANO VENTURINI
Academic year2021/22
CourseCOMPUTER SCIENCE
Code645AA
Credits6
PeriodSemester 1
LanguageEnglish

ModulesAreaTypeHoursTeacher(s)
COMPETITIVE PROGRAMMING AND CONTESTSINF/01LEZIONI48
ROSSANO VENTURINI unimap
Obiettivi di apprendimento
Learning outcomes
Conoscenze

L'obiettivo del corso è migliorare le capacità di programmazione e di problem solving degli studenti affrontando problemi algoritmici difficili e presentando tecniche che aiutino il loro ragionamento nell'implementazione di soluzioni corrette ed efficienti. L'importanza di queste competenze è stata riconosciuta dalle più importanti società di software in tutto il mondo, che utilizzano problemi algoritmici nelle loro interview per valutare i candidati all'assunzione.

Knowledge

The goal of the course is to improve programming and problem solving skills of the students by facing them with difficult problems and by presenting the techniques that help their reasoning in the implementation of correct and efficient solutions. The importance of these skills has been recognized by the most important software companies worldwide, which evaluate candidates in their job interviews mostly by the ability in addressing such difficult problems. A natural goal is to involve the students in the intellectual pleasure of programming and problem solving, also preparing them for the most important international online contests, such as TopCoder, HackerRank, CodeChef, Facebook Hacker Cup, Google Code Jam and so on, for internships in most important companies and their interviews. A desirable side-effect of the course could be to organize and prepare teams of students for the ACM International Collegiate Programming Contests.

 

Modalità di verifica delle conoscenze

Gli studenti dovranno risolvere problemi algoritmici simili a quelli visti a lezione.

Assessment criteria of knowledge

Problems will be posed to students to asses their knowledges and test their pregresses.

Capacità

Gli studenti miglioreranno le loro capacità di programmazione e di problem solving e saranno preparati per affrontare intervieww per interniship nelle più importanti società di software.

Skills

The students will

- improve their problem solving skill;

- improve their programming skils;

- be ready for interviews for internships in the most important companies.

Modalità di verifica delle capacità

Esame pratico e esame orale.

Assessment criteria of skills

Practical exam and oral exam.

Prerequisiti (conoscenze iniziali)

Conoscenza dei classici algoritmi e strutture di dati. 

Prerequisites

Knowledge of basic algorithms and data structures

Programma (contenuti dell'insegnamento)

 

C++ e la STL

- Applicazioni dell'ordinamento

- Strutture dati di base: code di priorità, alberi binari di ricerca e tabelle hash

- Strutture dati avanzate:  union-find, Fenwick tree, interval tree, range-minima query

- Algoritmi di base su stringhe

- Algoritmi di base su grafi

- Programmazione dinamica

- Geometria computazionale

Syllabus

- C++ and its standard template library

- Real-world applications of sorting

- Basic data structures: priority queues, search trees, and hash maps

- Advanced data structures: union-find, Fenwick tree, interval trees, range-minima query

- Basic string algorithms

- Basic graph algorithms

- Fast optimization with dynamic programming

- Computational geometry

Each topic of the above syllabus will be covered by

- offering a quick recap of the related concepts from an introductory class on algorithms;

- programming and engineering fast software solutions for real-life computational problems;

- learning how to recognize their applicability through contests and experimentation.

Updated: 26/07/2021 14:56