30540 - COMPUTER SCIENCE - MODULE 2 (COMPUTING THEORY AND ALGORITHMS)
Course taught in English
Go to class group/s: 27
Synchronous Blended: Lezioni erogate in modalità sincrona in aula (max 1 ora per credito online sincrona)
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.
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.
- 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