Insegnamento a.a. 2022-2023

• 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

• 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

• 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

• Face-to-face lectures
• Online lectures
• Exercises (exercises, database, software etc.)

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.

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.

The recommended textbook is: 

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

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