Course 2024-2025 a.y.

20602 - COMPUTER SCIENCE (ALGORITHMS)

Department of Computing Sciences

Course taught in English

Student consultation hours
Class timetable
Exam timetable
DSBA (6 credits - II sem. - OP  |  INF/01)
Course Director:
ADAM POLAK

Classi: 31 (I/II sem.)
Docenti responsabili delle classi:
Classe 31: ADAM POLAK


Conoscenze pregresse consigliate

To feel comfortable in this course students should be fluent in a modern programming language (e.g., Python or C/C++) and familiar with elementary calculus, linear algebra, and discrete mathematics.

Mission e Programma sintetico

MISSION

Efficient algorithms lie at the core of computing. The course will teach the students the fundamentals of designing and analysing algorithms. The students will learn to apply design paradigms when designing their own algorithms, and will be able to estimate the computational complexity and resource requirements of algorithms they encounter. They will be familiarized with important algorithms and will use them as building blocks in their own work.

PROGRAMMA SINTETICO

Basics
– Asymptotic notation
– Sorting
– Searching

 

Data structures
– Arrays, lists, stacks, queues
– Heaps
– Binary trees

 

Graphs
– BFS, DFS
– Shortest paths: Dijkstra, Bellman–Ford

 

Algorithm design techniques
– Dynamic programming
– Greedy approach
– Divide and conquer

 

Cryptography
– Basic notions
– Secret-key encryption
– Public-key schemes, RSA


Risultati di Apprendimento Attesi (RAA)

CONOSCENZA E COMPRENSIONE

Al termine dell'insegnamento, lo studente sarà in grado di...
  • describe classic algorithms and algorithm design techniques;
  • analyse correctness and efficiency of algorithms;
  • define basic concepts from computational complexity;
  • understand sources of hardness of computational problems.

CAPACITA' DI APPLICARE CONOSCENZA E COMPRENSIONE

Al termine dell'insegnamento, lo studente sarà in grado di...
  • implement algorithms covered in class;
  • model problems stated in natural language as formal computational problems;
  • design and implement algorithms, and analyse their correctness and efficiency;
  • test, debug, and optimize implementations of algorithms.

Modalità didattiche

  • Lezioni frontali
  • Esercitazioni (esercizi, banche dati, software etc.)
  • Lavori/Assignment individuali

DETTAGLI

Homework exercises will involve designing and analysing algorithms for posted problems. Students will present their solutions in class and/or write down and submit their solutions.

 

There will be also individual programming assignments that involve implementing algorithms learned in class. Students will submit their solutions via an online system that will provide them with live feedback.


Metodi di valutazione dell'apprendimento

  Accertamento in itinere Prove parziali Prova generale
  • Prova individuale scritta (tradizionale/online)
    x
  • Assignment individuale (relazione, esercizio, dimostrazione, progetto etc.)
x    

STUDENTI FREQUENTANTI E NON FREQUENTANTI

There will be a final exam, homework assignments, and programming assignments.

 

Assignments are not mandatory. Each completed assignment guarantees a certain percentage of the final grade and decreases the contribution of the final exam by the same percentage. For instance, if a student completes assignments worth in total 40%, their final grade (on the scale from 0 to 100) is calculated as 40 + 0.6 * [exam-result].

 

The exam and homework assignments will test the students' understanding of basic concepts presented in class, and their ability to apply learned algorithms and algorithm design techniques to new computational problems stated in natural language, explain and implement proposed solutions, and reason about their correctness and efficiency. The programming assignments will test the students' ability to understand and implement algorithms learned in class.
 


Materiali didattici


STUDENTI FREQUENTANTI E NON FREQUENTANTI

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, MIT Press, 3rd edition.

 

Additional materials – e.g., research papers, technical reports, notes – will be posted on the course website throughout the semester.
 

Modificato il // :