Insegnamento a.a. 2024-2025

30540 - COMPUTER SCIENCE - MODULE 2 (COMPUTING THEORY AND ALGORITHMS)

Department of Computing Sciences

Course taught in English
code 30540 and the code 30539 ‘Computer Science - Module 1 (Introduction to Computer Science and Programming) are respectively the first and the second module of the course code 30538 ‘Computer Science’

Class timetable
Exam timetable
BAI (8 credits - II sem. - OB  |  INF/01)
Course Director:
GIULIO MALAVOLTA

Classi: 27 (I/II sem.)
Docenti responsabili delle classi:
Classe 27: FABRIZIO IOZZI


Conoscenze pregresse consigliate

Students should have some familiarity with programming in an imperative programming language such as Java, C++ or Python, and be able to translate an algorithm formulated in pseudocode into working code in one such language. Students should be familiar with basic data structures such as lists, queues and binary trees, and with basic algorithms such as sorting and graph traversal. This course will emphasize the rigorous analysis of algorithms, and hence it will be helpful to possess the mathematical maturity that comes from having taken a proof-based mathematical course.

Mission e Programma sintetico

MISSION

Students will learn how to apply algorithm design techniques to new problems, and how to design an efficient algorithm, rigorously prove its correctness, and rigorously analyze the way in which the running time and memory requirements scale with the size of the input.

PROGRAMMA SINTETICO

  • Divide-and-conquer algorithms and the solution of recurrence equations with the Master Theorem. Example will include mergesort, randomized linear-time median-finding, and fast multiplication of large integers
  • Review of graph algorithms. Introduction to directed and undirected graphs, notions of paths and connectivity. DFS exploration and use of DFS to find connected components in an undirected graph, to find topological sort of directed acyclic graphs, and find the strongly connected components of a general directed graph
  • Shortest paths algorithms. Dijkstra's alorithm
  • Dynamic programming. Examples will include shortest paths in graphs with negative edge weights, all-pairs shortest paths, knapsack and subset sum, edit distance and string alignment
  • Greedy algorithms. Examples will include minimum spanning trees and Huffman codes
  • Flow and cut problems. Max-Flow / Min-Cut theorem, Ford-Fulkerson methodology, Edmonds-Karp analysis, Karger's randomized algorithm for global min-cut, reduction of bipartite matching to Max Flow
  • Linear Programming. Formulating optimization problems as linear programming, duality, simplex algorithm
  • NP-completeness. Cook's theorem and some examples of NP-complete problems
  • Heuristic algorithms for NP-complete problems. Overview of techniques for the design of approximation algorithms

Risultati di Apprendimento Attesi (RAA)

CONOSCENZA E COMPRENSIONE

Al termine dell'insegnamento, lo studente sarà in grado di...
  • Master a number of algorithmic techniques, including divide-and-conquer, greedy, dynamic programming, graph traversal, and reduction to linear programming
  • Reason about the correctness of algorithms
  • Reason about the running time and the memory use of algorithms
  • Master the concept of NP-compleness

CAPACITA' DI APPLICARE CONOSCENZA E COMPRENSIONE

Al termine dell'insegnamento, lo studente sarà in grado di...
  • Design algorithms for problems that they have never seen before
  • Prove correctness of algorithms of their design
  • Analyze running time and memory use of algorithms of their design
  • Identify flaws in proposed algorithms that are not correct
  • Prove NP-completeness results

Modalità didattiche

  • Lezioni frontali
  • Lezioni online
  • Esercitazioni (esercizi, banche dati, software etc.)

DETTAGLI

Online lectures will be developed as needed if face-to-face lectures cannot be attended by some or all students.

 

Exercises will be given, but not graded, throughout the course, for students to test their understanding of the material.


Metodi di valutazione dell'apprendimento

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

STUDENTI FREQUENTANTI E NON FREQUENTANTI

The final grade will come 40% from a written partial exam, 55% from a written general exam, and 5% from the evaluation of individual assignments. Exams and assignments include questions that test the students' understanding of the basic concepts presented in the course, and questions that require the design and analysis of an algorithm for a new problem.


Materiali didattici


STUDENTI FREQUENTANTI E NON FREQUENTANTI

The recommended textbook is: 

  • Dasgupta, Papadimitriou, Vazirani Algorithms 2006, McGraw-Hill

 

Additional lecture notes will be posted on bboard and on the class website

Modificato il // :