Ammissione

Colloquio

Computer Science · Sapienza

Colloquio superato ✓

1 ottobre 2026 alle ore 11:45

In presenza

62%
13 rossi7 gialli32 verdi

Argomenti

Padronanza impostata manualmente

  • Algoritmi divide-and-conquer introduzione
  • The maximum-subarray problem
  • Strassen’s algorithm for matrix multiplication
  • The substitution method for solving recurrences
  • The recursion-tree method for solving recurrences
  • The master method for solving recurrences
  • Algoritmi di Sorting
  • Heapsort
  • Quicksort
  • Sorting in Linear Time
  • Counting sort
  • Radix sort
  • Bucket sort
  • Data structure introduzione
  • Stacks and queues
  • Linked lists
  • Implementing pointers and objects
  • Representing rooted trees
  • Hash Tables
  • Hash functions
  • Universal hashing
  • Open addressing
  • Perfect hashing
  • Binary Search Trees
  • Red-Black Trees
  • Dynamic Programming: introduzione
  • Matrix-chain multiplication
  • Elements of dynamic programming
  • Longest common subsequence
  • Optimal binary search trees
  • Greedy Algorithms: introduzione
  • Elements of the greedy strategy
  • Huffman codes
  • Matroids and greedy methods
  • A task-scheduling problem as a matroid
  • Elementary Graph Algorithms
  • Breadth-first search
  • Depth-first search
  • Topological sort
  • Minimum Spanning Trees
  • The algorithms of Kruskal and Prim
  • Single-Source Shortest Paths
  • The Bellman-Ford algorithm
  • Dijkstra’s algorithm
  • Difference constraints and shortest paths
  • Proofs of shortest-paths properties
  • All-Pairs Shortest Paths
  • Shortest paths and matrix multiplication
  • The Floyd-Warshall algorithm
  • Johnson’s algorithm for sparse graphs
  • Dimostrazione del teorema master
  • Priority queues

Rosso: non ne ho idea · Giallo: lo so, ma non benissimo · Verde: lo so perfettamente

Domande probabili

Prepara i punti chiave delle risposte

  1. 1
    Cosa è il metodo divide-and-conquer?
  2. 2
    Spiegami il Maximum subarray problem
  3. 3
    Spiegami l'algoritmo di Strassen
  4. 4
    Come funziona il metodo di sostituzione?
  5. 5
    Come funziona il metodo dell'albero ricorsivo
  6. 6
    Come funziona il master theorem
  7. 7
    Dimostra il teorema master
  8. 8
    A cosa serve il sorting?
  9. 9
    Quali sono i costi dei più famosi algoritmi di sorting?
  10. 10
    Come funziona heapsort?
  11. 11
    Come implementi le priority queues?
  12. 12
    Come è fatto il Quicksort? Quanto costa?
  13. 13
    Si può ordinare in tempo lineare?
  14. 14
    Come funziona il counting sort?
  15. 15
    Come funziona il bucket sort?
  16. 16
    Quali sono le strutture dati elementari? Come funzionano?
  17. 17
    Cosa sono le tabelle di hash?
  18. 18
    Come scegliamo le hash function?
  19. 19
    Cosa sono le famiglie universali di hash?

Checklist

Preparazione pratica

  • Esercizi Max-subarray problem pg 74 e 75
  • Riscrivere Max subarray problema
  • Esercizi Strassen pg 82 e 83
  • Esercizi sul metodo di sostituzione
  • Esercizi Master theorem
  • Esercizi recursion tree
  • Esercizi heapsort
  • Esercizi priority queues
  • Esercizi quicksort
  • Esercizi sorting in linear time
  • Esercizi counting sort
  • Esercizi radix sort
  • Esercizi bucket sort
  • Esercizi stack, queue e linked list
  • Esercizi hash tables e hash functions
  • Esercizi perfect hashing
  • Riscrivere Strassen

Informazioni

Dettagli organizzativi del colloquio